\\limsup_{\\delta\\to0}\\mathbb{E}[\\tau_\\delta]/\\log(1/\\delta)\\le c^*(\\nu) under optimal tracking
OpenBanditAlgorithm.chernoff_stopping_time_sample_complexity(Garivier–Kaufmann Proposition 13 and Theorem 14, sample complexity of Chernoff's stopping rule under optimal tracking) Fix a unit-variance Gaussian bandit with a unique optimal arm, and a sampling rule whose empirical allocation tracks an optimal allocation: for some attaining the supremum in
almost every trajectory satisfies for every arm . Then, for Chernoff's stopping rule with the threshold of Lemma 33.7:
- for every (this is Proposition 13, a separate result — almost-sure finiteness and integrability of do not follow from the expectation bound);
- for every , eventually as , .
Clause 2 is , in -form so as to avoid the junk value a real-valued limsup takes on a function that is not bounded above.
A constant to watch. G&K's Theorem 14 is stated for thresholds with , , and concludes ; L&S's threshold has , i.e. , outside that range. The factor is an artefact of their Lemma 18, which supplies a deliberately lossy explicit solution of : the least such is , not . Since and the polynomial factor contributes only , the true asymptotics are for any polynomial — which is what L&S's proof sketch asserts. A proof of this node should therefore redo the Lemma 18 step without the inflation rather than quote Theorem 14 verbatim.
The remaining ingredients of G&K's argument are their Lemma 19 (concentration of the empirical means, from forced exploration) and Lemmas 7 and 8 (the tracking estimates). None of these is in Mathlib.
import Definitions.Def_TrackAndStop import Definitions.Def_GaussianBandit open MeasureTheory ProbabilityTheory InformationTheory NNReal ENNReal Filter
theorem BanditAlgorithm.chernoff_stopping_time_sample_complexity {k : ℕ} [NeZero k]
(π : BanditPolicy k) (ν : StochasticBandit k)
(hν : ν ∈ Set.range (gaussianBandit (k := k)))
(huniq : ∃! i, i ∈ banditOptimalArms ν) (α : Fin k → ℝ≥0)
(hα : IsOptimalAllocation ν (Set.range (gaussianBandit (k := k))) α)
(htrack : ∀ᵐ ω ∂banditTrajMeasure ν π, ∀ i : Fin k,
Tendsto (fun t : ℕ ↦ trajAllocation i t ω) atTop (nhds ((α i : ℝ)))) :
(∀ δ ∈ Set.Ioo (0 : ℝ) 1,
∫⁻ ω, (chernoffStoppingTime (k := k) δ ω : ℝ≥0∞) ∂banditTrajMeasure ν π ≠ ⊤) ∧
∀ ε : ℝ, 0 < ε →
∀ᶠ δ in nhdsWithin (0 : ℝ) (Set.Ioi 0),
(∫⁻ ω, (chernoffStoppingTime (k := k) δ ω : ℝ≥0∞) ∂banditTrajMeasure ν π).toReal /
Real.log (1 / δ)
≤ (baiComplexity ν (Set.range (gaussianBandit (k := k)))).toReal + ε := by
sorry