Polynomial Cost of Adaptation for X -Armed Bandits

Coût de l'adaptation pour les bandits à continuum de bras

Hédi Hadiji (1, 2)

1 LMO - Laboratoire de Mathématiques d'Orsay
2 CELESTE - Statistique mathématique et apprentissage

In the context of stochastic continuum-armed bandits, we present an algorithm that adapts to the unknown smoothness of the objective function. We exhibit and compute a polynomial cost of adaptation to the Hölder regularity for regret minimization. To do this, we first reconsider the recent lower bound of Locatelli and Carpentier [20], and define and characterize admissible rate functions. Our new algorithm matches any of these minimal rate functions. We provide a finite-time analysis and a thorough discussion about asymptotic optimality.

Domaines: Machine Learning [stat.ML]; Apprentissage [cs.LG]; Statistiques [math.ST]

Hédi Hadiji. Polynomial Cost of Adaptation for X -Armed Bandits. NeurIPS 2019 - Thirty-third Conference on Neural Information Processing Systems, Dec 2019, Vancouver, Canada. ⟨hal-02138492v2⟩