Towards Optimal Algorithms for Prediction with Expert Advice
Abstract
We study the classical problem of prediction with expert advice in the
adversarial setting with a geometric stopping time. In
1965, Cover'65 gave the optimal algorithm for the case of 2
experts. In this paper, we design the optimal algorithm, adversary and regret
for the case of 3 experts. Further, we show that the optimal algorithm for 2
and 3 experts is a probability matching algorithm (analogous to Thompson
sampling) against a particular randomized adversary. Remarkably, our proof
shows that the probability matching algorithm is not only optimal against this
particular randomized adversary, but also minimax optimal.
Our analysis develops upper and lower bounds simultaneously, analogous to the
primal-dual method. Our analysis of the optimal adversary goes through delicate
asymptotics of the random walk of a particle between multiple walls. We use the
connection we develop to random walks to derive an improved algorithm and
regret bound for the case of 4 experts, and, provide a general framework for
designing the optimal algorithm and adversary for an arbitrary number of
experts.