Uniform bound for the optimal-arm reciprocal posterior-tail sum
ProvedBanditAlgorithm.gaussian_ts_optimal_exact_rank_reciprocal_tail_sum_uniformasymptoticsbanditsgaussianthompson-sampling
Let be an optimal arm in a unit-variance Gaussian bandit, and fix an offset . For every adaptive policy and every horizon , consider the sum over the realized pull ranks of the reciprocal posterior-tail penalty
There is a universal constant such that the expectation of this sum is bounded uniformly in by
In particular, the optimal-arm reciprocal-tail contribution is 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 ; 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 sorrySource
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.