Testing Indexability and Computing Whittle and Gittins Index in Subcubic Time

Nicolas Gast (1) , Bruno Gaujal (1) , Kimang Khun (1)

1 POLARIS - Performance analysis and optimization of LARge Infrastructures and Systems

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.

Mots clés: Whittle index; Gittins index; Restless bandit; Markov decision process; Sherman-Morrison-Woodbury; Multi-armed bandit; Whittle Index Gittins Index Restless Bandit Multi-armed Bandit Sherman-Morrison Markov Decision Process Fast Matrix Multiplication; Whittle Index; Gittins Index; Restless Bandit; Multi-armed Bandit; Sherman-Morrison; Markov Decision Process; Fast Matrix Multiplication

Domaines: Complexité [cs.CC]; Analyse numérique [cs.NA]; Performance et fiabilité [cs.PF]

Nicolas Gast, Bruno Gaujal, Kimang Khun. Testing Indexability and Computing Whittle and Gittins Index in Subcubic Time. Mathematical Methods of Operations Research, 2023, ⟨10.1007/s00186-023-00821-4⟩. ⟨hal-03602458v5⟩