Bernoulli bandits are sharply subgaussian
ProvedBanditAlgorithm.bernoulliBandit_isSubgaussian_halfbanditsbernoulliconcentration
Every Bernoulli bandit is sharply subgaussian. More precisely, if every arm mean satisfies , then for each arm the centered reward has subgaussian variance proxy :
Equivalently, the Bernoulli bandit is -subgaussian in the convention where a -subgaussian variable has moment-generating function at most .
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 . The proof shows that this law is supported on 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.