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 for the first time, to our knowledge, that it is possible toreconcile in online learning in zero-sum games two seemingly contradictoryobjectives: vanishing time-average regret and non-vanishing step sizes. Thisphenomenon, that we coin ``fast and furious" learning in games, sets a newbenchmark about what is possible both in max-min optimization as well as inmulti-agent systems. Our analysis does not depend on introducing a carefullytailored dynamic. Instead we focus on the most well studied online dynamic,gradient descent. Similarly, we focus on the simplest textbook class of games,two-agent two-strategy zero-sum games, such as Matching Pennies. Even for thissimplest of benchmarks the best known bound for total regret, prior to ourwork, was the trivial one of $O(T)$, which is immediately applicable even to anon-learning agent. Based on a tight understanding of the geometry of thenon-equilibrating trajectories in the dual space we prove a regret bound of$\Theta(\sqrt{T})$ matching the well known optimal bound for adaptive stepsizes in the online setting. This guarantee holds for all fixed step-sizeswithout having to know the time horizon in advance and adapt the fixedstep-size accordingly. As a corollary, we establish that even with fixedlearning rates the time-average of mixed strategies, utilities converge totheir exact Nash equilibrium values.

Fast and Furious Learning in Zero-Sum Games: Vanishing Regret with Non-Vanishing Step Sizes