# Faster Q-Learning Algorithms for Restless Bandits

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods.
- Builds on 16 of its 36 references that are in the map.
- First posted on arXiv 6 Sep 2024.

## Placed in

- Deep reinforcement learning methods / [RL theory and sample complexity](https://mlsanity.com/deeprl/rl-theory-and-sample-complexity/)

## Builds on (most cited first, 16 of 16)

- [Is Q-learning Provably Efficient?](https://mlsanity.com/paper/1807.03765/) (2018)
- [Variance Reduced Value Iteration and Faster Algorithms for Solving Markov Decision Processes](https://mlsanity.com/paper/1710.09988/) (2017)
- [Whittle index based Q-learning for restless bandits with average reward](https://mlsanity.com/paper/2004.14427/) (2020)
- [Regret Bounds for Thompson Sampling in Episodic Restless Bandit Problems](https://mlsanity.com/paper/1905.12673/) (2019)
- [Restless-UCB, an Efficient and Low-complexity Algorithm for Online Restless Bandits](https://mlsanity.com/paper/2011.02664/) (2020)
- [NeurWIN: Neural Whittle Index Network For Restless Bandits Via Deep RL](https://mlsanity.com/paper/2110.02128/) (2021)
- [Optimistic Whittle Index Policy: Online Learning for Restless Bandits](https://mlsanity.com/paper/2205.15372/) (2022)
- [Opportunistic Scheduling as Restless Bandits](https://mlsanity.com/paper/1706.09778/) (2017)
- [Optimal Recommendation to Users that React: Online Learning for a Class of POMDPs](https://mlsanity.com/paper/1603.09233/) (2016)
- [Full Gradient DQN Reinforcement Learning: A Provably Convergent Scheme](https://mlsanity.com/paper/2103.05981/) (2021)
- [Whittle Index based Q-Learning for Wireless Edge Caching with Linear Function Approximation](https://mlsanity.com/paper/2202.13187/) (2022)
- [Empirical Q-Value Iteration](https://mlsanity.com/paper/1412.0180/) (2014)
- [A Hidden Markov Restless Multi-armed Bandit Model for Playout Recommendation Systems](https://mlsanity.com/paper/1704.02894/) (2017)
- [Full Gradient Deep Reinforcement Learning for Average-Reward Criterion](https://mlsanity.com/paper/2304.03729/) (2023)
- [Generalized Speedy Q-learning](https://mlsanity.com/paper/1911.00397/) (2019)
- [Tabular and Deep Learning for the Whittle Index](https://mlsanity.com/paper/2406.02057/) (2024)

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

- [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)

## Abstract (arXiv)

We study the Whittle index learning algorithm for restless multi-armed bandits (RMAB). We first present Q-learning algorithm and its variants -- speedy Q-learning (SQL), generalized speedy Q-learning (GSQL) and phase Q-learning (PhaseQL). We also discuss exploration policies -- ε-greedy and Upper confidence bound (UCB). We extend the study of Q-learning and its variants with UCB policy. We illustrate using numerical example that Q-learning with UCB exploration policy has faster convergence and PhaseQL with UCB have fastest convergence rate. We next extend the study of Q-learning variants for index learning to RMAB. The algorithm of index learning is two-timescale variant of stochastic approximation, on slower timescale we update index learning scheme and on faster timescale we update Q-learning assuming fixed index value. We study constant stepsizes two timescale stochastic approximation algorithm. We describe the performance of our algorithms using numerical example. It illustrate that index learning with Q learning with UCB has faster convergence that ε greedy. Further, PhaseQL (with UCB and ε greedy) has the best convergence than other Q-learning algorithms.