Beyond Time-Average Convergence: Near-Optimal Uncoupled Online Learning via Clairvoyant Multiplicative Weights Update

Georgios Piliouras, Ryann Sim, Stratis Skoulakis

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 Coarse Correlated Equilibrium. The latter improves on the current state-of-the-art convergence rate of uncoupled online learning dynamics.

Introduction

In the intersection of game theory and online learning, researchers study how selfish agents can learn to play optimally in an environment where they don't know the full game rules—the "uncoupled" setting. Traditionally, agents use algorithms like Multiplicative Weights Update (MWU) to minimize regret—the difference between their actual payoff and what they could have earned with the best fixed strategy in hindsight.

While standard MWU guarantees that average regret vanishes at a rate of $O(1/\sqrt{T})$, the community has been searching for "fast" convergence. Specifically, how quickly can a group of agents, each acting independently, reach a Coarse Correlated Equilibrium (CCE)? Previous state-of-the-art methods achieved rates near $1/T$, but they often involved complex "optimistic" updates and intricate proofs. This paper seeks a simpler, faster, and more intuitive mechanism for this convergence.

Methodology

The authors propose Clairvoyant MWU (CMWU), which operates within the standard uncoupled online learning framework.

Algorithm 1: Uncoupled Online Learning Dynamics framework

The core idea is a "look-ahead" mechanism:

  • The "Clairvoyant" Update: In standard MWU, an agent uses today's payoffs to decide tomorrow's strategy. In CMWU, agents update their strategies based on the payoff profiles resulting from tomorrow's behavior.
  • The Fixed-Point Challenge: Because an agent's strategy depends on what everyone else plays tomorrow (and vice versa), the update rule is implicit—it defines a fixed-point equation ($x^{t+1}$ appears on both sides).
  • Contraction Mapping: The authors prove that if the learning rate ($\eta$) is sufficiently small ($\eta < \frac{1}{(n-1)V}$), this fixed-point equation is a contraction map. This means agents can find the "clairvoyant" strategy efficiently through simple iteration, making the algorithm computationally practical and decentralized.
  • Sparse Sub-sampling: To achieve the final convergence result, the algorithm identifies a $O(\log T)$-sparse sub-sequence of "anchor points" in the history of play, rather than just averaging all play.

Key Results and Insights

CMWU achieves a constant regret of $\frac{\ln(m)}{\eta}$ for any normal-form game. Unlike standard algorithms where regret grows with time, CMWU's regret is bounded by a value independent of the number of rounds $T$.

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

The algorithm converges to a CCE at a rate of $O(nV \log m \frac{\log T}{T})$. As shown in the comparison table, this improves upon the previous state-of-the-art rate of $O(nV \log m \log^4 T / T)$ for general-sum games. This is a near-optimal result, as the theoretical lower bound for any uncoupled dynamic is $\Omega(1/T)$.

Key insights include:

  • Mental Simulation: CMWU can be viewed as agents sharing a "mental model" of the next period. They simulate play internally until it equilibrates, then take that equilibrium strategy into the real world.
  • Beyond Time-Averages: Focusing on a specific, sparse sub-sequence of the history is the key to breaking previous speed records for CCE convergence.
  • Simplicity of Proof: The authors note that their proof for $O(\frac{\log T}{T})$ convergence is significantly simpler than the previous proofs for slower $O(\frac{\log^4 T}{T})$ rates.

Limitations and Future Work

  • Step-Size Constraints: The fast convergence and the contraction mapping property rely on the step-size $\eta$ being relatively small. Exploring how the algorithm behaves with larger, more aggressive step-sizes is an open question.
  • Adversarial Robustness: CMWU is designed for "self-play" (where all agents follow the same logic). It prioritizes fast equilibrium convergence over the $O(\sqrt{T})$ adversarial regret guarantees that some other algorithms maintain when opponents are acting irrationally or maliciously.
  • Averaging Policies: The authors highlight the "averaging policy" (choosing which parts of history to look at) as an under-explored hyper-parameter in online learning that warrants further study in more complex game settings (like extensive-form games).

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)/η$ in all normal-form games with m actions and fixed step-sizes $η$. 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 $η$ 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{piliouras2022beyond,
  author = {Georgios Piliouras and Ryann Sim and Stratis Skoulakis},
  title = {{Beyond Time-Average Convergence: Near-Optimal Uncoupled Online Learning via Clairvoyant Multiplicative Weights Update}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
  url = {https://openreview.net/forum?id=s7HF717GKP},
}

Loading related content...

Figure