Source-linked AI summary
Cycles in adversarial regularized learning
Panayotis Mertikopoulos, Christos Papadimitriou, Georgios Piliouras
TL;DR
The paper asks how coupled regularized learners behave in zero-sum competition beyond their time-averaged no-regret guarantees. It analyzes continuous-time FoReL dynamics and shows that almost every trajectory is recurrent, with cycling robust across regularizers, payoff transformations, and polymatrix games.
Problem
Regret-based convergence of time averages does not determine whether actual play converges, recurs, or cycles in zero-sum games.
Method
The paper studies continuous-time FoReL by transforming play into payoff-difference coordinates and combining incompressibility with an invariant coupling.
Results
FoReL is Poincaré recurrent in zero-sum games with an interior equilibrium, and cycling persists across different regularizers, positive-affine utility transformations, and constant-sum polymatrix games.
Takeaways & Limitations
Strong no-regret guarantees do not imply convergence of actual play; regularized learning can instead generate persistent cycles in adversarial environments.
Takeaways & Limitations
Zero-sum polymatrix games without an interior equilibrium are left for future work.
Abstract
from arXiv · showhide
Regularized learning is a fundamental technique in online optimization, machine learning and many other fields of computer science. A natural question that arises in these settings is how regularized learning algorithms behave when faced against each other. We study a natural formulation of this problem by coupling regularized learning dynamics in zero-sum games. We show that the system's behavior is Poincaré recurrent, implying that almost every trajectory revisits any (arbitrarily small) neighborhood of its starting point infinitely often. This cycling behavior is robust to the agents' choice of regularization mechanism (each agent could be using a different regularizer), to positive-affine transformations of the agents' utilities, and it also persists in the case of networked competition, i.e., for zero-sum polymatrix games.
1. Introduction
Regularization supports flexible no-regret learning, but standard analyses mainly describe time-averaged behavior and leave the actual long-run trajectory unresolved.
- Regularization improves conditioning, reduces overfitting, and can yield sparse, efficient algorithms.
- FoReL offers O(t−1/2) adversarial min-max regret, adapts to problem geometry, and includes hedge, multiplicative weights, and gradient descent as special cases.
- Standard no-regret analysis combines empirical-frequency convergence to coarse correlated equilibria with structural properties of those equilibria.
- Later work obtains stronger regret rates in structured games, including O(log t/t) in two-player zero-sum games and O(t−3/4) in broader multi-player settings.
- Regret-based analysis does not answer the fundamental behavioral question of how the coupled dynamics evolve over time.
Does it even stabilize?
The paper asks whether optimization-driven learning stabilizes in perfect competition, where time averages may converge while actual play follows a different long-run pattern.
- Convergent, recurrent, and chaotic systems can all exhibit similarly strong regret minimization, so regret alone cannot distinguish their long-run behavior.
- Zero-sum games model competitive optimization duels, and regret-minimizing dynamics can have time averages converging to approximate equilibria.
- Time-averaged FoReL marginals converge to min-max states, but the actual sequence of play raises separate questions about convergence and equilibration.
Our results.
The paper shows that FoReL cycles rather than stabilizes in relevant zero-sum settings: trajectories are recurrent, and this behavior persists across regularizers, payoff transformations, and networked competition.
- Our results.: FoReL in zero-sum games with an interior equilibrium is Poincaré recurrent, so almost every trajectory returns arbitrarily close to its starting point infinitely often.
- Our results.: The cycling behavior is robust when agents use different regularizers and under positive-affine utility transformations.
- Our results.: The same cycling behavior persists in constant-sum polymatrix games, including networked competition.
- Our results.: FoReL’s continuous-time formulation includes replicator and projection dynamics as special cases and achieves an O(t−1) regret rate.
- Our results.: In payoff-difference coordinates, the FoReL flow is incompressible, preserving the volume of sets of initial conditions.
- Our results.: For an interior equilibrium, an invariant coupling built from convex conjugates combines with incompressibility to establish recurrence.
- Our results.: Without an interior equilibrium, G decreases until the support matches a maximal-support Nash equilibrium, and convergence is possible only under the restrictive pure-unique-equilibrium case.
2. Definitions from game theory
The paper defines finite normal-form games, mixed strategies, equilibria, zero-sum interactions, and polymatrix extensions in which players aggregate payoffs across network neighbors.
- A finite normal-form game specifies players, finite action sets, and payoff functions over action profiles.
- A mixed strategy is a probability distribution over a player’s actions, and a strategy profile is the product of players’ mixed-strategy spaces.
- Expected payoffs are obtained by averaging action-profile payoffs under the players’ mixed strategies, while pure-strategy payoffs form each player’s payoff vector.
- A Nash equilibrium is a mixed-strategy profile from which no player benefits by unilaterally deviating.
- An interior equilibrium fully mixes every player’s actions, whereas a coarse correlated equilibrium is a distribution over action profiles satisfying deviation inequalities.
- In a two-player zero-sum game, one player’s payoff is the negative of the other’s, and Nash equilibria solve the min-max saddle-point problem.
- A polymatrix game places pairwise zero- or constant-sum games on graph edges, with each player’s payoff equal to the sum of interactions with neighbors.
- The analysis also includes games payoff-equivalent to positive-affine transformations of pairwise constant-sum polymatrix games.
3. No-regret learning via regularization
The section presents FoReL as a regularized no-regret framework for online decision making, with continuous-time dynamics that achieve an O(1/t) regret bound under basic regularizer assumptions.
- Setting: The analysis focuses on repeated decision making in low-information environments where players may not know the game’s rules or equilibrium strategies.The section therefore assumes only that players seek to minimize regret.
- No-regret learning: Players are assumed to minimize regret, defined as the average payoff difference from the best strategy in hindsight.No regret means lim sup_t→∞ Reg_i(t) ≤ 0.
- FoReL dynamics: FoReL selects strategies by maximizing cumulative payoff minus a convex regularization penalty.The penalty smooths the hard arg max and biases play toward the regularizer’s prox-center.
- Examples: The framework includes multiplicative-weights and projection dynamics as prototypical regularizer-induced examples.The entropic regularizer yields replicator dynamics, while the Euclidean regularizer induces projection dynamics.
- Guarantees: Under continuous-time FoReL, each player achieves an O(1/t) regret bound against every continuous trajectory of opponents.This improves on the Θ(t−1/2) worst-case discrete-time bound cited in the section.
4. Recurrence in adversarial regularized learning
The paper analyzes FoReL trajectories in zero-sum games through recurrence and boundary behavior. With an interior equilibrium, almost every trajectory is recurrent; without one, trajectories approach an equilibrium-supported face, with analogous recurrence extending to suitable polymatrix games.
- Recurrence: Recurrence means that almost every trajectory returns arbitrarily close to its starting state infinitely often.The paper contrasts this with convergence, in which trajectories approach a well-defined end-state.
- 4.1. Zero-sum games with an interior equilibrium.: In zero-sum games with an interior Nash equilibrium, almost every FoReL trajectory is recurrent.For almost every initial condition, there are times t_n→∞ at which x(t_n)→x(0).
- 4.1. Zero-sum games with an interior equilibrium.: The proof combines incompressibility, a transformed system of score differences, bounded invariant level sets, and Poincaré’s recurrence theorem.The primal-dual coupling is invariant, while the transformed coupling level sets become compact.
- 4.1. Zero-sum games with an interior equilibrium.: The score-difference transformation is needed because the original dynamics are not immediately autonomous: score differences do not uniquely recover the score vector.A reduced choice map is introduced to define the transformed dynamics on the difference variables.
- 4.2. Zero-sum games with no interior equilibria.: Without an interior Nash equilibrium, every FoReL trajectory converges to the relative interior of the face spanned by a maximal-support equilibrium.The coupling decreases until the players’ supports match that equilibrium’s support.
- 4.2. Zero-sum games with no interior equilibria.: In general zero-sum games, FoReL eventually wanders within the smallest face containing the equilibrium set.Interior equilibria yield recurrent cycling, pure unique equilibria yield convergence, and intermediate cases combine face convergence with perpetual cycling.
- 4.3. Zero-sum polymatrix games & positive affine payoff transformations.: For constant-sum polymatrix games with an interior equilibrium, almost every FoReL trajectory is recurrent.The result also holds after positive-affine payoff transformations, including the class of strictly competitive games.
5. Conclusions
The results show that regularized learning can combine strong no-regret guarantees with recurrent, cyclic trajectories. This finer dynamical behavior is more intricate than regret properties alone suggest.
- FoReL’s empirical frequency converges to coarse correlated equilibria, while its actual play trajectory is recurrent and cycles in zero-sum games.
- The contrast between convergent, recurrent, and chaotic systems cannot be resolved by regret-based analysis alone.
- Dynamical-systems theory provides additional concepts for examining learning algorithms beyond their regret-minimization properties.
Appendix A. Examples of FoReL dynamics
FoReL includes several familiar learning dynamics through different regularizers and choice maps. Entropic regularization yields multiplicative-weights and replicator dynamics, while quadratic regularization yields projection-based dynamics.
- FoReL encompasses hedge, multiplicative weights, and gradient descent as special cases of regularized learning dynamics.
- The logit choice map with an entropic regularizer produces multiplicative-weights dynamics.
- Differentiating multiplicative-weights dynamics gives the replicator dynamics studied in evolutionary game theory.
- A quadratic penalty induces the Euclidean projection map and a projected reinforcement-learning process.
- Multiplicative weights is the continuous-time version of the discrete-time multiplicative-weights update rule.
Poincaré’s recurrence theorem.
Poincaré recurrence states that volume-preserving dynamical systems with bounded orbits repeatedly return arbitrarily close to their initial positions.
- Poincaré recurrence concerns dynamical systems whose flows preserve volume and have bounded orbits.
- Almost all trajectories return arbitrarily close to their starting points infinitely often.
- More precisely, every open set has orbits that intersect it infinitely often under the stated conditions.
Appendix C. Technical proofs
The technical proofs characterize equilibrium supports, establish monotonic coupling behavior for games without interior equilibria, and analyze recurrence through payoff-space dynamics and polymatrix structure.
- Equilibrium characterization: In zero-sum games without interior equilibria, an equilibrium can assign positive probability to every essential strategy while non-essential deviations perform strictly below the game value.
- Equilibrium characterization: Farkas’ lemma is used to construct opponent equilibria that make each non-essential strategy strictly worse than the game value.
- Monotonicity: For fully mixed initial conditions in such games, the coupling function strictly increases under FoReL for every trajectory of the other players.
- Monotonicity: The coupling is bounded below and strictly decreasing in the analyzed orientation, so it has a finite limit.
- Boundary behavior: Every omega-limit point lies on the boundary when the game lacks an interior equilibrium.
- Polymatrix extension: Different edge weights alter trajectories and the equilibrium set in a three-player zero-sum polymatrix game, but not the cycling behavior.
Appendix D. Auxiliary results
Appendix D establishes auxiliary lemmas used in the proof of Theorem 4.2. These results show that bounded Fenchel-coupling levels constrain score differences, while large score gaps force lower-scoring strategies to vanish, and a finite differentiable limit forces derivatives to approach zero.
- Extinction under diverging gaps: If a score difference y_β,n − y_α,n diverges to infinity, Lemma D.1 implies Q_α(y_n) → 0.Thus, the strategy with the lower score becomes extinct under the regularized choice map.
- Bounded score differences: Lemma D.2 shows that bounded h∗(y_n) − ⟨y_n, p⟩ with interior p implies all coordinate differences y_β,n − y_α,n remain bounded.The lemma is used to show boundedness of level sets under the coordinate-reduction transformation.
- Bounded score differences: The contradiction argument proves that bounded Fenchel coupling prevents any coordinate score difference from becoming unbounded.The proof uses extinction of the lower-scoring strategy and derives G_n → −∞, contradicting boundedness.
- Contradiction argument: The identity G_n = h∗(y_n) − ⟨y_n, x∗⟩ = ⟨y_n, p − x_n⟩ − h(x_n) drives the contradiction when a score gap diverges.Since h is finite on the simplex, the argument concludes that G_n would tend to −∞ despite its assumed boundedness.
- Derivative asymptotics: Lemma D.3 states that if L has a Lipschitz-continuous derivative and a finite limit at infinity, then L′(t) → 0.The proof shows that any derivative bounded away from zero over intervals of fixed width would force L to exceed its finite limiting value.