The Chernoff inverse is a genuine threshold
ProvedBanditAlgorithm.chernoffInverse_is_thresholdbanditsbest-arm-identification
The threshold constant of Lattimore--Szepesv'ari Lemma 33.7, defined as for , is a genuine inverse: for and it satisfies , , and for every .
The last clause is the one the analysis uses -- the threshold works at every round, not just at the critical value. The content is that is continuous and strictly decreasing on with and , so the defining set is a nonempty closed up-set and its infimum is attained. Defining by an infimum rather than by inverting avoids having to produce a global inverse function.
Preamble
import Definitions.Def_TrackAndStop open MeasureTheory ProbabilityTheory NNReal ENNReal Filter Real
Formal statement
theorem BanditAlgorithm.chernoffInverse_is_threshold {k : ℕ} (hk : 0 < k) {δ : ℝ}
(hδ : 0 < δ) :
(k : ℝ) ≤ BanditAlgorithm.chernoffInverse k δ ∧
BanditAlgorithm.chernoffF k (BanditAlgorithm.chernoffInverse k δ) ≤ δ ∧
∀ x : ℝ, BanditAlgorithm.chernoffInverse k δ ≤ x →
BanditAlgorithm.chernoffF k x ≤ δ := by
sorrySource
Elementary property of f(x) = e^{k-x}(x/k)^k and its inverse, the functions introduced in Lattimore & Szepesvari, Bandit Algorithms (CUP 2020), Lemma 33.7, p. 410. The lemma uses f^{-1} without constructing it; this supplies the construction.