Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 4.5.1 — backward induction finds optimal values and policies

Proved
PutermanMDP.FiniteHorizon.backward_induction

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

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

Consider a finite-horizon model with a nonempty finite or countable state space, nonempty admissible action sets, stochastic transition rows, and bounded signed rewards. Suppose UUU is initialized by U(H,s)=g(s)U(H,s)=g(s)U(H,s)=g(s) and satisfies the backward maximum recurrence

U(t,s)=max⁡a∈As{rt(s,a)+∑jpt(j∣s,a)U(t+1,j)},t<H.U(t,s)=\max_{a\in A_s}\left\{r_t(s,a)+\sum_jp_t(j\mid s,a)U(t+1,j)\right\},\qquad t<H.U(t,s)=a∈As​max​{rt​(s,a)+j∑​pt​(j∣s,a)U(t+1,j)},t<H.

Let As,t∗A^*_{s,t}As,t∗​ be the set of all actions attaining this maximum. Then:

  1. At every history hth_tht​ ending in state sts_tst​, including zero-probability histories,
U(t,st)=sup⁡π∈ΠHRutπ(ht),0≤t≤H.U(t,s_t)=\sup_{\pi\in\Pi^{HR}}u_t^\pi(h_t),\qquad 0\le t\le H.U(t,st​)=π∈ΠHRsup​utπ​(ht​),0≤t≤H.
  1. Every deterministic Markov selector dt(s)∈As,t∗d_t(s)\in A^*_{s,t}dt​(s)∈As,t∗​ is optimal against all history-dependent randomized policies and satisfies
vd(s)=sup⁡π∈ΠHRvπ(s),utd(ht)=U(t,st).v^d(s)=\sup_{\pi\in\Pi^{HR}}v^\pi(s),\qquad u_t^d(h_t)=U(t,s_t).vd(s)=π∈ΠHRsup​vπ(s),utd​(ht​)=U(t,st​).

The equalities hold simultaneously for every state and every continuation epoch. The theorem identifies the actual expected reward values computed by backward induction and the policies its maximizing sets describe.

Formalization Note The implementation uses H=N−1H=N-1H=N−1 decisions and zero-based epochs. The terminal condition and the attained-maximum equations specify the algorithm's output; maximizing sets are defined from the one-step expressions rather than supplied independently. No finiteness of the state or action sets, and no restriction of the comparison class to Markov policies, is introduced.

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

theorem backward_induction {S A : Type} [Countable S] [Nonempty S]
    (M : Model S A) (u : ℕ → S → ℝ) (hu : BackwardSolution M u) :
    (∀ h : History S A, h.time ≤ M.horizon →
      u h.time h.state = ⨆ π : Policy M, continuationValue M π h) ∧
    (∀ d : MarkovPolicy M,
      (∀ t, t < M.horizon → ∀ s, d t s ∈ maximizingActions M u t s) →
      IsOptimal M d.randomized ∧
      (∀ s, totalValue M d.randomized s = ⨆ π : Policy M, totalValue M π s) ∧
      (∀ h : History S A, h.time ≤ M.horizon →
        continuationValue M d.randomized h = u h.time h.state)) := 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, pp. 92–93 (PDF 108–109), Theorem 4.5.1; Eqs. (4.5.1)–(4.5.2) and the terminal initialization; https://doi.org/10.1002/9780470316887.ch4
Read-back

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

Setting. Let SSS (states) be a countable, nonempty type and AAA (actions) any type. The model MMM has the following data:

  • a horizon N∈NN \in \mathbb{N}N∈N, the number of decisions;
  • for each state sss, a nonempty set As⊆AA_s \subseteq AAs​⊆A of available actions;
  • for each epoch t∈Nt \in \mathbb{N}t∈N, state sss and available action a∈Asa \in A_sa∈As​, a probability distribution pt(⋅∣s,a)p_t(\cdot \mid s,a)pt​(⋅∣s,a) on SSS and a real reward rt(s,a)r_t(s,a)rt​(s,a);
  • a real terminal reward g(s)g(s)g(s) for each state;
  • a constant C≥0C \ge 0C≥0 with ∣rt(s,a)∣≤C|r_t(s,a)| \le C∣rt​(s,a)∣≤C for all t<Nt < Nt<N, all sss and all a∈Asa \in A_sa∈As​, and ∣g(s)∣≤C|g(s)| \le C∣g(s)∣≤C for all sss. Rewards at epochs t≥Nt \ge Nt≥N are not bounded.

Histories. A history hhh is a finite list of past state–action pairs (s0,a0),…,(sk−1,ak−1)(s_0,a_0),\dots,(s_{k-1},a_{k-1})(s0​,a0​),…,(sk−1​,ak−1​) together with a current state shs_hsh​. Its time is τ(h)=k\tau(h) = kτ(h)=k, the length of the list. Nothing requires the recorded actions to be available, or the history to be reachable with positive probability. Extending hhh by an action aaa and a next state jjj appends (sh,a)(s_h,a)(sh​,a) to the list and makes jjj the current state.

Policies. A policy π\piπ assigns to every history hhh, of any length, a probability distribution π(⋅∣h)\pi(\cdot \mid h)π(⋅∣h) on AshA_{s_h}Ash​​. It may be randomized and may depend on the whole history.

A Markov rule ddd assigns to every t∈Nt \in \mathbb{N}t∈N and every state sss one action dt(s)∈Asd_t(s) \in A_sdt​(s)∈As​. Its induced policy d^\hat dd^ puts all its mass on dτ(h)(sh)d_{\tau(h)}(s_h)dτ(h)​(sh​).

