Pinsker inequality for bounded expectations
ProvedBanditAlgorithm.pinsker_squared_bounded_expectation_differencebanditsinformation-theorypinsker
Let and be probability measures and let be a measurable function with values in . If is finite, then
This is the bounded-expectation form of Pinsker’s inequality used in the one-step Thompson-sampling information-ratio argument.
Preamble
import Mathlib.InformationTheory.KullbackLeibler.Basic open MeasureTheory InformationTheory open scoped ENNReal
Formal statement
theorem BanditAlgorithm.pinsker_squared_bounded_expectation_difference
{Omega : Type} {mOmega : MeasurableSpace Omega}
(P Q : Measure Omega) [IsProbabilityMeasure P] [IsProbabilityMeasure Q]
(f : Omega → ℝ) (hf : Measurable f)
(hf0 : ∀ x, 0 ≤ f x) (hf1 : ∀ x, f x ≤ 1)
(hD : klDiv P Q ≠ ∞) :
2 * ((∫ x, f x ∂Q) - ∫ x, f x ∂P) ^ 2 ≤ (klDiv P Q).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), proof of Lemma 36.7, first inequality after the definition of Δ_t; the extension from events to [0,1]-valued rewards is the standard layer-cake form of Pinsker.
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.