自适应切换算法提升预测不可靠时的在线决策鲁棒性
AdaSwitch: An Adaptive Switching Meta-Algorithm for Learning-Augmented Bounded-Influence Problems
- 设计自适应切换机制，根据预测质量动态调整策略
- 预测准确时逼近离线最优，误差大时仍保持经典竞争比
- 适用于资源分配、服务器调度等多类在线问题
我们研究一类具有序列预测的多周期在线决策问题，预测可能来自机器学习模型但准确性无法保证。每期决策者需在未知未来请求的情况下，根据实际请求做出不可撤销的操作，获得收益或产生成本。本文提出有界影响框架，其中过去决策和请求对未来的最优收益影响有限。在此框架下，提出AdaSwitch元算法，在预测准确时性能接近离线基准，预测不准确时仍保持经典竞争比。该方法适用于处理系统中的提前期报价、k-服务器问题以及可重用资源的在线分配等场景，展现了学习增强型在线决策的灵活性与广泛适用性。
原文摘要 · Abstract (English)
We study a class of multi-period online decision-making problems with sequence-based predictions, which may be generated by machine learning models but whose accuracy is not guaranteed. In each period, the decision-maker observes the realized request and must take an irrevocable action that yields a reward or incurs a cost, without knowledge of future arrivals. We introduce a bounded-influence framework, in which past decisions and requests exert only limited impact on the future optimal reward. Within this framework, we propose the AdaSwitch meta-algorithm, which exploits predictions to attain performance close to the offline benchmark when predictions are accurate, while preserving classical competitive-ratio guarantees under highly inaccurate predictions. Our framework and meta-algorithm apply to diverse settings, including lead-time quotation in processing systems, the $k$-server problem, and online allocation of reusable resources. These applications illustrate the flexibility and broad applicability of our approach to learning-augmented online decision-making.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。