# Tabular and Deep Learning for the Whittle Index

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

## Key facts

- Cited by 3 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 10 of its 30 references that are in the map.
- First posted on arXiv 4 Jun 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, 10 of 10)

- [Deep Reinforcement Learning with Double Q-learning](https://mlsanity.com/paper/1509.06461/) (2015)
- [Whittle index based Q-learning for restless bandits with average reward](https://mlsanity.com/paper/2004.14427/) (2020)
- [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)
- [Age of Information: Whittle Index for Scheduling Stochastic Arrivals](https://mlsanity.com/paper/1801.03422/) (2018)
- [Q-Learning Lagrange Policies for Multi-Action Restless Bandits](https://mlsanity.com/paper/2106.12024/) (2021)
- [Deadline Scheduling as Restless Bandits](https://mlsanity.com/paper/1610.00399/) (2016)
- [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)
- [A verification theorem for threshold-indexability of real-state discounted restless bandits](https://mlsanity.com/paper/1902.09318/) (2019)
- [Full Gradient Deep Reinforcement Learning for Average-Reward Criterion](https://mlsanity.com/paper/2304.03729/) (2023)

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

- [Lagrangian Index Policy for Restless Bandits with Average Reward](https://mlsanity.com/paper/2412.12641/) (2024)
- [Faster Q-Learning Algorithms for Restless Bandits](https://mlsanity.com/paper/2409.05908/) (2024)
- [Restless Bandits with Individual Penalty Constraints: Near-Optimal Indices and Deep Reinforcement Learning](https://mlsanity.com/paper/2604.04101/) (2026)

## Abstract (arXiv)

The Whittle index policy is a heuristic that has shown remarkably good performance (with guaranteed asymptotic optimality) when applied to the class of problems known as Restless Multi-Armed Bandit Problems (RMABPs). In this paper we present QWI and QWINN, two reinforcement learning algorithms, respectively tabular and deep, to learn the Whittle index for the total discounted criterion. The key feature is the use of two time-scales, a faster one to update the state-action Q -values, and a relatively slower one to update the Whittle indices. In our main theoretical result we show that QWI, which is a tabular implementation, converges to the real Whittle indices. We then present QWINN, an adaptation of QWI algorithm using neural networks to compute the Q -values on the faster time-scale, which is able to extrapolate information from one state to another and scales naturally to large state-space environments. For QWINN, we show that all local minima of the Bellman error are locally stable equilibria, which is the first result of its kind for DQN-based schemes. Numerical computations show that QWI and QWINN converge faster than the standard Q -learning algorithm, neural-network based approximate Q-learning and other state of the art algorithms.