PaperlayerView exact revision on arXiv

Source-linked AI summary

Stable Opponent Shaping in Differentiable Games

Alistair Letcher, Jakob Foerster, David Balduzzi, Tim Rocktäschel, Shimon Whiteson

arXiv:1811.08469v3cs.MAcs.AIcs.LG

TL;DR

Learning in differentiable games lacks convergence guarantees across the general class, while opponent shaping can improve learning but LOLA may fail to preserve fixed points. The paper proposes SOS, interpolating between LookAhead and LOLA; it reports strong theoretical guarantees and experimental outcomes that match or exceed LOLA in the tested settings.

  • Problem

    No algorithm had been shown to converge even locally across all differentiable games, where players’ losses depend on one another’s parameters.

    Source: §1 · p. 1

  • Method

    SOS interpolates between LookAhead and LOLA to combine LookAhead’s stability with LOLA’s opponent shaping.

    Source: §4.2 · p. 6, §6 · p. 9

  • Results

    SOS matches LOLA’s tit-for-tat behavior in the IPD, outperforms it in the tandem game, and achieves convincing Gaussian-mixture results, slightly exceeding others on KL divergence.

    Source: §5.2 · pp. 7–8, §6 · p. 9

  • Takeaways & Limitations

    In the reported experiments, SOS retains opponent shaping while improving on LOLA in the tandem game and matching or exceeding comparison methods in other settings.

    Source: §5.2 · pp. 7–8, §6 · p. 9

    Convergence results assume the game Jacobian is invertible at stable fixed points; extending to global initializations is harder for SOS because p(θ) is not globally continuous.

    Source: §2.2 · p. 3, §4.2 · p. 6

Abstract

from arXiv · show

A growing number of learning methods are actually differentiable games whose players optimise multiple, interdependent objectives in parallel -- from GANs and intrinsic curiosity to multi-agent RL. Opponent shaping is a powerful approach to improve learning dynamics in these games, accounting for player influence on others' updates. Learning with Opponent-Learning Awareness (LOLA) is a recent algorithm that exploits this response and leads to cooperation in settings like the Iterated Prisoner's Dilemma. Although experimentally successful, we show that LOLA agents can exhibit 'arrogant' behaviour directly at odds with convergence. In fact, remarkably few algorithms have theoretical guarantees applying across all (n-player, non-convex) games. In this paper we present Stable Opponent Shaping (SOS), a new method that interpolates between LOLA and a stable variant named LookAhead. We prove that LookAhead converges locally to equilibria and avoids strict saddles in all differentiable games. SOS inherits these essential guarantees, while also shaping the learning of opponents and consistently either matching or outperforming LOLA experimentally.

1 INTRODUCTION

Differentiable games capture learning systems with multiple interdependent objectives, but simultaneous learning lacks convergence guarantees across the general class. The paper introduces SOS to combine LookAhead’s stability with LOLA’s opponent shaping, and reports strong results across several experiments.

1 INTRODUCTION

  • No algorithm had been shown to converge even locally across all differentiable games, despite the growing use of interacting objectives in systems such as GANs and multi-agent RL.Simultaneous gradient descent can fail even in a simple two-player, two-parameter zero-sum game.Source: §1 · p. 1
  • LOLA (Foerster et al., 2018) can encourage cooperation but has no guarantee of convergence or fixed-point preservation.The paper identifies a tandem-game failure in which LOLA agents exhibit arrogant behavior and converge to non-fixed points.Source: §1 · p. 2
  • SOS interpolates between LookAhead and LOLA, using a criterion to retain LookAhead’s convergence guarantees while shaping opponents’ learning.The method is designed to combine stability with opponent shaping.Source: §1 · p. 2
  • SOS matches LOLA’s tit-for-tat behavior in the IPD, outperforms LOLA in the tandem game, and spreads mass across Gaussian-mixture modes at least as well as dedicated methods.In the Gaussian-mixture experiment, LookAhead is significantly slower and simultaneous gradient descent fails.Source: §1 · p. 2

