Lemma 33.7:
ProvedBanditAlgorithm.chernoffInverse_le_one_add_eps_mul_logLet and let be the least with , as in Lattimore--Szepesv'ari Lemma 33.7. For every and every ,
Two bounds on are already easy: the order bound , whose multiplicative constant is too lossy to keep the leading constant of Theorem 33.6 exact, and the asymptotic , which has the right constant but only holds eventually in . The sample-complexity argument needs both at once, and that is what this is: multiplicative constant , valid at every confidence level, the excess absorbed into an additive constant depending only on and .
The mechanism is the choice of tangent. The order bound estimates , the tangent to the logarithm at ; replacing it by the tangent at an arbitrary point , , makes the linear coefficient as small as desired at the cost of an additive . Taking makes the coefficient of come out to exactly .
The blow-up of the additive constant as is not an artefact: is unbounded, so no bound with and a constant can hold.
import Definitions.Def_TrackAndStop open Real
theorem BanditAlgorithm.chernoffInverse_le_one_add_eps_mul_log {k : ℕ} (hk : 0 < k)
{ε : ℝ} (hε : 0 < ε) {δ : ℝ} (hδ : 0 < δ) (hδ1 : δ ≤ 1) :
BanditAlgorithm.chernoffInverse k δ
≤ (1 + ε) * Real.log (1 / δ)
+ ((k : ℝ) + (k : ℝ) * (1 + ε) * Real.log ((1 + ε) / ε)) := by
sorry