Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 4.3.3 — maximizing selectors yield optimal policies

Proved
PutermanMDP.FiniteHorizon.maximizing_selectors

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

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

Suppose utu_tut​ solves the maximum form of the history optimality equations (4.3.4), with terminal boundary condition (4.3.3). Let ddd be a deterministic history-dependent policy whose chosen action attains that maximum at every nonterminal history:

rt(st,dt(ht))+∑jpt(j∣st,dt(ht))ut+1(ht,dt(ht),j)=ut(ht).r_t(s_t,d_t(h_t))+\sum_jp_t(j\mid s_t,d_t(h_t))u_{t+1}(h_t,d_t(h_t),j)=u_t(h_t).rt​(st​,dt​(ht​))+j∑​pt​(j∣st​,dt​(ht​))ut+1​(ht​,dt​(ht​),j)=ut​(ht​).

Then, at every history and epoch 0≤t≤H0\le t\le H0≤t≤H,

utd(ht)=ut(ht).u_t^d(h_t)=u_t(h_t).utd​(ht​)=ut​(ht​).

Furthermore, ddd is optimal among all history-dependent randomized policies, and vd(s)=v∗(s)v^d(s)=v^*(s)vd(s)=v∗(s) for every initial state sss. The result verifies a supplied maximizing policy and identifies its continuation values.

Formalization Note H=N−1H=N-1H=N−1. Deterministic actions are embedded in randomized policies using point masses. Maximum attainment is retained explicitly in the equation predicate.

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

theorem maximizing_selectors {S A : Type} [Countable S] [Nonempty S]
    (M : Model S A) (u : History S A → ℝ) (hu : MaxBellmanSolution M u)
    (d : HistoryPolicy M)
    (hd : ∀ h, h.time < M.horizon → historyScore M u h (d h) = u h) :
    (∀ h : History S A, h.time ≤ M.horizon →
      continuationValue M d.randomized h = u h) ∧
    IsOptimal M d.randomized ∧
    (∀ s, totalValue M d.randomized 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. 86 (PDF 102), Theorem 4.3.3, Eqs. (4.3.10)–(4.3.12); 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 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);
  • 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 an unconstrained finite list of state–action pairs 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) and moves to jjj. The initial history h0(s)h_0(s)h0​(s) has an empty list.

A (randomized, history-dependent) policy π\piπ gives a probability mass function on A(s(h))A(s(h))A(s(h)) for each hhh. The reward law Lkπ(h)\mathcal{L}^\pi_k(h)Lkπ​(h) is defined recursively:

  • L0π(h)=δg(s(h))\mathcal{L}^\pi_0(h) = \delta_{g(s(h))}L0π​(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), j∼p∣h∣(⋅∣s(h),a)j \sim p_{|h|}(\cdot \mid s(h),a)j∼p∣h∣​(⋅∣s(h),a) and Z∼Lkπ(h⊕(a,j))Z \sim \mathcal{L}^\pi_k(h \oplus (a,j))Z∼Lkπ​(h⊕(a,j)).

The values are:

  • vπ(h)=∫z dLN−˙∣h∣π(h)v^\pi(h) = \int z \, d\mathcal{L}^\pi_{N \dot- |h|}(h)vπ(h)=∫zdLN−˙​∣h∣π​(h), with −˙\dot-−˙​ truncated subtraction and the integral set to 000 if not integrable;
  • Vπ(s)=vπ(h0(s))V^\pi(s) = v^\pi(h_0(s))Vπ(s)=vπ(h0​(s));
  • V∗(s)=sup⁡πVπ(s)V^*(s) = \sup_\pi V^\pi(s)V∗(s)=supπ​Vπ(s), the real supremum over all policies, with default 000 if unbounded above.

For real uuu on histories and available aaa, the score is

Qu(h,a)=r∣h∣(s(h),a)+∑jp∣h∣(j∣s(h),a) u(h⊕(a,j)),Q_u(h,a) = r_{|h|}(s(h),a) + \sum_j p_{|h|}(j \mid s(h),a)\, u\big(h \oplus (a,j)\big),Qu​(h,a)=r∣h∣​(s(h),a)+j∑​p∣h∣​(j∣s(h),a)u(h⊕(a,j)),

where a non-summable sum counts as 000.

Hypotheses.

  • u(h)=g(s(h))u(h) = g(s(h))u(h)=g(s(h)) for every history with ∣h∣=N|h| = N∣h∣=N.
  • For every history with ∣h∣<N|h| < N∣h∣<N, u(h)u(h)u(h) is the greatest element of {Qu(h,a):a∈A(s(h))}\{Q_u(h,a) : a \in A(s(h))\}{Qu​(h,a):a∈A(s(h))}. That is, it is attained by some available action and is ≥\ge≥ every score.
  • ddd is a deterministic history-dependent rule, choosing d(h)∈A(s(h))d(h) \in A(s(h))d(h)∈A(s(h)) for every history hhh.
  • For every history with ∣h∣<N|h| < N∣h∣<N, including unreachable ones, Qu(h,d(h))=u(h)Q_u(h, d(h)) = u(h)Qu​(h,d(h))=u(h).

Write πd\pi_dπd​ for the policy that puts probability 111 on d(h)d(h)d(h) at each hhh.

Conclusion. All three of the following hold:

  1. vπd(h)=u(h)v^{\pi_d}(h) = u(h)vπd​(h)=u(h) for every history with ∣h∣≤N|h| \le N∣h∣≤N.
  2. πd\pi_dπd​ is optimal: for every state sss and every policy ρ\rhoρ (randomized, history-dependent), Vρ(s)≤Vπd(s)V^\rho(s) \le V^{\pi_d}(s)Vρ(s)≤Vπd​(s).
  3. Vπd(s)=V∗(s)V^{\pi_d}(s) = V^*(s)Vπd​(s)=V∗(s) for every state sss.

Degenerate cases. If N=0N = 0N=0, the second and fourth hypotheses are vacuous, so every deterministic rule ddd qualifies. The conclusions then state the following:

  • u=g(s(h))u = g(s(h))u=g(s(h)) at histories with an empty list.
  • Every policy's total value is the same expectation of the point mass at g(s)g(s)g(s), so πd\pi_dπd​ is optimal.
  • That common value equals the real supremum.

Nothing is asserted about vπdv^{\pi_d}vπd​ or uuu at histories with ∣h∣>N|h| > N∣h∣>N.

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