# Timely Information Updating for Mobile Devices Without and With ML Advice

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 14 of its 31 references that are in the map.
- First posted on arXiv 19 Dec 2025.

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

- [Competitive caching with machine learned advice](https://mlsanity.com/paper/1802.05399/) (2018)
- [The Primal-Dual method for Learning Augmented Algorithms](https://mlsanity.com/paper/2010.11632/) (2020)
- [Age of Information: An Introduction and Survey](https://mlsanity.com/paper/2007.08564/) (2020)
- [Survey of Important Issues in UAV Communication Networks](https://mlsanity.com/paper/1603.08462/) (2016)
- [Scheduling Policies for Minimizing Age of Information in Broadcast Wireless Networks](https://mlsanity.com/paper/1801.01803/) (2018)
- [On The Age Of Information In Status Update Systems With Packet Management](https://mlsanity.com/paper/1506.08637/) (2015)
- [An Online Learning Approach to Optimizing Time-Varying Costs of AoI](https://mlsanity.com/paper/2105.13383/) (2021)
- [Online Energy-Efficient Scheduling for Timely Information Downloads in Mobile Networks](https://mlsanity.com/paper/1901.03137/) (2019)
- [Age Minimization in Energy Harvesting Communications: Energy-Controlled Delays](https://mlsanity.com/paper/1712.03945/) (2017)
- [Characterizing Power Consumption of Dual-Frequency GNSS of a Smartphone](https://mlsanity.com/paper/1910.13041/) (2019)
- [Throughput and Age of Information in a Cellular-based IoT Network](https://mlsanity.com/paper/2005.09547/) (2020)
- [Learning-augmented Online Minimization of Age of Information and Transmission Costs](https://mlsanity.com/paper/2403.02573/) (2024)
- [Age of Information Versions: a Semantic View of Markov Source Monitoring](https://mlsanity.com/paper/2406.14594/) (2024)
- [Understanding the Fundamental Trade-Off Between Age of Information and Throughput in Unreliable Wireless Networks](https://mlsanity.com/paper/2508.12185/) (2025)

## Abstract (arXiv)

This paper investigates an information update system in which a mobile device monitors a physical process and sends status updates to an access point (AP). A fundamental trade-off arises between the timeliness of the information maintained at the AP and the update cost incurred at the device. To address this trade-off, we propose an online algorithm that determines when to transmit updates using only available observations. The proposed algorithm asymptotically achieves the optimal competitive ratio against an adversary that can simultaneously manipulate multiple sources of uncertainty, including the operation duration, information staleness, update cost, and update opportunities. Furthermore, by incorporating machine learning (ML) advice of unknown reliability into the design, we develop an ML-augmented algorithm that asymptotically attains the optimal consistency-robustness trade-off, even when the adversary can additionally corrupt the ML advice. The optimal competitive ratio scales linearly with the range of update costs, but is unaffected by other sources of uncertainty. Moreover, an optimal competitive online algorithm exhibits a threshold-like response to the ML advice: it either fully trusts or completely ignores the ML advice, as partially trusting the advice cannot improve the consistency without severely degrading the robustness. Extensive simulations in stochastic settings further validate the theoretical findings in the adversarial environment.