No-Regret Caching with Noisy Request Estimates

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

Abstract

Online learning algorithms have been successfully used to design caching policies with regret guarantees. Existing algorithms assume that the cache knows the exact request sequence, but this may not be feasible in high load and/or memory-constrained scenarios, where the cache may have access only to sampled requests or to approximate requests' counters. In this paper, we propose the Noisy-Follow-the-Perturbed-Leader (NFPL) algorithm, a variant of the classic Follow-the-Perturbed-Leader (FPL) when request estimates are noisy, and we show that the proposed solution has sublinear regret under specific conditions on the requests estimator. The experimental evaluation compares the proposed solution against classic caching policies and validates the proposed approach under both synthetic and real request traces.

Introduction

In modern content delivery networks (CDNs) and edge computing environments, caching is a fundamental mechanism for reducing latency and bandwidth consumption. To optimize performance, researchers have increasingly turned to online learning, specifically the framework of "regret minimization." In this context, regret measures the difference between the cumulative cache misses incurred by an online algorithm and those of the best static cache configuration determined in hindsight. An algorithm is considered "no-regret" if its average regret vanishes over time, meaning its performance converges to the optimal static strategy.

However, a significant gap exists between theory and practice. Most no-regret algorithms, such as Online Gradient Descent or the classic Follow-the-Perturbed-Leader (FPL), assume the system can track every single request perfectly. In high-throughput environments or on memory-constrained devices, maintaining exact request counts is often impossible. Instead, systems rely on sampling or approximate data structures (like Bloom filters), which introduce noise. This paper introduces Noisy-Follow-the-Perturbed-Leader (NFPL) to bridge this gap, providing theoretical guarantees for caching under uncertainty.

The NFPL Algorithm

The proposed NFPL algorithm builds upon the standard FPL approach. In a standard FPL setting, the cache maintains a history of request counts, adds a random perturbation (noise) to these counts to prevent adversarial exploitation, and then selects the top $C$ items to populate the cache.

NFPL adapts this by replacing the true request vector $r_t$ with an estimate $\hat{r}_t$. The authors analyze two primary implementations of this estimation:

  1. NFPL-Fix: The system samples a fixed number of requests ($b$) from each batch of traffic.
  2. NFPL-Var: Each request is sampled independently with a fixed probability ($f$).

The mathematical core of the paper proves that as long as the estimator is unbiased—meaning the expected value of the estimate equals the true request count—NFPL maintains sublinear regret. This ensures that even with noisy data, the algorithm eventually learns the optimal caching strategy.

Theoretical Contributions

A major highlight of this work is the derivation of a new regret bound for FPL that is independent of the catalog size ($N$). Traditional bounds often suggest that regret scales with the number of possible items in the library, which would make these algorithms impractical for massive CDNs. This paper proves that for the caching problem, the size of the library does not degrade the theoretical performance guarantee. Specifically, for NFPL-Fix, the regret is bounded by $O(\sqrt{T})$, or more precisely $\leq 2\sqrt{2} \cdot B\sqrt{C \cdot T}$, where $B$ is the batch size and $C$ is the cache capacity.

Experimental Evaluation

The researchers validated NFPL using three distinct request traces to test different traffic characteristics:

  • Zipf Trace: A synthetic trace following a power-law distribution, representing stationary web traffic.
  • Akamai Trace: A real-world dataset from the Akamai CDN, featuring temporal correlations and shifting popularities.
  • Round-robin Trace: An adversarial scenario where requests cycle through files ($1, 2, 3... N$). This is a known failure case for traditional heuristics like Least Recently Used (LRU).

Key Findings

  • Convergence: In both Zipf and Akamai traces, NFPL successfully converged toward the optimal static allocation (OPT). While the convergence was naturally slower than FPL with perfect knowledge, it remained robust and eventually outperformed standard heuristics.
  • Adversarial Resilience: In the round-robin test, where LRU and Least Frequently Used (LFU) suffered near 100% miss rates, NFPL maintained a miss ratio close to the theoretical optimum. Interestingly, the sampling noise in NFPL occasionally acted as an additional layer of randomization that helped the algorithm avoid being "tricked" by the repeating sequence.
  • Sampling Robustness: The experiments indicated that the specific sampling method (fixed vs. variable) had a negligible impact on performance. The primary factor was the sampling rate; while lower rates increased the time required to learn, the no-regret property held firm.

Conclusion and Future Work

NFPL demonstrates that perfect information is not a prerequisite for effective, no-regret caching. By accounting for noise in the request estimation process, the algorithm provides a mathematically sound and practically viable solution for high-load systems.

Future research directions include extending the NFPL analysis to more complex approximate counting structures, such as Count-Min Sketches, and developing adaptive versions of the algorithm. An adaptive NFPL could dynamically tune its learning rate ($\eta$) in response to fluctuating traffic volumes and noise levels, further enhancing its utility in volatile network environments.

Summary updated

Abstract

Online learning algorithms have been successfully used to design caching policies with regret guarantees. Existing algorithms assume that the cache knows the exact request sequence, but this may not be feasible in high load and/or memory-constrained scenarios, where the cache may have access only to sampled requests or to approximate requests' counters. In this paper, we propose the Noisy-Follow-the-Perturbed-Leader (NFPL) algorithm, a variant of the classic Follow-the-Perturbed-Leader (FPL) when request estimates are noisy, and we show that the proposed solution has sublinear regret under specific conditions on the requests estimator. The experimental evaluation compares the proposed solution against classic caching policies and validates the proposed approach under both synthetic and real request traces.
BibTeX
@inproceedings{mazziane2023no,
  author = {Younes Ben Mazziane and Francescomaria Faticanti and Giovanni Neglia and Sara Alouf},
  title = {{No-Regret Caching with Noisy Request Estimates}},
  booktitle = {VCC},
  year = {2023},
  url = {https://openreview.net/forum?id=uaDNM3jrgD},
}
Figure