Average-cost policy iteration (Prop. 7.4.2)
ProvedBertsekasDP.average_cost_policy_iterationProposition 7.4.2 (policy iteration for the average-cost problem). Under Assumption 7.4.1, consider policy iteration in its average-cost form: evaluate the current stationary policy by solving
and improve it by letting attain at every state. Then each iteration makes irreversible progress:
- the gain never increases: for every ;
- when the gain is unchanged, the differential costs do not increase: if then for every state ;
- the algorithm terminates at a solution of Bellman's equation: for some ,
The two-tier progress measure is what the average-cost setting requires: an iteration that fails to reduce the long-run rate must at least reduce the transient term, and since there are finitely many stationary policies, neither can happen indefinitely. By Prop. 7.4.1 the pair reached at termination certifies the optimal average cost, and the policies attaining it are optimal.
Formalization Note The evaluation equations and the normalization are given as hypotheses on the sequences , matching the linear system solved at each step in practice. Part 2 is a conditional statement, asserted only at iterations where the gain is unchanged, and the inequality is not strict.
import Mathlib import Definitions.Def_BertsekasSSPModel
namespace BertsekasDP
theorem average_cost_policy_iteration {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)
(μ : ℕ → Fin n → C) (hadm : ∀ k i, μ k i ∈ M.U i)
(lam : ℕ → ℝ) (h : ℕ → Fin n → ℝ)
(heval : ∀ k i, lam k + h k i =
M.g i (μ k i) + ∑ j, M.p i (μ k i) j * h k j)
(hnorm : ∀ k, h k s = 0)
(himp : ∀ k i,
M.g i (μ (k + 1) i) + ∑ j, M.p i (μ (k + 1) i) j * h k j =
BertsekasSSPBellmanOp M (h k) i) :
(∀ k, lam (k + 1) ≤ lam k) ∧
(∀ k, lam (k + 1) = lam k → ∀ i, h (k + 1) i ≤ h k i) ∧
(∃ k, ∀ i, lam k + h k i = BertsekasSSPBellmanOp M (h k) i) := 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 (note the presence of a state among the hypotheses forces for the theorem to be invocable). Assume:
- : for every state and every , ;
- a distinguished state ;
- : there exists such that every admissible policy sequence and every state satisfy , with the -step avoid- probability defined in this bundle;
- a sequence of stage policies with for all ;
- sequences and ;
- evaluation equations: for every and state , ;
- normalization: for every ;
- improvement: for every and state ,
where is the undiscounted SSP Bellman operator; i.e. attains the Bellman minimum for at every state.
The conclusion is the conjunction of three claims:
- for every (the gain sequence is non-increasing);
- for every , if then for every state (bias decrease is asserted only conditionally on the gain being unchanged at that step, and only as a non-strict pointwise inequality);
- there exists a such that for every state , — i.e. at some iteration the pair satisfies the average-cost Bellman equation.
Nothing is asserted about optimality of or at that , about the sequences converging, or about uniqueness. The proof is a placeholder.
Confirmed by the mission captain (proposal self-audit).