# Learning to Cache With No Regrets

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

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Apr 2019.

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

- [No-Regret Caching via Online Mirror Descent](https://mlsanity.com/paper/2101.12588/) (2021)
- [Online Caching with Optimal Switching Regret](https://mlsanity.com/paper/2101.07043/) (2021)
- [Whittle Index based Q-Learning for Wireless Edge Caching with Linear Function Approximation](https://mlsanity.com/paper/2202.13187/) (2022)
- [Online Caching with Optimistic Learning](https://mlsanity.com/paper/2202.10590/) (2022)
- [Online Caching with no Regret: Optimistic Learning via Recommendations](https://mlsanity.com/paper/2204.09345/) (2022)
- [Ascent Similarity Caching with Approximate Indexes](https://mlsanity.com/paper/2107.00957/) (2021)
- [Universal Caching](https://mlsanity.com/paper/2205.04860/) (2022)
- [On the Regret of Online Edge Service Hosting](https://mlsanity.com/paper/2303.06851/) (2023)
- [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)
- [Online Subset Selection using α-Core with no Augmented Regret](https://mlsanity.com/paper/2209.14222/) (2022)
- [On the Regret of Coded Caching with Adversarial Requests](https://mlsanity.com/paper/2409.12387/) (2024)
- [Optimistic Learning for Communication Networks](https://mlsanity.com/paper/2504.03499/) (2025)
- [Continuous Semantic Caching for Low-Cost LLM Serving](https://mlsanity.com/paper/2604.20021/) (2026)
- [The Sample Complexity of Quantum Entanglement Allocation](https://mlsanity.com/paper/2609.10141/) (2026)

## Abstract (arXiv)

This paper introduces a novel caching analysis that, contrary to prior work, makes no modeling assumptions for the file request sequence. We cast the caching problem in the framework of Online Linear Optimization (OLO), and introduce a class of minimum regret caching policies, which minimize the losses with respect to the best static configuration in hindsight when the request model is unknown. These policies are very important since they are robust to popularity deviations in the sense that they learn to adjust their caching decisions when the popularity model changes. We first prove a novel lower bound for the regret of any caching policy, improving existing OLO bounds for our setting. Then we show that the Online Gradient Ascent (OGA) policy guarantees a regret that matches the lower bound, hence it is universally optimal. Finally, we shift our attention to a network of caches arranged to form a bipartite graph, and show that the Bipartite Subgradient Algorithm (BSA) has no regret