Unimodal Bandits with Continuous Arms: Order-optimal Regret without Smoothness

摘要

We consider stochastic bandit problems with a continuous set of arms and where the expected reward is a continuous and unimodal function of the arm. For these problems, we propose the Stochastic Polychotomy (SP) algorithms, and derive finite-time upper bounds on their regret and optimization error. We show that, for a class of reward functions, the SP algorithm achieves a regret and an optimization error with optimal scalings, i.e., O(T~(1/2)) and O(1/T~(1/2)) (up to a logarithmic factor), respectively.