2015
Jun
07

# Game Theory & Math Economics: Yuval Peres (Microsoft Research) - "Towards Optimal Algorithms for Prediction with Expert Advice"

4:00pm to 5:00pm

## Location:

Elath Hall, 2nd floor, Feldman Building, Edmond J. Safra Campus

We study the classical problem of prediction with expert advice in the adversarial setting with a geometric stopping time. Cover (1965) gave the optimal algorithm that minimizes worst-case regret for the case of 2 experts. In this talk, I will describe the optimal algorithm, adversary and regret for the case of 3 experts. We will see that optimal algorithm for 2 and 3 experts is a probability matching algorithm (analogous to Thompson sampling) against a particular randomized adversary.