Flexible Budgets in Restless Bandits: A Primal-Dual Algorithm for Efficient Budget Allocation
Paula Rodriguez Diaz, Jackson A. Killian, Lily Xu, Arun Sai Suggala, Aparna Taneja, Milind Tambe
Abstract
Restless multi-armed bandits (RMABs) are an important model to optimize allocation of limited resources in sequential decision-making settings. Typical RMABs assume the budget --- the number of arms pulled --- to be fixed for each step in the planning horizon. However, for realistic real-world planning, resources are not necessarily limited at each planning step; we may be able to distribute surplus resources in one round to an earlier or later round. In real-world planning settings, this flexibility in budget is often constrained to within a subset of consecutive planning steps, e.g., weekly planning of a monthly budget. In this paper we define a general class of RMABs with flexible budget, which we term F-RMABs, and provide an algorithm to optimally solve for them. We derive a min-max formulation to find optimal policies for F-RMABs and leverage gradient primal-dual algorithms to solve for reward-maximizing policies with flexible budgets. We introduce a scheme to sample expected gradients to apply primal-dual algorithms to the F-RMAB setting and make an otherwise computationally expensive approach tractable. Additionally, we provide heuristics that trade off solution quality for efficiency and present experimental comparisons of different F-RMAB solution approaches.
BibTeX
@article{Rodriguez Diaz_Killian_Xu_Suggala_Taneja_Tambe_2023, title={Flexible Budgets in Restless Bandits: A Primal-Dual Algorithm for Efficient Budget Allocation}, volume={37}, url={https://ojs.aaai.org/index.php/AAAI/article/view/26427}, DOI={10.1609/aaai.v37i10.26427}, abstractNote={Restless multi-armed bandits (RMABs) are an important model to optimize allocation of limited resources in sequential decision-making settings. Typical RMABs assume the budget --- the number of arms pulled --- to be fixed for each step in the planning horizon. However, for realistic real-world planning, resources are not necessarily limited at each planning step; we may be able to distribute surplus resources in one round to an earlier or later round. In real-world planning settings, this flexibility in budget is often constrained to within a subset of consecutive planning steps, e.g., weekly planning of a monthly budget. In this paper we define a general class of RMABs with flexible budget, which we term F-RMABs, and provide an algorithm to optimally solve for them. We derive a min-max formulation to find optimal policies for F-RMABs and leverage gradient primal-dual algorithms to solve for reward-maximizing policies with flexible budgets. We introduce a scheme to sample expected gradients to apply primal-dual algorithms to the F-RMAB setting and make an otherwise computationally expensive approach tractable. Additionally, we provide heuristics that trade off solution quality for efficiency and present experimental comparisons of different F-RMAB solution approaches.}, number={10}, journal={Proceedings of the AAAI Conference on Artificial Intelligence}, author={Rodriguez Diaz, Paula and Killian, Jackson A. and Xu, Lily and Suggala, Arun Sai and Taneja, Aparna and Tambe, Milind}, year={2023}, month={Jun.}, pages={12103-12111} }