Stopped binary-testing information inequality for adaptive bandits
ProvedBanditAlgorithm.bandit_stopped_binary_testing_information_lower_boundbanditsinformation-theorylower-boundsstopping-times
Run the same adaptive bandit policy in two environments and , and stop at an almost surely integrable stopping time . Let be any event measurable from the stopped experiment. If the two testing errors satisfy
then the expected information collected before stopping obeys
Here . This is the stopping-time form of the canonical bandit divergence decomposition combined with the Bretagnolle--Huber binary-testing inequality.
Preamble
import Definitions.Def_BanditTrajectory open MeasureTheory ProbabilityTheory InformationTheory ENNReal
Formal statement
theorem BanditAlgorithm.bandit_stopped_binary_testing_information_lower_bound
{k : ℕ} (δ : ℝ) (hδ : δ ∈ Set.Ioo (0 : ℝ) 1)
(ν ν' : StochasticBandit k) (π : BanditPolicy k)
(τ : (ℕ → Fin k × ℝ) → ℕ∞) (hτ : IsBanditStoppingTime τ)
(hfinite : ∫⁻ ω, (τ ω : ℝ≥0∞) ∂banditTrajMeasure ν π < ⊤)
(A : Set (ℕ → Fin k × ℝ)) (hA : Measurable[hτ.measurableSpace] A)
(hνerr : (banditTrajMeasure ν π).real Aᶜ ≤ δ)
(hν'err : (banditTrajMeasure ν' π).real A ≤ δ) :
ENNReal.ofReal (Real.log (1 / (4 * δ))) ≤
∑ 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 Lemma 15.1), combined with Theorem 14.2, printed pp. 190--191 (Bretagnolle--Huber); used in Theorem 33.5, Eq. (33.6), printed p. 407.