# Regret-Optimal Online Caching for Adversarial and Stochastic Arrivals

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Nov 2022.

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

- [On Optimal Caching and Model Multiplexing for Large Model Inference](https://mlsanity.com/paper/2306.02003/) (2023)
- [Efficient Prompt Caching via Embedding Similarity](https://mlsanity.com/paper/2402.01173/) (2024)
- [An Online Gradient-Based Caching Policy with Logarithmic Complexity and Regret Guarantees](https://mlsanity.com/paper/2405.01263/) (2024)
- [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)

## Abstract (arXiv)

We consider the online caching problem for a cache of limited size. In a time-slotted system, a user requests one file from a large catalog in each slot. If the requested file is cached, the policy receives a unit reward and zero rewards otherwise. We show that a Follow the Perturbed Leader (FTPL)-based anytime caching policy is simultaneously regret-optimal for both adversarial and i.i.d. stochastic arrivals. Further, in the setting where there is a cost associated with switching the cached contents, we propose a variant of FTPL that is order-optimal with respect to time for both adversarial and stochastic arrivals and has a significantly better performance compared to FTPL with respect to the switching cost for stochastic arrivals. We also show that these results can be generalized to the setting where there are constraints on the frequency with which cache contents can be changed. Finally, we validate the results obtained on various synthetic as well as real-world traces.