No-regret Learning In Games Is Turing Complete

Abstract

Games are natural models for multi-agent machine learning settings, such as generative adversarial networks (GANs). The desirable outcomes from algorithmic interactions in these games are encoded as game theoretic equilibrium concepts, e.g. Nash and coarse correlated equilibria. As directly computing an equilibrium is typically impractical, one often aims to design learning algorithms that iteratively converge to equilibria. A growing body of negative results casts doubt on this goal, from non-convergence to chaotic and even arbitrary behaviour. In this paper we add a strong negative result to this list: learning in games is Turing complete. Specifically, 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.

Stats

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

Related papers

• Learning In Multi-memory Games Triggers Complex Dynamics Diverging From Nash Equilibrium (2023)0.00
• On The Complexity Of Computing Sparse Equilibria And Lower Bounds For No-regret Learning In Games (2023)0.00
• The Bounds Of Algorithmic Collusion; \(q\)-learning, Gradient Learning, And The Folk Theorem (2024)0.00
• Regret Minimization And Convergence To Equilibria In General-sum Markov Games (2022)0.00
• Hardness Of Independent Learning And Sparse Equilibrium Computation In Markov Games (2023)0.00
• Distributed No-regret Learning In Multi-agent Systems (2020)0.00
• A Black-box Approach For Non-stationary Multi-agent Reinforcement Learning (2023)0.00
• What Game Are We Playing? End-to-end Learning In Normal And Extensive Form Games (2018)0.00