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.
Introduction
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 traffic patterns. This paper bridges the gap between theoretical optimality and practical computational efficiency.
The NFPL Framework
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 exploiting the cache's state.
The paper introduces three variants of the NFPL (Noisy Follow-the-Perturbed-Leader) algorithm:
- S-NFPL (Static): Uses a fixed noise vector generated at the start.
- D-NFPL (Dynamic): Regenerates noise at every update (computationally expensive).
- L-NFPL (Lazy): The most innovative variant. It uses a "lazy" coupling of noise vectors to ensure the cache state only needs to be updated infrequently, achieving $O(1)$ amortized time complexity.
As shown in the comparison above, NFPL is the only algorithm that provides an optimal regret bound while maintaining constant time complexity in the partial observation regime ($p \in (0, 1]$).
Experimental Evaluation
The researchers evaluated their algorithms using three distinct types of request traces: synthetic Zipf traces (stationary), Zipf-RR (adversarial/non-stationary), and a real-world Akamai CDN trace containing 20 million requests.
Key Results
- Optimal Regret: NFPL achieves $O(\sqrt{T})$ regret, 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 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.
Conclusion
NFPL represents a significant step forward in practical no-regret caching. By combining the exploration power of noise with a lazy update mechanism, it achieves theoretical optimality without the computational overhead that has previously hindered such algorithms. Future work includes extending these $O(1)$ guarantees to multi-cache hierarchies and bipartite caching networks.
Summary updated