Opportunistic Scheduling Revisited Using Restless Bandits: Indexability and Index Policy

We revisit the opportunistic scheduling problem in which a server opportunistically serves multiple classes of users under time-varying multi-state Markovian channels. The aim of the server is to find an optimal policy minimizing the average waiting cost of those users. Mathematically, the problem can be recast to a restless multiarmed bandit one, and a pivot to solve restless bandit by the Whittle index approach is to establish indexability. Despite the theoretical and practical importance of the Whittle index policy, the indexability is still open for opportunistic scheduling in the heterogeneous multi-state channel case. To fill this gap, we mathematically identify a set of sufficient conditions on a channel state transition matrix under which the indexability is guaranteed and consequently, the Whittle index policy is feasible. Furthermore, we obtain the closed-form Whittle index by exploiting the structural property of the channel state transition matrix. For a generic channel state transition matrix, we propose an eigenvalue-arithmetic-mean scheme to obtain the corresponding approximate matrix which satisfies the sufficient conditions, and consequently can get an approximate Whittle index. This paper constitutes a small step toward solving the opportunistic scheduling problem in its generic form involving multi-state Markovian channels and multi-class users.