Learning in Matrix Games can be Arbitrarily Complex
- URL: http://arxiv.org/abs/2103.03405v1
- Date: Fri, 5 Mar 2021 00:41:35 GMT
- Title: Learning in Matrix Games can be Arbitrarily Complex
- Authors: Gabriel P. Andrade, Rafael Frongillo, Georgios Piliouras
- Abstract summary: We show that replicator dynamics is rich enough to be able to approximate arbitrary dynamical systems.
We show how replicator dynamics can effectively reproduce the well-known strange attractor of Lonrenz dynamics.
- Score: 24.6667169480096
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: A growing number of machine learning architectures, such as Generative
Adversarial Networks, rely on the design of games which implement a desired
functionality via a Nash equilibrium. In practice these games have an implicit
complexity (e.g. from underlying datasets and the deep networks used) that
makes directly computing a Nash equilibrium impractical or impossible. For this
reason, numerous learning algorithms have been developed with the goal of
iteratively converging to a Nash equilibrium. Unfortunately, the dynamics
generated by the learning process can be very intricate and instances of
training failure hard to interpret. In this paper we show that, in a strong
sense, this dynamic complexity is inherent to games. Specifically, we prove
that replicator dynamics, the continuous-time analogue of Multiplicative
Weights Update, even when applied in a very restricted class of games -- known
as finite matrix games -- is rich enough to be able to approximate arbitrary
dynamical systems. Our results are positive in the sense that they show the
nearly boundless dynamic modelling capabilities of current machine learning
practices, but also negative in implying that these capabilities may come at
the cost of interpretability. As a concrete example, we show how replicator
dynamics can effectively reproduce the well-known strange attractor of Lonrenz
dynamics (the "butterfly effect") while achieving no regret.
Related papers
- Last-Iterate Convergence of Payoff-Based Independent Learning in Zero-Sum Stochastic Games [31.554420227087043]
We develop learning dynamics that are payoff-based, convergent, rational, and symmetric between the two players.
In the matrix game setting, the results imply a complexity of $O(epsilon-1)$ to find the Nash distribution.
In the game setting, the results also imply a complexity of $O(epsilon-8)$ to find a Nash equilibrium.
arXiv Detail & Related papers (2024-09-02T20:07:25Z) - Hindsight States: Blending Sim and Real Task Elements for Efficient
Reinforcement Learning [61.3506230781327]
In robotics, one approach to generate training data builds on simulations based on dynamics models derived from first principles.
Here, we leverage the imbalance in complexity of the dynamics to learn more sample-efficiently.
We validate our method on several challenging simulated tasks and demonstrate that it improves learning both alone and when combined with an existing hindsight algorithm.
arXiv Detail & Related papers (2023-03-03T21:55:04Z) - Dynamical Equations With Bottom-up Self-Organizing Properties Learn
Accurate Dynamical Hierarchies Without Any Loss Function [15.122944754472435]
We propose a learning system where patterns are defined within the realm of nonlinear dynamics with positive and negative feedback loops.
Experiments reveal that such a system can map temporal to spatial correlation, enabling hierarchical structures to be learned from sequential data.
arXiv Detail & Related papers (2023-02-04T10:00:14Z) - Asymptotic Convergence and Performance of Multi-Agent Q-Learning
Dynamics [38.5932141555258]
We study the dynamics of smooth Q-Learning, a popular reinforcement learning algorithm.
We show a sufficient condition on the rate of exploration such that the Q-Learning dynamics is guaranteed to converge to a unique equilibrium in any game.
arXiv Detail & Related papers (2023-01-23T18:39:11Z) - No-Regret Learning in Games is Turing Complete [33.03065693224728]
We prove Turing completeness of the replicator dynamic on matrix games, one of the simplest possible settings.
Our results imply the undecicability of reachability problems for learning algorithms in games, a special case of which is determining equilibrium convergence.
arXiv Detail & Related papers (2022-02-24T02:37:50Z) - Dynamic Inference with Neural Interpreters [72.90231306252007]
We present Neural Interpreters, an architecture that factorizes inference in a self-attention network as a system of modules.
inputs to the model are routed through a sequence of functions in a way that is end-to-end learned.
We show that Neural Interpreters perform on par with the vision transformer using fewer parameters, while being transferrable to a new task in a sample efficient manner.
arXiv Detail & Related papers (2021-10-12T23:22:45Z) - Teach me to play, gamer! Imitative learning in computer games via
linguistic description of complex phenomena and decision tree [55.41644538483948]
We present a new machine learning model by imitation based on the linguistic description of complex phenomena.
The method can be a good alternative to design and implement the behaviour of intelligent agents in video game development.
arXiv Detail & Related papers (2021-01-06T21:14:10Z) - No-regret learning and mixed Nash equilibria: They do not mix [64.37511607254115]
We study the dynamics of "follow-the-regularized-leader" (FTRL)
We show that any Nash equilibrium which is not strict cannot be stable and attracting under FTRL.
This result has significant implications for predicting the outcome of a learning process.
arXiv Detail & Related papers (2020-10-19T13:49:06Z) - Continuous-in-Depth Neural Networks [107.47887213490134]
We first show that ResNets fail to be meaningful dynamical in this richer sense.
We then demonstrate that neural network models can learn to represent continuous dynamical systems.
We introduce ContinuousNet as a continuous-in-depth generalization of ResNet architectures.
arXiv Detail & Related papers (2020-08-05T22:54:09Z) - Model-Based Reinforcement Learning for Atari [89.3039240303797]
We show how video prediction models can enable agents to solve Atari games with fewer interactions than model-free methods.
Our experiments evaluate SimPLe on a range of Atari games in low data regime of 100k interactions between the agent and the environment.
arXiv Detail & Related papers (2019-03-01T15:40:19Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.