Gaussian posterior overshoot at one exact realized rank
ProvedBanditAlgorithm.gaussian_exact_rank_posterior_overshoot_probability_boundbanditsconcentrationgaussianthompson-sampling
Fix an optimal arm , a suboptimal arm of gap , a separating offset , a horizon , and a positive exact realized rank . On histories where arm has been pulled more than times, the probability that its rank- Gaussian posterior assigns more than mass above is at most
This is the arbitrary-threshold exact-rank form of the deviation estimate used in Exercise 36.6(b).
Preamble
import Definitions.Def_ThompsonSampling import Definitions.Def_GaussianBandit open MeasureTheory ProbabilityTheory
Formal statement
theorem BanditAlgorithm.gaussian_exact_rank_posterior_overshoot_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 →
∀ ε : ℝ, 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₀ - ε) h} ≤
if 2 * Real.log n /
(BanditAlgorithm.banditGap (BanditAlgorithm.gaussianBandit μvec) i - ε) ^ 2 < (s : ℝ)
then
Real.exp
(-((s : ℝ) *
(BanditAlgorithm.banditGap (BanditAlgorithm.gaussianBandit μvec) i - ε -
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; Theorem 36.2 and Eq. (36.3), printed pp. 463–465 / PDF pp. 472–474; reward-stack construction in §4.6, printed p. 65 / PDF p. 74.