提出新框架，让预测增强的页面置换算法逼近最优鲁棒性。
Towards Optimal Robustness in Learning-Augmented Paging
- 引入相对预测预算统一分析机制
- 实现 $H_k + O(1)$ 的最优鲁棒性界
- 适合对系统可靠性要求高的实时场景
近年来，预测增强的页面置换问题受到广泛关注。相较于直接使用机器学习方法，其关键优势在于具有有界鲁棒性——即使预测不准确也能保证最坏情况下的性能，因此在真实系统中极具价值。此前工作在随机设置下仅能达到 $2H_k + O(1)$ 的鲁棒性界，与最优竞争比 $H_k$ 存在差距。本文首先回顾在线最优性并证明最新 $H_k$-竞争算法的新性质，为预测增强设置分析提供支持；接着梳理现有算法，提出统一的‘相对预测预算’概念，揭示以往方法或过度使用或低估预测。基于此分析，我们设计新框架，首次实现学习增强页置换的最优鲁棒性：$H_k + O(1)$。实验进一步验证其优异的实际表现。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。