2 BACKGROUND

The background formalizes differentiable games and stable fixed points, then explains how LOLA shapes opponents’ learning and why that can break fixed-point preservation. Its tandem-game example illustrates the resulting failure.

2.1 DIFFERENTIABLE GAMES

  • In a differentiable game, each player’s loss depends on all players’ parameters; simultaneous gradient descent can diverge even when the origin is a Nash equilibrium.For the two-player zero-sum example, the gradient field cycles and every positive learning rate moves away from the origin.Source: §2.1 · pp. 2–3

2.2 STABLE FIXED POINTS

  • A Nash equilibrium can be an undesirable target: in the game where both losses are xy, the origin is a Nash equilibrium and saddle, despite arbitrarily better losses along the anti-diagonal.The paper motivates stable fixed points as a more tractable target closer to local minima in multi-loss optimization.Source: §2.2 · p. 3
  • Stable fixed points are defined through the game’s generally nonsymmetric gradient Jacobian, with stability classified by the Jacobian’s eigenvalues.The paper assumes the Jacobian is invertible at stable fixed points for its convergence results.Source: §2.2 · p. 3

2.3 LEARNING WITH OPPONENT-LEARNING AWARENESS (LOLA)

  • LOLA predicts an opponent’s learning step and differentiates through it, aligning that step with a direction that reduces its own loss and thereby shaping opponent learning.The paper retains a middle term omitted in the original LOLA formulation as part of its approach to stable opponent shaping.Source: §2.3 · p. 4
  • LOLA’s shaping term can move agents away from game fixed points; in the tandem game, none of the stable fixed points is preserved, and LOLA converges only to sub-optimal outcomes with worse losses for both agents.The authors describe the failure as agents pushing strongly in opposite directions while assuming a dynamic response from one another.Source: §2.3 · p. 4

3 METHOD

LookAhead removes LOLA’s differentiable shaping term by treating the opponent’s predicted update as fixed during differentiation. SOS restores opponent shaping through an interpolation whose criteria are designed to retain stability.

3.1 LOOKAHEAD

  • LookAhead removes the shaping term by treating the opponent’s predicted update as independent of the current parameter during differentiation, yielding the update variant (I − αH_o)ξ.This preserves fixed points and avoids assuming an opponent can observe updated parameters before the next step.Source: §3.1 · pp. 4–5
  • LookAhead is proved to converge locally to stable fixed points and not to converge to strict saddles in all differentiable games, but it loses LOLA’s opponent-shaping capacity.Earlier, Zhang & Lesser (2010) established convergence only for two-player, two-action bimatrix games.Source: §3.1 · p. 5

3.2 STABLE OPPONENT SHAPING (SOS)

  • SOS defines a partial stop-gradient interpolation between LookAhead and LOLA, with p = 0 yielding LookAhead and p = 1 yielding LOLA.The method chooses p at each learning step rather than relying on an infinitesimal interpolation parameter.Source: §3.2 · p. 5
  • SOS selects p to keep its update aligned with LookAhead and scales p near fixed points to support local convergence; its theoretical results do not depend on hyperparameters a and b.The alignment criterion limits shaping when it would point against LookAhead, while the second criterion reduces p when the gradient norm is small.Source: §3.2 · p. 5

4 THEORETICAL RESULTS

LookAhead and SOS have local convergence guarantees across differentiable games, and SOS also preserves fixed points and locally avoids strict saddles. These results assume thrice continuously differentiable losses and, for SOS, hold for any a,b in (0,1).

4 THEORETICAL RESULTS

  • LookAhead and SOS converge locally to stable fixed points and avoid strict saddles across differentiable games, assuming thrice continuously differentiable losses.The SOS guarantees hold for any a,b in (0,1).Source: §4 · p. 5

