On the Active-Time Condition for Partial Indexability and Application to Heterogeneous-Channel AoI Minimization
Sixiang Zhou, Xiaojun Lin · 2024
Motivated by an Age-of-Information (AoI) minimization problem for systems with both fast (but unreliable) and slow (but more reliable) channels, in this paper we are interested in MDPs (Markov Decision Processes) where multiple agents compete for multiple heterogeneous channels. Such an MDP is known to suffer the curse-of-dimensionality when the number of sources is large. Recently, a partial index approach, which generalizes the Whittle index for single-channel systems, has been proposed to decompose such a large-scale MDP into smaller sub-problems, if each sub-problem satisfies the partial indexability and the precise division property. Unfortunately, verifying partial indexability and the precise division property is highly non-trivial. This paper provides a new Active-Time (AT) condition, which ensures the precise-division property (which then implies the partial indexability). Our new AT condition generalizes the AT condition for Whittle indexability in a non-trivial manner, and is much easier to verify for systems with heterogeneous channels. We then apply our AT condition to the fast-slow-channel setting, and establish its partial indexability for the first time in the literature. Our analysis reveals new semi-threshold structures of the optimal policy, and uses a new coupling approach to analyze the corresponding AT condition, which could also be of independent interest. Numerical simulations are provided to verify our theoretical results and to demonstrate the close-to-optimal performance of the partial index policy.