Gaussian Thompson sampling: large posterior tail at one exact rank
ProvedBanditAlgorithm.gaussian_exact_rank_large_posterior_tail_probability_boundbanditsconcentrationgaussianthompson-sampling
Consider Gaussian Thompson sampling with independent rewards and posterior variance after observations of arm . Fix an optimal arm , a suboptimal arm with gap , a horizon , and an exact positive rank . On histories where arm has been pulled more than times, the probability that its rank- posterior assigns more than mass above the midpoint is at most
The event reduction uses the Gaussian posterior tail bound and the stopped reward-stack concentration inequality for the first rewards of arm .
Preamble
import Definitions.Def_ThompsonSampling import Definitions.Def_GaussianBandit open MeasureTheory ProbabilityTheory
Formal statement
theorem BanditAlgorithm.gaussian_exact_rank_large_posterior_tail_probability_bound :
∀ (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 →
∀ n : ℕ, 2 ≤ n →
∀ s : ℕ, 0 < s →
(BanditAlgorithm.banditMeasure (BanditAlgorithm.gaussianBandit μvec) π n).real
{h : BanditAlgorithm.BanditHistory k n |
s < BanditAlgorithm.armPullCount i h ∧
1 / (n : ℝ) <
BanditAlgorithm.gaussianTSTailProb i s
(BanditAlgorithm.banditArmMean (BanditAlgorithm.gaussianBandit μvec) i₀ -
BanditAlgorithm.banditGap (BanditAlgorithm.gaussianBandit μvec) i / 2) h} ≤
if 2 * Real.log n /
(BanditAlgorithm.banditGap (BanditAlgorithm.gaussianBandit μvec) i / 2) ^ 2 < (s : ℝ)
then
Real.exp
(-((s : ℝ) *
(BanditAlgorithm.banditGap (BanditAlgorithm.gaussianBandit μvec) i / 2 -
Real.sqrt (2 * Real.log n / s))) ^ 2 /
((2 : ℝ) * (s : ℝ) * 1))
else 1 := by sorrySource
Lattimore and Szepesvári, Bandit Algorithms (CUP 2020), Exercise 36.6(b), printed p. 475 / PDF p. 484; reward-stack construction in §4.6, printed p. 65 / PDF p. 74, and Gaussian Thompson-sampling analysis in Theorem 36.2, printed pp. 463–465 / PDF pp. 472–474.