Proof of Theorem 7.1, p. 13 — the case s = 1: ‖v₁ − T(v₁)‖∞ ≤ λ‖v₀ − T(v₀)‖∞ ≤ λ′‖v₀ − T(v₀)‖∞
ProvedAccelVI.SafeAVI.first_step_residualaccelerationbellman-residualmarkov-decision-processp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1value-iteration
Let be a valid finite MDP with a nonempty action set and Bellman operator , let and , and let be the iterates of Safe Accelerated Value Iteration (Algorithm 1) started at , so that . Then
This is the base case of the induction in the proof of Theorem 7.1, which shows that the Bellman residual of the S-AVI iterates decays like .
Formalization Note Both inequalities of the chain are stated, as a conjunction. is the iterate savi M lam' α γ v0 1, which is by definition.
Preamble
import Mathlib import Definitions.Def_AccelVI_SafeAVI_Setting
Formal statement
namespace AccelVI.SafeAVI
theorem first_step_residual {S A : Type*} [Fintype S] [DecidableEq S] [Fintype A] [Nonempty A]
(M : MDP S A) (hM : M.Valid) (lam' α γ : ℝ) (hlam' : M.lam ≤ lam') (hlam'1 : lam' < 1)
(hα : 0 < α) (hγ : 0 < γ) (v0 : S → ℝ) :
‖savi M lam' α γ v0 1 - bellman M (savi M lam' α γ v0 1)‖ ≤ M.lam * ‖v0 - bellman M v0‖ ∧
M.lam * ‖v0 - bellman M v0‖ ≤ lam' * ‖v0 - bellman M v0‖ := by sorry
end AccelVI.SafeAVI
Source
Goyal & Grand-Clément, A First-Order Approach to Accelerated Value Iteration, arXiv:1905.09963v7, p. 13, proof of Theorem 7.1, second display
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.