Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 4.4.2 — deterministic Markov policies suffice

Proved
PutermanMDP.FiniteHorizon.markov_suffices

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

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

Let utu_tut​ solve the history optimality equations and terminal condition in a bounded-reward discrete finite-horizon model. Three conclusions hold.

  1. For each 0≤t≤H0\le t\le H0≤t≤H, ut(ht)u_t(h_t)ut​(ht​) depends on the history only through its last state: histories of equal length with the same current state have equal values.
  2. For every ε>0\varepsilon>0ε>0, there is one deterministic Markov policy ddd satisfying
v∗(s)<vd(s)+εfor every initial state s.v^*(s)<v^d(s)+\varepsilon\qquad\text{for every initial state }s.v∗(s)<vd(s)+εfor every initial state s.
  1. If a maximizing action exists in the one-step optimality expression at every nonterminal history, a deterministic Markov policy is optimal among all history-dependent randomized policies.

This distinguishes approximate optimality, which needs no maximizer, from exact optimality under attainment.

Formalization Note H=N−1H=N-1H=N−1. In the attainment premise, histories index the expression in (4.4.1); the first conclusion makes this equivalent to attainment at each state and epoch. The policy is a single time-dependent state rule, chosen simultaneously for all initial states.

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

theorem markov_suffices {S A : Type} [Countable S] [Nonempty S]
    (M : Model S A) (u : History S A → ℝ) (hu : BellmanSolution M u) :
    (∀ h g : History S A, h.time ≤ M.horizon → h.time = g.time →
      h.state = g.state → u h = u g) ∧
    (∀ ε : ℝ, 0 < ε → ∃ d : MarkovPolicy M, IsEpsilonOptimal M ε d.randomized) ∧
    ((∀ h : History S A, h.time < M.horizon →
        ∃ a, historyScore M u h a = u h) →
      ∃ d : MarkovPolicy M, IsOptimal M d.randomized) := 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. 89 (PDF 105), Theorem 4.4.2; Eq. (4.4.1); 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 policy π\piπ is randomized and history-dependent: it gives a probability mass function on A(s(h))A(s(h))A(s(h)) for each history. 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π(s)=∫z dLNπ(h0(s))V^\pi(s) = \int z \, d\mathcal{L}^\pi_N(h_0(s))Vπ(s)=∫zdLNπ​(h0​(s)), with the integral set to 000 if not integrable;
  • 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.

A deterministic Markov rule ddd chooses d(t,s)∈A(s)d(t,s) \in A(s)d(t,s)∈A(s) for each time t∈Nt \in \mathbb{N}t∈N and state sss. Write πd\pi_dπd​ for the policy that puts probability 111 on d(∣h∣,s(h))d(|h|, s(h))d(∣h∣,s(h)) at each history hhh.

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.

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 of {Qu(h,a):a∈A(s(h))}\{Q_u(h,a) : a \in A(s(h))\}{Qu​(h,a):a∈A(s(h))}, not necessarily attained.

Conclusion. All three of the following hold:

  1. Dependence on time and state only. For any two histories h,g′h, g'h,g′ with ∣h∣≤N|h| \le N∣h∣≤N, ∣h∣=∣g′∣|h| = |g'|∣h∣=∣g′∣ and s(h)=s(g′)s(h) = s(g')s(h)=s(g′), we have u(h)=u(g′)u(h) = u(g')u(h)=u(g′).
  2. ε-optimal Markov rules. For every real ε>0\varepsilon > 0ε>0 there is a deterministic Markov rule ddd such that, for every state sss simultaneously,
V∗(s)<Vπd(s)+ε.V^*(s) < V^{\pi_d}(s) + \varepsilon.V∗(s)<Vπd​(s)+ε.

The inequality is strict. 3. Optimal Markov rule under attainment. Suppose that for every history with ∣h∣<N|h| < N∣h∣<N (including unreachable ones) some available action aaa satisfies Qu(h,a)=u(h)Q_u(h,a) = u(h)Qu​(h,a)=u(h). Then there is a deterministic Markov rule ddd such that, for every state sss and every randomized history-dependent policy ρ\rhoρ, Vρ(s)≤Vπd(s)V^\rho(s) \le V^{\pi_d}(s)Vρ(s)≤Vπd​(s).

Degenerate cases. If N=0N = 0N=0:

  • Part 1 compares only histories with empty lists and the same current state, which are identical, so it holds trivially.
  • In part 2, every policy's value is the expectation of the point mass at g(s)g(s)g(s), so every Markov rule satisfies the strict ε-inequality.
  • In part 3, the attainment premise is vacuous, so the conclusion is asserted unconditionally.

Part 1 says nothing about histories with ∣h∣>N|h| > N∣h∣>N. Part 2 compares against the real supremum V∗(s)V^*(s)V∗(s), which would be the default 000 if the policy values were unbounded above.

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