Optimistic Learning with Applications to Caching Networks

AI/ML-based approaches are at the forefront of resource management in modern communication networks. Deep learning, in particular, enables fast and high-performing decision-making when sufficient representative training data is available to build accurate offline models. Conversely, online learning solutions operate without prior training and make decisions based on real-time observations; however, they tend to be overly conservative to ensure robustness (i.e., worst-case guarantees).

This thesis advocates optimistic learning as a decision-making framework for resource management in networked systems. An optimistic learning algorithm integrates untrusted predictions and assesses their accuracy at runtime. When predictions are accurate, these algorithms achieve performance levels comparable to offline-trained models. Crucially, they maintain the robustness of regular online learning, ensuring reliability even when predictions are inaccurate.

We focus on caching networks and propose new optimistic learning algorithms for coded caching, and whole-file caching. These algorithms provably converge to the best fixed caching allocation at an order-optimal rate, independent of prediction accuracy. However, when predictions are accurate, convergence is highly accelerated, achieving the “optimistic" premise.

We then extend our focus to scenarios where the optimization target itself changes over time. In caching, this translates to competing against dynamic caching configurations rather than a single best fixed allocation. We demonstrate that optimism is even more valuable in this setting; accurate predictions help the learner efficiently track moving targets, adapting in real-time without excessive conservatism. Furthermore, we explore the role of predictions in stateful systems, where past decisions influence future costs. In such environments, optimistic learning benefits from horizon-based predictions, leveraging forecasts over extended time windows rather than immediate next-cost predictions.

All proposed algorithms are rigorously analyzed and come with provable performance guarantees under carefully designed and explicitly stated metrics. By integrating optimistic learning into network optimization, this thesis explores the spectrum between prediction-driven and robust approaches, offering a principled framework for leveraging untrusted ML predictions in network resource allocation.