Theory and applications of a repeated game playing algorithm
Robert Schapire
Abstract:
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 matrices. Taken together, these properties make the
algorithm a good fit for a range of 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.