# An Online Learning Approach to Optimizing Time-Varying Costs of AoI

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 41 references that are in the map.
- First posted on arXiv 27 May 2021.

## Builds on (most cited first, 12 of 12)

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Non-stationary Stochastic Optimization](https://mlsanity.com/paper/1307.5449/) (2013)
- [Online Optimization : Competing with Dynamic Comparators](https://mlsanity.com/paper/1501.06225/) (2015)
- [Learning to Optimize under Non-Stationarity](https://mlsanity.com/paper/1810.03024/) (2018)
- [Optimal Exploration-Exploitation in a Multi-Armed-Bandit Problem with Non-stationary Rewards](https://mlsanity.com/paper/1405.3316/) (2014)
- [Scheduling Policies for Minimizing Age of Information in Broadcast Wireless Networks](https://mlsanity.com/paper/1801.01803/) (2018)
- [A Whittle Index Approach to Minimizing Functions of Age of Information](https://mlsanity.com/paper/1908.10438/) (2019)
- [Sampling for Data Freshness Optimization: Non-linear Age Functions](https://mlsanity.com/paper/1812.07241/) (2018)
- [Optimizing Information Freshness in Wireless Networks under General Interference Constraints](https://mlsanity.com/paper/1803.06467/) (2018)
- [Regret of Age-of-Information Bandits](https://mlsanity.com/paper/2001.09317/) (2020)
- [Optimizing Age-of-Information in a Multi-class Queueing System](https://mlsanity.com/paper/1504.05103/) (2015)
- [Performance Characterization Using AoI in a Single-loop Networked Control System](https://mlsanity.com/paper/1901.06694/) (2019)

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

- [Online Learning of Whittle Indices for Restless Bandits with Non-Stationary Transition Kernels](https://mlsanity.com/paper/2506.18186/) (2025)
- [Age Optimal Sampling for Unreliable Channels under Unknown Channel Statistics](https://mlsanity.com/paper/2412.18119/) (2024)
- [Age-of-information minimization under energy harvesting and non-stationary environment](https://mlsanity.com/paper/2504.04916/) (2025)
- [Online Learning for Optimizing AoI-Energy Tradeoff under Unknown Channel Statistics](https://mlsanity.com/paper/2509.18654/) (2025)
- [Timely Information Updating for Mobile Devices Without and With ML Advice](https://mlsanity.com/paper/2512.17381/) (2025)
- [Learning When to Update: A Near-Optimal Timing Bandit Approach](https://mlsanity.com/paper/2609.37932/) (2026)

## Abstract (arXiv)

We consider systems that require timely monitoring of sources over a communication network, where the cost of delayed information is unknown, time-varying and possibly adversarial. For the single source monitoring problem, we design algorithms that achieve sublinear regret compared to the best fixed policy in hindsight. For the multiple source scheduling problem, we design a new online learning algorithm called Follow-the-Perturbed-Whittle-Leader and show that it has low regret compared to the best fixed scheduling policy in hindsight, while remaining computationally feasible. The algorithm and its regret analysis are novel and of independent interest to the study of online restless multi-armed bandit problems. We further design algorithms that achieve sublinear regret compared to the best dynamic policy when the environment is slowly varying. Finally, we apply our algorithms to a mobility tracking problem. We consider non-stationary and adversarial mobility models and illustrate the performance benefit of using our online learning algorithms compared to an oblivious scheduling policy.