Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Subgaussian lower tails control reciprocal Gaussian optimism

Disproved
BanditAlgorithm.gaussian_reciprocal_posterior_tail_expectation_of_subgaussian_lower_tail

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

gaussianprobabilitysubgaussianthompson-sampling

Let PPP be a finite subprobability measure, let XXX be a measurable real random variable, and suppose that for some integer s≥1s\ge1s≥1 and center μ\muμ its lower tail satisfies

P{X≤μ−t}≤exp⁡ ⁣(−st22)(t≥0).P\{X\le\mu-t\}\le \exp\!\left(-\frac{s t^2}{2}\right) \qquad(t\ge0).P{X≤μ−t}≤exp(−2st2​)(t≥0).

For ε>0\varepsilon>0ε>0, let

G(X)=PY∼N(X,1/s){Y>μ−ε}.G(X)=\mathbb P_{Y\sim\mathcal N(X,1/s)}\{Y>\mu-\varepsilon\}.G(X)=PY∼N(X,1/s)​{Y>μ−ε}.

There is a universal constant C>0C>0C>0 such that

EP ⁣[(1G(X)−1)+]≤Csε2.\mathbb E_P\!\left[\left(\frac1{G(X)}-1\right)_+\right] \le \frac{C}{s\varepsilon^2}.EP​[(G(X)1​−1)+​]≤sε2C​.

This analytic lemma converts a sample-mean lower-tail estimate into the reciprocal posterior-optimism bound used in Gaussian Thompson sampling. It is independent of the policy or bandit construction.

Formalization Note A subprobability measure is represented by a finite measure whose total real mass is at most one; the expectation is a lintegral.

Preamble
import Mathlib.Probability.Distributions.Gaussian.Real

open MeasureTheory ProbabilityTheory ENNReal
Formal statement
namespace BanditAlgorithm

/-- A subgaussian lower tail controls the expected reciprocal Gaussian
posterior optimism probability. -/
theorem gaussian_reciprocal_posterior_tail_expectation_of_subgaussian_lower_tail :
    ∃ C : ℝ, 0 < C ∧
      ∀ {Ω : Type} [MeasurableSpace Ω] (P : Measure Ω) [IsFiniteMeasure P],
        P.real Set.univ ≤ 1 →
        ∀ (X : Ω → ℝ), Measurable X →
        ∀ μ ε : ℝ, 0 < ε →
        ∀ s : ℕ, 0 < s →
          (∀ t : ℝ, 0 ≤ t →
            P.real {ω | X ω ≤ μ - t} ≤
              Real.exp (-(s : ℝ) * t ^ 2 / 2)) →
          (∫⁻ ω, ENNReal.ofReal
              (1 /
                (gaussianReal (X ω) ((s : NNReal))⁻¹).real
                  {x | μ - ε < x} - 1) ∂P) ≤
            ENNReal.ofReal (C / ((s : ℝ) * ε ^ 2)) := by
  sorry

end BanditAlgorithm
Source
Lattimore and Szepesvári, Bandit Algorithms (CUP 2020), Gaussian-tail hint for Exercise 36.6(a), printed p. 475 / PDF p. 484, together with the subgaussian sample-mean lower tail from Chapter 5. This is the abstract tail-integration form of that calculation.

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