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.

arXiv comment13 pages, NIPS 2017

References in corpus (7)

• On the Complexity of Best Arm Identification in Multi-Armed Bandit Models
• Thompson Sampling for Contextual Bandits with Linear Payoffs
• The KL-UCB Algorithm for Bounded Stochastic Bandits and Beyond
• The on-line shortest path problem under partial monitoring
• Tight Regret Bounds for Stochastic Combinatorial Semi-Bandits
• Lipschitz Bandits: Regret Lower Bounds and Optimal Algorithms
• Regret Lower Bound and Optimal Algorithm in Dueling Bandit Problem

Cited by in corpus (10)

• Exploration in Structured Reinforcement Learning
• Mixture Martingales Revisited with Applications to Sequential Tests and Confidence Intervals
• Pure Exploration with Multiple Correct Answers
• Fair Exploration via Axiomatic Bargaining
• Information Directed Sampling for Sparse Linear Bandits
• Bounded Regret for Finitely Parameterized Multi-Armed Bandits
• Accelerated learning from recommender systems using multi-armed bandit
• Experimental Design for Regret Minimization in Linear Bandits
• Constant or logarithmic regret in asynchronous multiplayer bandits
• Indexed Minimum Empirical Divergence for Unimodal Bandits