Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 4.1, p. 15 — projected gradient ascent with η = (1−γ)³/(2γ|A|): V⋆(ρ) − V^{(t)}(ρ) ≤ ε for some t ≤ T whenever T > 64γ|S||A|D²/((1−γ)⁶ε²)

Proved
PolicyGradTheory.ProjGA.projected_gradient_ascent_rate

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

global-convergenceiteration-complexityp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1policy-gradientprojected-gradient-ascent

Let (S,A,P,r,γ)(\mathcal S,\mathcal A,P,r,\gamma)(S,A,P,r,γ) be a finite discounted MDP with rewards r(s,a)∈[0,1]r(s,a)\in[0,1]r(s,a)∈[0,1] and discount factor γ∈(0,1)\gamma\in(0,1)γ∈(0,1). Let μ,ρ∈Δ(S)\mu,\rho\in\Delta(\mathcal S)μ,ρ∈Δ(S) be state distributions, π⋆\pi^\starπ⋆ an optimal policy with V⋆=Vπ⋆V^\star=V^{\pi^\star}V⋆=Vπ⋆, and dρπ⋆d^{\pi^\star}_\rhodρπ⋆​ its discounted state visitation distribution from ρ\rhoρ. Let DDD be a bound on the distribution mismatch coefficient, i.e. dρπ⋆(s)≤D μ(s)d^{\pi^\star}_\rho(s)\le D\,\mu(s)dρπ⋆​(s)≤Dμ(s) for all sss (the smallest such DDD is ∥dρπ⋆/μ∥∞\|d^{\pi^\star}_\rho/\mu\|_\infty∥dρπ⋆​/μ∥∞​).

Run projected gradient ascent (9) on Vπ(μ)V^\pi(\mu)Vπ(μ) under the direct parameterization,

π(t+1)=PΔ(A)∣S∣(π(t)+η∇πV(t)(μ)),η=(1−γ)32γ∣A∣,\pi^{(t+1)}=P_{\Delta(\mathcal A)^{|\mathcal S|}}\big(\pi^{(t)}+\eta\nabla_\pi V^{(t)}(\mu)\big),\qquad \eta=\frac{(1-\gamma)^3}{2\gamma|\mathcal A|},π(t+1)=PΔ(A)∣S∣​(π(t)+η∇π​V(t)(μ)),η=2γ∣A∣(1−γ)3​,

from any initial policy π(0)\pi^{(0)}π(0), where PΔ(A)∣S∣P_{\Delta(\mathcal A)^{|\mathcal S|}}PΔ(A)∣S∣​ is the Euclidean projection onto the product simplex.

Theorem. For every ϵ>0\epsilon>0ϵ>0 and every integer TTT with

T>64γ∣S∣∣A∣(1−γ)6ϵ2 D2,T>\frac{64\gamma|\mathcal S||\mathcal A|}{(1-\gamma)^6\epsilon^2}\,D^2,T>(1−γ)6ϵ264γ∣S∣∣A∣​D2,

there is an index t∈{0,1,…,T}t\in\{0,1,\dots,T\}t∈{0,1,…,T} with V⋆(ρ)−V(t)(ρ)≤ϵV^\star(\rho)-V^{(t)}(\rho)\le\epsilonV⋆(ρ)−V(t)(ρ)≤ϵ.

The guarantee holds simultaneously for all performance distributions ρ\rhoρ, although the algorithm only optimizes Vπ(μ)V^\pi(\mu)Vπ(μ); the price of the mismatch between ρ\rhoρ and μ\muμ is the factor D2D^2D2. It is the paper's first global convergence rate for a policy gradient method on a non-concave objective.

