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:
- 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.
- 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.
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