On the Optimality of the Whittle’s Index Policy for Minimizing the Age of Information
Ali Maatouk, Saad Kriouile, Mohamad Assaad, Anthony Ephremides
Abstract
In this article, we consider the average age minimization problem where a central entity schedules M users among the N available users for transmission over unreliable channels. It is well-known that obtaining the optimal policy, in this case, is a difficult task. Accordingly, the Whittle's index policy has been suggested in earlier works as a heuristic for this problem. However, the analysis of its performance remained elusive. In the sequel, we overcome these difficulties and provide rigorous results on its asymptotic optimality in the many-users regime. Specifically, we first establish its optimality in the neighborhood of a specific system's state. Next, we extend our proof to the global case under a recurrence assumption, which we verify numerically. These findings showcase that the Whittle's index policy has analytically provable optimality in the many-users regime for the AoI minimization problem. Finally, numerical results that showcase its performance and corroborate our theoretical findings are presented.