Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Uniform bound for the optimal-arm reciprocal posterior-tail sum

Proved
BanditAlgorithm.gaussian_ts_optimal_exact_rank_reciprocal_tail_sum_uniform

by Harry_Xu · Jul 31, 2026 · Mathlib c5ea003 (Lean v4.30.0)

asymptoticsbanditsgaussianthompson-sampling

Let i0i_0i0​ be an optimal arm in a unit-variance Gaussian bandit, and fix an offset ε>0\varepsilon>0ε>0. For every adaptive policy and every horizon nnn, consider the sum over the realized pull ranks s<Ti0(n)s<T_{i_0}(n)s<Ti0​​(n) of the reciprocal posterior-tail penalty

1P(θi0,s>μi0−ε∣H)−1.\frac{1}{\mathbb P(\theta_{i_0,s}>\mu_{i_0}-\varepsilon\mid\mathcal H)}-1.P(θi0​,s​>μi0​​−ε∣H)1​−1.

There is a universal constant C>0C>0C>0 such that the expectation of this sum is bounded uniformly in nnn by

2eε2/8ε2/8+2Cε2 e3ε2/323ε2/32.\frac{2e^{\varepsilon^2/8}}{\varepsilon^2/8} +\frac{2C}{\varepsilon^2}\, \frac{e^{3\varepsilon^2/32}}{3\varepsilon^2/32}.ε2/82eε2/8​+ε22C​3ε2/32e3ε2/32​.

In particular, the optimal-arm reciprocal-tail contribution is Oε(1)O_{\varepsilon}(1)Oε​(1) rather than logarithmic in the horizon. This is the finite-horizon form of the summability assertion used in Exercise 36.6(a).

Formalization Note The Lean integral includes exactly the ranks realized before time nnn; the displayed constant is an explicit finite envelope obtained from the exact-rank exponential estimate.

Preamble
import Definitions.Def_ThompsonSampling
import Definitions.Def_GaussianBandit
import Mathlib.Analysis.SumIntegralExpDecay

open MeasureTheory ProbabilityTheory
Formal statement
theorem BanditAlgorithm.gaussian_ts_optimal_exact_rank_reciprocal_tail_sum_uniform :
    ∃ C : ℝ, 0 < C ∧
      ∀ (k : ℕ) [NeZero k] (μvec : Fin k → ℝ) (π : BanditAlgorithm.BanditPolicy k),
        ∀ (i₀ : Fin k),
          BanditAlgorithm.banditArmMean (BanditAlgorithm.gaussianBandit μvec) i₀ =
            BanditAlgorithm.banditOptimalMean (BanditAlgorithm.gaussianBandit μvec) →
        ∀ ε : ℝ, 0 < ε →
        ∀ n : ℕ,
          (∫⁻ h, ∑ s ∈ Finset.range (BanditAlgorithm.armPullCount i₀ h),
              ENNReal.ofReal
                (1 / BanditAlgorithm.gaussianTSTailProb i₀ s
                  (BanditAlgorithm.banditArmMean (BanditAlgorithm.gaussianBandit μvec) i₀ - ε) h - 1)
              ∂BanditAlgorithm.banditMeasure (BanditAlgorithm.gaussianBandit μvec) π n) ≤
            ENNReal.ofReal
              (2 * Real.exp (ε ^ 2 / 8) / (ε ^ 2 / 8) +
                (2 * C / ε ^ 2) *
                  (Real.exp (3 * ε ^ 2 / 32) / (3 * ε ^ 2 / 32))) := by sorry
Source
Lattimore and Szepesvári, Bandit Algorithms, Cambridge University Press, 2020, Chapter 36, Exercise 36.6(a), printed p. 475 (PDF p. 484), together with the Gaussian posterior calculation in the solution outline.

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