Distribution-free regret bound for Gaussian Thompson Sampling
ProvedBanditAlgorithm.thompson_sampling_gaussian_minimax_regretbanditsgaussian-banditsminimax-regretthompson-sampling
There is a universal constant such that Gaussian Thompson sampling on every -armed unit-variance Gaussian bandit with means in satisfies, for every horizon ,
This is the distribution-free companion to the instance-dependent logarithmic asymptotic bound. The normalization of the means controls the regret of the algorithm's forced initialization, while the lower bound avoids the degenerate logarithmic right-hand side at horizon one.
Formalization Note The existential constant is uniform over the number of arms, the normalized mean vector, the policy implementation satisfying IsGaussianTSPolicy, and the horizon.
Preamble
import Definitions.Def_ThompsonSampling import Definitions.Def_GaussianBandit import Definitions.Def_banditRegret open MeasureTheory ProbabilityTheory
Formal statement
theorem BanditAlgorithm.thompson_sampling_gaussian_minimax_regret :
∃ C : ℝ, 0 < C ∧
∀ (k : ℕ) [NeZero k] (μvec : Fin k → ℝ) (π : BanditPolicy k),
IsGaussianTSPolicy π → (∀ i, μvec i ∈ Set.Icc (0 : ℝ) 1) →
∀ n : ℕ, 2 ≤ n →
banditRegret (gaussianBandit μvec) π n ≤
C * Real.sqrt (k * n * Real.log n) := by
sorrySource
Lattimore and Szepesvári, Bandit Algorithms (CUP 2020), Theorem 36.3, distribution-free bound in Eq. (36.6), printed p. 465, with the bounded-mean normalization of Theorem 36.1, printed p. 459.