Faster Rates for No-Regret Learning in General Games via Cautious Optimism

Ashkan Soleymani, Georgios Piliouras, Gabriele Farina · 2025

Read Faster Rates for No-Regret Learning in General Games via Cautious Optimism by Ashkan Soleymani, Georgios Piliouras, Gabriele Farina (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-24340.txt.

Introduction

In a game played again and again, a learner who keeps regret low will, over time, play near the best it can. Ashkan Soleymani, Georgios Piliouras, and Gabriele Farina speed that learning up in 2025. Their method is uncoupled: each player learns from its own past alone, with no view of the rest.

The team pairs a classic hopeful update rule with a learning pace that shifts as it goes. When a player's regret dips too far below zero, the pace eases, which makes the player more cautious. The bound they prove grows far more slowly with the count of moves than past bests. It also trims the growth with rounds played. Sharp regret bounds matter since they set how fast a group of learners can settle to a shared balance.

Catalog record

CREATORAshkan Soleymani, Georgios Piliouras, Gabriele Farina
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE140 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-24340

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Faster Rates for No-Regret Learning in General Games via Cautious Optimism Ashkan Soleymani, Georgios Piliouras, Gabriele Farina Abstract We establish the first uncoupled learning algorithm that attains O ⁡ ( n ​ log 2 ​ d ​ log ⁡ T ) O(n\log^{2}d\log T) per-player regret in multi-player general-sum games, where n n is the number of players, d d is the number of actions available to each player, and T T is the number of repetitions of the game. Our results exponentially improve the dependence on d d compared to the O ⁡ ( n ​ d ​ log ⁡ T ) O(n\,d\log T) regret attainable by Log-Regularized Lifted Optimistic FTRL [ Far+22b ] , and also reduce the dependence on the number of iterations T T from log 4 ⁡ T \log^{4}T to log ⁡ T \log T compared to Optimistic Hedge, the previously well-studied algorithm with O ⁡ ( n ​ log ⁡ d ​ log 4 ​ T ) O(n\log d\log^{4}T) regret [ DFG21 ] . Our algorithm is obtained by combining the classic Optimistic Multiplicative Weights Update (OMWU) with an adaptive, non-monotonic learning rate that paces the learning process of the players, making them more cautious when their regret becomes too negative. 1 Introduction The study of how multiple interacting agents learn to adapt their strategies is a well-established problem with significant foundations in game theory, online optimization, control theory, economics, and behavioral sciences [ CL06 , Nis+07 , MS15 , Gin00 , Cam11 ] . This area has gained increased importance with the advent of machine learning, where multi-agent games are integral to many fundamental architectures and applications [ Goo+14 , Sil+17 , Mor+17 , BS19 , Big+24 ] . Despite the intuitive appeal of simple uncoupled learning algorithms that globally converge to Nash equilibria in all games, strong impossibility results demonstrate that such algorithms do not exist—even in the classic and relatively constrained context of normal-form games [ HM03 , Mil+23 ] . From the perspective of centralized algorithms, [ DGP06 ] took a step further by linking the computational complexity of finding a Nash equilibrium in games to solving Brouwer’s fixed-point problem, showing that computing a Nash equilibrium in polynomial time is impossible unless PPAD = P, suggesting the problem is inherently computationally difficult. These roadblocks have inspired the pursuit of alternative solution concepts, with the notion of regret minimization being arguably the most influential and well-studied among them [ Sha12 , Haz+16 ] . Originally defined within the context of single-agent optimization, regret measures the difference between the accumulated performance of an algorithm and that of the best fixed action in hindsight, under uncertain and possibly adversarial realizations of payoffs. Regret minimization in general games is sufficient to establish the time-average convergence of the empirical distribution of play to the set of Coarse Correlated Equilibria (CCE). This set is a relaxation of the Nash equilibrium concept—motivated by the intractability of Nash equilibrium—and possesses several desirable properties, including approximate optimality of the resulting social welfare, connections to Nash and correlated equilibria, broad applicability across a diverse range of games, and flexibility in strategy coordination [ BEL06 , NP10 , Rou15 , Cai+16 , MP17 , RST17 ] . Beyond convergence to CCE in game settings, regret minimization is recognized as a fundamental concept with wide-ranging applications, including learning and generalization [ Lit88 , Blu90 , LN23 ] , von Neumann’s minimax theorem and Blackwell approachability [ FS96 , ABH11 ] , boosting [ FS95 , FS96 ] , combinatorial optimization [ PST95 , AK07 ] , complexity theory [ KS99 , BHK09 ] , differential privacy [ HR10 , HRU13 ] , prediction markets [ CV10 , ACV13 ] , evolutionary dynamics [ Cha+13 ] , and more. In the adversarial case, it is classically known that simple algorithms such as Hedge/Multiplicative Weights Update (MWU) suffice to establish the optimal regret rate of O(T^{1/2}) [ FS97 ] . Nevertheless, an adversarial framework is often overly pessimistic for applications in game theory, as it may yield suboptimal results in more favorable and predictable environments. This is particularly evident in the context of learning in games, where player interactions are nonstationary but typically evolve slowly. Consequently, determining the tightest possible bounds for no-regret learning in general games remains a fundamental and unresolved problem. We enumerate major previous attempts in this line of work in Section 1.2 . By the Optimism framework of [ Syr+15 ] , there exist algorithms for which the sum of players’ regrets in self-play remains constant over time. Unfortunately, controlling individual regrets—necessary for convergence to Coarse Correlated Equilibria (CCE)—is much harder , and despite nearly a decade of noteworthy progress, the optimal regret rate remains elusive. Intuitively, we seek to avoid agents with runaway negative regret. Our main high-level idea is to adapt optimism into a form of Cautious Optimism , where agents decrease their learning rates when their regret becomes too negative—that is, when they significantly outperform all fixed actions. Surprisingly, we show that it is possible to carefully apply this germ of an idea to achieve new state-of-the-art regret bounds. 1.1 Overview of the Main Result and Techniques We establish the first uncoupled no-regret learning algorithm that attains O(n\log^{2}d\log T) regret in multi-player general-sum games. Our algorithm is best understood as an Optimistic Multiplicative Weights Update ( OMWU ) paired with a dynamic learning rate that is adjusted based on the regret accumulated by the learner. For this reason, we coin our method Dynamic Learning Rate Control OMWU ( DLRC-OMWU ) . A key characteristic that sets our approach apart from standard adaptive learning-rate techniques is that our dynamic control does not produce monotonically decreasing learning rates. Instead, the goal of our dynamic learning rate is to properly pace the learner— slowing it down when it is performing too well —that is, when its maximum regret becomes too negative. We achieve this by solving an optimization problem at each iteration to determine the learning rate, based on the player’s current regret vector. The idea of agents differentiating their behavior depending on whether they feel content or discontent is both simple and intuitive, and has inspired other game dynamics that provably concentrate around pure Nash equilibria [ You09 ] , as well as adjusted replicator dynamics in evolutionary game theory [ Wei97 ] . In the context of regret minimization, this idea can be traced back to the work of [ BV02 ] , who introduced the Win or Learn Fast (WoLF) principle. This principle increases the learning rate of agents when they are losing, thereby resulting in quicker adaptation to the environment and to the strategies of other agents. [ BV02 ] demonstrated the convergence of gradient ascent-descent with WoLF to a Nash equilibrium in the restricted case of two players with two actions. [ Bow04 ] extended WoLF to multiplayer settings, showing it achieves no-regret dynamics with O(d\sqrt{T}) regret. Despite the success of WoLF and related heuristics in small-scale games [ AL08 , BP03 , Blo+15 , Kai+09 , LP22 ] , their theoretical guarantees in general games remain unclear. On the negative side, it has recently been shown that the multiplicative weights update algorithm, even when equipped

Read the complete text