§2, (1) — V_β exists as the limit of value iteration, is bounded, and is the unique bounded solution of the optimality equation
ProvedRossQC.Regions.optimality_equationbellman-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 , bounded costs and a discount factor . Let be the set of probability vectors on the states and the value iterates, with .
- For every the sequence converges; its limit is .
- is bounded on .
- solves the optimality equation: for every ,
- Every function that is bounded on and satisfies the same equation on coincides with on .
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 . The paper's companion clause, that a rule selecting a minimizer of the right side is -optimal, is the definition of -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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.