# Online Learning of Whittle Indices for Restless Bandits with Non-Stationary Transition Kernels

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 30 of its 60 references that are in the map.
- First posted on arXiv 22 Jun 2025.

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

- [Non-stationary Stochastic Optimization](https://mlsanity.com/paper/1307.5449/) (2013)
- [Multi-armed Bandit Models for the Optimal Design of Clinical Trials: Benefits and Challenges](https://mlsanity.com/paper/1507.08025/) (2015)
- [Non-stationary Reinforcement Learning without Prior Knowledge: An Optimal Black-box Approach](https://mlsanity.com/paper/2102.05406/) (2021)
- [Reinforcement Learning for Non-Stationary Markov Decision Processes: The Blessing of (More) Optimism](https://mlsanity.com/paper/2006.14389/) (2020)
- [Collapsing Bandits and Their Application to Public Health Interventions](https://mlsanity.com/paper/2007.04432/) (2020)
- [Hedging the Drift: Learning to Optimize under Non-Stationarity](https://mlsanity.com/paper/1903.01461/) (2019)
- [Whittle index based Q-learning for restless bandits with average reward](https://mlsanity.com/paper/2004.14427/) (2020)
- [Optimal Exploration-Exploitation in a Multi-Armed-Bandit Problem with Non-stationary Rewards](https://mlsanity.com/paper/1405.3316/) (2014)
- [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)
- [Variational Regret Bounds for Reinforcement Learning](https://mlsanity.com/paper/1905.05857/) (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)
- [A Decision-Language Model (DLM) for Dynamic Restless Multi-Armed Bandit Tasks in Public Health](https://mlsanity.com/paper/2402.14807/) (2024)
- [Scheduling Policies for Minimizing Age of Information in Broadcast Wireless Networks](https://mlsanity.com/paper/1801.01803/) (2018)
- [A Whittle Index Approach to Minimizing Functions of Age of Information](https://mlsanity.com/paper/1908.10438/) (2019)
- [Q-Learning Lagrange Policies for Multi-Action Restless Bandits](https://mlsanity.com/paper/2106.12024/) (2021)
- [Provably Efficient Model-Free Algorithms for Non-stationary CMDPs](https://mlsanity.com/paper/2303.05733/) (2023)
- [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)
- [On the Whittle Index for Restless Multi-armed Hidden Markov Bandits](https://mlsanity.com/paper/1603.04739/) (2016)
- [Sampling for Data Freshness Optimization: Non-linear Age Functions](https://mlsanity.com/paper/1812.07241/) (2018)
- [Monitored Markov Decision Processes](https://mlsanity.com/paper/2402.06819/) (2024)
- [Scalable Operator Allocation for Multi-Robot Assistance: A Restless Bandit Approach](https://mlsanity.com/paper/2111.06437/) (2021)
- [An Online Learning Approach to Optimizing Time-Varying Costs of AoI](https://mlsanity.com/paper/2105.13383/) (2021)
- [DeepTOP: Deep Threshold-Optimal Policy for MDPs and RMABs](https://mlsanity.com/paper/2209.08646/) (2022)
- [Timely Communications for Remote Inference](https://mlsanity.com/paper/2404.16281/) (2024)
- [A Hidden Markov Restless Multi-armed Bandit Model for Playout Recommendation Systems](https://mlsanity.com/paper/1704.02894/) (2017)
- [When are Kalman-filter restless bandits indexable?](https://mlsanity.com/paper/1509.04541/) (2015)
- [MetaCURL: Non-stationary Concave Utility Reinforcement Learning](https://mlsanity.com/paper/2405.19807/) (2024)

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

- [MARBLE: Multi-Armed Restless Bandits in Latent Markovian Environment](https://mlsanity.com/paper/2511.09324/) (2025)

## Abstract (arXiv)

The restless multi-armed bandit (RMAB) framework is a popular approach to solving resource allocation problems in networked systems. In this paper, we study optimal resource allocation in RMABs facing unknown and non-stationary dynamics. Solving RMABs optimally is known to be PSPACE-hard even with full knowledge of model parameters. While Whittle index policies offer asymptotic optimality with low computational cost, they require access to stationary transition kernels, an unrealistic assumption in many modern networking applications. To address this challenge, we propose a Sliding-Window Online Whittle (SW-Whittle) policy that remains computationally efficient while adapting to time-varying kernels. Through theoretical analysis, we show that our algorithm achieves sub-linear dynamic regret with respect to the number of episodes. We further address the important case where the variation budget is unknown in advance by combining a Bandit-over-Bandit framework with our sliding-window design. In our scheme, window lengths are tuned online as a function of the estimated variation, while Whittle indices are computed via an upper-confidence-bound of the estimated transition kernels and a bilinear optimization routine. Numerical experiments demonstrate that our algorithm consistently outperforms baselines, achieving the lowest cumulative regret across a range of non-stationary environments.