4.1 LOCAL CONVERGENCE TO STABLE FIXED POINTS

  • LookAhead converges locally to stable fixed points for sufficiently small positive learning rates.The proof uses Ostrowski’s Theorem to reduce convergence to positive stability of the gradient adjustment near stable fixed points.Source: §4.1 · p. 6
  • SOS converges locally to stable fixed points for sufficiently small positive learning rates, despite retaining a shaping term.Source: §4.1 · p. 6

4.2 AVOIDING STRICT SADDLES

  • For sufficiently small positive learning rates, SOS converges only to game fixed points and almost surely avoids strict saddles under random or arbitrarily small-noise initialization.Source: §4.2 · p. 6
  • Global-initialization guarantees for LookAhead require a strong boundedness assumption on ∥H∥2; extending them to SOS is harder because p(θ) is not globally continuous.Unlike LookAhead, SOS retains LOLA’s opponent-shaping capacity.Source: §4.2 · p. 6

5 EXPERIMENTS AND DISCUSSION

Across the experiments, SOS matches LOLA’s cooperation in the IPD, outperforms it in the tandem game, and achieves results similar to dedicated methods in a Gaussian-mixture GAN task.

5.1 EXPERIMENTAL SETUP

  • Experiments cover the IPD, tandem game, and Gaussian-mixture GAN; SOS uses a=0.5 and b=0.1 in the IPD and GAN, and a=b=0.5 in the tandem game.Source: §5 · p. 6, §5.1 · pp. 6–7

5.2 RESULTS AND DISCUSSION

  • In the IPD, SOS and LOLA mostly play tit-for-tat with nearly identical trained parameters and losses, while LA, CO, SGA, and NL mostly defect.Source: Figure 2 · p. 7, §5.2 · p. 7
  • SOS averages loss 0 in the tandem game versus LOLA’s 4/9, decaying p to avoid overshooting.Source: §5.2 · p. 7, Figure 3 · p. 8
  • For Gaussian-mixture GANs, SOS and CO learn the mixture and are slightly superior by KL divergence, while NL collapses or hops between modes and LookAhead is slower.The reported KL divergence is estimated from 25,600 samples.Source: Figure 4 · p. 8, §5.2 · p. 8

6 CONCLUSION

The paper addresses the lack of general convergence guarantees for learning in differentiable games, establishing robust convergence results for LookAhead. SOS combines that stability with opponent shaping and performs strongly in the reported experiments.

6 CONCLUSION

  • LookAhead provides robust convergence results in all differentiable games, with stable fixed points as the relevant solution concept.The paper presents a unified framework to establish these results.Source: §6 · p. 9
  • SOS interpolates between LookAhead and LOLA, retaining opponent shaping while inheriting stability and convergence guarantees.The paper attributes this to a robust interpolation criterion and preserving LOLA’s middle term.Source: §6 · p. 9
  • SOS is practically superior to LOLA in the tandem game, outperforms SGA, CO, LA, and NL in the IPD, and learns Gaussian mixtures on par with CO.In the IPD, SOS encourages tit-for-tat rather than defecting.Source: §6 · p. 9

A STABLE FIXED POINTS

Stable fixed points are used as a tractable solution concept for multi-agent learning, where Nash equilibria can coincide with saddle points. The supplied passages do not provide a complete claim about the LOLA vectorial-form subsection.

A STABLE FIXED POINTS

  • The origin can be a global Nash equilibrium yet a saddle point of the agents’ losses, making Nash equilibria inadequate as a solution concept here.The example uses L1 = L2 = xy.Source: A STABLE FIXED POINTS · p. 11
  • Stable fixed points generalize fixed points with positive semi-definite Hessian and correspond to second-order-tractable local minima.The definition retains positive semi-definiteness to keep the class as large as possible.Source: A STABLE FIXED POINTS · p. 11
  • Positive semi-definiteness is a minimal requirement for gradient-descent-like convergence guarantees, since strict saddles need not be locally convergent.The passage notes that strict saddles are almost always avoided by gradient descent.Source: A STABLE FIXED POINTS · p. 11

