On No-Regret Learning, Fictitious Play, and Nash Equilibrium

Amir Jafari, Amy Greenwald, David Gondek, and Gunes Ercal

Abstract

This paper addresses the following question: what is the outcome of multi-agent learning via no-regret algorithms in repeated games? Specifically, can the outcome of no-regret learning be characterized by traditional game-theoretic solution concepts, such as Nash equilibrium? The conclusion of this study is that no-regret learning is reminiscent of fictitious play: play converges to Nash equilibrium in dominance-solvable, constant-sum, and general-sum 2 x 2 games, but cycles exponentially in the Shapley game. Notably, however, the information required of fictitious play far exceeds that of no-regret learning.