Towards Optimal Robustness in Learning-Augmented Paging

Learning-augmented paging has been extensively studied in recent years. A key advantage over naive ML-based approaches is bounded robustness, which guarantees worst-case performance even when predictions are inaccurate, making these algorithms valuable for real-world systems. Prior work achieves robustness bounds of 2H k + O(1) in the randomized setting, leaving a gap to the optimal competitive ratio H k . In this paper, we study how to close this gap. We begin by reviewing online optimality and proving a new property of the latest H k -competitive algorithm, which facilitates our analysis in the learning-augmented setting. Then, we review existing learning-augmented paging algorithms and introduce a unifying primitive, the relative prediction budget, which captures the essence of establishing robustness and reveals that prior algorithms either overuse or underutilize predictions. Guided by the above analysis, we develop a new framework that achieves the best-possible robustness up to an additive constant for learningaugmented paging: H k + O(1). Experiments further demonstrate strong practical performance. 3. Building on the above, we propose a new learningaugmented algorithmic framework, RPB-ONOPT. Using this framework, RPB-OM achieves 1-consistency and optimal robustness up to an additive constant, i.e., H k + O(1). The experiments demonstrate the benefits of our improved robustness guarantees and the stronger designs guided by the relative prediction budget.