Exponential Convergence Rate for the Asymptotic Optimality of Whittle Index Policy

Nicolas Gast, Bruno Gaujal, Chen YanarXiv 2020 · arXiv

Abstract

The Whittle Index Policy (WIP) is a prominent heuristic for addressing the Restless Multi-Armed Bandit (RMAB) problem, which is known to be PSPACE-hard. While WIP has been proven asymptotically optimal as the number of bandits $N$ grows, the specific rate of convergence remained largely unquantified, with many assuming a standard polynomial rate of $O(1/\sqrt{N})$. This paper proves that under common stability and non-singularity conditions, the performance gap between WIP and the optimal policy actually vanishes exponentially fast ($e^{-cN}$). This result highlights the efficiency of WIP in large-scale stochastic systems.

Introduction

Multi-armed bandit (MAB) problems are fundamental in decision-making under uncertainty. In the Restless MAB (RMAB) variant, the states of all arms evolve over time, regardless of whether they are activated. This added complexity makes optimal solutions computationally intractable for large systems. The Whittle Index Policy (WIP) offers a scalable alternative by assigning a dynamic index to each arm and prioritizing those with the highest values. While its asymptotic optimality was established decades ago, this research provides the first proof of its exponential convergence rate.

Theoretical Framework

The authors' proof strategy bridges stochastic processes with deterministic dynamical systems through several key pillars:

  1. Mean-Field Approximation: The system is modeled by a configuration vector representing the proportion of bandits in each state. As $N \to \infty$, the stochastic evolution of this vector converges to a deterministic map $\phi$.
  2. Piecewise Affine Dynamics: A critical insight is that WIP partitions the state space into polytopes. Within each region, the system's drift is affine (linear plus a constant). Although the system is non-smooth at the boundaries, its linear nature within regions allows for rapid error decay.
  3. Stein’s Method and Concentration Inequalities: The authors use Stein’s method to bound the distance between the stochastic system and its mean-field limit. They employ Hoeffding’s and exponential martingale inequalities to show that the system remains tightly concentrated around its global attractor.

The Non-Singular Requirement

The transition from polynomial to exponential convergence hinges on the location of the system's fixed point relative to the decision boundaries created by the WIP.

Comparison of singular (left) and non-singular (right) fixed points in the state space partition.

As shown in the figure above, a singular fixed point (left) lies exactly on the boundary between two decision zones ($\mathcal{Z}_1, \mathcal{Z}_2, \mathcal{Z}_3$). In such cases, the convergence rate reverts to the standard $O(1/\sqrt{N})$. Conversely, a non-singular fixed point (right) resides within the interior of a zone. Once the system enters this zone, the piecewise affine nature of the dynamics ensures that the error vanishes at an exponential rate.

Key Results and Validation

The core theoretical contributions are Theorems 3.2 and 6.2, which establish the $b \cdot e^{-cN}$ bound for synchronous and asynchronous models, respectively.

To validate these findings, the authors conducted extensive numerical experiments:

  • Statistical Prevalence: In tests of $10^7$ randomly generated 3-state RMAB instances, over 99.8% satisfied the conditions for exponential convergence. The likelihood of meeting these conditions increases with the number of states.
  • Performance Scaling: Simulations of a 3-state model showed a linear relationship between the log-scale performance gap and $N$, directly confirming exponential decay.
  • Application Benchmarks: The theory was successfully applied to the Markovian Fading Channel Model (Gilbert-Elliott model), a standard benchmark in telecommunications.

Limitations and Future Directions

Despite the strength of the exponential convergence result, certain edge cases remain:

  • Singular Points and Chaos: While rare, singular points lead to slower convergence. Furthermore, if the deterministic system enters a "limit cycle" or exhibits chaotic behavior instead of settling at a fixed point, WIP may fail to be asymptotically optimal.
  • Discretization Effects: The exponential rate assumes the ability to activate exactly $\alpha N$ bandits. In practice, rounding $\alpha N$ to an integer can introduce $O(1/N)$ errors if not handled carefully.
  • Multi-Action Extensions: Future work may extend these proofs to multi-action restless bandits, where arms have more complex state-action spaces.

Summary updated

Abstract

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.
BibTeX
@misc{gast2020exponential,
  author = {Nicolas Gast and Bruno Gaujal and Chen Yan},
  title = {{Exponential Convergence Rate for the Asymptotic Optimality of Whittle Index Policy}},
  year = {2020},
  eprint = {2012.09064},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2012.09064},
}
Figure