# Online Caching with Optimal Switching Regret

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- Builds on 4 of its 20 references that are in the map.
- First posted on arXiv 18 Jan 2021.

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

- [Improved Strongly Adaptive Online Learning using Coin Betting](https://mlsanity.com/paper/1610.04578/) (2016)
- [Learning to Cache With No Regrets](https://mlsanity.com/paper/1904.09849/) (2019)
- [Temporal Locality in Today's Content Caching: Why it Matters and How to Model it](https://mlsanity.com/paper/1305.7114/) (2013)
- [Online Coded Caching](https://mlsanity.com/paper/1311.3646/) (2013)

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

- [On Optimal Caching and Model Multiplexing for Large Model Inference](https://mlsanity.com/paper/2306.02003/) (2023)
- [No-Regret Caching via Online Mirror Descent](https://mlsanity.com/paper/2101.12588/) (2021)
- [Efficient Prompt Caching via Embedding Similarity](https://mlsanity.com/paper/2402.01173/) (2024)
- [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)
- [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)
- [On the Regret of Coded Caching with Adversarial Requests](https://mlsanity.com/paper/2409.12387/) (2024)
- [Follow The Approximate Sparse Leader for No-Regret Online Sparse Linear Approximation](https://mlsanity.com/paper/2501.00799/) (2025)
- [Optimistic Learning for Communication Networks](https://mlsanity.com/paper/2504.03499/) (2025)

## Abstract (arXiv)

We consider the classical uncoded caching problem from an online learning point-of-view. A cache of limited storage capacity can hold C files at a time from a large catalog. A user requests an arbitrary file from the catalog at each time slot. Before the file request from the user arrives, a caching policy populates the cache with any C files of its choice. In the case of a cache-hit, the policy receives a unit reward and zero rewards otherwise. In addition to that, there is a cost associated with fetching files to the cache, which we refer to as the switching cost. The objective is to design a caching policy that incurs minimal regret while considering both the rewards due to cache-hits and the switching cost due to the file fetches. The main contribution of this paper is the switching regret analysis of a Follow the Perturbed Leader-based anytime caching policy, which is shown to have an order optimal switching regret. In this pursuit, we improve the best-known switching regret bound for this problem by a factor of Theta(√C). We conclude the paper by comparing the performance of different popular caching policies using a publicly available trace from a commercial CDN server.