Bandits and Experts in Metric Spaces
Authors:
Top Cited Papers
Open Access
- 31 May 2019
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 66 (4) , 1-77
Abstract
In a multi-armed bandit problem, an online algorithm chooses from a set of strategies in a sequence of trials to maximize the total payoff of the chosen strategies. While the performance of bandit algorithms with a small finite strategy set is well understood, bandit problems with large strategy sets are still a topic of 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 that enable the design of efficient solutions. In this work, we study a 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 solution for the multi-armed bandit problem in this setting. That is, for every metric space, we define an isometry invariant that bounds from below the performance of Lipschitz MAB algorithms for this metric space, and we present an algorithm that comes arbitrarily close to meeting this bound. Furthermore, our technique gives even better results for benign payoff functions. We also address the full-feedback (“best expert”) version of the problem, where after every round the payoffs from all arms are revealed.Keywords
All Related Versions
Funding Information
- NSF (CCF-0643934, CCF-0729102, CCR-0121154 and DMI-0600384)
- ONR (N000140610607)
This publication has 50 references indexed in Scilit:
- Triangulation and embedding using small sets of beaconsJournal of the ACM, 2009
- Exploration–exploitation tradeoff using variance estimates in multi-armed banditsTheoretical Computer Science, 2009
- Online linear optimization and adaptive routingJournal of Computer and System Sciences, 2008
- A Game of Prediction with Expert AdviceJournal of Computer and System Sciences, 1998
- Bandit problems with infinitely many armsThe Annals of Statistics, 1997
- How to use expert adviceJournal of the ACM, 1997
- The Continuum-Armed Bandit ProblemSIAM Journal on Control and Optimization, 1995
- Asymptotically efficient adaptive allocation rulesAdvances in Applied Mathematics, 1985
- Some aspects of the sequential design of experimentsBulletin of the American Mathematical Society, 1952
- ON THE LIKELIHOOD THAT ONE UNKNOWN PROBABILITY EXCEEDS ANOTHER IN VIEW OF THE EVIDENCE OF TWO SAMPLESBiometrika, 1933