Universal learning of repeated matrix games

Abstract

We study and compare the learning dynamics of two universal learning algorithms, one based on Bayesian learning and the other on prediction with expert advice. Both approaches have strong asymptotic performance guarantees. When confronted with the task of finding good long-term strategies in repeated 2 x 2 matrix games, they behave quite differently. We consider the case where the learning algorithms are not even informed about the game they are playing.