Chaos Persists In Large-scale Multi-agent Learning Despite Adaptive Learning Rates

Abstract

Multi-agent learning is intrinsically harder, more unstable and unpredictable than single agent optimization. For this reason, numerous specialized heuristics and techniques have been designed towards the goal of achieving convergence to equilibria in self-play. One such celebrated approach is the use of dynamically adaptive learning rates. Although such techniques are known to allow for improved convergence guarantees in small games, it has been much harder to analyze them in more relevant settings with large populations of agents. These settings are particularly hard as recent work has established that learning with fixed rates will become chaotic given large enough populations.In this work, we show that chaos persists in large population congestion games despite using adaptive learning rates even for the ubiquitous Multiplicative Weight Updates algorithm, even in the presence of only two strategies. At a technical level, due to the non-autonomous nature of the system, our approach g

Stats

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

Related papers

• Stability Of Multi-agent Learning In Competitive Networks: Delaying The Onset Of Chaos (2023)0.00
• On The Stability Of Learning In Network Games With Many Players (2024)0.00
• Convergence And Connectivity: Dynamics Of Multi-agent Q-learning In Random Networks (2025)0.00
• Convergence Analysis Of Gradient-based Learning With Non-uniform Learning Rates In Non-cooperative Multi-agent Settings (2019)0.00
• The Evolutionary Dynamics Of Independent Learning Agents In Population Games (2020)0.00
• Asymptotic Convergence And Performance Of Multi-agent Q-learning Dynamics (2023)0.00
• Learning In Multi-memory Games Triggers Complex Dynamics Diverging From Nash Equilibrium (2023)0.00
• A Survey Of Learning In Multiagent Environments: Dealing With Non-stationarity (2017)0.00