Towards Optimal Algorithms For Prediction With Expert Advice

  • Balu Sivan | Microsoft Research

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

Speaker Bios

Balu Sivan is a postdoc in the Theory Group at Microsoft Research Redmond. He received his PhD in Computer Science from the University of Wisconsin-Madison advised by Prof. Shuchi Chawla. His primary research interests are in Algorithmic Game Theory and online/approximation algorithms. More details here: http://research.microsoft.com/en-us/um/people/bsivan/

Taille: Microsoft Research Talks