On the Global Optimality of Whittle’s Index Policy for Minimizing the Age of Information
- 18 October 2021
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 68 (1) , 572-600
Abstract
This paper examines the average age minimization problem where only a fraction of the network users can transmit simultaneously over unreliable channels. Finding the optimal scheduling scheme, in this case, is known to be challenging. Accordingly, the Whittle’s index policy was proposed in the literature as a low-complexity heuristic to the problem. Although simple to implement, characterizing this policy’s performance is recognized to be a notoriously tricky task. In the sequel, we provide a new mathematical approach to establish its optimality in the many-users regime for specific network settings. Contrary to previous works in the literature that use restrictive mathematical assumptions, which can be challenging to verify, our novel approach is based on intricate techniques and it is free of any strong mathematical assumptions. These findings showcase that the Whittle’s index policy has analytically provable asymptotic optimality for the AoI minimization problem. Finally, we lay out numerical results that corroborate our theoretical findings and demonstrate the policy’s notable performance in the many-users regime.Keywords
This publication has 25 references indexed in Scilit:
- Update or Wait: How to Keep Your Data FreshIEEE Transactions on Information Theory, 2017
- Age-optimal information updates in multihop networks2017
- Downlink Scheduling Over Markovian Fading ChannelsIEEE/ACM Transactions on Networking, 2015
- Indexability of Restless Bandit Problems and Optimality of Whittle Index for Dynamic Multichannel AccessIEEE Transactions on Information Theory, 2010
- Whittle's index policy for a multi-class queueing system with convex holding costsMathematical Methods of Operations Research, 2003
- Exploiting structure in adaptive dynamic programming algorithms for a stochastic batch service problemEuropean Journal of Operational Research, 2002
- The Complexity of Optimal Queuing Network ControlMathematics of Operations Research, 1999
- On an index policy for restless banditsJournal of Applied Probability, 1990
- Restless bandits: activity allocation in a changing worldJournal of Applied Probability, 1988
- Strong approximation theorems for density dependent Markov chainsStochastic Processes and their Applications, 1978