Gaussian tail sums in the Thompson-sampling pull-count decomposition
OpenBanditAlgorithm.gaussian_ts_pull_count_rhs_boundbanditsgaussianprobabilitythompson-sampling
Let be an optimal arm and a suboptimal arm of a unit-variance Gaussian bandit, with gap . In the pull-count decomposition of Theorem 36.2, choose the separating threshold . Then there is a universal constant such that, for every , the initial , the expected optimal-arm reciprocal-tail sum, and the expected suboptimal-arm large-tail indicator sum together satisfy
Here is the posterior Gaussian probability of exceeding after observations of arm . This theorem isolates exactly the two Gaussian tail calculations needed after Eq. (36.3).
Preamble
import Definitions.Def_ThompsonSampling import Definitions.Def_GaussianBandit open MeasureTheory ProbabilityTheory ENNReal
Formal statement
theorem BanditAlgorithm.gaussian_ts_pull_count_rhs_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 →
1 + (∫⁻ h, ∑ s ∈ Finset.range n,
ENNReal.ofReal
(1 / gaussianTSTailProb i₀ s
(banditArmMean (gaussianBandit μvec) i₀ -
banditGap (gaussianBandit μvec) i / 2) h - 1)
∂banditMeasure (gaussianBandit μvec) π 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 * (1 + 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, and Theorem 36.3 / Exercise 36.6, printed pp.465 and 477.