Tabular and Deep Learning for the Whittle Index
ACM Transactions on Modeling and Performance Evaluation of Computing Systems · 30.09.2024 · 9 (3) · 1-21
DOI: 10.1145/3670686 ↗Kurz gefasst
Fachartikel in der Zeitschrift ACM Transactions on Modeling and Performance Evaluation of Computing Systems, online erschienen am 13.08.2024. Verfasst von Francisco Robledo Relaño und 3 weiteren Autor:innen. Die Arbeit wurde bisher 8-mal zitiert (Crossref) und nennt 28 Literaturangaben. Gefördert von: Department of Education of the Basque Government through the Consolidated Research Group MATHMODE, French “Agence Nationale de la Recherche (ANR)”, S. S. Bhatnagar Fellowship from Council of Scientific and Industrial Research, Government of India and Google Research.
Abstract (Originalsprache)
The Whittle index policy is a heuristic that has shown remarkably good performance (with guaranteed asymptotic optimality) when applied to the class of problems known as Restless Multi-Armed Bandit Problems (RMABPs). In this article, we present QWI and QWINN, two reinforcement learning algorithms, respectively tabular and deep, to learn the Whittle index for the total discounted criterion. The key feature is the use of two time-scales, a faster one to update the state-action Q -values, and a relatively slower one to update the Whittle indices. In our main theoretical result, we show that QWI, which is a tabular implementation, converges to the real Whittle indices. We then present QWINN, an adaptation of QWI algorithm using neural networks to compute the Q -values on the faster time-scale, which is able to extrapolate information from one state to another and scales naturally to large state-space environments. For QWINN, we show that all local minima of the Bellman error are locally stable equilibria, which is the first result of its kind for DQN-based schemes. Numerical computations show that QWI and QWINN converge faster than the standard Q -learning algorithm, neural-network based approximate Q-learning, and other state-of-the-art algorithms.
Förderung
- Department of Education of the Basque Government through the Consolidated Research Group MATHMODE
- French “Agence Nationale de la Recherche (ANR)”
- S. S. Bhatnagar Fellowship from Council of Scientific and Industrial Research, Government of India and Google Research
Zitieren
APA
Relaño, F. R., Borkar, V., Ayesta, U., & Avrachenkov, K. (2024). Tabular and Deep Learning for the Whittle Index. ACM Transactions on Modeling and Performance Evaluation of Computing Systems, 9(3), 1-21. https://doi.org/10.1145/3670686
Vancouver
Relaño FR, Borkar V, Ayesta U, Avrachenkov K. Tabular and Deep Learning for the Whittle Index. ACM Transactions on Modeling and Performance Evaluation of Computing Systems. 2024;9(3):1-21. doi:10.1145/3670686
BibTeX
@article{Relao2024,
author = {Relaño, Francisco Robledo and Borkar, Vivek and Ayesta, Urtzi and Avrachenkov, Konstantin},
title = {Tabular and Deep Learning for the Whittle Index},
journal = {ACM Transactions on Modeling and Performance Evaluation of Computing Systems},
year = {2024},
volume = {9},
number = {3},
pages = {1--21},
doi = {10.1145/3670686}
}
EUVIMED