BanditAlgorithm.thompson_sampling_bayesian_regret
Provedbanditsbayesianinformation-ratiothompson-sampling
(Bayesian regret, information-theoretic; L&S Theorem 36.5) For the Bayesian -armed adversarial bandit of §36.4 — reward matrix drawn from an arbitrary prior — Thompson sampling (the policy playing each action according to the conditional probability that it is optimal given the history) satisfies
(Proved in the book via the generic information-ratio Theorem 36.6 with the negentropy potential and Lemma 36.7's bound .)
Preamble
import Definitions.Def_ThompsonSampling open MeasureTheory ProbabilityTheory
Formal statement
theorem BanditAlgorithm.thompson_sampling_bayesian_regret {k n : ℕ} [NeZero k]
(Q : Measure (Fin n → Fin k → ℝ)) [IsProbabilityMeasure Q]
(hQ : ∀ᵐ X ∂Q, ∀ (t : Fin n) (a : Fin k), X t a ∈ Set.Icc (0 : ℝ) 1)
{π : BanditPolicy k} (hπ : IsBayesianTSPolicy Q π) :
bayesianAdversarialRegret Q π ≤ Real.sqrt (k * n * Real.log k / 2) := by
sorry
Source
L&S Theorem 36.5 (with Theorem 36.6), p.469