Learning and sharing in a changing world: Non-Bayesian restless bandit with multiple players
Authors:
- 1 February 2011
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 1-7
Abstract
We consider decentralized restless multi-armed bandit problems with unknown dynamics and multiple players. The reward state of each arm transits according to an unknown Markovian rule when it is played and evolves according to an arbitrary unknown random process when it is passive. Players activating the same arm at the same time collide and suffer from reward loss. The objective is to maximize the long-term reward by designing a decentralized arm selection policy to address unknown reward models and collisions among players. A decentralized policy is constructed that achieves a regret with logarithmic order. The result finds applications in communication networks, financial investment, and industrial engineering.Keywords
This publication has 13 references indexed in Scilit:
- The non-Bayesian restless multi-armed bandit: A case of near-logarithmic regret2011
- Distributed Algorithms for Learning and Cognitive Medium Access with Logarithmic RegretIEEE Journal on Selected Areas in Communications, 2011
- Online algorithms for the multi-armed bandit problem with Markovian rewards2010
- Distributed Learning in Multi-Armed Bandit With Multiple PlayersIEEE Transactions on Signal Processing, 2010
- A Chernoff bound for random walks on expander graphs2002
- Finite-time Analysis of the Multiarmed Bandit ProblemMachine Learning, 2002
- The Nonstochastic Multiarmed Bandit ProblemSIAM Journal on Computing, 2002
- The Complexity of Optimal Queuing Network ControlMathematics of Operations Research, 1999
- Sample mean based index policies byO(logn) regret for the multi-armed bandit problemAdvances in Applied Probability, 1995
- Asymptotically efficient allocation rules for the multiarmed bandit problem with multiple plays-Part II: Markovian rewardsIEEE Transactions on Automatic Control, 1987