Weighted-union Chernoff bound over a family of tilts (discrete method of mixtures)
ProvedBanditAlgorithm.bandit_chernoff_unionbanditsconcentrationgaussian
The weighted-union Chernoff bound over a countable family of tilts (the discrete method of mixtures). Let be arbitrary tilts and positive weights with . Then for every ,
A fixed-tilt bound is useless when the optimal tilt depends on the realised pull count, which is random; this upgrades it to hold simultaneously over a whole family, at the price of for the -th member. It is the discrete counterpart of integrating the exponential martingale against a prior on , and needs nothing beyond a union bound. Taking and the on a geometric grid is the standard concrete instance.
Preamble
import Definitions.Def_TrackAndStop import Definitions.Def_GaussianBandit open MeasureTheory ProbabilityTheory NNReal ENNReal open scoped Classical
Formal statement
theorem BanditAlgorithm.bandit_chernoff_union {k : ℕ} (μvec : Fin k → ℝ)
(pol : BanditAlgorithm.BanditPolicy k) (a : Fin k) (n : ℕ)
(lams : ℕ → ℝ) (w : ℕ → ℝ) (hw : ∀ j, 0 < w j) (hsum : Summable w)
(hle : ∑' j, w j ≤ 1) (x : ℝ) :
BanditAlgorithm.banditTrajMeasure (BanditAlgorithm.gaussianBandit μvec) pol
{ω : ℕ → Fin k × ℝ | ∃ j : ℕ,
x + Real.log (1 / w j)
≤ lams j * ((∑ s ∈ (Finset.range n).filter fun s ↦ (ω s).1 = a, (ω s).2)
- (BanditAlgorithm.trajPullCount a n ω : ℝ) * μvec a)
- lams j ^ 2 * (BanditAlgorithm.trajPullCount a n ω : ℝ) / 2}
≤ ENNReal.ofReal (Real.exp (-x)) := by
sorrySource
The discrete method of mixtures (weighted union over a countable family of tilts); standard, see Garivier & Kaufmann, COLT 2016, Section 4, and Magureanu, Combes & Proutiere, COLT 2014.