Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proposition 7.7.2 — the conclusions of Theorem 7.2.3 hold under the weaker (H) assumptions

Proved
SennottDP.SEN.prop_7_7_2_h_acoi

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

acoiaverage-costp2o-batch-b23ap2o-gran-per-chapterp2o-plan-bookp2o-v1

Let Δ\DeltaΔ be an MDC for which the (H) assumptions hold for the distinguished state zzz, with function MMM in (H2) and function LLL in (H3). Then the conclusions of Theorem 7.2.3 are valid, with LLL the function from (H3):

  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) for every iii;
  2. a limit function exists; every limit function hhh satisfies −L(i)≤h(i)≤M(i)-L(i) \le h(i) \le M(i)−L(i)≤h(i)≤M(i) and
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 this minimum is average cost optimal with Je≡JJ_e \equiv JJe​≡J, and lim⁡n1nEe[h(Xn)∣X0=i]=0\lim_n \frac1n E_e[h(X_n) \mid X_0 = i] = 0limn​n1​Ee​[h(Xn​)∣X0​=i]=0; 3. every limit point fff of stationary policies realizing the discount optimality equation is average cost optimal, has an associated limit function, and every associated hhh satisfies (7.11) and (7.12); 4. for every average cost optimal policy ψ\psiψ and every iii, Jψ(i)=lim⁡nvψ,n(i)/nJ_\psi(i) = \lim_n v_{\psi,n}(i)/nJψ​(i)=limn​vψ,n​(i)/n.

Formalization Note The statement is Theorem 7.2.3's, with the (H) assumptions in place of (SEN) and −L(i)≤h(i)-L(i) \le h(i)−L(i)≤h(i) in place of −L≤h-L \le h−L≤h; conventions are as there.

Preamble
import Mathlib
import Definitions.Def_SennottDP_SEN_Assumptions

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

/-- Sennott (1999), Proposition 7.7.2, p. 158: let `Δ` be an SennottDP.Discounted.MDC for which the (H) assumptions
hold for the distinguished state `z`, with function `Mf` in (H2) and function `Lf` in (H3). Then
the conclusions of Theorem 7.2.3 are valid, where `L` is the function `Lf` from (H3):

(i) there is a finite constant `J = lim_{α→1⁻} (1 − α) V_α(i)` for all `i`;
(ii) a limit function exists; every limit function `h` satisfies `−Lf ≤ h ≤ Mf` and the average
cost optimality inequality (7.9); every stationary policy `e` realizing the minimum in (7.9) is
average cost optimal with average cost `J`, and (7.10) holds;
(iii) every limit point `f` of discount optimal stationary policies is average cost optimal, has
an associated limit function, and every associated `h` satisfies (7.11) and (7.12);
(iv) the average cost under any average cost optimal policy is obtained as a limit. -/
theorem prop_7_7_2_h_acoi {S : Type} [Countable S] {Act : Type} (M : SennottDP.Discounted.MDC S Act) (z : S)
    (Mf Lf : S → ℝ) (hH : HAssumptions M z Mf Lf) :
    ∃ 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, -Lf i ≤ 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), p. 158, Proposition 7.7.2 (conclusions of Theorem 7.2.3, pp. 134–135)
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