Towards Optimal Algorithms for Prediction with Expert Advice
  We study the classical problem of prediction with expert advice in the
adversarial setting with a geometric stopping time. In 1965, Cover 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.
