# On the Whittle Index for Restless Multi-armed Hidden Markov Bandits

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Mar 2016.

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

- [NeurWIN: Neural Whittle Index Network For Restless Bandits Via Deep RL](https://mlsanity.com/paper/2110.02128/) (2021)
- [Generalized non-stationary bandits](https://mlsanity.com/paper/2102.00725/) (2021)
- [Weakly Coupled Deep Q-Networks](https://mlsanity.com/paper/2310.18803/) (2023)
- [Low-Complexity Algorithm for Restless Bandits with Imperfect Observations](https://mlsanity.com/paper/2108.03812/) (2021)
- [Indexability and Rollout Policy for Multi-State Partially Observable Restless Bandits](https://mlsanity.com/paper/2108.00892/) (2021)
- [Using Non-Stationary Bandits for Learning in Repeated Cournot Games with Non-Stationary Demand](https://mlsanity.com/paper/2201.00486/) (2022)
- [Monte Carlo Rollout Policy for Recommendation Systems with Dynamic User Behavior](https://mlsanity.com/paper/2102.04321/) (2021)
- [Indexability of Finite State Restless Multi-Armed Bandit and Rollout Policy](https://mlsanity.com/paper/2305.00410/) (2023)
- [Online Learning of Whittle Indices for Restless Bandits with Non-Stationary Transition Kernels](https://mlsanity.com/paper/2506.18186/) (2025)
- [Caching Contents with Varying Popularity using Restless Bandits](https://mlsanity.com/paper/2212.03291/) (2022)
- [Influencing Bandits: Arm Selection for Preference Shaping](https://mlsanity.com/paper/2403.00036/) (2024)
- [Lagrangian Relaxation for Multi-Action Partially Observable Restless Bandits: Heuristic Policies and Indexability](https://mlsanity.com/paper/2509.00415/) (2025)

## Abstract (arXiv)

We consider a restless multi-armed bandit in which each arm can be in one of two states. When an arm is sampled, the state of the arm is not available to the sampler. Instead, a binary signal with a known randomness that depends on the state of the arm is available. No signal is available if the arm is not sampled. An arm-dependent reward is accrued from each sampling. In each time step, each arm changes state according to known transition probabilities which in turn depend on whether the arm is sampled or not sampled. Since the state of the arm is never visible and has to be inferred from the current belief and a possible binary signal, we call this the hidden Markov bandit. Our interest is in a policy to select the arm(s) in each time step that maximizes the infinite horizon discounted reward. Specifically, we seek the use of Whittle's index in selecting the arms. We first analyze the single-armed bandit and show that in general, it admits an approximate threshold-type optimal policy when there is a positive reward for the `no-sample' action. We also identify several special cases for which the threshold policy is indeed the optimal policy. Next, we show that such a single-armed bandit also satisfies an approximate-indexability property. For the case when the single-armed bandit admits a threshold-type optimal policy, we perform the calculation of the Whittle index for each arm. Numerical examples illustrate the analytical results.