Sharp lower bound on the threshold constant of Chernoff's stopping rule
ProvedBanditAlgorithm.chernoffInverse_ge_sharp_lower_boundreference
Taking logarithms in f(f^{-1}(δ)) ≤ δ, where , gives the sharp lower bound
Dropping the last term (it is nonnegative, since ) recovers the crude . The last term is what one cannot afford to drop: it grows like , and it is exactly the slack that pays for the prices incurred by a self-normalised mixture martingale run at prior variance . Without it the mixture argument fails for small no matter how the variance is tuned.
Preamble
import Definitions.Def_TrackAndStop import Definitions.Def_GaussianBandit open MeasureTheory ProbabilityTheory Real NNReal ENNReal
Formal statement
theorem BanditAlgorithm.chernoffInverse_ge_sharp_lower_bound {k : ℕ} (hk : 0 < k)
{δ : ℝ} (hδ : 0 < δ) :
(k : ℝ) + Real.log (1 / δ)
+ (k : ℝ) * Real.log (BanditAlgorithm.chernoffInverse k δ / (k : ℝ))
≤ BanditAlgorithm.chernoffInverse k δ := by
sorrySource
Elementary consequence of the defining property of f^{-1} for the function f(x) = e^{k-x}(x/k)^k of Lattimore & Szepesvari, Bandit Algorithms (CUP 2020), Lemma 33.7, p. 410. The sharp form (with the logarithmic correction retained) is what the mixture-martingale proof of the pairwise deviation bound needs.