Towards optimal algorithms for prediction with expert advice

Date

August 13, 2014

Overview

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

Speakers

Balu Sivan

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/

‚Äč