论文标题
通过专家建议进行预测的最佳跟踪
Optimal Tracking in Prediction with Expert Advice
论文作者
论文摘要
我们使用专家建议设置研究预测，目的是结合一组专家（例如独立运行算法）产生的决策来做出决定。我们通过专家建议设置的预测实现了最低的最佳动态遗憾，即，我们可以以最佳的方式与专家决策的时变（不一定是固定）组合竞争。我们的最终算法是真正的在线，没有先前的信息，例如时间范围或损失范围，文献中不同算法通常使用它们。我们的遗憾保证和最小的最低界限都普遍考虑，即专家损失可以具有时间变化的属性，并且可能是无限的。我们的算法可以适应有关损失反馈和决策的限制性方案。我们的保证是普遍的，即，我们的最终算法可以以最小的最佳方式以对数复杂性提供对任何竞争者序列的后悔保证。请注意，据我们所知，对于有专家建议问题的预测，我们的算法是第一个在没有先验知识的情况下生产出如此最佳，自适应和真正的在线保证的算法。
We study the prediction with expert advice setting, where the aim is to produce a decision by combining the decisions generated by a set of experts, e.g., independently running algorithms. We achieve the min-max optimal dynamic regret under the prediction with expert advice setting, i.e., we can compete against time-varying (not necessarily fixed) combinations of expert decisions in an optimal manner. Our end-algorithm is truly online with no prior information, such as the time horizon or loss ranges, which are commonly used by different algorithms in the literature. Both our regret guarantees and the min-max lower bounds are derived with the general consideration that the expert losses can have time-varying properties and are possibly unbounded. Our algorithm can be adapted for restrictive scenarios regarding both loss feedback and decision making. Our guarantees are universal, i.e., our end-algorithm can provide regret guarantee against any competitor sequence in a min-max optimal manner with logarithmic complexity. Note that, to our knowledge, for the prediction with expert advice problem, our algorithms are the first to produce such universally optimal, adaptive and truly online guarantees with no prior knowledge.
