Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proposition 8.6.1 — gain improvement

Proved
PutermanMDP.Unichain.gain_improvement

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

average-rewardmarkov-decision-processesp2o-gran-per-chapterp2o-plan-bookp2o-v1policy-iterationunichain

Consider the finite unichain model of §8.6. Let d,d′d,d'd,d′ be admissible stationary rules, let (g,h)(g,h)(g,h) evaluate ddd and (g′,h′)(g',h')(g′,h′) evaluate d′d'd′, and suppose d′d'd′ maximizes rd+Pdhr_d+P_dhrd​+Pd​h. Write B(g,h)B(g,h)B(g,h) for the optimality residual. Then

g′e=ge+Pd′∗B(g,h).g'e=ge+P_{d'}^*B(g,h).g′e=ge+Pd′∗​B(g,h).

If B(g,h)(s)>0B(g,h)(s)>0B(g,h)(s)>0 at some state recurrent under d′d'd′, then g′>gg'>gg′>g. If B(g,h)B(g,h)B(g,h) vanishes at every state recurrent under d′d'd′, then g′=gg'=gg′=g.

All three conclusions are included. This result separates improvements of the long-run average reward from changes confined to transient states. It does not need tie retention.

Differences from the source:

  • encoding: finite nonempty state set and finite nonempty state-dependent action sets → finite types S and A, Nonempty S, and nonempty admissible finsets; reason: the union of finitely many finite action sets is finite; irrelevant action entries can be extended by zero rewards and any stochastic row
  • encoding: standing finite unichain model of §8.6 with bounded rewards → IsUnichain M and a finite stationary MDP; reason: finiteness makes the reward bound automatic; no irreducibility or aperiodicity is added
  • encoding: decision rules d_n and d_{n+1} and their evaluation solutions → admissible-rule subtypes d and d′, with explicit evaluation equations; reason: these are the algorithm variables and equations (8.6.1), not assumptions of improvement or termination
  • encoding: P* is the Cesàro limit and H = (I − P + P*)⁻¹(I − P*) → published Cesàro limit and equivalent deviation matrix (I − P + P*)⁻¹ − P*; reason: for finite stochastic P, (I − P + P*)⁻¹P* = P*, so these are the same matrices, including periodic chains
  • encoding: g_{d_n}, h_{d_n} in clause (c) → the same evaluation pair g,h as in clauses (a)–(b); reason: any two bias solutions differ by a constant, and the residual is invariant under that constant
Preamble
import Mathlib
import Definitions.Def_PutermanMDP_Unichain_Iteration
open MarkovDecisionProcesses Matrix
Formal statement
namespace PutermanMDP.Unichain

/-- Proposition 8.6.1, all three conclusions, in the finite unichain setting
of §8.6. No tie retention is needed for this proposition. -/
theorem gain_improvement {S A : Type*} [Fintype S] [Fintype A]
    [DecidableEq S] [Nonempty S] (M : StationaryMDP S A) (hM : IsUnichain M)
    (d d' : Rule M) (g g' : ℝ) (h h' : S → ℝ)
    (heval : Evaluates M d g h) (heval' : Evaluates M d' g' h')
    (himp : IsImproving M h d'.val) :
    (∀ s, g' = g + (policyLimit M d').mulVec (optimalityResidual M g h) s) ∧
    ((∃ s, IsRecurrent (transMatrix M d'.val) s ∧
        0 < optimalityResidual M g h s) → g < g') ∧
    ((∀ s, IsRecurrent (transMatrix M d'.val) s →
        optimalityResidual M g h s = 0) → g' = g) := by sorry

end PutermanMDP.Unichain
Source
Puterman, Markov Decision Processes, Wiley, 1994, p. 379 (PDF 395), Proposition 8.6.1, (8.6.9)
Read-back

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

Setting. SSS and AAA are finite types, SSS is nonempty and has decidable equality, and MMM is a StationaryMDP satisfying IsUnichain(M)\mathrm{IsUnichain}(M)IsUnichain(M), an imported predicate not shown.

Data.

  • d,d′d, d'd,d′ are rules, that is, functions S→AS \to AS→A with d(s),d′(s)∈M.admissible(s)d(s), d'(s) \in M.\mathrm{admissible}(s)d(s),d′(s)∈M.admissible(s) for all sss.
  • g,g′∈Rg, g' \in \mathbb{R}g,g′∈R and h,h′∈RSh, h' \in \mathbb{R}^Sh,h′∈RS.

Hypotheses.

  • (g,h)(g,h)(g,h) evaluates ddd:
g+h(s)=r(s,d(s))+∑jp(j∣s,d(s)) h(j)for all s.g + h(s) = r(s,d(s)) + \sum_j p(j\mid s,d(s))\,h(j) \quad\text{for all } s.g+h(s)=r(s,d(s))+j∑​p(j∣s,d(s))h(j)for all s.
  • (g′,h′)(g',h')(g′,h′) evaluates d′d'd′ in the same sense.
  • IsImproving(M,h,d′)\mathrm{IsImproving}(M,h,d')IsImproving(M,h,d′) holds. This predicate is imported and not shown.

Notation for the conclusion.

  • ψ:=optimalityResidual(M,g,h)∈RS\psi := \mathrm{optimalityResidual}(M,g,h) \in \mathbb{R}^Sψ:=optimalityResidual(M,g,h)∈RS, an imported function not shown.
  • Pd′=transMatrix(M,d′)P_{d'} = \mathrm{transMatrix}(M,d')Pd′​=transMatrix(M,d′), imported.
  • Pd′∗=limitMatrix(Pd′)P^*_{d'} = \mathrm{limitMatrix}(P_{d'})Pd′∗​=limitMatrix(Pd′​), imported.
  • Rd′R_{d'}Rd′​ is the set of states recurrent for Pd′P_{d'}Pd′​, an imported predicate.

Conclusion. All three of the following hold:

  1. For every s∈Ss \in Ss∈S,
g′=g+(Pd′∗ ψ)(s).g' = g + \bigl(P^*_{d'}\,\psi\bigr)(s).g′=g+(Pd′∗​ψ)(s).

In particular, the right-hand side takes the same value at every sss. 2. If there is some s∈Rd′s \in R_{d'}s∈Rd′​ with ψ(s)>0\psi(s) > 0ψ(s)>0, then g<g′g < g'g<g′ (strict inequality). 3. If ψ(s)=0\psi(s) = 0ψ(s)=0 for every s∈Rd′s \in R_{d'}s∈Rd′​, then g′=gg' = gg′=g.

What is not required.

  • d′≠dd' \neq dd′=d is not required.
  • Only IsImproving for d′d'd′ is assumed, not the tie-retention condition.
  • h′h'h′ appears only in the evaluation hypothesis for d′d'd′.
  • hhh is any solution of the evaluation equations for ddd, with no normalization.

Degenerate cases. SSS is required to be nonempty, so S=∅S = \emptysetS=∅ is excluded. If no rule exists (some admissible set is empty, or AAA is empty), the statement is vacuous. It is also vacuous if MMM admits no pair satisfying either evaluation equation, or if IsUnichain(M)\mathrm{IsUnichain}(M)IsUnichain(M) cannot hold. If Rd′R_{d'}Rd′​ is empty under the imported definition of recurrence, then:

  • the hypothesis of clause 2 is false, so clause 2 holds trivially;
  • the hypothesis of clause 3 holds vacuously, so clause 3 asserts g′=gg' = gg′=g.
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