Efficient and Optimal No-Regret Caching Under Partial Observation

Younes Ben Mazziane, Francescomaria Faticanti, Sara Alouf, Giovanni Neglia

TL;DR

This paper introduces NFPL (Noisy Follow-the-Perturbed-Leader), a family of caching algorithms designed for scenarios where only a fraction of requests are observed. It is the first approach to achieve both asymptotically optimal "no-regret" performance and constant $O(1)$ amortized time complexity, making it highly practical for high-speed networking hardware.

What Problem Does This Paper Address?

In modern content delivery networks (CDNs) and edge computing, caching is vital for reducing latency. Most "no-regret" caching algorithms—which are mathematically guaranteed to perform as well as the best static strategy in hindsight—assume the system can see every single request.

However, in the real world, visibility is often limited. For example, a central controller might only see "cache misses" from local nodes, or a router might only sample a small percentage of traffic to save on overhead. This is known as partial observation. Existing robust algorithms for this setting are either computationally expensive (scaling with the total number of files) or fail to provide strong performance guarantees under adversarial (non-stationary) traffic patterns. The authors aim to bridge the gap between theoretical optimality and practical computational efficiency.

Methods

The authors propose a new framework called Bernoulli Partial Observability (BPO), where each request is observed with a probability $p$. They build upon the classic Follow-the-Perturbed-Leader (FPL) algorithm, which makes decisions by adding random noise to request counts to prevent an "adversary" from predicting and exploiting the cache's state.

The paper introduces three variants of the NFPL algorithm:

  1. S-NFPL (Static): Uses a fixed noise vector generated at the start.
  2. D-NFPL (Dynamic): Regenerates noise at every update (computationally expensive).
  3. L-NFPL (Lazy): The most innovative variant. It uses a clever "lazy" coupling of noise vectors. By correlating noise over time, it ensures that the cache state only needs to be updated infrequently.

To further reduce overhead, the algorithms use batching (updating only after $B$ requests) and sampling (ignoring some observed requests with probability $q$).

Datasets

The researchers evaluated their algorithms using three distinct types of request traces:

  • Synthetic Zipf Trace: A standard model where file popularity follows a stationary power-law distribution.
  • Zipf-RR (Round Robin): A synthetic adversarial trace where the most popular files shift in a cycle, specifically designed to "trick" standard heuristics like Least-Frequently-Used (LFU).
  • Akamai Trace: A large-scale, real-world dataset containing 20 million requests from an Akamai CDN, representing actual internet traffic patterns.

Key Insights and Ideas

  • The Power of Noise: Adding uniform noise to request counts isn't just a mathematical trick; it acts as a form of "exploration." This prevents the cache from becoming too "greedy" and allows it to adapt to sudden shifts in file popularity that simple heuristics like LRU or LFU might miss.
  • Constant Time Complexity: The "aha moment" for L-NFPL is the realization that as the number of requests ($T$) grows, the probability that a new request will actually change the "top $C$" files in the cache decreases. By using a heap data structure and lazy noise, the amortized cost of an update becomes $O(1)$—effectively constant time.
  • Independence from Catalog Size: Unlike many previous algorithms whose performance degrades as the number of available files ($N$) increases, NFPL’s regret bound is independent of $N$. This makes it uniquely suited for massive modern catalogs.

Key Results

  • Optimal Regret: The authors proved that NFPL achieves $O(\sqrt{T})$ regret, which is the theoretical gold standard for online learning.
  • Superior Robustness: On the adversarial Zipf-RR trace, NFPL variants outperformed standard LRU and LFU by approximately 16% in terms of miss ratio. While LRU/LFU got "stuck" on old patterns, NFPL successfully converged toward the optimal strategy.
  • Efficiency: L-NFPL demonstrated the lowest execution time among the robust variants, confirming that its $O(1)$ amortized complexity holds up in practice.
  • Resilience to Low Visibility: Even when the observation probability $p$ was as low as 0.01 (seeing only 1% of traffic), the algorithm still managed to converge toward the optimal static allocation, albeit more slowly.

Limitations and Future Work

The current study focuses on a single cache scenario. In many real-world deployments, caches are organized in complex hierarchies or networks (bipartite caching). The authors acknowledge that extending these $O(1)$ no-regret guarantees to multi-cache networks with partial visibility is a significant and necessary next step. Additionally, while the algorithm is robust, its performance depends on tuning parameters like the noise scale ($\eta$) and batch size ($B$), which may require different settings for different types of network traffic.

Summary updated

Abstract

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.
BibTeX
@article{mazziane2026efficient,
  author = {Younes Ben Mazziane and Francescomaria Faticanti and Sara Alouf and Giovanni Neglia},
  title = {{Efficient and Optimal No-Regret Caching Under Partial Observation}},
  journal = {IEEE Trans. Netw.},
  year = {2026},
  doi = {10.1109/ton.2025.3636929},
}

Loading related content...

Figure