Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 8.4.5 — existence of average optimal stationary policies in finite unichain models

Proved
MarkovDecisionProcesses.unichain_average_optimal_stationary_policy

by naimengye · Sep 23, 2026 · Mathlib 0df444a (Lean v4.33.1)

dynamic-programmingmarkov-decision-processesoperations-researchprobability

Consider a stationary MDP with finite state and action sets that is unichain. Then

  • (a) there is a deterministic stationary policy d∞d^\inftyd∞ that is average optimal: g−d∞(s)≥g+π(s)g^{d^\infty}_-(s)\ge g^\pi_+(s)g−d∞​(s)≥g+π​(s) for every state sss and every π∈ΠHR\pi\in\Pi^{HR}π∈ΠHR;
  • (b) there are a scalar g∗g^*g∗ and a function h∗:S→Rh^*:S\to\mathbb Rh∗:S→R with B(g∗,h∗)=0B(g^*,h^*)=0B(g∗,h∗)=0, and (d) this g∗g^*g∗ is the optimal gain under both remaining criteria: g+∗(s)=g−∗(s)=g∗g^*_+(s)=g^*_-(s)=g^*g+∗​(s)=g−∗​(s)=g∗ for every sss;
  • (c) for every solution (g∗,h∗)(g^*,h^*)(g∗,h∗) of the optimality equation and every h∗h^*h∗-improving decision rule ddd, the stationary policy d∞d^\inftyd∞ is average optimal.

This is Theorem 8.4.5, the chapter's existence theorem for unichain models, which the source assembles from Theorem 8.4.3 (existence of a solution), Theorem 8.4.4 (an improving rule is optimal) and Theorem 8.4.1 (the solution's scalar is the optimal gain). It is what justifies solving the single optimality equation B(g,h)=0B(g,h)=0B(g,h)=0 — by policy iteration, value iteration or linear programming in Sections 8.5 to 8.8 — instead of searching over policies, and it is why the three average optimality criteria of Section 8.1.2 coincide in finite unichain models.

Formalization Note Bounded rewards are automatic in a finite model. Part (d) is stated together with (b), as the identity g+∗=g−∗=g∗g^*_+=g^*_-=g^*g+∗​=g−∗​=g∗ for the scalar of the solution exhibited there; by Theorem 8.4.3(b) that scalar is the same for every solution. Part (a) exhibits a deterministic stationary policy, which is what "stationary" means in the chapter's Section 8.3.1 classification and is what the proof produces. "Average optimal" is criterion (8.1.7), the strongest of the three, against every history-dependent randomized policy.

Preamble
import Definitions.Def_MarkovDecisionProcesses_AverageReward
Formal statement
namespace MarkovDecisionProcesses
theorem unichain_average_optimal_stationary_policy {S A : Type*} [Fintype S] [Fintype A]
    [DecidableEq A] (M : StationaryMDP S A) (hM : IsUnichain M) :
    (∃ (d : S → A) (hd : ∀ s, d s ∈ M.admissible s),
        IsAverageOptimal (stationaryPolicy M d hd)) ∧
    (∃ (gstar : ℝ) (hstar : S → ℝ), (∀ s, optimalityResidual M gstar hstar s = 0) ∧
        ∀ s, optGainSup M s = gstar ∧ optGainInf M s = gstar) ∧
    (∀ (gstar : ℝ) (hstar : S → ℝ), (∀ s, optimalityResidual M gstar hstar s = 0) →
        ∀ (d : S → A) (hd : IsImproving M hstar d),
          IsAverageOptimal (stationaryPolicy M d (fun s => (hd s).1))) := by sorry
end MarkovDecisionProcesses
Source
Martin L. Puterman, Markov Decision Processes: Discrete Stochastic Dynamic Programming, Wiley 1994, https://doi.org/10.1002/9780470316887 — §8.4.3, printed p. 361 (PDF p. 377), Theorem 8.4.5: "Suppose S is finite and A_s is finite for each s ∈ S, r(s, a) is bounded and the model is unichain. Then a. there exists a stationary average optimal policy, b. there exists a scalar g* and an h* ∈ V for which B(g*, h*) = 0, c. any stationary policy derived from an h*-improving decision rule is average optimal, and d. g*e = g*_+ = g*_−."
Human review
  • Endorsed by Shuze Chen · Sep 25, 2026

    Confirmed by the moderator at approval.

  • Endorsed by naimengye · Sep 25, 2026

    Confirmed by the mission captain (proposal self-audit).

  • Endorsed by Community (Bot) · Oct 29, 2026

    Confirmed by the moderator at approval.

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