Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proposition 10.3.5 — finite coefficient determination

Disproved
PutermanMDP.Sensitive.finite_coefficient_determination

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

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

Let δ,d\delta,dδ,d be deterministic decision rules in a finite Markov decision process. Suppose PdP_dPd​ has rrr recurrent classes and their Laurent coefficient vectors agree through the indicated order:

ykδ∞=ykd∞(−1≤k≤∣S∣−r−1).y_k^{\delta^\infty}=y_k^{d^\infty}\qquad(-1\le k\le |S|-r-1).ykδ∞​=ykd∞​(−1≤k≤∣S∣−r−1).

The printed proposition concludes

ykδ∞=ykd∞for every integer k≥−1.y_k^{\delta^\infty}=y_k^{d^\infty}\qquad\text{for every integer }k\ge-1.ykδ∞​=ykd∞​for every integer k≥−1.

This is the chapter's finite-determination claim. FINDINGS records a counterexample at r=∣S∣r=|S|r=∣S∣; the statement is preserved rather than silently adding a hypothesis.

Formalization Note The threshold uses integer subtraction and is −1-1−1 when r=∣S∣r=|S|r=∣S∣. There is no assumption that PδP_\deltaPδ​ also has rrr recurrent classes.

Preamble
import Mathlib
import Definitions.Def_PutermanMDP_Sensitive_Coefficients
Formal statement
namespace PutermanMDP.Sensitive

/-- Printed Proposition 10.3.5. The coefficient interval is closed at both ends:
when r = |S| it consists of the single index -1; when r = |S|-1 it is {-1, 0}.
The r=|S| boundary is disputed in FINDINGS. -/
theorem finite_coefficient_determination {S A : Type} [Fintype S] [DecidableEq S] [Nonempty S] [Fintype A]
    (M : Model S A) (δ d : DecisionRule M) (r : ℕ)
    (hr : recurrentCount (policyMatrix d) = r)
    (heq : ∀ k ∈ Set.Icc (-1 : ℤ) ((Fintype.card S : ℤ) - (r : ℤ) - 1),
      coefficient δ k = coefficient d k) :
    ∀ k : ℤ, -1 ≤ k → coefficient δ k = coefficient d k := by sorry

end PutermanMDP.Sensitive
Source
Puterman, Markov Decision Processes, Wiley, 1994, p. 518 (PDF 534), Proposition 10.3.5; https://doi.org/10.1002/9780470316887
Read-back

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

Setting. Let SSS and AAA be types. SSS is finite, has decidable equality and is nonempty. AAA is finite and may be empty. The statement takes the following data:

  • MMM, a value of type Model S A;
  • δ\deltaδ and ddd, two values of type DecisionRule M;
  • r∈Nr \in \mathbb{N}r∈N, a natural number.

Model, DecisionRule, policyMatrix, recurrentCount and coefficient come from the imported file Definitions.Def_PutermanMDP_Sensitive_Coefficients. Their definitions are not part of this declaration, so this read-back cannot expand them. Read from their types alone:

  • PdP_dPd​ (policyMatrix d) is some matrix-like object built from the decision rule ddd.
  • rc(Pd)\mathrm{rc}(P_d)rc(Pd​) (recurrentCount) is a natural number computed from PdP_dPd​.
  • cδ(k)c_\delta(k)cδ​(k) (coefficient δ k) is a value attached to the decision rule δ\deltaδ and an integer index k∈Zk \in \mathbb{Z}k∈Z. The type of that value is not visible here. The code does not pass MMM to coefficient explicitly; any dependence on MMM comes through the type of δ\deltaδ.

Hypotheses.

  1. rc(Pd)=r\mathrm{rc}(P_d) = rrc(Pd​)=r. Only ddd's count is constrained. The statement makes no assumption about rc(Pδ)\mathrm{rc}(P_\delta)rc(Pδ​).
  2. For every integer kkk in the closed integer interval below, the coefficients agree: cδ(k)=cd(k)c_\delta(k) = c_d(k)cδ​(k)=cd​(k). The bound is computed in Z\mathbb{Z}Z, so there is no truncation at zero.
−1≤k≤∣S∣−r−1-1 \le k \le |S| - r - 1−1≤k≤∣S∣−r−1

Here ∣S∣|S|∣S∣ is the number of elements of SSS.

Conclusion. For every integer k≥−1k \ge -1k≥−1,

cδ(k)=cd(k).c_\delta(k) = c_d(k).cδ​(k)=cd​(k).

The coefficients at indices up to ∣S∣−r−1|S| - r - 1∣S∣−r−1 are assumed to agree. The conclusion then says they agree at every index k≥−1k \ge -1k≥−1. Indices k<−1k < -1k<−1 appear in neither the hypotheses nor the conclusion. The comment attached to the code describes the cases r=∣S∣r = |S|r=∣S∣ and r=∣S∣−1r = |S| - 1r=∣S∣−1 and says the r=∣S∣r = |S|r=∣S∣ case is disputed elsewhere. That comment is not part of what the statement asserts.

Degenerate cases.

  • r=∣S∣r = |S|r=∣S∣. The interval is {−1}\{-1\}{−1}. Agreement at the single index −1-1−1 is then claimed to force agreement at every k≥−1k \ge -1k≥−1.
  • r=∣S∣−1r = |S| - 1r=∣S∣−1. The interval is {−1,0}\{-1, 0\}{−1,0}.
  • r=0r = 0r=0. The interval is {−1,…,∣S∣−1}\{-1, \dots, |S| - 1\}{−1,…,∣S∣−1}.
  • r≥∣S∣+1r \ge |S| + 1r≥∣S∣+1. The upper end ∣S∣−r−1|S| - r - 1∣S∣−r−1 is at most −2-2−2, so the interval is empty and the second hypothesis holds automatically. The statement would then assert that cδ(k)=cd(k)c_\delta(k) = c_d(k)cδ​(k)=cd​(k) for all k≥−1k \ge -1k≥−1, for any δ\deltaδ and any ddd with rc(Pd)=r\mathrm{rc}(P_d) = rrc(Pd​)=r. Whether rc\mathrm{rc}rc can actually exceed ∣S∣|S|∣S∣ depends on the imported definition, which is not visible here.
  • One-element SSS (∣S∣=1|S| = 1∣S∣=1). The interval is {−1,…,−r}\{-1, \dots, -r\}{−1,…,−r}. That is {−1}\{-1\}{−1} when r=1r = 1r=1, {−1,0}\{-1, 0\}{−1,0} when r=0r = 0r=0, and empty when r≥2r \ge 2r≥2.
  • Empty AAA. Whether DecisionRule M has any inhabitants then depends on the imported definitions. If it has none, the statement is vacuous.
  • Undefined arithmetic. Nothing in the statement itself divides, subtracts in N\mathbb{N}N, takes a supremum or integrates. Any default values arising inside coefficient, policyMatrix or recurrentCount are hidden in the imported definitions.
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