Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 10.3.6 — finite sensitivity implies Blackwell optimality

Disproved
PutermanMDP.Sensitive.finite_sensitivity_blackwell

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

blackwell-optimalitymdpp2o-gran-per-chapterp2o-plan-bookp2o-v1sensitive-discount

Consider a finite-state, finite-action Markov decision process, and let d∗d^*d∗ be a deterministic stationary decision rule. Suppose Pd∗P_{d^*}Pd∗​ has rrr recurrent classes and (d∗)∞(d^*)^\infty(d∗)∞ is (∣S∣−r−1)(|S|-r-1)(∣S∣−r−1)-discount optimal. The printed theorem asserts both conclusions:

(d∗)∞ is Blackwell optimal,(d^*)^\infty\text{ is Blackwell optimal},(d∗)∞ is Blackwell optimal, ∀n∈Z, n≥−1 ⟹ (d∗)∞ is n-discount optimal.\forall n\in\mathbb Z,\ n\ge-1\ \Longrightarrow\ (d^*)^\infty\text{ is }n\text{-discount optimal}.∀n∈Z, n≥−1 ⟹ (d∗)∞ is n-discount optimal.

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 rrr counts the closed irreducible classes of Pd∗P_{d^*}Pd∗​ itself, not a minimum over other policies. The threshold is computed in the integers, including −1-1−1.

Preamble
import Mathlib
import Definitions.Def_PutermanMDP_Sensitive_Model
Formal statement
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
Source
Puterman, Markov Decision Processes, Wiley, 1994, p. 518 (PDF 534), Theorem 10.3.6; https://doi.org/10.1002/9780470316887
Read-back

What the Lean code literally says, in plain math · claude-opus-5-5

Let SSS be a state space and AAA an action space. Both are finite types. SSS is nonempty and has decidable equality. AAA is not assumed nonempty. Let MMM 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 M
  • stationary
  • policyMatrix
  • recurrentCount
  • NDiscountOptimal
  • BlackwellOptimal

An auditor needs their definitions to judge what the statement means.

Fix the following:

  • a decision rule d∗d^*d∗ for MMM;
  • the stationary policy (d∗)∞(d^*)^\infty(d∗)∞ built from it, written stationary dstar;
  • a natural number rrr.

The statement has two hypotheses:

  1. (Optimality at one index.) (d∗)∞(d^*)^\infty(d∗)∞ is nnn-discount optimal, in the sense of NDiscountOptimal, for the single integer index
n0  =  ∣S∣−r−1,n_0 \;=\; |S| - r - 1,n0​=∣S∣−r−1,

where ∣S∣|S|∣S∣ is the number of states. This is computed in Z\mathbb{Z}Z, not in N\mathbb{N}N, so it is a true difference and can be negative. 2. (Recurrent count.) Let Pd∗P_{d^*}Pd∗​ be the matrix policyMatrix dstar. The quantity recurrentCount of Pd∗P_{d^*}Pd∗​ equals rrr.

Because of hypothesis 2, rrr is not a free parameter: it is fixed by d∗d^*d∗. Together, the hypotheses say exactly that (d∗)∞(d^*)^\infty(d∗)∞ is (∣S∣−recurrentCount(Pd∗)−1)\big(|S| - \mathrm{recurrentCount}(P_{d^*}) - 1\big)(∣S∣−recurrentCount(Pd∗​)−1)-discount optimal.

The conclusion is a conjunction of two claims:

  1. (d∗)∞(d^*)^\infty(d∗)∞ is Blackwell optimal, in the sense of BlackwellOptimal.
  2. For every integer n≥−1n \ge -1n≥−1, (d∗)∞(d^*)^\infty(d∗)∞ is nnn-discount optimal:
∀n∈Z,  n≥−1  ⟹  (d∗)∞ is n-discount optimal.\forall n \in \mathbb{Z},\; n \ge -1 \implies (d^*)^\infty \text{ is } n\text{-discount optimal}.∀n∈Z,n≥−1⟹(d∗)∞ is n-discount optimal.

This second claim covers infinitely many indices: −1,0,1,2,…-1, 0, 1, 2, \dots−1,0,1,2,…, including every index above n0n_0n0​.

Degenerate cases.

  • One state (∣S∣=1|S| = 1∣S∣=1). The index is n0=−rn_0 = -rn0​=−r. It equals 000 if r=0r = 0r=0, −1-1−1 if r=1r = 1r=1, and is below −1-1−1 if r≥2r \ge 2r≥2.
  • Large recurrent count. In general, if recurrentCount(Pd∗)≥∣S∣\mathrm{recurrentCount}(P_{d^*}) \ge |S|recurrentCount(Pd∗​)≥∣S∣, then n0≤−1n_0 \le -1n0​≤−1. If it is ≥∣S∣+1\ge |S| + 1≥∣S∣+1, then n0<−1n_0 < -1n0​<−1, 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 what NDiscountOptimal means at indices below −1-1−1, 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 recurrentCount(Pd∗)=0\mathrm{recurrentCount}(P_{d^*}) = 0recurrentCount(Pd∗​)=0, then n0=∣S∣−1n_0 = |S| - 1n0​=∣S∣−1.
  • Empty action type. AAA may be empty. If that makes DecisionRule M uninhabited, 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 n0n_0n0​. Any such junk-value behaviour would sit inside the imported definitions and cannot be judged from this code.
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