BanditAlgorithm.best_arm_identification_track_and_stop_optimality
Provedbanditsbest-armpure-explorationtrack-and-stop
(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,
Preamble
import Definitions.Def_BanditTrajectory import Definitions.Def_GaussianBandit open MeasureTheory ProbabilityTheory Filter ENNReal
Formal statement
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
Source
L&S Theorem 33.6, p.410