One-step information-ratio bound with arm-dependent reference laws
ProvedBanditAlgorithm.thompson_sampling_one_step_information_ratio_varying_referencebanditsinformation-theoryprobability
Let be real weights. For every arm , let and be probability measures on the same measurable space, and let be a measurable function taking values in . If every is finite, then
This is the analytic Pinsker–Cauchy–Schwarz step in the one-round Thompson-sampling information-ratio argument, allowing the reference distribution to depend on the arm.
Preamble
import Mathlib.InformationTheory.KullbackLeibler.Basic open MeasureTheory InformationTheory open scoped ENNReal BigOperators
Formal statement
namespace BanditAlgorithm
theorem thompson_sampling_one_step_information_ratio_varying_reference
{k : ℕ} {Omega : Type} {mOmega : MeasurableSpace Omega}
(p : Fin k → ℝ) (P M : Fin k → Measure Omega)
[∀ a, IsProbabilityMeasure (P a)] [∀ a, IsProbabilityMeasure (M a)]
(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) ≠ ∞) :
(∑ a, p a * ((∫ x, reward a x ∂(P a)) - ∫ x, reward a x ∂(M a))) ^ 2 ≤
((k : ℝ) / 2) * ∑ a, p a ^ 2 * (klDiv (P a) (M a)).toReal := by
sorry
end BanditAlgorithm
Source
Lattimore and Szepesvári, Bandit Algorithms (2020), Lemma 36.7, printed p. 470 (free PDF p. 479), https://tor-lattimore.com/downloads/book/book.pdf; Pinsker and Cauchy–Schwarz steps.