AdaSwitch：一种用于有界影响问题的自适应切换元算法

arXiv:2509.02302v2 公告类型：替换 摘要：我们研究一类历史相关的在线问题，其中对未来请求序列的预测可能并不准确。受多个现实世界应用的启发，我们引入了一个“有界影响”框架，在该框架中，过去的决策和请求对未来最优值的影响仅限于一个有界范围内。在此框架下，我们开发了 AdaSwitch，这是一种能够在适当的离线预言机和在线预言机之间自适应切换的元算法。AdaSwitch 对期望性能提供了明确的保证，并且随着预测误差减小或离线最优值增大，这些保证会变得更加严格。当预测完全准确时，随着离线最优值增大，其保证将趋近于离线预言机的保证。在任意预测下，它还保留了接近在线预言机的最坏情况保证。在线提前期报价、$k$-server 与缓存，以及在线可复用资源分配等应用表明，该框架既适用于奖励最大化，也适用于成本最小化。