Gaussian TS: eventual upper half of the armwise asymptotic
ProvedBanditAlgorithm.gaussian_ts_suboptimal_pull_count_eventual_upperasymptoticsbanditsgaussianthompson-sampling
Fix a suboptimal arm of gap under Gaussian Thompson sampling. For every real number , all sufficiently large horizons satisfy
Equivalently, the upper asymptotic envelope of the normalized expected pull count is at most . This is the posterior-tail calculation in Exercise 36.6(a,b), combined with the pull-count decomposition (36.3).
Preamble
import Definitions.Def_ThompsonSampling import Definitions.Def_GaussianBandit open MeasureTheory ProbabilityTheory Filter
Formal statement
theorem BanditAlgorithm.gaussian_ts_suboptimal_pull_count_eventual_upper
{k : ℕ} [NeZero k] (μvec : Fin k → ℝ) (π : BanditAlgorithm.BanditPolicy k)
(hπ : BanditAlgorithm.IsGaussianTSPolicy π) (i : Fin k)
(hi : 0 < BanditAlgorithm.banditGap (BanditAlgorithm.gaussianBandit μvec) i) :
∀ b : ℝ, 2 / BanditAlgorithm.banditGap (BanditAlgorithm.gaussianBandit μvec) i ^ 2 < b →
∀ᶠ n : ℕ in Filter.atTop,
(∫ h, (BanditAlgorithm.armPullCount i h : ℝ)
∂BanditAlgorithm.banditMeasure (BanditAlgorithm.gaussianBandit μvec) π n) /
Real.log n < b := by sorrySource
Lattimore and Szepesvári, Bandit Algorithms (CUP 2020), Theorem 36.2, Eq. (36.3), printed pp. 463–465 / PDF pp. 472–474, and Exercise 36.6(a,b), printed p. 475 / PDF p. 484.