Proved
BanditAlgorithm.summable_sq_mul_exp_neg_sqrtbanditssequential-analysis
For every ,
A sub-exponential decay absorbs any polynomial weight. The quadratic weight is the one a delayed covering argument costs: if a failure at round is covered by failures at rounds , exchanging the two sums replaces the weight by , so a first moment on one side is a second moment on the other.
The comparison is , obtained by applying at rather than at . It gives once , hence , and a fourth power leaves a convergent against the quadratic weight.
Preamble
import Definitions.Def_TrackAndStop import Mathlib.Analysis.PSeries import Mathlib.Analysis.SpecificLimits.Normed open Filter Topology
Formal statement
theorem BanditAlgorithm.summable_sq_mul_exp_neg_sqrt {c : ℝ} (hc : 0 < c) :
Summable fun m : ℕ ↦ ((m : ℝ) + 1) ^ 2 * Real.exp (-(c * Real.sqrt (m : ℝ))) := by
sorrySource
Tail estimate behind Lattimore & Szepesvari, Bandit Algorithms (CUP 2020), Theorem 33.6; used for the settling time of Garivier & Kaufmann, COLT 2016, Proposition 13.