Theorem 7.3.2 (Exact CPI, explicit-constant form) — strict improvement per update, halting within 8H²/ε² updates, future advantages ≤ ε/H
ProvedSampleComplexityRL.CPI.exact_cpiConsider a finite MDP with nonempty state set , nonempty action set , transition kernel , rewards and discount , with normalized values. Let , let be a reset distribution on , let , and let be a nonempty class of stationary policies. Write , for the future state-action value and for the future advantage.
Run Exact CPI (Algorithm 11): from a stationary policy , at each round the ExactPolicyChooser returns ; if , the algorithm sets and ; otherwise it halts and returns . Then there is a halting round such that
- the number of updates is bounded:
so the ExactPolicyChooser is called times; 2. every update strictly improves the value: for every the test passes and
- at round the test fails, , so the algorithm halts and returns ;
- the returned is a stationary policy and, for all ,
This is the guarantee of the exact version of conservative policy iteration: a monotone sequence of policies that stops after polynomially many updates in the horizon and the accuracy, with an output that no policy of the class can improve much in the future-advantage sense. The output is in general not a member of .
Formalization Note This is the explicit-constant form of Theorem 7.3.2: the thesis states "halts after calls" and "improves the value after each update"; the constant is the one Corollary 7.2.3 gives (improvement at least per update, with values in ). The ExactPolicyChooser is encoded by its argmax property over , which is an assumption on the run; the halting round is part of the conclusion, not an assumption. In Lean the class is named Pi.
import Mathlib import Definitions.Def_FoundationsML_ReinforcementLearning_IsTransitionKernel import Definitions.Def_FoundationsML_ReinforcementLearning_IsPolicy import Definitions.Def_ApproxOptRL_Shared_Model import Definitions.Def_ApproxOptRL_CPI_PolicyAdvantage import Definitions.Def_SampleComplexityRL_CPI_ExactCPI open ApproxOptRL.Shared ApproxOptRL.CPI FoundationsML.ReinforcementLearning
namespace SampleComplexityRL.CPI
/-- **Theorem 7.3.2 (Exact CPI)**, Kakade 2003, p. 90, in **explicit-constant form**: the
thesis's `O(H²/ε²)` is pinned to the constant `8` that Corollary 7.2.3 gives (improvement
`≥ 𝔸²/8 > ε²/(8H²)` per update, values in `[0, 1]`).
For every run `(π, π')` of Exact CPI (Algorithm 11) with policy class `Pi`, reset distribution `μ`
and accuracy `ε > 0`, there is a halting round `K` such that
1. `K < 8H²/ε²` (so the ExactPolicyChooser is called `K + 1` times);
2. at every round `k < K` the test `𝔸_{π k}(μ, π' k) > ε/H` passes and the update strictly
improves `V_π(μ)`, by more than `ε²/(8H²)`;
3. at round `K` the test fails, so the algorithm halts and returns `π K`;
4. `π K` is a stationary policy with `𝔸_{π K}(μ, h) ≤ ε/H` for every `h ∈ Pi`.
`H = 1/(1 − γ)`; values are normalized. -/
theorem exact_cpi {S A : Type} [Fintype S] [DecidableEq S] [Fintype A]
[Nonempty S] [Nonempty A]
(P : S → A → S → ℝ) (hP : IsTransitionKernel P)
(r : S → A → ℝ) (hr : ∀ s a, 0 ≤ r s a ∧ r s a ≤ 1)
(γ : ℝ) (hγ0 : 0 ≤ γ) (hγ1 : γ < 1)
(μ : S → ℝ) (hμ : IsStateDist μ)
(ε : ℝ) (hε : 0 < ε)
(Pi : Set (S → A → ℝ)) (hPi_ne : Pi.Nonempty) (hPi : ∀ h ∈ Pi, IsPolicy h)
(π π' : ℕ → S → A → ℝ) (hrun : IsExactCPIRun P r γ μ ε Pi π π') :
∃ K : ℕ,
(K : ℝ) < 8 * horizon γ ^ 2 / ε ^ 2 ∧
(∀ k < K, ε / horizon γ < policyAdvantage P r γ (π k) μ (π' k) ∧
ε ^ 2 / (8 * horizon γ ^ 2) < eta P r γ (π (k + 1)) μ - eta P r γ (π k) μ) ∧
policyAdvantage P r γ (π K) μ (π' K) ≤ ε / horizon γ ∧
IsPolicy (π K) ∧
∀ h ∈ Pi, policyAdvantage P r γ (π K) μ h ≤ ε / horizon γ := by sorry
end SampleComplexityRL.CPI
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.