Abstract
Learning in zero-sum games studies a situation where multiple agents competitively learn their strategy. In such multi-agent learning, we often see that the strategies cycle around their optimum, i.e., Nash equilibrium. When a game periodically varies (called a "periodic" game), however, the Nash equilibrium moves generically. How learning dynamics behave in such periodic games is of interest but still unclear. Interestingly, we discover that the behavior is highly dependent on the relationship between the two speeds at which the game changes and at which players learn. We observe that when these two speeds synchronize, the learning dynamics diverge, and their time-average does not converge. Otherwise, the learning dynamics draw complicated cycles, but their time-average converges. Under some assumptions introduced for the dynamical systems analysis, we prove that this behavior occurs. Furthermore, our experiments observe this behavior even if removing these assumptions. This study discovers a novel phenomenon, i.e., synchronization, and gains insight widely applicable to learning in periodic games.
Introduction
In classical game theory, static games with constant payoffs are the standard. In these environments, learning algorithms like Gradient Descent-Ascent (GDA) typically result in strategies that cycle around the Nash Equilibrium (NE). While the trajectory itself does not converge, the time-average of these strategies eventually reaches the NE—a property known as time-average convergence.
However, real-world interactions are rarely static. Many games are periodic, influenced by daily, seasonal, or economic cycles. While recent research has explored time-varying games, most assume a constant NE despite shifting payoffs. This paper addresses the more realistic scenario: the behavior of learning dynamics when the Nash Equilibrium itself moves periodically.
Methodology
The study employs a combination of dynamical systems theory and numerical simulation. GDA is modeled as a continuous-time dynamical system, where the "natural frequency" ($\alpha$) of player cycling is characterized by the system's eigenvalues. The authors derive closed-form solutions for "Eigenvalue Invariant Games" to prove the conditions for divergence. This analysis is extended to "Smooth Periodic Games" using integral analysis, demonstrating that divergence is a generic property of integer frequency ratios.
To verify these theoretical findings, the authors conducted numerical experiments using Runge-Kutta methods. They simulated various scenarios, including $3 \times 3$ and $6 \times 6$ games, non-smooth payoff changes (square and triangle waves), and games with boundary constraints. These experiments utilized synthetic game matrices, such as variants of "Matching Pennies" perturbed by periodic functions, and random periodic perturbations for higher-dimensional games.
Key Insights: The Resonance Phenomenon
The central discovery is that learning in a periodic game behaves like a forced pendulum without dissipation. When the frequency of the game's change ($\omega$) matches the natural cycling frequency of the learning algorithm ($\alpha$), the system resonates.
This "synchronization" causes strategy oscillations to amplify until they diverge. The authors prove that divergence occurs whenever the ratio $\alpha/\omega$ is an integer. If the ratio is non-integer, the system remains stable, and the time-average converges. In multi-agent systems, such as 3-player polymatrix games, interactions shift the synchronization point (e.g., to $\omega/\alpha = \sqrt{3}$), indicating more complex natural frequencies.
Results and Discussion
Theoretical proofs for $2 \times 2$ games show that when $\alpha/\omega = n \in \mathbb{N}$, the strategy trajectory $x(t)$ grows at a speed proportional to $t$. Under these synchronized conditions, the time-average $\bar{x}(T)$ fails to converge to the Nash Equilibrium, breaking a fundamental assumption in multi-agent reinforcement learning.
Experiments confirmed that this phenomenon persists across non-smooth payoff waves and higher-dimensional games. Interestingly, boundary constraints (confining strategies to a valid probability simplex) prevent infinite divergence. Instead, strategies hit the boundaries, which eventually forces time-average convergence, though not necessarily to the moving NE.
Conclusion and Future Work
This research identifies synchronization as a critical factor in periodic game learning. While continuous-time analysis provides deep insight, future work should address discrete-time implementations common in AI. Additionally, investigating whether stabilized algorithms like Optimistic GDA or Extra-gradient methods can "de-synchronize" and successfully track a moving NE remains a vital open question. Developing algorithms capable of active tracking in real-time is a primary direction for future research.
Summary updated