Average cost Bellman equation (Prop. 7.4.1)
ProvedBertsekasDP.average_cost_bellmanProposition 7.4.1 (average cost per stage). Consider the finite-state average-cost problem with stochastic transition rows, under Assumption 7.4.1: some designated state is visited within stages with positive probability, regardless of the policy and the initial state. Then there exist a scalar and a vector with such that:
- Bellman's equation for the average-cost problem holds:
- the gain is unique: any pair satisfying this equation has ;
- is a lower bound on the average cost of every admissible policy:
- greedy stationary policies attain it: if a stationary attains the minimum above for every , then
The vector is a differential or relative cost: measures the transient advantage of starting at rather than at the reference state , once the long-run rate has been accounted for. That the optimal average cost is the same from every initial state, and that it is determined by an equation of Bellman type, is what makes the average-cost criterion tractable at all.
Formalization Note Existence is asserted for the pair ; only is pinned down, as is determined only up to the normalization under this assumption. The lower bound is stated with deliberately: for arbitrary nonstationary policies the Cesàro limit need not exist, while part 4 asserts a genuine limit for greedy stationary policies. The term of the quotient is a junk value and does not affect the limit.
import Mathlib import Definitions.Def_BertsekasSSPModel
namespace BertsekasDP
theorem average_cost_bellman {n : ℕ} {C : Type} [Fintype C]
(M : BertsekasSSPModel n C)
(hp1 : ∀ i, ∀ u ∈ M.U i, ∑ j, M.p i u j = 1)
(s : Fin n)
(hA : ∃ m : ℕ, 0 < m ∧ ∀ π, BertsekasSSPAdmissible M π →
∀ i, BertsekasSSPAvoidProb M s π m i < 1) :
∃ (lam : ℝ) (h : Fin n → ℝ),
h s = 0 ∧
(∀ i, lam + h i = BertsekasSSPBellmanOp M h i) ∧
(∀ (lam' : ℝ) (h' : Fin n → ℝ),
(∀ i, lam' + h' i = BertsekasSSPBellmanOp M h' i) → lam' = lam) ∧
(∀ π, BertsekasSSPAdmissible M π → ∀ i,
lam ≤ Filter.liminf
(fun N => BertsekasSSPNCost M π N i / (N : ℝ)) Filter.atTop) ∧
(∀ μ : Fin n → C, (∀ i, μ i ∈ M.U i) →
(∀ i, lam + h i = M.g i (μ i) + ∑ j, M.p i (μ i) j * h j) →
∀ i, Filter.Tendsto
(fun N => BertsekasSSPNCost M (fun _ => μ) N i / (N : ℝ))
Filter.atTop (nhds lam)) := by sorry
end BertsekasDPRead-back
What the Lean code literally says, in plain math · claude-fable-5
Let be a BertsekasSSPModel on states with finite control type . Assume:
- : for every state and every , exactly;
- a distinguished state ;
- : there exists such that for every admissible policy sequence (i.e. for all ) and every state , , where is the probability (as defined in this bundle) that, starting from under , the process avoids state at all times .
The theorem asserts the existence of a real number and a function satisfying the conjunction of five clauses, where is the undiscounted SSP Bellman operator and the undiscounted -stage cost:
- Normalization: .
- Average-cost Bellman equation: for every state , .
- Uniqueness of only: for every pair with and satisfying for all — with no normalization requirement on — one has . Nothing is asserted about versus .
- is a lower bound on the average cost of every admissible policy: for every admissible policy sequence and every state ,
Here the quotient is real division: at the term is under Lean's convention (division by zero yields ), which does not affect the limit inferior along . The is taken in (not the extended reals) with Mathlib's conventions: if the sequence were unbounded below (or the relevant set of eventual lower bounds empty/unbounded), the takes the convention-determined junk value ( or of an unbounded set for real numbers), and the inequality is then a claim about that value. 5. Stationary policies satisfying the evaluation equation with this achieve average cost exactly : for every stage policy with for every , if
(with the specific and whose existence is asserted), then for every state the sequence converges to as (a genuine limit, not just a liminf statement; the term is again the junk value ).
The existence is , not unique existence, for the pair ; only is pinned down by clause 3. Because a state is among the hypotheses, the theorem can only be invoked when . The proof is a placeholder.
Confirmed by the mission captain (proposal self-audit).