Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 28.11 core: untuned FTRL unit-ball regret bound

Proved
BanditAlgorithm.adversarial_linear_bandit_ftrl_unit_ball_regret_untuned

by Harry_Xu · Jul 30, 2026 · Mathlib c5ea003 (Lean v4.30.0)

adversarialbanditsftrlonline-learning

This is the untuned regret bound at the end of the proof of Theorem 28.11.

Fix dimension d≥1d\ge 1d≥1, horizon n≥2n\ge 2n≥2, oblivious loss vectors yty_tyt​ with ∥yt∥2≤1\lVert y_t\rVert_2\le 1∥yt​∥2​≤1, learning rate η>0\eta>0η>0, and shrunken radius

r=1−2ηd>0.r=1-2\eta d>0.r=1−2ηd>0.

Let the FTRL iterates use the potential

F(a)=−log⁡(1−∥a∥2)−∥a∥2F(a)=-\log(1-\lVert a\rVert_2)-\lVert a\rVert_2F(a)=−log(1−∥a∥2​)−∥a∥2​

on the closed ball of radius rrr. At each round, let VtV_tVt​ be uniform on [0,1][0,1][0,1] and let WtW_tWt​ be uniform on the 2d2d2d signed coordinate directions. Assume the pairs (Vt,Wt)(V_t,W_t)(Vt​,Wt​) are mutually independent across rounds and that VtV_tVt​ and WtW_tWt​ are independent within every round. The action explores in direction WtW_tWt​ when Vt<1−∥Aˉt∥2V_t<1-\lVert\bar A_t\rVert_2Vt​<1−∥Aˉt​∥2​, and otherwise plays the radial normalization of Aˉt\bar A_tAˉt​; the loss estimate is the one-point importance-weighted estimator from Eq. (28.12).

Then, for every comparator a0a_0a0​ in the Euclidean unit ball,

E ⁣[∑t<n⟨At−a0,yt⟩]≤(1−r)n+log⁡(1/(1−r))η+ηnd.\mathbb E\!\left[\sum_{t<n}\langle A_t-a_0,y_t\rangle\right] \le (1-r)n+\frac{\log(1/(1-r))}{\eta}+\eta nd.E[t<n∑​⟨At​−a0​,yt​⟩]≤(1−r)n+ηlog(1/(1−r))​+ηnd.

This parameterized form isolates the stochastic FTRL analysis from the final choice of learning rate and is reusable for alternative tuning rules.

Formalization Note The random exploration seed and signed-direction seed are represented separately. Their within-round independence is stated explicitly in addition to independence of the pairs across rounds.

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_untuned
    (d n : ℕ) (hd : 0 < d) (hn : 2 ≤ n)
    (y : ℕ → EuclideanSpace ℝ (Fin d)) (hy : ∀ t, ‖y t‖ ≤ 1)
    (η r : ℝ) (hη0 : 0 < η)
    (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 ≤
        (1 - r) * n + Real.log (1 / (1 - r)) / η + η * n * d := by
  sorry
Source
Lattimore–Szepesvári, Bandit Algorithms (2020), Theorem 28.11, printed pp. 338–339, especially Eq. (28.12), Eq. (28.14), and the final displayed untuned bound.

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