BanditAlgorithm.thompson_sampling_pull_count_bound
Proved(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.
import Definitions.Def_BanditPolicy import Definitions.Def_ThompsonSampling open MeasureTheory ProbabilityTheory ENNReal
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
Read-back
What the Lean code literally says, in plain math · claude-fable-5
Setup. A -armed stochastic bandit ( by typeclass) is a family of probability measures on ; is arm 's mean and (real supremum over the finitely many arms). is the -round interaction law of policy with : each round the arm is drawn from 's kernel applied to the past (arm, reward) pairs and the reward from that arm's distribution, the pair being appended to the history. is arm 's pull count in history . is if , else the probability that a Gaussian with mean and variance strictly exceeds , where is the sum of the rewards of the first at-most- plays of arm divided by the nominal .
Assertion (all three integrals are lower Lebesgue integrals valued in ; clamps the real to ):
Hypotheses.
- ; is an arbitrary -armed bandit — no integrability, subgaussianity, or Gaussianity of the arm distributions is assumed.
- is a Gaussian TS policy: at every history its selection kernel equals the Gaussian-posterior-sampling distribution (point mass at the least-index unpulled arm if some arm is unpulled; otherwise the pushforward under least-index-argmax of independent samples).
- (arm is optimal); .
- is an arbitrary real — no positivity or size constraint.
- is an arbitrary natural number.
Edge cases.
- : both sums are empty and is the real junk ; the claim degenerates to .
- If a tail probability were , the real convention gives , hence : the corresponding summand vanishes instead of blowing up. (For actual Gaussian tail probabilities the value lies strictly in , so and the clamp is inert.)
- Both sides live in , so the inequality is meaningful even if a side is infinite.
- The threshold uses the true mean of the optimal arm, and the same threshold appears in both sums (once for , once for ).
Confirmed by the mission captain (proposal self-audit).