Tabular and Deep Learning of Whittle Index

Description

The Whittle index policy is a heuristic that has shown remarkable good performance (with guaranted asymptotic optimality) when applied to the class of problems known as Restless Multi-Armed Bandit Problems (RMABP). In this paper we present QWI and QWINN, two algorithms capable of learning the Whittle indices for the total discounted criterion. The key feature is the usage of two timescales , 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 timescale , which is able to extrapolate information from one state to another and scales naturally to large state-space environments. Numerical computations show that QWI and QWINN converge much faster than the standard Q-learning algorithm, neural-network based approximate Q-learning and other state of the art algorithms.

Abstract (French)

La politique de l'indice de Whittle est une heuristique qui a montré des performances remarquables (avec une optimalité asymptotique garantie) lorsqu'elle est appliquée à la classe de problèmes connus sous le nom de problèmes de bandits multi-bras sans repos (RMABP). Dans cet article, nous présentons QWI et QWINN, deux algorithmes capables d'apprendre les indices de Whittle pour le critère de décote totale. La caractéristique principale est l'utilisation de deux échelles de temps, une plus rapide pour mettre à jour les Q-values état-action, et une relativement plus lente pour mettre à jour les indices de Whittle. Dans notre principal résultat théorique, nous montrons que QWI, qui est une implémentation tabulaire, converge vers les vrais indices de Whittle. Nous présentons ensuite QWINN, une adaptation de l'algorithme QWI utilisant des réseaux neuronaux pour calculer les Q-values sur l'échelle de temps la plus rapide, qui est capable d'extrapoler l'information d'un état à un autre et qui s'adapte naturellement aux grands espaces d'état. Les calculs numériques montrent que QWI et QWINN convergent beaucoup plus rapidement que l'algorithme standard de Q-learning, le Q-learning approximatif basé sur les réseaux neuronaux et d'autres algorithmes de pointe.

Abstract

International audience

Additional details