# Model Predictive Control is Almost Optimal for Restless Bandit

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 37 references that are in the map.
- First posted on arXiv 8 Oct 2024.

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

- [Whittle index based Q-learning for restless bandits with average reward](https://mlsanity.com/paper/2004.14427/) (2020)
- [An Asymptotically Optimal Index Policy for Finite-Horizon Restless Bandits](https://mlsanity.com/paper/1707.00205/) (2017)
- [Restless Bandits with Many Arms: Beating the Central Limit Theorem](https://mlsanity.com/paper/2107.11911/) (2021)
- [LP-based policies for restless bandits: necessary and sufficient conditions for (exponentially fast) asymptotic optimality](https://mlsanity.com/paper/2106.10067/) (2021)
- [Indexability is Not Enough for Whittle: Improved, Near-Optimal Algorithms for Restless Bandits](https://mlsanity.com/paper/2211.00112/) (2022)
- [Near-optimality for infinite-horizon restless bandits with many arms](https://mlsanity.com/paper/2203.15853/) (2022)
- [Restless Bandits with Average Reward: Breaking the Uniform Global Attractor Assumption](https://mlsanity.com/paper/2306.00196/) (2023)
- [Adaptive Caching Networks with Optimality Guarantees](https://mlsanity.com/paper/1604.03175/) (2016)
- [Full Gradient DQN Reinforcement Learning: A Provably Convergent Scheme](https://mlsanity.com/paper/2103.05981/) (2021)
- [Reoptimization Nearly Solves Weakly Coupled Markov Decision Processes](https://mlsanity.com/paper/2211.01961/) (2022)
- [Unichain and Aperiodicity are Sufficient for Asymptotic Optimality of Average-Reward Restless Bandits](https://mlsanity.com/paper/2402.05689/) (2024)
- [An Optimal-Control Approach to Infinite-Horizon Restless Bandits: Achieving Asymptotic Optimality with Minimal Assumptions](https://mlsanity.com/paper/2403.11913/) (2024)
- [Dynamic allocation indices for restless projects and queueing admission control: a polyhedral approach](https://mlsanity.com/paper/2304.01946/) (2023)
- [Asymptotically Optimal Policies for Weakly Coupled Markov Decision Processes](https://mlsanity.com/paper/2406.04751/) (2024)
- [Optimal Policies for Observing Time Series and Related Restless Bandit Problems](https://mlsanity.com/paper/1703.10010/) (2017)

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

- [The Gittins Index: A Design Principle for Decision-Making Under Uncertainty](https://mlsanity.com/paper/2506.10872/) (2025)

## Abstract (arXiv)

We consider the discrete time infinite horizon average reward restless markovian bandit (RMAB) problem. We propose a model predictive control based non-stationary policy with a rolling computational horizon τ. At each time-slot, this policy solves a τ horizon linear program whose first control value is kept as a control for the RMAB. Our solution requires minimal assumptions and quantifies the loss in optimality in terms of τ and the number of arms, N. We show that its sub-optimality gap is O(1/√N) in general, and exp(-Omega(N)) under a local-stability condition. Our proof is based on a framework from dynamic control known as dissipativity. Our solution easy to implement and performs very well in practice when compared to the state of the art. Further, both our solution and our proof methodology can easily be generalized to more general constrained MDP settings and should thus, be of great interest to the burgeoning RMAB community.