The vector-tilt exponential martingale has expectation one
ProvedBanditAlgorithm.bandit_vector_exp_martingalebanditsconcentrationgaussianmartingale
The vector-tilt exponential martingale has expectation one: for a unit-variance Gaussian bandit, an arbitrary policy and an arbitrary tilt vector ,
Tilting every arm simultaneously, each by its own parameter, costs no more than tilting one: the one-round integral is whichever arm is played.
This is the object the threshold of Lemma 33.7 actually needs. That threshold is , and its polynomial factor arises precisely from a -dimensional mixture over the tilt vector -- integrating this martingale against a Gaussian prior on produces one factor per arm. A one-dimensional, per-arm bound cannot produce it: unioning the per-arm estimate over rounds gives a bound that diverges for .
Preamble
import Definitions.Def_TrackAndStop import Definitions.Def_GaussianBandit open MeasureTheory ProbabilityTheory NNReal ENNReal open scoped Classical
Formal statement
theorem BanditAlgorithm.bandit_vector_exp_martingale {k : ℕ} (μvec : Fin k → ℝ)
(pol : BanditAlgorithm.BanditPolicy k) (lams : Fin k → ℝ) (n : ℕ) :
∫⁻ ω, ENNReal.ofReal (Real.exp (∑ i : Fin k,
(lams i * ((∑ s ∈ (Finset.range n).filter fun s ↦ (ω s).1 = i, (ω s).2)
- (BanditAlgorithm.trajPullCount i n ω : ℝ) * μvec i)
- (lams i) ^ 2 * (BanditAlgorithm.trajPullCount i n ω : ℝ) / 2)))
∂(BanditAlgorithm.banditTrajMeasure (BanditAlgorithm.gaussianBandit μvec) pol) = 1 := by
sorrySource
Standard multivariate exponential-martingale construction; see Garivier & Kaufmann, COLT 2016, Section 4, and Kaufmann & Koolen, JMLR 22 (2021), Section 3.