Flexible Budgets in Restless Bandits: A Primal-Dual Algorithm for Efficient Budget Allocation
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 plann…