Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proposition 6.4 — under A.1–A.5 and C~\tilde CC~, J∗J^*J∗ is the unique fixed point of TTT in Bˉ∩F∗\bar B\cap F^*Bˉ∩F∗

Proved
BertsekasShreve.Generalized.prop6_4_contraction_fixed_point

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

contractiondynamic-programmingfixed-pointinfinite-horizonp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-bookp2o-v1

Consider the generalized abstract model of Section 6.1 under conditions A.1–A.5 and Assumption C~\tilde CC~, with the closed set Bˉ⊆B\bar B\subseteq BBˉ⊆B and the scalars m,ρ,αm,\rho,\alpham,ρ,α of C~\tilde CC~. Then:

  1. J∗∈Bˉ∩F∗J^*\in\bar B\cap F^*J∗∈Bˉ∩F∗ and J∗J^*J∗ is the unique fixed point of TTT within Bˉ∩F∗\bar B\cap F^*Bˉ∩F∗. Furthermore, if J′∈Bˉ∩F∗J'\in\bar B\cap F^*J′∈Bˉ∩F∗ satisfies T(J′)≤J′T(J')\le J'T(J′)≤J′ then J∗≤J′J^*\le J'J∗≤J′, while if J′≤T(J′)J'\le T(J')J′≤T(J′) then J′≤J∗J'\le J^*J′≤J∗.
  2. For every μ∈M~\mu\in\tilde Mμ∈M~, Jμ∈Bˉ∩F~J_\mu\in\bar B\cap\tilde FJμ​∈Bˉ∩F~ and JμJ_\muJμ​ is the unique fixed point of TμT_\muTμ​ within Bˉ∩F~\bar B\cap\tilde FBˉ∩F~.
lim⁡N→∞∥TN(J)−J∗∥=0∀J∈Bˉ∩F∗,lim⁡N→∞∥TμN(J)−Jμ∥=0∀J∈Bˉ∩F~, μ∈M~.\lim_{N\to\infty}\|T^N(J)-J^*\|=0\quad\forall J\in\bar B\cap F^*,\qquad\lim_{N\to\infty}\|T_\mu^N(J)-J_\mu\|=0\quad\forall J\in\bar B\cap\tilde F,\ \mu\in\tilde M.N→∞lim​∥TN(J)−J∗∥=0∀J∈Bˉ∩F∗,N→∞lim​∥TμN​(J)−Jμ​∥=0∀J∈Bˉ∩F~, μ∈M~.
  1. A stationary policy π∗=(μ∗,μ∗,… )∈Π~\pi^*=(\mu^*,\mu^*,\dots)\in\tilde\Piπ∗=(μ∗,μ∗,…)∈Π~ is optimal if and only if Tμ∗(J∗)=T(J∗)T_{\mu^*}(J^*)=T(J^*)Tμ∗​(J∗)=T(J∗). Equivalently, π∗\pi^*π∗ is optimal if and only if Jμ∗∈Bˉ∩F∗J_{\mu^*}\in\bar B\cap F^*Jμ∗​∈Bˉ∩F∗ and Tμ∗(Jμ∗)=T(Jμ∗)T_{\mu^*}(J_{\mu^*})=T(J_{\mu^*})Tμ∗​(Jμ∗​)=T(Jμ∗​).
  2. For every ε>0\varepsilon>0ε>0 there is a stationary policy πε=(με,με,… )∈Π~\pi_\varepsilon=(\mu_\varepsilon,\mu_\varepsilon,\dots)\in\tilde\Piπε​=(με​,με​,…)∈Π~ with ∥J∗−Jμε∥≤ε\|J^*-J_{\mu_\varepsilon}\|\le\varepsilon∥J∗−Jμε​​∥≤ε.

This is the restricted-class analogue of Propositions 4.2 and 4.3: under a contraction assumption the optimal cost over Π~\tilde\PiΠ~ solves Bellman's equation, value iteration converges in sup norm, optimal stationary policies are characterized by Bellman's equation, and ε\varepsilonε-optimal stationary policies exist within the restricted class. The book states it without proof.

Formalization Note "J∈Bˉ∩GJ\in\bar B\cap GJ∈Bˉ∩G" means JJJ is (the extended-real image of) a bounded real function in Bˉ\bar BBˉ belonging to GGG. A sup-norm bound ∥G−G′∥≤c\|G-G'\|\le c∥G−G′∥≤c between extended-real functions means both are real at every point and ∣G(x)−G′(x)∣≤c|G(x)-G'(x)|\le c∣G(x)−G′(x)∣≤c for all xxx; the limits in item 3 are stated as "for every ε>0\varepsilon>0ε>0 the distance is eventually at most ε\varepsilonε".

Preamble
import Mathlib
import Definitions.Def_BertsekasShreve_Generalized_Model
import Definitions.Def_BertsekasShreve_Generalized_Assumptions
import Definitions.Def_BertsekasShreve_Generalized_Optimality
Formal statement
namespace BertsekasShreve.Generalized

