Chernoff's stopping rule is well formed
ProvedBanditAlgorithm.chernoff_stopping_rule_wellformedbanditsbest-arm-identificationmeasurabilitystopping-time
Chernoff's stopping rule is a well-formed learner: for and , the rule
of Lattimore--Szepesv'ari Algorithm 21, line 3, is a stopping time of the natural filtration ; the recommendation of line 11 is -measurable; and on the pair satisfies with a maximiser of .
This is the measurability half of Definition 33.4, which soundness presupposes. The -measurability of is the delicate part, since is built from an arbitrary choice of maximiser: it is recovered from , which forces and hence a unique maximiser at the stopping round.
Preamble
import Definitions.Def_TrackAndStop import Definitions.Def_GaussianBandit open MeasureTheory ProbabilityTheory InformationTheory NNReal ENNReal Filter
Formal statement
theorem BanditAlgorithm.chernoff_stopping_rule_wellformed {k : ℕ} [NeZero k] (hk : 0 < k)
{δ : ℝ} (hδ : 0 < δ) :
∃ hτ : BanditAlgorithm.IsBanditStoppingTime
(BanditAlgorithm.chernoffStoppingTime (k := k) δ),
Measurable[hτ.measurableSpace] (BanditAlgorithm.chernoffRecommendation (k := k) δ) ∧
∀ ω : ℕ → Fin k × ℝ, BanditAlgorithm.chernoffStoppingTime (k := k) δ ω < ⊤ →
∃ n : ℕ, ENNReal.ofReal (BanditAlgorithm.chernoffThreshold k δ n)
≤ BanditAlgorithm.trajGLR n ω ∧
∀ j, BanditAlgorithm.trajEmpiricalMean j n ω
≤ BanditAlgorithm.trajEmpiricalMean
(BanditAlgorithm.chernoffRecommendation (k := k) δ ω) n ω := by
sorrySource
Measurability and well-formedness of the learner of Lattimore & Szepesvari, Bandit Algorithms (CUP 2020), Algorithm 21, lines 3 and 11 (Section 33.2.2). Definition 33.4 presupposes these; the book does not verify them.