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. Problem Setting. While machine learning has traditionally focused on optimising single objectives, generative adversarial nets (GANs) BID9 have showcased the potential of architectures dealing with multiple interacting goals. They have since then proliferated substantially, including intrinsic curiosity BID19 , imaginative agents BID20 , synthetic gradients , hierarchical reinforcement learning (RL) BID23 BID22 and multi-agent RL in general BID2 .These can effectively be viewed as differentiable games played by cooperating and competing agents -which may simply be different internal components of a single system, like the generator and discriminator in GANs. The difficulty is that each loss depends on all parameters, including those of other agents. While gradient descent on single functions has been widely successful, converging to local minima under rather mild conditions BID13 , its simultaneous generalisation can fail even in simple two-player, two-parameter zero-sum games. No algorithm has yet been shown to converge, even locally, in all differentiable games.Related Work. Convergence has widely been studied in convex n-player games, see especially BID21 ; BID5 . However, the recent success of non-convex games exemplified by GANs calls for a better understanding of this general class where comparatively little is known. BID14 recently prove local convergence of no-regreat learning to variationally stable equilibria, though under a number of regularity assumptions.Conversely, a number of algorithms have been successful in the non-convex setting for restricted classes of games. These include policy prediction in two-player two-action bimatrix games BID24 ; WoLF in two-player two-action games BID1 ; AWESOME in repeated games BID3 ; Optimistic Mirror Descent in two-player bilinear zero-sum games BID4 and Consensus Optimisation (CO) in two-player zerosum games BID15 ). An important body of work including BID10 ; BID16 has also appeared for the specific case of GANs.Working towards bridging this gap, some of the authors recently proposed Symplectic Gradient Adjustment (SGA), see BID0 . This algorithm is provably 'attracted' to stable fixed points while 'repelled' from unstable ones in all differentiable games (n-player, non-convex). Nonetheless, these results are weaker than strict convergence guarantees. Moreover, SGA agents may act against their own self-interest by prioritising stability over individual loss. SGA was also discovered independently by BID8 , drawing on variational inequalities.In a different direction, Learning with Opponent-Learning Awareness (LOLA) modifies the learning objective by predicting and differentiating through opponent learning steps. This is intuitively appealing and experimentally successful, encouraging cooperation in settings like the Iterated Prisoner's Dilemma (IPD) where more stable algorithms like SGA defect. However, LOLA has no guarantees of converging or even preserving fixed points of the game.Contribution. We begin by constructing the first explicit tandem game where LOLA agents adopt 'arrogant' behaviour and converge to non-fixed points. We pinpoint the cause of failure and show that a natural variant named LookAhead (LA), discovered before LOLA by BID24 , successfully preserves fixed points. We then prove that LookAhead locally converges and avoids strict saddles in all differentiable games, filling a theoretical gap in multi-agent learning. This is enabled through a unified approach based on fixed-point iterations and dynamical systems. These techniques apply equally well to algorithms like CO and SGA , though this is not our present focus.While LookAhead is theoretically robust, the shaping component endowing LOLA with a capacity to exploit opponent dynamics is lost. We solve this dilemma with an algorithm named Stable Opponent Shaping (SOS), trading between stability and exploitation by interpolating between LookAhead and LOLA. Using an intuitive and theoretically grounded criterion for this interpolation parameter, SOS inherits both strong convergence guarantees from LA and opponent shaping from LOLA.On the experimental side, we show that SOS plays tit-for-tat in the IPD on par with LOLA, while all other methods mostly defect. We display the practical consequences of our theoretical guarantees in the tandem game, where SOS always outperforms LOLA. Finally we implement a more involved GAN setup, testing for mode collapse and mode hopping when learning Gaussian mixture distributions. SOS successfully spreads mass across all Gaussians, at least matching dedicated algorithms like CO, while LA is significantly slower and simultaneous gradient descent fails entirely. We evaluate the performance of SOS in three differentiable games. We first showcase opponent shaping and superiority over LA/CO/SGA/NL in the Iterated Prisoner's Dilemma (IPD). This leaves SOS and LOLA, which have differed only in theory up to now. We bridge this gap by showing that SOS always outperforms LOLA in the tandem game, avoiding arrogant behaviour by decaying p while LOLA overshoots. Finally we test SOS on a more involved GAN learning task, with results similar to dedicated methods like Consensus Optimisation. IPD: Results are given in FIG1 . Parameters in part (A) are the end-run probabilities of cooperating for each memory state, encoded in different colours. Only 50 runs are shown for visibility. Losses at each step are displayed in part (B), averaged across 300 episodes with shaded deviations.SOS and LOLA mostly succeed in playing tit-for-tat, displayed by the accumulation of points in the correct corners of (A) plots. For instance, CC and CD points are mostly in the top right and left corners so agent 2 responds to cooperation with cooperation. Agents also cooperate at the start state, represented by ∅ points all hidden in the top right corner. Tit-for-tat strategy is further indicated by the losses close to 1 in part (B). On the other hand, most points for LA/CO/SGA/NL are accumulated at the bottom left, so agents mostly defect. This results in poor losses, demonstrating the limited effectiveness of recent proposals like SGA and CO. Finally note that trained parameters and losses for SOS are almost identical to those for LOLA, displaying equal capacity in opponent shaping while also inheriting convergence guarantees and outperforming LOLA in the next experiment.Tandem: Results are given in Figure 3 . SOS always succeeds in decreasing p to reach the correct equilibria, with losses averaging at 0. LOLA fails to preserve fixed points, overshooting with losses averaging at 4/9. The criterion for SOS is shown in action in part (B), decaying p to avoid overshooting. This illustrates that purely theoretical guarantees descend into practical outperfor- mance. Note that SOS even gets away from the LOLA fixed points if initialised there (not shown), converging to improved losses using the alignment criterion with LookAhead. Theoretical results in machine learning have significantly helped understand the causes of success and failure in applications, from optimisation to architecture. While gradient descent on single losses has been studied extensively, algorithms dealing with interacting goals are proliferating, with little grasp of the underlying dynamics. The analysis behind CO and SGA has been helpful in this respect, though lacking either in generality or convergence guarantees. The first contribution of this paper is to provide a unified framework and fill this theoretical gap with robust convergence results for LookAhead in all differentiable games. Capturing stable fixed points as the correct solution concept was essential for these techniques to apply.Furthermore, we showed that opponent shaping is both a powerful approach leading to experimental success and cooperative behaviour -while at the same time preventing LOLA from preserving fixed points in general. This conundrum is solved through a robust interpolation between LookAhead and LOLA, giving birth to SOS through a robust criterion. This was partially enabled by choosing to preserve the 'middle' term in LOLA, and using it to inherit stability from LookAhead. This results in convergence guarantees stronger than all previous algorithms, but also in practical superiority over LOLA in the tandem game. Moreover, SOS fully preserves opponent shaping and outperforms SGA, CO, LA and NL in the IPD by encouraging tit-for-tat policy instead of defecting. Finally, SOS convincingly learns Gaussian mixtures on par with the dedicated CO algorithm.
Opponent shaping is a powerful approach to multi-agent learning but can prevent convergence; our SOS algorithm fixes this with strong guarantees in all differentiable games.
{"src": "scitldr-AIC_train", "paper_id": "SyGjjsC5tQ"}