(6.2)–(6.4), p. 12 — on the chain, first-order iterates have ‖v_s − T(v_s)‖∞ ≥ λ^s for 1 ≤ s ≤ n − 1
ProvedAccelVI.LowerBound.residual_lower_boundfirst-order-methodslower-boundmarkov-decision-processp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let , , let be the Bellman operator of the -state chain of Figure 1, and let be first-order iterates for . Then for every with ,
This is the chain of inequalities (6.2)–(6.4) in the proof of Theorem 6.3: the residual of any first-order iterate stays above for the first steps.
Formalization Note. is Mathlib's sup norm on Fin n → ℝ; is natural-number subtraction, so with the hypotheses force and .
Preamble
import Mathlib import Definitions.Def_AccelVI_LowerBound_Setting
Formal statement
namespace AccelVI.LowerBound
theorem residual_lower_bound (n : ℕ) (lam : ℝ) (h0 : 0 < lam) (h1 : lam < 1) (v : ℕ → Fin n → ℝ)
(hv : IsFirstOrder (bellman (chainMDP n lam)) v) (s : ℕ) (hs1 : 1 ≤ s) (hs2 : s ≤ n - 1) :
lam ^ s ≤ ‖v s - bellman (chainMDP n lam) (v s)‖ := by sorry
end AccelVI.LowerBound
Source
Goyal & Grand-Clément, A First-Order Approach to Accelerated Value Iteration, arXiv:1905.09963v7, p. 12, proof of Theorem 6.3, displays (6.2)–(6.4)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.