arXiv：cs.LG· Xi Chen, Yuze Chen, Shibo Dai, Yuan Zhou·· 3 小时前
AdaSwitch：面向学习增强型有界影响问题的自适应切换元算法
AdaSwitch: An Adaptive Switching Meta-Algorithm for Learning-Augmented Bounded-Influence Problems
AI 导读
研究者提出 AdaSwitch 元算法，用于带未来请求序列预测的历史依赖型在线问题，可在离线与在线 oracle 之间自适应切换，其期望性能保证随预测误差减小或离线最优值增大而收紧。在完美预测下，其保证随离线最优值增长逼近离线 oracle；在任意预测下，仍保持接近在线 oracle 的最坏情况保证。该框架已应用于在线交货期报价、k-server 与缓存、在线可复用资源分配等场景。
正文
Abstract:We study history-dependent online problems with a possibly inaccurate prediction of the future request sequence. Motivated by several real-world applications, we introduce a \emph{bounded-influence} framework in which past decisions and requests affect the future optimal value by only a bounded amount. Within this framework, we develop AdaSwitch, a meta-algorithm that adaptively switches between suitable offline and online oracles. AdaSwitch provides explicit guarantees on expected performance that tighten as prediction error decreases or the offline optimum increases. With perfect predictions, its guarantee approaches the offline oracle's guarantee as the offline optimum grows. It also retains a worst-case guarantee close to that of the online oracle under arbitrary predictions. Applications to online lead-time quotation, $k$-server and caching, and online reusable resource allocation demonstrate the framework's applicability to both reward maximization and cost minimization.
| Comments: | 77 pages, 7 figures |
| Subjects: | Machine Learning (cs.LG); Optimization and Control (math.OC) |
| Cite as: | arXiv:2509.02302 [cs.LG] |
| (or arXiv:2509.02302v2 [cs.LG] for this version) | |
| https://doi.org/10.48550/arXiv.2509.02302 arXiv-issued DOI via DataCite |
Submission history
From: Yuze Chen [view email]
[v1]
Tue, 2 Sep 2025 13:26:23 UTC (585 KB)
[v2]
Thu, 8 Oct 2026 14:44:13 UTC (1,051 KB)
来源：arXiv：cs.LG · arxiv.org