Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proposition 11.4.1 — stationary semi-Markov reward ratio

Disproved
PutermanMDP.SemiMarkov.stationary_ratio

by Shuze Chen · Oct 29, 2026 · Mathlib 0df444a (Lean v4.33.1)

average-rewardoperations-researchp2o-gran-per-chapterp2o-plan-bookp2o-v1semi-markovstationary-policy

Let SSS be nonempty and countable, and fix a stationary randomized rule ddd in a semi-Markov model satisfying Assumption 11.1.1. Suppose the Cesaro limit Md∗M_d^*Md∗​ exists and is a transition probability matrix. All finite-epoch expectations and the two limiting matrix products below are interpreted as finite, absolutely convergent expectations. Then the reward ratios converge and

gd∞(s)=lim⁡n→∞Rnd(s)=(Md∗rd)(s)(Md∗yd)(s).g^{d^\infty}(s)=\lim_{n\to\infty}R_n^d(s)=\frac{(M_d^*r_d)(s)}{(M_d^*y_d)(s)}.gd∞(s)=n→∞lim​Rnd​(s)=(Md∗​yd​)(s)(Md∗​rd​)(s)​.

If the embedded chain is unichain, this gain is one real constant independent of the initial state.

This is the source's stationary reward-ratio representation. Its literal countable-state claim is retained despite finding F3, which supplies a counterexample with unbounded mean holding times.

Formalization Note Absolute summability makes explicit the finite-real domain of the displayed expectations and matrix products; no uniform boundedness of rdr_drd​ or ydy_dyd​ is imposed. The gain itself uses an extended-real liminf, and the conclusion asserts equality with a real limit.

Preamble
import Definitions.Def_PutermanMDP_SemiMarkov_Stationary

open Filter
open scoped Topology
Formal statement
namespace PutermanMDP.SemiMarkov

theorem stationary_ratio {S : Type*} [Countable S] [Nonempty S]
    (M : Model S) (d : Rule M) (hNE : Nonexplosive M)
    (hP : CesaroProbability M d) (hE : FiniteEpochMoments M d)
    (hL : FiniteLimitMoments M d) :
    ((∀ s, Tendsto (fun n => rewardRatio M d n s) atTop
        (𝓝 (limitingRatio M d s))) ∧
      (∀ s, gain M d s = (limitingRatio M d s : EReal))) ∧
    (Unichain M d → ∃ g : ℝ, ∀ s, gain M d s = (g : EReal)) := by sorry

end PutermanMDP.SemiMarkov
Source
Puterman, Markov Decision Processes, Wiley, 1994, https://doi.org/10.1002/9780470316887, p. 551 (PDF 567), Proposition 11.4.1
Read-back

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

Setting. Let SSS be a countable, nonempty type of states and let MMM be a model on SSS. The model gives, for each state sss:

  • a nonempty action type A(s)A(s)A(s);
  • for each a∈A(s)a \in A(s)a∈A(s):
    • a next-state probability mass function P(⋅∣s,a)P(\cdot\mid s,a)P(⋅∣s,a) on SSS;
    • a probability measure Hs,aH_{s,a}Hs,a​ on [0,∞)[0,\infty)[0,∞) with finite mean τ(s,a)=∫t dHs,a\tau(s,a) = \int t\, dH_{s,a}τ(s,a)=∫tdHs,a​;
    • a real reward r(s,a)r(s,a)r(s,a).

Let ddd be a stationary randomized rule: probability mass functions qsq_sqs​ on A(s)A(s)A(s) such that a↦qs(a)r(s,a)a\mapsto q_s(a) r(s,a)a↦qs​(a)r(s,a) and a↦qs(a)τ(s,a)a \mapsto q_s(a)\tau(s,a)a↦qs​(a)τ(s,a) are absolutely summable. Write:

  • rd(s)=∑aqs(a)r(s,a)r_d(s) = \sum_a q_s(a)r(s,a)rd​(s)=∑a​qs​(a)r(s,a);
  • τd(s)=∑aqs(a)τ(s,a)\tau_d(s) = \sum_a q_s(a)\tau(s,a)τd​(s)=∑a​qs​(a)τ(s,a);
  • Pd(j∣s)=∑aqs(a)P(j∣s,a)P_d(j\mid s) = \sum_a q_s(a)P(j\mid s,a)Pd​(j∣s)=∑a​qs​(a)P(j∣s,a);
  • PdnP_d^nPdn​ for the nnn-fold composition, with Pd0(⋅∣s)=δsP_d^0(\cdot\mid s) = \delta_sPd0​(⋅∣s)=δs​.

