Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Corollary 4.1, p. 11 — all policies proper and A self-weighted ⇒ T_M and M_A are compatible and approximate value iteration converges

Proved
StableFA.DerivedMDP.corollary_4_1

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

approximate-value-iterationaveragerconvergencep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1self-weightedstochastic-shortest-path

Let MMM be a finite nondiscounted Markov decision process with a cost-free absorbing goal state, in which every policy is proper. Let AAA be an averager that is self-weighted for MMM, let TMT_MTM​ be the parallel value backup operator of MMM (which sets V(1)=0V(1)=0V(1)=0) and MAM_AMA​ the mapping of AAA. Then:

  1. TMT_MTM​ and MAM_AMA​ are compatible: for every initial guess V0V_0V0​ the iterates (MA∘TM)k(V0)(M_A\circ T_M)^k(V_0)(MA​∘TM​)k(V0​) converge;
  2. approximate value iteration based on AAA converges when applied to MMM: for every initial guess V0V_0V0​ the iterates (TM∘MA)k(V0)(T_M\circ M_A)^k(V_0)(TM​∘MA​)k(V0​) converge.

This is the report's convergence guarantee for nondiscounted problems. An averager need not be a nonexpansion in the weighted max norm in which TMT_MTM​ contracts, and approximate value iteration can diverge (Figure 4); self-weighting rules that out.

Formalization Note "Compatible" follows the definition on p. 5: Compatible MF T iterates MF ∘ T, so part 1 is Compatible A.apply (BertsekasSSPBellmanOp M). The approximate value iteration sequence of p. 10 interleaves the two orders, V0,MA(V0),TM(MA(V0)),…V_0, M_A(V_0), T_M(M_A(V_0)),\dotsV0​,MA​(V0​),TM​(MA​(V0​)),…; part 2 states the convergence of TM∘MAT_M\circ M_ATM​∘MA​, the other order. The goal is the implicit termination state of BertsekasSSPModel; its value is 000. "All policies proper" quantifies over stationary policies (p. 3). The hypotheses are about MMM and AAA only; nothing is assumed about the derived MDP.

Preamble
import Mathlib
import Definitions.Def_BertsekasSSPModel
import Definitions.Def_StableFA_DerivedMDP_Setting
Formal statement
namespace StableFA.DerivedMDP

theorem corollary_4_1 {n : ℕ} {C : Type} [Fintype C]
    (M : BertsekasSSPModel n C) (A : Averager n)
    (hproper : ∀ μ : Fin n → C, (∀ i, μ i ∈ M.U i) → IsProper M μ)
    (hself : SelfWeighted M A) :
    StableFA.Discounted.Compatible A.apply (BertsekasSSPBellmanOp M) ∧
      StableFA.Discounted.Compatible (BertsekasSSPBellmanOp M) A.apply := by sorry

end StableFA.DerivedMDP
Source
Gordon, Stable Function Approximation in Dynamic Programming, Tech. Rep. CMU-CS-95-103, Carnegie Mellon University (1995), p. 11, Corollary 4.1; argument pp. 9–10
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