Journal
IEEE TRANSACTIONS ON INFORMATION THEORY
Volume 56, Issue 11, Pages 5547-5567Publisher
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/TIT.2010.2068950
Keywords
Dynamic channel selection; indexability; myopic policy; opportunistic access; restless multiarmed bandit (RMAB); Whittle index
Funding
- Army Research Office [W911NF-08-1-0467]
- National Science Foundation [ECS-0622200, CCF-0830685]
- Direct For Computer & Info Scie & Enginr [830685] Funding Source: National Science Foundation
- Division of Computing and Communication Foundations [830685] Funding Source: National Science Foundation
Ask authors/readers for more resources
In this paper, we consider a class of restless multiarmed bandit processes (RMABs) that arises in dynamic multichannel access, user/server scheduling, and optimal activation in multiagent systems. For this class of RMABs, we establish the indexability and obtain Whittle index in closed form for both discounted and average reward criteria. These results lead to a direct implementation of Whittle index policy with remarkably low complexity. When arms are stochastically identical, we show that Whittle index policy is optimal under certain conditions. Furthermore, it has a semiuniversal structure that obviates the need to know the Markov transition probabilities. The optimality and the semiuniversal structure result from the equivalence between Whittle index policy and the myopic policy established in this work. For nonidentical arms, we develop efficient algorithms for computing a performance upper bound given by Lagrangian relaxation. The tightness of the upper bound and the near-optimal performance of Whittle index policy are illustrated with simulation examples.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available