Optimal No-Regret Learning in General Games: Bounded Regret with Unbounded Step-Sizes via Clairvoyant MWU

Georgios Piliouras, Ryann Sim, Stratis Skoulakis

Abstract

This paper introduces Clairvoyant Multiplicative Weights Updates (CMWU), a novel and simple algorithm for regret minimization in general games. CMWU effectively corresponds to the standard MWU algorithm but where agents are "clairvoyant," using payoff profiles based on future behavior. While this involves a fixed-point computation, we demonstrate that for sufficiently small step-sizes, the update can be computed efficiently via a contraction map. This leads to an uncoupled online learning dynamic that achieves a constant regret of $\ln(m)/\eta$ and converges to a Coarse Correlated Equilibrium (CCE) at a rate of $O(nV \log m \log T / T)$, significantly improving upon previous state-of-the-art results.

Introduction

In multi-agent systems, agents often learn through repeated interactions without knowing the full rules of the game or their opponents' payoff matrices. This "uncoupled online learning" setting is fundamental to training AI in complex environments. While standard no-regret algorithms like Multiplicative Weights Update (MWU) guarantee convergence to Coarse Correlated Equilibrium (CCE) at a rate of $O(1/\sqrt{T})$, this rate is often too slow for practical self-play applications. Recent advancements have pushed this to $O(\log^4 T / T)$, but the search for faster, simpler dynamics continues. This work presents CMWU, which achieves near-optimal convergence by leveraging an implicit "look-ahead" mechanism.

The Uncoupled Learning Problem

The core challenge lies in the uncoupled nature of the learning dynamics. In this setting, agents only observe their own rewards and do not have access to the internal states or payoff functions of others.

Algorithm 1: Uncoupled Online Learning Dynamics

As shown in Algorithm 1, at each round $t$, agents broadcast their mixed strategies, learn their own reward vectors, and update their strategies for the next round based solely on their own history of rewards. The goal is to find dynamics where the time-averaged strategies converge rapidly to an equilibrium.

Methodology: Clairvoyant MWU (CMWU)

The proposed algorithm, Clairvoyant Multiplicative Weights Updates (CMWU), modifies the standard MWU by having agents update their strategies based on the payoffs of tomorrow's actions rather than today's. This "clairvoyance" creates an implicit fixed-point equation: the strategy at time $t+1$ depends on the strategy profile at time $t+1$.

While solving such a fixed-point equation centrally would be computationally expensive and violate the uncoupled constraint, the authors prove that if the learning step-size $\eta$ is upper bounded by $\frac{1}{(n-1)V}$ (where $n$ is the number of agents and $V$ is the payoff range), the CMWU update rule becomes a contraction map.

This allows for a practical implementation using:

  1. Anchor Points: Play is punctuated by "anchor points" spaced $O(\log T)$ steps apart.
  2. Internal Simulation: Between these points, agents run standard MWU internally to converge to the "clairvoyant" fixed point.
  3. Sparse Averaging: Instead of averaging the entire history, the algorithm averages only the $O(\log T)$-sparse anchor points.

Key Results and Convergence

CMWU provides significant theoretical improvements over existing methods. It guarantees that the sparse sub-trajectory admits constant regret ($\ln(m)/\eta$) for all agents, independent of the total time $T$.

Comparison of convergence rates for various update rules in general and zero-sum games.

As summarized in the table above, CMWU (Theorem 4.1) achieves a convergence rate of $O(nV \log m \log T / T)$ to CCE in general-sum games. This is a substantial improvement over the previous state-of-the-art rate of $O(nV \log m \log^4 T / T)$ achieved by prior optimistic methods. By decoupling the requirements of adversarial no-regret from CCE convergence, CMWU achieves faster rates with a simpler mathematical framework.

Conclusion

CMWU represents a major step forward in the theory of uncoupled learning dynamics. By utilizing implicit methods through contraction maps and introducing the concept of sparse averaging, it achieves near-optimal convergence in general games. Future work includes extending these results to extensive-form games and exploring the empirical performance of sparse averaging in deep learning contexts like GANs.

Summary updated

Abstract

In this paper, we provide a novel and simple algorithm, Clairvoyant Multiplicative Weights Updates (CMWU) for regret minimization in general games. CMWU effectively corresponds to the standard MWU algorithm but where all agents, when updating their mixed strategies, use the payoff profiles based on tomorrow's behavior, i.e. the agents are clairvoyant. CMWU achieves constant regret of $\ln(m)/\eta$ in all normal-form games with m actions and fixed step-sizes $\eta$. Although CMWU encodes in its definition a fixed point computation, which in principle could result in dynamics that are neither computationally efficient nor uncoupled, we show that both of these issues can be largely circumvented. Specifically, as long as the step-size $\eta$ is upper bounded by $\frac{1}{(n-1)V}$, where $n$ is the number of agents and $[0,V]$ is the payoff range, then the CMWU updates can be computed linearly fast via a contraction map. This implementation results in an uncoupled online learning dynamic that admits a $O (\log T)$-sparse sub-sequence where each agent experiences at most $O(nV\log m)$ regret. This implies that the CMWU dynamics converge with rate $O(nV \log m \log T / T)$ to a \textit{Coarse Correlated Equilibrium}. The latter improves on the current state-of-the-art convergence rate of \textit{uncoupled online learning dynamics} \cite{daskalakis2021near,anagnostides2021near}.
BibTeX
@inproceedings{piliouras2022optimal,
  author = {Georgios Piliouras and Ryann Sim and Stratis Skoulakis},
  title = {{Optimal No-Regret Learning in General Games: Bounded Regret with Unbounded Step-Sizes via Clairvoyant MWU}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
  url = {https://openreview.net/forum?id=s7HF717GKP},
}
Figure