Theory and applications of a repeated game playing algorithm


                   Robert Schapire

                 Princeton University




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.