Chernoff's stopping time is at least the time all arms are pulled
ProvedBanditAlgorithm.chernoff_stopping_time_ge_all_arms_pulledFor arms, every and every trajectory ,
where is Chernoff's stopping time and is the number of pulls of arm in the first rounds.
The reason is that the generalised-likelihood-ratio statistic
carries the factor , which vanishes as soon as either count is zero. If some arm is unplayed at round then : either that arm is one of the competitors and its own term vanishes, or it is the empirical maximiser and then every term vanishes. The threshold is strictly positive, so the rule cannot fire.
The consequence is a constraint on any bound of the form with integrable and independent of : such a bound forces the expected time to play every arm to be finite, a quantitative property of the sampling rule. Almost-sure convergence of the empirical allocation does not supply it — a rule may postpone the first pull of arm to a round that is finite almost surely but has , and still satisfy almost surely, since a finite delay does not affect a Cesaro limit. This is why the analysis of Track-and-Stop needs forced exploration and not merely tracking.
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_ge_all_arms_pulled {k : ℕ} [NeZero k]
(hk2 : 1 < k) {δ : ℝ} (hδ : 0 < δ) (ω : ℕ → Fin k × ℝ) :
((sInf {n : ℕ | ∀ i : Fin k, 0 < BanditAlgorithm.trajPullCount i n ω} : ℕ) : ℕ∞)
≤ BanditAlgorithm.chernoffStoppingTime (k := k) δ ω := by
sorry