Infinite-horizon dynamic programming is the mathematical core of Markov decision processes and reinforcement learning: Bellman equations, value iteration, policy iteration, and their guarantees. Chapter 7 of Bertsekas, Dynamic Programming and Optimal Control, Vol. I (3rd ed., 2005) develops the finite-state theory in its cleanest generality — stochastic shortest path (SSP) problems first (Prop. 7.2.1–7.2.2), with discounted problems (Prop. 7.3.1) and average-cost problems (Prop. 7.4.1–7.4.2) derived from the SSP analysis. These propositions are cited throughout the MDP/RL literature as the base case of the theory; none of them exists in Mathlib.
States plus an implicit cost-free absorbing termination state ; finite nonempty control sets ; costs ; sub-stochastic transitions , , the deficit being the termination probability (BertsekasSSPModel). Operators
(BertsekasSSPPolicyOp, BertsekasSSPBellmanOp), -stage costs by backward recursion with policy shift (BertsekasSSPNCost), and the survival mass (BertsekasSSPSurvival). Assumption 7.2.1: for some , every admissible policy has survival mass from every state after stages. The discounted setting reuses the same model with stochastic rows and (BertsekasDiscounted*); the average-cost setting adds a designated state with the avoidance probability of Assumption 7.4.1 (BertsekasSSPAvoidProb).
Under Assumption 7.2.1, there is a vector with
and a stationary policy attaining — BertsekasDP.ssp_main_theorem (goal, Prop. 7.2.1(a),(b)). Milestones: 7.2.1(c) policy evaluation, 7.2.1(d) optimality iff greediness, 7.2.2 policy iteration, 7.3.1 the full discounted counterpart, 7.4.1 the average-cost Bellman equation, 7.4.2 average-cost policy iteration.
These are the convergence guarantees behind value iteration and policy iteration — the two algorithms at the root of dynamic programming practice and of RL analyses (Q-learning's target operator is exactly ). The SSP form is the strongest of the three: the discounted theory is its special case (termination with probability per stage) and the average-cost theory reduces to it through cycles at the recurrent state. Formalized, the chapter yields a reusable finite-MDP theory: monotone operators, -stage contractions, and the machinery for later Vol. II material. All results are proved in the book; the formalization is new.
is not a one-stage contraction in the sup-norm under Assumption 7.2.1 — only an -stage contraction, uniformly over the finitely many -stage policy prefixes; extracting the uniform contraction factor (via finiteness of the policy space) is the crux of the whole chapter. The limit of -stage costs for nonstationary policies must be established, not assumed (tail-sum estimate ). For the average-cost results the associated-SSP construction (stop on reaching ) must be built inside the proof. The liminf phrasing of average-cost optimality is deliberate: for arbitrary nonstationary policies the Cesàro limit need not exist.
Finite states Fin n, finite control type, constraint sets as Finsets with attained minima; no termination state in the carrier — termination is the sub-stochastic deficit, exactly as the book treats it computationally. Policies are sequences of stage policies (Markov); costs of nonstationary policies via the shift recursion. Convergence is Tendsto in the product topology (equivalently sup-norm, finite). Average cost uses real liminf and division with the term junk-valued at 0 (irrelevant at infinity). The discounted theorem packages parts (a)–(e) in one statement mirroring Prop. 7.3.1.
namespace BertsekasDP
theorem ssp_main_theorem {n : ℕ} {C : Type} [Fintype C]
(M : BertsekasSSPModel n C)
(hA : ∃ m : ℕ, 0 < m ∧ ∀ π, BertsekasSSPAdmissible M π →
∀ i, BertsekasSSPSurvival M π m i < 1) :
∃ Jstar : Fin n → ℝ,
(∀ J₀ : Fin n → ℝ,
Filter.Tendsto (fun k => (BertsekasSSPBellmanOp M)^[k] J₀)
Filter.atTop (nhds Jstar)) ∧
BertsekasSSPBellmanOp M Jstar = Jstar ∧
(∀ J : Fin n → ℝ, BertsekasSSPBellmanOp M J = J → J = Jstar) ∧
(∀ π, BertsekasSSPAdmissible M π → ∀ i, ∃ Jπ : ℝ,
Filter.Tendsto (fun N => BertsekasSSPNCost M π N i)
Filter.atTop (nhds Jπ) ∧ Jstar i ≤ Jπ) ∧
(∃ μ : Fin n → C, (∀ i, μ i ∈ M.U i) ∧ ∀ i,
Filter.Tendsto (fun N => BertsekasSSPNCost M (fun _ => μ) N i)
Filter.atTop (nhds (Jstar i))) := by sorry
end BertsekasDPProposition 7.2.1(a),(b) (the stochastic shortest path theorem). Consider the finite-state stochastic shortest path problem under Assumption 7.2.1: there is an integer such that, regardless of the policy used and the initial state, termination is reached within stages with positive probability,
Then there is a cost vector such that:
This is the base case of infinite-horizon dynamic programming, and the theorem that value iteration and -learning ultimately rest on: the Bellman operator has a unique fixed point which is the optimal cost, and it can be found by iterating from anywhere. The discounted theory of §7.3 is the special case where termination occurs with probability at each stage.
Formalization Note Uniqueness of the fixed point is asserted over all real-valued cost vectors, with no boundedness side condition. The existence of the limit defining for nonstationary policies is part of the claim, not an assumption. Assumption 7.2.1 is stated through the survival probability under admissible policies; the source notes one may always take .
No open leaves. Every sub-goal is proved or awaiting decomposition.