mlsanityData to 14 Oct 2026

Networked Restless Multi-Arm Bandits with Reinforcement Learning

arXiv 2512.06274 ↗First posted 6 Dec 2025cs.LG cs.AIcited by 0

On the map: Deep reinforcement learning methods → RL theory and sample complexity

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.

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.

Builds on

10 of 32 references.

References · 10

  1. 2017Learning Combinatorial Optimization Algorithms over Graphscited by 561
  2. 2014Epidemic processes in complex networkscited by 58
  3. 2020Collapsing Bandits and Their Application to Public Health Interventionscited by 47
  4. 2022Efficient Resource Allocation with Fairness Constraints in Restless Multi-Armed Banditscited by 11
  5. 2024Multi-Armed Bandits with Network Interferencecited by 8
  6. 2022Networked Restless Multi-Armed Bandits for Mobile Interventionscited by 7
  7. 2021Active Screening for Recurrent Diseases: A Reinforcement Learning Approachcited by 6
  8. 2021Efficient Algorithms for Finite Horizon and Streaming Restless Multi-Armed Bandit Problemscited by 6
  9. 2022Networked Restless Bandits with Positive Externalitiescited by 5
  10. 2023Multi-Bellman operator for convergence of Q-learning with linear function approximationcited by 3

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2024The Bandit Whisperer: Communication Learning for Restless Bandits
  2. 2026Restless Bandits with Individual Penalty Constraints: Near-Optimal Indices and Deep Reinforcement Learning
  3. 2024GINO-Q: Learning an Asymptotically Optimal Index Policy for Restless Multi-armed Bandits
  4. 2025Non-Stationary Restless Multi-Armed Bandits with Provable Guarantee
  5. 2024Provably Efficient Reinforcement Learning for Adversarial Restless Multi-Armed Bandits with Unknown Transitions and Bandit Feedback
  6. 2025MARBLE: Multi-Armed Restless Bandits in Latent Markovian Environment
  7. 2025Reinforcement learning with combinatorial actions for coupled restless bandits
  8. 2024EduQate: Generating Adaptive Curricula through RMABs in Education Settings