Unimodal Bandits 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. 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.
