English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We show that, for any sufficiently small fixed $\epsilon > 0$, when bothplayers in a general-sum two-player (bimatrix) game employ optimistic mirrordescent (OMD) with smooth regularization, learning rate $\eta = O(\epsilon^2)$and $T = \Omega(\text{poly}(1/\epsilon))$ repetitions, either the dynamicsreach an $\epsilon$-approximate Nash equilibrium (NE), or the averagecorrelated distribution of play is an $\Omega(\text{poly}(\epsilon))$-strongcoarse correlated equilibrium (CCE): any possible unilateral deviation does notonly leave the player worse, but will decrease its utility by$\Omega(\text{poly}(\epsilon))$. As an immediate consequence, when the iteratesof OMD are bounded away from being Nash equilibria in a bimatrix game, weguarantee convergence to an exact CCE after only $O(1)$ iterations. Our resultsreveal that uncoupled no-regret learning algorithms can converge to CCE ingeneral-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 aNE, the (cumulative) regret of both players is not only negative, but decayslinearly with time. Given that regret is the canonical measure of performancein online learning, our results suggest that cycling behavior of no-regretlearning algorithms in games can be justified in terms of efficiency.

Optimistic Mirror Descent Either Converges to Nash or to Strong Coarse Correlated Equilibria in Bimatrix Games