Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Example 7.4.1 — the improvement bound of Lemma 7.2.2 is tight for all α and γ

Proved
SampleComplexityRL.CPI.example_tight

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

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

Consider the two-state MDP with states i,ji,ji,j and actions 1,21,21,2 at each state. At iii, action 111 is a self transition with reward r(i,1)=12r(i,1)=\tfrac12r(i,1)=21​ and action 222 moves to jjj with reward r(i,2)=1r(i,2)=1r(i,2)=1. At jjj both actions are self transitions, with r(j,1)=12r(j,1)=\tfrac12r(j,1)=21​ and r(j,2)=0r(j,2)=0r(j,2)=0. The reset distribution is the point mass at iii. Let π\piπ be the deterministic policy π(i)=π(j)=1\pi(i)=\pi(j)=1π(i)=π(j)=1, π′\pi'π′ the deterministic policy π′(i)=π′(j)=2\pi'(i)=\pi'(j)=2π′(i)=π′(j)=2, and πnew=(1−α)π+απ′\pi_{\rm new}=(1-\alpha)\pi+\alpha\pi'πnew​=(1−α)π+απ′. Values are normalized and 0≤γ<10\le\gamma<10≤γ<1, 0≤α≤10\le\alpha\le10≤α≤1.

Then:

  1. dπ,i(i)=1d_{\pi,i}(i)=1dπ,i​(i)=1;
  2. Aπ(i,2)=(1−γ)/2A_\pi(i,2)=(1-\gamma)/2Aπ​(i,2)=(1−γ)/2, Aπ(j,2)=−(1−γ)/2A_\pi(j,2)=-(1-\gamma)/2Aπ​(j,2)=−(1−γ)/2, and Aπ(i,1)=Aπ(j,1)=0A_\pi(i,1)=A_\pi(j,1)=0Aπ​(i,1)=Aπ​(j,1)=0;
  3. the future advantage is Aπ(i,π′)=(1−γ)/2\mathbb A_\pi(i,\pi')=(1-\gamma)/2Aπ​(i,π′)=(1−γ)/2 and ϵ∞=max⁡s∣Ea∼π′(⋅∣s)Aπ(s,a)∣=(1−γ)/2\epsilon_\infty=\max_s|\mathbb E_{a\sim\pi'(\cdot\mid s)}A_\pi(s,a)|=(1-\gamma)/2ϵ∞​=maxs​∣Ea∼π′(⋅∣s)​Aπ​(s,a)∣=(1−γ)/2;
  4. Vπ(i)=12V_\pi(i)=\tfrac12Vπ​(i)=21​ and
Vπnew(i)=12+α2−γα21−γ(1−α);V_{\pi_{\rm new}}(i)=\frac12+\frac\alpha2-\frac{\gamma\alpha^2}{1-\gamma(1-\alpha)};Vπnew​​(i)=21​+2α​−1−γ(1−α)γα2​;
  1. consequently the improvement equals the lower bound of Lemma 7.2.2:
Vπnew(i)−Vπ(i)=α1−γ(Aπ(i,π′)−2γα1−γ(1−α)ϵ∞).V_{\pi_{\rm new}}(i)-V_\pi(i)=\frac{\alpha}{1-\gamma}\Big(\mathbb A_\pi(i,\pi')-\frac{2\gamma\alpha}{1-\gamma(1-\alpha)}\epsilon_\infty\Big).Vπnew​​(i)−Vπ​(i)=1−γα​(Aπ​(i,π′)−1−γ(1−α)2γα​ϵ∞​).

The example shows that the conservative-update bound cannot be improved uniformly in α\alphaα and γ\gammaγ, which is why CPI's step size is set from the worst case.

Formalization Note The thesis writes the state iii as "1" in its last two displays; here it is iii. The actions 1,21,21,2 are the constructors one, two, and π,π′\pi,\pi'π,π′ are indicator policies.

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

/-- **Example 7.4.1** (Kakade 2003, p. 94): the improvement bound of Lemma 7.2.2 is tight for
all `α ∈ [0, 1]` and `γ ∈ [0, 1)`. Two states `i, j`, two actions `1, 2` (`one`, `two`),
reset distribution the point mass at `i`, `π` = always action `1`, `π'` = always action `2`,
`π_new = (1 − α)π + απ'`. Then `d_{π,i}(i) = 1`, `A_π(i,2) = (1−γ)/2`, `A_π(j,2) = −(1−γ)/2`,
the advantages of the actions taken by `π` are `0`, `𝔸_π(i, π') = (1−γ)/2`,
`ε_∞ = (1−γ)/2`, `V_π(i) = 1/2`, `V_{π_new}(i) = 1/2 + α/2 − γα²/(1 − γ(1 − α))`, and
`V_{π_new}(i) − V_π(i)` equals the right-hand side of Lemma 7.2.2. -/
theorem example_tight (γ α : ℝ) (hγ0 : 0 ≤ γ) (hγ1 : γ < 1) (hα0 : 0 ≤ α) (hα1 : α ≤ 1) :
    let μ : ExState → ℝ := pointMass ExState.i
    let πnew : ExState → ExAction → ℝ := mixPolicy α exPi exPi'
    let εinf : ℝ := Finset.univ.sup' Finset.univ_nonempty
      (fun s => |∑ a, exPi' s a * advantage exP exR γ exPi s a|)
    futureStateDist exP γ exPi μ ExState.i = 1 ∧
    advantage exP exR γ exPi ExState.i ExAction.two = (1 - γ) / 2 ∧
    advantage exP exR γ exPi ExState.j ExAction.two = -((1 - γ) / 2) ∧
    advantage exP exR γ exPi ExState.i ExAction.one = 0 ∧
    advantage exP exR γ exPi ExState.j ExAction.one = 0 ∧
    policyAdvantage exP exR γ exPi μ exPi' = (1 - γ) / 2 ∧
    εinf = (1 - γ) / 2 ∧
    value exP exR γ exPi ExState.i = 1 / 2 ∧
    value exP exR γ πnew ExState.i = 1 / 2 + α / 2 - γ * α ^ 2 / (1 - γ * (1 - α)) ∧
    value exP exR γ πnew ExState.i - value exP exR γ exPi ExState.i =
      α / (1 - γ) * (policyAdvantage exP exR γ exPi μ exPi' -
        2 * γ * α / (1 - γ * (1 - α)) * εinf) := by sorry

end SampleComplexityRL.CPI
Source
Kakade, On the Sample Complexity of Reinforcement Learning, PhD thesis, University College London, 2003, p. 94, Example 7.4.1
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