Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Average cost Bellman equation (Prop. 7.4.1)

Proved
BertsekasDP.average_cost_bellman

by Shuze Chen · Sep 8, 2026 · Mathlib 0df444a (Lean v4.33.1)

averagecostbellmanequation

Proposition 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 sss is visited within mmm stages with positive probability, regardless of the policy and the initial state. Then there exist a scalar λ∗\lambda^*λ∗ and a vector h∗h^*h∗ with h∗(s)=0h^*(s) = 0h∗(s)=0 such that:

  1. Bellman's equation for the average-cost problem holds:
λ∗+h∗(i)  =  min⁡u∈U(i)[ g(i,u)+∑j=1npij(u)h∗(j) ],i=1,…,n;\lambda^* + h^*(i) \;=\; \min_{u \in U(i)} \Bigl[\, g(i,u) + \sum_{j=1}^{n} p_{ij}(u) h^*(j) \,\Bigr], \qquad i = 1, \dots, n ;λ∗+h∗(i)=u∈U(i)min​[g(i,u)+j=1∑n​pij​(u)h∗(j)],i=1,…,n;
  1. the gain is unique: any pair (λ,h)(\lambda, h)(λ,h) satisfying this equation has λ=λ∗\lambda = \lambda^*λ=λ∗;
  2. λ∗\lambda^*λ∗ is a lower bound on the average cost of every admissible policy:
λ∗  ≤  lim inf⁡N→∞1NJπN(i)for every admissible π and every i;\lambda^* \;\le\; \liminf_{N \to \infty} \frac{1}{N} J^N_\pi(i) \qquad \text{for every admissible } \pi \text{ and every } i ;λ∗≤N→∞liminf​N1​JπN​(i)for every admissible π and every i;
  1. greedy stationary policies attain it: if a stationary μ\muμ attains the minimum above for every iii, then
lim⁡N→∞1NJμN(i)  =  λ∗for every initial state i.\lim_{N \to \infty} \frac{1}{N} J^N_{\mu}(i) \;=\; \lambda^* \qquad \text{for every initial state } i .N→∞lim​N1​JμN​(i)=λ∗for every initial state i.

The vector h∗h^*h∗ is a differential or relative cost: h∗(i)h^*(i)h∗(i) measures the transient advantage of starting at iii rather than at the reference state sss, once the long-run rate λ∗\lambda^*λ∗ 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 (λ∗,h∗)(\lambda^*, h^*)(λ∗,h∗); only λ∗\lambda^*λ∗ is pinned down, as h∗h^*h∗ is determined only up to the normalization h∗(s)=0h^*(s) = 0h∗(s)=0 under this assumption. The lower bound is stated with lim inf⁡\liminfliminf deliberately: for arbitrary nonstationary policies the Cesàro limit need not exist, while part 4 asserts a genuine limit for greedy stationary policies. The N=0N = 0N=0 term of the quotient is a junk value and does not affect the limit.

Preamble
import Mathlib
import Definitions.Def_BertsekasSSPModel
Formal statement
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 BertsekasDP
Source
D. P. Bertsekas, Dynamic Programming and Optimal Control, Vol. I, 3rd ed., Athena Scientific, 2005, Proposition 7.4.1
Read-back

What the Lean code literally says, in plain math · claude-fable-5

Let MMM be a BertsekasSSPModel on nnn states with finite control type CCC. Assume:

  • hp1hp1hp1: for every state iii and every u∈U(i)u \in U(i)u∈U(i), ∑jpij(u)=1\sum_j p_{ij}(u) = 1∑j​pij​(u)=1 exactly;
  • a distinguished state sss;
  • hAhAhA: there exists m>0m > 0m>0 such that for every admissible policy sequence π\piπ (i.e. πk(i)∈U(i)\pi_k(i) \in U(i)πk​(i)∈U(i) for all k,ik,ik,i) and every state iii, As,πm(i)<1A^m_{s,\pi}(i) < 1As,πm​(i)<1, where As,πm(i)A^m_{s,\pi}(i)As,πm​(i) is the probability (as defined in this bundle) that, starting from iii under π\piπ, the process avoids state sss at all times 1,…,m1,\dots,m1,…,m.

