BanditAlgorithm.thompson_sampling_frequentist_regret
Provedasymptoticbanditsregretthompson-sampling
(Thompson sampling frequentist optimality, GOAL; L&S Theorem 36.3) Thompson sampling with and Gaussian updates (Algorithm 24) on any unit-variance Gaussian bandit satisfies
(a genuine limit); and there is a universal constant such that
for all and all Gaussian bandits with means in (the normalization of Theorem 36.1; as literally stated in the book the distribution-free bound fails for and for unbounded means, since the forced first pull of each arm costs ).
Preamble
import Definitions.Def_banditRegret import Definitions.Def_GaussianBandit import Definitions.Def_ThompsonSampling open MeasureTheory ProbabilityTheory Filter
Formal statement
theorem BanditAlgorithm.thompson_sampling_frequentist_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))) ∧
(∃ 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
sorry
Source
L&S Theorem 36.3, p.465