Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 7.2.3 — under (SEN) the ACOI holds and optimal stationary policies exist with constant average cost

Proved
SennottDP.SEN.thm_7_2_3_sen_acoi

by mikedeng1 · Oct 2, 2026 · Mathlib 0df444a (Lean v4.33.1)

acoiaverage-costp2o-batch-b23ap2o-gran-per-chapterp2o-plan-bookp2o-v1sen-assumptions

Let Δ\DeltaΔ be an MDC for which the (SEN) assumptions hold for the distinguished state zzz, with function MMM in (SEN2) and constant LLL in (SEN3).

  1. There is a finite constant J=lim⁡α→1−(1−α)Vα(i)J = \lim_{\alpha \to 1^-} (1-\alpha) V_\alpha(i)J=limα→1−​(1−α)Vα​(i), the same for every i∈Si \in Si∈S.
  2. A limit function exists. Every limit function hhh satisfies −L≤h≤M-L \le h \le M−L≤h≤M and the average cost optimality inequality
J+h(i)≥min⁡a∈Ai{C(i,a)+∑jPij(a)h(j)},i∈S.(7.9)J + h(i) \ge \min_{a \in A_i} \Big\{ C(i,a) + \sum_j P_{ij}(a) h(j) \Big\}, \qquad i \in S. \qquad (7.9)J+h(i)≥a∈Ai​min​{C(i,a)+j∑​Pij​(a)h(j)},i∈S.(7.9)

Every stationary policy eee realizing the minimum in (7.9) is average cost optimal with constant average cost Je(i)=JJ_e(i) = JJe​(i)=J, and

lim⁡n→∞1nEe[h(Xn)∣X0=i]=0,i∈S.(7.10)\lim_{n\to\infty} \frac1n E_e[h(X_n) \mid X_0 = i] = 0, \qquad i \in S. \qquad (7.10)n→∞lim​n1​Ee​[h(Xn​)∣X0​=i]=0,i∈S.(7.10)
  1. For any family (fα)(f_\alpha)(fα​) of stationary policies realizing the discount optimality equation, every limit point fff is average cost optimal; a limit function associated with fff exists; and every such hhh satisfies
J+h(i)≥C(i,f(i))+∑jPij(f(i))h(j),lim⁡n→∞1nEf[h(Xn)∣X0=i]=0,i∈S.(7.11), (7.12)J + h(i) \ge C(i,f(i)) + \sum_j P_{ij}(f(i)) h(j), \qquad \lim_{n\to\infty} \frac1n E_f[h(X_n) \mid X_0 = i] = 0, \qquad i \in S. \qquad (7.11),\ (7.12)J+h(i)≥C(i,f(i))+j∑​Pij​(f(i))h(j),n→∞lim​n1​Ef​[h(Xn​)∣X0​=i]=0,i∈S.(7.11), (7.12)
  1. For every average cost optimal policy ψ\psiψ (not necessarily stationary) and every iii, the average cost is a limit: Jψ(i)=lim⁡n→∞vψ,n(i)/nJ_\psi(i) = \lim_{n\to\infty} v_{\psi,n}(i)/nJψ​(i)=limn→∞​vψ,n​(i)/n.

This is the central existence theorem for average cost optimization on countable state spaces: it gives a constant minimum average cost, an average cost optimal stationary policy, and two ways to obtain one (from a limit function, or as a limit of discount optimal policies).

Formalization Note JJJ is a nonnegative real (finite). The limit in part 1 is along α→1−\alpha \to 1^-α→1− (the filter 𝓝[<] 1) in ℝ≥0∞. Sums against hhh are extended reals (positive minus negative part), finite here because h≥−Lh \ge -Lh≥−L. Expectations Ee[h(Xn)]E_e[h(X_n)]Ee​[h(Xn​)] are extended reals, and 1nE\frac1n En1​E is multiplication by the real 1/n1/n1/n in EReal. Part 4 is stated as convergence of vψ,n(i)/nv_{\psi,n}(i)/nvψ,n​(i)/n to Jψ(i)J_\psi(i)Jψ​(i) in ℝ≥0∞.

Preamble
import Mathlib
import Definitions.Def_SennottDP_SEN_Assumptions

open scoped ENNReal NNReal
open Filter Topology
Formal statement
namespace SennottDP.SEN