Formalization Note (1) The page states min⁡t<T\min_{t<T}mint<T​; its proof (p. 50) bounds min⁡t=0,…,T\min_{t=0,\dots,T}mint=0,…,T​ because Proposition B.1 transfers a small gradient mapping at π(t)\pi^{(t)}π(t) to near-stationarity at π(t+1)\pi^{(t+1)}π(t+1). The printed index range fails at T=1T=1T=1 (one state, two actions with rewards 1 and 0, γ=0.001\gamma=0.001γ=0.001, μ=ρ=δs\mu=\rho=\delta_sμ=ρ=δs​, D=1D=1D=1, ϵ=1/2\epsilon=1/2ϵ=1/2, π(0)\pi^{(0)}π(0) on the bad action), so the statement uses t≤Tt\le Tt≤T. (2) γ>0\gamma>0γ>0 is assumed: the step size divides by γ\gammaγ. (3) ϵ>0\epsilon>0ϵ>0 is assumed: the threshold divides by ϵ\epsilonϵ. (4) The mismatch coefficient is any upper bound DDD, avoiding Lean's x/0=0x/0=0x/0=0. (5) The gradient is the Euclidean gradient of π↦Vπ(μ)\pi\mapsto V^\pi(\mu)π↦Vπ(μ) on EuclideanSpace ℝ (S × A), and the projection is any map satisfying the projection predicate.

Preamble
import Mathlib
import Definitions.Def_FoundationsML_ReinforcementLearning_IsPolicy
import Definitions.Def_FoundationsML_ReinforcementLearning_IsOptimalPolicy
import Definitions.Def_PolicyGradTheory_ProjGA_MDP
import Definitions.Def_PolicyGradTheory_ProjGA_Projection
import Definitions.Def_PolicyGradTheory_ProjGA_Algorithm

open FoundationsML.ReinforcementLearning
Formal statement
namespace PolicyGradTheory.ProjGA

/-- Theorem 4.1, arXiv:1908.00261v5, p. 15: projected gradient ascent (9) on `V^π(μ)` with step
size `η = (1−γ)³/(2γ|A|)`, from any initial policy, satisfies, for every distribution `ρ`,
`V⋆(ρ) − V^{(t)}(ρ) ≤ ε` for some `t ≤ T` whenever `T > 64γ|S||A|/((1−γ)⁶ε²) · D²`, where `D` is
any bound `d^{π⋆}_ρ ≤ D μ` on the distribution mismatch coefficient `‖d^{π⋆}_ρ/μ‖_∞`. The index
range `t ≤ T` is the one the proof (p. 50) establishes; the printed `t < T` fails at `T = 1`. -/
theorem projected_gradient_ascent_rate {S A : Type*} [Fintype S] [DecidableEq S] [Fintype A]
    [DecidableEq A] (P : S → A → S → ℝ) (r : S → A → ℝ) (γ : ℝ) (hM : IsFiniteMDP P r γ)
    (hγ : 0 < γ) (μ : S → ℝ) (hμ : IsDist μ) (ρ : S → ℝ) (hρ : IsDist ρ)
    (πstar : S → A → ℝ) (hπstar : IsPolicy πstar) (hopt : IsOptimalPolicy πstar P r γ)
    (D : ℝ) (hD : ∀ s, visitation πstar P γ ρ s ≤ D * μ s)
    (Proj : EuclideanSpace ℝ (S × A) → EuclideanSpace ℝ (S × A))
    (hProj : IsProjOnto (simplexSet S A) Proj)
    (π : ℕ → EuclideanSpace ℝ (S × A)) (hπ0 : π 0 ∈ simplexSet S A)
    (hrun : IsProjGARun P r γ μ ((1 - γ) ^ 3 / (2 * γ * (Fintype.card A : ℝ))) Proj π)
    (ε : ℝ) (hε : 0 < ε) :
    ∀ T : ℕ,
      64 * γ * (Fintype.card S : ℝ) * (Fintype.card A : ℝ) / ((1 - γ) ^ 6 * ε ^ 2) * D ^ 2 <
          (T : ℝ) →
        ∃ t ≤ T, valueAt πstar P r γ ρ - valueAt (asPolicy (π t)) P r γ ρ ≤ ε := by sorry

end PolicyGradTheory.ProjGA
Source
arXiv:1908.00261v5, Theorem 4.1, p. 15 (proof App. B.1, pp. 49–50)
Human review
  • Endorsed by Shuze Chen · Oct 5, 2026

    Confirmed by the moderator at approval.

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