Proof of Theorem 7.1, p. 14 — ‖v − v*‖∞ ≤ (1 − λ)⁻¹ ‖v − T(v)‖∞
ProvedAccelVI.SafeAVI.error_le_residualbellman-operatorbellman-residualcontractionmarkov-decision-processp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a valid finite MDP with a nonempty action set and Bellman operator , and let be a fixed point of , . Then for every ,
The distance to the optimal value function is thus controlled by the Bellman residual, which is computable. In the proof of Theorem 7.1 this converts the geometric decay of the residual into the geometric decay of the error.
Formalization Note The paper applies the bound to the iterates ; nothing about them is used, so it is stated for an arbitrary vector . The paper's line drops a parenthesis (); the intended is stated. (the unique fixed point of , p. 3) enters as a vector with .
Preamble
import Mathlib import Definitions.Def_AccelVI_SafeAVI_Setting
Formal statement
namespace AccelVI.SafeAVI
theorem error_le_residual {S A : Type*} [Fintype S] [DecidableEq S] [Fintype A] [Nonempty A]
(M : MDP S A) (hM : M.Valid) (vstar : S → ℝ) (hfix : bellman M vstar = vstar) (v : S → ℝ) :
‖v - vstar‖ ≤ (1 - M.lam)⁻¹ * ‖v - bellman M v‖ := 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 after the display of ‖v_s − v*‖∞
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.