Exponentially decaying exact-rank reciprocal Gaussian tail
ProvedBanditAlgorithm.gaussian_exact_rank_reciprocal_tail_exponential_boundbanditsgaussianprobabilitythompson-sampling
There is a universal constant such that, for any arm, positive exact realized rank , offset , policy, and horizon, the expected reciprocal Gaussian posterior-tail term is at most
The expectation includes the indicator that rank was actually realized. This exponentially decaying refinement is summable over and is the finite-rank analytic core of Exercise 36.6(a).
Preamble
import Definitions.Def_ThompsonSampling import Definitions.Def_GaussianBandit open MeasureTheory ProbabilityTheory
Formal statement
theorem BanditAlgorithm.gaussian_exact_rank_reciprocal_tail_exponential_bound :
∃ C : ℝ, 0 < C ∧
∀ (k : ℕ) [NeZero k] (μvec : Fin k → ℝ) (π : BanditAlgorithm.BanditPolicy k),
∀ (i : Fin k) (s : ℕ), 0 < s →
∀ ε : ℝ, 0 < ε →
∀ n : ℕ,
(∫⁻ h,
if s < BanditAlgorithm.armPullCount i h then
ENNReal.ofReal
(1 / BanditAlgorithm.gaussianTSTailProb i s
(BanditAlgorithm.banditArmMean (BanditAlgorithm.gaussianBandit μvec) i - ε) h - 1)
else 0
∂BanditAlgorithm.banditMeasure (BanditAlgorithm.gaussianBandit μvec) π n) ≤
ENNReal.ofReal
(2 * Real.exp (-((s : ℝ) * ε ^ 2) / 8) +
2 * C / ((s : ℝ) * ε ^ 2) *
Real.exp (-(3 * (s : ℝ) * ε ^ 2) / 32)) := by sorrySource
Lattimore and Szepesvári, Bandit Algorithms (CUP 2020), Exercise 36.6(a) and its Gaussian Mills-ratio hint, printed p. 475 / PDF p. 484; reward-stack construction in §4.6, printed p. 65 / PDF p. 74.