On the Myopic Policy for a Class of Restless Bandit Problems with Applications in Dynamic Multichannel Access
Abstract
We consider a class of restless multi-armed bandit problems that arises in multi-channel opportunistic communications, where channels are modeled as independent and stochastically identical Gilbert-Elliot channels and channel state observations are subject to errors. We show that the myopic channel selection policy has a semi-universal structure that obviates the need to know the Markovian transition probabilities of the channel states. Based on this semi-universal structure, we establish closed-form lower and upper bounds on the maximum throughput (i.e., average reward) achieved by the myopic policy. Furthermore, we characterize the approximation factor of the myopic policy by considering a genie-aided system.
Document Details
- Document Type
- Technical Report
- Publication Date
- Mar 01, 2009
- Accession Number
- ADA554809
Entities
People
- Keqin Liu
- Qing Zhao
Organizations
- University of California