Unimodal Bandits without Smoothness

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. No further assumption is made regarding the smoothness and the structure of the expected reward function. For these problems, we propose the Stochastic Pentachotomy (SP) algorithm, and derive finite-time upper bounds on its regret and optimization error. In particular, we show that, for any expected reward function $\mu$ that behaves as $\mu (x)=\mu (x^{\star })-C|x-x^{\star }{|}^{\xi }$ locally around its maximizer $x^{\star }$ for some $\xi ,C>0$, the SP algorithm is order-optimal. Namely its regret and optimization error scale as $O(\sqrt{T\log (T)})$ and $O(\sqrt{\log (T)/T})$, respectively, when the time horizon $T$ grows large. These scalings are achieved without the knowledge of $\xi$ and $C$. Our algorithm is based on asymptotically optimal sequential statistical tests used to successively trim an interval that contains the best arm with high probability. To our knowledge, the SP algorithm constitutes the first sequential arm selection rule that achieves a regret and optimization error scaling as $O(\sqrt{T})$ and $O(1/\sqrt{T})$, respectively, up to a logarithmic factor for non-smooth expected reward functions, as well as for smooth functions with unknown smoothness.

25 pages

References in corpus (5)

• The KL-UCB Algorithm for Bounded Stochastic Bandits and Beyond
• lil' UCB : An Optimal Exploration Algorithm for Multi-Armed Bandits
• Query Complexity of Derivative-Free Optimization
• Lipschitz Bandits: Regret Lower Bounds and Optimal Algorithms
• Multi-Armed Bandits in Metric Spaces

Cited by in corpus (7)

• Optimal Best Arm Identification with Fixed Confidence
• Black-box optimization of noisy functions with unknown smoothness
• From self-tuning regulators to reinforcement learning and back again
• Learning the distribution with largest mean: two bandit frameworks
• Finite-Time Analysis of Round-Robin Kullback-Leibler Upper Confidence Bounds for Optimal Adaptive Allocation with Multiple Plays and Markovian Rewards
• The Influence of Shape Constraints on the Thresholding Bandit Problem
• Thompson Sampling for Unimodal Bandits