Adaptivity to Smoothness in X-armed bandits

Andrea Locatelli, Alexandra Carpentier

Conference on Learning Theory · 2018 · 33 citations · 0 references

Concepts

Abstract

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