# On learning Whittle index policy for restless bandits with scalable regret

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 74 references that are in the map.
- First posted on arXiv 7 Feb 2022.

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

- [Learning to Optimize Via Posterior Sampling](https://mlsanity.com/paper/1301.2609/) (2013)
- [Efficient Bias-Span-Constrained Exploration-Exploitation in Reinforcement Learning](https://mlsanity.com/paper/1802.04020/) (2018)
- [Learning Unknown Markov Decision Processes: A Thompson Sampling Approach](https://mlsanity.com/paper/1709.04570/) (2017)
- [Whittle index based Q-learning for restless bandits with average reward](https://mlsanity.com/paper/2004.14427/) (2020)
- [Regret Minimization for Reinforcement Learning by Evaluating the Optimal Bias Function](https://mlsanity.com/paper/1906.05110/) (2019)
- [Regret Bounds for Thompson Sampling in Episodic Restless Bandit Problems](https://mlsanity.com/paper/1905.12673/) (2019)
- [Posterior sampling for reinforcement learning: worst-case regret bounds](https://mlsanity.com/paper/1705.07041/) (2017)
- [Thompson Sampling in Non-Episodic Restless Bandits](https://mlsanity.com/paper/1910.05654/) (2019)
- [Learning in Restless Multi-Armed Bandits via Adaptive Arm Sequencing Rules](https://mlsanity.com/paper/1906.08120/) (2019)
- [Opportunistic Scheduling as Restless Bandits](https://mlsanity.com/paper/1706.09778/) (2017)
- [Scalable Operator Allocation for Multi-Robot Assistance: A Restless Bandit Approach](https://mlsanity.com/paper/2111.06437/) (2021)
- [User Association in Dense mmWave Networks as Restless Bandits](https://mlsanity.com/paper/2107.09153/) (2021)
- [Learning Augmented Index Policy for Optimal Service Placement at the Network Edge](https://mlsanity.com/paper/2101.03641/) (2021)
- [Two families of indexable partially observable restless bandits and Whittle index computation](https://mlsanity.com/paper/2104.05151/) (2021)
- [A near-optimal maintenance policy for automated DR devices](https://mlsanity.com/paper/1410.5496/) (2014)
- [Reinforcement Learning for Markovian Bandits: Is Posterior Sampling more Scalable than Optimism?](https://mlsanity.com/paper/2106.08771/) (2021)

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

- [Context in Public Health for Underserved Communities: A Bayesian Approach to Online Restless Bandits](https://mlsanity.com/paper/2402.04933/) (2024)
- [Bayesian Learning of Optimal Policies in Markov Decision Processes with Countably Infinite State-Space](https://mlsanity.com/paper/2306.02574/) (2023)
- [DOPL: Direct Online Preference Learning for Restless Bandits with Preference Feedback](https://mlsanity.com/paper/2410.05527/) (2024)
- [Tabular and Deep Reinforcement Learning for Gittins Index](https://mlsanity.com/paper/2405.01157/) (2024)
- [A Federated Online Restless Bandit Framework for Cooperative Resource Allocation](https://mlsanity.com/paper/2406.07992/) (2024)
- [A resource-constrained stochastic scheduling algorithm for homeless street outreach and gleaning edible food](https://mlsanity.com/paper/2403.10638/) (2024)
- [Structured Reinforcement Learning for Delay-Optimal Data Transmission in Dense mmWave Networks](https://mlsanity.com/paper/2404.16920/) (2024)
- [Risk-Aware Decision Making in Restless Bandits: Theory and Algorithms for Planning and Learning](https://mlsanity.com/paper/2410.23029/) (2024)
- [Age-of-information minimization under energy harvesting and non-stationary environment](https://mlsanity.com/paper/2504.04916/) (2025)
- [Model-Based Learning of Whittle indices](https://mlsanity.com/paper/2511.20397/) (2025)

## Abstract (arXiv)

Reinforcement learning is an attractive approach to learn good resource allocation and scheduling policies based on data when the system model is unknown. However, the cumulative regret of most RL algorithms scales as tilde O(mathsfS √mathsfA T), where mathsfS is the size of the state space, mathsfA is the size of the action space, T is the horizon, and the tildeO(·) notation hides logarithmic terms. Due to the linear dependence on the size of the state space, these regret bounds are prohibitively large for resource allocation and scheduling problems. In this paper, we present a model-based RL algorithm for such problems which has scalable regret. In particular, we consider a restless bandit model, and propose a Thompson-sampling based learning algorithm which is tuned to the underlying structure of the model. We present two characterizations of the regret of the proposed algorithm with respect to the Whittle index policy. First, we show that for a restless bandit with n arms and at most m activations at each time, the regret scales either as tildeO(mn√T) or tildeO(n2 √T) depending on the reward model. Second, under an additional technical assumption, we show that the regret scales as tildeO(n1.5 √T) or tildeO(maxm√n, n √T). We present numerical examples to illustrate the salient features of the algorithm.