Average categorical KL divergence is bounded by marginal entropy
ProvedInformationTheory.kernel_average_categorical_kl_le_marginal_entropybanditsinformation-theoryprobability
Let be a probability measure on a standard Borel space , and let be a Markov kernel from to a finite action set . Write for the marginal action distribution. Then
Thus the expected information carried by a finite-valued conditional distribution is no larger than the entropy of its marginal. This is the entropy bound used in the information-ratio proof of the Bayesian Thompson-sampling regret theorem.
Formalization Note The conclusion is stated for real-valued KL divergence and uses negMulLog so that zero-probability atoms are handled continuously.
Preamble
import Mathlib.InformationTheory.KullbackLeibler.Basic import Mathlib.Analysis.SpecialFunctions.Log.NegMulLog open MeasureTheory ProbabilityTheory InformationTheory open scoped BigOperators
Formal statement
namespace InformationTheory
theorem kernel_average_categorical_kl_le_marginal_entropy
{Alpha : Type} {mAlpha : MeasurableSpace Alpha}
[StandardBorelSpace Alpha] [Nonempty Alpha]
{k : ℕ} [NeZero k] (mu : Measure Alpha) [IsProbabilityMeasure mu]
(kappa : Kernel Alpha (Fin k)) [IsMarkovKernel kappa] :
∫ x, (klDiv (kappa x) (kappa ∘ₘ mu)).toReal ∂mu ≤
∑ a, Real.negMulLog ((kappa ∘ₘ mu).real {a}) := by
sorry
end InformationTheory
Source
Lattimore and Szepesvári, Bandit Algorithms (2020), printed pp. 470–471, Theorem 36.6 and Lemma 36.7, https://tor-lattimore.com/downloads/book/book.pdf; abstracted entropy step in the proof.