Stable Opponent Shaping in Differentiable Games

By Alistair Letcher, Jakob N. Foerster, David Balduzzi, Tim Rocktaschel, Shimon Whiteson. 2018

129 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Management Science and Operations Research

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Management Science and Operations Research

Citations in the corpus

Towards Continual Reinforcement Learning: A Review and Perspectives (2020, background): “Moreover, agents can learn to shape the learning of other agents and thus the nature of the non-stationarity in their environment (Kim et al., 2022; Foerster et al., 2018a,1; Kim et al., 2021a; Letcher et al., 2019; Zhang and Lesser, 2010).”
From Poincaré Recurrence to Convergence in Imperfect Information Games: Finding Equilibrium via Regularization (2020, background): “This problem can be resolved by introducing second-order optimization (Balduzzi et al., 2018; Foerster et al., 2017; Mescheder et al., 2017; Letcher et al., 2019), negative momentum (Gidel et al., 2019) or game theoretic algorithms (Oliehoek et al., 2017; Grnarova et al., 2018).”
Multi-agent deep reinforcement learning: a survey (2021, background): “2017), in social dilemmas (Jaques et al. 2019; Letcher et al. 2019), and by predicting behaviors from observations (Hong et al.”
Differentiable Game Mechanics (2019, background): “The deﬁnition is adapted from Letcher et al. (2019), where conditions on the Jacobian hold at the ﬁxed point; in contrast, Balduzzi et al. (2018a) imposed conditions on the Jacobian in a neighborhood of the ﬁxed point.”
Influencing Long-Term Behavior in Multiagent Reinforcement Learning (2022, unknown): “Notably, LOLA [6] and its more recent improvements [7, 43] study the impact of behavior on one or a few of another agent’s policy updates.”
Optimizing Millions of Hyperparameters by Implicit Differentiation (2019, background): “Examples of this include GANs [39], and other multi-agent games [63, 64].”
A Policy Gradient Algorithm for Learning to Learn in Multiagent Reinforcement Learning (2020, background): “For example, consider a stateless zero-sum game played be-tween two agents based off the one shown by Letcher et al. (2019).”
Convergence of Learning Dynamics in Stackelberg Games (2019, background): “There has also been a shift toward analyzing gradient-based learning rules and convergence analysis [3, 15, 24, 28, 43].”