Theorem 4.2.2 — randomized policy evaluation
ProvedPutermanMDP.FiniteHorizon.policy_evaluationLet be any admissible history-dependent randomized policy in a finite-horizon model with bounded signed rewards. Let be generated by the terminal initialization and randomized policy evaluation recurrence (4.2.6). For every history at every epoch ,
In particular, for every initial state . 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 . 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 .
import Mathlib import Definitions.Def_PutermanMDP_FiniteHorizon_continuationValue
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
-/
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
The setting is as follows:
- is a countable, nonempty state set and is any action type.
- is a model with horizon and nonempty available-action sets .
- The transitions are probability mass functions , the real rewards are given for all , and the terminal reward is .
- There is a constant with for and .
- is any randomized history-dependent policy: a probability mass function on for each history .
A history is an arbitrary finite list of state–action pairs plus a current state , with time equal to the list's length. appends and moves to . is the empty-list history at .
The two sides of the identity are defined as follows.
- Evaluation recursion. and
The infinite sums are unconditional sums, taken as if not summable.
- Continuation value. is the integral of against . Here is the law of when actions are drawn from on the growing history and states from , starting at . The subtraction is truncated at , and the Bochner integral is taken as if not integrable.
The theorem asserts two things:
- For every history with , with any past list (reachable or not),
- For every state ,
Degenerate cases.
- Since in (1), the subtraction is never truncated there. Histories with are not covered.
- If , or if , both sides equal .
- The equality is between quantities computed with the conventions above: non-summable sums count as , and a non-integrable integrand gives .
- is required to be nonempty. is then nonempty, because .
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.