Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Bernoulli bandits are sharply subgaussian

Proved
BanditAlgorithm.bernoulliBandit_isSubgaussian_half

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

banditsbernoulliconcentration

Every Bernoulli bandit is sharply subgaussian. More precisely, if every arm mean satisfies μi∈[0,1]\mu_i\in[0,1]μi​∈[0,1], then for each arm the centered reward X−μiX-\mu_iX−μi​ has subgaussian variance proxy 1/41/41/4:

E ⁣[exp⁡ ⁣(λ(X−μi))]≤exp⁡ ⁣(λ28)(λ∈R).\mathbb E\!\left[\exp\!\left(\lambda(X-\mu_i)\right)\right] \le \exp\!\left(\frac{\lambda^2}{8}\right) \qquad(\lambda\in\mathbb R).E[exp(λ(X−μi​))]≤exp(8λ2​)(λ∈R).

Equivalently, the Bernoulli bandit is 1/21/21/2-subgaussian in the convention where a σ\sigmaσ-subgaussian variable has moment-generating function at most exp⁡(σ2λ2/2)\exp(\sigma^2\lambda^2/2)exp(σ2λ2/2).

This supplies the sharp Hoeffding constant used in the finite-time KL-UCB concentration estimates.

Formalization Note: The Bernoulli reward law is represented as the two-point measure μiδ1+(1−μi)δ0\mu_i\delta_1+(1-\mu_i)\delta_0μi​δ1​+(1−μi​)δ0​. The proof shows that this law is supported on [0,1][0,1][0,1] and applies Mathlib's bounded-variable form of Hoeffding's lemma.

Preamble
import Definitions.Def_bernoulliRelativeEntropy

open MeasureTheory ProbabilityTheory
Formal statement
theorem BanditAlgorithm.bernoulliBandit_isSubgaussian_half
    {k : ℕ} (μvec : Fin k → ℝ)
    (hμ : ∀ i, μvec i ∈ Set.Icc (0 : ℝ) 1) :
    BanditAlgorithm.IsSubgaussianBandit (1 / 2)
      (BanditAlgorithm.bernoulliBandit μvec hμ) := by
  sorry
Source
Hoeffding's lemma; applied to the Bernoulli bandit model of Lattimore and Szepesvári, Bandit Algorithms (2020), Chapter 10, printed pp. 133–134.

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