The bandit exponential martingale has expectation one
ProvedBanditAlgorithm.bandit_exp_martingale_lintegral_eq_onebanditsconcentrationgaussianmartingale
The bandit exponential martingale has expectation one: for a unit-variance Gaussian bandit, an arbitrary policy, an arm and a tilt ,
where and is the pull count.
The pull count is random and depends on the past, so this is not the classical i.i.d.\ statement -- it is what makes the estimate usable for an adaptive sampling rule, which is exactly the situation in best-arm identification. The proof is induction on using the one-step tilt identity: at round the exponent changes only if arm is played, and then by precisely the amount whose conditional expectation is one.
Preamble
import Definitions.Def_TrackAndStop import Definitions.Def_GaussianBandit open MeasureTheory ProbabilityTheory NNReal ENNReal open scoped Classical
Formal statement
theorem BanditAlgorithm.bandit_exp_martingale_lintegral_eq_one {k : ℕ} (μvec : Fin k → ℝ)
(pol : BanditAlgorithm.BanditPolicy k) (a : Fin k) (lam : ℝ) (n : ℕ) :
∫⁻ ω, ENNReal.ofReal (Real.exp
(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))
∂(BanditAlgorithm.banditTrajMeasure (BanditAlgorithm.gaussianBandit μvec) pol) = 1 := by
sorrySource
Standard exponential martingale for an adaptively sampled arm; see Garivier & Kaufmann, COLT 2016, Section 4, and Kaufmann & Koolen, JMLR 22 (2021).