Theorem 10.3.6 — finite sensitivity implies Blackwell optimality
DisprovedPutermanMDP.Sensitive.finite_sensitivity_blackwellConsider a finite-state, finite-action Markov decision process, and let be a deterministic stationary decision rule. Suppose has recurrent classes and is -discount optimal. The printed theorem asserts both conclusions:
All optimality comparisons are against every history-dependent randomized policy. This policy-specific threshold is the mission's faithful goal. FINDINGS records an explicit two-state counterexample to the printed theorem; no corrected claim is substituted.
Formalization Note counts the closed irreducible classes of itself, not a minimum over other policies. The threshold is computed in the integers, including .
import Mathlib import Definitions.Def_PutermanMDP_Sensitive_Model
namespace PutermanMDP.Sensitive
/-- Printed Theorem 10.3.6; its policy-specific recurrent count is preserved. -/
theorem finite_sensitivity_blackwell {S A : Type} [Fintype S] [DecidableEq S] [Nonempty S] [Fintype A]
(M : Model S A) (dstar : DecisionRule M) (r : ℕ)
(hopt : NDiscountOptimal (stationary dstar) ((Fintype.card S : ℤ) - (r : ℤ) - 1))
(hr : recurrentCount (policyMatrix dstar) = r) :
BlackwellOptimal (stationary dstar) ∧
∀ n : ℤ, -1 ≤ n → NDiscountOptimal (stationary dstar) n := by sorry
end PutermanMDP.Sensitive
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
Let be a state space and an action space. Both are finite types. is nonempty and has decidable equality. is not assumed nonempty. Let be an object of type Model S A, which is a notion defined in the imported module Definitions.Def_PutermanMDP_Sensitive_Model. The names suggest a Markov decision process, but this read-back cannot unfold what that type contains. The other notions used below come from the same module and are also not unfolded here:
DecisionRule MstationarypolicyMatrixrecurrentCountNDiscountOptimalBlackwellOptimal
An auditor needs their definitions to judge what the statement means.
Fix the following:
- a decision rule for ;
- the stationary policy built from it, written
stationary dstar; - a natural number .
The statement has two hypotheses:
- (Optimality at one index.) is -discount optimal, in the sense of
NDiscountOptimal, for the single integer index
where is the number of states. This is computed in , not in , so it is a true difference and can be negative.
2. (Recurrent count.) Let be the matrix policyMatrix dstar. The quantity recurrentCount of equals .
Because of hypothesis 2, is not a free parameter: it is fixed by . Together, the hypotheses say exactly that is -discount optimal.
The conclusion is a conjunction of two claims:
- is Blackwell optimal, in the sense of
BlackwellOptimal. - For every integer , is -discount optimal:
This second claim covers infinitely many indices: , including every index above .
Degenerate cases.
- One state (). The index is . It equals if , if , and is below if .
- Large recurrent count. In general, if , then . If it is , then , so the hypothesis asks for optimality at an index below the range the conclusion covers. The statement itself places no bound on
recurrentCount. Whether such values can occur, and whatNDiscountOptimalmeans at indices below , depends entirely on the unexpanded definitions. If it holds trivially or is empty there, the hypothesis is correspondingly weak or vacuous. - Zero recurrent count. If , then .
- Empty action type. may be empty. If that makes
DecisionRule Muninhabited, the statement holds vacuously in that case. - What this code asserts. No division, natural-number subtraction, integral or supremum appears in this statement's own code; the only subtraction is the integer one in . Any such junk-value behaviour would sit inside the imported definitions and cannot be judged from this code.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.