# Simulation Based Algorithms for Markov Decision Processes and Multi-Action Restless Bandits

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Jul 2020.

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

- [Near-optimality for infinite-horizon restless bandits with many arms](https://mlsanity.com/paper/2203.15853/) (2022)
- [Fairness for Workers Who Pull the Arms: An Index Based Policy for Allocation of Restless Bandit Tasks](https://mlsanity.com/paper/2303.00799/) (2023)
- [Indexability and Rollout Policy for Multi-State Partially Observable Restless Bandits](https://mlsanity.com/paper/2108.00892/) (2021)
- [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)
- [Deep reinforcement learning for weakly coupled MDP's with continuous actions](https://mlsanity.com/paper/2406.01099/) (2024)
- [Outcome-Fair Restless Multi-Armed Bandits for Stochastic Deadline Scheduling](https://mlsanity.com/paper/2607.23772/) (2026)

## Abstract (arXiv)

We consider multi-dimensional Markov decision processes and formulate a long term discounted reward optimization problem. Two simulation based algorithms---Monte Carlo rollout policy and parallel rollout policy are studied, and various properties for these policies are discussed. We next consider a restless multi-armed bandit (RMAB) with multi-dimensional state space and multi-actions bandit model. A standard RMAB consists of two actions for each arms whereas in multi-actions RMAB, there are more that two actions for each arms. A popular approach for RMAB is Whittle index based heuristic policy. Indexability is an important requirement to use index based policy. Based on this, an RMAB is classified into indexable or non-indexable bandits. Our interest is in the study of Monte-Carlo rollout policy for both indexable and non-indexable restless bandits. We first analyze a standard indexable RMAB (two-action model) and discuss an index based policy approach. We present approximate index computation algorithm using Monte-Carlo rollout policy. This algorithm's convergence is shown using two-timescale stochastic approximation scheme. Later, we analyze multi-actions indexable RMAB, and discuss the index based policy approach. We also study non-indexable RMAB for both standard and multi-actions bandits using Monte-Carlo rollout policy.