§2.6, p. 36 — symmetry of the expected KL divergence
ProvedFoundationsRL.PosteriorSampling.kl_symmetrybandit-algorithmsp2o-gran-per-chapterp2o-plan-bookp2o-v1posterior-samplingreinforcement-learning
For a pair of random variables,
Both sides are the mutual information between and . The identity turns information carried by the reward about into the change of the posterior of .
Formalization Note The conditional laws are regular conditional distributions, and both sides take values in .
Differences from the source:
- encoding: random variables X, Y, no space specified → values in standard Borel spaces; reason: this is where P_{Y|X} and P_{X|Y} exist as conditional laws
- encoding: D_KL as a real quantity → InformationTheory.klDiv in ℝ≥0∞; reason: both sides may be infinite
- encoding: X, Y random variables (their value spaces carry a law) → [Nonempty X] [Nonempty Y]; reason: a probability measure on X × Y already forces both spaces nonempty; the instances are needed by Measure.condKernel and exclude no instance
Preamble
import Mathlib open MeasureTheory ProbabilityTheory InformationTheory
Formal statement
namespace FoundationsRL.PosteriorSampling
/-- Symmetry of the expected KL divergence (Foster & Rakhlin, *Foundations of Reinforcement
Learning and Interactive Decision Making*, arXiv:2312.16730v1, §2.6, p. 36):
`E_X[D_KL(P_{Y|X} ∥ P_Y)] = E_Y[D_KL(P_{X|Y} ∥ P_X)]`, for a pair `(X, Y)` of law `ρ`.
**Formalization Note.** `X` and `Y` take values in standard Borel spaces, where the conditional
laws `P_{Y|X}` and `P_{X|Y}` exist as kernels (`Measure.condKernel`). Both sides are in `ℝ≥0∞`
and may be `∞`. -/
theorem kl_symmetry {X Y : Type*} [MeasurableSpace X] [MeasurableSpace Y]
[StandardBorelSpace X] [StandardBorelSpace Y] [Nonempty X] [Nonempty Y]
(ρ : Measure (X × Y)) [IsProbabilityMeasure ρ] :
∫⁻ x, klDiv (ρ.condKernel x) ρ.snd ∂ρ.fst =
∫⁻ y, klDiv ((ρ.map Prod.swap).condKernel y) ρ.fst ∂ρ.snd := by sorry
end FoundationsRL.PosteriorSampling
Source
Foster & Rakhlin, Foundations of Reinforcement Learning and Interactive Decision Making, arXiv:2312.16730v1, §2.6, line before (2.33), p. 36
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.