BanditAlgorithm.thompson_sampling_frequentist_regret
Proved(Thompson sampling frequentist optimality, GOAL; L&S Theorem 36.3) Thompson sampling with and Gaussian updates (Algorithm 24) on any unit-variance Gaussian bandit satisfies
(a genuine limit); and there is a universal constant such that
for all and all Gaussian bandits with means in (the normalization of Theorem 36.1; as literally stated in the book the distribution-free bound fails for and for unbounded means, since the forced first pull of each arm costs ).
import Definitions.Def_banditRegret import Definitions.Def_GaussianBandit import Definitions.Def_ThompsonSampling open MeasureTheory ProbabilityTheory Filter
theorem BanditAlgorithm.thompson_sampling_frequentist_regret :
(∀ (k : ℕ) [NeZero k] (μvec : Fin k → ℝ) (π : BanditPolicy k),
IsGaussianTSPolicy π →
Tendsto (fun n : ℕ ↦ banditRegret (gaussianBandit μvec) π n / Real.log n)
atTop
(nhds (∑ i ∈ Finset.univ.filter
(fun i ↦ 0 < banditGap (gaussianBandit μvec) i),
2 / banditGap (gaussianBandit μvec) i))) ∧
(∃ C : ℝ, 0 < C ∧
∀ (k : ℕ) [NeZero k] (μvec : Fin k → ℝ) (π : BanditPolicy k),
IsGaussianTSPolicy π → (∀ i, μvec i ∈ Set.Icc (0 : ℝ) 1) →
∀ n : ℕ, 2 ≤ n →
banditRegret (gaussianBandit μvec) π n ≤
C * Real.sqrt (k * n * Real.log n)) := by
sorry
Read-back
What the Lean code literally says, in plain math · claude-fable-5
Setup. For a mean vector , the unit-variance Gaussian bandit has arm distributions (second parameter a variance); its arm means equal , , and the gaps are . For a policy , the expected regret at horizon is , the expectation over the -round interaction law and the round- reward. " is a Gaussian TS policy" means: at every round and history, the selection kernel is the point mass at the least-index unpulled arm if some arm is unpulled, else the pushforward under least-index-argmax of independent posterior samples ( = empirical mean and pull count).
Assertion. The theorem is a closed statement (no free variables): the conjunction of
- (Exact asymptotics) For every , every , and every Gaussian TS policy :
- (Minimax bound) There exists such that for every , every , every Gaussian TS policy , and every :
Hypotheses / scope.
- Part 1 imposes no bound on the means; part 2 requires every and .
- Both parts are conditional on the policy satisfying the Gaussian TS predicate; the theorem does not assert that such a policy exists.
- The sum in part 1 runs only over arms with strictly positive gap; when every arm is optimal the asserted limit is .
- The single constant of part 2 is uniform in , , , and .
Edge cases.
- Part 1 asserts genuine two-sided convergence of (not just an upper bound), with the natural logarithm; the junk values at (where makes the quotient the division-by-zero junk) do not affect the limit along .
- is defined through a Bochner integral of the total reward (junk if non-integrable) and through the finite real supremum .
Confirmed by the mission captain (proposal self-audit).