论文标题
随时对两位专家感到最佳遗憾
Optimal anytime regret with two experts
论文作者
论文摘要
我们考虑了通过专家建议的经典预测问题。在固定的时间设置中，在预先知道时间范围的情况下，当有两个，三个或四个专家或专家数量较大时，可以知道实现最佳遗憾的算法。在任何时间设置的问题中，时间范围未提前知道的问题，知之甚少。无论专家数量如何，在任何时间设置中都没有最小值最佳算法。即使对于两名专家的情况，Luo和Schapire也打开了确定最佳算法的问题。 我们设计了第一个最小值最佳算法，以最大程度地减少任何时间设置的遗憾。我们考虑了两位专家的案例，并证明最佳遗憾是$γ\ sqrt {t} / 2 $在所有时间步骤$ t $，其中$γ$是35年前在研究布朗尼运动基本属性时出现的自然常数。该算法是通过考虑遗憾问题的连续类似物而设计的，后者是使用随机演算中的思想来解决的。
We consider the classical problem of prediction with expert advice. In the fixed-time setting, where the time horizon is known in advance, algorithms that achieve the optimal regret are known when there are two, three, or four experts or when the number of experts is large. Much less is known about the problem in the anytime setting, where the time horizon is not known in advance. No minimax optimal algorithm was previously known in the anytime setting, regardless of the number of experts. Even for the case of two experts, Luo and Schapire have left open the problem of determining the optimal algorithm. We design the first minimax optimal algorithm for minimizing regret in the anytime setting. We consider the case of two experts, and prove that the optimal regret is $γ\sqrt{t} / 2$ at all time steps $t$, where $γ$ is a natural constant that arose 35 years ago in studying fundamental properties of Brownian motion. The algorithm is designed by considering a continuous analogue of the regret problem, which is solved using ideas from stochastic calculus.
