From Chaos to Order: Symmetry and Conservation Laws in Game Dynamics
Games are an increasingly useful tool for training and testing learning algorithms. Recent examples include GANs, AlphaZero and the AlphaStar league. However, multi-agent learning can be extremely difficult to predict and control. Even simple games learning dynamics can yield chaotic behavior. In this paper, we present basic \emph{mechanism design} tools for constructing games with predictable and controllable dynamics. We show that arbitrarily large and complex network games, encoding both cooperation (team play) and competition (zero-sum interaction), exhibit conservation laws when agents use the standard regret-minimizing dynamics known as Follow-the-Regularized-Leader. These laws persist even if different agents use different dynamics and encode long-range correlations between agents' behavior even though the agents may not interact directly. Moreover, we provide sufficient conditions under which the dynamics have multiple, linearly independent, conservation laws. Increasing the number of conservation laws results in more predictable dynamics, eventually making chaotic behavior in some cases even formally impossible.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Constants of Motion: The Antidote to Chaos in Optimization and Game Dynamics
Several recent works in online optimization and game dynamics have established strong negative complexity results including the formal emergence of instability and chaos even in small such settings, e.g., $2\times 2$ gam…
From Data to Laws: Neural Discovery of Conservation Laws Without False Positives
Conservation laws are fundamental to understanding dynamical systems, but discovering them from data remains challenging due to parameter variation, non-polynomial invariants, local minima, and false positives on chaotic…
An Equivariance Toolbox for Learning Dynamics
Many theoretical results in deep learning can be traced to symmetry or equivariance of neural networks under parameter transformations. However, existing analyses are typically problem-specific and focus on first-order c…
Symmetry-regularized neural ordinary differential equations
Neural ordinary differential equations (Neural ODEs) is a class of machine learning models that approximate the time derivative of hidden states using a neural network. They are powerful tools for modeling continuous-tim…
Symmetry, Conservation Laws, and Learning Dynamics in Neural Networks
Predicting the dynamics of neural network parameters during training is one of the key challenges in building a theoretical foundation for deep learning. A central obstacle is that the motion of a network in high-dimensi…