open Filter Topology

/-- Proposition 6.4, p. 97. Let A.1–A.5 and Assumption C̃ hold, with the closed set `B̄ ⊆ B` and
the scalars `m`, `ρ`, `α` of C̃.
(a) `J* ∈ B̄ ∩ F*` and `J*` is the unique fixed point of `T` within `B̄ ∩ F*`; if `J' ∈ B̄ ∩ F*`
and `T(J') ≤ J'` then `J* ≤ J'`, while if `J' ≤ T(J')` then `J' ≤ J*`.
(b) For every `μ ∈ M̃`, `J_μ ∈ B̄ ∩ F̃` and `J_μ` is the unique fixed point of `T_μ` within
`B̄ ∩ F̃`.
(c) `‖T^N(J) − J*‖ → 0` for all `J ∈ B̄ ∩ F*`, and `‖T_μ^N(J) − J_μ‖ → 0` for all `J ∈ B̄ ∩ F̃`,
`μ ∈ M̃`.
(d) A stationary policy `(μ*, μ*, …) ∈ Π̃` is optimal iff `T_{μ*}(J*) = T(J*)`; equivalently,
iff `J_{μ*} ∈ B̄ ∩ F*` and `T_{μ*}(J_{μ*}) = T(J_{μ*})`.
(e) For every `ε > 0` there is a stationary `(μ_ε, μ_ε, …) ∈ Π̃` with `‖J* − J_{μ_ε}‖ ≤ ε`.

The sup-norm statements are written with `SupDistLe`: `‖G − G'‖ ≤ c` means `G`, `G'` are real at
every point and `|G(x) − G'(x)| ≤ c` for all `x`; convergence in (c) is "for every `ε > 0` the
distance is eventually `≤ ε`". -/
theorem prop6_4_contraction_fixed_point {S C : Type*} (P : Model S C)
    (hA1 : P.A1) (hA2 : P.A2) (hA3 : P.A3) (hA4 : P.A4) (hA5 : P.A5)
    (Bbar : Set (BertsekasShreve.Contraction.BFun S)) (m : ℕ) (ρ α : ℝ) (hC : P.AssumptionCtilde Bbar m ρ α) :
    -- (a)
    (MemBbarInter Bbar P.Fstar P.Jstar ∧ P.T P.Jstar = P.Jstar ∧
      (∀ J', MemBbarInter Bbar P.Fstar J' → P.T J' = J' → J' = P.Jstar) ∧
      (∀ J', MemBbarInter Bbar P.Fstar J' → P.T J' ≤ J' → P.Jstar ≤ J') ∧
      (∀ J', MemBbarInter Bbar P.Fstar J' → J' ≤ P.T J' → J' ≤ P.Jstar)) ∧
    -- (b)
    (∀ μ : P.Sel, MemBbarInter Bbar P.Ftil (P.Jmu μ) ∧ P.Tmu μ.1 (P.Jmu μ) = P.Jmu μ ∧
      ∀ J', MemBbarInter Bbar P.Ftil J' → P.Tmu μ.1 J' = J' → J' = P.Jmu μ) ∧
    -- (c)
    (∀ J, MemBbarInter Bbar P.Fstar J → ∀ ε : ℝ, 0 < ε →
        ∃ N₀ : ℕ, ∀ N, N₀ ≤ N → BertsekasShreve.Contraction.SupDistLe (P.T^[N] J) P.Jstar ε) ∧
    (∀ μ : P.Sel, ∀ J, MemBbarInter Bbar P.Ftil J → ∀ ε : ℝ, 0 < ε →
        ∃ N₀ : ℕ, ∀ N, N₀ ≤ N → BertsekasShreve.Contraction.SupDistLe ((P.Tmu μ.1)^[N] J) (P.Jmu μ) ε) ∧
    -- (d)
    (∀ μ : P.Sel,
      (P.IsOptimal (P.stationary μ) ↔ P.Tmu μ.1 P.Jstar = P.T P.Jstar) ∧
      (P.IsOptimal (P.stationary μ) ↔
        MemBbarInter Bbar P.Fstar (P.Jmu μ) ∧ P.Tmu μ.1 (P.Jmu μ) = P.T (P.Jmu μ))) ∧
    -- (e)
    (∀ ε : ℝ, 0 < ε → ∃ μ : P.Sel, BertsekasShreve.Contraction.SupDistLe P.Jstar (P.Jmu μ) ε) := by sorry

end BertsekasShreve.Generalized
Source
Bertsekas & Shreve, Stochastic Optimal Control: The Discrete-Time Case, Athena Scientific 1996, p. 97, Proposition 6.4
Human review
  • Endorsed by Shuze Chen · Oct 5, 2026

    Confirmed by the moderator at approval.

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