Achieving Exponential Asymptotic Optimality in Average-Reward Restless Bandits without Global Attractor Assumption

Yige Hong, Qiaomin Xie, Yudong Chen, Weina Wang

TL;DR

This paper introduces a new "two-set policy" for a complex decision-making problem called the restless bandit problem. This policy achieves near-perfect performance (exponentially small optimality gap) without requiring a strong, hard-to-verify assumption that previous methods needed, making it more practical and broadly applicable.

What Problem Does This Paper Address?

Imagine you have a collection of independent systems (like machines in a factory, or wireless communication channels), each with its own state and the ability to perform one of two actions: "work" or "rest." However, there's a global constraint: you can only have a certain fraction of these systems working at any given time. The goal is to maximize the total "reward" (e.g., output, successful transmissions) over the long run. This is the essence of the Restless Bandit (RB) problem.

The challenge is that as the number of systems ($N$) grows, finding the absolute best strategy becomes computationally impossible. Researchers have developed policies that get close to optimal, but often with a trade-off: either the performance improvement is limited (an $O(1/\sqrt{N})$ gap, meaning the error decreases slowly with $N$), or they rely on a strong assumption called the "global attractor property" (UGAP). UGAP is mathematically convenient but difficult to check in practice. This paper asks: can we achieve the best possible performance (exponentially small gap, $O(\exp(-CN))$) without needing this UGAP assumption?

Methods

The authors propose a novel two-set policy. This policy dynamically divides the systems (arms) into two groups:

  1. DOL (Dynamic Optimal Local Control): Arms in this set are managed using a sophisticated local control strategy that aims to keep their states close to an ideal distribution.
  2. D* (Unconstrained Optimal Control): Arms in this set are managed using a simpler, unconstrained optimal strategy that would drive them towards the ideal distribution if they were alone.

The policy cleverly manages the transitions between these sets. Initially, some arms might be in D*, but they are encouraged to move towards DOL. As arms get closer to the ideal state distribution, they are moved into DOL. The key idea is that DOL will eventually encompass almost all arms, and when this happens, the local control strategy within DOL guarantees near-optimal performance.

This approach is built upon the Linear Programming (LP) relaxation framework, a standard tool in this field for analyzing performance guarantees. The authors also introduce and rely on three specific assumptions:

  • Aperiodic Unichain: Ensures that the underlying single-system dynamics are well-behaved and have a unique stable state.
  • Non-degeneracy: Guarantees the existence of a "fluid neutral state" where both actions (work and rest) are potentially optimal for a single system.
  • Local Stability: This is the crucial weaker assumption. It requires that the dynamics of the system, when controlled by a specific policy (related to the LP solution), are stable in a local sense. This is a relaxation of the stronger UGAP.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and experimental validation using simulated scenarios based on the problem setup.

Key Insights and Ideas

  • Breaking the UGAP Barrier: The most significant insight is demonstrating that the strong "global attractor property" (UGAP) is not necessary for achieving exponential asymptotic optimality. This opens the door to more practical policy design.
  • The Power of Two Sets: The dynamic partitioning of arms into two sets (DOL and D*) is a novel mechanism that allows for both exploration (driving arms towards the ideal) and exploitation (maintaining near-optimal performance once arms are close to ideal).
  • Local Stability is Key: The paper strongly emphasizes that "local stability" is a fundamental requirement for exponential optimality. They provide a lower bound showing that without it, performance is capped at $O(1/\sqrt{N})$.
  • Assumptions are Necessary: The authors argue that their three assumptions (aperiodic unichain, non-degeneracy, and local stability) are not only sufficient but also necessary for achieving exponential optimality within the LP relaxation framework.

Key Results

  • Theorem 3.1: The proposed two-set policy achieves an $O(\exp(-CN))$ optimality gap under the assumptions of aperiodic unichain, non-degeneracy, and local stability. This is the main theoretical contribution, proving exponential performance without UGAP.
  • Theorem 3.2: A lower bound of $\Omega(1/\sqrt{N})$ is established for a class of "regular unstable RBs" when local stability is violated. This highlights the necessity of the local stability assumption for exponential gains.
  • Experimental Validation: The paper's experiments show that the two-set policy outperforms existing methods when UGAP is not met but the paper's assumptions are, and remains competitive in general settings.

Limitations and Future Work

  • Assumptions: While the paper argues for the necessity of their assumptions within the LP relaxation framework, it would be interesting to explore if exponential optimality can be achieved with even weaker conditions or different analytical tools.
  • Generalization: The paper focuses on average-reward RBs. Extending these findings to other reward settings (e.g., discounted rewards) or more complex system dynamics could be a fruitful direction.
  • Practical Implementation: While the assumptions are more verifiable than UGAP, further research into efficient and robust methods for checking these conditions in real-world systems would be valuable.
  • Lower Bound Tightness: The paper establishes a lower bound for a specific class of RBs. Investigating if this lower bound holds more broadly or if tighter bounds can be derived for other scenarios is an open question.

Summary updated

Abstract

We study the infinite-horizon average-reward restless bandit (RB) problem, a representative class of problems within the broader framework of weakly-coupled Markov decision processes (MDPs). Each RB problem consists of $N$ MDPs coupled by a resource constraint. Existing computationally efficient policies either only achieve an $O(1/\sqrt{N})$ optimality gap or require a strong *global attractor assumption* to achieve an exponentially small $O(\exp(-C N))$ optimality gap. In this paper, we propose a novel *two-set policy* that achieves an $O(\exp(-C N))$ optimality gap under the weaker and easily verifiable assumptions of aperiodic unichain, non-degeneracy, and local stability. We further show that dropping *any* of these three assumptions precludes an exponential optimality gap, with local stability playing a particularly fundamental role as demonstrated by our lower bound. Finally, our experimental results confirm that the two-set policy outperforms existing policies when our assumptions are met but not the global attractor assumption, while remaining competitive across general settings.
BibTeX
@inproceedings{hong2025achieving,
  author = {Yige Hong and Qiaomin Xie and Yudong Chen and Weina Wang},
  title = {{Achieving Exponential Asymptotic Optimality in Average-Reward Restless Bandits without Global Attractor Assumption}},
  booktitle = {MLxOR @ NeurIPS},
  year = {2025},
  url = {https://openreview.net/forum?id=igPYJRM3Yi},
}
Figure