The oldest bandit algorithm (Thompson, 1933) is also the most modern: sample a parameter from the posterior and act greedily. Chapters 34–36 of Lattimore–Szepesvári develop the Bayesian view in two crowning results. The Gittins index theorem: for infinite-horizon discounted Markov bandits, the seemingly intractable dynamic program is solved exactly by an index policy — each arm gets a retirement-value index computable arm-by-arm, and playing the largest index is Bayesian optimal. And the frequentist analysis of Thompson sampling — the goal theorem: with Gaussian posteriors, Thompson sampling on 1-subgaussian bandits achieves , exactly asymptotically optimal, alongside the minimax-grade . Together they explain why posterior sampling is both principled and practically dominant.
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
(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 ).
No open leaves. Every sub-goal is proved or awaiting decomposition.