Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 5.9 — under Sennott's Assumptions 5.14–5.16 an AC-optimal stationary policy exists

Proved
ArapostathisAC.SennottACOI.theorem_5_9

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

average-costcontrolled-markov-processexistence-of-optimal-policyp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1vanishing-discount

Consider a controlled Markov process with countable state space S={0,1,2,… }S=\{0,1,2,\dots\}S={0,1,2,…}, nonempty compact admissible action sets U(i)U(i)U(i), a nonnegative one-stage cost c(i,a)c(i,a)c(i,a) and transition probabilities P(j∣i,a)P(j\mid i,a)P(j∣i,a), with c(i,⋅)c(i,\cdot)c(i,⋅) and P(j∣i,⋅)P(j\mid i,\cdot)P(j∣i,⋅) continuous on U(i)U(i)U(i). Let Jβ∗J^*_\betaJβ∗​ be the optimal β\betaβ-discounted cost, hβ(i)=Jβ∗(i)−Jβ∗(0)h_\beta(i)=J^*_\beta(i)-J^*_\beta(0)hβ​(i)=Jβ∗​(i)−Jβ∗​(0), and suppose:

  1. (Assumption 5.14) Jβ∗(i)<∞J^*_\beta(i)<\inftyJβ∗​(i)<∞ for every i∈Si\in Si∈S and β∈(0,1)\beta\in(0,1)β∈(0,1);
  2. (Assumption 5.15) there is a nonnegative integer LLL with hβ(i)≥−Lh_\beta(i)\ge-Lhβ​(i)≥−L for all iii and β\betaβ;
  3. (Assumption 5.16) there is M:S→R+M:S\to\mathbb R_+M:S→R+​ with hβ(i)≤M(i)h_\beta(i)\le M(i)hβ​(i)≤M(i) for all iii and β\betaβ, and for each iii an action a(i)∈U(i)a(i)\in U(i)a(i)∈U(i) with ∑jP(j∣i,a(i))M(j)<∞\sum_jP(j\mid i,a(i))M(j)<\infty∑j​P(j∣i,a(i))M(j)<∞.

Then there exists a stationary deterministic policy f∈ΠSDf\in\Pi_{SD}f∈ΠSD​ that is AC-optimal:

J(i,f)=lim sup⁡N→∞1NEif∑t=0N−1c(Xt,At)=inf⁡π∈ΠJ(i,π)=J∗(i)for every i∈S,J(i,f)=\limsup_{N\to\infty}\frac1N E^f_i\sum_{t=0}^{N-1}c(X_t,A_t)=\inf_{\pi\in\Pi}J(i,\pi)=J^*(i)\qquad\text{for every }i\in S,J(i,f)=N→∞limsup​N1​Eif​t=0∑N−1​c(Xt​,At​)=π∈Πinf​J(i,π)=J∗(i)for every i∈S,

the infimum ranging over all admissible policies, history dependent and randomized.

This is Sennott's existence theorem for average-cost optimal stationary policies with unbounded costs, in the form surveyed by Arapostathis et al.; it requires no bounded solution of the average cost optimality equation, only the one-sided conditions above.

Formalization Note The average costs are lim sup⁡\limsuplimsups in [0,∞][0,\infty][0,∞] and the optimal average cost is the infimum over the class Π\PiΠ of all admissible policies. Assumptions 5.14–5.16 are the definitions Assumption5_14, Assumption5_15, Assumption5_16; the differential value hβh_\betahβ​ is used only together with Assumption 5.14, so it is never read off an infinite Jβ∗J^*_\betaJβ∗​. The proof also shows that J(i,f)=J∗(i)J(i,f)=J^*(i)J(i,f)=J∗(i) is a constant ρ∗\rho^*ρ∗ and that fff attains an average cost optimality inequality; these are stated in the milestones, not in this goal.

Preamble
import Mathlib
import Definitions.Def_ArapostathisAC_SennottACOI_CMP
import Definitions.Def_ArapostathisAC_SennottACOI_Assumptions

open MeasureTheory ProbabilityTheory Filter Topology
open scoped ENNReal
Formal statement
namespace ArapostathisAC.SennottACOI

variable {A : Type*} [MetricSpace A] [MeasurableSpace A] [BorelSpace A]

/-- Theorem 5.9 (p. 308): under Assumptions 5.14–5.16 there exists an AC-optimal stationary
deterministic policy `f ∈ Π_SD`, i.e. `J(i, f) = J*(i) = inf_{π ∈ Π} J(i, π)` for every state
`i`, the infimum ranging over all admissible (history-dependent, randomized) policies. -/
theorem theorem_5_9 (M : ArapostathisAC.VanishingDiscount.CMP A) (h14 : Assumption5_14 M) (h15 : Assumption5_15 M)
    (h16 : Assumption5_16 M) :
    ∃ f : StationaryPolicy M, ArapostathisAC.VanishingDiscount.IsAvgOptimal M f := by sorry

end ArapostathisAC.SennottACOI
Source
Arapostathis, Borkar, Fernández-Gaucherand, Ghosh, Marcus, Discrete-time controlled Markov processes with average cost criterion: a survey, SIAM J. Control Optim. 31(2) (1993), p. 308, Theorem 5.9 (Assumptions 5.14–5.16, p. 307)
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