# Networked Restless Multi-Arm Bandits with Reinforcement Learning

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods.
- Builds on 10 of its 32 references that are in the map.
- First posted on arXiv 6 Dec 2025.

## Placed in

- Deep reinforcement learning methods / [RL theory and sample complexity](https://mlsanity.com/deeprl/rl-theory-and-sample-complexity/)

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

- [Learning Combinatorial Optimization Algorithms over Graphs](https://mlsanity.com/paper/1704.01665/) (2017)
- [Epidemic processes in complex networks](https://mlsanity.com/paper/1408.2701/) (2014)
- [Collapsing Bandits and Their Application to Public Health Interventions](https://mlsanity.com/paper/2007.04432/) (2020)
- [Efficient Resource Allocation with Fairness Constraints in Restless Multi-Armed Bandits](https://mlsanity.com/paper/2206.03883/) (2022)
- [Multi-Armed Bandits with Network Interference](https://mlsanity.com/paper/2405.18621/) (2024)
- [Networked Restless Multi-Armed Bandits for Mobile Interventions](https://mlsanity.com/paper/2201.12408/) (2022)
- [Active Screening for Recurrent Diseases: A Reinforcement Learning Approach](https://mlsanity.com/paper/2101.02766/) (2021)
- [Efficient Algorithms for Finite Horizon and Streaming Restless Multi-Armed Bandit Problems](https://mlsanity.com/paper/2103.04730/) (2021)
- [Networked Restless Bandits with Positive Externalities](https://mlsanity.com/paper/2212.05144/) (2022)
- [Multi-Bellman operator for convergence of Q-learning with linear function approximation](https://mlsanity.com/paper/2309.16819/) (2023)

## Abstract (arXiv)

Restless Multi-Armed Bandits (RMABs) are a powerful framework for sequential decision-making, widely applied in resource allocation and intervention optimization challenges in public health. However, traditional RMABs assume independence among arms, limiting their ability to account for interactions between individuals that can be common and significant in a real-world environment. This paper introduces Networked RMAB, a novel framework that integrates the RMAB model with the independent cascade model to capture interactions between arms in networked environments. We define the Bellman equation for networked RMAB and present its computational challenge due to exponentially large action and state spaces. To resolve the computational challenge, we establish the submodularity of Bellman equation and apply the hill-climbing algorithm to achieve a 1-frac1e approximation guarantee in Bellman updates. Lastly, we prove that the approximate Bellman updates are guaranteed to converge by a modified contraction analysis. We experimentally verify these results by developing an efficient Q-learning algorithm tailored to the networked setting. Experimental results on real-world graph data demonstrate that our Q-learning approach outperforms both k-step look-ahead and network-blind approaches, highlighting the importance of capturing and leveraging network effects where they exist.