Time-uniform deviation bound for a bandit's empirical means
ProvedBanditAlgorithm.bandit_mean_deviation_time_uniformbanditssequential-analysis
For every arm and every , under any sampling rule,
Equivalently, with probability at least the empirical mean of arm is within of the truth at every round at which the arm has been played.
Uniformity in the round is the point. The number of pulls is itself random and adapted, so a fixed-sample Chernoff bound cannot simply be evaluated at it, and a union bound over rounds costs a factor growing with the horizon. The route is the method of mixtures: average the exponential martingales over a Gaussian prior on the tilt , giving a nonnegative supermartingale in closed form, and apply Ville's maximal inequality to it. The price of the mixture is exactly the term.
Preamble
import Definitions.Def_TrackAndStop import Definitions.Def_GaussianBandit open MeasureTheory ProbabilityTheory InformationTheory NNReal ENNReal Filter
Formal statement
theorem BanditAlgorithm.bandit_mean_deviation_time_uniform {k : ℕ} [NeZero k]
(μvec : Fin k → ℝ) (pol : BanditAlgorithm.BanditPolicy k) (a : Fin k) {δ : ℝ}
(hδ : 0 < δ) (hδ1 : δ ≤ 1) :
BanditAlgorithm.banditTrajMeasure (BanditAlgorithm.gaussianBandit μvec) pol
{ω : ℕ → Fin k × ℝ | ∃ n : ℕ, 1 ≤ BanditAlgorithm.trajPullCount a n ω ∧
4 * (Real.log (1 / δ)
+ Real.log (1 + (BanditAlgorithm.trajPullCount a n ω : ℝ)) / 2)
/ (BanditAlgorithm.trajPullCount a n ω : ℝ)
< (BanditAlgorithm.trajEmpiricalMean a n ω - μvec a) ^ 2}
≤ ENNReal.ofReal δ := by
sorrySource
Method of mixtures: Robbins & Siegmund 1970; de la Pena, Klass & Lai, Ann. Probab. 32 (2004); Kaufmann & Koolen, JMLR 22 (2021). Used for the empirical-mean half of Proposition 13 in Garivier & Kaufmann, COLT 2016.