# Exponential Convergence Rate for the Asymptotic Optimality of Whittle Index Policy

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Dec 2020.

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

- [Restless Bandits with Average Reward: Breaking the Uniform Global Attractor Assumption](https://mlsanity.com/paper/2306.00196/) (2023)
- [Contextual Restless Multi-Armed Bandits with Application to Demand Response Decision-Making](https://mlsanity.com/paper/2403.15640/) (2024)
- [Unichain and Aperiodicity are Sufficient for Asymptotic Optimality of Average-Reward Restless Bandits](https://mlsanity.com/paper/2402.05689/) (2024)
- [Global Rewards in Restless Multi-Armed Bandits](https://mlsanity.com/paper/2406.00738/) (2024)
- [Achieving Exponential Asymptotic Optimality in Average-Reward Restless Bandits without Global Attractor Assumption](https://mlsanity.com/paper/2405.17882/) (2024)

## Abstract (arXiv)

We evaluate the performance of Whittle index policy for restless Markovian bandits, when the number of bandits grows. It is proven in [30] that this performance is asymptotically optimal if the bandits are indexable and the associated deterministic system has a global attractor fixed point. In this paper we show that, under the same conditions, the convergence rate is exponential in the number of bandits, unless the fixed point is singular (to be defined later). Our proof is based on the nature of the deterministic equation governing the stochastic system: We show that it is a piecewise affine continuous dynamical system inside the simplex of the empirical measure of the bandits. Using simulations and numerical solvers, we also investigate the cases where the conditions for the exponential rate theorem are violated, notably when attracting limit cycles appear, or when the fixed point is singular. We illustrate our theorem on a Markovian fading channel model, which has been well studied in the literature. Finally, we extend our synchronous model results to the asynchronous model.