# Q-Learning Lagrange Policies for Multi-Action Restless Bandits

arXiv: https://arxiv.org/abs/2106.12024 · HTML: https://mlsanity.com/paper/2106.12024/

## Key facts

- Cited by 21 papers in the map (data through 14 Oct 2026).
- Builds on 5 of its 34 references that are in the map.
- First posted on arXiv 22 Jun 2021.

## Builds on (most cited first, 5 of 5)

- [Collapsing Bandits and Their Application to Public Health Interventions](https://mlsanity.com/paper/2007.04432/) (2020)
- [Whittle index based Q-learning for restless bandits with average reward](https://mlsanity.com/paper/2004.14427/) (2020)
- [Learn to Intervene: An Adaptive Learning Policy for Restless Bandits in Application to Preventive Healthcare](https://mlsanity.com/paper/2105.07965/) (2021)
- [Learning to Prescribe Interventions for Tuberculosis Patients Using Digital Adherence Data](https://mlsanity.com/paper/1902.01506/) (2019)
- [Learning in Restless Multi-Armed Bandits via Adaptive Arm Sequencing Rules](https://mlsanity.com/paper/1906.08120/) (2019)

## Built on by (most cited first, 21 of 21)

- [Field Study in Deploying Restless Multi-Armed Bandits: Assisting Non-Profits in Improving Maternal and Child Health](https://mlsanity.com/paper/2109.08075/) (2021)
- [Optimistic Whittle Index Policy: Online Learning for Restless Bandits](https://mlsanity.com/paper/2205.15372/) (2022)
- [Finite-Time Analysis of Whittle Index based Q-Learning for Restless Multi-Armed Bandits with Neural Network Function Approximation](https://mlsanity.com/paper/2310.02147/) (2023)
- [Indexability is Not Enough for Whittle: Improved, Near-Optimal Algorithms for Restless Bandits](https://mlsanity.com/paper/2211.00112/) (2022)
- [Online Restless Multi-Armed Bandits with Long-Term Fairness Constraints](https://mlsanity.com/paper/2312.10303/) (2023)
- [Towards a Pretrained Model for Restless Bandits via Multi-arm Generalization](https://mlsanity.com/paper/2310.14526/) (2023)
- [Restless and Uncertain: Robust Policies for Restless Bandits via Deep Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2107.01689/) (2021)
- [DeepTOP: Deep Threshold-Optimal Policy for MDPs and RMABs](https://mlsanity.com/paper/2209.08646/) (2022)
- [Weakly Coupled Deep Q-Networks](https://mlsanity.com/paper/2310.18803/) (2023)
- [Evaluating the Effectiveness of Index-Based Treatment Allocation](https://mlsanity.com/paper/2402.11771/) (2024)
- [The Bandit Whisperer: Communication Learning for Restless Bandits](https://mlsanity.com/paper/2408.05686/) (2024)
- [Tabular and Deep Learning for the Whittle Index](https://mlsanity.com/paper/2406.02057/) (2024)
- [Projection-based Lyapunov method for fully heterogeneous weakly-coupled MDPs](https://mlsanity.com/paper/2502.06072/) (2025)
- [Fairness of Exposure in Online Restless Multi-armed Bandits](https://mlsanity.com/paper/2402.06348/) (2024)
- [Deep reinforcement learning for weakly coupled MDP's with continuous actions](https://mlsanity.com/paper/2406.01099/) (2024)
- [Whittle Index Learning Algorithms for Restless Bandits with Constant Stepsizes](https://mlsanity.com/paper/2409.04605/) (2024)
- [Online Learning of Whittle Indices for Restless Bandits with Non-Stationary Transition Kernels](https://mlsanity.com/paper/2506.18186/) (2025)
- [Structured Reinforcement Learning for Delay-Optimal Data Transmission in Dense mmWave Networks](https://mlsanity.com/paper/2404.16920/) (2024)
- [From Restless to Contextual: A Thresholding Bandit Reformulation For Finite-horizon Improvement](https://mlsanity.com/paper/2502.05145/) (2025)
- [Age-of-information minimization under energy harvesting and non-stationary environment](https://mlsanity.com/paper/2504.04916/) (2025)
- [MARBLE: Multi-Armed Restless Bandits in Latent Markovian Environment](https://mlsanity.com/paper/2511.09324/) (2025)

## Abstract (arXiv)

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 trightarrow∞. 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-performing and more general Lagrange policy for multi-action RMABs by learning to minimize the Lagrange bound through a variant of Q-learning. To ensure fast convergence, we take an approximation strategy that enables learning on a single timescale, then give a guarantee relating the approximation's precision to an upper bound of LPQL's return as trightarrow∞. Finally, we show that our approaches always outperform baselines across multiple settings, including one derived from real-world medication adherence data.