Hypotheses.

  1. Nonexplosive. There are reals ε>0\varepsilon > 0ε>0 and δ>0\delta > 0δ>0 such that ε≤1\varepsilon \le 1ε≤1 and, for every sss and a∈A(s)a\in A(s)a∈A(s), Hs,a([0,δ])≤1−εH_{s,a}([0,\delta]) \le 1-\varepsilonHs,a​([0,δ])≤1−ε.
  2. Cesàro probability. Write Cn(s,j)=1n∑k=0n−1Pdk(j∣s)C_n(s,j) = \frac1n\sum_{k=0}^{n-1}P_d^k(j\mid s)Cn​(s,j)=n1​∑k=0n−1​Pdk​(j∣s), with C0=0C_0 = 0C0​=0, and Pd∗(s,j)=lim inf⁡nCn(s,j)P^*_d(s,j) = \liminf_n C_n(s,j)Pd∗​(s,j)=liminfn​Cn​(s,j). Then for all s,js,js,j:
    • Cn(s,j)→Pd∗(s,j)C_n(s,j) \to P^*_d(s,j)Cn​(s,j)→Pd∗​(s,j);
    • Pd∗(s,j)≥0P^*_d(s,j)\ge 0Pd∗​(s,j)≥0;
    • for every sss, ∑jPd∗(s,j)=1\sum_j P^*_d(s,j) = 1∑j​Pd∗​(s,j)=1.
  3. Finite epoch moments. For all nnn and sss, the families j↦Pdn(j∣s)rd(j)j\mapsto P_d^n(j\mid s) r_d(j)j↦Pdn​(j∣s)rd​(j) and j↦Pdn(j∣s)τd(j)j \mapsto P_d^n(j\mid s)\tau_d(j)j↦Pdn​(j∣s)τd​(j) are summable.
  4. Finite limit moments. For all sss, the families j↦Pd∗(s,j)rd(j)j\mapsto P^*_d(s,j) r_d(j)j↦Pd∗​(s,j)rd​(j) and j↦Pd∗(s,j)τd(j)j\mapsto P^*_d(s,j)\tau_d(j)j↦Pd∗​(s,j)τd​(j) are summable.

No boundedness of rdr_drd​ or τd\tau_dτd​ is assumed.

Quantities in the conclusion. Define

Rn(s)=∑k=0n∑jPdk(j∣s) rd(j),Tn(s)=∑k=0n∑jPdk(j∣s) τd(j),ρn(s)=Rn(s)Tn(s),R_n(s) = \sum_{k=0}^n\sum_j P_d^k(j\mid s)\, r_d(j),\qquad T_n(s) = \sum_{k=0}^n\sum_j P_d^k(j\mid s)\,\tau_d(j),\qquad \rho_n(s) = \frac{R_n(s)}{T_n(s)},Rn​(s)=k=0∑n​j∑​Pdk​(j∣s)rd​(j),Tn​(s)=k=0∑n​j∑​Pdk​(j∣s)τd​(j),ρn​(s)=Tn​(s)Rn​(s)​, ρˉ(s)=∑jPd∗(s,j) rd(j)∑jPd∗(s,j) τd(j),gd(s)=lim inf⁡n→∞ρn(s)∈[−∞,+∞].\bar\rho(s) = \frac{\sum_j P^*_d(s,j)\, r_d(j)}{\sum_j P^*_d(s,j)\,\tau_d(j)},\qquad g_d(s) = \liminf_{n\to\infty}\rho_n(s) \in [-\infty,+\infty].ρˉ​(s)=∑j​Pd∗​(s,j)τd​(j)∑j​Pd∗​(s,j)rd​(j)​,gd​(s)=n→∞liminf​ρn​(s)∈[−∞,+∞].

Both ratios use the convention x/0=0x/0 = 0x/0=0.

Conclusion. The statement asserts all three of:

  • (a) for every sss, ρn(s)→ρˉ(s)\rho_n(s) \to \bar\rho(s)ρn​(s)→ρˉ​(s) in R\mathbb{R}R as n→∞n\to\inftyn→∞;
  • (b) for every sss, gd(s)=ρˉ(s)g_d(s) = \bar\rho(s)gd​(s)=ρˉ​(s), so in particular gd(s)g_d(s)gd​(s) is finite;
  • (c) if ddd is unichain, then there is a single real number ggg with gd(s)=gg_d(s) = ggd​(s)=g for every sss. Unichain here means that some state sss has ∑nPdn(s∣s)=+∞\sum_n P_d^n(s\mid s) = +\infty∑n​Pdn​(s∣s)=+∞, and that for any two such recurrent states s,js, js,j some Pdn(j∣s)>0P_d^n(j\mid s) > 0Pdn​(j∣s)>0 with n≥0n \ge 0n≥0.

Degenerate cases.

  • SSS empty. Excluded, because SSS is assumed nonempty.
  • Zero denominators.
    • If Tn(s)=0T_n(s) = 0Tn​(s)=0 for some nnn, then ρn(s)\rho_n(s)ρn​(s) is 000 at that nnn.
    • If ∑jPd∗(s,j)τd(j)=0\sum_j P^*_d(s,j)\tau_d(j) = 0∑j​Pd∗​(s,j)τd​(j)=0, then the limit asserted in (a), and the value asserted in (b), is ρˉ(s)=0\bar\rho(s) = 0ρˉ​(s)=0.
  • Index range. RnR_nRn​ and TnT_nTn​ include the k=0k = 0k=0 term, so R0(s)=rd(s)R_0(s) = r_d(s)R0​(s)=rd​(s) and T0(s)=τd(s)T_0(s) = \tau_d(s)T0​(s)=τd​(s).
  • SSS a single state sss.
    • Pdn=1P_d^n = 1Pdn​=1, Pd∗=1P^*_d = 1Pd∗​=1, and the state is recurrent, so the unichain premise holds.
    • ρn=rd/τd\rho_n = r_d/\tau_dρn​=rd​/τd​ for every nnn, or 000 if τd=0\tau_d = 0τd​=0, and ρˉ\bar\rhoρˉ​ equals the same value.
    • The conclusion then says the gain equals this value.
Human review
  • Endorsed by Community (Bot) · Oct 29, 2026

    Confirmed by the moderator at approval.

  • Endorsed by Shuze Chen · Oct 29, 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