# Unichain and Aperiodicity are Sufficient for Asymptotic Optimality of Average-Reward Restless Bandits

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 29 references that are in the map.
- First posted on arXiv 8 Feb 2024.

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

- [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)
- [LP-based policies for restless bandits: necessary and sufficient conditions for (exponentially fast) asymptotic optimality](https://mlsanity.com/paper/2106.10067/) (2021)
- [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)
- [Exponential Convergence Rate for the Asymptotic Optimality of Whittle Index Policy](https://mlsanity.com/paper/2012.09064/) (2020)

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

- [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)
- [Lyapunov-Based Sample Complexity Analysis for Weakly-Coupled MDPs](https://mlsanity.com/paper/2606.14095/) (2026)
- [Achieving an O(1/N) Optimality Gap in Average-Reward Weakly-Coupled MDPs](https://mlsanity.com/paper/2609.38132/) (2026)

## Abstract (arXiv)

We consider the infinite-horizon, average-reward restless bandit problem in discrete time. We propose a new class of policies that are designed to drive a progressively larger subset of arms toward the optimal distribution. We show that our policies are asymptotically optimal with an O(1/√N) optimality gap for an N-armed problem, assuming only a unichain and aperiodicity assumption. Our approach departs from most existing work that focuses on index or priority policies, which rely on the Global Attractor Property (GAP) to guarantee convergence to the optimum, or a recently developed simulation-based policy, which requires a Synchronization Assumption (SA).