Aging Bandits: Regret Analysis and Order-Optimal Learning Algorithm for
  Wireless Networks with Stochastic Arrivals
  We consider a single-hop wireless network with sources transmitting
time-sensitive information to the destination over multiple unreliable
channels. Packets from each source are generated according to a stochastic
process with known statistics and the state of each wireless channel (ON/OFF)
varies according to a stochastic process with unknown statistics. The
reliability of the wireless channels is to be learned through observation. At
every time slot, the learning algorithm selects a single pair (source, channel)
and the selected source attempts to transmit its packet via the selected
channel. The probability of a successful transmission to the destination
depends on the reliability of the selected channel. The goal of the learning
algorithm is to minimize the Age-of-Information (AoI) in the network over $T$
time slots. To analyze the performance of the learning algorithm, we introduce
the notion of AoI regret, which is the difference between the expected
cumulative AoI of the learning algorithm under consideration and the expected
cumulative AoI of a genie algorithm that knows the reliability of the channels
a priori. The AoI regret captures the penalty incurred by having to learn the
statistics of the channels over the $T$ time slots. The results are two-fold:
first, we consider learning algorithms that employ well-known solutions to the
stochastic multi-armed bandit problem (such as $\epsilon$-Greedy, Upper
Confidence Bound, and Thompson Sampling) and show that their AoI regret scales
as $\Theta(\log T)$; second, we develop a novel learning algorithm and show
that it has $O(1)$ regret. To the best of our knowledge, this is the first
learning algorithm with bounded AoI regret.
