{"ID":2921804,"CreatedAt":"2026-06-02T02:42:49.606572591Z","UpdatedAt":"2026-06-03T05:56:00.181519634Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2606.01342","arxiv_id":"2606.01342","title":"Towards Optimal Robustness in Learning-Augmented Paging","abstract":"Learning-augmented paging has been extensively studied in recent years. A key advantage over naive ML-based approaches is \\emph{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 \\emph{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.","short_abstract":"Learning-augmented paging has been extensively studied in recent years. A key advantage over naive ML-based approaches is \\emph{bounded robustness}, which guarantees worst-case performance even when predictions are inaccurate, making these algorithms valuable for real-world systems. Prior work achieves robustness bound...","url_abs":"https://arxiv.org/abs/2606.01342","url_pdf":"https://arxiv.org/pdf/2606.01342v1","authors":"[\"Peng Chen\",\"Hailiang Zhao\",\"Xueyan Tang\",\"Yixuan Wang\",\"Shuiguang Deng\"]","published":"2026-05-31T16:49:36Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"cs.LG\"]","methods":"[]","has_code":false}