Lemma 5.2, p. 8 — x_s = x^π + B_π^{s−1}(x_1 − x^π) for all s ≥ 1
ProvedAccelVI.AVC.lemma_5_2accelerationlinear-recursionmarkov-decision-processp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1value-iteration
Let be a finite MDP with and let be a policy, with reward vector , transition matrix and value function . Let be the iterates of Accelerated Value Computation with the step sizes (4.1), and , started from arbitrary . Put and , and let be the matrix (5.1). Then
The lemma turns the analysis of A-VC into that of the powers of a single matrix. It holds for every policy; reversibility is not needed.
Formalization Note. is the function on equal to on the first copy and on the second; the hypothesis keeps meaningful. is the discounted reward series (the published PolicyValue). The paper's proof ends with "", a slip; the statement, with , is the one posed.
Preamble
import Mathlib import Definitions.Def_mm_basic import Definitions.Def_AccelVI_AVC_Setting
Formal statement
namespace AccelVI.AVC
variable {S A : Type*} [Fintype S] [DecidableEq S] [Fintype A]
/-- Lemma 5.2, p. 8: with `x^π = (v^π, v^π)` and `x_s = (v_s, v_{s−1})`, the A-VC iterates with
step sizes (4.1) satisfy `x_s = x^π + B_π^{s−1}(x_1 − x^π)` for every `s ≥ 1`. -/
theorem lemma_5_2 (M : MDP S A) (hM : M.Valid) (pol : S → A → ℝ) (hpol : FoundationsML.ReinforcementLearning.IsPolicy pol)
(v0 v1 : S → ℝ) (s : ℕ) (hs : 1 ≤ s) :
xvec (avc M pol (alphaAVC M.lam) (gammaAVC M.lam) v0 v1) s =
xPi M pol + ((Bpol M pol) ^ (s - 1)).mulVec
(xvec (avc M pol (alphaAVC M.lam) (gammaAVC M.lam) v0 v1) 1 - xPi M pol) := by sorry
end AccelVI.AVC
Source
Goyal & Grand-Clément, A First-Order Approach to Accelerated Value Iteration, arXiv:1905.09963v7, p. 8, Lemma 5.2
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.