Explicit stochastic convex-bandit regret rate
DefinitionLG2021_RegretRateconvex-analysisonline-learningprobability
For dimension , horizon , and diameter , define
This is the explicit rate in Theorems 1 and 2 of Lattimore and György (COLT 2021). The Lean expression uses and for the fractional powers. This entry defines the rate; the regret guarantee is proved in the corresponding theorem entries.
Definition code
import Mathlib
noncomputable section
namespace LG2021
/-- The explicit dimension, horizon, and diameter dependence in the regret bound. -/
def sharpRate (d : ℕ) (D : ℝ) (n : ℕ) : ℝ :=
(d : ℝ) ^ 4 * Real.sqrt d * Real.sqrt n *
(Real.log ((n : ℝ) * D) * Real.sqrt (Real.log ((n : ℝ) * D))) *
max 1 (Real.sqrt (Real.log ((n : ℝ) * D)) / (d : ℝ))
end LG2021
Source
Tor Lattimore and András György, Improved Regret for Zeroth-Order Stochastic Convex Bandits, Proceedings of the 34th Conference on Learning Theory (COLT 2021), Proceedings of Machine Learning Research 134:2938–2964, 2021, Theorems 1 and 2, printed p. 1.