Distributed Stochastic Online Learning Policies for Opportunistic Spectrum Access
Authors:
- 29 September 2014
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Signal Processing
- Vol. 62 (23) , 6184-6193
Abstract
The fundamental problem of multiple secondary users contending for opportunistic spectrum access over multiple channels in cognitive radio networks has been formulated recently as a decentralized multi-armed bandit (D-MAB) problem. In a D-MAB problem there are $M$ users and $N$ arms (channels) that each offer i.i.d. stochastic rewards with unknown means so long as they are accessed without collision. The goal is to design distributed online learning policies that incur minimal regret. We consider two related problem formulations in this paper. First, we consider the setting where the users have a prioritized ranking, such that it is desired for the $K$ -th-ranked user to learn to access the arm offering the $K$ -th highest mean reward. For this problem, we present DLP, the first distributed policy that yields regret that is uniformly logarithmic over time without requiring any prior assumption about the mean rewards. Second, we consider the case when a fair access policy is required, i.e., it is desired for all users to experience the same mean reward. For this problem, we present DLF, a distributed policy that yields order-optimal regret scaling with respect to the number of users and arms, better than previously proposed policies in the literature. Both of our distributed policies make use of an innovative modification of the well-known UCB1 policy for the classic multi-armed bandit problem that allows a single user to learn how to play the arm that yields the $K$ $K$ -th largest mean reward.
Keywords
Funding Information
- National Science Foundation
This publication has 17 references indexed in Scilit:
- Opportunistic spectrum access in unslotted primary systemsJournal of the Franklin Institute, 2012
- Multi-channel opportunistic spectrum access in unslotted primary systems with unknown models2011
- Learning with the Bandit: A Cooperative Spectrum Selection Scheme for Cognitive Radio Networks2011
- Distributed Algorithms for Learning and Cognitive Medium Access with Logarithmic RegretIEEE Journal on Selected Areas in Communications, 2011
- Distributed Learning in Multi-Armed Bandit With Multiple PlayersIEEE Transactions on Signal Processing, 2010
- A survey of spectrum sensing algorithms for cognitive radio applicationsIEEE Communications Surveys & Tutorials, 2009
- Asymptotically efficient allocation rules for the multiarmed bandit problem with multiple plays-Part I: I.I.D. rewardsIEEE Transactions on Automatic Control, 1987
- 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
- Convergence of Stochastic Processes1984