Source-linked AI summary
Maintaining cooperation in complex social dilemmas using deep reinforcement learning
Adam Lerer, Alexander Peysakhovich
TL;DR
The paper asks how to construct artificial agents that maintain cooperation in social dilemmas despite incentives to defect. It modifies self-play to build amTFT agents with cooperative and safe policies, and shows analytically and experimentally that they maintain cooperation in Markov social dilemmas. The approach extends to environments where competitive strategies can already be constructed, while its cooperative objective depends on selecting an appropriate focal point.
Problem
The paper addresses how artificial agents can achieve cooperative outcomes when individual incentives favor increasing personal payoffs at a cost to total welfare.
Method
The paper uses modified self-play to construct amTFT agents that combine cooperative and safe policies with value-based switching during a single Markov game.
Results
Analytical and experimental evidence shows that amTFT can maintain cooperation and avoid exploitation in Markov social dilemmas.
Takeaways & Limitations
The construction requires no training machinery beyond modified self-play and can be applied in environments where competitive agents can be constructed.
Abstract
from arXiv · showhide
Social dilemmas are situations where individuals face a temptation to increase their payoffs at a cost to total welfare. Building artificially intelligent agents that achieve good outcomes in these situations is important because many real world interactions include a tension between selfish interests and the welfare of others. We show how to modify modern reinforcement learning methods to construct agents that act in ways that are simple to understand, nice (begin by cooperating), provokable (try to avoid being exploited), and forgiving (try to return to mutual cooperation). We show both theoretically and experimentally that such agents can maintain cooperation in Markov social dilemmas. Our construction does not require training methods beyond a modification of self-play, thus if an environment is such that good strategies can be constructed in the zero-sum case (eg. Atari) then we can construct agents that solve social dilemmas in this environment.
1. Introduction
The paper asks how artificial agents can maintain cooperation in one-shot Markov social dilemmas requiring function approximation. It develops amTFT, which adapts tit-for-tat through modified self-play and value-based responses to support cooperation while avoiding exploitation.
- Method: amTFT is designed to satisfy tit-for-tat properties: cooperation, resistance to exploitation, and recovery toward mutual cooperation.The paper calls the strategy approximate Markov tit-for-tat because reinforcement-learning function approximation is used in Markov games.
- Problem: One-shot Markov social dilemmas require agents to cooperate with an unknown partner during a single test game.The setting differs from repeated-game approaches that use future rounds to threaten defection.
- Method: amTFT learns cooperative and safe policies through modified self-play, then switches between them during play.The switching rule tracks partners’ value-based gains relative to the cooperative policy as a per-period debit.
- Results: Analytical and experimental results show that amTFT is a good strategy for Markov social dilemmas.Experiments use grid-world, Coins, and a pixel-based Atari modification.
- Results: Defining defection by value rather than action makes amTFT robust to outcome-equivalent cooperative policies and function approximation.This design choice is identified as important for scaling beyond simple games.
- Scope: The cooperative policy is defined here as maximizing the sum of both players’ payoffs, but other settings may require a different focal point.The paper leaves automatic focal-point determination for future research while retaining the algorithmic construction once the objective is chosen.
2. The Basic Model
The basic model formalizes finite two-player Markov games, policies, value functions, best responses, cooperative policies, and social dilemmas. It also shows why memory and modified self-play are needed to maintain cooperation rather than converge to mutual defection.
- Markov game: A finite two-player Markov game specifies states, player actions, stochastic transitions, and bounded rewards.Policies map states to action distributions, while value and Q functions evaluate expected discounted rewards.
- Equilibrium concepts: A best response maximizes a player’s value against the other player’s policy from the relevant states.A perfect best response satisfies this condition from every state; mutual best responses form a Nash or Markov perfect equilibrium.
- Cooperation: Cooperative Markov policies maximize the sum of both players’ values from a state, with perfect cooperation requiring this property from every state.The cooperative-policy set is denoted by ΠC.
- Social dilemma: A social dilemma has no cooperative policies that are equilibria because a player can exploit a partner committed to cooperation.Some policies may still achieve cooperative payoffs along the realized trajectory while preventing exploitation through off-trajectory threats.
- Memory and learning: Memory is required when current observations do not reveal whether cooperation occurred previously.Adding memory does not eliminate always-defect equilibria, which can remain more robust attractors than cooperative equilibria.
- Memory and learning: Modified self-play explicitly constructs cooperative and cooperation-maintaining strategies because naive self-play may settle on always-defect equilibria.This motivates amTFT’s separate construction of policies and its switching rule.
3. Approximate Markov TFT
amTFT is a meta-policy that switches between cooperative and defensive policies in response to partner behavior, aiming to preserve cooperation while limiting exploitation. Under stated exchangeability and dominance assumptions, it cooperates from the cooperative phase and eventually returns to cooperation after punishment.
- Approximate Markov TFT: amTFT switches between cooperative and defensive policies to incentivize cooperation while responding to partner exploitation.The strategy begins cooperatively, measures deviations through value differences, and enters a defensive phase when the deviation exceeds the prescribed threshold.
- Assumptions: The construction assumes cooperative policies are exchangeable and that their combinations produce a unique distribution of total rewards.Without these assumptions, the problem also includes coordinating on how cooperation should occur and how gains should be divided.
- Limitations: When policies are not exchangeable or distribute cooperative gains differently, selecting a focal point becomes an additional coordination problem outside this work’s scope.The authors note that the appropriate focal point can depend on contextual factors.
- Assumptions: πD-dominance bounds a partner’s payoff during punishment and is sufficient, though not necessary, for the analysis.The authors define compound policies as following one policy for k turns and then another, which formalizes the defensive phase.
- Guarantees: If the partner cooperates according to the cooperative policy, an amTFT agent remains cooperative; after a defensive phase, it eventually returns to cooperation.The theorem states that, under the assumptions and without noise, cooperation persists from the cooperative phase and recovery occurs from the defensive phase.
- Guarantees: amTFT satisfies the targeted TFT properties: it is explainable, cooperates with pure cooperators, limits exploitation by pure defectors, and incentivizes cooperation.These properties describe the intended behavior of the meta-policy along the trajectory of play.
4. Constructing an amTFT Agent
The agent is constructed with reinforcement learning using selfish and cooperative self-play to learn defensive and cooperative components, then combines them with a debit-based switching rule. Rollouts estimate deviations and punishment lengths, while value-based detection preserves cooperation with outcome-equivalent partners.
- Training: Reinforcement learning uses selfish and cooperative reward schedules to approximate defensive and cooperative policies and their value functions.Selfish training treats the other agent as part of the environment, whereas cooperative training sums both players’ rewards.
- Training: Cooperative self-play is equivalent to one super-agent controlling both players and optimizing a single scalar reward, so standard RL convergence guarantees apply.The authors contrast this with possible convergence issues in selfish self-play.
- Switching policy: The amTFT agent tracks a partner’s accumulated debit and switches to a defensive phase when that balance crosses threshold T.The defensive duration is chosen so the partner’s loss relative to cooperation exceeds α times the current debit; T and α trade off robustness to error and noise.
- Debit estimation: Batched policy rollouts estimate the debit by comparing the partner’s reward on the observed deviation path with a counterfactual cooperative path.When the partner follows the cooperative action, the debit is zero; otherwise, 2B replicas are simulated for M turns and the average reward difference is used.
- Training: In the two Markov social dilemmas, standard self-play converges to defecting strategies, whereas modified self-play finds cooperative but exploitable strategies used to construct the agent.Figure 1 summarizes the two training outcomes underlying the construction of the cooperative and defensive components.
- Debit estimation: The rollout debit estimator is unbiased in the limit of large B and M but computationally intensive at test time.If actions affect payoffs for only M future periods, rollouts of length M suffice without a continuation value.
- Robustness: Value-based deviation detection continues cooperation when a partner uses an outcome-equivalent cooperative policy rather than the exact learned policy.Such deviations have estimated debit zero in expectation, a property the experiments identify as important in real Markov social dilemmas.
5. Experiments
Experiments evaluate amTFT against alternative strategies in Markov social dilemmas, showing that value-based partner assessment supports cooperation while avoiding exploitation. The evaluation also examines safety, self-cooperation, partner incentives, and learning from cooperative teachers.
- Training outcomes: In the Pong Player’s Dilemma, selfishly trained agents compete to score, while prosocially trained agents gently hit the ball back and forth.Both environments use deep neural networks for state representation, including raw pixels in the Pong setup.
- Evaluation design: The experiments compare cooperative, defective, and amTFT policies through fixed-length matchups using 1000 replicates per strategy pair.The evaluation measures whether strategies avoid exploitation, cooperate conditionally, and incentivize partner cooperation.
- Strategy evaluation: amTFT avoids exploitation by defectors, performs well against itself, and incentivizes cooperative behavior from its partner.These properties correspond to safety, self-match, and partner-incentive measures.
- Strategy evaluation: Value-based inference of partner cooperation is more stable than action-based inference, which makes Grim interpret any deviation as defection.Grim therefore behaves almost identically to pure defection in the evaluated dilemmas.
6. amTFT As Teacher
The teacher experiments test whether amTFT can shape the behavior of a selfish deep RL learner. Unlike purely cooperative or selfish teachers, amTFT leads learners toward cooperation and gives both agents higher long-run payoffs.
- Experimental design: The teacher retraining experiment uses Coins and treats learner retraining as an additional test of whether a strategy can be cheated.The authors attempted the procedure in the Pong Player’s Dilemma but report a limitation in that setting.
- Teacher effects: Learners paired with amTFT learn to cooperate, whereas learners paired with purely cooperative or defective teachers learn exploitative strategies.Purely cooperative teachers are exploited, while learners paired with πD also learn to exploit, more slowly.
- Teacher effects: Choosing amTFT gives both the Learner and Teacher higher payoffs than a purely greedy strategy.This makes amTFT advantageous even when evaluating only the focal agent’s payoff.
7. Conclusion
The paper shows that amTFT can maintain cooperation and avoid exploitation in Markov games using a construction requiring no more than modified self-play. It also identifies limits for human interaction and cooperative-agent design.
- amTFT can maintain cooperation and avoid exploitation in Markov games.
- The strategy uses a simple construction requiring no more than modified self-play.
- The construction can be applied to social dilemmas in many environments.
- Cooperation via a shift to πD requires a low discount rate, while A3C was unstable in this regime.
- For human interaction, defining cooperation as joint-payoff maximization may be inappropriate, requiring agents to understand and adapt to human cooperative and moral intuitions.
8. Appendix
The appendix explains why standard self-play fails to discover cooperation-maintaining strategies and outlines the assumptions and proof structure supporting amTFT’s incentives. It also describes practical challenges in estimating the quantities needed to implement the strategy.
- 8.1. Standard Self-Play Fails to Discover Cooperative Strategies in the Repeated PD: Standard self-play can converge to mutual defection because simple defection equilibria may have larger attraction basins than cooperative policies.
- 8.1. Standard Self-Play Fails to Discover Cooperative Strategies in the Repeated PD: The repeated Prisoner’s Dilemma experiment uses one-memory policies trained with policy gradient and REINFORCE across varying temptation payoffs.
- 8.1. Standard Self-Play Fails to Discover Cooperative Strategies in the Repeated PD: Figure 4 finds that cooperation robustly occurs only when it is dominant for both players, so the game is no longer a social dilemma.
- 8.2. Proof of Main Theorem: The proof treats the partner’s behavior as a Markov game with state representation (s, k), where k indicates the cooperation or defection phase.
- 8.2. Proof of Main Theorem: The one-deviation principle establishes optimality by ruling out profitable one-shot deviations in both the defection and cooperation phases.
- 8.3. Computing Debit: Implementing the strategy may require estimating best responses or value functions, and accurate Q models are difficult because bias accumulates and cooperative data omit off-path actions.