# Restless Bandits with Many Arms: Beating the Central Limit Theorem

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

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- Builds on 2 of its 46 references that are in the map.
- First posted on arXiv 25 Jul 2021.

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

- [Algorithms with Logarithmic or Sublinear Regret for Constrained Contextual Bandits](https://mlsanity.com/paper/1504.06937/) (2015)
- [An Asymptotically Optimal Index Policy for Finite-Horizon Restless Bandits](https://mlsanity.com/paper/1707.00205/) (2017)

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

- [Indexability is Not Enough for Whittle: Improved, Near-Optimal Algorithms for Restless Bandits](https://mlsanity.com/paper/2211.00112/) (2022)
- [Online Restless Multi-Armed Bandits with Long-Term Fairness Constraints](https://mlsanity.com/paper/2312.10303/) (2023)
- [Near-optimality for infinite-horizon restless bandits with many arms](https://mlsanity.com/paper/2203.15853/) (2022)
- [Restless Bandits with Average Reward: Breaking the Uniform Global Attractor Assumption](https://mlsanity.com/paper/2306.00196/) (2023)
- [Towards a Pretrained Model for Restless Bandits via Multi-arm Generalization](https://mlsanity.com/paper/2310.14526/) (2023)
- [Unichain and Aperiodicity are Sufficient for Asymptotic Optimality of Average-Reward Restless Bandits](https://mlsanity.com/paper/2402.05689/) (2024)
- [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)
- [DOPL: Direct Online Preference Learning for Restless Bandits with Preference Feedback](https://mlsanity.com/paper/2410.05527/) (2024)
- [Model Predictive Control is Almost Optimal for Restless Bandit](https://mlsanity.com/paper/2410.06307/) (2024)
- [Finite-Horizon Single-Pull Restless Bandits: An Efficient Index Policy For Scarce Resource Allocation](https://mlsanity.com/paper/2501.06103/) (2025)
- [Model Predictive Control is almost Optimal for Heterogeneous Restless Multi-armed Bandits](https://mlsanity.com/paper/2511.08097/) (2025)
- [Reinforcement Learning for Finite-Horizon Restless Multi-Armed Multi-Action Bandits](https://mlsanity.com/paper/2109.09855/) (2021)
- [Structured Reinforcement Learning for Delay-Optimal Data Transmission in Dense mmWave Networks](https://mlsanity.com/paper/2404.16920/) (2024)
- [Optimal Control of Fluid Restless Multi-armed Bandits: A Machine Learning Approach](https://mlsanity.com/paper/2502.03725/) (2025)
- [From Restless to Contextual: A Thresholding Bandit Reformulation For Finite-horizon Improvement](https://mlsanity.com/paper/2502.05145/) (2025)
- [Multi-agent Markov Entanglement](https://mlsanity.com/paper/2506.02385/) (2025)
- [Achieving an O(1/N) Optimality Gap in Average-Reward Weakly-Coupled MDPs](https://mlsanity.com/paper/2609.38132/) (2026)

## Abstract (arXiv)

We consider finite-horizon restless bandits with multiple pulls per period, which play an important role in recommender systems, active learning, revenue management, and many other areas. While an optimal policy can be computed, in principle, using dynamic programming, the computation required scales exponentially in the number of arms N. Thus, there is substantial value in understanding the performance of index policies and other policies that can be computed efficiently for large N. We study the growth of the optimality gap, i.e., the loss in expected performance compared to an optimal policy, for such policies in a classical asymptotic regime proposed by Whittle in which N grows while holding constant the fraction of arms that can be pulled per period. Intuition from the Central Limit Theorem and the tightest previous theoretical bounds suggest that this optimality gap should grow like O(√N). Surprisingly, we show that it is possible to outperform this bound. We characterize a non-degeneracy condition and a wide class of novel practically-computable policies, called fluid-priority policies, in which the optimality gap is O(1). These include most widely-used index policies. When this non-degeneracy condition does not hold, we show that fluid-priority policies nevertheless have an optimality gap that is O(√N), significantly generalizing the class of policies for which convergence rates are known. We demonstrate that fluid-priority policies offer state-of-the-art performance on a collection of restless bandit problems in numerical experiments.