  We consider a system with a single source that measures/tracks a time-varying
quantity and periodically attempts to report these measurements to a monitoring
station. Each update from the source has to be scheduled on one of K available
communication channels. The probability of success of each attempted
communication is a function of the channel used. This function is unknown to
the scheduler.
  The metric of interest is the Age-of-Information (AoI), formally defined as
the time elapsed since the destination received the recent most update from the
source. We model our scheduling problem as a variant of the multi-arm bandit
problem with communication channels as arms. We characterize a lower bound on
the AoI regret achievable by any policy and characterize the performance of
UCB, Thompson Sampling, and their variants. Our analytical results show that
UCB and Thompson sampling are order-optimal for AoI bandits. In addition, we
propose novel policies which, unlike UCB and Thompson Sampling, use the current
AoI to make scheduling decisions. Via simulations, we show the proposed
AoI-aware policies outperform existing AoI-agnostic policies.
