Research map / Multi-agent systems and games / Games and equilibria
Self-Play $Q$-Learners Can Provably Collude in the Iterated Prisoner's Dilemma
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Theoretically shows that self-play epsilon-greedy Q-learners with one-step memory in the iterated prisoner's dilemma can move from always-defect to the cooperative Pavlov policy, with proofs for greedy and epsilon-greedy cases plus deep Q-learning experiments.
Problem
Understanding why simple multi-agent Q-learners converge to cooperative (collusive) behavior in social dilemmas such as the iterated prisoner's dilemma; prior theory used memoryless averaged dynamics that cannot represent retaliatory equilibria.
Approach
Analyzes the stochastic (non-averaged) self-play epsilon-greedy Q-learning with one-step memory and shows, under optimistic Q-initialization and small step size, that the dynamics provably transition from always-defect through lose-shift to the subgame-perfect Pavlov cooperative policy.
Key results
- With epsilon=0 and optimistic initialization satisfying the stated assumptions, Q-learners move from always-defect through lose-shift to Pavlov, with linear convergence in each phase and O(1/alpha) transition times.
- In tabular experiments (gamma=0.6, g=1.8, 100 runs, 2000 iterations), cooperation probability rises for smaller epsilon and alpha, and fails at epsilon=0.2 where Pavlov is no longer a stable fixed point.
- Deep Q-network agents initialized against a random agent and then trained by self-play with decaying epsilon from 1/2 to 1e-2 converge to the Pavlov policy around iteration 6000.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use optimistic Q-value initialization with no exploration (ε=0), starting from always defect | Self-play Q-learning · Iterated Prisoner's Dilemma | convergence to cooperative policy | Helped |
| Use sufficiently small exploration ε and step size α | Self-play ε-greedy Q-learning · Iterated Prisoner's Dilemma | probability of learning a cooperative strategy | Helped |
| Increase exploration to ε=0.2 | Self-play ε-greedy Q-learning · Iterated Prisoner's Dilemma | cooperation | Hurt |
| Extend from tabular Q-learning to deep Q-learning, initializing against a random agent and then using self-play | Deep Q-learning · Iterated Prisoner's Dilemma | cooperative policy convergence | Helped |
| Increase the exploration parameter ε | Self-play ε-greedy Q-learning · Iterated Prisoner's Dilemma | cooperation | Hurt |
Surprising findings
- Pavlov cooperation emerges even when both agents start from an always-defect policy, without relying on memoryless limitations.
- Relaxing the self-play assumption still yields cooperation most of the time, per cited empirical work.
Limitations
- Analysis depends on self-play; relaxing it would require analyzing stationary distributions, which is harder.
- Requires optimistic initialization and sufficiently small epsilon and alpha; Pavlov fixed-point condition fails for large epsilon.
- Only one-step memory and simplified symmetric rewards are analyzed; policy gradient and Bertrand games left to future work.
Experimental setup
Benchmarks: iterated prisoner's dilemma simulations
Metrics: probability of cooperation fraction of runs reaching Pavlov
Baselines: memoryless Q-learning dynamics (Calvano-style averaged ODE analysis)
Builds on: Q-learning self-play Pavlov (win-stay, lose-shift) deep Q-learning
Closest papers by meaning
- Mitigating Retaliatory Algorithmic Collusion in Repeated Games (NeurIPS 2026 · similarity 0.89)
- Domination-Avoiding Learning Agents Cannot Collude (NeurIPS 2026 · similarity 0.89)
- Multi-agent cooperation through learning-aware policy gradients (ICLR 2025 · similarity 0.89)
- LOQA: Learning with Opponent Q-Learning Awareness (ICLR 2024 · similarity 0.88)
- Reciprocal Reward Influence Encourages Cooperation From Self-Interested Agents (NeurIPS 2024 · similarity 0.88)
- Multi-Agent Learning under Uncertainty: Recurrence vs. Concentration (NeurIPS 2025 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.