Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 7.2.2 — Nonnegative supersolutions bound the value

Proved
PutermanMDP.TotalReward.supersolution_bound

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

dynamic-programmingmdpp2o-gran-per-chapterp2o-plan-bookp2o-v1total-reward

Consider a positive bounded model on nonempty countable state and action spaces: every policy has finite expected accumulated positive reward at each initial state, and a nonnegative-reward action is available in every state. Let v:S→Rv:S\to\mathbb Rv:S→R be pointwise finite and nonnegative. If v≥Lvv\ge\mathcal Lvv≥Lv, then

v(s)≥v∗(s)(s∈S).v(s)\ge v^*(s)\qquad(s\in S).v(s)≥v∗(s)(s∈S).

Thus any nonnegative supersolution bounds the optimum over all admissible history-dependent randomized policies.

Formalization Note The standing assumptions of §7.2 are explicit. Lean embeds the real-valued class V+V^+V+ into extended-real functions by requiring 0≤v(s)<∞0\le v(s)<\infty0≤v(s)<∞. No uniform bound on vvv is imposed, and the Bellman inequality itself excludes an infinite positive Bellman value.

Preamble
import Mathlib
import Definitions.Def_PutermanMDP_TotalReward_Bellman
Formal statement
/-
Dependency source for blind auditing. The following is a verbatim snapshot
of the two imported definition modules; these are comments, not redeclarations.

import Mathlib
open scoped ENNReal

namespace PutermanMDP.TotalReward

/-- The time-homogeneous discrete model of §§2.1 and 7.1. Actions depend on the state.
Countability and nonemptiness are imposed by each theorem, not finiteness. -/
structure Model (S : Type*) (A : S → Type*) where
  reward : (s : S) → A s → ℝ
  transition : (s : S) → A s → PMF S

/-- Observable history: the preceding state/action pairs in chronological order,
followed by the current state. Its list length is the zero-based decision epoch. -/
abbrev History (S : Type*) (A : S → Type*) := List (Sigma A) × S

/-- All admissible history-dependent randomized policies, including decisions on
histories of probability zero. The dependent action type enforces admissibility. -/
abbrev HRPolicy (S : Type*) (A : S → Type*) := (h : History S A) → PMF (A h.2)

/-- Time-dependent randomized Markov policies. -/
abbrev MRPolicy (S : Type*) (A : S → Type*) := ℕ → (s : S) → PMF (A s)

def markovPolicy {S : Type*} {A : S → Type*} (π : MRPolicy S A) : HRPolicy S A :=
  fun h => π h.1.length h.2

/-- The distribution of the observable history at epoch n, constructed from the
actual transition and action distributions; n=0 precedes the first reward. -/
noncomputable def historyLaw {S : Type*} {A : S → Type*}
    (M : Model S A) (π : HRPolicy S A) (s : S) : ℕ → PMF (History S A)
  | 0 => PMF.pure ([], s)
  | n + 1 => (historyLaw M π s n).bind fun h =>
      (π h).bind fun a => (M.transition h.2 a).bind fun t =>
        PMF.pure (h.1 ++ [⟨h.2, a⟩], t)

/-- Expected accumulated nonnegative stage rewards, computed using the finite
history laws. ENNReal sums retain divergence as +∞. The generic payoff g may
itself equal +∞, including at a single state/action; zero probability times
this infinite payoff is zero. The later reward-part definitions specialize g
to finite one-step values, but that is not a restriction of this helper. -/
noncomputable def accumulated {S : Type*} {A : S → Type*}
    (M : Model S A) (π : HRPolicy S A) (s : S)
    (g : (t : S) → A t → ℝ≥0∞) : ℝ≥0∞ :=
  ∑' n : ℕ, ∑' h : History S A, ∑' a : A h.2,
    historyLaw M π s n h * π h a * g h.2 a

