Restless-UCB, an Efficient and Low-complexity Algorithm for Online Restless Bandits

Siwei Wang, Longbo Huang, John Lui

Abstract

Researchers have developed Restless-UCB, the first algorithm for online restless bandits that achieves both sublinear regret and polynomial computational complexity. By exploiting the structural sparsity of birth-death Markov chains, the algorithm overcomes the exponential "curse of dimensionality" inherent in previous state-of-the-art methods. Restless-UCB utilizes a practical "explore-then-commit" framework to provide theoretical guarantees and superior empirical performance in real-world scenarios like wireless communication scheduling.

Introduction

In the classic Multi-Armed Bandit (MAB) problem, only the selected arm's state evolves. However, many real-world applications—such as job scheduling or wireless channel management—are better modeled as Restless Multi-Armed Bandits (RMAB). In RMAB, every arm’s state evolves according to its own Markov chain at every time step, regardless of whether it is pulled.

The "online" version of this problem is particularly challenging because the player does not know the transition probabilities or reward functions beforehand. Previous algorithms with theoretical guarantees, such as colored-UCRL2, suffered from exponential computational complexity and regret bounds tied to the game's "diameter," which grows exponentially with the number of arms and states. Restless-UCB addresses these flaws by providing a computationally efficient alternative with polynomial regret bounds.

Methodology

Restless-UCB operates on an explore-then-commit framework divided into two phases:

  1. Exploration Phase: The algorithm pulls each arm $i$ until it has observed every state $k$ at least $m(T)$ times, enabling a reliable empirical estimation of transition matrices and rewards.
  2. Exploitation Phase: The algorithm constructs a "carefully optimistic" offline instance ($\mathcal{R}'$). It employs Upper Confidence Bounds (UCB) for transitions to higher-reward states and Lower Confidence Bounds for transitions to lower-reward states.

The core innovation is the assumption of birth-death state Markov chains, where states only transition to immediate neighbors (e.g., state $k$ moves to $k-1, k,$ or $k+1$). This sparsity allows the authors to bypass exponential complexity. Furthermore, the optimistic offline construction requires only $O(N)$ time, a massive improvement over the exponential search required by previous methods.

Experimental Evaluation

The algorithm was evaluated using both synthetic and real-world datasets:

  • Synthetic Instances: Two-arm problems designed to test robustness against inaccurate prior estimations.
  • Wireless Communication Dataset: Modeling digital video broadcasting (DVB-SH) to handheld devices. This includes channel models for urban, suburban, and heavy tree-shadowed environments across S-band and L-band frequencies.

Key Results and Discussion

Restless-UCB achieves a regret upper bound of $\tilde{O}((N + M^3)T^{2/3})$, which is polynomial in the number of arms ($N$) and states ($M$). This eliminates the exponential factors that previously limited RMAB algorithms to small-scale problems.

Cumulative regret comparisons across synthetic instances and various wireless environments (Urban, Suburban, Heavy Tree-shadowed) in S-band and L-band.

In empirical tests, Restless-UCB demonstrated a massive computational speedup. For a 5-arm problem, Restless-UCB completed in just 5 seconds, whereas the previous state-of-the-art, colored-UCRL2, required over 35 hours (129,387 seconds). As shown in the figures above, Restless-UCB consistently outperformed Thompson Sampling and UCRL2 variants, exhibiting lower cumulative regret and higher stability across all tested environments.

Conclusion

By focusing on birth-death chains, Restless-UCB provides a scalable solution for online restless bandits. While the $T^{2/3}$ regret rate is slightly higher than the $T^{1/2}$ rate found in simpler bandit problems, it represents a necessary trade-off for achieving polynomial complexity. Future work may involve extending these polynomial bounds to more general sparse Markov structures beyond birth-death chains.

Summary updated

Abstract

We study the online restless bandit problem, where the state of each arm evolves according to a Markov chain, and the reward of pulling an arm depends on both the pulled arm and the current state of the corresponding Markov chain. In this paper, we propose Restless-UCB, a UCB-based learning policy that follows the explore-then-commit framework. In Restless-UCB, we present a novel method to construct offline instances, which only requires $O(N)$ time-complexity and is exponentially better than the complexity of existing learning policy. We also prove that Restless-UCB achieves a regret upper bound of $\tilde{O}((N+M^3)T^{2\over 3})$, where $N$ is the number of arms, $M$ is the Markov chain state space size and $T$ is the time horizon. Compared to existing algorithms, our result eliminates the exponential factor (in $M,N$) in the regret upper bound, due to a novel exploitation of the sparsity in transitions in general restless bandit problems. As a result, our analysis technique can also be adopted to tighten the regret bounds of existing algorithms. Finally, we conduct experiments based on real-world dataset, to compare the Restless-UCB policy with state-of-the-art benchmarks. Our results show that Restless-UCB outperforms existing algorithms in regret, and significantly reduces the running time.
BibTeX
@inproceedings{wang2020restless,
  author = {Siwei Wang and Longbo Huang and John Lui},
  title = {{Restless-UCB, an Efficient and Low-complexity Algorithm for Online Restless Bandits}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
}
Figure