cs.LGMay 28, 2024

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

Authors: Yige Hong, Qiaomin Xie, Yudong Chen, Weina Wang

Organizations: Computer Science Department, Carnegie Mellon University · Department of Industrial and Systems Engineering, University of Wisconsin-Madison · Department of Computer Sciences, University of Wisconsin-Madison

Abstract

We consider the infinite-horizon average-reward restless bandit problem. We propose a novel 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 LP-Priority 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))O(\exp(-C N)) optimality gap for an NN-armed problem, under the assumptions of aperiodic-unichain, non-degeneracy, and local stability. Our policy is the first to achieve exponential asymptotic optimality under the above set of easy-to-verify assumptions, whereas prior work either requires a global attractor assumption or only achieves an O(1/N)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 restless bandit problems and performs competitively overall.

Figures & tables

Explore similar work

CardsList
  1. A single algorithm for both restless and rested rotting bandits

    Apr 23, 2026Julien Seznec, Pierre Ménard, Alessandro Lazaric +1Multi-Armed BanditsNon-Stationary Bandits

  2. Bridging Rested and Restless Bandits with Graph-Triggering: Rising and Rotting

    Sep 9, 2024Gianmarco Genalti, Marco Mussi, Nicola Gatti +3Multi-Armed BanditsGraph Bandits