/-- Sennott (1999), Theorem 7.2.3, pp. 134–135: let `Δ` be an SennottDP.Discounted.MDC for which the (SEN) assumptions
hold for the distinguished state `z`, with function `Mf` in (SEN2) and constant `L` in (SEN3).

(i) There exists a finite constant `J = lim_{α→1⁻} (1 − α) V_α(i)` for `i ∈ S`.

(ii) There exists a limit function. Any such function `h` satisfies `−L ≤ h ≤ Mf` and
`J + h(i) ≥ min_a { C(i,a) + ∑_j P_{ij}(a) h(j) }`, `i ∈ S` (7.9). Let `e` be a stationary policy
realizing the minimum in (7.9). Then `e` is average cost optimal with (constant) average cost `J`
and `lim_{n→∞} (1/n) E_e[h(X_n) | X_0 = i] = 0`, `i ∈ S` (7.10).

(iii) Any limit point `f` (of any family `f_α` of stationary policies realizing the discount
optimality equation) is average cost optimal. There exists a limit function associated with `f`.
Any such function `h` satisfies `J + h(i) ≥ C(i,f) + ∑_j P_{ij}(f) h(j)`, `i ∈ S` (7.11), and
`lim_{n→∞} (1/n) E_f[h(X_n) | X_0 = i] = 0`, `i ∈ S` (7.12).

(iv) The average cost under any optimal policy is obtained as a limit:
`J_ψ(i) = lim_{n→∞} v_{ψ,n}(i)/n` for every average cost optimal policy `ψ` and every `i`. -/
theorem thm_7_2_3_sen_acoi {S : Type} [Countable S] {Act : Type} (M : SennottDP.Discounted.MDC S Act) (z : S)
    (Mf : S → ℝ) (L : ℝ) (hSEN : SENAssumptions M z Mf L) :
    ∃ J : ℝ≥0,
      -- (i)
      (∀ i, Tendsto (fun α : ℝ => ENNReal.ofReal (1 - α) * discValue M α i) (𝓝[<] 1)
        (𝓝 (J : ℝ≥0∞))) ∧
      -- (ii)
      (∃ h : S → ℝ, IsLimitFunction M z h) ∧
      (∀ h : S → ℝ, IsLimitFunction M z h →
        (∀ i, -L ≤ h i ∧ h i ≤ Mf i) ∧
        (∀ i, acoiMin M h i ≤ (((J : ℝ) + h i : ℝ) : EReal)) ∧
        ∀ e : StationaryPolicy M, RealizesACOI M h e →
          IsAverageOptimal M e.toPolicy ∧ (∀ i, avgCost M e.toPolicy i = (J : ℝ≥0∞)) ∧
          ∀ i, Tendsto (fun n : ℕ => (((n : ℝ)⁻¹ : ℝ) : EReal) * expReal M e.toPolicy i n h)
            atTop (𝓝 0)) ∧
      -- (iii)
      (∀ fam : ℝ → StationaryPolicy M, (∀ α ∈ Set.Ioo (0 : ℝ) 1, RealizesDOE M α (fam α)) →
        ∀ f : StationaryPolicy M, IsLimitPoint M fam f →
          IsAverageOptimal M f.toPolicy ∧
          (∃ h : S → ℝ, IsAssociated M z fam f h) ∧
          ∀ h : S → ℝ, IsAssociated M z fam f h →
            (∀ i, ((M.C i (f.1 i) : ℝ) : EReal) + wsum (M.P i (f.1 i)) h ≤
              (((J : ℝ) + h i : ℝ) : EReal)) ∧
            ∀ i, Tendsto (fun n : ℕ => (((n : ℝ)⁻¹ : ℝ) : EReal) * expReal M f.toPolicy i n h)
              atTop (𝓝 0)) ∧
      -- (iv)
      (∀ ψ : SennottDP.Discounted.Policy M, IsAverageOptimal M ψ → ∀ i,
        Tendsto (fun n : ℕ => horizonCost M ψ n i / (n : ℝ≥0∞)) atTop (𝓝 (avgCost M ψ i))) := by sorry

end SennottDP.SEN
Source
Sennott, Stochastic Dynamic Programming and the Control of Queueing Systems (Wiley, 1999), pp. 134–135, Theorem 7.2.3, (7.9)–(7.12)
Human review
  • Endorsed by Shuze Chen · Oct 5, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 5, 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