Indexability of Restless Bandit Problems and Optimality of Whittle Index for Dynamic Multichannel Access

By Keqin Liu, Qing Zhao. IEEE Transactions on Information Theory, 2008

401 citations recorded by the source corpus.

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.

Subfields: Computer Networks and Communications, Electrical and Electronic Engineering, Management Science and Operations Research

View Paper: https://www.semanticscholar.org/paper/cded72089e6c1d1e719352b07d6d648a79b7feda

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

In Electrical and Electronic Engineering

In Management Science and Operations Research

Citations in the corpus

Deep Multi-User Reinforcement Learning for Dynamic Spectrum Access in Multichannel Wireless Networks (2017, background): “The problem has been widely studied under multiarmed bandit (and variants) formulations in [7]–[9], [18]–[20] (and references therein), game theoretic and congestion control in [3], [21]–[26] and references therein, and matching theory in [2], [5], [27]–[29] and references therein.”
Age of Information: An Introduction and Survey (2020, background): “This low-complexity heuristic policy has been extensively used in the literature [167]–[169] and is known to have a strong performance in a range of applications [170], [171].”
Deep Multi-User Reinforcement Learning for Distributed Dynamic Spectrum Access (2017, methodology): “The primary users activity is modeled by Markovian processes as commonly assumed in the literature [3]–[6], [22]–[24], [26].”
Deep Reinforcement Learning for Dynamic Multichannel Access in Wireless Networks (2018, background): “In [10], the Whittle Index is obtained in closed-form for the case when P is known and all channels are independent but may follow different 2-state Markov chain models.”
Scheduling Policies for Minimizing Age of Information in Broadcast Wireless Networks (2018, background): “This low-complexity heuristic policy has been extensively used in the literature [29], [32], [43] and is known to have a strong performance in a range of applications [44], [45].”