Q-learning Lagrange Policies For Multi-action Restless Bandits
2021 · Jackson A. Killian, Arpita Biswas, Sanket Shah, et al.
Abstract
Multi-action restless multi-armed bandits (RMABs) are a powerful framework for constrained resource allocation in which \(N\) independent processes are managed. However, previous work only study the offline setting where problem dynamics are known. We address this restrictive assumption, designing the first algorithms for learning good policies for Multi-action RMABs online using combinations of Lagrangian relaxation and Q-learning. Our first approach, MAIQL, extends a method for Q-learning the Whittle index in binary-action RMABs to the multi-action setting. We derive a generalized update rule and convergence proof and establish that, under standard assumptions, MAIQL converges to the asymptotically optimal multi-action RMAB policy as \(t\rightarrow\{\}\infty\). However, MAIQL relies on learning Q-functions and indexes on two timescales which leads to slow convergence and requires problem structure to perform well. Thus, we design a second algorithm, LPQL, which learns the well-perfor
Authors
(none)
Tags
Stats
Related papers
- Provably Efficient Reinforcement Learning For Adversarial Restless Multi-armed Bandits With Unknown Transitions And Bandit Feedback (2024)0.00
- GINO-Q: Learning An Asymptotically Optimal Index Policy For Restless Multi-armed Bandits (2024)0.00
- Finite-time Analysis Of Whittle Index Based Q-learning For Restless Multi-armed Bandits With Neural Network Function Approximation (2023)0.00
- Towards A Pretrained Model For Restless Bandits Via Multi-arm Generalization (2023)0.00
- Multi-action Restless Bandits With Weakly Coupled Constraints: Simultaneous Learning And Control (2024)0.00
- Learning In Restless Bandits Under Exogenous Global Markov Process (2021)6.34
- MA2QL: A Minimalist Approach To Fully Decentralized Multi-agent Reinforcement Learning (2022)0.00
- Online Learning For Cooperative Multi-player Multi-armed Bandits (2021)5.24