Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 6.2, p. 12 — iteration of T_M ∘ M_A converges to V₀ with ‖V₀ − V*‖ ≤ 2γε/(1 − γ)

Proved
StableFA.Discounted.theorem_6_2

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

approximate-value-iterationaveragercontractionerror-boundp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1

Let MMM be a finite Markov decision process on states 1,…,n1,\dots,n1,…,n with nonempty finite action sets U(i)U(i)U(i), expected costs ciac_{ia}cia​, stochastic transition probabilities paijp_{aij}paij​ and discount factor 0≤γ<10\le\gamma<10≤γ<1. Let TMT_MTM​ be its parallel value backup operator,

(TMV)(i)=min⁡a∈U(i)(cia+γ∑jpaijV(j)),(T_MV)(i)=\min_{a\in U(i)}\Big(c_{ia}+\gamma\sum_j p_{aij}V(j)\Big),(TM​V)(i)=a∈U(i)min​(cia​+γj∑​paij​V(j)),

and let V∗V^*V∗ be the optimal value function, i.e. the fixed point TMV∗=V∗T_MV^*=V^*TM​V∗=V∗. Let AAA be an averager with mapping MAM_AMA​, let VAV^AVA be any fixed point of MAM_AMA​, and put ε=∥VA−V∗∥\varepsilon=\|V^A-V^*\|ε=∥VA−V∗∥, where ∥⋅∥\|\cdot\|∥⋅∥ is the max norm. Then there is a value function V0V_0V0​ such that, from every initial guess VVV, the iterates (TM∘MA)k(V)(T_M\circ M_A)^k(V)(TM​∘MA​)k(V) converge to V0V_0V0​, and

∥V0−V∗∥≤2γε1−γ.\|V_0-V^*\|\le\frac{2\gamma\varepsilon}{1-\gamma}.∥V0​−V∗∥≤1−γ2γε​.

So if the averager can represent some function within ε\varepsilonε of the optimal value function, approximate value iteration through it converges, from any start, to a value function whose error is of order ε\varepsilonε; as γ→0\gamma\to0γ→0 the bound vanishes. Here V0V_0V0​ denotes the limit of the iteration, not its starting point.

Formalization Note V∗V^*V∗ is taken as a hypothesis, the fixed point of TMT_MTM​. This is licensed by the last clause of Theorem 2.2 (p. 4: "The fixed point of each of these operators is the optimal value function for the MDP"), which is the content of the published, proved theorem BertsekasDP.discounted_main_theorem (existence, uniqueness and optimality of the fixed point for 0<γ<10<\gamma<10<γ<1; for γ=0\gamma=0γ=0 the fixed point is min⁡acia\min_a c_{ia}mina​cia​, plainly optimal). The page says "with discount factor γ\gammaγ"; the theorem sits in the paper's discounted discussion (§6.1: "If we are trying to solve a discounted MDP") and its proof uses that TMT_MTM​ is a γ\gammaγ-contraction, so γ<1\gamma<1γ<1 is assumed. The MDP is BertsekasSSPModel plus the stochastic-row hypothesis; action sets may depend on the state, which harmlessly generalizes the paper's single action set. The averager acts on whole value functions (Fin n → ℝ), the sampled approximator being the special case of zero weights outside the sample. The iterated map is TM∘MAT_M\circ M_ATM​∘MA​ (fit, then back up), as on the page. ∥⋅∥\|\cdot\|∥⋅∥ on Fin n → ℝ is the max norm.

Preamble
import Mathlib
import Definitions.Def_BertsekasSSPModel
import Definitions.Def_StableFA_Discounted_Setting

open Filter Topology
Formal statement
namespace StableFA.Discounted

theorem theorem_6_2 {n : ℕ} {C : Type} [Fintype C] (M : BertsekasSSPModel n C)
    (γ : ℝ) (hγ0 : 0 ≤ γ) (hγ1 : γ < 1)
    (hp1 : ∀ i, ∀ u ∈ M.U i, ∑ j, M.p i u j = 1)
    (A : Averager n) (Vstar VA : Fin n → ℝ) (ε : ℝ)
    (hV : BertsekasDiscountedBellmanOp M γ Vstar = Vstar)
    (hVA : A.apply VA = VA) (hε : ‖VA - Vstar‖ = ε) :
    ∃ V₀ : Fin n → ℝ,
      (∀ V : Fin n → ℝ,
        Tendsto (fun k => (BertsekasDiscountedBellmanOp M γ ∘ A.apply)^[k] V) atTop (𝓝 V₀)) ∧
      ‖V₀ - Vstar‖ ≤ 2 * γ * ε / (1 - γ) := by sorry

end StableFA.Discounted
Source
Gordon, Stable Function Approximation in Dynamic Programming, Tech. Rep. CMU-CS-95-103, Carnegie Mellon University (1995), p. 12, Theorem 6.2; proof pp. 12–13
Human review
  • Endorsed by Shuze Chen · Oct 6, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 6, 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