Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 8.6.4 — transient blocks of the deviation matrix

Proved
PutermanMDP.Unichain.transient_deviation

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

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

Let ddd be an admissible rule in a finite stationary model, and suppose its transition matrix PdP_dPd​ is unichain. Other policies need not be unichain. Partition the states into recurrent states RdR_dRd​ and transient states TdT_dTd​, and partition HdH_dHd​ accordingly. Then

HdRT=0,HdTT=(I−PdTT)−1.H_d^{RT}=0,\qquad H_d^{TT}=(I-P_d^{TT})^{-1}.HdRT​=0,HdTT​=(I−PdTT​)−1.

Moreover, if a vector uuu is zero on RdR_dRd​ and nonnegative on TdT_dTd​, then

Hdu≥u≥0.H_du\ge u\ge0.Hd​u≥u≥0.

Both inequalities are coordinatewise. This statement includes all three clauses of the source lemma and allows an empty transient set.

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: 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: canonical recurrent/transient block matrix → entries with recurrent/transient predicates and matrices indexed by the transient subtype; reason: restriction to these indices is the same block decomposition without choosing a permutation of the state set
Preamble
import Mathlib
import Definitions.Def_PutermanMDP_Unichain_PolicyData
open MarkovDecisionProcesses Matrix
Formal statement
namespace PutermanMDP.Unichain

/-- Lemma 8.6.4: all three clauses, including the full transient inverse. -/
theorem transient_deviation {S A : Type*} [Fintype S] [Fintype A]
    [DecidableEq S] [Nonempty S] (M : StationaryMDP S A) (d : Rule M)
    (hd : IsUnichainMatrix (transMatrix M d.val)) :
    (∀ i j, IsRecurrent (transMatrix M d.val) i →
      ¬ IsRecurrent (transMatrix M d.val) j → policyDeviation M d i j = 0) ∧
    (transientBlock (transMatrix M d.val) (policyDeviation M d) =
      transientResolvent (transMatrix M d.val)) ∧
    (∀ u : S → ℝ,
      (∀ s, IsRecurrent (transMatrix M d.val) s → u s = 0) →
      (∀ s, ¬ IsRecurrent (transMatrix M d.val) s → 0 ≤ u s) →
      ∀ s, u s ≤ (policyDeviation M d).mulVec u s ∧ 0 ≤ u s) := by sorry

end PutermanMDP.Unichain
Source
Puterman, Markov Decision Processes, Wiley, 1994, p. 381 (PDF 397), Lemma 8.6.4, (8.6.11); proof p. 382 (PDF 398)
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, MMM is a StationaryMDP, and ddd is a rule (a function S→AS\to AS→A choosing admissible actions).

Hypothesis. IsUnichainMatrix(Pd)\mathrm{IsUnichainMatrix}(P_d)IsUnichainMatrix(Pd​) holds, where Pd=transMatrix(M,d)P_d = \mathrm{transMatrix}(M,d)Pd​=transMatrix(M,d). Both are imported and not shown.

Notation.

  • Hd=deviationMatrix(Pd)H_d = \mathrm{deviationMatrix}(P_d)Hd​=deviationMatrix(Pd​), imported.
  • RRR is the set of states recurrent for PdP_dPd​ (imported predicate), and T=S∖RT = S \setminus RT=S∖R.

Conclusion. All three of the following hold:

  1. Hd(i,j)=0H_d(i,j) = 0Hd​(i,j)=0 for every i∈Ri \in Ri∈R and j∈Tj \in Tj∈T.
  2. The T×TT\times TT×T submatrix of HdH_dHd​ equals (I−PTT)−1(I - P_{TT})^{-1}(I−PTT​)−1. Here PTTP_{TT}PTT​ is the T×TT\times TT×T submatrix of PdP_dPd​, III is the T×TT\times TT×T identity, and the inverse is the library's total inverse, which is the zero matrix when det⁡(I−PTT)=0\det(I-P_{TT}) = 0det(I−PTT​)=0. So this clause by itself does not assert that I−PTTI - P_{TT}I−PTT​ is invertible. If I−PTTI - P_{TT}I−PTT​ were singular, the clause would say that the T×TT\times TT×T block of HdH_dHd​ is zero.
  3. Let u∈RSu \in \mathbb{R}^Su∈RS be any vector with u(s)=0u(s) = 0u(s)=0 for all s∈Rs\in Rs∈R and u(s)≥0u(s)\ge 0u(s)≥0 for all s∈Ts \in Ts∈T. Then for every s∈Ss\in Ss∈S:
u(s)≤(Hd u)(s)and0≤u(s).u(s) \le (H_d\,u)(s) \quad\text{and}\quad 0 \le u(s).u(s)≤(Hd​u)(s)and0≤u(s).

The second inequality already follows from the two hypotheses on uuu. At recurrent sss, the first inequality says 0≤(Hdu)(s)0 \le (H_d u)(s)0≤(Hd​u)(s).

Degenerate cases. S=∅S=\emptysetS=∅ is excluded. The statement is vacuous if no rule exists or if IsUnichainMatrix(Pd)\mathrm{IsUnichainMatrix}(P_d)IsUnichainMatrix(Pd​) is unsatisfiable.

  • If TTT is empty (every state recurrent):
    • clause 1 is vacuous;
    • clause 2 is an equality of empty matrices;
    • clause 3 forces u=0u = 0u=0 and asserts 0≤00 \le 00≤0.
  • If RRR is empty (only if the imported definitions permit it):
    • clause 1 is vacuous;
    • clause 3 concerns all nonnegative uuu.
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