Thompson-sampling pull-count decomposition with exact realized ranks
ProvedBanditAlgorithm.thompson_sampling_pull_count_bound_exact_ranksbanditsprobabilitythompson-sampling
Assume arm is optimal, let , and fix a separating parameter . For Gaussian follow-the-perturbed-leader / Thompson sampling, the expected number of pulls of arm is bounded by
Here is the Gaussian perturbation tail probability above after the first observations of arm . Unlike the looser published platform version, each sum stops at the realized pull count. Thus every empirical mean appearing in is based on exactly actual observations, matching the reward-stack rank argument in the proof of Theorem 36.2.
Preamble
import Definitions.Def_BanditPolicy import Definitions.Def_ThompsonSampling open MeasureTheory ProbabilityTheory ENNReal
Formal statement
theorem BanditAlgorithm.thompson_sampling_pull_count_bound_exact_ranks {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 (armPullCount i₀ h),
ENNReal.ofReal (1 / gaussianTSTailProb i₀ s
(banditArmMean ν i₀ - ε) h - 1)
∂banditMeasure ν π n)
+ ∫⁻ h, ∑ s ∈ Finset.range (armPullCount i h),
(if 1 / (n : ℝ) <
gaussianTSTailProb i s (banditArmMean ν i₀ - ε) h
then (1 : ℝ≥0∞) else 0)
∂banditMeasure ν π n := by
sorrySource
Lattimore and Szepesvari, Bandit Algorithms (CUP 2020), proof of Theorem 36.2, Eqs. (36.4)-(36.6), printed pp.464-465. This is the exact rank-sum inequality before enlarging the realized rank ranges to 0,...,n-1 in Eq. (36.3).