Average finite-valued KL divergence is bounded by marginal entropy
ProvedInformationTheory.kernel_average_categorical_kl_le_marginal_entropy_generalbanditsinformation-theoryprobability
Let be a probability measure on an arbitrary measurable space , and let be a Markov kernel from to a finite action set . Write for the marginal action distribution. Then
No topological or standard-Borel assumption is needed on : finiteness of the output alphabet suffices. This general form is the entropy bound used when a joint law is disintegrated into a finite-valued conditional distribution.
Formalization Note The proof derives almost-everywhere absolute continuity directly from , so it does not rely on a posterior-kernel construction on the source space.
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_general
{Alpha : Type} {mAlpha : MeasurableSpace 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 finite-alphabet entropy step.