BanditAlgorithm.thompson_sampling_pull_count_bound
Provedbanditsthompson-sampling
(Pull-count decomposition, L&S Theorem 36.2, stated for the Gaussian instantiation of Algorithm 24 used in Theorem 36.3.) Assume arm is optimal, let and let be arbitrary. Then
where is the posterior tail probability that arm 's sample exceeds after plays ( = CDF of , ). Both sides are stated in (lintegrals), so no integrability hypotheses are needed — exactly as in the book, where the right-hand side may be infinite.
Preamble
import Definitions.Def_BanditPolicy import Definitions.Def_ThompsonSampling open MeasureTheory ProbabilityTheory ENNReal
Formal statement
theorem BanditAlgorithm.thompson_sampling_pull_count_bound {k : ℕ} [NeZero k]
(ν : StochasticBandit k) {π : BanditPolicy k} (hπ : IsGaussianTSPolicy π)
(i₀ : Fin k) (h₀ : banditArmMean ν i₀ = banditOptimalMean ν)
(i : Fin k) (hi : i ≠ i₀) (ε : ℝ) (n : ℕ) :
∫⁻ h, (armPullCount i h : ℝ≥0∞) ∂banditMeasure ν π n ≤
1 + (∫⁻ h, ∑ s ∈ Finset.range n,
ENNReal.ofReal (1 / gaussianTSTailProb i₀ s (banditArmMean ν i₀ - ε) h - 1)
∂banditMeasure ν π n)
+ ∫⁻ h, ∑ s ∈ Finset.range n,
(if 1 / (n : ℝ) < gaussianTSTailProb i s (banditArmMean ν i₀ - ε) h
then (1 : ℝ≥0∞) else 0)
∂banditMeasure ν π n := by
sorry
Source
L&S Theorem 36.2, p.463