Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 11.4.2 — evaluation equation identifies the gain

Disproved
PutermanMDP.SemiMarkov.evaluation_identifies_gain

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. Assume that its embedded chain is unichain, its Cesaro limit is a probability matrix, and Assumption 11.1.1 holds. The finite-epoch reward and time expectations are finite. If a real constant ggg and a real function hhh satisfy

h=rd−gyd+Mdh,h=r_d-g y_d+M_dh,h=rd​−gyd​+Md​h,

with each transition expectation of hhh absolutely convergent, then

gd∞(s)=g(s∈S).g^{d^\infty}(s)=g\qquad(s\in S).gd∞(s)=g(s∈S).

This is the printed gain-identification assertion. The statement deliberately retains an arbitrary, possibly unbounded hhh; finding F1 and its draft verification F4 show that this literal formulation is false.

Formalization Note The finite-moment predicates specify the real-expectation domain. They do not impose invariant integrability or boundedness of hhh. The extended gain is asserted equal to the real scalar ggg.

Preamble
import Definitions.Def_PutermanMDP_SemiMarkov_Stationary
Formal statement
namespace PutermanMDP.SemiMarkov

theorem evaluation_identifies_gain {S : Type*} [Countable S] [Nonempty S]
    (M : Model S) (d : Rule M) (hNE : Nonexplosive M)
    (hU : Unichain M d) (hP : CesaroProbability M d)
    (hE : FiniteEpochMoments M d)
    (g : ℝ) (h : S → ℝ) (hEq : EvaluationEquation M d (fun _ => g) h) :
    ∀ 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. 552 (PDF 568), Theorem 11.4.2
Read-back

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

Setting. SSS is a state space: any type that is countable (finite or countably infinite) and nonempty. Its countability and nonemptiness are the only structural assumptions. MMM is an object of type Model over SSS, and ddd is an object of type Rule for MMM. The names suggest a semi-Markov decision model and a decision rule, but this code does not show what either type contains: both are defined in the imported file Definitions.Def_PutermanMDP_SemiMarkov_Stationary, which is not reproduced here.

Hypotheses. Five named conditions are assumed. Each one is a predicate defined in the same imported file, and this read-back does not unfold any of them.

  • Nonexplosive(M)\texttt{Nonexplosive}(M)Nonexplosive(M) is a condition on the model alone.
  • Unichain(M,d)\texttt{Unichain}(M, d)Unichain(M,d) is a condition on the model together with the rule ddd.
  • CesaroProbability(M,d)\texttt{CesaroProbability}(M, d)CesaroProbability(M,d) is a condition on the model together with the rule ddd.
  • FiniteEpochMoments(M,d)\texttt{FiniteEpochMoments}(M, d)FiniteEpochMoments(M,d) is a condition on the model together with the rule ddd.
  • Fix a real number g∈Rg \in \mathbb{R}g∈R and a real-valued function h:S→Rh : S \to \mathbb{R}h:S→R. The pair satisfies EvaluationEquation(M,d,gˉ,h)\texttt{EvaluationEquation}(M, d, \bar g, h)EvaluationEquation(M,d,gˉ​,h), where gˉ:S→R\bar g : S \to \mathbb{R}gˉ​:S→R is the constant function gˉ(s)=g\bar g(s) = ggˉ​(s)=g for every state sss. In other words, the "gain" argument of the evaluation equation is a constant vector with value ggg. Nothing further is assumed about hhh: it may be unbounded, and it has no normalisation.

Conclusion. For every state s∈Ss \in Ss∈S,

gain⁡M,d(s)=g,\operatorname{gain}_{M,d}(s) = g,gainM,d​(s)=g,

where gain⁡M,d(s)\operatorname{gain}_{M,d}(s)gainM,d​(s) is the quantity gain M d s defined in the imported file. That quantity takes values in the extended reals R‾=[−∞,+∞]\overline{\mathbb{R}} = [-\infty, +\infty]R=[−∞,+∞], and ggg is viewed there as a finite extended real. So the statement says three things together:

  • the gain is finite at every state;
  • the gain is the same at every state;
  • the gain equals the constant ggg that appears in the evaluation equation.

Degenerate cases. SSS cannot be empty, but it may have exactly one element. In that case the conclusion is the single equation gain⁡M,d(s0)=g\operatorname{gain}_{M,d}(s_0) = ggainM,d​(s0​)=g at the only state s0s_0s0​. Because gain is R‾\overline{\mathbb{R}}R-valued, the conclusion rules out the values ±∞\pm\infty±∞ whenever the hypotheses hold. If the five hypotheses can never hold together for any MMM and ddd, or if no pair (g,h)(g, h)(g,h) satisfies the evaluation equation, then the theorem is vacuously true. Whether either happens depends on the imported definitions, which this code does not show.

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