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

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.