  Age-of-Information (AoI) is a critical metric for network applications.
Existing works mostly address optimization with homogeneous AoI requirements,
which is different from practice. In this work, we optimize uplink scheduling
for an access point (AP) over multiple unknown channels with heterogeneous AoI
requirements defined by AoI-dependent costs. The AP serves $N$ users by using
$M$ channels without the channel state information. Each channel serves only
one user in each decision epoch. The optimization objective is to minimize the
time-averaged AoI-dependent costs plus additional communication transmission
costs over an infinite horizon. This decision-making problem can be formulated
as a Markov decision process, but it is computationally intractable because the
size of the state space grows exponentially with respect to the number of
users. To alleviate the challenge, we reformulate the problem as a variant of
the restless multi-armed bandit (RMAB) problem and leverage Whittle's index
theory to design an index-based scheduling policy algorithm. We derive an
analytic formula for the indices, which reduces the computational overhead and
facilitates online adaptation. Our numerical examples show that our index-based
scheduling policy achieves comparable performance to the optimal policy and
outperforms several other heuristics.
