Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 7.3.2 (Exact CPI, explicit-constant form) — strict improvement per update, halting within 8H²/ε² updates, future advantages ≤ ε/H

Proved
SampleComplexityRL.CPI.exact_cpi

by mikedeng1 · Oct 7, 2026 · Mathlib 0df444a (Lean v4.33.1)

dynamic-programmingoptimizationp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-bookp2o-v1reinforcement-learning

Consider a finite MDP with nonempty state set SSS, nonempty action set AAA, transition kernel PPP, rewards r(s,a)∈[0,1]r(s,a)\in[0,1]r(s,a)∈[0,1] and discount 0≤γ<10\le\gamma<10≤γ<1, with normalized values. Let H=1/(1−γ)H=1/(1-\gamma)H=1/(1−γ), let μ\muμ be a reset distribution on SSS, let ε>0\varepsilon>0ε>0, and let Π\PiΠ be a nonempty class of stationary policies. Write Vπ(μ)=Es∼μ[Vπ(s)]V_\pi(\mu)=\mathbb E_{s\sim\mu}[V_\pi(s)]Vπ​(μ)=Es∼μ​[Vπ​(s)], Qπ(μ,h)\mathbb Q_\pi(\mu,h)Qπ​(μ,h) for the future state-action value and Aπ(μ,h)=Es∼dπ,μEa∼h(⋅∣s)[Aπ(s,a)]\mathbb A_\pi(\mu,h)=\mathbb E_{s\sim d_{\pi,\mu}}\mathbb E_{a\sim h(\cdot\mid s)}[A_\pi(s,a)]Aπ​(μ,h)=Es∼dπ,μ​​Ea∼h(⋅∣s)​[Aπ​(s,a)] for the future advantage.

Run Exact CPI (Algorithm 11): from a stationary policy π0\pi_0π0​, at each round kkk the ExactPolicyChooser returns πk′∈arg⁡max⁡h∈ΠQπk(μ,h)\pi'_k\in\arg\max_{h\in\Pi}\mathbb Q_{\pi_k}(\mu,h)πk′​∈argmaxh∈Π​Qπk​​(μ,h); if Aπk(μ,πk′)>ε/H\mathbb A_{\pi_k}(\mu,\pi'_k)>\varepsilon/HAπk​​(μ,πk′​)>ε/H, the algorithm sets αk=Aπk(μ,πk′)/(4H)\alpha_k=\mathbb A_{\pi_k}(\mu,\pi'_k)/(4H)αk​=Aπk​​(μ,πk′​)/(4H) and πk+1=(1−αk)πk+αkπk′\pi_{k+1}=(1-\alpha_k)\pi_k+\alpha_k\pi'_kπk+1​=(1−αk​)πk​+αk​πk′​; otherwise it halts and returns πk\pi_kπk​. Then there is a halting round KKK such that

  1. the number of updates is bounded:
K<8H2ε2,K<\frac{8H^2}{\varepsilon^2},K<ε28H2​,

so the ExactPolicyChooser is called K+1K+1K+1 times; 2. every update strictly improves the value: for every k<Kk<Kk<K the test passes and

Vπk+1(μ)−Vπk(μ)>ε28H2;V_{\pi_{k+1}}(\mu)-V_{\pi_k}(\mu)>\frac{\varepsilon^2}{8H^2};Vπk+1​​(μ)−Vπk​​(μ)>8H2ε2​;
  1. at round KKK the test fails, AπK(μ,πK′)≤ε/H\mathbb A_{\pi_K}(\mu,\pi'_K)\le\varepsilon/HAπK​​(μ,πK′​)≤ε/H, so the algorithm halts and returns πK\pi_KπK​;
  2. the returned πK\pi_KπK​ is a stationary policy and, for all h∈Πh\in\Pih∈Π,
AπK(μ,h)≤εH.\mathbb A_{\pi_K}(\mu,h)\le\frac{\varepsilon}{H}.AπK​​(μ,h)≤Hε​.

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 Π\PiΠ.

Formalization Note This is the explicit-constant form of Theorem 7.3.2: the thesis states "halts after O(H2/ε2)O(H^2/\varepsilon^2)O(H2/ε2) calls" and "improves the value after each update"; the constant 888 is the one Corollary 7.2.3 gives (improvement at least A2/8>(ε/H)2/8\mathbb A^2/8>(\varepsilon/H)^2/8A2/8>(ε/H)2/8 per update, with values in [0,1][0,1][0,1]). The ExactPolicyChooser is encoded by its argmax property over Π\PiΠ, 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.

Preamble
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
Formal statement
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
Source
Kakade, On the Sample Complexity of Reinforcement Learning, PhD thesis, University College London, 2003, p. 90, Theorem 7.3.2 (Exact CPI), with Algorithm 11 (p. 90) and Corollary 7.2.3 (p. 87)
Human review
  • Endorsed by Shuze Chen · Oct 7, 2026

    Confirmed by the moderator at approval.

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