PaperlayerView exact revision on arXiv

Source-linked AI summary

Learning with Opponent-Learning Awareness

Jakob N. Foerster, Richard Y. Chen, Maruan Al-Shedivat, Shimon Whiteson, Pieter Abbeel, Igor Mordatch

arXiv:1709.04326v4cs.AIcs.GT

TL;DR

Multi-agent learning is difficult in partially cooperative environments because independent learners ignore how other agents’ updates change the training dynamics. LOLA differentiates through opponents’ anticipated learning steps, producing cooperation in IPD and Coin Game settings while retaining broader multi-agent performance.

  • Problem

    Independent multi-agent learners can fail to cooperate because they treat other agents as static parts of a non-stationary environment.

  • Method

    LOLA augments each agent’s update with a term capturing how its policy affects opponents’ anticipated parameter updates.

  • Results

    LOLA produces cooperation and reciprocity in IPD, stable Nash-equilibrium learning in IMP, high average IPD returns, and cooperation in Coin Game experiments.

  • Takeaways & Limitations

    Considering opponents’ learning processes enables self-interested agents to learn cooperation across exact-value, policy-gradient, recurrent-policy, and opponent-modelling settings.

  • Takeaways & Limitations

    Opponent modelling is less reliable than LOLA-PG because parameter non-identifiability introduces noise, increasing gradient variance and bias.

Abstract

from arXiv · show

Multi-agent settings are quickly gathering importance in machine learning. This includes a plethora of recent work on deep multi-agent reinforcement learning, but also can be extended to hierarchical RL, generative adversarial networks and decentralised optimisation. In all these settings the presence of multiple learning agents renders the training problem non-stationary and often leads to unstable training or undesired final results. We present Learning with Opponent-Learning Awareness (LOLA), a method in which each agent shapes the anticipated learning of the other agents in the environment. The LOLA learning rule includes a term that accounts for the impact of one agent's policy on the anticipated parameter update of the other agents. Results show that the encounter of two LOLA agents leads to the emergence of tit-for-tat and therefore cooperation in the iterated prisoners' dilemma, while independent learning does not. In this domain, LOLA also receives higher payouts compared to a naive learner, and is robust against exploitation by higher order gradient-based methods. Applied to repeated matching pennies, LOLA agents converge to the Nash equilibrium. In a round robin tournament we show that LOLA agents successfully shape the learning of a range of multi-agent learning algorithms from literature, resulting in the highest average returns on the IPD. We also show that the LOLA update rule can be efficiently calculated using an extension of the policy gradient estimator, making the method suitable for model-free RL. The method thus scales to large parameter and input spaces and nonlinear function approximators. We apply LOLA to a grid world task with an embedded social dilemma using recurrent policies and opponent modelling. By explicitly considering the learning of the other agent, LOLA agents learn to cooperate out of self-interest. The code is at github.com/alshedivat/lola.

1 INTRODUCTION

Multi-agent RL must address partially cooperative settings where agents learn alongside competitors, since independent learning can fail to produce reciprocity. LOLA accounts for opponents’ learning updates and yields cooperation across several evaluated settings.

  • Partially cooperative applications such as self-driving cars combine interaction, competition, and conflict, unlike much fully cooperative multi-agent RL research.
  • Reciprocity among self-interested reward-maximizing agents is both theoretically interesting and practically important because IPD defection can reduce rewards for everyone.
  • Independent gradient descent agents in the infinitely repeated prisoners’ dilemma defect with high probability, failing to cooperate reliably even in this simple social setting.
  • LOLA adds a term accounting for how one agent’s policy affects another agent’s learning step, thereby reasoning over opponents’ learning behavior.
  • When both agents use LOLA, cooperation and emergent reciprocity arise in IPD; LOLA also achieves the highest average IPD return in a round-robin tournament.
  • Policy-gradient LOLA scales to high-dimensional inputs and parameters, and cooperation also emerges in a recurrent-policy grid-world task with opponent modelling.

2 RELATED WORK

