在只允许每次查询一个启发式策略的情况下，实现接近最优策略的性能。
Learning-Augmented Algorithms for MTS with Bandit Access to Multiple Predictors
- 设计算法在仅能单步查询多个启发式策略时，动态选择最优策略。
- 达到与最优策略相比的遗憾上界为 $O( ext{OPT}^{2/3})$。
- 适用于在线任务系统中存在多种输入类型且需自适应选择策略的场景。
我们研究如下问题：给定 $\ell$ 个针对度量任务系统（MTS）的启发式策略，每个可能针对不同类型的输入实例。在处理在线接收的输入实例时，每个时间步只能查询其中一个启发式策略的动作。目标是实现性能接近所给启发式策略中的最优者。该设置的主要难点在于：某个启发式策略在时间 $t$ 的代价无法估计，除非该策略也在时间 $t-1$ 被查询过。这与带记忆限制对手的赌博学习（Bandit Learning against memory bounded adversaries）相关。我们展示了如何实现 $O(\text{OPT}^{2/3})$ 的遗憾，并基于 Dekel 等人（2013）的构造证明了该上界的紧性。
原文摘要 · Abstract (English)
We consider the following problem: We are given $\ell$ heuristics for Metrical Task Systems (MTS), where each might be tailored to a different type of input instances. While processing an input instance received online, we are allowed to query the action of only one of the heuristics at each time step. Our goal is to achieve performance comparable to the best of the given heuristics. The main difficulty of our setting comes from the fact that the cost paid by a heuristic at time $t$ cannot be estimated unless the same heuristic was also queried at time $t-1$. This is related to Bandit Learning against memory bounded adversaries (Arora et al., 2012). We show how to achieve regret of $O(\text{OPT}^{2/3})$ and prove a tight lower bound based on the construction of Dekel et al. (2013).
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。