BanditAlgorithm.bandit_adaptive_stopped_centered_sum_tail
Provedbanditsconcentrationprobability
Fix an arm in a -subgaussian stochastic bandit, an arbitrary possibly randomized policy , a horizon , and a pull cap . Let
be the centered reward accumulated only over the first pulls of arm . For every ,
This is the canonical-history formulation of the reward-stack and bounded optional-stopping concentration argument.
Preamble
import Definitions.Def_ucbStoppedCenteredSum import Mathlib.Data.Fintype.Order import Mathlib.Probability.Kernel.Composition.IntegralCompProd open MeasureTheory ProbabilityTheory
Formal statement
theorem BanditAlgorithm.bandit_adaptive_stopped_centered_sum_tail
{k n : ℕ} (ν : BanditAlgorithm.StochasticBandit k)
(hν : BanditAlgorithm.IsSubgaussianBandit 1 ν)
{π : BanditAlgorithm.BanditPolicy k}
(i : Fin k) (u : ℕ) {t : ℝ} (ht : 0 ≤ t) :
(BanditAlgorithm.banditMeasure ν π n).real
{h : BanditAlgorithm.BanditHistory k n |
(u : ℝ) * t ≤
BanditAlgorithm.armStoppedCenteredSum ν i u n h} ≤
Real.exp (-(u : ℝ) * t ^ 2 / 2) ∧
(BanditAlgorithm.banditMeasure ν π n).real
{h : BanditAlgorithm.BanditHistory k n |
BanditAlgorithm.armStoppedCenteredSum ν i u n h ≤
-(u : ℝ) * t} ≤
Real.exp (-(u : ℝ) * t ^ 2 / 2) := by
sorrySource
Lattimore and Szepesvári, Bandit Algorithms (CUP 2020), reward-stack model in §4.6, printed p. 65 / PDF p. 74, and Exercise 4.4, printed p. 69 / PDF p. 78; the same stopped centered-reward argument is used in Theorem 7.1, Eqs. (7.7)–(7.10), printed pp. 106–108 / PDF pp. 115–117, and in Theorem 8.1, Eq. (8.4), printed pp. 119–120 / PDF pp. 128–129.