  We show that, for any sufficiently small fixed $\epsilon > 0$, when both
players in a general-sum two-player (bimatrix) game employ optimistic mirror
descent (OMD) with smooth regularization, learning rate $\eta = O(\epsilon^2)$
and $T = \Omega(\text{poly}(1/\epsilon))$ repetitions, either the dynamics
reach an $\epsilon$-approximate Nash equilibrium (NE), or the average
correlated distribution of play is an $\Omega(\text{poly}(\epsilon))$-strong
coarse correlated equilibrium (CCE): any possible unilateral deviation does not
only leave the player worse, but will decrease its utility by
$\Omega(\text{poly}(\epsilon))$. As an immediate consequence, when the iterates
of OMD are bounded away from being Nash equilibria in a bimatrix game, we
guarantee convergence to an exact CCE after only $O(1)$ iterations. Our results
reveal that uncoupled no-regret learning algorithms can converge to CCE in
general-sum games remarkably faster than to NE in, for example, zero-sum games.
To establish this, we show that when OMD does not reach arbitrarily close to a
NE, the (cumulative) regret of both players is not only negative, but decays
linearly with time. Given that regret is the canonical measure of performance
in online learning, our results suggest that cycling behavior of no-regret
learning algorithms in games can be justified in terms of efficiency.
