BanditAlgorithm.bandit_divergence_decomposition
Provedbanditsinformation-theorylower-bounds
(Divergence decomposition) Let and be reward distributions of two -armed bandits, a fixed policy, and the measures induced on the canonical bandit model by the -round interconnection. Then
Preamble
import Mathlib.InformationTheory.KullbackLeibler.Basic import Definitions.Def_BanditPolicy open MeasureTheory ProbabilityTheory InformationTheory
Formal statement
theorem BanditAlgorithm.bandit_divergence_decomposition {k : ℕ} (ν ν' : StochasticBandit k)
(hKL : ∀ i, klDiv (ν.P i) (ν'.P i) ≠ ⊤)
(π : BanditPolicy k) (n : ℕ) :
klDiv (banditMeasure ν π n) (banditMeasure ν' π n) =
∑ i, ENNReal.ofReal (∫ h, (armPullCount i h : ℝ) ∂banditMeasure ν π n) *
klDiv (ν.P i) (ν'.P i) := by
sorry
Source
L&S Lemma 15.1, Eq. (15.1), p.198
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.