Chernoff's stopping time integrable time linear in
ProvedBanditAlgorithm.chernoff_stopping_time_le_integrable_plus_linear_of_settling_timeFix a Gaussian bandit with a unique best arm and at least two arms, and an optimal allocation (a maximiser in Eq. (33.4)) with all weights strictly positive. Write
for the round from which the empirical allocation and the empirical means have settled to within . Assume that for every the sampling rule settles almost surely and — this is exactly the conclusion of Garivier & Kaufmann's Proposition 13. Then for every there is a random time , not depending on , with and
Three multiplicative losses are incurred and no more, each of size with , so that . First, the slope of the line the statistic must exceed is taken at rather than , because the settling window has to be strictly positive and the pair rates degrade continuously in . Second, the threshold constant obeys . Third, the crossing round is rather than , the extra -share of the line paying for the logarithmic term . Every remaining cost is additive and free of , hence joins .
The integrability hypothesis is not removable and not implied by almost-sure tracking. Chernoff's rule cannot fire while some arm is unplayed, so a bound of the stated shape forces the expected time to play every arm to be finite; a rule that postpones the first pull of arm to a round with almost surely but still has almost surely, and for it the conclusion fails. The quantitative input --- here , in Garivier & Kaufmann the forced exploration of D-Tracking --- is doing real work.
import Definitions.Def_TrackAndStop import Definitions.Def_GaussianBandit import Mathlib.MeasureTheory.Measure.Prod open MeasureTheory ProbabilityTheory Real NNReal ENNReal Filter Topology
theorem BanditAlgorithm.chernoff_stopping_time_le_integrable_plus_linear_of_settling_time
{k : ℕ} [NeZero k] (pol : BanditAlgorithm.BanditPolicy k) (μvec : Fin k → ℝ)
{istar : Fin k} (hstar : ∀ j, j ≠ istar → μvec j < μvec istar)
(hk2 : ∃ j : Fin k, j ≠ 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) ≠ ⊤)
{ε : ℝ} (hε : 0 < ε) :
∃ W : (ℕ → Fin k × ℝ) → ℕ,
(∫⁻ ω, (W ω : ℝ≥0∞)
∂(BanditAlgorithm.banditTrajMeasure (BanditAlgorithm.gaussianBandit μvec) pol) ≠ ⊤) ∧
∀ δ ∈ Set.Ioo (0 : ℝ) 1,
∀ᵐ ω ∂(BanditAlgorithm.banditTrajMeasure
(BanditAlgorithm.gaussianBandit μvec) pol),
BanditAlgorithm.chernoffStoppingTime (k := k) δ ω
≤ ((W ω : ℕ∞) + ((⌈(1 + ε)
* (BanditAlgorithm.baiComplexity (BanditAlgorithm.gaussianBandit μvec)
(Set.range (BanditAlgorithm.gaussianBandit (k := k)))).toReal
* Real.log (1 / δ)⌉₊ : ℕ) : ℕ∞)) := by
sorry