Sample complexity of Chernoff's stopping rule from a settling allocation
ProvedBanditAlgorithm.chernoff_stopping_time_sample_complexity_of_settlingIf the empirical allocation and the empirical means settle to an optimal allocation with an integrable settling time (Garivier--Kaufmann Proposition 13), then Chernoff's stopping rule with the threshold satisfies
This is the upper half of Lattimore--Szepesv'ari Theorem 33.6 for a fixed sampling rule; combined with the matching lower bound, which holds for every sound rule, it gives the limit.
Theorem 14 supplies, for each , a -free integrable time with almost surely. The passage to the statement above is bookkeeping, and it is what fixes where the of Theorem 14 must sit: an multiplying survives the limit while an additive one does not, so is divided away by and only remains. Taking makes , and the additive constant is swallowed by the remaining once is small.
The single-arm case is included rather than excluded: with there is no alternative hypothesis, is an infimum over the empty set and hence , so the rule stops at round and both clauses are trivial. This is why the statement needs no lower bound on the number of arms, matching the hypothesis under which Theorem 33.6 is stated.
import Definitions.Def_TrackAndStop import Definitions.Def_GaussianBandit open MeasureTheory ProbabilityTheory InformationTheory NNReal ENNReal Filter
theorem BanditAlgorithm.chernoff_stopping_time_sample_complexity_of_settling
{k : ℕ} [NeZero k]
(pol : BanditAlgorithm.BanditPolicy k) (μvec : Fin k → ℝ) {istar : Fin k}
(hstar : ∀ j, j ≠ istar → μvec j < μvec istar)
(α : Fin k → NNReal) (hαpos : ∀ i, 0 < α i)
(hopt : BanditAlgorithm.IsOptimalAllocation (BanditAlgorithm.gaussianBandit μvec)
(Set.range (BanditAlgorithm.gaussianBandit (k := k))) α)
(hsettle : ∀ ξ : ℝ, 0 < ξ →
(∀ᵐ ω ∂(BanditAlgorithm.banditTrajMeasure
(BanditAlgorithm.gaussianBandit μvec) pol),
∃ N : ℕ, ∀ n : ℕ, N ≤ n →
(0 < n ∧
(∀ i, |BanditAlgorithm.trajAllocation i n ω - (α i : ℝ)| ≤ ξ) ∧
(∀ i, |BanditAlgorithm.trajEmpiricalMean i n ω - μvec i| ≤ ξ))) ∧
∫⁻ ω, ((sInf {N : ℕ | ∀ n, N ≤ n →
(0 < n ∧
(∀ i, |BanditAlgorithm.trajAllocation i n ω - (α i : ℝ)| ≤ ξ) ∧
(∀ i, |BanditAlgorithm.trajEmpiricalMean i n ω - μvec i| ≤ ξ))} : ℕ) : ℝ≥0∞)
∂(BanditAlgorithm.banditTrajMeasure
(BanditAlgorithm.gaussianBandit μvec) pol) ≠ ⊤) :
(∀ δ ∈ Set.Ioo (0 : ℝ) 1,
∫⁻ ω, (BanditAlgorithm.chernoffStoppingTime (k := k) δ ω : ℝ≥0∞)
∂BanditAlgorithm.banditTrajMeasure (BanditAlgorithm.gaussianBandit μvec) pol ≠ ⊤) ∧
∀ ε : ℝ, 0 < ε →
∀ᶠ δ in nhdsWithin (0 : ℝ) (Set.Ioi 0),
(∫⁻ ω, (BanditAlgorithm.chernoffStoppingTime (k := k) δ ω : ℝ≥0∞)
∂BanditAlgorithm.banditTrajMeasure
(BanditAlgorithm.gaussianBandit μvec) pol).toReal / Real.log (1 / δ)
≤ (BanditAlgorithm.baiComplexity (BanditAlgorithm.gaussianBandit μvec)
(Set.range (BanditAlgorithm.gaussianBandit (k := k)))).toReal + ε := by
sorry