Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Sharp adaptive stopped-sum Hoeffding bound

Proved
BanditAlgorithm.bandit_adaptive_stopped_centered_sum_tail_half

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

banditsconcentrationhoeffding

Let a stochastic bandit be 1/21/21/2-subgaussian, let a possibly randomized adaptive policy interact with it for nnn rounds, and fix an arm iii. Stop the centered reward sum for that arm after its first uuu observations. For every t≥0t\ge0t≥0, both tails obey the sharp Hoeffding estimate

P ⁣(Si,u≥ut)≤e−2ut2,P ⁣(Si,u≤−ut)≤e−2ut2.\mathbb P\!\left(S_{i,u}\ge ut\right) \le e^{-2ut^2}, \qquad \mathbb P\!\left(S_{i,u}\le-ut\right) \le e^{-2ut^2}.P(Si,u​≥ut)≤e−2ut2,P(Si,u​≤−ut)≤e−2ut2.

The result remains valid even when fewer than uuu observations of the arm have occurred by the horizon; the stopped sum then uses all observations that are available.

This is the adaptive reward-stack concentration bridge needed to apply ordinary Bernoulli Hoeffding estimates at a random arm-pull count.

Formalization Note: armStoppedCenteredSum is constructed directly from the finite interaction history. The Lean proof builds the exponential supermartingale with compensator λ2/8\lambda^2/8λ2/8 at every selected reward, integrates it through the policy and reward kernels, and applies Chernoff's method with λ=4t\lambda=4tλ=4t.

Preamble
import Definitions.Def_ucbStoppedCenteredSum
import Mathlib.Data.Fintype.Order
import Mathlib.Probability.Kernel.Composition.IntegralCompProd

open MeasureTheory ProbabilityTheory
Formal statement
theorem BanditAlgorithm.bandit_adaptive_stopped_centered_sum_tail_half
    {k n : ℕ} (ν : BanditAlgorithm.StochasticBandit k)
    (hν : BanditAlgorithm.IsSubgaussianBandit (1 / 2) ν)
    {π : BanditAlgorithm.BanditPolicy k}
    (i : Fin k) (u : ℕ) {t : ℝ} (ht : 0 ≤ t) :
    (BanditAlgorithm.banditMeasure ν π n).real
        {h : BanditAlgorithm.BanditHistory k n |
          (u : ℝ) * t ≤
            BanditAlgorithm.armStoppedCenteredSum ν i u n h} ≤
        Real.exp (-2 * (u : ℝ) * t ^ 2) ∧
      (BanditAlgorithm.banditMeasure ν π n).real
        {h : BanditAlgorithm.BanditHistory k n |
          BanditAlgorithm.armStoppedCenteredSum ν i u n h ≤
            -(u : ℝ) * t} ≤
        Real.exp (-2 * (u : ℝ) * t ^ 2) := by
  sorry
Source
Lattimore and Szepesvári, Bandit Algorithms (2020), reward-stack construction in Section 4.6 and Hoeffding concentration used in Chapters 8 and 10.

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