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

Richard Combes, Alexandre Proutière, Alexandre Fauquette

Abstract

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) and O(1/√T) (up to a logarithmic factor), respectively.
BibTeX
@article{combes2020unimodal,
  author = {Richard Combes and Alexandre Proutière and Alexandre Fauquette},
  title = {{Unimodal Bandits with Continuous Arms: Order-optimal Regret without Smoothness}},
  journal = {ACM SIGMETRICS Performance Evaluation Review},
  year = {2020},
  doi = {10.1145/3410048.3410110},
}

Loading related content...

Figure