Multiplicative Weights Update with Constant Step-Size in Congestion Games: Convergence, Limit Cycles and Chaos

Gerasimos Palaiopanos, Ioannis Panageas, Georgios Piliouras

Introduction

This paper reveals a surprising divergence between two nearly identical versions of the Multiplicative Weights Update (MWU) algorithm when used with constant learning rates. While the "linear" variant ($\text{MWU}_\ell$) is guaranteed to converge to exact Nash equilibria in congestion games, the "exponential" variant ($\text{MWU}_e$, also known as Hedge) can spiral into limit cycles or even full-blown Li-Yorke chaos, even in the simplest two-player scenarios.

The Challenge of Constant Learning Rates

In game theory and machine learning, MWU is a ubiquitous "workhorse" algorithm used for regret minimization. Standard theory dictates that to achieve zero average regret, the learning rate ($\epsilon$) must decrease over time. However, in practice, researchers and practitioners often prefer to use a constant learning rate for its simplicity and its ability to adapt to non-stationary environments.

The authors pose a fundamental question: Can MWU with a constant learning rate behave well in a standard class of games?

To answer this, they focus on congestion games (such as traffic routing or load balancing), where players choose resources and the cost of a resource increases with the number of players using it. While these games are known to possess stable equilibria, previous empirical observations suggested that MWU dynamics often fail to reach them. This paper seeks to provide a formal mathematical explanation for this failure and offers a stable, theoretically sound alternative.

Two Variants, Two Drastically Different Outcomes

The authors analyze the discrete-time dynamical systems created by two common variants of MWU:

  1. Linear MWU ($\text{MWU}_\ell$): The probability of an action is multiplied by $(1 - \epsilon \cdot \text{cost})$.
  2. Exponential MWU ($\text{MWU}_e$): The probability is multiplied by $(1 - \epsilon)^{\text{cost}}$.

Despite being treated as interchangeable in most literature because they share the same regret bounds, these two variants have fundamentally different stability properties.

The Linear Advantage via Baum-Eagon

To prove convergence for the linear variant, the authors establish a novel connection between $\text{MWU}_\ell$ and the Baum-Eagon inequality. This inequality is a cornerstone of the Baum-Welch algorithm, widely used for training Hidden Markov Models. By demonstrating that $\text{MWU}_\ell$ in a congestion game is a special case of a Baum-Eagon system, they prove that a specific potential function (acting as a Lyapunov function) strictly decreases until the system hits a Nash equilibrium.

Result: For any congestion game, $\text{MWU}_\ell$ with an admissible constant learning rate converges to an exact Nash equilibrium from any interior starting point.

Chaos in the Exponential Variant

To prove the failure of the exponential variant, the authors utilize tools from nonlinear dynamics, specifically the Li-Yorke theorem (famous for the concept "Period three implies chaos"). They construct specific instances of simple load-balancing games—specifically "balls-and-bins" games where $n$ agents choose between $n$ resources—and show that the $\text{MWU}_e$ update rule maps to a chaotic function.

Result: There exist simple symmetric congestion games where $\text{MWU}_e$ exhibits Li-Yorke chaos. This means the system has periodic orbits of every possible length and an uncountable set of initial conditions that result in "scrambled," non-periodic behavior. You do not need a complex game for chaos to emerge; a simple 2-player, 2-bin load-balancing game is sufficient to trigger unpredictable trajectories if the learning rate is constant and the update is exponential.

Key Insights and Visual Evidence

The paper provides striking visual evidence of this divergence. As shown below, while $\text{MWU}_\ell$ smoothly settles into a fixed point over successive iterations, $\text{MWU}_e$ creates a tangled web of trajectories that never settle, even when utilizing the same learning rate.

Comparison of Exponential vs. Linear MWU dynamics over multiple iterations.

This highlights a crucial algorithmic bridge: the connection between game-theoretic learning (MWU) and Expectation-Maximization (Baum-Welch) is a powerful insight. It suggests that convergence proofs from the world of HMMs can be successfully imported into algorithmic game theory to design more stable learning dynamics.

Limitations and Future Directions

While the paper provides a robust theoretical foundation for the divergence of these algorithms, several open questions remain:

  • Symmetry Assumptions: Some of the chaotic results rely on players starting with symmetric initial conditions. The authors note it is an open question whether this chaotic behavior is "generic"—meaning, does it happen for almost all starting points in more complex, asymmetric games?
  • Fine-tuning the Boundary: The paper shows that as the learning rate $\epsilon$ increases, the system moves from stability to limit cycles and then to chaos (a process known as period-doubling). Mapping out exactly where these transitions occur for different game topologies remains a challenge.
  • Beyond Congestion Games: While $\text{MWU}_\ell$ works beautifully for congestion games (which are a type of "potential game"), its performance in other game classes—like zero-sum games where cyclic behavior is common—is still a subject of active research.

Summary updated

Abstract

The Multiplicative Weights Update (MWU) method is a ubiquitous meta-algorithm that works as follows: A distribution is maintained on a certain set, and at each step the probability assigned to action $\gamma$ is multiplied by $(1 -\epsilon C(\gamma))>0$ where $C(\gamma)$ is the ``cost" of action $\gamma$ and then rescaled to ensure that the new values form a distribution. We analyze MWU in congestion games where agents use \textit{arbitrary admissible constants} as learning rates $\epsilon$ and prove convergence to \textit{exact Nash equilibria}. Interestingly, this convergence result does not carry over to the nearly homologous MWU variant where at each step the probability assigned to action $\gamma$ is multiplied by $(1 -\epsilon)^{C(\gamma)}$ even for the simplest case of two-agent, two-strategy load balancing games, where such dynamics can provably lead to limit cycles or even chaotic behavior.
BibTeX
@inproceedings{palaiopanos2017multiplicative,
  author = {Gerasimos Palaiopanos and Ioannis Panageas and Georgios Piliouras},
  title = {{Multiplicative Weights Update with Constant Step-Size in Congestion Games: Convergence, Limit Cycles and Chaos}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2017},
  url = {https://openreview.net/forum?id=rkbup8WdbB},
}
Figure