Sometimes reward during learning is irrelevant — a pharmaceutical company running phase-II trials only cares about identifying the best treatment, as quickly and as reliably as possible. Chapter 33 of Lattimore–Szepesvári formalizes fixed-confidence best-arm identification: a policy together with a stopping time and a recommendation must be sound (wrong with probability at most ) while minimizing . The information-theoretic complexity is : every sound strategy needs , and the Track-and-Stop algorithm — the goal theorem — achieves exactly. The mission also covers the fixed-budget counterpart, sequential halving.
theorem BanditAlgorithm.best_arm_identification_track_and_stop_optimality {k : ℕ} (hk : 0 < k) :
∃ (π : BanditPolicy k) (τ : ℝ → (ℕ → Fin k × ℝ) → ℕ∞)
(ψ : ℝ → (ℕ → Fin k × ℝ) → Fin k),
(∀ δ ∈ Set.Ioo (0 : ℝ) 1,
∃ hτ : IsBanditStoppingTime (τ δ),
Measurable[hτ.measurableSpace] (ψ δ) ∧
IsSoundBAI δ π (τ δ) (ψ δ) (Set.range (gaussianBandit (k := k)))) ∧
∀ ν ∈ Set.range (gaussianBandit (k := k)), (∃! i, i ∈ banditOptimalArms ν) →
Tendsto
(fun δ : ℝ ↦
(∫⁻ ω, (τ δ ω : ℝ≥0∞) ∂banditTrajMeasure ν π).toReal / Real.log (1 / δ))
(nhdsWithin 0 (Set.Ioi 0))
(nhds (baiComplexity ν (Set.range (gaussianBandit (k := k)))).toReal) := by
sorry
(Track-and-Stop asymptotic optimality, Theorem 33.6, GOAL) Over the class of unit-variance Gaussian bandits there exist a policy (independent of ) and, for each , a stopping time and an -measurable selection rule — Track-and-Stop, Algorithm 21, with the threshold of Lemma 33.7 — such that each triple is sound at confidence , and for every with a unique optimal arm,
No open leaves. Every sub-goal is proved or awaiting decomposition.