Proposition 11.4.1 — stationary semi-Markov reward ratio
DisprovedPutermanMDP.SemiMarkov.stationary_ratioLet be nonempty and countable, and fix a stationary randomized rule in a semi-Markov model satisfying Assumption 11.1.1. Suppose the Cesaro limit 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
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 or is imposed. The gain itself uses an extended-real liminf, and the conclusion asserts equality with a real limit.
import Definitions.Def_PutermanMDP_SemiMarkov_Stationary open Filter open scoped Topology
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
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
Setting. Let be a countable, nonempty type of states and let be a model on . The model gives, for each state :
- a nonempty action type ;
- for each :
- a next-state probability mass function on ;
- a probability measure on with finite mean ;
- a real reward .
Let be a stationary randomized rule: probability mass functions on such that and are absolutely summable. Write:
- ;
- ;
- ;
- for the -fold composition, with .
Hypotheses.
- Nonexplosive. There are reals and such that and, for every and , .
- Cesàro probability. Write , with , and . Then for all :
- ;
- ;
- for every , .
- Finite epoch moments. For all and , the families and are summable.
- Finite limit moments. For all , the families and are summable.
No boundedness of or is assumed.
Quantities in the conclusion. Define
Both ratios use the convention .
Conclusion. The statement asserts all three of:
- (a) for every , in as ;
- (b) for every , , so in particular is finite;
- (c) if is unichain, then there is a single real number with for every . Unichain here means that some state has , and that for any two such recurrent states some with .
Degenerate cases.
- empty. Excluded, because is assumed nonempty.
- Zero denominators.
- If for some , then is at that .
- If , then the limit asserted in (a), and the value asserted in (b), is .
- Index range. and include the term, so and .
- a single state .
- , , and the state is recurrent, so the unichain premise holds.
- for every , or if , and equals the same value.
- The conclusion then says the gain equals this value.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.