Theorem 8.6.6 — finite termination of unichain policy iteration
DisprovedPutermanMDP.Unichain.policy_iteration_terminatesLet be a finite stationary Markov decision process with a nonempty state set and nonempty admissible action sets, and suppose every admissible deterministic stationary policy is unichain. Start with any admissible rule . Policy iteration evaluates each rule by (8.6.1), chooses a maximizing rule by (8.6.2), retains the whole incumbent if it is still maximizing, and stops at the first equality of consecutive rules.
Runs exist from every . For every run, with arbitrary choices of evaluation constants and maximizing rules allowed by those steps, there is a finite first stopping index such that
The returned stationary policy is average optimal against every admissible history-dependent randomized policy :
Its scalar evaluation value is the optimal gain under both criteria:
This is finite termination of the actual policy iteration algorithm, including transient states, rather than just existence of an optimality-equation solution. Average rewards are limits of expected finite-horizon rewards per decision epoch.
Differences from the source:
- encoding: finite nonempty state set and finite nonempty state-dependent action sets → finite types S and A, Nonempty S, and nonempty admissible finsets; reason: the union of finitely many finite action sets is finite; irrelevant action entries can be extended by zero rewards and any stochastic row
- encoding: standing finite unichain model of §8.6 with bounded rewards → IsUnichain M and a finite stationary MDP; reason: finiteness makes the reward bound automatic; no irreducibility or aperiodicity is added
- encoding: policy iteration initialized at an arbitrary rule and stopped at its first adjacent equality → existence of infinite extensions of runs and a first finite stopping index for every such run; reason: continuation past stopping only represents a finite execution by a total sequence; it adds no assumption of termination
- encoding: a solution (g*,h) and an average optimal stationary policy → Bellman equality, expected liminf-versus-limsup optimality, and equality with both optimal gain functions; reason: these spell out the meanings of g* and average optimality in §8.1.2; evaluation vectors retain all permitted additive constants
import Mathlib import Definitions.Def_PutermanMDP_Unichain_Iteration open MarkovDecisionProcesses
namespace PutermanMDP.Unichain
/-- Theorem 8.6.6 with every permitted evaluation solution and tie choice.
Runs exist from every initial rule, and every run reaches the exact step-4
stopping test with Bellman equality and optimality against all HR policies. -/
theorem policy_iteration_terminates {S A : Type*} [Fintype S] [Fintype A]
[DecidableEq A] [Nonempty S] (M : StationaryMDP S A) (hM : IsUnichain M)
(d₀ : Rule M) :
(∃ (d : ℕ → Rule M) (g : ℕ → ℝ) (h : ℕ → S → ℝ),
d 0 = d₀ ∧ IsRun M d g h) ∧
(∀ (d : ℕ → Rule M) (g : ℕ → ℝ) (h : ℕ → S → ℝ),
d 0 = d₀ → IsRun M d g h →
∃ n, StopsAt M d n ∧
(∀ s, optimalityResidual M (g n) (h n) s = 0) ∧
IsAverageOptimal (stationaryPolicy M (d n).val (d n).property) ∧
(∀ s, optGainSup M s = g n ∧ optGainInf M s = g n)) := by sorry
end PutermanMDP.Unichain
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
The statement concerns a finite stationary MDP with state set and action set . The types and are arbitrary types, each with finitely many elements. has decidable equality. is required to be nonempty; is not. The remaining hypotheses are:
- belongs to a structure called
StationaryMDPon and ; - satisfies a predicate
IsUnichain; - is an element of a type
Rule M(a "rule" for ).
The notions StationaryMDP, Rule, IsUnichain, IsRun, StopsAt, optimalityResidual, stationaryPolicy, IsAverageOptimal, optGainSup and optGainInf all come from the imported definitions file, whose code was not available to me. Each is described below only by its name and the arguments it receives; their actual content is not visible here. The code does show two structural facts about Rule M:
- each rule has an underlying value and an accompanying proof ;
- these two pieces are what get passed to
stationaryPolicy.
Conclusion. The statement is the conjunction of two claims.
(i) Existence. There exist all three of the following:
- a sequence of rules in
Rule M; - a sequence of real numbers ;
- a sequence of real-valued functions , with .
They satisfy (the given initial rule) and .
(ii) Universal claim. Take any sequences , , of the same types with first rule equal to the given and . For every such triple, there exists a natural number satisfying all of the following:
- holds;
- for every state ,
- the policy built from the -th rule satisfies ;
- for every state ,
Both are real numbers.
Strength of the claim.
- The index is only asserted to exist, separately for each triple . Nothing says is the first index with these properties, or that it is unique.
- No bound on is given, uniform or otherwise. may depend on the particular run.
- Nothing is asserted about indices other than .
- The conclusions in items 2–4 refer to the single value and the single function at that same index .
- Claim (ii) quantifies over every triple satisfying
IsRun. So whatever freedomIsRunleaves, it is all covered, including in the choice of , and later rules.
Degenerate cases.
- . This is permitted as a witness. Then the conclusion concerns , and themselves.
- One-element . This is allowed. The "for every state" clauses then reduce to a single state.
- Empty . This is excluded by the hypothesis that is nonempty.
- Empty . This is not excluded by any hypothesis. If
Rule Mhas no elements in that case (or in any other), no can be supplied and the statement is vacuously true. Whether that happens depends on the unseen definition ofRule. IsUnichainnever satisfiable. IfIsUnichaincannot hold for any , the whole statement is vacuous. That also cannot be determined from this code.IsRunnever satisfiable. Claim (i) asserts that at least one run starting from exists, so claim (ii) is not vacuous for lack of runs, provided the hypotheses on and can be met.- Default values. Two quantities are stated to be equal to the real number at every state:
optGainSupandoptGainInf. If either is defined through a supremum or infimum over real numbers, or through a limit, it could take a default value whenever that set is empty or unbounded, or the limit fails to exist. Such a default is typically for real suprema and infima. In that event the equalities could hold or fail through that default rather than through a genuine optimum. Whether this can occur depends on the unseen definitions. optimalityResidual. Likewise, the content of "" depends entirely on how that quantity is defined, including any default values it may involve.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.