# Online Caching with no Regret: Optimistic Learning via Recommendations

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 31 of its 74 references that are in the map.
- First posted on arXiv 20 Apr 2022.

## Builds on (most cited first, 30 of 31)

- [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)
- [Online metric algorithms with untrusted predictions](https://mlsanity.com/paper/2003.02144/) (2020)
- [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)
- [A Tale of Two Metrics: Simultaneous Bounds on Competitiveness and Regret](https://mlsanity.com/paper/1508.03769/) (2015)
- [Learning to Cache With No Regrets](https://mlsanity.com/paper/1904.09849/) (2019)
- [Projection onto the capped simplex](https://mlsanity.com/paper/1503.01002/) (2015)
- [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)
- [LeadCache: Regret-Optimal Caching in Networks](https://mlsanity.com/paper/2009.08228/) (2020)
- [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)
- [Wireless Caching: Technical Misconceptions and Business Barriers](https://mlsanity.com/paper/1602.00173/) (2016)
- [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)
- [Online Caching with Optimistic Learning](https://mlsanity.com/paper/2202.10590/) (2022)
- [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)
- [Online User-AP Association with Predictive Scheduling in Wireless Caching Networks](https://mlsanity.com/paper/2008.00161/) (2020)
- [Network Friendly Recommendations: Optimizing for Long Viewing Sessions](https://mlsanity.com/paper/2110.00772/) (2021)

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

- [Adaptive Online Non-stochastic Control](https://mlsanity.com/paper/2310.02261/) (2023)
- [Optimistic Online Non-stochastic Control via FTRL](https://mlsanity.com/paper/2404.03309/) (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)

## 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 pre-reserved or dynamic storage 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 also extend the framework to learn and utilize the best request predictor in cases where many are available. We prove that the proposed optimistic learning caching policies can achieve sub-zero performance loss (regret) for perfect predictions, and maintain the sub-linear regret bound O(√ T), which is the best achievable bound for policies that do not use predictions, even for arbitrary-bad predictions. The performance of the proposed algorithms is evaluated with detailed trace-driven numerical tests.