How well can any algorithm possibly do? Chapters 13–17 of Lattimore–Szepesvári answer with three matching impossibility results. The divergence decomposition identifies the information a policy collects: . Feeding it into the Bretagnolle–Huber inequality of Mission VI yields the goal theorem — the minimax lower bound over Gaussian bandits, showing MOSS (Mission III) is optimal up to a constant. The same machinery gives the instance-dependent bound of Lai–Robbins type: every consistent policy suffers , certifying the asymptotic optimality of the UCB of Mission III and KL-UCB of Mission IV, and a high-probability lower bound showing the Exp3-IX guarantees of Mission V cannot be improved.
theorem BanditAlgorithm.bandit_minimax_lower_bound {k n : ℕ} (hk : 1 < k) (hn : k - 1 ≤ n)
(π : BanditPolicy k) :
∃ μvec : Fin k → ℝ, (∀ i, μvec i ∈ Set.Icc (0 : ℝ) 1) ∧
Real.sqrt (((k : ℝ) - 1) * n) / 27 ≤
banditRegret (gaussianBandit μvec) π n := by
sorry
(Minimax lower bound, GOAL) Let and . For any policy there exists a mean vector such that on the unit-variance Gaussian bandit ,
No open leaves. Every sub-goal is proved or awaiting decomposition.