# Restless Bandits with Average Reward: Breaking the Uniform Global Attractor Assumption

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 34 references that are in the map.
- First posted on arXiv 31 May 2023.

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

- [Multi-armed Bandit Models for the Optimal Design of Clinical Trials: Benefits and Challenges](https://mlsanity.com/paper/1507.08025/) (2015)
- [An Asymptotically Optimal Index Policy for Finite-Horizon Restless Bandits](https://mlsanity.com/paper/1707.00205/) (2017)
- [Restless Bandits with Many Arms: Beating the Central Limit Theorem](https://mlsanity.com/paper/2107.11911/) (2021)
- [Indexability is Not Enough for Whittle: Improved, Near-Optimal Algorithms for Restless Bandits](https://mlsanity.com/paper/2211.00112/) (2022)
- [Near-optimality for infinite-horizon restless bandits with many arms](https://mlsanity.com/paper/2203.15853/) (2022)
- [Exponential Convergence Rate for the Asymptotic Optimality of Whittle Index Policy](https://mlsanity.com/paper/2012.09064/) (2020)

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

- [Unichain and Aperiodicity are Sufficient for Asymptotic Optimality of Average-Reward Restless Bandits](https://mlsanity.com/paper/2402.05689/) (2024)
- [The Gittins Index: A Design Principle for Decision-Making Under Uncertainty](https://mlsanity.com/paper/2506.10872/) (2025)
- [Achieving Exponential Asymptotic Optimality in Average-Reward Restless Bandits without Global Attractor Assumption](https://mlsanity.com/paper/2405.17882/) (2024)
- [Projection-based Lyapunov method for fully heterogeneous weakly-coupled MDPs](https://mlsanity.com/paper/2502.06072/) (2025)
- [Model Predictive Control is Almost Optimal for Restless Bandit](https://mlsanity.com/paper/2410.06307/) (2024)
- [Model Predictive Control is almost Optimal for Heterogeneous Restless Multi-armed Bandits](https://mlsanity.com/paper/2511.08097/) (2025)
- [Optimal Control of Fluid Restless Multi-armed Bandits: A Machine Learning Approach](https://mlsanity.com/paper/2502.03725/) (2025)
- [From Relaxed Indexability to Exact Indexability: A t-Step Approach for Partially Observable Restless Bandits](https://mlsanity.com/paper/2608.24167/) (2026)
- [Achieving an O(1/N) Optimality Gap in Average-Reward Weakly-Coupled MDPs](https://mlsanity.com/paper/2609.38132/) (2026)

## Abstract (arXiv)

We study the infinite-horizon restless bandit problem with the average reward criterion, in both discrete-time and continuous-time settings. A fundamental goal is to efficiently compute policies that achieve a diminishing optimality gap as the number of arms, N, grows large. Existing results on asymptotic optimality all rely on the uniform global attractor property (UGAP), a complex and challenging-to-verify assumption. In this paper, we propose a general, simulation-based framework, Follow-the-Virtual-Advice, that converts any single-armed policy into a policy for the original N-armed problem. This is done by simulating the single-armed policy on each arm and carefully steering the real state towards the simulated state. Our framework can be instantiated to produce a policy with an O(1/√N) optimality gap. In the discrete-time setting, our result holds under a simpler synchronization assumption, which covers some problem instances that violate UGAP. More notably, in the continuous-time setting, we do not require any additional assumptions beyond the standard unichain condition. In both settings, our work is the first asymptotic optimality result that does not require UGAP.