Online Learning of Rested and Restless Bandits
Authors:
- 16 May 2012
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 58 (8) , 5588-5611
Abstract
In this paper, we study the online learning problem involving rested and restless bandits, in both a centralized and a decentralized setting. In a centralized setting, the system consists of a single player/user and a set of K finite-state discrete-time Markov chains (arms) with unknown state spaces (rewards) and statistics. The objective of the player is to decide in each step which M of the K arms to play over a sequence of trials so as to maximize its long-term reward. In a decentralized setting, multiple uncoordinated players each makes its own decision on which arm to play in a step, and if two or more players select the same arm simultaneously, a collision results and none of the players selecting that arm gets a reward. The objective of each player again is to maximize its long-term reward. We first show that logarithmic regret algorithms exist both for the centralized rested and restless bandit problems. For the decentralized setting, we propose an algorithm with logarithmic regret with respect to the optimal centralized arm allocation. Numerical results and extensive discussion are also provided to highlight insights obtained from this study.Keywords
All Related Versions
This publication has 23 references indexed in Scilit:
- Approximation algorithms for restless bandit problemsJournal of the ACM, 2010
- Exploration–exploitation tradeoff using variance estimates in multi-armed banditsTheoretical Computer Science, 2009
- On the expectation of the maximum of IID geometric random variablesStatistics & Probability Letters, 2008
- The Nonstochastic Multiarmed Bandit ProblemSIAM Journal on Computing, 2002
- Chernoff-type bound for finite Markov chainsThe Annals of Applied Probability, 1998
- Sample mean based index policies byO(logn) regret for the multi-armed bandit problemAdvances in Applied Probability, 1995
- Restless bandits: activity allocation in a changing worldJournal of Applied Probability, 1988
- Asymptotically efficient allocation rules for the multiarmed bandit problem with multiple plays-Part II: Markovian rewardsIEEE Transactions on Automatic Control, 1987
- Asymptotically efficient adaptive allocation rulesAdvances in Applied Mathematics, 1985
- Some aspects of the sequential design of experimentsBulletin of the American Mathematical Society, 1952