# On the Regret of Coded Caching with Adversarial Requests

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 11 of its 35 references that are in the map.
- First posted on arXiv 19 Sep 2024.

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

- [Online Linear Optimization via Smoothing](https://mlsanity.com/paper/1405.6076/) (2014)
- [Learning to Cache With No Regrets](https://mlsanity.com/paper/1904.09849/) (2019)
- [LeadCache: Regret-Optimal Caching in Networks](https://mlsanity.com/paper/2009.08228/) (2020)
- [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)
- [Regret-Optimal Online Caching for Adversarial and Stochastic Arrivals](https://mlsanity.com/paper/2211.16051/) (2022)
- [Online Coded Caching](https://mlsanity.com/paper/1311.3646/) (2013)
- [Coded Caching with Nonuniform Demands](https://mlsanity.com/paper/1308.0178/) (2013)
- [Hierarchical Coded Caching](https://mlsanity.com/paper/1403.7007/) (2014)
- [Learning to Cooperate in D2D Caching Networks](https://mlsanity.com/paper/1905.01530/) (2019)
- [Structured Index Coding Problem and Multi-access Coded Caching](https://mlsanity.com/paper/2012.04705/) (2020)

## Abstract (arXiv)

We study the well-known coded caching problem in an online learning framework, wherein requests arrive sequentially, and an online policy can update the cache contents based on the history of requests seen thus far. We introduce a caching policy based on the Follow-The-Perturbed-Leader principle and show that for any time horizon T and any request sequence, it achieves a sub-linear regret of O(√(T) ) with respect to an oracle that knows the request sequence beforehand. Our study marks the first examination of adversarial regret in the coded caching setup. Furthermore, we also address the issue of switching cost by establishing an upper bound on the expected number of cache updates made by our algorithm under unrestricted switching and also provide an upper bound on the regret under restricted switching when cache updates can only happen in a pre-specified subset of timeslots. Finally, we validate our theoretical insights with numerical results using a real-world dataset