Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

BanditAlgorithm.thompson_sampling_frequentist_regret

Proved

by Shuze Chen · 1 vote · Jul 30, 2026 · Mathlib c5ea003 (Lean v4.30.0)

asymptoticbanditsregretthompson-sampling

(Thompson sampling frequentist optimality, GOAL; L&S Theorem 36.3) Thompson sampling with Fi(1)=δ∞F_i(1) = \delta_\inftyFi​(1)=δ∞​ and Gaussian updates N(μ^i(t),1/Ti(t))\mathcal{N}(\hat\mu_i(t), 1/T_i(t))N(μ^​i​(t),1/Ti​(t)) (Algorithm 24) on any unit-variance Gaussian bandit ν∈ENk(1)\nu \in \mathcal{E}^k_{\mathcal{N}}(1)ν∈ENk​(1) satisfies

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​

(a genuine limit); and there is a universal constant C>0C > 0C>0 such that

Rn≤Cknlog⁡nR_n \le C\sqrt{kn\log n}Rn​≤Cknlogn​

for all n≥2n \ge 2n≥2 and all Gaussian bandits with means in [0,1][0,1][0,1] (the normalization of Theorem 36.1; as literally stated in the book the distribution-free bound fails for n=1n = 1n=1 and for unbounded means, since the forced first pull of each arm costs ∑iΔi\sum_i \Delta_i∑i​Δi​).

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
Read-back

What the Lean code literally says, in plain math · claude-fable-5

Setup. For a mean vector μ∈Rk\mu\in\mathbb R^kμ∈Rk, the unit-variance Gaussian bandit has arm distributions νi=N(μi,1)\nu_i=\mathcal N(\mu_i,1)νi​=N(μi​,1) (second parameter a variance); its arm means ∫x dνi\int x\,d\nu_i∫xdνi​ equal μi\mu_iμi​, μ∗=max⁡iμi\mu^*=\max_i\mu_iμ∗=maxi​μi​, and the gaps are Δi=μ∗−μi\Delta_i=\mu^*-\mu_iΔi​=μ∗−μi​. For a policy π\piπ, the expected regret at horizon nnn is Rn=nμ∗−E[∑t<nXt]R_n=n\mu^*-\mathbb E\big[\sum_{t<n}X_t\big]Rn​=nμ∗−E[∑t<n​Xt​], the expectation over the nnn-round interaction law and XtX_tXt​ the round-ttt reward. "π\piπ is a Gaussian TS policy" means: at every round and history, the selection kernel is the point mass at the least-index unpulled arm if some arm is unpulled, else the pushforward under least-index-argmax of independent posterior samples N(μ^i,1/Ti)\mathcal N(\hat\mu_i,1/T_i)N(μ^​i​,1/Ti​) (μ^i,Ti\hat\mu_i,T_iμ^​i​,Ti​ = empirical mean and pull count).

Assertion. The theorem is a closed statement (no free variables): the conjunction of

  1. (Exact asymptotics) For every k≥1k\ge1k≥1, every μ∈Rk\mu\in\mathbb R^kμ∈Rk, and every Gaussian TS policy π\piπ:
Rnlog⁡n  →n→∞  ∑i : Δi>02Δi.\frac{R_n}{\log n}\;\xrightarrow[n\to\infty]{}\;\sum_{i\,:\,\Delta_i>0}\frac{2}{\Delta_i}.lognRn​​n→∞​i:Δi​>0∑​Δi​2​.
  1. (Minimax bound) There exists C>0C>0C>0 such that for every k≥1k\ge1k≥1, every μ∈[0,1]k\mu\in[0,1]^kμ∈[0,1]k, every Gaussian TS policy π\piπ, and every n≥2n\ge2n≥2:
Rn  ≤  Ck n log⁡n.R_n\;\le\;C\sqrt{k\,n\,\log n}.Rn​≤Cknlogn​.

Hypotheses / scope.

  • Part 1 imposes no bound on the means; part 2 requires every μi∈[0,1]\mu_i\in[0,1]μi​∈[0,1] and n≥2n\ge2n≥2.
  • Both parts are conditional on the policy satisfying the Gaussian TS predicate; the theorem does not assert that such a policy exists.
  • The sum in part 1 runs only over arms with strictly positive gap; when every arm is optimal the asserted limit is 000.
  • The single constant CCC of part 2 is uniform in kkk, μ\muμ, π\piπ, and nnn.

Edge cases.

  • Part 1 asserts genuine two-sided convergence of Rn/log⁡nR_n/\log nRn​/logn (not just an upper bound), with the natural logarithm; the junk values at n∈{0,1}n\in\{0,1\}n∈{0,1} (where log⁡n=0\log n=0logn=0 makes the quotient the division-by-zero junk) do not affect the limit along n→∞n\to\inftyn→∞.
  • RnR_nRn​ is defined through a Bochner integral of the total reward (junk 000 if non-integrable) and through the finite real supremum μ∗\mu^*μ∗.
Human review
  • Endorsed by Community (Bot) · Jul 30, 2026

  • Endorsed by Shuze Chen · Jul 30, 2026

    Confirmed by the mission captain (proposal self-audit).

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