Introduction
Restless Bandits (RB) provide a versatile framework for sequential resource allocation, with applications ranging from sensor scheduling and clinical trials to communication network management. In a typical RB problem, an operator manages $N$ independent arms, each represented by a Markov Decision Process (MDP). At each time step, the operator can activate a fixed fraction of these arms. However, determining the exact optimal policy is PSPACE-hard, leading researchers to focus on asymptotic optimality—strategies where the reward gap relative to the theoretical maximum shrinks as the number of arms $N$ grows.
Historically, the literature has been divided into two regimes of convergence:
- The Exponential Regime: Policies that achieve an optimality gap of $O(e^{-CN})$. These results typically rely on the Uniform Global Attractor Property (UGAP), a condition requiring the system's fluid limit to converge globally to a unique equilibrium. Unfortunately, UGAP is notoriously difficult to verify in practice.
- The Square-Root Regime: Policies that do not require UGAP but are limited by the Central Limit Theorem (CLT), resulting in a much slower $O(1/\sqrt{N})$ convergence rate.
This paper bridges this gap by identifying the fundamental requirements for exponential optimality and proposing a novel policy that achieves it without the restrictive UGAP assumption.
The Stability Barrier
A central contribution of this research is the characterization of a "stability barrier." The authors prove that local stability is a necessary condition for exponential optimality. Specifically, for "regular unstable" restless bandits, they establish a lower bound showing that the optimality gap is at least $\Omega(1/\sqrt{N})$. This implies that if a system is locally unstable, the square-root convergence of the CLT is the best any policy can achieve. Conversely, this suggests that global convergence (UGAP) is not the requirement; rather, local stability around the optimal operating point is the key to unlocking exponential performance.
The Two-Set Policy
To achieve exponential optimality under local stability, the authors introduce the Two-Set Policy. This approach departs from traditional index-based or priority-based policies by dynamically partitioning the $N$ arms into two distinct groups:
- The Stable Set (Set 1): This group contains arms whose state distributions are already close to the optimal steady-state distribution. These arms are managed using an Optimal Local Control routine—a localized version of LP-priority control that leverages local linearity to maintain system stability.
- The Steering Set (Set 2): This group contains arms that have drifted significantly from the target distribution. These arms follow an Unconstrained Optimal Control routine designed to drive them back toward the stable region as rapidly as possible.
As the system evolves, the policy manages the flow between these sets. To prove the efficacy of this dual-structure approach, the authors developed a novel multivariate Lyapunov function technique. This mathematical framework allows for the decoupling of the complex interactions between individual arm transitions and the fluctuating sizes of the two sets, ultimately proving that the error shrinks exponentially with $N$.
Verification and Practical Performance
One of the primary advantages of this framework is its practical utility. The three assumptions required for the Two-Set Policy—aperiodic-unichain structure, non-degeneracy, and local stability—can be verified by examining the primitives of a single-arm MDP or the properties of a simple Linear Program (LP). This is a significant improvement over the global convergence requirements of UGAP.
In numerical simulations, the Two-Set Policy demonstrates robust performance:
- Non-UGAP Instances: In problems specifically designed to violate the Global Attractor assumption, traditional policies often fail to converge quickly. The Two-Set Policy, however, maintains an exponential decay in error, reaching near-zero optimality gaps almost immediately as $N$ increases.
- Randomized MDPs: When tested against randomly generated 8-state MDPs, the policy remains competitive with the Whittle Index—a popular heuristic—while providing the theoretical safety net of guaranteed exponential convergence.
Conclusion
This work redefines the boundaries of what is possible in Restless Bandit optimization. By demonstrating that local stability, rather than global attraction, is the threshold for exponential optimality, the authors provide both a new theoretical lower bound and a practical algorithm. While the Two-Set Policy involves higher computational overhead than simple index sorting (requiring the solution of Second-Order Conic Programs), it offers a mathematically rigorous path to beating the Central Limit Theorem in complex resource allocation problems.
Summary updated