# Efficient and Optimal No-Regret Caching under Partial Observation

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 43 references that are in the map.
- First posted on arXiv 4 Mar 2025.

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

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Follow the Leader If You Can, Hedge If You Must](https://mlsanity.com/paper/1301.0534/) (2013)
- [Fighting Bandits with a New Kind of Smoothness](https://mlsanity.com/paper/1512.04152/) (2015)
- [Online Linear Optimization via Smoothing](https://mlsanity.com/paper/1405.6076/) (2014)
- [Importance weighting without importance weights: An efficient algorithm for combinatorial semi-bandits](https://mlsanity.com/paper/1503.05087/) (2015)
- [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)
- [Temporal Locality in Today's Content Caching: Why it Matters and How to Model it](https://mlsanity.com/paper/1305.7114/) (2013)
- [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)
- [Optimistic No-regret Algorithms for Discrete Caching](https://mlsanity.com/paper/2208.06414/) (2022)
- [Adaptive Caching Networks with Optimality Guarantees](https://mlsanity.com/paper/1604.03175/) (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)
- [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)
- [Learning to Cache and Caching to Learn: Regret Analysis of Caching Algorithms](https://mlsanity.com/paper/2004.00472/) (2020)
- [Online Caching with no Regret: Optimistic Learning via Recommendations](https://mlsanity.com/paper/2204.09345/) (2022)
- [Adaptive Selective Sampling for Online Prediction with Experts](https://mlsanity.com/paper/2302.08397/) (2023)
- [Optimistic Online Caching for Batched Requests](https://mlsanity.com/paper/2310.01309/) (2023)
- [Dynamic Regret of Randomized Online Service Caching in Edge Computing](https://mlsanity.com/paper/2301.04128/) (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)

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

- [No-Regret Mixing of LRU and LFU with Optimal Switching Cost](https://mlsanity.com/paper/2609.07566/) (2026)

## Abstract (arXiv)

Online learning algorithms have been successfully used to design caching policies with sublinear regret in the total number of requests, with no statistical assumption about the request sequence. Most existing algorithms involve computationally expensive operations and require knowledge of all past requests. However, this may not be feasible in practical scenarios like caching at a cellular base station. Therefore, we study the caching problem in a more restrictive setting where only a fraction of past requests are observed, and we propose a randomized caching policy with sublinear regret based on the classic online learning algorithm Follow-the-Perturbed-Leader (FPL). Our caching policy is the first to attain the asymptotically optimal regret bound while ensuring asymptotically constant amortized time complexity in the partial observability setting of requests. The experimental evaluation compares the proposed solution against classic caching policies and validates the proposed approach under synthetic and real-world request traces.