KL divergence decomposition for a stopped adaptive bandit experiment
ProvedBanditAlgorithm.bandit_stopped_klDiv_le_expected_informationbanditsinformation-theorylower-boundsstopping-times
Run an adaptive policy in environments and , and let be the sigma-algebra observable at an integrable stopping time . The KL divergence between the two trajectory laws restricted to is at most the expected armwise information accumulated before stopping:
For the canonical bandit experiment this is in fact an equality under the usual finite-divergence hypotheses; the inequality is the singularity-safe form needed by lower-bound arguments.
Preamble
import Definitions.Def_BanditTrajectory open MeasureTheory ProbabilityTheory InformationTheory ENNReal
Formal statement
theorem BanditAlgorithm.bandit_stopped_klDiv_le_expected_information
{k : ℕ} (ν ν' : StochasticBandit k) (π : BanditPolicy k)
(τ : (ℕ → Fin k × ℝ) → ℕ∞) (hτ : IsBanditStoppingTime τ)
(hfinite : ∫⁻ ω, (τ ω : ℝ≥0∞) ∂banditTrajMeasure ν π < ⊤) :
@klDiv (ℕ → Fin k × ℝ) hτ.measurableSpace
((banditTrajMeasure ν π).trim hτ.measurableSpace_le)
((banditTrajMeasure ν' π).trim hτ.measurableSpace_le) ≤
∑ i, (∫⁻ ω, ∑' t : ℕ,
if (t : ℕ∞) < τ ω ∧ (ω t).1 = i then (1 : ℝ≥0∞) else 0
∂banditTrajMeasure ν π) * klDiv (ν.P i) (ν'.P i) := by
sorrySource
Lattimore--Szepesvári, Bandit Algorithms (CUP 2020), Exercise 15.7, printed p. 211: stopping-time extension of the divergence decomposition in Lemma 15.1, Eq. (15.1), printed p. 198.