Gaussian Thompson Sampling has asymptotically optimal logarithmic regret
ProvedBanditAlgorithm.thompson_sampling_gaussian_asymptotic_regretasymptotic-regretbanditsgaussian-banditsthompson-sampling
Consider Thompson sampling with the Gaussian update rule of Algorithm 24 on a -armed unit-variance Gaussian bandit with mean vector . Let be the gap of arm , and let denote expected cumulative regret. Then
Thus Gaussian Thompson sampling attains the Lai–Robbins instance-dependent asymptotic constant, with a genuine limit rather than only a limsup. The statement allows arbitrary real means because translating all Gaussian means does not change the gaps or the algorithm's regret.
Formalization Note The policy is characterized extensionally by IsGaussianTSPolicy, including the forced initial pulls induced by the point mass at positive infinity.
Preamble
import Definitions.Def_ThompsonSampling import Definitions.Def_GaussianBandit import Definitions.Def_banditRegret open MeasureTheory ProbabilityTheory Filter
Formal statement
theorem BanditAlgorithm.thompson_sampling_gaussian_asymptotic_regret :
∀ (k : ℕ) [NeZero k] (μvec : Fin k → ℝ) (π : BanditPolicy k),
IsGaussianTSPolicy π →
Tendsto (fun n : ℕ ↦ banditRegret (gaussianBandit μvec) π n / Real.log n)
atTop
(nhds (∑ i ∈ Finset.univ.filter
(fun i ↦ 0 < banditGap (gaussianBandit μvec) i),
2 / banditGap (gaussianBandit μvec) i)) := by
sorrySource
Lattimore and Szepesvári, Bandit Algorithms (CUP 2020), Theorem 36.3, Eq. (36.6), printed p. 465; based on the pull-count decomposition in Theorem 36.2, printed p. 463.