Testing Indexability and Computing Whittle and Gittins Index in Subcubic Time
| Autor: | Gast, Nicolas, Gaujal, Bruno, Khun, Kimang |
|---|---|
| Přispěvatelé: | Performance analysis and optimization of LARge Infrastructures and Systems (POLARIS), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire d'Informatique de Grenoble (LIG), Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP ), Université Grenoble Alpes (UGA)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP ), Université Grenoble Alpes (UGA), ANR-19-CE23-0015,REFINO,Optimisation grace au Champ Moyen Raffiné(2019) |
| Jazyk: | angličtina |
| Rok vydání: | 2023 |
| Předmět: |
FOS: Computer and information sciences
Multi-armed bandit [INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC] Computer Science - Performance Whittle Index Gittins Index Restless Bandit Multi-armed Bandit Sherman-Morrison Markov Decision Process Fast Matrix Multiplication Sherman-Morrison Gittins index Whittle index Computational Complexity (cs.CC) [INFO.INFO-NA]Computer Science [cs]/Numerical Analysis [cs.NA] Sherman-Morrison-Woodbury Performance (cs.PF) Restless bandit Computer Science - Computational Complexity [INFO.INFO-PF]Computer Science [cs]/Performance [cs.PF] Fast Matrix Multiplication Markov decision process |
| Zdroj: | Mathematical Methods of Operations Research Mathematical Methods of Operations Research, 2023, ⟨10.1007/s00186-023-00821-4⟩ |
| ISSN: | 1432-2994 1432-5217 |
| Popis: | Whittle index is a generalization of Gittins index that provides very efficient allocation rules for restless multi-armed bandits. In this work, we develop an algorithm to test the indexability and compute the Whittle indices of any finite-state restless bandit arm. This algorithm works in the discounted and non-discounted cases, and can compute Gittins index. Our algorithm builds on three tools: (1) a careful characterization of Whittle index that allows one to compute recursively the kth smallest index from the $(k - 1)$th smallest, and to test indexability, (2) the use of the Sherman-Morrison formula to make this recursive computation efficient, and (3) a sporadic use of the fastest matrix inversion and multiplication methods to obtain a subcubic complexity. We show that an efficient use of the Sherman-Morrison formula leads to an algorithm that computes Whittle index in $(2/3)n^3 + o(n^3)$ arithmetic operations, where $n$ is the number of states of the arm. The careful use of fast matrix multiplication leads to the first subcubic algorithm to compute Whittle or Gittins index: By using the current fastest matrix multiplication, the theoretical complexity of our algorithm is O(n^2.5286 ). We also develop an efficient implementation of our algorithm that can compute indices of Markov chains with several thousands of states in less than a few seconds. Mathematical Methods of Operations Research, 2023 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink