Learn Quickly, Adapt Slowly - Convergent Learning Algorithms for Normal Form Games

Hirsch [2], is called smooth fictitious play. Using techniques from stochastic approximation by the ODE method [1, 12] it has been shown that the asymptotic behaviour of this random process is characterised by the asymptotic behaviour of a deterministic dynamical system --- the smooth best response dynamics. The results of Hofbauer and Hopkins [10] show that this algorithm must therefore converge to Nash distribution in two-player zero-sum games, and in two-player partnership games (indeed extending this to N-player partnership games is trivial). However the application of these ideas to economic and biological interpretations is hampered by the fact that all players need to be aware of the actions of all other players, and to explicitly calculate their expected rewards given beliefs about the play of others. We propose a model under which players learn the values of their actions directly, ignoring the presence of the other players and the rules of the game. Indeed, our algorithm r