Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 4.3.2 — optimality equations characterize the value

Proved
PutermanMDP.FiniteHorizon.optimality_equations

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

dynamic-programmingfinite-horizonmdpp2o-gran-per-chapterp2o-plan-bookp2o-v1

In a finite-horizon discrete model with bounded rewards, suppose the real functions utu_tut​ satisfy the history optimality equations (4.3.2) and terminal condition (4.3.3). Then for every history and every epoch,

ut(ht)=sup⁡π∈ΠHRutπ(ht),0≤t≤H,u_t(h_t)=\sup_{\pi\in\Pi^{HR}}u_t^\pi(h_t),\qquad 0\le t\le H,ut​(ht​)=π∈ΠHRsup​utπ​(ht​),0≤t≤H,

and at the initial epoch,

u0(s)=sup⁡π∈ΠHRvπ(s)=v∗(s).u_0(s)=\sup_{\pi\in\Pi^{HR}}v^\pi(s)=v^*(s).u0​(s)=π∈ΠHRsup​vπ(s)=v∗(s).

Thus the Bellman equations characterize the value against all admissible history-dependent randomized policies, whether or not a maximizing action exists.

Formalization Note H=N−1H=N-1H=N−1. Genuine real suprema are represented by least-upper-bound predicates in the hypotheses; attainment is not assumed.

Preamble
import Mathlib
import Definitions.Def_PutermanMDP_FiniteHorizon_BellmanSolution
Formal statement
namespace PutermanMDP.FiniteHorizon

theorem optimality_equations {S A : Type} [Countable S] [Nonempty S]
    (M : Model S A) (u : History S A → ℝ) (hu : BellmanSolution M u) :
    (∀ h : History S A, h.time ≤ M.horizon → u h = optimalContinuation M h) ∧
    (∀ s, u (History.initial s) = optimalTotal M s) := by sorry

end PutermanMDP.FiniteHorizon

/- Imported definition source snapshots for a self-contained offline audit.

import Mathlib

namespace PutermanMDP.FiniteHorizon

/-- A history consists of past state-action pairs in chronological order and the current state.
Its list length is the zero-based current epoch. No positive-probability restriction is imposed. -/
structure History (S A : Type) where
  past : List (S × A)
  state : S

def History.time {S A : Type} (h : History S A) : ℕ := h.past.length

def History.initial {S A : Type} (s : S) : History S A := ⟨[], s⟩

def History.extend {S A : Type} (h : History S A) (a : A) (j : S) : History S A :=
  ⟨h.past ++ [(h.state, a)], j⟩

