Towards Optimal Robustness in Learning-Augmented Paging

Peng Chen, Hailiang Zhao, Xueyan Tang, Yixuan Wang, Shuiguang DengICML 2026 · OpenReview

Abstract

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 learning-augmented paging: $H_k + O(1)$. Experiments further demonstrate strong practical performance.
BibTeX
@inproceedings{chen2026towards,
  author = {Peng Chen and Hailiang Zhao and Xueyan Tang and Yixuan Wang and Shuiguang Deng},
  title = {{Towards Optimal Robustness in Learning-Augmented Paging}},
  booktitle = {International Conference on Machine Learning},
  year = {2026},
  url = {https://openreview.net/forum?id=ESa07RwpVr},
}

Loading related content...

Figure