Prior work studies cooperation, convergence, opponent prediction, or fixed learning dynamics, but does not generally shape opponents’ learning. LOLA differentiates through those updates to promote reciprocity in general-sum settings.

  • Tit-for-tat is an effective strategy in IPD that cooperates initially and then copies the opponent’s most recent move.
  • Convergence-oriented algorithms such as WoLF, JAL, and AWESOME have understood behavior under constraints but cannot shape opponents’ learning to obtain higher payouts.
  • Many prior methods encode reciprocity and cooperation through heuristics, limiting their generality rather than making these behaviors emergent from learning.
  • Opponent-modelling methods predict strategies or distributions and use look-ahead for best responses, but do not address opponents’ learning dynamics.
  • LOLA directly shapes opponents’ policy updates by differentiating through their learning steps, which the paper identifies as crucial for tit-for-tat and reciprocity.
  • Unlike related differentiable opponent-training methods for GANs, LOLA is designed for the general reinforcement-learning setting rather than requiring an end-to-end differentiable loss.

3 NOTATION

The paper models multi-agent tasks as stochastic games in which agents choose actions, induce state transitions, and receive discounted rewards. Naive learning separately maximizes each agent’s expected return using policy-gradient methods.

  • A stochastic game is specified by G = ⟨S,U,P,r,Z,O,n,γ⟩, with agents choosing actions in environment states.
  • The joint action determines state transitions through P(s′|s,u), while each agent’s reward function maps states and joint actions to real-valued rewards.
  • Each agent’s discounted future return is defined from time t onward, and naive learning separately maximizes its expected total discounted reward.
  • Policy-gradient methods update policy parameters θ_a through gradient ascent on an estimate of expected discounted total reward.

4 METHODS

LOLA extends naive learning by optimizing against a one-step look-ahead of opponent learning, with exact-gradient and policy-gradient formulations plus opponent modelling. Experiments show cooperation in the IPD, Nash convergence in IMP, and higher-order extensions that require third-order derivatives.

  • Naive Learner: Naive learning optimizes each agent’s own expected discounted return using local function values and gradients, treating the opponent’s policy as part of the environment.The exact-gradient formulation uses policy parameters and expected returns as functions of both agents’ parameters, while the policy-gradient formulation estimates derivatives from sampled episodes.
  • Learning with Opponent Learning Awareness: LOLA optimizes an agent’s return after a one-step opponent update, differentiating through that anticipated update to shape the opponent’s future learning direction.A first-order Taylor expansion produces a correction involving the opponent’s update and the gradient of the agent’s return with respect to the opponent’s parameters.
  • Learning with Opponent Learning Awareness: The LOLA learning rule includes a second-order correction term, with separate step sizes for first- and second-order updates.Exact LOLA and naive learners can access gradients and Hessians of the agents’ expected returns at the current policy parameters.
  • Experiments: In the IPD, naive learners defect in all states, whereas LOLA-Ex agents usually learn tit-for-tat; in IMP, LOLA converges to the 50%/50% Nash equilibrium while naive strategies fail to converge.Policy-gradient results are described as qualitatively similar for the IPD, and the IMP LOLA result contrasts with near-deterministic, unstable naive strategies.
  • Learning via Policy Gradient: Policy-gradient LOLA estimates the second-order correction from independently sampled actions, and the estimator is exact in expectation.The policy-gradient naive learner uses a baseline for variance reduction, while the complete LOLA-PG update incorporates the estimated correction.
  • Opponent Modelling: Opponent modelling replaces inaccessible opponent parameters with estimates fitted from recent action-observation data to address opponent non-stationarity.The estimated parameters substitute for the opponent’s true parameters in both exact and policy-gradient LOLA updates.
  • Higher-Order LOLA: Higher-order LOLA models an opponent using first-order LOLA rather than naive learning, producing third-order derivatives that are difficult to estimate with policy gradients.The exact-value-function setting makes these higher-order terms tractable, and the benefits are examined experimentally.

5 EXPERIMENTAL SETUP

The experiments compare naive learning (NL) and LOLA in iterated games and the sequential Coin Game, using exact or policy-gradient updates and recurrent policies where needed.

  • Experimental environments: The study evaluates NL and LOLA in the iterated prisoners’ dilemma (IPD), iterated matching pennies (IMP), and the more complex sequential Coin Game.The iterated games use exact policy updates derived from analytical discounted returns, while Coin Game requires policy-gradient learning.
  • Iterated games: Agents in the iterated games condition actions on the previous K rounds, with the experiments focusing on memory-1 policies.Each IPD policy is specified by five cooperation probabilities: one at game start and four for the possible previous joint actions.
  • Evaluation: Table 3 reports TFT or Nash probabilities, average reward per step, and standard deviation after 50 training runs for exact and policy-gradient settings.The comparisons include NL versus NL and LOLA versus LOLA in both iterated environments.
  • Coin Game: In Coin Game, agents receive 1 point for any coin, but collecting the other agent’s coin costs that agent 2 points, creating an embedded social dilemma.Greedy collection of any available coin yields 0 points in expectation, and the sequential policies are recurrent neural networks.
  • Coin Game: Coin Game uses recurrent policies with 32 hidden units and two convolutional layers processing a four-channel grid representation.The channels encode both agent positions and the red and blue coin positions.

