Adaptivity to Smoothness in X-armed bandits


Andrea Locatelli, Alexandra Carpentier ;
Proceedings of the 31st Conference On Learning Theory, PMLR 75:1463-1492, 2018.


We study the stochastic continuum-armed bandit problem from the angle of adaptivity to \emph{unknown regularity} of the reward function $f$. We prove that there exists no strategy for the cumulative regret that adapts optimally to the \emph{smoothness} of $f$. We show however that such minimax optimal adaptive strategies exist if the learner is given \emph{extra-information} about $f$. Finally, we complement our positive results with matching lower bounds.

Related Material