Fast Computation of Partial Index and Application to an AoI Minimization Problem

In this paper, we study efficient algorithms for computing the partial index. We focus on an AoI (Age-of-Information) minimization problem under the generate-at-will setting such that multiple sources/agents transmit information updates to the base-station over multiple heterogeneous and unreliable wireless channels. While the partial index has been proposed to solve this otherwise exponential-complexity MDP problem, computing the partial index for each source still incurs significant complexity. Existing fast computation algorithms for Whittle index cannot be applied to this setting due to the multiple heterogeneous channels. Instead, we identify a number of general structural conditions for the per-agent MDP, based on which we develop a fast algorithm that can compute the partial index more efficiently. We then verify that the AoI problem under the generate-at-will setting satisfies these general conditions and our algorithm can compute the partial index for all states and all channels with a complexity of$\mathcal{O}(M^{3}K^{3})$, where$K$denotes the number of per-source states and$M$denotes the number of channel types. Our numerical results confirm that our proposed algorithm is significantly faster in computing the partial index than standard methods based on binary search.