# MARBLE: Multi-Armed Restless Bandits in Latent Markovian Environment

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 13 of its 38 references that are in the map.
- First posted on arXiv 12 Nov 2025.

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

- [Whittle index based Q-learning for restless bandits with average reward](https://mlsanity.com/paper/2004.14427/) (2020)
- [NeurWIN: Neural Whittle Index Network For Restless Bandits Via Deep RL](https://mlsanity.com/paper/2110.02128/) (2021)
- [Link Scheduling using Graph Neural Networks](https://mlsanity.com/paper/2109.05536/) (2021)
- [Age of Information: Whittle Index for Scheduling Stochastic Arrivals](https://mlsanity.com/paper/1801.03422/) (2018)
- [Q-Learning Lagrange Policies for Multi-Action Restless Bandits](https://mlsanity.com/paper/2106.12024/) (2021)
- [Finite-Time Analysis of Whittle Index based Q-Learning for Restless Multi-Armed Bandits with Neural Network Function Approximation](https://mlsanity.com/paper/2310.02147/) (2023)
- [Efficient Resource Allocation with Fairness Constraints in Restless Multi-Armed Bandits](https://mlsanity.com/paper/2206.03883/) (2022)
- [Robust Recommender System: A Survey and Future Directions](https://mlsanity.com/paper/2309.02057/) (2023)
- [A verification theorem for threshold-indexability of real-state discounted restless bandits](https://mlsanity.com/paper/1902.09318/) (2019)
- [Full Gradient Deep Reinforcement Learning for Average-Reward Criterion](https://mlsanity.com/paper/2304.03729/) (2023)
- [Restless Multi-Armed Bandits under Exogenous Global Markov Process](https://mlsanity.com/paper/2202.13665/) (2022)
- [Reinforcement Learning in Switching Non-Stationary Markov Decision Processes: Algorithms and Convergence Analysis](https://mlsanity.com/paper/2503.18607/) (2025)
- [Online Learning of Whittle Indices for Restless Bandits with Non-Stationary Transition Kernels](https://mlsanity.com/paper/2506.18186/) (2025)

## Abstract (arXiv)

Restless Multi-Armed Bandits (RMABs) are powerful models for decision-making under uncertainty, yet classical formulations typically assume fixed dynamics, an assumption often violated in nonstationary environments. We introduce MARBLE (Multi-Armed Restless Bandits in a Latent Markovian Environment), which augments RMABs with a latent Markov state that induces nonstationary behavior. In MARBLE, each arm evolves according to a latent environment state that switches over time, making policy learning substantially more challenging. We further introduce the Markov-Averaged Indexability (MAI) criterion as a relaxed indexability assumption and prove that, despite unobserved regime switches, under the MAI criterion, synchronous Q-learning with Whittle Indices (QWI) converges almost surely to the optimal Q-function and the corresponding Whittle indices. We validate MARBLE on a calibrated simulator-embedded (digital twin) recommender system, where QWI consistently adapts to a shifting latent state and converges to an optimal policy, empirically corroborating our theoretical findings.