A Restless Bandit Model for Resource Allocation, Competition, and Reservation

• Published in: Operations research 2022-01, Vol.70 (1), p.416-431
• Main Authors: Fu, Jing, Moran, Bill, Taylor, Peter G.
• Format: Article
• Language: English
• Subjects: Asymptotic methods; Asymptotic properties; Estimating techniques; Markov decision process; Numerical analysis; Operations research; Optimization; Resource allocation; resource sharing; restless bandits; Stochastic Models
• ISSN: 0030-364X; 1526-5463
• DOI: 10.1287/opre.2020.2066

In “A Restless Bandit Model for Resource Allocation, Competition and Reservation,” J. Fu, B. Moran, and P. G. Taylor study a resource allocation problem with varying requests and with resources of limited capacity shared by multiple requests. This problem is modeled as a set of heterogeneous restless multi-armed bandit problems (RMABPs) connected by constraints imposed by resource capacity. Following Whittle’s idea of relaxing the constraints and Weber and Weiss’s proof of asymptotic optimality, the authors propose an index policy and establish conditions for it to be asymptotically optimal in a regime where both arrival rates and capacities increase. In particular, they provide a simple sufficient condition for asymptotic optimality of the policy and, in complete generality, propose a method that generates a set of candidate policies for which asymptotic optimality can be checked. Via numerical experiments, they demonstrate the effectiveness of these results even in the pre-limit case. We study a resource allocation problem with varying requests and with resources of limited capacity shared by multiple requests. It is modeled as a set of heterogeneous restless multiarmed bandit problems (RMABPs) connected by constraints imposed by resource capacity. Following Whittle’s relaxation idea and Weber and Weiss’ asymptotic optimality proof, we propose a simple policy and prove it to be asymptotically optimal in a regime where both arrival rates and capacities increase. We provide a simple sufficient condition for asymptotic optimality of the policy and, in complete generality, propose a method that generates a set of candidate policies for which asymptotic optimality can be checked. The effectiveness of these results is demonstrated by numerical experiments. To the best of our knowledge, this is the first work providing asymptotic optimality results for such a resource allocation problem and such a combination of multiple RMABPs.