Sharp exact-rank Gaussian posterior-overshoot sum
ProvedBanditAlgorithm.gaussian_ts_suboptimal_exact_rank_overshoot_sum_sharpasymptoticsbanditsgaussianthompson-sampling
Fix an optimal arm , a suboptimal arm of gap , and . Along the exact realized ranks of arm , the expected number of posterior distributions that put more than mass above satisfies
The leading coefficient is therefore the sharp from Exercise 36.6(b).
Preamble
import Definitions.Def_ThompsonSampling import Definitions.Def_GaussianBandit open MeasureTheory ProbabilityTheory ENNReal
Formal statement
theorem BanditAlgorithm.gaussian_ts_suboptimal_exact_rank_overshoot_sum_sharp :
∀ (k : ℕ) [NeZero k] (μvec : Fin k → ℝ) (π : BanditAlgorithm.BanditPolicy k),
∀ (i₀ : Fin k),
BanditAlgorithm.banditArmMean (BanditAlgorithm.gaussianBandit μvec) i₀ =
BanditAlgorithm.banditOptimalMean (BanditAlgorithm.gaussianBandit μvec) →
∀ (i : Fin k), 0 < BanditAlgorithm.banditGap (BanditAlgorithm.gaussianBandit μvec) i →
∀ ε : ℝ, 0 < ε →
ε < BanditAlgorithm.banditGap (BanditAlgorithm.gaussianBandit μvec) i →
∀ n : ℕ, 2 ≤ n →
(∫⁻ h, ∑ s ∈ Finset.range (BanditAlgorithm.armPullCount i h),
(if 1 / (n : ℝ) <
BanditAlgorithm.gaussianTSTailProb i s
(BanditAlgorithm.banditArmMean (BanditAlgorithm.gaussianBandit μvec) i₀ - ε) h
then (1 : ℝ≥0∞) else 0)
∂BanditAlgorithm.banditMeasure (BanditAlgorithm.gaussianBandit μvec) π n) ≤
ENNReal.ofReal
(1 + 2 / (BanditAlgorithm.banditGap (BanditAlgorithm.gaussianBandit μvec) i - ε) ^ 2 *
(Real.log n + Real.sqrt (Real.pi * Real.log n) + 1)) := by sorrySource
Lattimore and Szepesvári, Bandit Algorithms (CUP 2020), Exercise 36.6(b), printed p. 475 / PDF p. 484, and Theorem 36.2, Eq. (36.3), printed pp. 463–465 / PDF pp. 472–474.