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 novel "two-set policy" for restless bandits that achieves exponential asymptotic optimality without requiring a strong global attractor assumption, a common bottleneck in prior work. This new policy is theoretically proven to be highly efficient and demonstrates superior performance in simulations compared to existing methods on challenging bandit problems.

What Problem Does This Paper Address?

The paper tackles the problem of optimizing decisions in a "restless bandit" (RB) setting. Imagine a system with many independent "arms" (like slot machines), each in a particular state. At each step, you can only activate a fixed fraction of these arms. The goal is to maximize the long-term average reward you get from activating arms, but with a twist: arms can become "restless," meaning they might transition to different states even if not activated. This makes optimizing decisions much harder than in standard multi-armed bandits.

A key challenge in RB problems is achieving "asymptotic optimality," meaning the policy's performance gets arbitrarily close to the best possible performance as the number of arms grows large. Even more desirable is "exponential asymptotic optimality," where the gap between the policy's performance and the optimal performance shrinks exponentially fast. Previous work achieved this but often relied on a strong, hard-to-verify "global attractor assumption." This paper aims to achieve exponential asymptotic optimality without this assumption, using milder, more verifiable conditions.

Methods

The core innovation is the two-set policy. This policy dynamically divides the N arms into two main groups at each time step:

  1. Optimal Local Control (DOL): This subset of arms is managed to maintain a near-optimal state distribution. They are controlled using a "local version" of LP-Priority, which is designed to be efficient when the arms are close to their ideal states.
  2. Unconstrained Optimal Control (D*): This subset of arms is actively steered towards the optimal state distribution. This subroutine helps the system globally converge to the desired state.

These two subroutines work in tandem. The Optimal Local Control ensures efficiency when arms are in good states, while the Unconstrained Optimal Control drives arms towards those good states. The policy also carefully manages a budget constraint, ensuring that the correct fraction of arms are activated at each step. The theoretical analysis relies on novel Lyapunov function techniques to analyze the complex dynamics of these two interacting subsets.

Datasets

Not discussed in the paper. The experiments use simulated RB instances, including:

  • Instances designed to satisfy the paper's assumptions but violate the global attractor assumption.
  • Uniformly randomly generated instances.

Key Insights and Ideas

  • Decoupling Dynamics for Efficiency: The paper shows that by splitting arms into two dynamically managed sets, one can achieve exponential asymptotic optimality. This suggests that a hybrid approach, balancing local optimization with global convergence, is powerful.
  • Local Stability is Crucial: The authors prove a lower bound showing that if "local stability" (one of their key assumptions) is violated, exponential asymptotic optimality is impossible for a large class of problems. This highlights the fundamental importance of this assumption.
  • Beyond Global Attractors: The work demonstrates that the strong global attractor assumption, while sufficient, is not necessary for achieving exponential asymptotic optimality, opening up new avenues for designing efficient RB policies.

Key Results

  • First Exponential Asymptotic Optimality without UGAP: The proposed "two-set policy" achieves an optimality gap of $O(\exp(-CN))$ under mild assumptions (aperiodic unichain, non-degeneracy, and local stability), which are easier to verify than the global attractor assumption.
  • Lower Bound on Local Stability: A lower bound of $\Omega(1/\sqrt{N})$ is proven for regular unstable restless bandits, demonstrating that local stability is essential for exponential asymptotic optimality.
  • Simulation Performance: In experiments, the two-set policy significantly outperforms existing policies on instances designed to challenge prior methods and performs competitively on random instances, often converging to near-optimal performance.

Limitations and Future Work

  • Constant C Characterization: The authors suggest further work to provide a more precise characterization of the constant $C$ in the $O(\exp(-CN))$ optimality gap bound.
  • Extending Lower Bounds: The paper proposes extending the lower bound analysis to RB instances that are not "regular unstable."
  • Practical Implementation: While the paper focuses on theoretical guarantees, future work could explore more detailed practical implementation aspects and computational efficiency.

Summary updated

Abstract

We consider the infinite-horizon average-reward restless bandit problem. We propose a novel \emph{two-set policy} that maintains two dynamic subsets of arms: one subset of arms has a nearly optimal state distribution and takes actions according to an Optimal Local Control routine; the other subset of arms is driven towards the optimal state distribution and gradually merged into the first subset. We show that our two-set policy is asymptotically optimal with an $O(exp(−CN))$ optimality gap for an N-armed problem, under the mild assumptions of aperiodic-unichain, non-degeneracy, and local stability. Our policy is the first to achieve \emph{exponential asymptotic optimality} under the above set of easy-to-verify assumptions, whereas prior work either requires a strong \emph{global attractor} assumption or only achieves an $O(1/\sqrt{N})$ optimality gap. We further discuss obstacles in weakening the assumptions by demonstrating examples where exponential asymptotic optimality is not achievable when any of the three assumptions is violated. Notably, we prove a lower bound for a large class of locally unstable restless bandits, showing that local stability is particularly fundamental for exponential asymptotic optimality. Finally, we use simulations to demonstrate that the two-set policy outperforms previous policies on certain RB problems and performs competitively overall.
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