Squared instantaneous regret controlled by prior entropy
ProvedBanditAlgorithm.bayesian_ts_squared_regret_information_boundbanditsinformation-theoryprobabilitythompson-sampling
Consider the Bayesian adversarial -armed bandit over rounds with an arbitrary prior on reward matrices in , and let Thompson sampling use the posterior distribution of the best fixed action. There are per-round conditional expected-regret terms which decompose Bayesian regret and satisfy
This combines the pointwise information-ratio estimate with the mutual-information chain rule and the entropy bound . It isolates the probabilistic core before the final Cauchy--Schwarz conversion from squared instantaneous regret to total regret.
Preamble
import Definitions.Def_ThompsonSampling open MeasureTheory ProbabilityTheory open scoped BigOperators
Formal statement
theorem BanditAlgorithm.bayesian_ts_squared_regret_information_bound {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 π) :
∃ δ : Fin n → ℝ,
bayesianAdversarialRegret Q π = ∑ t, δ t ∧
∑ t, δ t ^ 2 ≤ ((k : ℝ) / 2) * 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.