# Online Caching with Optimistic Learning

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 60 references that are in the map.
- First posted on arXiv 22 Feb 2022.

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

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Online Learning: A Modern Introduction Using Convex Optimization](https://mlsanity.com/paper/1912.13213/) (2019)
- [Competitive caching with machine learned advice](https://mlsanity.com/paper/1802.05399/) (2018)
- [Optimization, Learning, and Games with Predictable Sequences](https://mlsanity.com/paper/1311.1869/) (2013)
- [An Online Convex Optimization Approach to Dynamic Network Resource Allocation](https://mlsanity.com/paper/1701.03974/) (2017)
- [How to Retrain Recommender System? A Sequential Meta-Learning Method](https://mlsanity.com/paper/2005.13258/) (2020)
- [Online Learning with Imperfect Hints](https://mlsanity.com/paper/2002.04726/) (2020)
- [Distributed Online Convex Optimization with Time-Varying Coupled Inequality Constraints](https://mlsanity.com/paper/1903.04277/) (2019)
- [Learning to Cache With No Regrets](https://mlsanity.com/paper/1904.09849/) (2019)
- [Optimal and Scalable Caching for 5G Using Reinforcement Learning of Space-time Popularities](https://mlsanity.com/paper/1708.06698/) (2017)
- [A Reinforcement-Learning Approach to Proactive Caching in Wireless Networks](https://mlsanity.com/paper/1712.07084/) (2017)
- [Temporal Locality in Today's Content Caching: Why it Matters and How to Model it](https://mlsanity.com/paper/1305.7114/) (2013)
- [Online Convex Optimization with Perturbed Constraints](https://mlsanity.com/paper/1906.00049/) (2019)
- [No-Regret Caching via Online Mirror Descent](https://mlsanity.com/paper/2101.12588/) (2021)
- [The Role of Caching in Future Communication Systems and Networks](https://mlsanity.com/paper/1805.11721/) (2018)
- [Reinforcement Learning for Adaptive Caching with Dynamic Storage Pricing](https://mlsanity.com/paper/1812.08593/) (2018)
- [Spatial multi-LRU Caching for Wireless Networks with Coverage Overlaps](https://mlsanity.com/paper/1602.07623/) (2016)
- [Online Convex Optimization for Caching Networks](https://mlsanity.com/paper/2001.06351/) (2020)
- [Cache Optimization Models and Algorithms](https://mlsanity.com/paper/1912.12339/) (2019)
- [Placing Dynamic Content in Caches with Small Population](https://mlsanity.com/paper/1601.03926/) (2016)
- [Implicit Coordination of Caches in Small Cell Networks under Unknown Popularity Profiles](https://mlsanity.com/paper/1804.01895/) (2018)
- [Catalog Dynamics: Impact of Content Publishing and Perishing on the Performance of a LRU Cache](https://mlsanity.com/paper/1403.5479/) (2014)
- [Spatial multi-LRU: Distributed Caching for Wireless Networks with Coverage Overlaps](https://mlsanity.com/paper/1612.04363/) (2016)

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

- [Optimistic No-regret Algorithms for Discrete Caching](https://mlsanity.com/paper/2208.06414/) (2022)
- [Online Caching with no Regret: Optimistic Learning via Recommendations](https://mlsanity.com/paper/2204.09345/) (2022)
- [No-Regret Caching with Noisy Request Estimates](https://mlsanity.com/paper/2309.02055/) (2023)
- [An Online Gradient-Based Caching Policy with Logarithmic Complexity and Regret Guarantees](https://mlsanity.com/paper/2405.01263/) (2024)
- [Efficient and Optimal No-Regret Caching under Partial Observation](https://mlsanity.com/paper/2503.02758/) (2025)
- [Optimistic Learning for Communication Networks](https://mlsanity.com/paper/2504.03499/) (2025)
- [SEArch: Optimistic Policy Selection Between Scene Noise and Drift for UAV Radar Search](https://mlsanity.com/paper/2606.01325/) (2026)

## Abstract (arXiv)

The design of effective online caching policies is an increasingly important problem for content distribution networks, online social networks and edge computing services, among other areas. This paper proposes a new algorithmic toolbox for tackling this problem through the lens of optimistic online learning. We build upon the Follow-the-Regularized-Leader (FTRL) framework which is developed further here to include predictions for the file requests, and we design online caching algorithms for bipartite networks with fixed-size caches or elastic leased caches subject to time-average budget constraints. The predictions are provided by a content recommendation system that influences the users viewing activity, and hence can naturally reduce the caching network's uncertainty about future requests. We prove that the proposed optimistic learning caching policies can achieve sub-zero performance loss (regret) for perfect predictions, and maintain the best achievable regret bound O(√ T) even for arbitrary-bad predictions. The performance of the proposed algorithms is evaluated with detailed trace-driven numerical tests.