The Chernoff inverse is asymptotically log(1/δ)
ProvedBanditAlgorithm.tendsto_chernoffInverse_div_logasymptoticsbanditsbest-arm-identification
The threshold constant of Lattimore--Szepesv'ari Lemma 33.7 is asymptotically : for every ,
This is the exact asymptotics that make the constant in Theorem 33.6 come out to and not a multiple of it: the sample complexity of Chernoff's rule is , so any slack in would propagate directly into the limit. The lower bound is forcing ; the upper bound is the explicit estimate fed back into that inequality, so the logarithmic correction is .
Preamble
import Definitions.Def_TrackAndStop open MeasureTheory ProbabilityTheory NNReal ENNReal Filter Real
Formal statement
theorem BanditAlgorithm.tendsto_chernoffInverse_div_log {k : ℕ} (hk : 0 < k) :
Filter.Tendsto (fun δ : ℝ ↦ BanditAlgorithm.chernoffInverse k δ / Real.log (1 / δ))
(nhdsWithin 0 (Set.Ioi 0)) (nhds 1) := by
sorrySource
Exact asymptotics f^{-1}(delta) = (1+o(1)) log(1/delta) for the threshold constant of Lattimore & Szepesvari, Bandit Algorithms (CUP 2020), Lemma 33.7, p. 410. This is what makes the constant in Theorem 33.6 come out to c*(nu) exactly.