Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 3.1 — under SBAR(J), Regret(z,T,PEGE) ≤ a₁(‖z‖ + 1/‖z‖)r√T and Risk(T,PEGE) ≤ a₂ r√T

Proved
LinParamBandits.PEGE.pege_regret_bound

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

bayes-risklinear-banditp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1regret

This is the main upper bound for the Phased Exploration and Greedy Exploitation policy.

  1. Let σ0,uˉ,λ0,J>0\sigma_0, \bar u, \lambda_0, J > 0σ0​,uˉ,λ0​,J>0. There is a constant a1>0a_1 > 0a1​>0, depending only on σ0,uˉ,λ0,J\sigma_0, \bar u, \lambda_0, Jσ0​,uˉ,λ0​,J, such that for every dimension r≥2r \ge 2r≥2, every arm set Ur\mathcal U_rUr​, error laws and exploration arms satisfying Assumption 1 with these constants and the SBAR(JJJ) condition, every greedy rule, every z∈Rr∖{0}z \in \mathbb R^r \setminus \{0\}z∈Rr∖{0} and every T≥rT \ge rT≥r,
Regret(z,T,PEGE)≤a1(∥z∥+1∥z∥) rT.\mathrm{Regret}(z, T, \mathrm{PEGE}) \le a_1 \Big(\|z\| + \frac{1}{\|z\|}\Big)\, r \sqrt T.Regret(z,T,PEGE)≤a1​(∥z∥+∥z∥1​)rT​.
  1. Let in addition M>0M > 0M>0. There is a constant a2>0a_2 > 0a2​>0, depending only on σ0,uˉ,λ0,J,M\sigma_0, \bar u, \lambda_0, J, Mσ0​,uˉ,λ0​,J,M, such that for every such rrr, instance and greedy rule, every prior μ\muμ on Rr\mathbb R^rRr with E[∥Z∥]≤M\mathbb E[\|Z\|] \le ME[∥Z∥]≤M and E[1/∥Z∥]≤M\mathbb E[1/\|Z\|] \le ME[1/∥Z∥]≤M, and every T≥rT \ge rT≥r,
Risk(T,PEGE)≤a2 rT.\mathrm{Risk}(T, \mathrm{PEGE}) \le a_2\, r \sqrt T.Risk(T,PEGE)≤a2​rT​.

Together with the lower bound of Theorem 2.1 this shows that PEGE attains the optimal order rTr\sqrt TrT​ for arm sets with smooth best arm response, such as the unit sphere.

Formalization Note The constants are chosen before the dimension, the arm set, the error laws, the exploration arms, the greedy rule, the prior, zzz and TTT; a constant allowed to depend on rrr or on the instance would make the statement trivial, since the regret never exceeds 2uˉ∥z∥T2\bar u\|z\|T2uˉ∥z∥T. The moments of ZZZ are lower Lebesgue integrals: E[1/∥Z∥]\mathbb E[1/\|Z\|]E[1/∥Z∥] is +∞+\infty+∞ when μ\muμ charges the origin. Regret and risk take values in [0,∞][0, \infty][0,∞], so the bounds also assert finiteness.

Preamble
import Mathlib
import Definitions.Def_LinParamBandits_PEGE_Model

open MeasureTheory ProbabilityTheory
Formal statement
namespace LinParamBandits.PEGE

/-- Theorem 3.1 (Regret and Risk Under the Greedy Policy), Rusmevichientong, Tsitsiklis,
arXiv:0812.3465v2, p. 15. Under Assumption 1 and SBAR(`J`):

1. there is a positive constant `a₁`, depending only on `σ₀, ū, λ₀, J`, such that for any
   `z ∈ ℝ^r \ {0}` and `T ≥ r`, `Regret(z, T, PEGE) ≤ a₁ (‖z‖ + 1/‖z‖) r √T`;
2. if moreover `E[‖Z‖] ≤ M` and `E[1/‖Z‖] ≤ M` for every `r ≥ 2`, there is a positive constant `a₂`,
   depending only on `σ₀, ū, λ₀, J, M`, such that for any `T ≥ r`, `Risk(T, PEGE) ≤ a₂ r √T`.

The constants are chosen before the dimension `r`, the arm set, the error laws, the exploration
arms, the tie-breaking rule, the prior, `z` and `T`. -/
theorem pege_regret_bound :
    (∀ σ₀ ū lam₀ J : ℝ, 0 < σ₀ → 0 < ū → 0 < lam₀ → 0 < J →
      ∃ a₁ : ℝ, 0 < a₁ ∧
        ∀ (r : ℕ), 2 ≤ r →
        ∀ (𝒰 : Set (LinParamBandits.LowerBound.Vec r)) (ν : LinParamBandits.LowerBound.Vec r → ProbabilityMeasure ℝ) (b : Fin r → LinParamBandits.LowerBound.Vec r)
          (g : ℕ → LinParamBandits.LowerBound.Vec r → LinParamBandits.LowerBound.Vec r),
        Assumption1 𝒰 ν b σ₀ ū lam₀ → SBAR 𝒰 J → GreedySelector 𝒰 g →
        ∀ (z : LinParamBandits.LowerBound.Vec r), z ≠ 0 → ∀ (T : ℕ), r ≤ T →
          regret 𝒰 ν b g z T ≤ ENNReal.ofReal (a₁ * (‖z‖ + 1 / ‖z‖) * r * Real.sqrt T)) ∧
    (∀ σ₀ ū lam₀ J M : ℝ, 0 < σ₀ → 0 < ū → 0 < lam₀ → 0 < J → 0 < M →
      ∃ a₂ : ℝ, 0 < a₂ ∧
        ∀ (r : ℕ), 2 ≤ r →
        ∀ (𝒰 : Set (LinParamBandits.LowerBound.Vec r)) (ν : LinParamBandits.LowerBound.Vec r → ProbabilityMeasure ℝ) (b : Fin r → LinParamBandits.LowerBound.Vec r)
          (g : ℕ → LinParamBandits.LowerBound.Vec r → LinParamBandits.LowerBound.Vec r),
        Assumption1 𝒰 ν b σ₀ ū lam₀ → SBAR 𝒰 J → GreedySelector 𝒰 g →
        ∀ (μ : Measure (LinParamBandits.LowerBound.Vec r)), IsProbabilityMeasure μ →
          ∫⁻ z, ‖z‖ₑ ∂μ ≤ ENNReal.ofReal M → ∫⁻ z, ‖z‖ₑ⁻¹ ∂μ ≤ ENNReal.ofReal M →
        ∀ (T : ℕ), r ≤ T →
          risk μ 𝒰 ν b g T ≤ ENNReal.ofReal (a₂ * r * Real.sqrt T)) := by sorry
end LinParamBandits.PEGE
Source
Rusmevichientong, Tsitsiklis, Linearly Parameterized Bandits, arXiv:0812.3465v2, Theorem 3.1, p. 15
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