Event Details

Lagrangian Index Policy for Restless Bandits with Average Reward

We present the Lagrangian Index Policy (LIP) for restless multi-armed bandits with long-run average reward. In particular, we compare the performance of LIP with the performance of the Whittle Index Policy (WIP), both heuristic policies known to be asymptotically optimal under certain natural conditions. Even though in most cases their performances are very similar, in the cases when WIP shows bad performance, LIP continues to perform very well. We then propose reinforcement learning algorithms, both tabular and NN-based, to obtain online learning schemes for LIP in the model-free setting. The proposed reinforcement learning schemes for LIP require significantly less memory than the analogous schemes for WIP. We calculate analytically the Lagrangian index for the restart model, which applies to the optimal web crawling and the minimization of the weighted age of information.

This is a joint work with V.S. Borkar and P. Shah and a preprint is available at https://arxiv.org/abs/2412.12641.

Bio: Konstantin Avrachenkov received his Master degree in Control Theory from St. Petersburg State Polytechnic University (1996), Ph.D. degree in Mathematics from University of South Australia (2000) and Habilitation from University of Nice Sophia Antipolis (2010). Currently, he is a Director of Research at Inria Sophia Antipolis, France. He is an associate editor of Probability in the Engineering and Informational Sciences, Stochastic Models, ACM TOMPECS, IEEE Trans on Automatic Control, and on advisory boards of ACM POMACS and International Journal of Performance Evaluation. Konstantin has co-authored two books “Analytic Perturbation Theory and its Applications”, SIAM, 2013 and “Statistical Analysis of Networks”, Now Publishers, 2022; and more than 200 articles. He has won 5 best paper awards. His main theoretical research interests are Markov chains, Markov decision processes, random graphs and singular perturbations. He applies these methodological tools to the modelling and control of networks, and to design data mining and machine learning algorithms.