Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 4.2.2 — randomized policy evaluation

Proved
PutermanMDP.FiniteHorizon.policy_evaluation

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

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

Let π\piπ be any admissible history-dependent randomized policy in a finite-horizon model with bounded signed rewards. Let UUU be generated by the terminal initialization and randomized policy evaluation recurrence (4.2.6). For every history hth_tht​ at every epoch 0≤t≤H0\le t\le H0≤t≤H,

Ut(ht)=Ehtπ ⁣[∑k=tH−1rk(Xk,Yk)+g(XH)]=utπ(ht).U_t(h_t)=\mathbb E^\pi_{h_t}\!\left[\sum_{k=t}^{H-1}r_k(X_k,Y_k)+g(X_H)\right]=u_t^\pi(h_t).Ut​(ht​)=Eht​π​[k=t∑H−1​rk​(Xk​,Yk​)+g(XH​)]=utπ​(ht​).

In particular, vπ(s)=U0(s)v^\pi(s)=U_0(s)vπ(s)=U0​(s) for every initial state sss. This connects an algorithm defined by nested sums with the expectation of the policy-induced total reward law.

Formalization Note Epochs are shifted by one from the book, with H=N−1H=N-1H=N−1. The evaluation array is computed by an explicit recursion on the number of remaining decisions. All histories are included, even those with zero probability under π\piπ.

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

theorem policy_evaluation {S A : Type} [Countable S] [Nonempty S]
    (M : Model S A) (π : Policy M) :
    (∀ h : History S A, h.time ≤ M.horizon →
      evaluate M π (M.horizon - h.time) h = continuationValue M π h) ∧
    (∀ s, totalValue M π s = evaluate M π M.horizon (History.initial 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
-/
Source
Puterman, Markov Decision Processes, Wiley, 1994, p. 82 (PDF 98), Theorem 4.2.2; Eq. (4.2.1) on p. 80 (PDF 96); https://doi.org/10.1002/9780470316887.ch4
Read-back

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

The setting is as follows:

  • SSS is a countable, nonempty state set and AAA is any action type.
  • MMM is a model with horizon N∈NN\in\mathbb NN∈N and nonempty available-action sets A(s)A(s)A(s).
  • The transitions are probability mass functions pt(⋅∣s,a)p_t(\cdot\mid s,a)pt​(⋅∣s,a), the real rewards rt(s,a)r_t(s,a)rt​(s,a) are given for all t∈Nt\in\mathbb Nt∈N, and the terminal reward is ggg.
  • There is a constant C≥0C\ge0C≥0 with ∣rt∣≤C|r_t|\le C∣rt​∣≤C for t<Nt<Nt<N and ∣g∣≤C|g|\le C∣g∣≤C.
  • π\piπ is any randomized history-dependent policy: a probability mass function π(⋅∣h)\pi(\cdot\mid h)π(⋅∣h) on A(sh)A(s_h)A(sh​) for each history hhh.

A history is an arbitrary finite list of state–action pairs plus a current state shs_hsh​, with time τ(h)\tau(h)τ(h) equal to the list's length. h⊕(a,j)h\oplus(a,j)h⊕(a,j) appends (sh,a)(s_h,a)(sh​,a) and moves to jjj. h0(s)h_0(s)h0​(s) is the empty-list history at sss.

The two sides of the identity are defined as follows.

  • Evaluation recursion. E0(h)=g(sh)E_0(h)=g(s_h)E0​(h)=g(sh​) and
Ek+1(h)=∑a∈A(sh)π(a∣h)[rτ(h)(sh,a)+∑j∈Spτ(h)(j∣sh,a) Ek(h⊕(a,j))].E_{k+1}(h)=\sum_{a\in A(s_h)}\pi(a\mid h)\Big[r_{\tau(h)}(s_h,a)+\sum_{j\in S}p_{\tau(h)}(j\mid s_h,a)\,E_k(h\oplus(a,j))\Big].Ek+1​(h)=a∈A(sh​)∑​π(a∣h)[rτ(h)​(sh​,a)+j∈S∑​pτ(h)​(j∣sh​,a)Ek​(h⊕(a,j))].

The infinite sums are unconditional sums, taken as 000 if not summable.

  • Continuation value. vπ(h)v^\pi(h)vπ(h) is the integral of zzz against LN−τ(h)(h)L_{N-\tau(h)}(h)LN−τ(h)​(h). Here Lk(h)L_k(h)Lk​(h) is the law of ∑i<krτ(h)+i(Xi,Yi)+g(Xk)\sum_{i<k}r_{\tau(h)+i}(X_i,Y_i)+g(X_k)∑i<k​rτ(h)+i​(Xi​,Yi​)+g(Xk​) when actions are drawn from π\piπ on the growing history and states from ppp, starting at X0=shX_0=s_hX0​=sh​. The subtraction is truncated at 000, and the Bochner integral is taken as 000 if not integrable.

The theorem asserts two things:

  1. For every history hhh with τ(h)≤N\tau(h)\le Nτ(h)≤N, with any past list (reachable or not),
EN−τ(h)(h)=vπ(h).E_{N-\tau(h)}(h)=v^\pi(h).EN−τ(h)​(h)=vπ(h).
  1. For every state sss,
vπ(h0(s))=EN(h0(s)).v^\pi(h_0(s))=E_N(h_0(s)).vπ(h0​(s))=EN​(h0​(s)).

Degenerate cases.

  • Since τ(h)≤N\tau(h)\le Nτ(h)≤N in (1), the subtraction N−τ(h)N-\tau(h)N−τ(h) is never truncated there. Histories with τ(h)>N\tau(h)>Nτ(h)>N are not covered.
  • If τ(h)=N\tau(h)=Nτ(h)=N, or if N=0N=0N=0, both sides equal g(sh)g(s_h)g(sh​).
  • The equality is between quantities computed with the conventions above: non-summable sums count as 000, and a non-integrable integrand gives 000.
  • SSS is required to be nonempty. AAA is then nonempty, because A(s)≠∅A(s)\neq\varnothingA(s)=∅.
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