Proof of Theorem 7.1, p. 14 — ‖v_s − T(v_s)‖∞ ≤ λ′^s ‖v₀ − T(v₀)‖∞ for every s ∈ ℕ
ProvedAccelVI.SafeAVI.residual_geometricaccelerationbellman-residualmarkov-decision-processp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paper
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 . Then for every ,
The Bellman residual of the safe scheme therefore decays geometrically at rate , whichever mix of accelerated and value-iteration steps the test in Step 5 selects. Combined with the bound of the distance to by the residual, it yields the rate of Theorem 7.1.
Formalization Note is Mathlib's sup norm on S → ℝ; is savi M lam' α γ v0 s.
Preamble
import Mathlib import Definitions.Def_AccelVI_SafeAVI_Setting
Formal statement
namespace AccelVI.SafeAVI
theorem residual_geometric {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 → ℝ) (s : ℕ) :
‖savi M lam' α γ v0 s - bellman M (savi M lam' α γ v0 s)‖ ≤ lam' ^ s * ‖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. 14, proof of Theorem 7.1, sentence beginning "Overall, we have proved by recursion"
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.