Asymptotically optimal priority policies for indexable and nonindexable restless bandits

Abstract

We study the asymptotic optimal control of multi-class restless bandits. A restless bandit is a controllable stochastic process whose state evolution depends on whether or not the bandit is made active. Since finding the optimal control is typically intractable, we propose a class of priority policies that are proved to be asymptotically optimal under a global attractor property and a technical condition. We consider both a fixed population of bandits as well as a dynamic population where bandits can depart and arrive. As an example of a dynamic population of bandits, we analyze a multi-class $M/M/S+M$ queue for which we show asymptotic optimality of an index policy. We combine fluid-scaling techniques with linear programming results to prove that when bandits are indexable, Whittle's index policy is included in our class of priority policies. We thereby generalize a result of Weber and Weiss [J. Appl. Probab. 27 (1990) 637-648] about asymptotic optimality of Whittle's index policy to settings with (i) several classes of bandits, (ii) arrivals of new bandits and (iii) multiple actions. Indexability of the bandits is not required for our results to hold. For nonindexable bandits, we describe how to select priority policies from the class of asymptotically optimal policies and present numerical evidence that, outside the asymptotic regime, the performance of our proposed priority policies is nearly optimal.

Published at http://dx.doi.org/10.1214/15-AAP1137 in the Annals of Applied Probability (http://www.imstat.org/aap/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (2)

• Dynamic priority allocation via restless bandit marginal productivity indices
• General notions of indexability for queueing control and asset management

Cited by in corpus (21)

• Timely Communications for Remote Inference
• Markovian restless bandits and index policies: A review
• LP-based policies for restless bandits: necessary and sufficient conditions for (exponentially fast) asymptotic optimality
• A Verification Theorem for Threshold-Indexability of Real-State Discounted Restless Bandits
• Testing Indexability and Computing Whittle and Gittins Index in Subcubic Time
• Restless-UCB, an Efficient and Low-complexity Algorithm for Online Restless Bandits
• A fast-pivoting algorithm for Whittle's restless bandit index
• Learning Augmented Index Policy for Optimal Service Placement at the Network Edge
• Tabular and Deep Learning for the Whittle Index
• Simulation Based Algorithms for Markov Decision Processes and Multi-Action Restless Bandits
• Whittle Index Based User Association in Dense Millimeter Wave Networks
• Bandit Learning with Delayed Impact of Actions
• Relaxed Indexability and Index Policy for Partially Observable Restless Bandits
• Reinforcement Learning for Finite-Horizon Restless Multi-Armed Multi-Action Bandits
• A Restless Bandit Model for Resource Allocation, Competition and Reservation
• A unifying computations of Whittle's Index for Markovian bandits
• Energy-Efficient Job-Assignment Policy with Asymptotically Guaranteed Performance Deviation
• Unichain and Aperiodicity are Sufficient for Asymptotic Optimality of Average-Reward Restless Bandits
• A Restless Bandit Model for Dynamic Ride Matching with Reneging Travelers
• Asymptotically Optimal Policies for Weakly Coupled Markov Decision Processes
• Lagrangian Index Policy for Restless Bandits with Average Reward