Lemma 8.6.4 — transient blocks of the deviation matrix
ProvedPutermanMDP.Unichain.transient_deviationLet be an admissible rule in a finite stationary model, and suppose its transition matrix is unichain. Other policies need not be unichain. Partition the states into recurrent states and transient states , and partition accordingly. Then
Moreover, if a vector is zero on and nonnegative on , then
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
import Mathlib import Definitions.Def_PutermanMDP_Unichain_PolicyData open MarkovDecisionProcesses Matrix
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
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
Setting. and are finite types, is nonempty and has decidable equality, is a StationaryMDP, and is a rule (a function choosing admissible actions).
Hypothesis. holds, where . Both are imported and not shown.
Notation.
- , imported.
- is the set of states recurrent for (imported predicate), and .
Conclusion. All three of the following hold:
- for every and .
- The submatrix of equals . Here is the submatrix of , is the identity, and the inverse is the library's total inverse, which is the zero matrix when . So this clause by itself does not assert that is invertible. If were singular, the clause would say that the block of is zero.
- Let be any vector with for all and for all . Then for every :
The second inequality already follows from the two hypotheses on . At recurrent , the first inequality says .
Degenerate cases. is excluded. The statement is vacuous if no rule exists or if is unsatisfiable.
- If is empty (every state recurrent):
- clause 1 is vacuous;
- clause 2 is an equality of empty matrices;
- clause 3 forces and asserts .
- If is empty (only if the imported definitions permit it):
- clause 1 is vacuous;
- clause 3 concerns all nonnegative .
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.