Asymptotic pull count of a suboptimal arm under Gaussian TS
ProvedBanditAlgorithm.gaussian_ts_suboptimal_pull_count_asymptoticbanditsgaussianprobabilitythompson-sampling
Let Thompson sampling use independent Gaussian posterior perturbations of variance in a unit-variance Gaussian -armed bandit. For any suboptimal arm with gap , its expected number of pulls satisfies
This is the armwise probabilistic core of the instance-dependent asymptotic regret theorem. Summing it against the gaps via the regret decomposition yields the Lai--Robbins-optimal coefficient .
Preamble
import Definitions.Def_ThompsonSampling import Definitions.Def_GaussianBandit open MeasureTheory ProbabilityTheory Filter
Formal statement
theorem BanditAlgorithm.gaussian_ts_suboptimal_pull_count_asymptotic
{k : ℕ} [NeZero k] (μvec : Fin k → ℝ) (π : BanditPolicy k)
(hπ : IsGaussianTSPolicy π) (i : Fin k)
(hi : 0 < banditGap (gaussianBandit μvec) i) :
Tendsto
(fun n : ℕ ↦
(∫ h, (armPullCount i h : ℝ)
∂banditMeasure (gaussianBandit μvec) π n) / Real.log n)
atTop
(nhds (2 / banditGap (gaussianBandit μvec) i ^ 2)) := by
sorrySource
Lattimore and Szepesvari, Bandit Algorithms (CUP 2020), Theorem 36.3 and its proof, printed pp. 464-468, using Theorem 36.2.