Proposition 8.6.5 — strict transient bias improvement
DisprovedPutermanMDP.Unichain.strict_bias_improvementIn the finite unichain model, let evaluate the incumbent rule , and let be chosen by step 3 as printed. Suppose is zero at every state recurrent under and positive at some state transient under . The source asserts that
The two biases are the canonical vectors and . The printed assertion is retained; the counterexample under whole-rule tie retention is recorded separately in INSIGHTS.yaml. No statewise tie-retention hypothesis is inserted to repair it.
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
import Mathlib import Definitions.Def_PutermanMDP_Unichain_Iteration open MarkovDecisionProcesses Matrix
namespace PutermanMDP.Unichain
/-- Proposition 8.6.5 as printed. The meaning of step 3 is exactly `Improves`;
no extra statewise tie-retention assumption is inserted. -/
theorem strict_bias_improvement {S A : Type*} [Fintype S] [Fintype A]
[DecidableEq S] [Nonempty S] (M : StationaryMDP S A) (hM : IsUnichain M)
(d d' : Rule M) (g : ℝ) (h : S → ℝ)
(heval : Evaluates M d g h) (himp : Improves M d d' h)
(hrec : ∀ s, IsRecurrent (transMatrix M d'.val) s →
optimalityResidual M g h s = 0)
(htrans : ∃ s, ¬ IsRecurrent (transMatrix M d'.val) s ∧
0 < optimalityResidual M g h s) :
∃ s, ¬ IsRecurrent (transMatrix M d'.val) s ∧
policyBias M d s < policyBias M d' 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, and is a StationaryMDP with , an imported predicate not shown.
Data. are rules, , and .
Notation.
- , imported.
- is the set of states recurrent for (imported predicate), and .
- , an imported function not shown.
Hypotheses.
- Evaluation: for all ,
- Improvement: holds. That is, holds, and if holds then as whole rules. IsImproving is imported and not shown.
- for every .
- There exists with .
Conclusion. There exists a state with
where for a rule the bias is , with and . Three points about this conclusion:
- The state in the conclusion need not be the state given by hypothesis 4.
- The comparison is between the defined biases and , not between and anything.
- Nothing is asserted at the other states.
Degenerate cases. is excluded. If is empty, hypothesis 4 cannot hold and the statement is vacuous. It is likewise vacuous in each of the following cases:
- no rule exists;
- the evaluation equations for have no solution;
- no satisfies Improves;
- is unsatisfiable.
Nothing in the hypotheses excludes , subject to the imported definitions.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.