Multi-armed Bandit with Additional Observations
Authors:
Open Access
- 3 April 2018
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Measurement and Analysis of Computing Systems
- Vol. 2 (1) , 1-22
Abstract
We study multi-armed bandit (MAB) problems with additional observations, where in each round, the decision maker selects an arm to play and can also observe rewards of additional arms (within a given budget) by paying certain costs. In the case of stochastic rewards, we develop a new algorithm KL-UCB-AO which is asymptotically optimal when the time horizon grows large, by smartly identifying the optimal set of the arms to be explored using the given budget of additional observations. In the case of adversarial rewards, we propose H-INF, an algorithm with order-optimal regret. H-INF exploits a two-layered structure where in each layer, we run a known optimal MAB algorithm. Such a hierarchical structure facilitates the regret analysis of the algorithm, and in turn, yields order-optimal regret. We apply the framework of MAB with additional observations to the design of rate adaptation schemes in 802.11-like wireless systems, and to that of online advertisement systems. In both cases, we demonstrate that our algorithms leverage additional observations to significantly improve the system performance. We believe the techniques developed in this paper are of independent interest for other MAB problems, e.g., contextual or graph-structured MAB.Keywords
Funding Information
- ERC Consolidator (308267)
- National ResearchFoundation of Kore (No. 2016R1A2A2A05921755)
- ICT R&D program of MSIP/IITP (2016-0-00563)
This publication has 16 references indexed in Scilit:
- Online Controlled Experiments2015
- Bayesian Incentive-Compatible Bandit Exploration2015
- Bandits with Budgets2015
- Stochastic bandits with side observations on networks2014
- Incentivizing exploration2014
- The Nonstochastic Multiarmed Bandit ProblemSIAM Journal on Computing, 2002
- A Decision-Theoretic Generalization of On-Line Learning and an Application to BoostingJournal of Computer and System Sciences, 1997
- How to use expert adviceJournal of the ACM, 1997
- Asymptotically efficient adaptive allocation rulesAdvances in Applied Mathematics, 1985
- Some aspects of the sequential design of experimentsBulletin of the American Mathematical Society, 1952