/-- `horizon` counts decisions. The terminal epoch is `horizon`, corresponding to epoch
`N = horizon + 1` under one-based indexing. Rewards may have either sign. -/
structure Model (S A : Type) [Countable S] where
  horizon : ℕ
  available : S → Set A
  available_nonempty : ∀ s, (available s).Nonempty
  transition : ℕ → (s : S) → {a // a ∈ available s} → PMF S
  reward : ℕ → (s : S) → {a // a ∈ available s} → ℝ
  terminal : S → ℝ
  bounded : ∃ C : ℝ, 0 ≤ C ∧
    (∀ t, t < horizon → ∀ s a, |reward t s a| ≤ C) ∧
    (∀ s, |terminal s| ≤ C)

/-- All history-dependent randomized decision rules, extended harmlessly beyond the horizon. -/
def Policy {S A : Type} [Countable S] (M : Model S A) : Type :=
  (h : History S A) → PMF {a // a ∈ M.available h.state}

def HistoryPolicy {S A : Type} [Countable S] (M : Model S A) : Type :=
  (h : History S A) → {a // a ∈ M.available h.state}

def MarkovPolicy {S A : Type} [Countable S] (M : Model S A) : Type :=
  ℕ → (s : S) → {a // a ∈ M.available s}

noncomputable def HistoryPolicy.randomized {S A : Type} [Countable S] {M : Model S A}
    (d : HistoryPolicy M) : Policy M := fun h => PMF.pure (d h)

noncomputable def MarkovPolicy.randomized {S A : Type} [Countable S] {M : Model S A}
    (d : MarkovPolicy M) : Policy M := fun h => PMF.pure (d h.time h.state)

end PutermanMDP.FiniteHorizon

import Mathlib
import Definitions.Def_PutermanMDP_FiniteHorizon_Model

namespace PutermanMDP.FiniteHorizon

/-- The probability law of the sum of the next `k` decision rewards and the terminal reward.
At each decision, sample the policy's action, then the transition's state. The recursion
pushes forward the future reward law by adding the immediate reward; it does not evaluate
expectations or optimize policies. -/
noncomputable def rewardLaw {S A : Type} [Countable S] (M : Model S A) (π : Policy M) :
    ℕ → History S A → PMF ℝ
  | 0, h => PMF.pure (M.terminal h.state)
  | k + 1, h => (π h).bind fun a =>
      (M.transition h.time h.state a).bind fun j =>
        (rewardLaw M π k (h.extend a.val j)).map
          (fun z => M.reward h.time h.state a + z)

/-- The expectation of the actual remaining reward law. It is used only for `h.time ≤ horizon`.
The bounded reward assumption then implies integrability and a uniform bound over policies. -/
noncomputable def continuationValue {S A : Type} [Countable S]
    (M : Model S A) (π : Policy M) (h : History S A) : ℝ :=
  ∫ z : ℝ, z ∂(rewardLaw M π (M.horizon - h.time) h).toMeasure

noncomputable def totalValue {S A : Type} [Countable S]
    (M : Model S A) (π : Policy M) (s : S) : ℝ :=
  continuationValue M π (History.initial s)

/-- The supremum is over all history-dependent randomized policies, not merely Markov rules.
Nonempty action fibers give policies, and bounded finite-horizon rewards bound this range. -/
noncomputable def optimalContinuation {S A : Type} [Countable S]
    (M : Model S A) (h : History S A) : ℝ :=
  ⨆ π : Policy M, continuationValue M π h

noncomputable def optimalTotal {S A : Type} [Countable S] (M : Model S A) (s : S) : ℝ :=
  ⨆ π : Policy M, totalValue M π s

def IsOptimal {S A : Type} [Countable S] (M : Model S A) (π : Policy M) : Prop :=
  ∀ s, ∀ ρ : Policy M, totalValue M ρ s ≤ totalValue M π s

/-- Strict epsilon optimality, simultaneously for every initial state. -/
def IsEpsilonOptimal {S A : Type} [Countable S] (M : Model S A)
    (ε : ℝ) (π : Policy M) : Prop :=
  ∀ s, optimalTotal M s < totalValue M π s + ε

/-- The separate randomized policy evaluation algorithm: terminal initialization followed
by the action-averaged one-step recurrence, repeated exactly `k` times. -/
noncomputable def evaluate {S A : Type} [Countable S] (M : Model S A) (π : Policy M) :
    ℕ → History S A → ℝ
  | 0, h => M.terminal h.state
  | k + 1, h => ∑' a, (π h a).toReal *
      (M.reward h.time h.state a +
        ∑' j, (M.transition h.time h.state a j).toReal *
          evaluate M π k (h.extend a.val j))

end PutermanMDP.FiniteHorizon

import Mathlib
import Definitions.Def_PutermanMDP_FiniteHorizon_continuationValue

namespace PutermanMDP.FiniteHorizon

/-- The model parameter in every definition in this module includes the common bound
`∃ C ≥ 0, (∀ t < M.horizon, ∀ s a, |M.reward t s a| ≤ C) ∧
(∀ s, |M.terminal s| ≤ C)` through `Model.bounded`. In particular these predicates
are defined on bounded-reward models, not on arbitrary unbounded transition-reward data.
This score is the immediate reward plus the next-state weighted continuation. -/
noncomputable def historyScore {S A : Type} [Countable S] (M : Model S A)
    (u : History S A → ℝ) (h : History S A) (a : {a // a ∈ M.available h.state}) : ℝ :=
  M.reward h.time h.state a +
    ∑' j, (M.transition h.time h.state a j).toReal * u (h.extend a.val j)

/-- A real solution of the history optimality equations with terminal boundary data.
`IsLUB` means a genuine finite supremum, avoiding the default value of an unbounded real sup. -/
def BellmanSolution {S A : Type} [Countable S] (M : Model S A)
    (u : History S A → ℝ) : Prop :=
  (∀ h, h.time = M.horizon → u h = M.terminal h.state) ∧
  (∀ h, h.time < M.horizon → IsLUB (Set.range (historyScore M u h)) (u h))

/-- The maximum form of the same equations, including attainment at every history. -/
def MaxBellmanSolution {S A : Type} [Countable S] (M : Model S A)
    (u : History S A → ℝ) : Prop :=
  (∀ h, h.time = M.horizon → u h = M.terminal h.state) ∧
  (∀ h, h.time < M.horizon → IsGreatest (Set.range (historyScore M u h)) (u h))

noncomputable def stateScore {S A : Type} [Countable S] (M : Model S A)
    (u : ℕ → S → ℝ) (t : ℕ) (s : S) (a : {a // a ∈ M.available s}) : ℝ :=
  M.reward t s a + ∑' j, (M.transition t s a j).toReal * u (t + 1) j

/-- The backward induction algorithm as its exact output recurrence: terminal initialization
and an attained maximum at every preceding epoch and state. No value or optimality condition
is included in this predicate. -/
def BackwardSolution {S A : Type} [Countable S] (M : Model S A)
    (u : ℕ → S → ℝ) : Prop :=
  (∀ s, u M.horizon s = M.terminal s) ∧
  (∀ t, t < M.horizon → ∀ s, IsGreatest (Set.range (stateScore M u t s)) (u t s))

/-- All maximizing actions, constructed directly from the one-step expression. -/
def maximizingActions {S A : Type} [Countable S] (M : Model S A)
    (u : ℕ → S → ℝ) (t : ℕ) (s : S) : Set {a // a ∈ M.available s} :=
  {a | ∀ b, stateScore M u t s b ≤ stateScore M u t s a}

end PutermanMDP.FiniteHorizon
-/
Source
Puterman, Markov Decision Processes, Wiley, 1994, p. 84 (PDF 100), Theorem 4.3.2; https://doi.org/10.1002/9780470316887.ch4
Read-back

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

Setting. SSS is a countable, nonempty type of states and AAA is a type of actions. The model MMM consists of the following data:

  • a horizon N∈NN \in \mathbb{N}N∈N;
  • nonempty available-action sets A(s)A(s)A(s);
  • for every time t∈Nt \in \mathbb{N}t∈N, transition probability mass functions pt(⋅∣s,a)p_t(\cdot \mid s,a)pt​(⋅∣s,a) and real rewards rt(s,a)r_t(s,a)rt​(s,a), for a∈A(s)a \in A(s)a∈A(s);
  • a terminal reward ggg.

There is a C≥0C \ge 0C≥0 such that ∣rt(s,a)∣≤C|r_t(s,a)| \le C∣rt​(s,a)∣≤C for t<Nt < Nt<N and ∣g(s)∣≤C|g(s)| \le C∣g(s)∣≤C.

A history hhh is a finite list of state–action pairs (with no consistency requirement) together with a current state s(h)s(h)s(h). Its time ∣h∣|h|∣h∣ is the list length. The extension h⊕(a,j)h \oplus (a,j)h⊕(a,j) appends (s(h),a)(s(h),a)(s(h),a) to the list and moves to state jjj. The initial history h0(s)h_0(s)h0​(s) has an empty list and current state sss.

A policy π\piπ assigns to every history hhh a probability mass function π(⋅∣h)\pi(\cdot \mid h)π(⋅∣h) on A(s(h))A(s(h))A(s(h)). Policies may therefore be randomized and depend on the whole history.

Reward law and values. The reward law Lkπ(h)\mathcal{L}^\pi_k(h)Lkπ​(h) is a distribution on R\mathbb{R}R, defined recursively:

  • L0π(h)\mathcal{L}^\pi_0(h)L0π​(h) is the point mass at g(s(h))g(s(h))g(s(h)).
  • Lk+1π(h)\mathcal{L}^\pi_{k+1}(h)Lk+1π​(h) is the law of r∣h∣(s(h),a)+Zr_{|h|}(s(h),a) + Zr∣h∣​(s(h),a)+Z, where a∼π(⋅∣h)a \sim \pi(\cdot \mid h)a∼π(⋅∣h), then j∼p∣h∣(⋅∣s(h),a)j \sim p_{|h|}(\cdot \mid s(h),a)j∼p∣h∣​(⋅∣s(h),a), then Z∼Lkπ(h⊕(a,j))Z \sim \mathcal{L}^\pi_k(h \oplus (a,j))Z∼Lkπ​(h⊕(a,j)).

The continuation value is

vπ(h)=∫z dLN−˙∣h∣π(h)(z),v^\pi(h) = \int z \, d\mathcal{L}^\pi_{N \dot- |h|}(h)(z),vπ(h)=∫zdLN−˙​∣h∣π​(h)(z),

where −˙\dot-−˙​ is truncated subtraction and the integral is set to 000 if zzz is not integrable. The optimal continuation is

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

taken in R\mathbb{R}R over all policies. This supremum takes the default value 000 if the set of values is unbounded above. The optimal total is V∗(s)=sup⁡πvπ(h0(s))V^*(s) = \sup_\pi v^\pi(h_0(s))V∗(s)=supπ​vπ(h0​(s)), with the same convention.

Hypothesis. uuu is a real function on histories satisfying both of the following:

  • u(h)=g(s(h))u(h) = g(s(h))u(h)=g(s(h)) whenever ∣h∣=N|h| = N∣h∣=N.
  • Whenever ∣h∣<N|h| < N∣h∣<N, u(h)u(h)u(h) is the least upper bound in R\mathbb{R}R (not necessarily attained) of the set
{ r∣h∣(s(h),a)+∑jp∣h∣(j∣s(h),a) u(h⊕(a,j))  :  a∈A(s(h))}.\Big\{\, r_{|h|}(s(h),a) + \sum_j p_{|h|}(j \mid s(h),a)\, u\big(h \oplus (a,j)\big) \;:\; a \in A(s(h)) \Big\}.{r∣h∣​(s(h),a)+j∑​p∣h∣​(j∣s(h),a)u(h⊕(a,j)):a∈A(s(h))}.

Here a non-summable sum counts as 000.

Conclusion. Both of the following hold:

  1. For every history hhh with ∣h∣≤N|h| \le N∣h∣≤N (including histories the model cannot reach):
u(h)=sup⁡πvπ(h).u(h) = \sup_\pi v^\pi(h).u(h)=πsup​vπ(h).
  1. For every state sss:
u(h0(s))=sup⁡πvπ(h0(s)).u(h_0(s)) = \sup_\pi v^\pi(h_0(s)).u(h0​(s))=πsup​vπ(h0​(s)).

The second conjunct is literally the first conjunct at h=h0(s)h = h_0(s)h=h0​(s), which has time 0≤N0 \le N0≤N.

Degenerate cases. If N=0N = 0N=0, the second hypothesis is vacuous. The only histories with ∣h∣≤0|h| \le 0∣h∣≤0 have an empty list, and the conclusion states that u(h)=g(s(h))u(h) = g(s(h))u(h)=g(s(h)) equals the supremum over policies of the expectation of the point mass at g(s(h))g(s(h))g(s(h)). The statement says nothing about histories with ∣h∣>N|h| > N∣h∣>N. Both conclusions are equalities with the real supremum. If the set of policy values were unbounded above, that supremum would be the default 000.

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