# Global Rewards in Restless Multi-Armed Bandits

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 39 references that are in the map.
- First posted on arXiv 2 Jun 2024.

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

- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Playing Atari with Deep Reinforcement Learning](https://mlsanity.com/paper/1312.5602/) (2013)
- [Collapsing Bandits and Their Application to Public Health Interventions](https://mlsanity.com/paper/2007.04432/) (2020)
- [Field Study in Deploying Restless Multi-Armed Bandits: Assisting Non-Profits in Improving Maternal and Child Health](https://mlsanity.com/paper/2109.08075/) (2021)
- [Submodular Reinforcement Learning](https://mlsanity.com/paper/2307.13372/) (2023)
- [Optimistic Whittle Index Policy: Online Learning for Restless Bandits](https://mlsanity.com/paper/2205.15372/) (2022)
- [Combinatorial Stochastic-Greedy Bandit](https://mlsanity.com/paper/2312.08057/) (2023)
- [Opportunistic Scheduling as Restless Bandits](https://mlsanity.com/paper/1706.09778/) (2017)
- [Adversarial Combinatorial Bandits with General Non-linear Reward Functions](https://mlsanity.com/paper/2101.01301/) (2021)
- [Indexability is Not Enough for Whittle: Improved, Near-Optimal Algorithms for Restless Bandits](https://mlsanity.com/paper/2211.00112/) (2022)
- [I Will Have Order! Optimizing Orders for Fair Reviewer Assignment](https://mlsanity.com/paper/2108.02126/) (2021)
- [Learning in Restless Bandits under Exogenous Global Markov Process](https://mlsanity.com/paper/2112.09484/) (2021)
- [Matching Algorithms for Blood Donation](https://mlsanity.com/paper/2108.04862/) (2021)
- [Algorithms for slate bandits with non-separable reward functions](https://mlsanity.com/paper/2004.09957/) (2020)
- [Exponential Convergence Rate for the Asymptotic Optimality of Whittle Index Policy](https://mlsanity.com/paper/2012.09064/) (2020)
- [Networked Restless Bandits with Positive Externalities](https://mlsanity.com/paper/2212.05144/) (2022)

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

- [Reinforcement learning with combinatorial actions for coupled restless bandits](https://mlsanity.com/paper/2503.01919/) (2025)
- [DeepOFW: Deep Learning-Driven OFDM-Flexible Waveform Modulation for Peak-to-Average Power Ratio Reduction](https://mlsanity.com/paper/2603.23544/) (2026)
- [Multi-agent Markov Entanglement](https://mlsanity.com/paper/2506.02385/) (2025)
- [Contextual Budget Bandit for Food Rescue Volunteer Engagement](https://mlsanity.com/paper/2509.10777/) (2025)
- [RescueLens: LLM-Powered Triage and Action on Volunteer Feedback for Food Rescue](https://mlsanity.com/paper/2511.15698/) (2025)
- [Distributed Learning in Markovian Restless Bandits over Interference Graphs for Stable Spectrum Sharing](https://mlsanity.com/paper/2512.17161/) (2025)

## Abstract (arXiv)

Restless multi-armed bandits (RMAB) extend multi-armed bandits so pulling an arm impacts future states. Despite the success of RMABs, a key limiting assumption is the separability of rewards into a sum across arms. We address this deficiency by proposing restless-multi-armed bandit with global rewards (RMAB-G), a generalization of RMABs to global non-separable rewards. To solve RMAB-G, we develop the Linear- and Shapley-Whittle indices, which extend Whittle indices from RMABs to RMAB-Gs. We prove approximation bounds but also point out how these indices could fail when reward functions are highly non-linear. To overcome this, we propose two sets of adaptive policies: the first computes indices iteratively, and the second combines indices with Monte-Carlo Tree Search (MCTS). Empirically, we demonstrate that our proposed policies outperform baselines and index-based policies with synthetic data and real-world data from food rescue.