One-step Thompson-sampling diagonal information-ratio bound
ProvedBanditAlgorithm.thompson_sampling_one_step_information_ratio_diagonalbanditsinformation-ratiothompson-sampling
Fix a posterior weight vector on actions. For each action , let be the conditional observation law on the event that is optimal, let be the posterior-predictive observation law, and let be the reward observable. If every is finite, then
The right side is the diagonal contribution to the information gained by posterior sampling.
Preamble
import Mathlib.InformationTheory.KullbackLeibler.Basic open MeasureTheory InformationTheory open scoped ENNReal BigOperators
Formal statement
theorem BanditAlgorithm.thompson_sampling_one_step_information_ratio_diagonal
{k : ℕ} {Omega : Type} {mOmega : MeasurableSpace Omega}
(p : Fin k → ℝ) (P : Fin k → Measure Omega)
[∀ a, IsProbabilityMeasure (P a)]
(M : Measure Omega) [IsProbabilityMeasure M]
(reward : Fin k → Omega → ℝ)
(hreward : ∀ a, Measurable (reward a))
(hreward0 : ∀ a x, 0 ≤ reward a x)
(hreward1 : ∀ a x, reward a x ≤ 1)
(hfinite : ∀ a, klDiv (P a) M ≠ ∞) :
(∑ a, p a * ((∫ x, reward a x ∂(P a)) - ∫ x, reward a x ∂M)) ^ 2 ≤
((k : ℝ) / 2) * ∑ a, p a ^ 2 * (klDiv (P a) M).toReal := by
sorrySource
Lattimore and Szepesvári, Bandit Algorithms (Cambridge UP, 2020), https://tor-lattimore.com/downloads/book/book.pdf, printed p. 470 (PDF p. 479), Lemma 36.7 and its proof: Pinsker followed by Cauchy–Schwarz, before the final Bayes-rule identification.