Title: Minimal Exploration in Structured Stochastic Bandits,
Abstract: This paper introduces and addresses a wide class of stochastic bandit
problems where the function mapping the arm to the corresponding reward
exhibits some known structural properties. Most existing structures (e.g.
linear, Lipschitz, unimodal, combinatorial, dueling, ...) are covered by our
framework. We derive an asymptotic instance-specific regret lower bound for
these problems, and develop OSSB, an algorithm whose regret matches this
fundamental limit. OSSB is not based on the classical principle of "optimism in
the face of uncertainty" or on Thompson sampling, and rather aims at matching
the minimal exploration rates of sub-optimal arms as characterized in the
derivation of the regret lower bound. We illustrate the efficiency of OSSB
using numerical experiments in the case of the linear bandit problem and show
that OSSB outperforms existing algorithms, including Thompson sampling.