The theorem asserts the existence of a real number λ\lambdaλ and a function h:{0,…,n−1}→Rh : \{0,\dots,n-1\} \to \mathbb{R}h:{0,…,n−1}→R satisfying the conjunction of five clauses, where TTT is the undiscounted SSP Bellman operator and JπNJ^N_\piJπN​ the undiscounted NNN-stage cost:

  1. Normalization: h(s)=0h(s) = 0h(s)=0.
  2. Average-cost Bellman equation: for every state iii, λ+h(i)=(Th)(i)=min⁡u∈U(i)[g(i,u)+∑jpij(u)h(j)]\lambda + h(i) = (T h)(i) = \min_{u \in U(i)} \big[ g(i,u) + \sum_j p_{ij}(u) h(j) \big]λ+h(i)=(Th)(i)=minu∈U(i)​[g(i,u)+∑j​pij​(u)h(j)].
  3. Uniqueness of λ\lambdaλ only: for every pair (λ′,h′)(\lambda', h')(λ′,h′) with λ′∈R\lambda' \in \mathbb{R}λ′∈R and h′:{0,…,n−1}→Rh' : \{0,\dots,n-1\} \to \mathbb{R}h′:{0,…,n−1}→R satisfying λ′+h′(i)=(Th′)(i)\lambda' + h'(i) = (T h')(i)λ′+h′(i)=(Th′)(i) for all iii — with no normalization requirement on h′h'h′ — one has λ′=λ\lambda' = \lambdaλ′=λ. Nothing is asserted about h′h'h′ versus hhh.
  4. λ\lambdaλ is a lower bound on the average cost of every admissible policy: for every admissible policy sequence π\piπ and every state iii,
λ≤lim inf⁡N→∞JπN(i)N.\lambda \le \liminf_{N \to \infty} \frac{J^N_\pi(i)}{N}.λ≤N→∞liminf​NJπN​(i)​.

Here the quotient is real division: at N=0N = 0N=0 the term is Jπ0(i)/0=0/0=0J^0_\pi(i)/0 = 0/0 = 0Jπ0​(i)/0=0/0=0 under Lean's convention (division by zero yields 000), which does not affect the limit inferior along N→∞N \to \inftyN→∞. The lim inf⁡\liminfliminf is taken in R\mathbb{R}R (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 lim inf⁡\liminfliminf takes the convention-determined junk value (sup⁡∅=0\sup \varnothing = 0sup∅=0 or sup⁡\supsup of an unbounded set =0= 0=0 for real numbers), and the inequality is then a claim about that value. 5. Stationary policies satisfying the evaluation equation with this hhh achieve average cost exactly λ\lambdaλ: for every stage policy μ:{0,…,n−1}→C\mu : \{0,\dots,n-1\} \to Cμ:{0,…,n−1}→C with μ(i)∈U(i)\mu(i) \in U(i)μ(i)∈U(i) for every iii, if

∀i,λ+h(i)=g(i,μ(i))+∑jpij(μ(i)) h(j)\forall i,\quad \lambda + h(i) = g(i,\mu(i)) + \sum_j p_{ij}(\mu(i))\, h(j)∀i,λ+h(i)=g(i,μ(i))+j∑​pij​(μ(i))h(j)

(with the specific λ\lambdaλ and hhh whose existence is asserted), then for every state iii the sequence N↦J(μ,μ,… )N(i)/NN \mapsto J^N_{(\mu,\mu,\dots)}(i)/NN↦J(μ,μ,…)N​(i)/N converges to λ\lambdaλ as N→∞N \to \inftyN→∞ (a genuine limit, not just a liminf statement; the N=0N=0N=0 term is again the junk value 000).

The existence is ∃\exists∃, not unique existence, for the pair (λ,h)(\lambda,h)(λ,h); only λ\lambdaλ is pinned down by clause 3. Because a state sss is among the hypotheses, the theorem can only be invoked when n≥1n \ge 1n≥1. The proof is a placeholder.

Human review
  • Endorsed by Community (Bot) · Sep 8, 2026

  • Endorsed by Shuze Chen · Sep 8, 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