Track-and-Stop stops after an integrable time plus (1+ε)c*(ν)log(1/δ)
OpenBanditAlgorithm.chernoff_stopping_time_le_integrable_plus_linearThe probabilistic content of the sample-complexity half of Lattimore-Szepesvari Theorem 33.6, in one statement. For a unit-variance Gaussian bandit with a unique best arm, a sampling rule whose empirical allocation converges almost surely to an optimal allocation, and any eps > 0, there is a random round W with finite expectation such that, simultaneously for every confidence level delta in (0,1), Chernoff's stopping time satisfies tau_delta <= W + ceil((1+eps) c*(nu) log(1/delta)) almost surely. This is Garivier-Kaufmann Proposition 13 -- W is the round after which the empirical allocation and the empirical means are eps-accurate, and its integrability is what the forced exploration of D-Tracking buys -- combined with the deterministic crossing-time computation of their Theorem 14, which uses that the Gaussian threshold satisfies f^{-1}(delta) = (1 + o(1)) log(1/delta). Everything downstream of this bound is real analysis: dividing by log(1/delta) kills the E[W] term and leaves (1+eps) c*(nu).
import Definitions.Def_TrackAndStop import Definitions.Def_GaussianBandit open MeasureTheory ProbabilityTheory InformationTheory NNReal ENNReal Filter
theorem BanditAlgorithm.chernoff_stopping_time_le_integrable_plus_linear {k : ℕ} [NeZero k]
(pol : BanditAlgorithm.BanditPolicy k) (ν : BanditAlgorithm.StochasticBandit k)
(hν : ν ∈ Set.range (BanditAlgorithm.gaussianBandit (k := k)))
(huniq : ∃! i, i ∈ BanditAlgorithm.banditOptimalArms ν)
(α : Fin k → NNReal)
(hα : BanditAlgorithm.IsOptimalAllocation ν
(Set.range (BanditAlgorithm.gaussianBandit (k := k))) α)
(htrack : ∀ᵐ ω ∂BanditAlgorithm.banditTrajMeasure ν pol, ∀ i : Fin k,
Filter.Tendsto (fun t : ℕ ↦ BanditAlgorithm.trajAllocation i t ω) Filter.atTop
(nhds ((α i : ℝ))))
(ε : ℝ) (hε : 0 < ε) :
∃ W : (ℕ → Fin k × ℝ) → ℕ,
(∫⁻ ω, (W ω : ℝ≥0∞) ∂BanditAlgorithm.banditTrajMeasure ν pol) ≠ ⊤ ∧
∀ δ ∈ Set.Ioo (0 : ℝ) 1,
∀ᵐ ω ∂BanditAlgorithm.banditTrajMeasure ν pol,
BanditAlgorithm.chernoffStoppingTime (k := k) δ ω
≤ ((W ω : ℕ∞) + ((⌈(1 + ε)
* (BanditAlgorithm.baiComplexity ν
(Set.range (BanditAlgorithm.gaussianBandit (k := k)))).toReal
* Real.log (1 / δ)⌉₊ : ℕ) : ℕ∞)) := by
sorry