Bretagnolle--Huber inequality at an adaptive bandit stopping time
ProvedBanditAlgorithm.bandit_stopped_bretagnolle_huberbanditsinformation-theorylower-boundsstopping-times
Run a common adaptive policy in two bandit environments and , and observe the experiment only until an integrable stopping time . For every event measurable from the stopped experiment, let
When , the two testing errors satisfy the stopped Bretagnolle--Huber inequality
This is the stopping-time extension of the canonical bandit divergence decomposition followed by data processing to the binary decision .
Preamble
import Definitions.Def_BanditTrajectory open MeasureTheory ProbabilityTheory InformationTheory ENNReal
Formal statement
theorem BanditAlgorithm.bandit_stopped_bretagnolle_huber
{k : ℕ} (ν ν' : StochasticBandit k) (π : BanditPolicy k)
(τ : (ℕ → Fin k × ℝ) → ℕ∞) (hτ : IsBanditStoppingTime τ)
(hfinite : ∫⁻ ω, (τ ω : ℝ≥0∞) ∂banditTrajMeasure ν π < ⊤)
(A : Set (ℕ → Fin k × ℝ)) (hA : Measurable[hτ.measurableSpace] A)
(hinfo : (∑ i, (∫⁻ ω, ∑' t : ℕ,
if (t : ℕ∞) < τ ω ∧ (ω t).1 = i then (1 : ℝ≥0∞) else 0
∂banditTrajMeasure ν π) * klDiv (ν.P i) (ν'.P i)) ≠ ⊤) :
(2 : ℝ)⁻¹ * Real.exp
(-(∑ i, (∫⁻ ω, ∑' t : ℕ,
if (t : ℕ∞) < τ ω ∧ (ω t).1 = i then (1 : ℝ≥0∞) else 0
∂banditTrajMeasure ν π) * klDiv (ν.P i) (ν'.P i)).toReal) ≤
(banditTrajMeasure ν π).real Aᶜ +
(banditTrajMeasure ν' π).real A := by
sorrySource
Lattimore--Szepesvári, Bandit Algorithms (CUP 2020), Exercise 15.7, printed p. 211 (stopping-time extension of Lemma 15.1), combined with Theorem 14.2, printed pp. 190--191 (Bretagnolle--Huber).