6 RESULTS

Across iterated games, tournaments, and the Coin Game, LOLA generally promotes cooperation or stable equilibrium behavior and outperforms or matches relevant learning baselines. Opponent modelling extends LOLA to unknown policies but is less stable and performs worse than direct policy access.

  • Iterated Games: LOLA-Ex agents usually learn tit-for-tat in the IPD, whereas NL-Ex agents learn full defection.LOLA-Ex achieves a normalised discounted reward close to −1, compared with −2 for NL-Ex.
  • Iterated Games: In IMP, LOLA policies converge to the only Nash equilibrium, while naive agents fail to converge.The equilibrium corresponds to playing 50%/50% heads/tails.
  • Iterated Games: In the IPD, LOLA achieves higher normalised discounted rewards than NL agents (−1.06 vs −1.98), while IMP return variance is lower under LOLA (0.02 vs 0.37).The comparison covers both exact and policy-gradient settings.
  • Round-Robin Tournament: LOLA-Ex obtains the highest normalised return in the IPD round-robin tournament and stable performance near the middle of the IMP results distribution.The tournament compares LOLA-Ex with several multi-agent learning algorithms from the literature.
  • Coin Game: In the Coin Game, LOLA-PG agents collect around 80% own-colour coins, whereas opponent-modelling LOLA agents collect around 60% and are less stable.LOLA-OM also obtains lower returns than LOLA-PG, attributed to noise in inferred opponent parameters.
  • Exploitability of LOLA: Higher-order LOLA provides no incremental exploitative gain against LOLA-Ex and reduces payouts for both agents.The higher-order comparison includes second-order LOLA with third-order corrections.

7 CONCLUSIONS & FUTURE WORK

LOLA accounts for other agents’ learning processes and produces cooperation in the iterated prisoners’ dilemma, stable Nash-equilibrium learning in matching pennies, and strong tournament performance. Its policy-gradient version extends these behaviors to deep recurrent settings, while exploitability remains an open concern.

  • Exact LOLA agents achieve the highest average returns on the IPD and respectable performance on IMP in a round-robin tournament.
  • LOLA produces tit-for-tat cooperation in the infinitely repeated IPD, whereas independent naive learners defect.
  • LOLA agents learn to cooperate in the Coin Game, while naive learners collect coins indiscriminately; opponent modeling also supports cooperation, though less reliably.
  • Higher-order gradient-based exploits show no further gain against LOLA in the IPD, but global-search exploitation remains future work.

Supplementary Material

The supplementary material is identified as version 4 of arXiv paper 1709.04326, dated 19 September 2018.

  • The supplementary material belongs to arXiv paper 1709.04326.
  • The document is version 4.
  • The document date is 19 September 2018.

A.1 Derivation of Second-Order derivative

The appendix derives LOLA’s second-order policy-gradient terms for finite-horizon episodes. It defines discounted returns and uses expectation-based policy-gradient manipulations to express cross-agent learning effects.

  • The derivation considers an episode with horizon T and derives LOLA’s second-order derivatives in the policy-gradient setting.
  • Discounted returns for each agent are defined at timestep t, with expectations taken over both policies and the episode trajectory.
  • The derivation obtains a second-order cross-term gradient for a reward of agent 1 and sums these rewards over timesteps.

A.2 Derivation of the exact value function in the Iterated Prisoners’ dilemma and Iterated Matching Pennies

The appendix represents IPD and IMP as five-state, two-action Markov games whose joint policies induce state transitions, enabling exact value-function calculations. Figures compare exact-gradient and policy-gradient behavior for cooperation, matching pennies, and returns.

  • Both games use two discrete actions and five states: one initial state plus four states determined by the agents’ previous actions.
  • Each policy uses five parameters representing the probability of action 0 in each state; in IPD, these encode cooperation probabilities across s0, CC, CD, DC, and DD.
  • The joint policies induce a state-transition function P(s′|s), while p0 denotes the initial-state distribution.
  • Because γ < 1 and P is stochastic, the infinite value-function sum converges; the figures compare exact and policy-gradient estimates for IPD and IMP behavior.
Loading 1709.04326v4…