Chernoff bound for a Gaussian bandit at a fixed tilt
ProvedBanditAlgorithm.bandit_chernoff_boundbanditsconcentrationgaussian
The Chernoff bound for an adaptively sampled arm: for a unit-variance Gaussian bandit, an arbitrary policy, an arm , a tilt and any ,
This is Markov's inequality applied to the bandit exponential martingale, and it is the fixed-tilt building block of the self-normalised bound that Chernoff's stopping rule requires. What is worth noting is that no assumption at all is made on the sampling rule: the bound holds for every policy, at every round, because the martingale property already accounts for the adaptivity of .
Preamble
import Definitions.Def_TrackAndStop import Definitions.Def_GaussianBandit open MeasureTheory ProbabilityTheory NNReal ENNReal open scoped Classical
Formal statement
theorem BanditAlgorithm.bandit_chernoff_bound {k : ℕ} (μvec : Fin k → ℝ)
(pol : BanditAlgorithm.BanditPolicy k) (a : Fin k) (lam : ℝ) (n : ℕ) (x : ℝ) :
BanditAlgorithm.banditTrajMeasure (BanditAlgorithm.gaussianBandit μvec) pol
{ω : ℕ → Fin k × ℝ |
x ≤ lam * ((∑ s ∈ (Finset.range n).filter fun s ↦ (ω s).1 = a, (ω s).2)
- (BanditAlgorithm.trajPullCount a n ω : ℝ) * μvec a)
- lam ^ 2 * (BanditAlgorithm.trajPullCount a n ω : ℝ) / 2}
≤ ENNReal.ofReal (Real.exp (-x)) := by
sorrySource
Chernoff's bound applied to the bandit exponential martingale; standard, see Garivier & Kaufmann, COLT 2016, Section 4.