C TANDEM GAME

The tandem game pits a coordination objective against agents’ individual preferences to move forward. In this setting, LOLA fails to preserve the stable fixed points and can converge only to outcomes with worse losses.

C TANDEM GAME

  • The agents’ objectives conflict: coordinating requires x ≈ −y, while each also prefers positive x and y.The quadratic term (x + y)^2 favors coordination, while the linear terms favor positive values.Source: C TANDEM GAME · p. 12
  • The fixed points are pairs (x, 1 − x), and their losses sum to zero.At these points, L1 = 1 − 2x = −L2.Source: C TANDEM GAME · p. 12
  • LOLA fails to preserve the tandem game’s fixed points and can converge only to points with worse losses.The passage states the relevant LOLA fixed-point condition is nonzero at every stable fixed point.Source: C TANDEM GAME · pp. 12–13
  • Reducing α makes the positive sum of LOLA’s losses negligible, but convergence then becomes arbitrarily slow.The passage says taking α arbitrarily small is not a viable solution.Source: C TANDEM GAME · p. 13

D CONVERGENCE PROOFS

The convergence proofs use fixed-point iteration theory to establish local convergence of LookAhead and SOS to stable fixed points. For LookAhead, the key step proves positive stability; SOS uses a criterion that is smooth near fixed points.

D CONVERGENCE PROOFS

  • Ostrowski’s theorem gives local convergence when the iteration’s Jacobian has eigenvalues strictly inside the unit circle.The theorem also gives at least linear convergence.Source: D CONVERGENCE PROOFS · p. 13
  • A similarity transformation proves positive stability even though (I − αHo)H need not be positive definite.The transformation enables analysis with respect to a different inner product.Source: D CONVERGENCE PROOFS · p. 14
  • LookAhead is shown to converge locally to stable fixed points for sufficiently small positive α.The proof establishes positive stability of (I − αHo)H under the stated Hessian conditions.Source: D CONVERGENCE PROOFS · pp. 13, 15
  • The SOS criterion satisfies p = ∥ξ∥² in a neighborhood of a fixed point for sufficiently small α, making it continuously differentiable there.The criterion is not claimed to be continuously differentiable globally.Source: D CONVERGENCE PROOFS · p. 15
  • SOS converges locally to stable fixed points for sufficiently small positive α.Near a stable fixed point, the relevant derivative is identical to LookAhead’s.Source: D CONVERGENCE PROOFS · p. 16

E NON-CONVERGENCE PROOFS

The appendix establishes that convergent SOS iterates are fixed points for sufficiently small step sizes, and that random initialization almost surely avoids strict saddles locally.

E NON-CONVERGENCE PROOFS

  • If SOS converges to a point and α is small, that point is a fixed point of the game.The proof takes limits in the iteration and establishes the fixed-point condition.Source: E NON-CONVERGENCE PROOFS · pp. 17–18
  • SOS locally avoids strict saddles almost surely when α > 0 is sufficiently small.The proof uses the Stable Manifold Theorem to show that the local stable set has measure zero.Source: E NON-CONVERGENCE PROOFS · p. 18
  • For sufficiently small α, the SOS update is locally invertible near a strict saddle, whose unstable direction makes its local stable set measure zero.The proof obtains an eigenvalue with magnitude greater than one, so the stable manifold has codimension at least one.Source: E NON-CONVERGENCE PROOFS · p. 18

F FURTHER GAUSSIAN MIXTURE EXPERIMENTS

In Gaussian-mixture GAN experiments, SOS reaches a strong match to the target distribution and remains stable, while LookAhead is slower and other methods show distinct failures or delays.

F FURTHER GAUSSIAN MIXTURE EXPERIMENTS

Related papers

Loading 1811.08469v3…