Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

§2, (1) — V_β exists as the limit of value iteration, is bounded, and is the unique bounded solution of the optimality equation

Proved
RossQC.Regions.optimality_equation

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

bellman-equationdynamic-programmingp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1quality-control

Consider the general model of Ross's §2: countably many underlying states, a stochastic transition matrix (Pij)(P_{ij})(Pij​), bounded costs Ci,Ii,RiC_i,I_i,R_iCi​,Ii​,Ri​ and a discount factor β∈(0,1)\beta\in(0,1)β∈(0,1). Let SSS be the set of probability vectors on the states and VnV^nVn the value iterates, with V0=0V^0=0V0=0.

  1. For every P∈SP\in SP∈S the sequence Vn(P)V^n(P)Vn(P) converges; its limit is Vβ(P)V_\beta(P)Vβ​(P).
  2. VβV_\betaVβ​ is bounded on SSS.
  3. VβV_\betaVβ​ solves the optimality equation: for every P∈SP\in SP∈S,
Vβ(P)=min⁡{∑iPiCi+βVβ(TP); ∑iPiIi+β∑iPiVβ(ei); ∑iPiRi+βVβ(e0)}.V_\beta(P)=\min\Big\{\sum_i P_iC_i+\beta V_\beta(TP);\ \sum_i P_iI_i+\beta\sum_i P_iV_\beta(e^i);\ \sum_i P_iR_i+\beta V_\beta(e^0)\Big\}.Vβ​(P)=min{i∑​Pi​Ci​+βVβ​(TP); i∑​Pi​Ii​+βi∑​Pi​Vβ​(ei); i∑​Pi​Ri​+βVβ​(e0)}.
  1. Every function WWW that is bounded on SSS and satisfies the same equation on SSS coincides with VβV_\betaVβ​ on SSS.

The paper quotes this from Blackwell as "well known"; every structural result of the paper is derived from it.

Formalization Note Uniqueness is among functions bounded on SSS. The paper's companion clause, that a rule selecting a minimizer of the right side is β\betaβ-optimal, is the definition of β\betaβ-optimality used in this mission rather than a claim of this theorem.

Preamble
import Mathlib
import Definitions.Def_RossQC_Regions_Model
Formal statement
namespace RossQC.Regions

open Filter Topology

/-- Ross, *Quality Control under Markovian Deterioration*, Management Science 17(9):587–596 (1971),
DOI 10.1287/mnsc.17.9.587, §2, (1), p. 588 (unnumbered statement): "It is well known (see [1]) that
`V_β(P)` is the unique solution to (1)".

Under the standing hypotheses of §1–§2 (`Model.Valid`):

1. for every belief `P ∈ S` the value iterates `V^n(P)` converge (so `V_β(P)` is their limit);
2. `V_β` is bounded on `S`;
3. `V_β` satisfies the optimality equation (1) at every `P ∈ S`;
4. every function `W` that is bounded on `S` and satisfies (1) on `S` equals `V_β` on `S`.

**Formalization Note.** `V_β` is defined as the limit of value iteration from `V⁰ = 0`
(see `Model.Vβ`), not as an infimum over a policy class. Uniqueness is asserted in the class of
functions bounded on `S`, the setting of Blackwell [1]. The second half of the paper's sentence ("any
rule which … selects an action which minimizes the right side of (1) is β-optimal") is the convention
by which β-optimality is formalized elsewhere in this mission, not a claim of this theorem. -/
theorem optimality_equation {ι : Type*} [Countable ι] (M : Model ι) (hM : M.Valid) :
    (∀ P ∈ M.simplex, ∃ L : ℝ, Tendsto (fun n => M.valueIter n P) atTop (𝓝 L)) ∧
    (∃ B : ℝ, ∀ P ∈ M.simplex, |M.Vβ P| ≤ B) ∧
    (∀ P ∈ M.simplex, M.Vβ P = M.bellman M.Vβ P) ∧
    (∀ W : (ι → ℝ) → ℝ, (∃ B : ℝ, ∀ P ∈ M.simplex, |W P| ≤ B) →
      (∀ P ∈ M.simplex, W P = M.bellman W P) → ∀ P ∈ M.simplex, W P = M.Vβ P) := by sorry

end RossQC.Regions
Source
Ross, Quality Control under Markovian Deterioration, Management Science 17(9):587–596 (1971), DOI 10.1287/mnsc.17.9.587, p. 588, §2, (1)
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