The basic UCB regret bound of Mission II is logarithmic but not tight: its leading constant is eight times the information-theoretic limit, and its worst-case rate carries a spurious . Chapters 8–9 of Lattimore–Szepesvári close both gaps. A refined confidence schedule yields the asymptotically optimal — exactly matching the instance-dependent lower bound of Mission VII for Gaussian noise. The MOSS index achieves minimax regret , matching the lower bound up to a constant. These two theorems are the gold standard for finite-armed stochastic bandits.
theorem BanditAlgorithm.bandit_asymptotically_optimal_ucb_regret_bound {k : ℕ}
{ν : StochasticBandit k} (hν : IsSubgaussianBandit 1 ν)
{π : BanditPolicy k} (hπ : IsAsymptoticUCBPolicy π) (n : ℕ)
(ε : Fin k → ℝ)
(hε : ∀ i, 0 < banditGap ν i → ε i ∈ Set.Ioo 0 (banditGap ν i)) :
banditRegret ν π n ≤
∑ i ∈ Finset.univ.filter (fun i ↦ 0 < banditGap ν i),
banditGap ν i *
(1 + 5 / ε i ^ 2 +
2 * (Real.log (asymptoticUcbSchedule n) +
Real.sqrt (Real.pi * Real.log (asymptoticUcbSchedule n)) + 1) /
(banditGap ν i - ε i) ^ 2) := by
sorry
(Asymptotically optimal UCB, finite-time, GOAL) For any 1-subgaussian -armed bandit and any policy that is an instance of Algorithm 6 (index with ), the regret satisfies
The per-arm infimum inside the sum is encoded in the equivalent -family form: the bound holds at every family with for each suboptimal arm .
No open leaves. Every sub-goal is proved or awaiting decomposition.