The Bounds Of Algorithmic Collusion; \(q\)-learning, Gradient Learning, And The Folk Theorem

Abstract

We explore the behaviour emerging from learning agents repeatedly interacting strategically for a wide range of learning dynamics, including \(Q\)-learning, projected gradient, replicator and log-barrier dynamics. Going beyond the better understood classes of potential games and zero-sum games, we consider the setting of a general repeated game with finite recall under different forms of monitoring. We obtain a Folk Theorem-style result and characterise the set of payoff vectors that can be obtained by these dynamics, discovering a wide range of possibilities for the emergence of algorithmic collusion. Achieving this requires a novel technical approach, which, to the best of our knowledge, yields the first convergence result for multi-agent \(Q\)-learning algorithms in repeated games.

Stats

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

Related papers

• Exploration-exploitation In Multi-agent Competition: Convergence With Bounded Rationality (2021)0.00
• Beyond Strict Competition: Approximate Convergence Of Multi Agent Q-learning Dynamics (2023)0.00
• Convergence And Connectivity: Dynamics Of Multi-agent Q-learning In Random Networks (2025)0.00
• On The Stability Of Learning In Network Games With Many Players (2024)0.00
• Asymptotic Convergence And Performance Of Multi-agent Q-learning Dynamics (2023)0.00
• Stability Of Multi-agent Learning In Competitive Networks: Delaying The Onset Of Chaos (2023)0.00
• Convergence Of Heterogeneous Learning Dynamics In Zero-sum Stochastic Games (2023)2.26
• Multi-agent Reinforcement Learning In Cournot Games (2020)0.00