Model-Based Learning of Whittle indices
Abstract
We present BLINQ , a new model-based algorithm that learns the Whittle indices of an indexable, communicating and unichain Markov Decision Process (MDP). Our approach relies on building an empirical estimate of the MDP and then computing its Whittle indices using an extended version of a state-of-the-art existing algorithm. We provide a proof of convergence to the Whittle indices we want to learn as well as a bound on the time needed to learn them with arbitrary precision. Moreover, we investigate its computational complexity. Our numerical experiments suggest that BLINQ significantly outperforms existing Q -learning approaches in terms of the number of samples needed to get an accurate approximation. In addition, it has a total computational cost even lower than Q -learning for any reasonably high number of samples. These observations persist even when the Q -learning algorithms are sped up using neural networks to predict Q-values.
Related
- Smoothness estimation for Whittle–Matérn processes on closed Riemannian manifolds
- Discrete Exterior Calculus-based Whittle-Matérn Fields on Meshes
- Whittle index approach to multi-server scheduling with convex delay costs and impatient customers
- Learning Global Sensitivity Indices from Observational Data: A Metamodel-Based Approach
- A bridge representation of Gaussian Whittle-Matérn fields on compact metric graphs
BibTeX
@article{charlesrebuffe2026modelbased,
title = {{Model-Based Learning of Whittle indices}},
author = {Joël Charles-Rebuffé and Nicolas Gast and Bruno Gaujal},
journal = {ACM Transactions on Modeling and Performance Evaluation of Computing Systems},
year = {2026},
month = aug,
doi = {10.1145/3844508},
eprint = {2511.20397},
archivePrefix = {arXiv},
url = {https://hal.science/hal-05767156v1},
note = {CC BY-NC 4.0},
}
RIS
TY - JOUR
TI - Model-Based Learning of Whittle indices
AU - Joël Charles-Rebuffé
AU - Nicolas Gast
AU - Bruno Gaujal
PY - 2026
DA - 2026/08/29
JO - ACM Transactions on Modeling and Performance Evaluation of Computing Systems
DO - 10.1145/3844508
UR - https://hal.science/hal-05767156v1
AB - We present BLINQ , a new model-based algorithm that learns the Whittle indices of an indexable, communicating and unichain Markov Decision Process (MDP). Our approach relies on building an empirical estimate of the MDP and then computing its Whittle indices using an extended version of a state-of-the-art existing algorithm. We provide a proof of convergence to the Whittle indices we want to learn as well as a bound on the time needed to learn them with arbitrary precision. Moreover, we investigate its computational complexity. Our numerical experiments suggest that BLINQ significantly outperforms existing Q -learning approaches in terms of the number of samples needed to get an accurate approximation. In addition, it has a total computational cost even lower than Q -learning for any reasonably high number of samples. These observations persist even when the Q -learning algorithms are sped up using neural networks to predict Q-values.
SN - 2376-3639
SN - 2376-3647
ER -