  This paper studies the minimum-age scheduling problem in a wireless sensor
network where an access point (AP) monitors the state of an object via a set of
sensors. The freshness of the sensed state, measured by the age-of-information
(AoI), varies at different sensors and is not directly observable to the AP.
The AP has to decide which sensor to query/sample in order to get the most
updated state information of the object (i.e., the state information with the
minimum AoI). In this paper, we formulate the minimum-age scheduling problem as
a multi-armed bandit problem with partially observable arms and explore the
greedy policy to minimize the expected AoI sampled over an infinite horizon. To
analyze the performance of the greedy policy, we 1) put forth a relaxed greedy
policy that decouples the sampling processes of the arms, 2) formulate the
sampling process of each arm as a partially observable Markov decision process
(POMDP), and 3) derive the average sampled AoI under the relaxed greedy policy
as a sum of the average AoI sampled from individual arms. Numerical and
simulation results validate that the relaxed greedy policy is an excellent
approximation to the greedy policy in terms of the expected AoI sampled over an
infinite horizon.
