Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 28.11: FTRL unit-ball bandit regret 23ndlog⁡n2\sqrt{3nd\log n}23ndlogn​ (corrected root)

Proved
BanditAlgorithm.adversarial_linear_bandit_ftrl_unit_ball_regret_indep_seeds

by Shuze Chen · Jul 29, 2026 · Mathlib 0df444a (Lean v4.33.1)

adversarialbanditsftrlonline-learning

(Adversarial linear bandit on the unit ball, GOAL, Theorem 28.11; corrected root — supersedes BanditAlgorithm.adversarial_linear_bandit_ftrl_unit_ball_regret, whose hypotheses omitted the within-round independence of the two seeds.) Fix oblivious losses ∥yt∥2≤1\|y_t\|_2 \le 1∥yt​∥2​≤1, 2≤n2 \le n2≤n, and action set the Euclidean unit ball. On a probability space carrying per-round seeds Vt∼Unif[0,1]V_t \sim \mathrm{Unif}[0,1]Vt​∼Unif[0,1] and Wt∼Unif({±e1,…,±ed})W_t \sim \mathrm{Unif}(\{\pm e_1,\ldots,\pm e_d\})Wt​∼Unif({±e1​,…,±ed​}) such that the pairs (Vt,Wt)(V_t, W_t)(Vt​,Wt​) are mutually independent across rounds and, within each round, VtV_tVt​ is independent of WtW_tWt​ — so the 2n2n2n seeds are jointly independent, exactly as Algorithm 17 samples the exploration bit and the direction UtU_tUt​ separately — Algorithm 16/17 runs FTRL with the Legendre potential

F(a)=−log⁡(1−∥a∥)−∥a∥F(a) = -\log(1-\|a\|) - \|a\|F(a)=−log(1−∥a∥)−∥a∥

on the shrunken ball of radius r=1−2ηd>0r = 1 - 2\eta d > 0r=1−2ηd>0 with η=log⁡(n)/(3dn)\eta = \sqrt{\log(n)/(3dn)}η=log(n)/(3dn)​: with exploration indicator Et=1{Vt<1−∥Aˉt∥}E_t = \mathbb{1}\{V_t < 1-\|\bar A_t\|\}Et​=1{Vt​<1−∥Aˉt​∥} it plays

At=EtUt+(1−Et)Aˉt∥Aˉt∥A_t = E_t U_t + (1-E_t)\frac{\bar A_t}{\|\bar A_t\|}At​=Et​Ut​+(1−Et​)∥Aˉt​∥Aˉt​​

and feeds FTRL the one-point importance-weighted estimator (Eq. (28.12))

Y^t=d Et ⟨At,yt⟩1−∥Aˉt∥ At.\hat Y_t = \frac{d\, E_t\, \langle A_t, y_t\rangle}{1-\|\bar A_t\|}\, A_t.Y^t​=1−∥Aˉt​∥dEt​⟨At​,yt​⟩​At​.

Then the expected regret satisfies

E[∑t<n⟨At−a0,yt⟩]≤23ndlog⁡n\mathbb{E}\Big[\sum_{t<n}\langle A_t - a_0, y_t\rangle\Big] \le 2\sqrt{3 n d \log n}E[t<n∑​⟨At​−a0​,yt​⟩]≤23ndlogn​

for every comparator a0a_0a0​ in the unit ball.

The within-round independence hypothesis is used exactly once in the source proof: it makes Y^t\hat Y_tY^t​ conditionally unbiased given the past (the sentence after Eq. (28.12)), which is what allows the FTRL master bound (Theorem 28.10) to be applied to the estimated losses.

Preamble
import Definitions.Def_OnlineLinearOptimization
import Mathlib.Probability.Independence.Basic
import Mathlib.MeasureTheory.Measure.Lebesgue.Basic
import Mathlib.MeasureTheory.Integral.Bochner.Basic


open RealInnerProductSpace MeasureTheory ProbabilityTheory
Formal statement
theorem BanditAlgorithm.adversarial_linear_bandit_ftrl_unit_ball_regret_indep_seeds
    (d n : ℕ) (hd : 0 < d) (hn : 2 ≤ n)
    (y : ℕ → EuclideanSpace ℝ (Fin d)) (hy : ∀ t, ‖y t‖ ≤ 1)
    (η r : ℝ)
    (hη : η = Real.sqrt (Real.log n / (3 * d * n)))
    (hr : r = 1 - 2 * η * d) (hr0 : 0 < r)
    {Ω : Type*} [MeasurableSpace Ω] (P : Measure Ω) [IsProbabilityMeasure P]
    (V : ℕ → Ω → ℝ) (W : ℕ → Ω → Fin d × Bool)
    (hVmeas : ∀ t, Measurable (V t)) (hWmeas : ∀ t, Measurable (W t))
    (hindep : iIndepFun (fun t ω => (V t ω, W t ω)) P)
    (hVW : ∀ t, IndepFun (V t) (W t) P)
    (hV : ∀ t, Measure.map (V t) P = (volume : Measure ℝ).restrict (Set.Icc 0 1))
    (hW : ∀ t (u : Fin d × Bool), P {ω | W t ω = u} = ((2 * d : ℕ) : ENNReal)⁻¹)
    (Abar A Yhat : ℕ → Ω → EuclideanSpace ℝ (Fin d))
    (hftrl : ∀ ω, IsFTRLIterates η
      (fun b : EuclideanSpace ℝ (Fin d) => -Real.log (1 - ‖b‖) - ‖b‖)
      (Metric.ball 0 1) (Metric.closedBall 0 r)
      (fun t => Yhat t ω) (fun t => Abar t ω))
    (hA : ∀ t ω, A t ω =
      if V t ω < 1 - ‖Abar t ω‖ then
        (if (W t ω).2 then (1 : ℝ) else -1) • EuclideanSpace.single (W t ω).1 1
      else ‖Abar t ω‖⁻¹ • Abar t ω)
    (hY : ∀ t ω, Yhat t ω =
      (if V t ω < 1 - ‖Abar t ω‖ then
        d * ⟪A t ω, y t⟫ / (1 - ‖Abar t ω‖) else 0) • A t ω) :
    ∀ a₀ ∈ Metric.closedBall (0 : EuclideanSpace ℝ (Fin d)) 1,
      ∫ ω, oloRegret (fun t => A t ω) y n a₀ ∂P ≤
        2 * Real.sqrt (3 * n * d * Real.log n) := by
  sorry
Source
L&S Theorem 28.11, p.338

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