Minimal Exploration in Structured Stochastic Bandits
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.
Problem Studied: The paper introduces and studies a wide range of stochastic bandit problem with known structural properties. This includes linear, lipschitz, unimodal, combinatorial, dueling bandits. 
Results: The paper derives an instance specific regret lower bound based on the structure and gives an algorithm which matches the lower bound. The algorithm needs to solve a semi-infinite LP in the general case, but they show that it can be efficiently done for special cases (which follows from previous literature).
Comments: The paper introduces a nice general framework for several of existing known results for several bandit problems such as linear, lipschitz, unimodal, combinatorial, dueling bandits. This encapsulates all these in very broad theoretical framework which can be useful for any new bandit problems.