STABLE OPPONENT SHAPING IN DIFFERENTIABLE GAMES
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.
This paper focuses on the problem of convergence in multi-objective optimisation with differentiable losses. This topic is timely and relevant, given the increasing amount of recent work on multi-objective architectures, e.g. GANs, adversarial learning, multi-agent reinforcement learning. The authors focus on stable fixed points (SFP), rather than Nash equilibria, as the solution concept in the entirety of their analysis. Casting the recently proposed LOLA gradient adjustment into a general matrix form, they diagnose an example where the shaping term in LOLA prevents convergence to SFP. They also find that discarding the shaping term leads to an earlier method (which they name ''LA'') with convergence guarantees in two-player two-action games. However, this also loses the opponent shaping ability of LOLA. To address these limitation, the authors propose SOS, which interpolates between LA and LOLA, and dynamically chooses the interpolation coefficient $p$ so that their adjusted gradient preserves LOLA's shaping ability only to the extent allowed by the constraint of moving in LA's direction. The main goal of the paper is to show that SOS converges locally to SFP, and to fixed points only, while avoiding strict saddles. Experiments on synthetic games show that SOS preserves the benefit of LOLA while avoiding its theoretically-predicted issues, and a more complex Gaussian mixture GAN experiment shows SOS is empirically competitive with other gradient adjustment methods.
The main conceptual novelty consists of the dynamic interpolation term to combine advantages of LOLA and LA while avoiding pitfalls of both. The major strength of the paper lies in the clear justification for this interpolation approach. The paper contains strong theoretical results for general differentiable games, and deserves the notice of the ICLR community if valid. However, I have major concerns with the proof of Theorem 2 (i.e. Theorem D.4 in the appendix), which affects the validity of Corollary 3 and Theorem 4. 
In the proof of Theorem D.4:
1. How does the expression $u^T M^{-1}GMu$ have conformable dimensions, when $G \in R^{d \times d}$ while $u \in R^{d-1}$? Was any assumption made about the matrix $M = (I + \alpha H_d)^{1/2}$?
2. In the middle of page 14, a unit vector $u \in S^m$ is defined, but it is not clear what vector space is meant by $S^m$.
3. In the second-to-last line of page 14, a quantity $S$ is used but not defined clearly in any preceding part of the proof. Remark D.5 refers to $S$ as the symmetric part of $G$, and asserts that S is not positive definite. If the quantity $S$ used in the proof is the same non-PD quantity, then $S$ does not have a Cholesky factorisation. So how is Cholesky decomposition conducted at end of page 14?
4. In the first line of page 15, a quantity $A$ is used but not defined anywhere else in the entire paper. 
5. From the subsequent line, it appears to be the anti-symmetric part of H. Is it correct assumption? If so, $H^2$ is not $(S^T - A^T)(S + A)$. If you replace it with correct form, whole quantity does not compute to be positive or becomes meaningless.
As Theorem 2 is the crux for all the theoretical advancement presented in the paper, clarifications on above correctness questions is very important for clear acceptance of this work.
While Definition 1 precisely defines differentiable games to have *twice* differentiable losses, why do the authors assume *thrice* differentiable losses at the start of Section 4?
In Section 2.2, the authors make a broad statement that ''Nash equilibria cannot be the right solution concept for multi-agent learning.'' They provide one example where Nash is undesirable (L^1 = L^2 = xy). However, since this example can be viewed as a fully cooperative game with joint loss L = 2xy, it does not support the broader statement that Nash is undesirable in all games. Because this statement directly motivates the authors to focus on stable fixed points, rather than Nash, as the solution concept in their subsequent analysis, it is very important to provide better justification for the claim.
Minor comments:
1. Under Proposition 1, the authors suddenly speak of ''...the policy being optimal''. Since the author's work pertains to general multi-objective settings, not solely multi-agent reinforcement learning, the word ''policy'' sounds strange in context.
2. The statement of Proposition B.1, and the concluding line of the derivation, left out a coefficient $\alpha$ that is present in Proposition 1 in the main text.
3. While the authors claim and prove independence of theoretical results from choice of a and b, are there any practical implications in terms of performance or convergence?