Synchronization In Learning In Periodic Zero-sum Games Triggers Divergence From Nash Equilibrium

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 d

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keyfujimoto2024synchronization

Related papers

• Convergence Of Heterogeneous Learning Dynamics In Zero-sum Stochastic Games (2023)2.26
• Memory Asymmetry Creates Heteroclinic Orbits To Nash Equilibrium In Learning In Zero-sum Games (2023)0.00
• Learning In Multi-memory Games Triggers Complex Dynamics Diverging From Nash Equilibrium (2023)0.00
• Last-iterate Convergence Of Payoff-based Independent Learning In Zero-sum Stochastic Games (2024)0.00
• On The Heterogeneity Of Independent Learning Dynamics In Zero-sum Stochastic Games (2021)0.00
• Teaching An Old Dynamics New Tricks: Regularization-free Last-iterate Convergence In Zero-sum Games Via BNN Dynamics (2026)0.00
• Learning In Zero-sum Markov Games: Relaxing Strong Reachability And Mixing Time Assumptions (2023)0.00
• Stability Of Multi-agent Learning In Competitive Networks: Delaying The Onset Of Chaos (2023)0.00