Finite-horizon KL chain rule at a bounded bandit stopping time
ProvedBanditAlgorithm.bandit_bounded_stopping_klDiv_le_expected_informationbanditschain-ruleinformation-theorystopping-times
Run an adaptive policy in two -armed environments and . Let be a stopping time and fix a deterministic horizon . For the bounded stopping time , the relative entropy between the two experiments observed through is at most the expected armwise information gathered before :
This is the bounded stopping-time form of the adaptive divergence decomposition. It isolates the finite likelihood-chain calculation from the separate limiting argument needed for unbounded stopping times.
Formalization Note Pulls are numbered from zero in the canonical trajectory, so counts indices satisfying and .
Preamble
import Definitions.Def_BanditTrajectory open MeasureTheory ProbabilityTheory InformationTheory ENNReal
Formal statement
theorem BanditAlgorithm.bandit_bounded_stopping_klDiv_le_expected_information
{k : ℕ} (ν ν' : StochasticBandit k) (π : BanditPolicy k)
(τ : (ℕ → Fin k × ℝ) → ℕ∞) (hτ : IsBanditStoppingTime τ) (n : ℕ) :
@klDiv (ℕ → Fin k × ℝ) (hτ.min_const n).measurableSpace
((banditTrajMeasure ν π).trim (hτ.min_const n).measurableSpace_le)
((banditTrajMeasure ν' π).trim (hτ.min_const n).measurableSpace_le) ≤
∑ i, (∫⁻ ω, ∑' t : ℕ,
if (t : ℕ∞) < min (τ ω) n ∧ (ω t).1 = i
then (1 : ℝ≥0∞) else 0
∂banditTrajMeasure ν π) * klDiv (ν.P i) (ν'.P i) := by
sorrySource
Lattimore and Szepesvári, Bandit Algorithms (CUP 2020), Lemma 15.1, Eq. (15.1), printed p. 198, together with Exercise 15.7, printed p. 211, bounded-stopping-time step.