# Indexability of Finite State Restless Multi-Armed Bandit and Rollout Policy

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 34 references that are in the map.
- First posted on arXiv 30 Apr 2023.

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

- [Whittle index based Q-learning for restless bandits with average reward](https://mlsanity.com/paper/2004.14427/) (2020)
- [On the Complexity of Solving Markov Decision Problems](https://mlsanity.com/paper/1302.4971/) (2013)
- [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)
- [Near-optimality for infinite-horizon restless bandits with many arms](https://mlsanity.com/paper/2203.15853/) (2022)
- [Reoptimization Nearly Solves Weakly Coupled Markov Decision Processes](https://mlsanity.com/paper/2211.01961/) (2022)
- [Dynamic priority allocation via restless bandit marginal productivity indices](https://mlsanity.com/paper/2304.06115/) (2023)
- [Simulation Based Algorithms for Markov Decision Processes and Multi-Action Restless Bandits](https://mlsanity.com/paper/2007.12933/) (2020)
- [A Hidden Markov Restless Multi-armed Bandit Model for Playout Recommendation Systems](https://mlsanity.com/paper/1704.02894/) (2017)
- [Sequential Decision Making with Limited Observation Capability: Application to Wireless Networks](https://mlsanity.com/paper/1801.01301/) (2018)

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

- [Outcome-Fair Restless Multi-Armed Bandits for Stochastic Deadline Scheduling](https://mlsanity.com/paper/2607.23772/) (2026)

## Abstract (arXiv)

We consider finite state restless multi-armed bandit problem. The decision maker can act on M bandits out of N bandits in each time step. The play of arm (active arm) yields state dependent rewards based on action and when the arm is not played, it also provides rewards based on the state and action. The objective of the decision maker is to maximize the infinite horizon discounted reward. The classical approach to restless bandits is Whittle index policy. In such policy, the M arms with highest indices are played at each time step. Here, one decouples the restless bandits problem by analyzing relaxed constrained restless bandits problem. Then by Lagrangian relaxation problem, one decouples restless bandits problem into N single-armed restless bandit problems. We analyze the single-armed restless bandit. In order to study the Whittle index policy, we show structural results on the single armed bandit model. We define indexability and show indexability in special cases. We propose an alternative approach to verify the indexable criteria for a single armed bandit model using value iteration algorithm. We demonstrate the performance of our algorithm with different examples. We provide insight on condition of indexability of restless bandits using different structural assumptions on transition probability and reward matrices. We also study online rollout policy and discuss the computation complexity of algorithm and compare that with complexity of index computation. Numerical examples illustrate that index policy and rollout policy performs better than myopic policy.