Indexability of Restless Bandit Problems and Optimality of Whittle Index for Dynamic Multichannel Access
Top Cited Papers
- 18 October 2010
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 56 (11), 5547-5567
- https://doi.org/10.1109/tit.2010.2068950
Abstract
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.Keywords
Other Versions
This publication has 33 references indexed in Scilit:
- Approximation algorithms for restless bandit problemsJournal of the ACM, 2010
- On the myopic policy for a class of restless bandit problems with applications in dynamic multichannel accessPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2009
- Some indexable families of restless bandit problemsAdvances in Applied Probability, 2006
- An index policy for a stochastic scheduling model with improving/deteriorating jobsNaval Research Logistics (NRL), 2002
- Error statistics in data transmission over fading channelsIEEE Transactions on Communications, 1998
- Discrete-Time Controlled Markov Processes with Average Cost Criterion: A SurveySIAM Journal on Control and Optimization, 1993
- What do discounted optima converge to?: A theory of discount rate asymptotics in economic modelsJournal of Economic Theory, 1991
- The Optimal Control of Partially Observable Markov Processes over the Infinite Horizon: Discounted CostsOperations Research, 1978
- The Optimal Control of Partially Observable Markov Processes over a Finite HorizonOperations Research, 1973
- Capacity of a Burst-Noise ChannelBell System Technical Journal, 1960