Bayesian Thompson sampling information accounting
ProvedBanditAlgorithm.bayesian_ts_information_accountingbanditsinformation-theoryprobabilitythompson-sampling
Consider a Bayesian adversarial -armed bandit over rounds. A reward matrix is drawn from an arbitrary prior , and Thompson sampling plays according to the posterior distribution of the best fixed action . Then there are per-round expected-regret terms and per-round information gains such that
The pointwise inequality is the Thompson-sampling information-ratio estimate, while the last inequality is the chain-rule bound . This theorem isolates the probabilistic and information-theoretic core from the final Cauchy--Schwarz step.
Preamble
import Definitions.Def_ThompsonSampling open MeasureTheory ProbabilityTheory open scoped BigOperators
Formal statement
theorem BanditAlgorithm.bayesian_ts_information_accounting {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 π) :
∃ δ info : Fin n → ℝ,
bayesianAdversarialRegret Q π = ∑ t, δ t ∧
(∀ t, δ t ^ 2 ≤ ((k : ℝ) / 2) * info t) ∧
∑ t, info t ≤ Real.log k := by
sorrySource
Lattimore and Szepesvari, Bandit Algorithms (CUP 2020), Theorem 36.5, Theorem 36.6, and Lemma 36.7, printed pp. 469-473; Eq. (36.10) and the proof of Lemma 36.7.