noncomputable def positiveReward {S : Type*} {A : S → Type*}
    (M : Model S A) (π : HRPolicy S A) (s : S) : ℝ≥0∞ :=
  accumulated M π s (fun t a => ENNReal.ofReal (M.reward t a))

noncomputable def negativeReward {S : Type*} {A : S → Type*}
    (M : Model S A) (π : HRPolicy S A) (s : S) : ℝ≥0∞ :=
  accumulated M π s (fun t a => ENNReal.ofReal (-M.reward t a))

/-- Assumption 7.1.1: at least one expected reward part is finite, separately
for every history-dependent randomized policy and starting state. -/
def WellDefined {S : Type*} {A : S → Type*} (M : Model S A) : Prop :=
  ∀ (π : HRPolicy S A) (s : S),
    positiveReward M π s < ⊤ ∨ negativeReward M π s < ⊤

/-- Total expected reward, used only under WellDefined or PositiveBounded.
The excluded case +∞−+∞ has EReal's totalized value, not a reward interpretation. -/
noncomputable def policyValue {S : Type*} {A : S → Type*}
    (M : Model S A) (π : HRPolicy S A) (s : S) : EReal :=
  (positiveReward M π s : EReal) - (negativeReward M π s : EReal)

/-- Equation (7.1.3): the supremum over all admissible HR policies, separately
at each initial state. Extended suprema preserve unbounded values. -/
noncomputable def optimalValue {S : Type*} {A : S → Type*}
    (M : Model S A) (s : S) : EReal :=
  ⨆ π : HRPolicy S A, policyValue M π s

/-- Exactly Assumptions 7.2.1 and 7.2.2. No uniform upper bound, optimal
policy, nonnegative reward for every action, or Bellman identity is assumed. -/
def PositiveBounded {S : Type*} {A : S → Type*} (M : Model S A) : Prop :=
  (∀ (π : HRPolicy S A) (s : S), positiveReward M π s < ⊤) ∧
  (∀ s : S, ∃ a : A s, 0 ≤ M.reward s a)

end PutermanMDP.TotalReward

import Mathlib
import Definitions.Def_PutermanMDP_TotalReward_Model
open scoped ENNReal

namespace PutermanMDP.TotalReward

