Model Predictive Control is almost Optimal for Heterogeneous Restless Multi-armed Bandits

Dheeraj Narasimha, Nicolas Gast · 2025

Read Model Predictive Control is almost Optimal for Heterogeneous Restless Multi-armed Bandits by Dheeraj Narasimha, Nicolas Gast (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-08097.txt.

Description

Dheeraj Narasimha and Nicolas Gast show that model predictive control is nearly optimal for restless multi armed bandits where arms differ from each other. Each arm changes state whether chosen or not, and heterogeneity between arms defeats many standard concentration arguments. Predictive control repeatedly solves a short horizon problem to steer a long horizon system, a strategy known to work well in practice.

Their version solves a finite linear program again and again, producing an LP update policy. Under a uniform ergodicity assumption, its suboptimality shrinks at a stated rate as the number of arms grows. Simulations perform strongly even with a horizon of five, keeping computation light.

Catalog record

CREATORDheeraj Narasimha, Nicolas Gast
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE122 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2511-08097

Browse the full library · About the Tower of Babel