Time-uniform self-normalised deviation bound for a pair of arms
ProvedBanditAlgorithm.bandit_pair_selfnormalised_time_uniform_deviationThe time-uniform self-normalised deviation bound for a fixed pair of arms. For a unit-variance Gaussian bandit, an arbitrary sampling rule, two distinct arms and any ,
where is the centred reward sum.
Two features distinguish this from a fixed-round Chernoff estimate. It is uniform over all rounds at once — there is no union over , hence no factor growing with the horizon, which is exactly what the threshold of Lattimore--Szepesv'ari Lemma 33.7 requires. And it is uniform over the realised pull counts, which enter only through the explicit price ; that is the self-normalisation.
The proof mixes the vector exponential martingale over a standard Gaussian prior on the tilt in the two coordinates and , which by the planar mixture formula produces the weight , and applies Ville's maximal inequality to it at level . The cost of doing without a union over rounds is the shift in the denominators, the trace left by the unit variance of the prior.
import Definitions.Def_TrackAndStop import Definitions.Def_GaussianBandit import Mathlib.MeasureTheory.Measure.Prod open MeasureTheory ProbabilityTheory Real NNReal ENNReal
theorem BanditAlgorithm.bandit_pair_selfnormalised_time_uniform_deviation {k : ℕ}
(μvec : Fin k → ℝ) (pol : BanditAlgorithm.BanditPolicy k) {a b : Fin k} (hab : a ≠ b)
{δ : ℝ} (hδ : 0 < δ) :
BanditAlgorithm.banditTrajMeasure (BanditAlgorithm.gaussianBandit μvec) pol
{ω : ℕ → Fin k × ℝ | ∃ n : ℕ,
Real.log (1 / δ)
+ Real.log (1 + (BanditAlgorithm.trajPullCount a n ω : ℝ)) / 2
+ Real.log (1 + (BanditAlgorithm.trajPullCount b n ω : ℝ)) / 2
≤ ((∑ s ∈ (Finset.range n).filter fun s ↦ (ω s).1 = a, (ω s).2)
- (BanditAlgorithm.trajPullCount a n ω : ℝ) * μvec a) ^ 2
/ (2 * (1 + (BanditAlgorithm.trajPullCount a n ω : ℝ)))
+ ((∑ s ∈ (Finset.range n).filter fun s ↦ (ω s).1 = b, (ω s).2)
- (BanditAlgorithm.trajPullCount b n ω : ℝ) * μvec b) ^ 2
/ (2 * (1 + (BanditAlgorithm.trajPullCount b n ω : ℝ)))}
≤ ENNReal.ofReal δ := by
sorry