Sharp exponential-sum bound for the UCB counting lemma
ProvedBanditAlgorithm.bandit_ucb_index_exponential_sum_bound_sharpanalysisbanditsconcentrationucb
For , , and , assign weight to each and weight
to each later . The sum of these weights for is at most . This is the sharp, no-extra- integral comparison used in Lemma 8.2.
Preamble
import Mathlib.Probability.Moments.SubGaussian import Mathlib.Analysis.SpecialFunctions.Trigonometric.Basic open MeasureTheory ProbabilityTheory Real
Formal statement
theorem BanditAlgorithm.bandit_ucb_index_exponential_sum_bound_sharp
{n : ℕ} {ε a : ℝ} (hε : 0 < ε) (ha : 0 < a) :
Finset.sum (Finset.Icc 1 n) (fun t ↦
if 2 * a / ε ^ 2 < (t : ℝ) then
Real.exp (-((t : ℝ) * (ε - Real.sqrt (2 * a / t))) ^ 2 / ((2 : ℝ) * (t : ℝ) * (1 : ℝ)))
else 1) ≤
2 / ε ^ 2 * (a + Real.sqrt (Real.pi * a) + 1) := by sorrySource
Lattimore and Szepesvári, Bandit Algorithms (Cambridge University Press, 2020), Lemma 8.2 and its proof, printed pp. 118–119 / PDF pp. 127–128, https://tor-lattimore.com/downloads/book/book.pdf