The Gaussian mixture of an exponential tilt
ProvedBanditAlgorithm.integral_exp_tilt_mixtureanalysisconcentrationgaussian
Mixing an exponential tilt over a standard Gaussian prior on the tilt parameter produces the self-normalised weight: for and ,
This is the method of mixtures in its basic form (Kaufmann--Koolen, JMLR 2021; Garivier--Kaufmann, COLT 2016, \S4). Applied to the bandit exponential martingale with and , it converts a family of fixed-tilt martingales into a single martingale whose exponent is the self-normalised deviation -- no longer requiring a union over pull counts. The prefactors , one per arm, are the source of the polynomial factor in the threshold of Lattimore--Szepesv'ari Lemma 33.7. The computation is the Gaussian integral with a linear term at , .
Preamble
import Mathlib.Analysis.SpecialFunctions.Gaussian.GaussianIntegral open MeasureTheory Real
Formal statement
theorem BanditAlgorithm.integral_exp_tilt_mixture {t : ℝ} (ht : 0 ≤ t) (z : ℝ) :
∫ lam : ℝ, (Real.sqrt (2 * Real.pi))⁻¹ * Real.exp (-(lam ^ 2) / 2)
* Real.exp (lam * z - lam ^ 2 * t / 2)
= (Real.sqrt (1 + t))⁻¹ * Real.exp (z ^ 2 / (2 * (1 + t))) := by
sorrySource
The method of mixtures in its basic form: Robbins & Siegmund (1970); Kaufmann & Koolen, Mixture martingales revisited, JMLR 22 (2021), Section 3; Garivier & Kaufmann, COLT 2016, Section 4.