We study the classic problem of prediction with expert advice in the adversarial setting. Focusing on settings with a constant number of experts, we develop optimal algorithms and obtain precisely optimal regret values for the case of 2 and 3 experts. Further, we develop regret lower bounds for the multiplicative weights algorithm that exactly match the known upper bounds for an arbitrary number of experts k. This establishes a constant factor separation between the regrets achieved by the optimal algorithm and the multiplicative weights algorithm for a constant number of experts. All prior work on this problem has been restricted to optimal algorithms for special cases of adversary, or, algorithms that are optimal only in the doubly asymptotic sense: when both the number of experts and the time horizon go to infinity. In contrast to these results, our algorithms are exactly optimal for the most general adversary. Our main tool is the minimax principle which lets us analyze the optimal adversary to compute optimal regret values. While analyzing the optimal adversary, we establish deep connections with non-trivial aspects of random walk. We further use this connection to develop an improved regret bound for the case of 4 experts.

本文研究了在对手设置下采用几何停止时间进行专家建议的预测经典问题。对于2个专家的情况，Cover提出了最优算法。对于三个专家的情况，我们设计了最优算法和对手，并证明了该算法与一个特定的随机对手的概率匹配算法（类似于汤普森抽样）是最优的，该证明显示概率匹配算法不仅针对这个特定的随机对手是最优的，而且是极小化的。同时我们通过主对偶（primal-dual)方法同时发展了上限和下限，并为任意数量的专家设计了最优算法和对手的通用框架。

朝着专家建议预测的最优算法