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.
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:
- Anchor Points: Play is punctuated by "anchor points" spaced $O(\log T)$ steps apart.
- Internal Simulation: Between these points, agents run standard MWU internally to converge to the "clairvoyant" fixed point.
- 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$.
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