Explicit O(k + log(1/δ)) bound on the Chernoff inverse
ProvedBanditAlgorithm.chernoffInverse_le_explicitbanditsbest-arm-identification
An explicit upper bound on the threshold constant of Lattimore--Szepesv'ari Lemma 33.7: for and ,
where .
Lemma 33.7 supplies only implicitly, but the sample-complexity half of Theorem 33.6 needs it to grow like and no faster. The proof bounds using in the form -- a linear majorant with slope -- so that .
Preamble
import Definitions.Def_TrackAndStop open MeasureTheory ProbabilityTheory NNReal ENNReal Filter Real
Formal statement
theorem BanditAlgorithm.chernoffInverse_le_explicit {k : ℕ} (hk : 0 < k) {δ : ℝ}
(hδ : 0 < δ) (hδ1 : δ ≤ 1) :
BanditAlgorithm.chernoffInverse k δ
≤ ((k : ℝ) + Real.log (1 / δ)) / (1 - (Real.exp 1)⁻¹) := by
sorrySource
Explicit upper bound on the threshold constant f^{-1}(delta) of Lattimore & Szepesvari, Bandit Algorithms (CUP 2020), Lemma 33.7, p. 410. The O(log(1/delta)) growth is used in the sample-complexity half of Theorem 33.6, not in Lemma 33.7 itself.