Theorem 7.1, p. 13 — Safe Accelerated Value Iteration converges to v*, with v_s = v* + O(λ′^s) for all s ≥ 0
ProvedAccelVI.SafeAVI.theorem_7_1Let be a finite MDP with a nonempty action set, in which every is a probability distribution over next states and , let be its Bellman operator and its fixed point, (the optimal value function). Let , let be any step sizes, and let be the iterates of Safe Accelerated Value Iteration (Algorithm 1) from any . Then converges to , and there is a constant such that
that is, for all .
S-AVI alternates accelerated value-iteration steps with plain value-iteration steps. The theorem says this safeguard restores the worst-case guarantee of value iteration: for the rate matches that of value iteration, which by the lower bound of Theorem 6.3 cannot be improved by any first-order method on all MDPs, while larger admits more accelerated steps.
Formalization Note is Mathlib's sup norm on S → ℝ. ", " is encoded as one constant valid for every , and convergence as Filter.Tendsto to nhds vstar. enters as a vector with , which exists and is unique for a valid MDP since is a -contraction. The hypotheses are those of Algorithm 1; the constant is not specified, as in the paper.
import Mathlib import Definitions.Def_AccelVI_SafeAVI_Setting
namespace AccelVI.SafeAVI
theorem theorem_7_1 {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 vstar : S → ℝ) (hfix : bellman M vstar = vstar) :
Filter.Tendsto (savi M lam' α γ v0) Filter.atTop (nhds vstar) ∧
∃ C : ℝ, ∀ s : ℕ, ‖savi M lam' α γ v0 s - vstar‖ ≤ C * lam' ^ s := by sorry
end AccelVI.SafeAVI
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.