Multi-Agent Learning under Uncertainty: Recurrence vs. Concentration
Kyriakos Lotidis, Panayotis Mertikopoulos, Nicholas Bambos, Jose Blanchet
In this paper, we examine the convergence landscape of multi-agent learning in continuous games under uncertainty.In more detail, we consider two stochastic models of regularized learning—in continuous and discrete time respectively—and we set out to characterize the long-run behavior of the induced sequence of play.In stark contrast to deterministic, full-information models of learning (or models with a vanishing learning rate), we show that, in general, the resulting dynamics do not converge.In lieu of this, we ask instead which actions are played more often in the long run, and by how much.To that end, we show that, despite wandering away from equilibrium infinitely often, the dynamics of regularized learning in strongly monotone games always return to its vicinity in finite time (which we estimate), and their long-run distribution is sharply concentrated around a neighborhood thereof.We quantify the degree of this concentration, and we show that these favorable properties may all break down if the underlying game is not strongly monotone—underscoring in this way the limits of regularized learning in the presence of persistent randomness and uncertainty.