Subgaussian lower tails control reciprocal Gaussian optimism
DisprovedBanditAlgorithm.gaussian_reciprocal_posterior_tail_expectation_of_subgaussian_lower_tailgaussianprobabilitysubgaussianthompson-sampling
Let be a finite subprobability measure, let be a measurable real random variable, and suppose that for some integer and center its lower tail satisfies
For , let
There is a universal constant such that
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 BanditAlgorithmSource
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.