# Finite-Time Analysis of Whittle Index based Q-Learning for Restless Multi-Armed Bandits with Neural Network Function Approximation

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- Builds on 29 of its 68 references that are in the map.
- First posted on arXiv 3 Oct 2023.

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

- [A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximation](https://mlsanity.com/paper/1806.02450/) (2018)
- [A Theoretical Analysis of Deep Q-Learning](https://mlsanity.com/paper/1901.00137/) (2019)
- [Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learning](https://mlsanity.com/paper/1902.00923/) (2019)
- [Finite-Time Analysis of Asynchronous Stochastic Approximation and Q-Learning](https://mlsanity.com/paper/2002.00260/) (2020)
- [Finite-Sample Analysis for SARSA with Linear Function Approximation](https://mlsanity.com/paper/1902.02234/) (2019)
- [Model-free Reinforcement Learning in Infinite-horizon Average-reward Markov Decision Processes](https://mlsanity.com/paper/1910.07072/) (2019)
- [Learning and Planning in Average-Reward Markov Decision Processes](https://mlsanity.com/paper/2006.16318/) (2020)
- [Finite Time Analysis of Linear Two-timescale Stochastic Approximation with Markovian Noise](https://mlsanity.com/paper/2002.01268/) (2020)
- [A Finite-Time Analysis of Q-Learning with Neural Network Function Approximation](https://mlsanity.com/paper/1912.04511/) (2019)
- [Collapsing Bandits and Their Application to Public Health Interventions](https://mlsanity.com/paper/2007.04432/) (2020)
- [Whittle index based Q-learning for restless bandits with average reward](https://mlsanity.com/paper/2004.14427/) (2020)
- [Towards Characterizing Divergence in Deep Q-Learning](https://mlsanity.com/paper/1903.08894/) (2019)
- [Finite-Time Performance Bounds and Adaptive Learning Rate Selection for Two Time-Scale Reinforcement Learning](https://mlsanity.com/paper/1907.06290/) (2019)
- [Nonlinear Two-Time-Scale Stochastic Approximation: Convergence and Finite-Time Performance](https://mlsanity.com/paper/2011.01868/) (2020)
- [Learn to Intervene: An Adaptive Learning Policy for Restless Bandits in Application to Preventive Healthcare](https://mlsanity.com/paper/2105.07965/) (2021)
- [Regret Bounds for Thompson Sampling in Episodic Restless Bandit Problems](https://mlsanity.com/paper/1905.12673/) (2019)
- [A Tale of Two-Timescale Reinforcement Learning with the Tightest Finite-Time Bound](https://mlsanity.com/paper/1911.09157/) (2019)
- [Average-Reward Off-Policy Policy Evaluation with Function Approximation](https://mlsanity.com/paper/2101.02808/) (2021)
- [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)
- [Q-Learning Lagrange Policies for Multi-Action Restless Bandits](https://mlsanity.com/paper/2106.12024/) (2021)
- [Neural Temporal-Difference and Q-Learning Provably Converge to Global Optima](https://mlsanity.com/paper/1905.10027/) (2019)
- [Finite-Sample Analysis of Stochastic Approximation Using Smooth Convex Envelopes](https://mlsanity.com/paper/2002.00874/) (2020)
- [Deadline Scheduling as Restless Bandits](https://mlsanity.com/paper/1610.00399/) (2016)
- [Optimal Recommendation to Users that React: Online Learning for a Class of POMDPs](https://mlsanity.com/paper/1603.09233/) (2016)
- [Finite-Time Convergence Rates of Nonlinear Two-Time-Scale Stochastic Approximation under Markovian Noise](https://mlsanity.com/paper/2104.01627/) (2021)
- [Whittle Index based Q-Learning for Wireless Edge Caching with Linear Function Approximation](https://mlsanity.com/paper/2202.13187/) (2022)
- [DeepTOP: Deep Threshold-Optimal Policy for MDPs and RMABs](https://mlsanity.com/paper/2209.08646/) (2022)
- [Full Gradient Deep Reinforcement Learning for Average-Reward Criterion](https://mlsanity.com/paper/2304.03729/) (2023)

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

- [Online Restless Multi-Armed Bandits with Long-Term Fairness Constraints](https://mlsanity.com/paper/2312.10303/) (2023)
- [Towards a Pretrained Model for Restless Bandits via Multi-arm Generalization](https://mlsanity.com/paper/2310.14526/) (2023)
- [Context in Public Health for Underserved Communities: A Bayesian Approach to Online Restless Bandits](https://mlsanity.com/paper/2402.04933/) (2024)
- [The Bandit Whisperer: Communication Learning for Restless Bandits](https://mlsanity.com/paper/2408.05686/) (2024)
- [Tabular and Deep Learning for the Whittle Index](https://mlsanity.com/paper/2406.02057/) (2024)
- [Improving the Prediction of Individual Engagement in Recommendations Using Cognitive Models](https://mlsanity.com/paper/2408.16147/) (2024)
- [Projection-based Lyapunov method for fully heterogeneous weakly-coupled MDPs](https://mlsanity.com/paper/2502.06072/) (2025)
- [DOPL: Direct Online Preference Learning for Restless Bandits with Preference Feedback](https://mlsanity.com/paper/2410.05527/) (2024)
- [Provably Efficient Reinforcement Learning for Adversarial Restless Multi-Armed Bandits with Unknown Transitions and Bandit Feedback](https://mlsanity.com/paper/2405.00950/) (2024)
- [GINO-Q: Learning an Asymptotically Optimal Index Policy for Restless Multi-armed Bandits](https://mlsanity.com/paper/2408.09882/) (2024)
- [Finite-Horizon Single-Pull Restless Bandits: An Efficient Index Policy For Scarce Resource Allocation](https://mlsanity.com/paper/2501.06103/) (2025)
- [MARBLE: Multi-Armed Restless Bandits in Latent Markovian Environment](https://mlsanity.com/paper/2511.09324/) (2025)
- [Model-Based Learning of Whittle indices](https://mlsanity.com/paper/2511.20397/) (2025)
- [From Relaxed Indexability to Exact Indexability: A t-Step Approach for Partially Observable Restless Bandits](https://mlsanity.com/paper/2608.24167/) (2026)

## Abstract (arXiv)

Whittle index policy is a heuristic to the intractable restless multi-armed bandits (RMAB) problem. Although it is provably asymptotically optimal, finding Whittle indices remains difficult. In this paper, we present Neural-Q-Whittle, a Whittle index based Q-learning algorithm for RMAB with neural network function approximation, which is an example of nonlinear two-timescale stochastic approximation with Q-function values updated on a faster timescale and Whittle indices on a slower timescale. Despite the empirical success of deep Q-learning, the non-asymptotic convergence rate of Neural-Q-Whittle, which couples neural networks with two-timescale Q-learning largely remains unclear. This paper provides a finite-time analysis of Neural-Q-Whittle, where data are generated from a Markov chain, and Q-function is approximated by a ReLU neural network. Our analysis leverages a Lyapunov drift approach to capture the evolution of two coupled parameters, and the nonlinearity in value function approximation further requires us to characterize the approximation error. Combing these provide Neural-Q-Whittle with O(1/k2/3) convergence rate, where k is the number of iterations.