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

arXiv: https://arxiv.org/abs/2011.02664 · HTML: https://mlsanity.com/paper/2011.02664/

## Key facts

- Cited by 27 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Nov 2020.

## Built on by (most cited first, 27 of 27)

- [Optimistic Whittle Index Policy: Online Learning for Restless Bandits](https://mlsanity.com/paper/2205.15372/) (2022)
- [Stochastic Rising Bandits](https://mlsanity.com/paper/2212.03798/) (2022)
- [Finite-Time Analysis of Whittle Index based Q-Learning for Restless Multi-Armed Bandits with Neural Network Function Approximation](https://mlsanity.com/paper/2310.02147/) (2023)
- [Online Restless Multi-Armed Bandits with Long-Term Fairness Constraints](https://mlsanity.com/paper/2312.10303/) (2023)
- [Policy Optimization for Personalized Interventions in Behavioral Health](https://mlsanity.com/paper/2303.12206/) (2023)
- [Whittle Index based Q-Learning for Wireless Edge Caching with Linear Function Approximation](https://mlsanity.com/paper/2202.13187/) (2022)
- [Restless and Uncertain: Robust Policies for Restless Bandits via Deep Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2107.01689/) (2021)
- [Approximately Stationary Bandits with Knapsacks](https://mlsanity.com/paper/2302.14686/) (2023)
- [Optimal Best Arm Identification with Fixed Confidence in Restless Bandits](https://mlsanity.com/paper/2310.13393/) (2023)
- [Tabular and Deep Learning for the Whittle Index](https://mlsanity.com/paper/2406.02057/) (2024)
- [On the Low-Complexity of Fair Learning for Combinatorial Multi-Armed Bandit](https://mlsanity.com/paper/2501.00924/) (2025)
- [Faster Q-Learning Algorithms for Restless Bandits](https://mlsanity.com/paper/2409.05908/) (2024)
- [DOPL: Direct Online Preference Learning for Restless Bandits with Preference Feedback](https://mlsanity.com/paper/2410.05527/) (2024)
- [Reinforcement Learning for Markovian Bandits: Is Posterior Sampling more Scalable than Optimism?](https://mlsanity.com/paper/2106.08771/) (2021)
- [Decision-Focused Evaluation: Analyzing Performance of Deployed Restless Multi-Arm Bandits](https://mlsanity.com/paper/2301.07835/) (2023)
- [Provably Efficient Reinforcement Learning for Adversarial Restless Multi-Armed Bandits with Unknown Transitions and Bandit Feedback](https://mlsanity.com/paper/2405.00950/) (2024)
- [A Federated Online Restless Bandit Framework for Cooperative Resource Allocation](https://mlsanity.com/paper/2406.07992/) (2024)
- [Whittle Index Learning Algorithms for Restless Bandits with Constant Stepsizes](https://mlsanity.com/paper/2409.04605/) (2024)
- [Online Learning of Whittle Indices for Restless Bandits with Non-Stationary Transition Kernels](https://mlsanity.com/paper/2506.18186/) (2025)
- [Reinforcement Learning for Finite-Horizon Restless Multi-Armed Multi-Action Bandits](https://mlsanity.com/paper/2109.09855/) (2021)
- [Structured Reinforcement Learning for Delay-Optimal Data Transmission in Dense mmWave Networks](https://mlsanity.com/paper/2404.16920/) (2024)
- [Restless Bandit Problem with Rewards Generated by a Linear Gaussian Dynamical System](https://mlsanity.com/paper/2405.09584/) (2024)
- [From Restless to Contextual: A Thresholding Bandit Reformulation For Finite-horizon Improvement](https://mlsanity.com/paper/2502.05145/) (2025)
- [Model-Based Learning of Whittle indices](https://mlsanity.com/paper/2511.20397/) (2025)
- [Adaptive Scheduling: A Reinforcement Learning Whittle Index Approach for Wireless Sensor Networks](https://mlsanity.com/paper/2601.01179/) (2026)
- [Online Social Welfare Function-based Resource Allocation](https://mlsanity.com/paper/2602.01400/) (2026)
- [A Practical Algorithm for Feature-Rich, Non-Stationary Bandit Problems](https://mlsanity.com/paper/2603.16755/) (2026)

## Abstract (arXiv)

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 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 (N is the number of arms) and is exponentially better than the complexity of existing learning policy. We also prove that Restless-UCB achieves a regret upper bound of tildeO((N+M3)T2over 3), where 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.