Abstract:
This talk will describe a simple, general algorithm for learning to play any matrix game against an unknown adversary. The 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, some of which will be discussed, for instance, to the problem of learning to imitate the behavior of an "expert" while attempting simultaneously to improve on the expert's performance.