L\&S Lemma 33.7: Chernoff's stopping rule is -sound
ProvedBanditAlgorithm.chernoff_stopping_rule_sound(L&S Lemma 33.7, soundness of Chernoff's stopping rule) Fix the unit-variance Gaussian class and a confidence level . Let
and let be Chernoff's stopping rule for the generalised-likelihood-ratio statistic , with the empirically best arm at that time. Then, whatever the sampling rule , is a stopping time of the natural filtration, is -measurable, and the triple is -sound for :
is strictly decreasing on with and , so is well defined on ; crucially , so the threshold does not inflate the leading constant.
This last point is why the statement is worth isolating. The general exponential-family analogue — Garivier & Kaufmann (COLT 2016), Proposition 12 — requires in the threshold , and combining it with their Theorem 14 yields only . The Gaussian-specific Lemma 33.7 is what makes soundness at every compatible with the exact constant , and hence what makes L&S Theorem 33.6 an equality.
L&S's proof: forces , so is well defined for ; then, writing , the definition of and give the inclusion , and the choice of makes the probability of the right-hand event at most .
import Definitions.Def_TrackAndStop import Definitions.Def_GaussianBandit open MeasureTheory ProbabilityTheory InformationTheory NNReal ENNReal Filter
theorem BanditAlgorithm.chernoff_stopping_rule_sound {k : ℕ} [NeZero k]
(δ : ℝ) (hδ : δ ∈ Set.Ioo (0 : ℝ) 1) (π : BanditPolicy k) :
∃ hτ : IsBanditStoppingTime (chernoffStoppingTime (k := k) δ),
Measurable[hτ.measurableSpace] (chernoffRecommendation (k := k) δ) ∧
IsSoundBAI δ π (chernoffStoppingTime (k := k) δ)
(chernoffRecommendation (k := k) δ) (Set.range (gaussianBandit (k := k))) := by
sorry