Towards optimal algorithms for prediction with expert advice

Speaker  Balu Sivan

Affiliation  MSR

Host  Yuval Peres

Duration  00:54:17

Date recorded  7 August 2014

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.)

©2014 Microsoft Corporation. All rights reserved.
> Towards optimal algorithms for prediction with expert advice