# Regret of Age-of-Information Bandits

arXiv: https://arxiv.org/abs/2001.09317 · HTML: https://mlsanity.com/paper/2001.09317/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Jan 2020.

## Built on by (most cited first, 4 of 4)

- [An Online Learning Approach to Optimizing Time-Varying Costs of AoI](https://mlsanity.com/paper/2105.13383/) (2021)
- [Representative Arm Identification: A fixed confidence approach to identify cluster representatives](https://mlsanity.com/paper/2408.14195/) (2024)
- [MAB-Based Channel Scheduling for Asynchronous Federated Learning in Non-Stationary Environments](https://mlsanity.com/paper/2503.01324/) (2025)
- [On the Regularity and Fairness of Combinatorial Multi-Armed Bandit](https://mlsanity.com/paper/2509.12457/) (2025)

## Abstract (arXiv)

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.