论文标题
有效，最佳的固定时间后悔与两位专家
Efficient and Optimal Fixed-Time Regret with Two Experts
论文作者
论文摘要
通过专家建议的预测是在线学习中的基本问题。在具有$ t $ rounds和$ n $ Experts的实例中，经典的乘法权重更新方法最多损坏$ \ sqrt {（t/2）\ ln n} $遗憾。此外，当$ t $和$ n $生长到无限时，这在渐近上是最佳的。但是，当专家的数量$ n $很小/固定时，存在具有更好遗憾保证的算法。 Cover在1967年显示了两种专家问题的动态编程算法，仅限于$ \ {0,1 \} $成本，最多损失$ \ sqrt {t/2π} + o（1）$（t^2）$预处理时间。在这项工作中，我们提出了一种预测的最佳算法，并与两位专家的建议提出了最佳的预测，这些建议甚至适用于$ [0,1] $的成本，并且每回合的$ O（1）$处理时间。我们的算法基于随机演算的技术和工具的最新工作，建立了有关专家问题的最新工作。
Prediction with expert advice is a foundational problem in online learning. In instances with $T$ rounds and $n$ experts, the classical Multiplicative Weights Update method suffers at most $\sqrt{(T/2)\ln n}$ regret when $T$ is known beforehand. Moreover, this is asymptotically optimal when both $T$ and $n$ grow to infinity. However, when the number of experts $n$ is small/fixed, algorithms with better regret guarantees exist. Cover showed in 1967 a dynamic programming algorithm for the two-experts problem restricted to $\{0,1\}$ costs that suffers at most $\sqrt{T/2π} + O(1)$ regret with $O(T^2)$ pre-processing time. In this work, we propose an optimal algorithm for prediction with two experts' advice that works even for costs in $[0,1]$ and with $O(1)$ processing time per turn. Our algorithm builds up on recent work on the experts problem based on techniques and tools from stochastic calculus.
