Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 7.1, p. 13 — Safe Accelerated Value Iteration converges to v*, with v_s = v* + O(λ′^s) for all s ≥ 0

Proved
AccelVI.SafeAVI.theorem_7_1

by mikedeng1 · Oct 15, 2026 · Mathlib 0df444a (Lean v4.33.1)

accelerationconvergence-ratemarkov-decision-processp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1value-iteration

Let (S,A,P,r,λ)(\mathbb S,\mathbb A,P,r,\lambda)(S,A,P,r,λ) be a finite MDP with a nonempty action set, in which every PiaP_{ia}Pia​ is a probability distribution over next states and λ∈(0,1)\lambda\in(0,1)λ∈(0,1), let TTT be its Bellman operator and v∗v^*v∗ its fixed point, T(v∗)=v∗T(v^*) = v^*T(v∗)=v∗ (the optimal value function). Let λ′∈[λ,1)\lambda'\in[\lambda,1)λ′∈[λ,1), let α,γ>0\alpha,\gamma>0α,γ>0 be any step sizes, and let (vs)s≥0(v_s)_{s\ge0}(vs​)s≥0​ be the iterates of Safe Accelerated Value Iteration (Algorithm 1) from any v0∈RSv_0\in\mathbb R^{\mathbb S}v0​∈RS. Then (vs)s≥0(v_s)_{s\ge 0}(vs​)s≥0​ converges to v∗v^*v∗, and there is a constant CCC such that

∥vs−v∗∥∞≤C λ′ sfor all s≥0,\|v_s - v^*\|_\infty \le C\,\lambda'^{\,s} \qquad \text{for all } s\ge 0,∥vs​−v∗∥∞​≤Cλ′sfor all s≥0,

that is, vs=v∗+O(λ′s)v_s = v^* + O(\lambda'^s)vs​=v∗+O(λ′s) for all s≥0s\ge0s≥0.

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 λ′=λ\lambda' = \lambdaλ′=λ 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 λ′\lambda'λ′ admits more accelerated steps.

Formalization Note ∥⋅∥∞\|\cdot\|_\infty∥⋅∥∞​ is Mathlib's sup norm on S → ℝ. "vs=v∗+O(λ′s)v_s = v^* + O(\lambda'^s)vs​=v∗+O(λ′s), ∀s≥0\forall s\ge0∀s≥0" is encoded as one constant CCC valid for every sss, and convergence as Filter.Tendsto to nhds vstar. v∗v^*v∗ enters as a vector with T(v∗)=v∗T(v^*) = v^*T(v∗)=v∗, which exists and is unique for a valid MDP since TTT is a λ\lambdaλ-contraction. The hypotheses α,γ>0\alpha,\gamma>0α,γ>0 are those of Algorithm 1; the constant CCC is not specified, as in the paper.

Preamble
import Mathlib
import Definitions.Def_AccelVI_SafeAVI_Setting
Formal statement
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
Source
Goyal & Grand-Clément, A First-Order Approach to Accelerated Value Iteration, arXiv:1905.09963v7, p. 13, Theorem 7.1; Algorithm 1 and proof p. 14
Human review
  • Endorsed by Shuze Chen · Oct 15, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 15, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me