Towards optimal algorithms for prediction with expert advice

Опубликовано 21 июня 2016, 19:21

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. 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 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. 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 and obtain a constant gap separation in regret from all previously known results. (Joint work with Nick Gravin and Yuval Peres.)