One-round divergence increment in the canonical bandit model
ProvedBanditAlgorithm.bandit_divergence_one_stepbanditsinformation-theorylower-bounds
For two finite-armed stochastic bandits run under the same possibly randomized policy, the KL divergence between their canonical history laws after round equals the divergence after round plus the expected KL contribution of the newly selected arm. The coefficient of arm is its round- selection probability averaged under the first bandit's -round history law. This is the one-round conditional-expectation identity used in the proof of the divergence decomposition.
Preamble
import Mathlib.InformationTheory.KullbackLeibler.ChainRule import Definitions.Def_BanditPolicy open MeasureTheory ProbabilityTheory InformationTheory
Formal statement
theorem BanditAlgorithm.bandit_divergence_one_step {k n : ℕ} (ν ν' : StochasticBandit k)
(hKL : ∀ i, klDiv (ν.P i) (ν'.P i) ≠ ⊤)
(π : BanditPolicy k) :
klDiv (banditMeasure ν π (n + 1)) (banditMeasure ν' π (n + 1)) =
klDiv (banditMeasure ν π n) (banditMeasure ν' π n) +
∑ i, ENNReal.ofReal
(∫ h, (π.select n h).real {i} ∂banditMeasure ν π n) *
klDiv (ν.P i) (ν'.P i) := by
sorrySource
Lattimore--Szepesvári, Bandit Algorithms (CUP 2020), Lemma 15.1 proof, Eq. (15.2), printed pp. 198--199 / PDF pp. 207--208: chain rule for the canonical likelihood ratio and conditioning on the selected arm.