Distinguished Lecture Series


"Theory and applications of an algorithm for playing repeated games"

Robert Schapire, Princeton University

Thursday, April 22, 2010 at 4:00 P.M.

Room 368 (CIT 3rd Floor)

This talk will describe a simple, general algorithm for learning to play any matrix game against an unknown adversary. The algorithm, which is based directly on Littlestone and Warmuth's weighted majority algorithm, can be shown never to perform much worse than the best fixed strategy, even if selected in hindsight. Moreover, because of the algorithm's moderate resource requirements, it can be used even when working with extremely large game matrices. Taken together, these properties make the algorithm a good fit for a range of machine-learning applications, including on-line learning and boosting. Recently, the algorithm has also been applied to reinforcement learning, specifically, to the problem of learning to imitate the behavior of an "expert" while attempting simultaneously to improve on the expert's performance.

Host: Philip Klein