Proof of Theorem 6.3, p. 12 — first-order iterates on the chain satisfy v_{s,i} = 0 for i ≥ s + 1
ProvedAccelVI.LowerBound.support_recursionfirst-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 : and . Then for every and every state ,
The reward sits only at state 1 and moves one state per application of ; this support property is what forces every first-order method to need steps before it sees state .
Formalization Note. States are 0-based: the paper's state is index , so "" is .
Preamble
import Mathlib import Definitions.Def_AccelVI_LowerBound_Setting
Formal statement
namespace AccelVI.LowerBound
theorem support_recursion (n : ℕ) (lam : ℝ) (h0 : 0 < lam) (h1 : lam < 1) (v : ℕ → Fin n → ℝ)
(hv : IsFirstOrder (bellman (chainMDP n lam)) v) (s : ℕ) (k : Fin n) (hk : s ≤ (k : ℕ)) :
v s k = 0 := 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, recursion paragraph
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.