BanditAlgorithm.bandit_asymptotically_optimal_ucb_regret_bound
Provedbanditsregretucb
(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 .
Preamble
import Definitions.Def_banditRegret import Definitions.Def_asymptoticUcbPolicy import Mathlib.Analysis.SpecialFunctions.Trigonometric.Basic open MeasureTheory ProbabilityTheory
Formal statement
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
Source
L&S Theorem 8.1, Eq. (8.1), p.117