Finite-time pull count bound for Gaussian Thompson sampling
ProvedBanditAlgorithm.gaussian_ts_suboptimal_pull_count_boundbanditsgaussianprobabilitythompson-sampling
There is a universal constant such that Gaussian Thompson sampling satisfies the following finite-time pull-count estimate. For every unit-variance Gaussian bandit, every suboptimal arm with gap , and every horizon ,
This is the gap-dependent probabilistic estimate obtained by applying the pull-count decomposition of Theorem 36.2 to Gaussian posterior tails. It implies both the instance-dependent logarithmic regret bound and, after a small-gap/large-gap split, the distribution-free bound.
Preamble
import Definitions.Def_ThompsonSampling import Definitions.Def_GaussianBandit open MeasureTheory ProbabilityTheory
Formal statement
theorem BanditAlgorithm.gaussian_ts_suboptimal_pull_count_bound :
∃ C : ℝ, 0 < C ∧
∀ (k : ℕ) [NeZero k] (μvec : Fin k → ℝ) (π : BanditPolicy k),
IsGaussianTSPolicy π →
∀ (i : Fin k), 0 < banditGap (gaussianBandit μvec) i →
∀ n : ℕ, 2 ≤ n →
∫ h, (armPullCount i h : ℝ)
∂banditMeasure (gaussianBandit μvec) π n ≤
C * (1 + Real.log n /
banditGap (gaussianBandit μvec) i ^ 2) := by
sorrySource
Lattimore and Szepesvari, Bandit Algorithms (CUP 2020), Theorem 36.3 and Exercise 36.6, printed pp. 465 and 477; derived from Theorem 36.2, Eq. (36.3), printed p.463.