One-round divergence of the canonical bandit model
ProvedBanditAlgorithm.klDiv_banditStepKernel_eq_sumOne round of the canonical bandit model costs exactly the policy-weighted average of the arm divergences.
Fix a policy and two bandit environments and with for every arm. Condition on a history of completed rounds, and let be the distribution of the arm played next. The law of the next round's (arm, reward) pair is a Markov kernel in each environment, and
The policy is the same in both environments, so its factor cancels from the likelihood ratio and contributes nothing; what remains is the divergence of the reward distribution of whichever arm was chosen, averaged over the choice.
This is the per-round content of the divergence decomposition of Lattimore and Szepesvari's Lemma 15.1: the full decomposition is obtained by summing this identity over rounds. Stated on its own it can be applied round by round, which is what any localised or stopping-time version of the decomposition needs.
Formalization Note The hypothesis that each arm divergence is finite gives absolute continuity , which is what makes the one-round Radon-Nikodym derivative available; the finiteness itself is not otherwise used, and the identity holds in .
import Mathlib.InformationTheory.KullbackLeibler.ChainRule import Definitions.Def_BanditPolicy open MeasureTheory ProbabilityTheory InformationTheory
theorem BanditAlgorithm.klDiv_banditStepKernel_eq_sum {k n : ℕ}
(nu nu' : StochasticBandit k)
(hKL : ∀ i, klDiv (nu.P i) (nu'.P i) ≠ ⊤)
(pi : BanditPolicy k) (h : BanditHistory k n) :
klDiv (banditStepKernel nu pi n h) (banditStepKernel nu' pi n h) =
∑ i, ENNReal.ofReal ((pi.select n h).real {i}) *
klDiv (nu.P i) (nu'.P i) := by
sorry