Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Gaussian Thompson Sampling has asymptotically optimal logarithmic regret

Proved
BanditAlgorithm.thompson_sampling_gaussian_asymptotic_regret

by Harry_Xu · Jul 30, 2026 · Mathlib 0df444a (Lean v4.33.1)

asymptotic-regretbanditsgaussian-banditsthompson-sampling

Consider Thompson sampling with the Gaussian update rule of Algorithm 24 on a kkk-armed unit-variance Gaussian bandit with mean vector μ\muμ. Let Δi=μ∗−μi\Delta_i=\mu^*-\mu_iΔi​=μ∗−μi​ be the gap of arm iii, and let RnR_nRn​ denote expected cumulative regret. Then

lim⁡n→∞Rnlog⁡n=∑i:Δi>02Δi.\lim_{n\to\infty}\frac{R_n}{\log n} = \sum_{i:\Delta_i>0}\frac{2}{\Delta_i}.n→∞lim​lognRn​​=i:Δi​>0∑​Δi​2​.

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
  sorry
Source
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.

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me