# Restless and Uncertain: Robust Policies for Restless Bandits via Deep Multi-Agent Reinforcement Learning

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 51 references that are in the map.
- First posted on arXiv 4 Jul 2021.

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

- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Multi-Agent Actor-Critic for Mixed Cooperative-Competitive Environments](https://mlsanity.com/paper/1706.02275/) (2017)
- [The Surprising Effectiveness of PPO in Cooperative, Multi-Agent Games](https://mlsanity.com/paper/2103.01955/) (2021)
- [Attention, Learn to Solve Routing Problems!](https://mlsanity.com/paper/1803.08475/) (2018)
- [Learning Combinatorial Optimization Algorithms over Graphs](https://mlsanity.com/paper/1704.01665/) (2017)
- [Robust Adversarial Reinforcement Learning](https://mlsanity.com/paper/1703.02702/) (2017)
- [A Unified Game-Theoretic Approach to Multiagent Reinforcement Learning](https://mlsanity.com/paper/1711.00832/) (2017)
- [Algorithms for multi-armed bandit problems](https://mlsanity.com/paper/1402.6028/) (2014)
- [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)
- [Regret Bounds for Thompson Sampling in Episodic Restless Bandit Problems](https://mlsanity.com/paper/1905.12673/) (2019)
- [Restless-UCB, an Efficient and Low-complexity Algorithm for Online Restless Bandits](https://mlsanity.com/paper/2011.02664/) (2020)
- [Q-Learning Lagrange Policies for Multi-Action Restless Bandits](https://mlsanity.com/paper/2106.12024/) (2021)
- [Thompson Sampling in Non-Episodic Restless Bandits](https://mlsanity.com/paper/1910.05654/) (2019)
- [Learning in Restless Multi-Armed Bandits via Adaptive Arm Sequencing Rules](https://mlsanity.com/paper/1906.08120/) (2019)
- [Robust Reinforcement Learning Under Minimax Regret for Green Security](https://mlsanity.com/paper/2106.08413/) (2021)
- [Policy Gradient Optimization of Thompson Sampling Policies](https://mlsanity.com/paper/2006.16507/) (2020)
- [Solving Continual Combinatorial Selection via Deep Reinforcement Learning](https://mlsanity.com/paper/1909.03638/) (2019)

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

- [A Decision-Language Model (DLM) for Dynamic Restless Multi-Armed Bandit Tasks in Public Health](https://mlsanity.com/paper/2402.14807/) (2024)
- [Towards a Pretrained Model for Restless Bandits via Multi-arm Generalization](https://mlsanity.com/paper/2310.14526/) (2023)
- [Equitable Restless Multi-Armed Bandits: A General Framework Inspired By Digital Health](https://mlsanity.com/paper/2308.09726/) (2023)
- [Robust Optimization with Diffusion Models for Green Security](https://mlsanity.com/paper/2503.05730/) (2025)
- [Projection-based Lyapunov method for fully heterogeneous weakly-coupled MDPs](https://mlsanity.com/paper/2502.06072/) (2025)
- [DOPL: Direct Online Preference Learning for Restless Bandits with Preference Feedback](https://mlsanity.com/paper/2410.05527/) (2024)
- [The Evidence Ladder for Reinforcement Learning in Healthcare: From Retrospective Policies to Trusted Interventions](https://mlsanity.com/paper/2609.23374/) (2026)

## Abstract (arXiv)

We introduce robustness in textitrestless multi-armed bandits (RMABs), a popular model for constrained resource allocation among independent stochastic processes (arms). Nearly all RMAB techniques assume stochastic dynamics are precisely known. However, in many real-world settings, dynamics are estimated with significant uncertainty, e.g., via historical data, which can lead to bad outcomes if ignored. To address this, we develop an algorithm to compute minimax regret -- robust policies for RMABs. Our approach uses a double oracle framework (oracles for textitagent and textitnature), which is often used for single-process robust planning but requires significant new techniques to accommodate the combinatorial nature of RMABs. Specifically, we design a deep reinforcement learning (RL) algorithm, DDLPO, which tackles the combinatorial challenge by learning an auxiliary "λ-network" in tandem with policy networks per arm, greatly reducing sample complexity, with guarantees on convergence. DDLPO, of general interest, implements our reward-maximizing agent oracle. We then tackle the challenging regret-maximizing nature oracle, a non-stationary RL challenge, by formulating it as a multi-agent RL problem between a policy optimizer and adversarial nature. This formulation is of general interest -- we solve it for RMABs by creating a multi-agent extension of DDLPO with a shared critic. We show our approaches work well in three experimental domains.