NeurIPS 2019poster16 citations
Polynomial Cost of Adaptation for X-Armed Bandits
Abstract
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, 2018, 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.
BibTeX
@inproceedings{NEURIPS2019_d7a728a6,
author = {Hadiji, Hedi},
booktitle = {Advances in Neural Information Processing Systems},
editor = {H. Wallach and H. Larochelle and A. Beygelzimer and F. d\textquotesingle Alch\'{e}-Buc and E. Fox and R. Garnett},
pages = {},
publisher = {Curran Associates, Inc.},
title = {Polynomial Cost of Adaptation for X-Armed Bandits},
url = {https://proceedings.neurips.cc/paper_files/paper/2019/file/d7a728a67d909e714c0774e22cb806f2-Paper.pdf},
volume = {32},
year = {2019}
}