Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 6.2, pp. 37–38 — deterministic NPG regret bound

Proved
PolicyGradTheory.QNPG.npg_regret_lemma

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

natural-policy-gradientp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1regret-boundsmoothness

Consider a policy class πθ with strictly positive action probabilities whose log probabilities are differentiable and β-smooth, a comparison policy π̃, a start distribution ρ, and an update θ(t+1)=θ(t)+ηw(t)\theta^{(t+1)}=\theta^{(t)}+\eta w^{(t)}θ(t+1)=θ(t)+ηw(t). Suppose π⁽⁰⁾ is uniform, η is positive, and each direction has norm at most W. Let

errt=Es∼dρπ~Ea∼π~(⋅∣s)[A(t)(s,a)−w(t)⋅∇θlog⁡π(t)(a∣s)].\mathrm{err}_t=\mathbb E_{s\sim d^{\tilde\pi}_\rho} \mathbb E_{a\sim\tilde\pi(\cdot\mid s)} [A^{(t)}(s,a)-w^{(t)}\cdot\nabla_\theta\log\pi^{(t)}(a\mid s)].errt​=Es∼dρπ~​​Ea∼π~(⋅∣s)​[A(t)(s,a)−w(t)⋅∇θ​logπ(t)(a∣s)].

For every positive horizon T, some t<Tt<Tt<T satisfies

Vπ~(ρ)−V(t)(ρ)≤11−γ(log⁡∣A∣ηT+ηβW22+1T∑i<Terri).V^{\tilde\pi}(\rho)-V^{(t)}(\rho)\le \frac{1}{1-\gamma} \left(\frac{\log|A|}{\eta T}+\frac{\eta\beta W^2}{2} +\frac{1}{T}\sum_{i<T}\mathrm{err}_i\right).Vπ~(ρ)−V(t)(ρ)≤1−γ1​(ηTlog∣A∣​+2ηβW2​+T1​i<T∑​erri​).

This isolates the deterministic optimization term from the prediction error later controlled by (25) and (26).

Formalization Note Strict positivity and differentiability are implicit in the assertion that every log action probability is smooth: Lean assigns a default value to the logarithm at zero and a totalized gradient at nondifferentiability. Nonnegative β is implicit in the usual definition of a smoothness constant. The finite minimum is represented by the existence of an index attaining at most the displayed bound.

Preamble
import Mathlib
import Definitions.Def_PolicyGradTheory_ProjGA_MDP
Formal statement
namespace PolicyGradTheory.QNPG

open FoundationsML.ReinforcementLearning

/-- Lemma 6.2, pp. 37–38, the deterministic NPG regret lemma. -/
theorem npg_regret_lemma {S A : Type} [Fintype S] [DecidableEq S]
    [Fintype A] [DecidableEq A] [Nonempty A] {d : ℕ}
    (P : S → A → S → ℝ) (r : S → A → ℝ) (γ : ℝ)
    (hM : PolicyGradTheory.ProjGA.IsFiniteMDP P r γ)
    (ρ : S → ℝ) (hρ : PolicyGradTheory.ProjGA.IsDist ρ)
    (πtilde : S → A → ℝ) (hπtilde : IsPolicy πtilde)
    (pol : EuclideanSpace ℝ (Fin d) → S → A → ℝ)
    (hpol : ∀ x, IsPolicy (pol x))
    (hpos : ∀ x s a, 0 < pol x s a)
    (β : ℝ) (hβ : 0 ≤ β)
    (hdiff : ∀ s a, Differentiable ℝ (fun z => Real.log (pol z s a)))
    (hsmooth : ∀ s a x y,
      ‖gradient (fun z => Real.log (pol z s a)) x -
        gradient (fun z => Real.log (pol z s a)) y‖ ≤ β * ‖x - y‖)
    (η W : ℝ) (hη : 0 < η)
    (T : ℕ) (hT : 0 < T)
    (θ w : ℕ → EuclideanSpace ℝ (Fin d))
    (hupdate : ∀ t < T, θ (t + 1) = θ t + η • w t)
    (hinit : ∀ s a, pol (θ 0) s a = 1 / (Fintype.card A : ℝ))
    (hw : ∀ t ≤ T, ‖w t‖ ≤ W) :
    ∃ t : ℕ, t < T ∧
      PolicyGradTheory.ProjGA.valueAt πtilde P r γ ρ - PolicyGradTheory.ProjGA.valueAt (pol (θ t)) P r γ ρ ≤
        (1 / (1 - γ)) *
          (Real.log (Fintype.card A : ℝ) / (η * T) + η * β * W ^ 2 / 2 +
            (1 / (T : ℝ)) * ∑ i ∈ Finset.range T,
              ∑ s : S, PolicyGradTheory.ProjGA.visitation πtilde P γ ρ s *
                ∑ a : A, πtilde s a *
                  (PolicyGradTheory.ProjGA.advantage (pol (θ i)) P r γ s a -
                    inner ℝ (w i) (gradient (fun z => Real.log (pol z s a)) (θ i)))) := by sorry

end PolicyGradTheory.QNPG
Source
arXiv:1908.00261v5, Lemma 6.2, pp. 37–38, (23)–(24)
Human review
  • Endorsed by Shuze Chen · Oct 6, 2026

    Confirmed by the moderator at approval.

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