Unichain and Aperiodicity are Sufficient for Asymptotic Optimality of
  Average-Reward Restless Bandits
Yige Hong Qiaomin Xie Yudong Chen Weina Wang
We consider the infinite-horizon, average-reward restless bandit problem in
discrete time. We propose a new class of policies that are designed to drive a
progressively larger subset of arms toward the optimal distribution. We show
that our policies are asymptotically optimal with an $O(1/\sqrt{N})$ optimality
gap for an $N$-armed problem, provided that the single-armed relaxed problem is
unichain and aperiodic. Our approach departs from most existing work that
focuses on index or priority policies, which rely on the Uniform Global
Attractor Property (UGAP) to guarantee convergence to the optimum, or a
recently developed simulation-based policy, which requires a Synchronization
Assumption (SA).