Definition: In this task, you are given a part of an article. Your task is to generate headline (title) for this text. Preferred headlines are under fifteen words.
Input: <lb>We consider stochastic bandit problems with a continuous set of arms and where the expected re-<lb>ward is a continuous and unimodal function of the arm. No further assumption is made regarding<lb>the smoothness and the structure of the expected reward function. For these problems, we propose<lb>the Stochastic Pentachotomy (SP) algorithm, and derive finite-time upper bounds on its regret and<lb>optimization error. In particular, we show that, for any expected reward function μ that behaves as<lb>μ(x) = μ(x)− C|x− x| locally around its maximizer x for some ξ, C > 0, the SP algorithm is<lb>order-optimal. Namely its regret and optimization error scale as O(<lb>√<lb>T log(T )) and O(<lb>√<lb>log(T )/T ),<lb>respectively, when the time horizon T grows large. These scalings are achieved without the knowledge<lb>of ξ and C. Our algorithm is based on asymptotically optimal sequential statistical tests used to suc-<lb>cessively trim an interval that contains the best arm with high probability. To our knowledge, the SP<lb>algorithm constitutes the first sequential arm selection rule that achieves a regret and optimization error<lb>scaling as O(<lb>√<lb>T ) and O(1/<lb>√<lb>T ), respectively, up to a logarithmic factor for non-smooth expected<lb>reward functions, as well as for smooth functions with unknown smoothness.

Unimodal Bandits without Smoothness