Chernoff's threshold is strictly positive
ProvedBanditAlgorithm.chernoffThreshold_pos_of_posbanditsbest-arm-identification
For and the threshold of Lattimore--Szepesv'ari Lemma 33.7,
is strictly positive at every round , where and is the least with .
Positivity is used twice in the analysis of Chernoff's stopping rule: it forces at the stopping time, hence a unique empirical best arm there (so the recommendation is well defined and measurable), and it makes the threshold usable as the of the self-normalised deviation bound.
Preamble
import Definitions.Def_TrackAndStop import Definitions.Def_GaussianBandit open MeasureTheory ProbabilityTheory InformationTheory NNReal ENNReal Filter
Formal statement
theorem BanditAlgorithm.chernoffThreshold_pos_of_pos {k : ℕ} (hk : 0 < k) {δ : ℝ}
(hδ : 0 < δ) (t : ℕ) :
0 < BanditAlgorithm.chernoffThreshold k δ t := by
sorrySource
Elementary property of the threshold beta_t(delta) = k log(t^2+t) + f^{-1}(delta) introduced in Lattimore & Szepesvari, Bandit Algorithms (CUP 2020), Lemma 33.7, p. 410. Positivity is not stated there; it is needed here to make Chernoff's recommendation well defined.