Values. The continuation value Vπ(h)V^\pi(h)Vπ(h) is the expectation, a Bochner integral that is 000 by convention when the integrand is not integrable, of a random total reward. The total is built by starting from hhh and performing k=N−˙τ(h)k = N \mathbin{\dot-} \tau(h)k=N−˙​τ(h) steps, where −˙\dot-−˙​ is truncated subtraction (000 if τ(h)≥N\tau(h) \ge Nτ(h)≥N). At each step from the current history h′h'h′:

  1. sample a∼π(⋅∣h′)a \sim \pi(\cdot \mid h')a∼π(⋅∣h′);
  2. sample j∼pτ(h′)(⋅∣sh′,a)j \sim p_{\tau(h')}(\cdot \mid s_{h'}, a)j∼pτ(h′)​(⋅∣sh′​,a);
  3. collect rτ(h′)(sh′,a)r_{\tau(h')}(s_{h'},a)rτ(h′)​(sh′​,a) and extend the history by (a,j)(a, j)(a,j).

After the kkk steps, add ggg of the final state.

The total value Vπ(s)V^\pi(s)Vπ(s) is VπV^\piVπ at the history with empty past and current state sss, which has time 000.

A policy π\piπ is optimal if, for every state sss and every policy ρ\rhoρ,

Vρ(s)≤Vπ(s).V^\rho(s) \le V^\pi(s).Vρ(s)≤Vπ(s).

Every supremum sup⁡π\sup_\pisupπ​ below is the real supremum over the set of all policies. By convention it equals 000 if that set of reals is unbounded above or empty.

Hypothesis on uuu. The function u:N×S→Ru : \mathbb{N} \times S \to \mathbb{R}u:N×S→R satisfies:

  • u(N,s)=g(s)u(N,s) = g(s)u(N,s)=g(s) for every sss;
  • for every t<Nt < Nt<N and every sss, u(t,s)u(t,s)u(t,s) is the greatest element (attained maximum) of the set of scores
Qt(s,a)=rt(s,a)+∑j∈Spt(j∣s,a) u(t+1,j),a∈As.Q_t(s,a) = r_t(s,a) + \sum_{j \in S} p_t(j \mid s,a)\, u(t+1,j), \qquad a \in A_s.Qt​(s,a)=rt​(s,a)+j∈S∑​pt​(j∣s,a)u(t+1,j),a∈As​.

The series here is an unconditional sum, taken to be 000 if it is not summable. Values u(t,s)u(t,s)u(t,s) for t>Nt > Nt>N are unconstrained.

An action a∈Asa \in A_sa∈As​ is maximizing at (t,s)(t,s)(t,s) if Qt(s,b)≤Qt(s,a)Q_t(s,b) \le Q_t(s,a)Qt​(s,b)≤Qt​(s,a) for all b∈Asb \in A_sb∈As​.

Conclusion. The statement asserts two things.

  1. For every history hhh with τ(h)≤N\tau(h) \le Nτ(h)≤N:
u(τ(h),sh)=sup⁡πVπ(h).u(\tau(h), s_h) = \sup_{\pi} V^\pi(h).u(τ(h),sh​)=πsup​Vπ(h).
  1. Let ddd be any Markov rule such that dt(s)d_t(s)dt​(s) is a maximizing action at (t,s)(t,s)(t,s) for every t<Nt < Nt<N and every sss. Nothing is required of ddd at epochs t≥Nt \ge Nt≥N. Then all three of the following hold:

    • d^\hat dd^ is optimal;
    • for every state sss, Vd^(s)=sup⁡πVπ(s)V^{\hat d}(s) = \sup_\pi V^\pi(s)Vd^(s)=supπ​Vπ(s);
    • for every history hhh with τ(h)≤N\tau(h) \le Nτ(h)≤N, Vd^(h)=u(τ(h),sh)V^{\hat d}(h) = u(\tau(h), s_h)Vd^(h)=u(τ(h),sh​).

    Because the hypothesis on uuu requires the maximum to be attained at each (t,s)(t,s)(t,s) with t<Nt < Nt<N, maximizing actions exist there. Part 2 is therefore not vacuous for lack of such rules.

Degenerate cases.

  • N=0N = 0N=0: the hypothesis on uuu reduces to u(0,s)=g(s)u(0,s) = g(s)u(0,s)=g(s). The maximizing condition on ddd is vacuous, so the second part applies to every Markov rule. The only histories with τ(h)≤0\tau(h) \le 0τ(h)≤0 are those with empty past. For them, Vπ(h)=g(sh)V^\pi(h) = g(s_h)Vπ(h)=g(sh​) for every policy π\piπ, so the first part says u(0,s)=g(s)u(0,s) = g(s)u(0,s)=g(s).
  • One-element SSS: nothing changes. AAA cannot be empty, because every AsA_sAs​ is nonempty.
  • Histories in scope: the claims cover every history with τ(h)≤N\tau(h) \le Nτ(h)≤N. This includes histories whose recorded actions are unavailable or have probability zero. Histories with τ(h)>N\tau(h) > Nτ(h)>N, and values of uuu beyond epoch NNN, are not mentioned.
  • Total-function conventions: the equalities are with the real supremum, which by convention is 000 for sets unbounded above. The integrals and series that define VπV^\piVπ and QtQ_tQt​ take the value 000 when not integrable or not summable. No extra hypothesis rules these cases out beyond the model's bound CCC, which applies only to epochs t<Nt < Nt<N and to ggg.
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).

  • Endorsed by iris · Oct 31, 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