Split envelope for reciprocal Gaussian tails
ProvedBanditAlgorithm.gaussian_reciprocal_tail_split_envelopeanalysisgaussianprobabilitythompson-sampling
There is a universal constant with the following property. Let for , and fix . If , then
For the complementary region, the reciprocal tail is bounded by the Laplace mixture
This split keeps the exponentially small contribution on the typical side while retaining a nonnegative exponential-mixture envelope on the rare side.
Preamble
import Mathlib.Probability.Distributions.Gaussian.Real open MeasureTheory ProbabilityTheory
Formal statement
theorem BanditAlgorithm.gaussian_reciprocal_tail_split_envelope :
∃ C : ℝ, 0 < C ∧ ∀ a : ℝ, 0 < a → ∀ u : ℝ,
ENNReal.ofReal
(1 / (gaussianReal 0 1).real (Set.Ioi u) - 1) ≤
if u ≤ -a / 2 then
ENNReal.ofReal (2 * Real.exp (-a ^ 2 / 8))
else
ENNReal.ofReal C *
(∫⁻ l : ℝ in Set.Ioi 0,
ENNReal.ofReal
(l * Real.exp (l * u - l ^ 2 / 2))) := by sorrySource
Lattimore and Szepesvári, Bandit Algorithms (CUP 2020), Gaussian Mills-ratio hint for Exercise 36.6(a), printed p. 475 / PDF p. 484; Abramowitz and Stegun (1964), §7.1.13.