Stopped change-of-measure inequality for best-arm identification
ProvedBanditAlgorithm.best_arm_identification_stopping_change_of_measurebanditsbest-arm-identificationinformation-theorylower-boundsstopping-times
Let be a best-arm-identification strategy that is sound at confidence on an environment class . Fix and an alternative whose optimal arms are disjoint from those of . Assume the expected stopping time under is finite. If denotes the number of pulls of arm strictly before the stopping time, then
The inequality is understood in , so it also covers singular arm laws. This is the stopped-experiment information constraint used in every fixed-confidence best-arm-identification lower bound.
Formalization Note The stopped pull count is represented directly as the infinite sum of the indicators on the canonical infinite trajectory.
Preamble
import Definitions.Def_BanditTrajectory open MeasureTheory ProbabilityTheory InformationTheory ENNReal
Formal statement
theorem BanditAlgorithm.best_arm_identification_stopping_change_of_measure {k : ℕ}
(𝓔 : Set (StochasticBandit k)) (δ : ℝ) (hδ : δ ∈ Set.Ioo (0 : ℝ) 1)
(π : BanditPolicy k) (τ : (ℕ → Fin k × ℝ) → ℕ∞)
(ψ : (ℕ → Fin k × ℝ) → Fin k)
(hτ : IsBanditStoppingTime τ) (hψ : Measurable[hτ.measurableSpace] ψ)
(hsound : IsSoundBAI δ π τ ψ 𝓔)
(ν ν' : StochasticBandit k) (hν : ν ∈ 𝓔)
(hν' : ν' ∈ baiAlternatives 𝓔 ν)
(hfinite : ∫⁻ ω, (τ ω : ℝ≥0∞) ∂banditTrajMeasure ν π < ⊤) :
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 and Szepesvári, Bandit Algorithms (CUP 2020), Theorem 33.5 proof, printed p. 407, Eqs. (33.5)–(33.6), using the stopping-time version of Lemma 15.1 requested in Exercise 15.7, printed p. 211.