Proposition 8.6.1 — gain improvement
ProvedPutermanMDP.Unichain.gain_improvementConsider the finite unichain model of §8.6. Let be admissible stationary rules, let evaluate and evaluate , and suppose maximizes . Write for the optimality residual. Then
If at some state recurrent under , then . If vanishes at every state recurrent under , then .
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
import Mathlib import Definitions.Def_PutermanMDP_Unichain_Iteration open MarkovDecisionProcesses Matrix
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
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, and is a StationaryMDP satisfying , an imported predicate not shown.
Data.
- are rules, that is, functions with for all .
- and .
Hypotheses.
- evaluates :
- evaluates in the same sense.
- holds. This predicate is imported and not shown.
Notation for the conclusion.
- , an imported function not shown.
- , imported.
- , imported.
- is the set of states recurrent for , an imported predicate.
Conclusion. All three of the following hold:
- For every ,
In particular, the right-hand side takes the same value at every . 2. If there is some with , then (strict inequality). 3. If for every , then .
What is not required.
- is not required.
- Only IsImproving for is assumed, not the tie-retention condition.
- appears only in the evaluation hypothesis for .
- is any solution of the evaluation equations for , with no normalization.
Degenerate cases. is required to be nonempty, so is excluded. If no rule exists (some admissible set is empty, or is empty), the statement is vacuous. It is also vacuous if admits no pair satisfying either evaluation equation, or if cannot hold. If 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 .
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.