One-round Thompson-sampling information-ratio bound
ProvedBanditAlgorithm.bayesian_ts_round_regret_sq_le_mutualInformation_incrementbanditsinformation-ratiothompson-sampling
Let
be the one-round Bayesian regret of posterior-sampling Thompson sampling, and let be the mutual information between the history before round and the optimal action. If rewards lie in , then
This is the one-step information-ratio estimate: the squared expected regret is controlled by the information about revealed by the next action–reward observation.
Preamble
import Definitions.Def_BayesianHistoryMutualInformation open MeasureTheory ProbabilityTheory
Formal statement
theorem BanditAlgorithm.bayesian_ts_round_regret_sq_le_mutualInformation_increment
{k n : ℕ} [NeZero k]
(Q : Measure (Fin n → Fin k → ℝ)) [IsProbabilityMeasure Q]
(hQ : ∀ᵐ X ∂Q, ∀ (s : Fin n) (a : Fin k), X s a ∈ Set.Icc (0 : ℝ) 1)
{pi : BanditPolicy k} (hpi : IsBayesianTSPolicy Q pi) (t : Fin n) :
(∫ p, (p.1 t (bayesianOptimalAction p.1) - p.1 t ((p.2 t).1))
∂bayesianAdversarialMeasure Q pi n le_rfl) ^ 2 ≤
((k : ℝ) / 2) *
(bayesianHistoryMutualInformation Q pi (t.1 + 1) (Nat.succ_le_iff.mpr t.2) -
bayesianHistoryMutualInformation Q pi t.1 (Nat.le_of_lt t.2)) := by
sorrySource
Lattimore and Szepesvári, Bandit Algorithms (Cambridge UP, 2020), https://tor-lattimore.com/downloads/book/book.pdf, printed pp. 470–471 (PDF pp. 479–480), Lemma 36.7 and the Bayes-rule equality at the end of its proof.