/-- Expectation of an extended value under a discrete probability distribution,
as the difference of nonnegative expectations. Bellman results below apply this
only to nonnegative values, where the negative expectation is zero. -/
noncomputable def transitionValue {S : Type*} (p : PMF S) (v : S → EReal) : EReal :=
  ((∑' t : S, p t * (v t).toENNReal : ℝ≥0∞) : EReal) -
    ((∑' t : S, p t * (-v t).toENNReal : ℝ≥0∞) : EReal)

/-- Component form of the undiscounted optimality operator (7.1.5).
The supremum is over all admissible actions; attainment is not required. -/
noncomputable def bellman {S : Type*} {A : S → Type*}
    (M : Model S A) (v : S → EReal) (s : S) : EReal :=
  ⨆ a : A s, (M.reward s a : EReal) + transitionValue (M.transition s a) v

/-- The pointwise-finite nonnegative class V⁺ on p. 285. It is not the class
of uniformly bounded functions. Bellman is not assumed to preserve this class. -/
def InVPlus {S : Type*} (v : S → EReal) : Prop :=
  ∀ s : S, 0 ≤ v s ∧ v s < ⊤

/-- The actual recurrence in Theorem 7.2.12, with the initial vector exactly zero.
Extended values make this a total definition without defaulting divergent sums to zero. -/
noncomputable def valueIterate {S : Type*} {A : S → Type*}
    (M : Model S A) : ℕ → S → EReal
  | 0 => fun _ => 0
  | n + 1 => bellman M (valueIterate M n)

end PutermanMDP.TotalReward
-/

namespace PutermanMDP.TotalReward

/-- Theorem 7.2.2, under the standing positive-bounded assumptions of §7.2.
Individual policy values may be −∞. The optimal value cannot be −∞ under
these hypotheses: choosing a nonnegative-reward action at every state gives
a policy with nonnegative value. This is not an added hypothesis. -/
theorem supersolution_bound {S : Type*} {A : S → Type*}
    [Countable S] [Nonempty S] [∀ s, Countable (A s)] [∀ s, Nonempty (A s)]
    (M : Model S A) (hM : PositiveBounded M)
    (v : S → EReal) (hv : InVPlus v) (hsuper : bellman M v ≤ v) :
    optimalValue M ≤ v := by sorry

end PutermanMDP.TotalReward
Source
Puterman, Markov Decision Processes, Wiley, 1994, p. 285 (PDF 301), Theorem 7.2.2; standing Assumptions 7.2.1–7.2.2, p. 284
Read-back

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

Setting. Let SSS be a countable, nonempty type of states. For each s∈Ss \in Ss∈S, let AsA_sAs​ be a countable, nonempty type of actions. Let MMM be a model with:

  • real rewards r(s,a)r(s,a)r(s,a);
  • discrete transition distributions p(⋅∣s,a)p(\cdot \mid s,a)p(⋅∣s,a) on SSS.

The following notions from the dependency modules are used.

Histories, policies and their law. A history is a finite list ((s0,a0),…,(sk−1,ak−1))\big((s_0,a_0),\dots,(s_{k-1},a_{k-1})\big)((s0​,a0​),…,(sk−1​,ak−1​)) with each ai∈Asia_i \in A_{s_i}ai​∈Asi​​, together with a current state. A history-dependent randomized policy π\piπ assigns to every history, including impossible ones, a probability distribution on the actions available at its current state.

For an initial state sss, the law Pπ,snP^n_{\pi,s}Pπ,sn​ of the history at epoch nnn is built as follows:

  • Pπ,s0P^0_{\pi,s}Pπ,s0​ is the point mass on (empty list, sss);
  • Pπ,sn+1P^{n+1}_{\pi,s}Pπ,sn+1​ draws h=(ℓ,s′)h = (\ell, s')h=(ℓ,s′) from Pπ,snP^n_{\pi,s}Pπ,sn​, then an action aaa from π(⋅∣h)\pi(\cdot \mid h)π(⋅∣h), then a next state ttt from p(⋅∣s′,a)p(\cdot \mid s',a)p(⋅∣s′,a), and outputs the history (ℓ\ellℓ with (s′,a)(s',a)(s′,a) appended, current state ttt).

Reward parts, policy value and optimal value. With x+=max⁡(x,0)x^+ = \max(x,0)x+=max(x,0), the two reward parts are

Rπ±(s)=∑n=0∞∑h=(ℓ,t)∑a∈AtPπ,sn(h) π(a∣h) (±r(t,a))+∈[0,+∞].R^{\pm}_\pi(s) = \sum_{n=0}^\infty \sum_{h=(\ell,t)} \sum_{a \in A_t} P^n_{\pi,s}(h)\,\pi(a\mid h)\,\big(\pm r(t,a)\big)^+ \in [0,+\infty].Rπ±​(s)=n=0∑∞​h=(ℓ,t)∑​a∈At​∑​Pπ,sn​(h)π(a∣h)(±r(t,a))+∈[0,+∞].

These are undiscounted sums of nonnegative extended reals over infinitely many epochs; a divergent sum equals +∞+\infty+∞.

The policy value is vπ(s)=Rπ+(s)−Rπ−(s)v_\pi(s) = R^+_\pi(s) - R^-_\pi(s)vπ​(s)=Rπ+​(s)−Rπ−​(s) in the extended reals. The optimal value is

v∗(s)=sup⁡πvπ(s),v^*(s) = \sup_\pi v_\pi(s),v∗(s)=πsup​vπ​(s),

the extended-real supremum over all history-dependent randomized policies.

Hypotheses.

  1. Positive-boundedness of MMM.
    • Rπ+(s)<+∞R^+_\pi(s) < +\inftyRπ+​(s)<+∞ for every history-dependent randomized policy π\piπ and every state sss.
    • Every state sss has some action a∈Asa \in A_sa∈As​ with r(s,a)≥0r(s,a) \ge 0r(s,a)≥0.
  2. The function vvv. v:S→[−∞,+∞]v : S \to [-\infty,+\infty]v:S→[−∞,+∞] satisfies 0≤v(s)<+∞0 \le v(s) < +\infty0≤v(s)<+∞ for every sss. So each value v(s)v(s)v(s) is a finite nonnegative real, but vvv need not be bounded uniformly in sss.
  3. Supersolution inequality. For every s∈Ss \in Ss∈S,
sup⁡a∈As(r(s,a)+Es,a[v])≤v(s).\sup_{a \in A_s} \Big( r(s,a) + E_{s,a}[v] \Big) \le v(s).a∈As​sup​(r(s,a)+Es,a​[v])≤v(s).

Here Es,a[v]E_{s,a}[v]Es,a​[v] is defined as a difference of two sums in [0,+∞][0,+\infty][0,+∞]:

Es,a[v]=∑tp(t∣s,a) v(t)+  −  ∑tp(t∣s,a) (−v(t))+.E_{s,a}[v] = \sum_{t} p(t\mid s,a)\, v(t)^+ \;-\; \sum_t p(t \mid s,a)\, (-v(t))^+.Es,a​[v]=t∑​p(t∣s,a)v(t)+−t∑​p(t∣s,a)(−v(t))+.

Because v≥0v \ge 0v≥0, the second sum is 000, so Es,a[v]=∑tp(t∣s,a) v(t)E_{s,a}[v] = \sum_t p(t\mid s,a)\, v(t)Es,a​[v]=∑t​p(t∣s,a)v(t). This value may be +∞+\infty+∞, in which case r(s,a)+Es,a[v]=+∞r(s,a) + E_{s,a}[v] = +\inftyr(s,a)+Es,a​[v]=+∞. The supremum is over all actions and need not be attained.

Conclusion. For every state s∈Ss \in Ss∈S,

v∗(s)=sup⁡π(Rπ+(s)−Rπ−(s))≤v(s).v^*(s) = \sup_\pi \big(R^+_\pi(s) - R^-_\pi(s)\big) \le v(s).v∗(s)=πsup​(Rπ+​(s)−Rπ−​(s))≤v(s).

Degenerate cases.

  • Empty types. The hypotheses rule out an empty SSS and empty action types.
  • One-element SSS. The statement applies without change.
  • Satisfiability. The hypotheses can be met. For example, take all rewards equal to 000 and v≡0v \equiv 0v≡0: then R+=0R^+ = 0R+=0, a nonnegative-reward action exists everywhere, and the supremum in hypothesis 3 is 0≤00 \le 00≤0.
  • Infinite expectations. Since v(s)<+∞v(s) < +\inftyv(s)<+∞, hypothesis 3 forces r(s,a)+Es,a[v]r(s,a) + E_{s,a}[v]r(s,a)+Es,a​[v] to be finite for every action aaa, and in particular Es,a[v]<+∞E_{s,a}[v] < +\inftyEs,a​[v]<+∞.
  • (+∞)−(+∞)(+\infty) - (+\infty)(+∞)−(+∞). The totalized subtraction would give −∞-\infty−∞, but it cannot arise here because hypothesis 1 makes every Rπ+(s)R^+_\pi(s)Rπ+​(s) finite.
  • Individual policy values. A policy value vπ(s)v_\pi(s)vπ​(s) may equal −∞-\infty−∞, namely when Rπ−(s)=+∞R^-_\pi(s) = +\inftyRπ−​(s)=+∞. The conclusion is only an upper bound on the supremum, so such policies are allowed.
  • Upper bound on v∗v^*v∗. The conclusion implies that v∗(s)v^*(s)v∗(s) is never +∞+\infty+∞.
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