The equivalence of dynamic and strategic stability under regularized
  learning in games
Victor Boone Panayotis Mertikopoulos
In this paper, we examine the long-run behavior of regularized, no-regret
learning in finite games. A well-known result in the field states that the
empirical frequencies of no-regret play converge to the game's set of coarse
correlated equilibria; however, our understanding of how the players' actual
strategies evolve over time is much more limited - and, in many cases,
non-existent. This issue is exacerbated further by a series of recent results
showing that only strict Nash equilibria are stable and attracting under
regularized learning, thus making the relation between learning and pointwise
solution concepts particularly elusive. In lieu of this, we take a more general
approach and instead seek to characterize the \emph{setwise} rationality
properties of the players' day-to-day play. To that end, we focus on one of the
most stringent criteria of setwise strategic stability, namely that any
unilateral deviation from the set in question incurs a cost to the deviator - a
property known as closedness under better replies (club). In so doing, we
obtain a far-reaching equivalence between strategic and dynamic stability: a
product of pure strategies is closed under better replies if and only if its
span is stable and attracting under regularized learning. In addition, we
estimate the rate of convergence to such sets, and we show that methods based
on entropic regularization (like the exponential weights algorithm) converge at
a geometric rate, while projection-based methods converge within a finite
number of iterations, even with bandit, payoff-based feedback.