Suboptimal-arm large Gaussian posterior-tail sum
DisprovedBanditAlgorithm.gaussian_ts_suboptimal_large_tail_sum_boundbanditsgaussianprobabilitythompson-sampling
Let be an optimal arm and a suboptimal arm with gap in a unit-variance Gaussian bandit. Write for the Gaussian posterior probability that arm exceeds after observations. There is a universal constant such that, for every ,
This is the suboptimal-arm posterior-overshoot estimate required by the second sum in the Thompson-sampling pull-count decomposition.
Preamble
import Definitions.Def_ThompsonSampling import Definitions.Def_GaussianBandit open MeasureTheory ProbabilityTheory ENNReal
Formal statement
theorem BanditAlgorithm.gaussian_ts_suboptimal_large_tail_sum_bound :
∃ C : ℝ, 0 < C ∧
∀ (k : ℕ) [NeZero k] (μvec : Fin k → ℝ) (π : BanditPolicy k),
IsGaussianTSPolicy π →
∀ (i₀ : Fin k),
banditArmMean (gaussianBandit μvec) i₀ =
banditOptimalMean (gaussianBandit μvec) →
∀ (i : Fin k), 0 < banditGap (gaussianBandit μvec) i →
∀ n : ℕ, 2 ≤ n →
(∫⁻ h, ∑ s ∈ Finset.range n,
(if 1 / (n : ℝ) <
gaussianTSTailProb i s
(banditArmMean (gaussianBandit μvec) i₀ -
banditGap (gaussianBandit μvec) i / 2) h
then (1 : ℝ≥0∞) else 0)
∂banditMeasure (gaussianBandit μvec) π n) ≤
ENNReal.ofReal
(C * Real.log n /
banditGap (gaussianBandit μvec) i ^ 2) := by
sorrySource
Lattimore and Szepesvari, Bandit Algorithms (CUP 2020), Theorem 36.2 Eq. (36.3), printed p.463, specialized to Gaussian updates as directed by Theorem 36.3 and Exercise 36.6, printed pp.465 and 477.