Multi-Armed Bandits in Metric Spaces

Abstract

In a multi-armed bandit problem, an online algorithm chooses from a set of strategies in a sequence of trials so as to maximize the total payoff of the chosen strategies. While the performance of bandit algorithms with a small finite strategy set is quite well understood, bandit problems with large strategy sets are still a topic of very active investigation, motivated by practical applications such as online auctions and web advertisement. The goal of such research is to identify broad and natural classes of strategy sets and payoff functions which enable the design of efficient solutions. In this work we study a very general setting for the multi-armed bandit problem in which the strategies form a metric space, and the payoff function satisfies a Lipschitz condition with respect to the metric. We refer to this problem as the "Lipschitz MAB problem". We present a complete solution for the multi-armed problem in this setting. That is, for every metric space (L,X) we define an isometry invariant which bounds from below the performance of Lipschitz MAB algorithms for X, and we present an algorithm which comes arbitrarily close to meeting this bound. Furthermore, our technique gives even better results for benign payoff functions.

16 pages, 0 figures

Cited by in corpus (29)

• From Bandits to Experts: On the Value of Side-Observations
• Resourceful Contextual Bandits
• On Kernelized Multi-armed Bandits
• Bandits with concave rewards and convex knapsacks
• Adaptive-treed bandits
• Unimodal Bandits without Smoothness
• Learning to Optimize Via Posterior Sampling
• Non-Stationary Bandits with Habituation and Recovery Dynamics
• Ranked bandits in metric spaces: learning optimally diverse rankings over large document collections
• Selective Call Out and Real Time Bidding
• Correlational Dueling Bandits with Application to Clinical Treatment in Large Decision Spaces
• Linearly Parameterized Bandits
• Multi-Objective Generalized Linear Bandits
• Stochastic Process Bandits: Upper Confidence Bounds Algorithms via Generic Chaining
• Characterizing Truthful Multi-Armed Bandit Mechanisms
• Multi-Objective Simultaneous Optimistic Optimization
• Nearly Optimal Regret for Stochastic Linear Bandits with Heavy-Tailed Payoffs
• Discovering Valuable Items from Massive Data
• Stream-based Online Active Learning in a Contextual Multi-Armed Bandit Framework
• Toward a Classification of Finite Partial-Monitoring Games
• Continuum armed bandit problem of few variables in high dimensions
• Be Greedy in Multi-Armed Bandits
• Continuous Assortment Optimization with Logit Choice Probabilities under Incomplete Information
• Bandit Market Makers
• Thompson Sampling for Unimodal Bandits
• Coarse-Grained Smoothness for RL in Metric Spaces
• Contextual Multi-armed Bandits for the Prevention of Spam in VoIP Networks
• Gaussian Process Bandits for Tree Search: Theory and Application to Planning in Discounted MDPs
• Truthful Mechanisms with Implicit Payment Computation