Unimodal Bandits with Continuous Arms: Order-optimal Regret without Smoothness
Lists
Only you see this
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...