Lipschitz Bandits: Regret Lower Bounds and Optimal Algorithms

Abstract

We consider stochastic multi-armed bandit problems where the expected reward is a Lipschitz function of the arm, and where the set of arms is either discrete or continuous. For discrete Lipschitz bandits, we derive asymptotic problem specific lower bounds for the regret satisfied by any algorithm, and propose OSLB and CKL-UCB, two algorithms that efficiently exploit the Lipschitz structure of the problem. In fact, we prove that OSLB is asymptotically optimal, as its asymptotic regret matches the lower bound. The regret analysis of our algorithms relies on a new concentration inequality for weighted sums of KL divergences between the empirical distributions of rewards and their true distributions. For continuous Lipschitz bandits, we propose to first discretize the action space, and then apply OSLB or CKL-UCB, algorithms that provably exploit the structure efficiently. This approach is shown, through numerical experiments, to significantly outperform existing algorithms that directly deal with the continuous set of arms. Finally the results and algorithms are extended to contextual bandits with similarities.

COLT 2014

Cited by in corpus (20)

• Online Learning: A Comprehensive Survey
• Combinatorial Bandits Revisited
• Optimal Best Arm Identification with Fixed Confidence
• Minimal Exploration in Structured Stochastic Bandits
• Exploration in Structured Reinforcement Learning
• Multiple-Play Bandits in the Position-Based Model
• Mixture Martingales Revisited with Applications to Sequential Tests and Confidence Intervals
• Unimodal Bandits without Smoothness
• Learning the distribution with largest mean: two bandit frameworks
• Pure Exploration in Infinitely-Armed Bandit Models with Fixed-Confidence
• Max-Utility Based Arm Selection Strategy For Sequential Query Recommendations
• Forced-exploration free Strategies for Unimodal Bandits
• Non-Asymptotic Pure Exploration by Solving Games
• (Almost) Free Incentivized Exploration from Decentralized Learning Agents
• A Novel Confidence-Based Algorithm for Structured Bandits
• Fundamental Limits of Online Network-Caching
• Transfer Learning in Bandits with Latent Continuity
• Discriminative Learning via Adaptive Questioning
• Optimal Strategies for Graph-Structured Bandits
• Indexed Minimum Empirical Divergence for Unimodal Bandits