The adaptive k-armed bandit

Dr. Hayes is an NSF Postdoctoral Research Fellow at the University of California, Berkeley
Suppose we want to predict the winners of a sequence of horse races, without any advance knowledge of the horses. How well can we do? The best we could reasonably hope for, is to "learn as we go," and to nearly match the overall performance of the best horse (in hindsight). But, what if we aren't told which horses win–only whether our predictions are right or wrong? And what if the mob is watching our every move and "fixing" each race based on our previous choices?

I will present a new algorithm for this most pessimistic setting, showing that these obstacles can all be overcome. I will also discuss several application domains in which these assumptions are realistic rather than paranoid, and touch on some related problems.