Gaussian TS: eventual lower half of the armwise asymptotic
ProvedBanditAlgorithm.gaussian_ts_suboptimal_pull_count_eventual_lowerasymptoticsbanditsgaussianthompson-sampling
Fix a suboptimal arm of gap under Gaussian Thompson sampling. For every real number , all sufficiently large horizons satisfy
Equivalently, the lower asymptotic envelope of the normalized expected pull count is at least . This is the armwise change-of-measure (Lai--Robbins) half of the proof of Theorem 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_lower
{k : ℕ} [NeZero k] (μvec : Fin k → ℝ) (π : BanditAlgorithm.BanditPolicy k)
(hπ : BanditAlgorithm.IsGaussianTSPolicy π) (i : Fin k)
(hi : 0 < BanditAlgorithm.banditGap (BanditAlgorithm.gaussianBandit μvec) i) :
∀ a : ℝ, a < 2 / BanditAlgorithm.banditGap (BanditAlgorithm.gaussianBandit μvec) i ^ 2 →
∀ᶠ n : ℕ in Filter.atTop,
a <
(∫ h, (BanditAlgorithm.armPullCount i h : ℝ)
∂BanditAlgorithm.banditMeasure (BanditAlgorithm.gaussianBandit μvec) π n) /
Real.log n := by sorrySource
Lattimore and Szepesvári, Bandit Algorithms (CUP 2020), Theorem 36.3 and Exercise 36.6(c), printed pp. 465 and 475 / PDF pp. 474 and 484; the lower half uses the fundamental asymptotic change-of-measure lower bound of Chapter 16.