# Optimistic Whittle Index Policy: Online Learning for Restless Bandits

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

## Key facts

- Cited by 20 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 41 references that are in the map.
- First posted on arXiv 30 May 2022.

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

- [Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oracles](https://mlsanity.com/paper/2002.04926/) (2020)
- [Multi-armed Bandit Models for the Optimal Design of Clinical Trials: Benefits and Challenges](https://mlsanity.com/paper/1507.08025/) (2015)
- [Adversarial Bandits with Knapsacks](https://mlsanity.com/paper/1811.11881/) (2018)
- [Whittle index based Q-learning for restless bandits with average reward](https://mlsanity.com/paper/2004.14427/) (2020)
- [Field Study in Deploying Restless Multi-Armed Bandits: Assisting Non-Profits in Improving Maternal and Child Health](https://mlsanity.com/paper/2109.08075/) (2021)
- [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)
- [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)
- [An efficient algorithm for learning with semi-bandit feedback](https://mlsanity.com/paper/1305.2732/) (2013)
- [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)
- [An Asymptotically Optimal Index Policy for Finite-Horizon Restless Bandits](https://mlsanity.com/paper/1707.00205/) (2017)
- [Thompson Sampling in Non-Episodic Restless Bandits](https://mlsanity.com/paper/1910.05654/) (2019)
- [Opportunistic Scheduling as Restless Bandits](https://mlsanity.com/paper/1706.09778/) (2017)
- [Dual-Mandate Patrols: Multi-Armed Bandits for Green Security](https://mlsanity.com/paper/2009.06560/) (2020)
- [Optimal Recommendation to Users that React: Online Learning for a Class of POMDPs](https://mlsanity.com/paper/1603.09233/) (2016)
- [TS-UCB: Improving on Thompson Sampling With Little to No Additional Computation](https://mlsanity.com/paper/2006.06372/) (2020)
- [Efficient Algorithms for Finite Horizon and Streaming Restless Multi-Armed Bandit Problems](https://mlsanity.com/paper/2103.04730/) (2021)

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

- [Context in Public Health for Underserved Communities: A Bayesian Approach to Online Restless Bandits](https://mlsanity.com/paper/2402.04933/) (2024)
- [Global Rewards in Restless Multi-Armed Bandits](https://mlsanity.com/paper/2406.00738/) (2024)
- [Reinforcement learning with combinatorial actions for coupled restless bandits](https://mlsanity.com/paper/2503.01919/) (2025)
- [Faster Q-Learning Algorithms for Restless Bandits](https://mlsanity.com/paper/2409.05908/) (2024)
- [DOPL: Direct Online Preference Learning for Restless Bandits with Preference Feedback](https://mlsanity.com/paper/2410.05527/) (2024)
- [OPTWIN: Drift identification with optimal sub-windows](https://mlsanity.com/paper/2305.11942/) (2023)
- [Fairness of Exposure in Online Restless Multi-armed Bandits](https://mlsanity.com/paper/2402.06348/) (2024)
- [A Federated Online Restless Bandit Framework for Cooperative Resource Allocation](https://mlsanity.com/paper/2406.07992/) (2024)
- [GINO-Q: Learning an Asymptotically Optimal Index Policy for Restless Multi-armed Bandits](https://mlsanity.com/paper/2408.09882/) (2024)
- [Online Learning of Whittle Indices for Restless Bandits with Non-Stationary Transition Kernels](https://mlsanity.com/paper/2506.18186/) (2025)
- [An Index Policy Based on Sarsa and Q-learning for Heterogeneous Smart Target Tracking](https://mlsanity.com/paper/2402.12015/) (2024)
- [A resource-constrained stochastic scheduling algorithm for homeless street outreach and gleaning edible food](https://mlsanity.com/paper/2403.10638/) (2024)
- [From Restless to Contextual: A Thresholding Bandit Reformulation For Finite-horizon Improvement](https://mlsanity.com/paper/2502.05145/) (2025)
- [Age-of-information minimization under energy harvesting and non-stationary environment](https://mlsanity.com/paper/2504.04916/) (2025)
- [Multi-agent Markov Entanglement](https://mlsanity.com/paper/2506.02385/) (2025)
- [Non-Stationary Restless Multi-Armed Bandits with Provable Guarantee](https://mlsanity.com/paper/2508.10804/) (2025)
- [Model-Based Learning of Whittle indices](https://mlsanity.com/paper/2511.20397/) (2025)
- [Adaptive Scheduling: A Reinforcement Learning Whittle Index Approach for Wireless Sensor Networks](https://mlsanity.com/paper/2601.01179/) (2026)
- [Restless Bandits with Individual Penalty Constraints: Near-Optimal Indices and Deep Reinforcement Learning](https://mlsanity.com/paper/2604.04101/) (2026)
- [A Modularized Framework for Piecewise-Stationary Restless Bandits](https://mlsanity.com/paper/2604.10177/) (2026)

## Abstract (arXiv)

Restless multi-armed bandits (RMABs) extend multi-armed bandits to allow for stateful arms, where the state of each arm evolves restlessly with different transitions depending on whether that arm is pulled. Solving RMABs requires information on transition dynamics, which are often unknown upfront. To plan in RMAB settings with unknown transitions, we propose the first online learning algorithm based on the Whittle index policy, using an upper confidence bound (UCB) approach to learn transition dynamics. Specifically, we estimate confidence bounds of the transition probabilities and formulate a bilinear program to compute optimistic Whittle indices using these estimates. Our algorithm, UCWhittle, achieves sublinear O(H √T log T) frequentist regret to solve RMABs with unknown transitions in T episodes with a constant horizon H. Empirically, we demonstrate that UCWhittle leverages the structure of RMABs and the Whittle index policy solution to achieve better performance than existing online learning baselines across three domains, including one constructed from a real-world maternal and childcare dataset.