Abstract
The design of effective online caching policies is an increasingly important problem for content distribution networks, online social networks and edge computing services, among other areas. This paper proposes a new algorithmic toolbox for tackling this problem through the lens of optimistic online learning. We build upon the Follow-the-Regularized-Leader (FTRL) framework which is developed further here to include predictions for the file requests, and we design online caching algorithms for bipartite networks with fixed-size caches or elastic leased caches subject to time-average budget constraints. The predictions are provided by a content recommendation system that influences the users viewing activity, and hence can naturally reduce the caching network's uncertainty about future requests. We prove that the proposed optimistic learning caching policies can achieve sub-zero performance loss (regret) for perfect predictions, and maintain the best achievable regret bound $O(\sqrt T)$ even for arbitrary-bad predictions. The performance of the proposed algorithms is evaluated with detailed trace-driven numerical tests.
Introduction
Caching remains a fundamental challenge in modern network infrastructure, from Content Delivery Networks (CDNs) to edge computing. Traditional policies like Least Recently Used (LRU) are often reactive, struggling to adapt to the non-stationary request patterns of modern users. While recent advances in Online Convex Optimization (OCO) have introduced "no-regret" policies that adapt to any request pattern, these remain purely reactive, looking only at historical data.
This research identifies a unique opportunity: modern recommendation systems (RecSys) actively influence future user behavior. By treating these recommendations as "optimistic" predictions, we can transform caching from a reactive process into a proactive one. The core challenge lies in the inherent noise of such predictions; a robust policy must benefit from good advice without being derailed by "garbage" predictions.
System Model and Methodology
We consider a bipartite network where users at various locations can access multiple edge caches. The system integrates a recommendation engine that provides hints about future requests, as illustrated in the system model below.
To address this, we introduce three primary algorithmic frameworks based on Follow-the-Regularized-Leader (FTRL):
- Optimistic Bipartite Caching (OBC): This algorithm incorporates a prediction term into the FTRL update. Theoretically, it achieves "negative regret" (outperforming the best static strategy) with perfect predictions while maintaining a robust $O(\sqrt{T})$ bound if predictions are poor.
- Optimistic Elastic Caching (OEC): Designed for cloud-based "leased" caches, this method uses saddle-point analysis to balance the utility of cache hits against the long-term costs of varying cache sizes.
- Experts Caching (XC): A meta-learning approach that runs an Optimistic expert (trusting RecSys) and a Pessimistic expert (robust/reactive) in parallel. A meta-learner dynamically adjusts the weight given to each expert based on their real-time performance.
Experimental Evaluation
The proposed algorithms were evaluated using both synthetic Zipf-distributed requests and real-world YouTube request traces. We simulated various recommendation qualities, including adversarial scenarios where the system provides intentionally incorrect predictions.
Key Results
- Utility Gains: In bipartite simulations, the OBC policy achieved utility within 5.32% of the Best Hindsight Solution (BHS).
- Regret Reduction: Compared to standard Online Gradient Descent (OGD), optimistic methods demonstrated up to a 57.1% improvement in regret.
- Elastic Efficiency: The OEC algorithm outperformed benchmarks by 42.5% by intelligently violating budget constraints temporarily to store high-value content predicted for future requests.
- Robustness via Meta-Learning: The XC framework successfully identified poor recommendation quality, shifting weight to the pessimistic expert to maintain system stability.
Conclusion
By bridging recommendation systems and online learning, this work demonstrates that "optimistic" caching can significantly outperform traditional reactive policies. The framework ensures that even in the presence of unreliable predictions, the system maintains theoretical performance guarantees. Future work will explore extending these principles to variable file sizes and uncoded caching environments.
Summary updated