COLA: Consistent Learning with Opponent-Learning Awareness
Authors: Timon Willi
Johannes Treutlein
Alistair Letcher
Jakob Nicolaus Foerster
Venue: ICLR 2022 Submitted (2022)
Keywords: Differentiable games
multi-agent reinforcement learning
general-sum games
lola

Abstract: Optimization problems with multiple, interdependent losses, such as Generative Adversarial Networks (GANs) or multi-agent RL, are commonly formalized as differentiable games. 
Learning with Opponent-Learning Awareness (LOLA) introduced opponent shaping to this setting. More specifically, LOLA introduced an augmented learning rule that accounts for the agent's influence on the anticipated learning step of the other agents. However, the original LOLA formulation is inconsistent because LOLA models other agents as naive learners rather than LOLA agents. 
In previous work, this inconsistency was stated to be the root cause of LOLA's failure to preserve stable fixed points (SFPs). We provide a counterexample by investigating cases where Higher-Order LOLA (HOLA) converges. 
Furthermore, we show that, contrary to claims made, Competitive Gradient Descent (CGD) does not solve the consistency problem.
Next, we propose a new method called Consistent LOLA (COLA), which learns update functions that are consistent under mutual opponent shaping. Lastly, we empirically compare the performance and consistency of HOLA, LOLA, and COLA on a set of general-sum learning games.

Under review as a conference paper at ICLR 2022
COLA: CONSISTENT LEARNING WITH OPPONENT- LEARNING AWARENESS
Anonymous authors Paper under double-blind review
ABSTRACT
Optimization problems with multiple, interdependent losses, such as Generative Adversarial Networks (GANs) multi-agent RI., are commonly formalized differentiable games, Learning with Opponen-LLeaming Awareness (LOLA) in- troduced opponent shaping to this setting. More specifically, LOLA introduced an augmented learning rule that accounts for the agent's 's influence on the antici- pated learning step of the other agents. However, the original LOLA formulation is inconsistent because LOLA models other agents as naive learners rather than LOLA agents. In previous work, this inconsistency was suggested as a root cause of LOLA's failure to preserve stable fixed points (SFPs). We show that, contrary to claims in previous work, Competitive Gradient Descent (CGD) does not solve the consistency problem and does not recover high-order LOLA (HOLA) as series expansion. Working towards a remedy, we formalize consistency and show that HOLA is consistent whenever it converges; however, it may fail to converge alto- gether. We propose a new method called Consistent LOLA (COLA) which learns update functions that are consistent under mutual opponent shaping. We prove that even such consistent update functions do not preserve SFPs, contradicting the hypothesis that this shortcoming is due to inconsistency. Finally, we empiri- cally compare the performance and consistency of aforementioned algorithms on a range of general-sum learning games.
INTRODUCTION
Multi-objective problems can be found in many domains, such as GANs (Goodfellow et al.] 2014) or single- and multi-agent reinforcement learning (RL) in the form of imaginative agents (Racanière cet al. 2017), hierarchical RL (Barto & Mahadevan 2002), and intrinsic curiosity (Schmidhuberj 1991. popular framework to understand systems with multiple, interdependent losses is differ- entiable games (Balduzzi al.] 2018). For example, in the case of GANs, the differentiable game framework models the generator and the discriminator as competing agents, each trying to optimize their respective loss. The action space of the game consists of choosing the respective network parameters (Balduzzi et al. 2018).
An effective paradigm improve learning in differentiable games is opponent shaping, where the players use their ability to shape each other's learning steps. LOLA (Foerster et al., 2018) was the first work make explicit use opponent shaping in the differentiable game setting. LOLA is also one of the only general learning methods designed for differentiable games that obtains mutual cooperation with the Tit-for- Tat strategy in the Iterated Prisoner's Dilemma (IPD). The Tit-for-Tat strategy starts out cooperating and retaliates once whenever the opponent does not cooperate. It achieves mutual cooperation and has proven to successful at IPD tournaments (Axelrod [984] Harper et al.) (017). In contrast, naive gradient descent and other more sophisticated methods typi- cally converge to the mutual defection policy under random initialization (Letcher et al. 2019b).
While LOLA discovers these interesting equilibria, the original LOLA formulation is inconsistent because LOLA agents assume that their opponent a naive learner. This assumption clearly violated if two LOLA agents leam together game. has been suggested that this inconsistency is the root cause for LOLA's shortcomings, such as not converging to SFPs in some simple quadratic p. 2, 26; see also Letcher al. 2019b).
games (Letcher 2018 g

---

Under review as a conference paper at ICLR 2022
Contributions. How can LOLA's inconsistency be resolved? To answer this question, first revisit the concept of higher-order LOLA (HOLA) (Foerster et al. 2018 in Section 4.1 For ex- ample, second-order LOLA assumes that the opponent 1s first-order LOLA agent (which in turn assumes the opponent is a naive learner) and so on. Assuming that HOLA converges with increasing order, define infinite-order LOLA (iLOLA) as the limit of HOLA whenever it exists. Intuitively, it should follow that two iLOLA agents have a consistent view of each other, meaning they make an accurate assumption about the learning behavior of the opponent under mutual opponent shap- ing. We introduce a formal definition of consistency and prove that iLOLA is indeed self- ooffcoosistent under mutual opponent shaping.
Previous work has claimed that a series expansion of Competitive Gradient Descent (CGD) (Schäfer & Anandkumar) 2020) recovers high-order LOOAA This would imply that CGD corresponds to iLOLA and thus solves the consistency problem. In Section 4.2] we prove that this is false: CGD) does not in general correspond to iL.OAA, and, unlike iLOLA, does not resolve the problem of con- sistency. In particular, show that, contrary to previous claims, the series expansion of CGD does not correspond to higher-order LOLA.
There are number of problems with addressing consistency using a limiting update (iLOLA): the process may not converge, and requires computation of arbitrarily high derivatives. In Section 4.3 propose Consistent LOLA (COLA) more general and efficient alternative. Instead of repeat- edly applying the LOLL learning rule (iLOLA), COLA learns a pair of consistent update functions by explicitly minimizing consistency loss. By reframing the problem such, the method only requires up to second-order derivatives, and instead of having a handcrafted update function as for LOLA or CGD, we use the representation power of neural networks to learn the update step.
In Section 4.4
we prove initial results about COLA. First, we show that COLA's solutions are not necessarily unique. Second, despite being consistent, COLA does not recover SFPs, contradicting the prior belief that this shortcoming is caused by inconsistency. Third, we provide an example in which COLA converges more robustly, i..., under a wider range of learning rates, than LOLA.
Finally, in Sections 5 and 6 we report our experimental setup and results, investigating COLA and HOLA and comparing to LOLA and CGD range of games. We show that, despite its non- uniqueness, COLA tends to find similar solutions in different runs empirically. Moreover, we show that COLA finds the iLOLA solution when HOLA converges but finds different solutions when HOLA diverges. These solutions have lower consistency loss and converge under a broader range of learning rates than LOLA and HOLA. Our experiments also show that, while COLA does not find Tit-for-Tal Tat the IPD (unlike LOLA), it does learn policies with near-optimal total payoff.
RELATED WORK
General-sum learning algorithms and their consequences have been investigated from different per- spectives in the reinforcement learning, game theory, and GAN literature, see e.g. (Schmidhuber) 1991 Barto& & Mahadevan] 2002; Racanière et al., 2017: Goodfellow et al. 2014) to name a few. Next, we will highlight few of the approaches the mutual opponent shaping problem.
Opponent modeling maintains an explicit belief of the opponent, which allows to reason over their strategies and compute optimal responses. Opponent modeling can be divided into different subcat- egories: There are classification methods, classifying the opponents into pre-defined types (Weber & Mateas 2009 Synnaeve & Bessiere (00T)), or policy reconstruction methods, where we explicitly predict the actions of the opponent (Mealing & Shapiro 2017). Most closely related to opponent shaping recursive reasoning. where methods model nested beliefs of the opponents (He et al.,
2016 Albrecht & Stone 2019 Wen et al. 2019).
In comparison, COLA assumes that we have access to the ground-truth model of the opponent, e.g., the opponent's payoff function, parameters, and gradients, which puts COLA into the framework of differentiable games (Balduzzi et al. 2018). Various methods have been proposed, investigating the local convergence properties to different solution concepts (Mescheder et al. 2018 Mazumdar et al.
2019 Letcher et al. 2019b] Azizian et al. 22200] Schäfer & Anandkumar [020 Schäfer et al. 2020, Hutter 2020). Most of the work in differentiable games has not focused on the issue of opponent shaping and consistency. Mescheder et al. (2018) and Mazumdar et al. (2019) focus solely on zero- sum games without shaping. Letcher al. (2019b) improve LOOLA, but do not investigate the
2

---

Under review as a conference paper at ICLR 2022
consistency issue. CGD (Schäter & Anandkumar 2020) addresses the consistency issue of LOLA for zero-sum games but not for general-sum games. The exact difference between CGD and LOLA is addressed in the Section 4.2
BACKGROUND
3.1 DIFFERENTIABLE GAMES
The framework of differentiable games has become increasingly popular to model the problem of multi-agent learning. Whereas in the framework of stochastic games are typically limited to parameters such as action-state probabilities, differentiable game generalizes to any parameters as long the loss function differentiable with respect to them (Balduzzi al., 2018). We restrict our attention on two-player games, as is standard the current differentable games literature.
Definition (Differentiable games). In a two-player differentiable game, players = 1,2 control parameters 0g Idd to minimize twice continuously differentiable losses L' 1dd+ R. We adopt the convention to write -i to denote the respective other player.
A fundamental challenge of the multi-loss setting is finding meaningful solution concept. Whereas in the single loss setting the typical solution concept local minima, in multi-loss settings there different sensible solution concepts. Most prominently, there are Nash Equilibria (Osborne & Ru- binstein 1994). However, Nash Equilibria include unstable saddle points that cannot be reasonably found via gradient- based learning algorithms (Letcher et al.] (019b).. A more appropriate concept are stable fixed points (SFPs), which could considered a differentiable game analogon to local minima in single loss optimization. We will omit a formal definition here for brevity and point the interested reader to previous work on the topic (Letcher et al. (019a).
3.2 LOLA AND SOS
Consider differentiable game with two players. A LOLA agent 01 uses its access to the opponent's 's parameters 0₂ to differentiate through the learning step the opponent. In other words, agent reformulates their loss to L' (01, 02 + Af2), where Ab₃ represents the assumed learning step of the opponent. In first-order LOLA we assume the opponent be naive learner: A0, -a VL? which is what makes LOLA inconsistent if the opponent was any other type of learner. Note that V2 denotes the gradient with respect to 02. Also note that a represents the look-ahead rate, which the assumed learning rate of the opponent. In the original paper the loss approximated using a Taylor expansion L 2V Ad2. For agent 1, their first-order (Taylor) LOLA update is then defined as
A0 = a V + V12l A02 + (V,402) Vel.'
Alternatively, in exact LOLA, the derivative is taken directly with respect to L (01. + A02).
LOLA has had some empirical success, being one of the first general learning methods to discover Tit-for-Tat like solutions in social dilemmas. However, later work showed that LOLA does not preserve SFPs 8 since the rightmost term be nonzero at 6. In fact, LOLA agents show "arrogant" behavior: they assume they can shape the learning of their naive opponents without having to adapt the shaping of the opponent. Prior work hypothesized that this arrogant behavior is due to LOLA's inconsistent formulation (Letcher 2018 2, 26; see also Letcher et al. 2019h).
To improve upon LOLA, Letcher et al. (209bb) have suggested the Stable Opponent Shaping (SOS) algorithm. SOS applies a correction to the LOLA update, leading to theoretically guaranteed con- vergence SFPs. However, despite its desirable convergence properties, SOS still does not solve the conceptual issue of inconsistent assumptions about the opponent.
3.3
CGD
CGD SShafeer & Anandkumar 2020 proposes updates that themselves Nash Equilibra of local bilinear approximation of the game. stands out by its robustness to different step sizes of opponents and its ability find SFPs. However, CGD does not find Tit-for-Tat on the IPD, instead
3

---

Under review as a conference paper at ICLR 2022
Table (a) This table shows the log of the squared consistency loss on the Tandem game, where e.g. HOLA6 is sixth-order higher-LOLA (b) Cosine similarity between COLA and LOLA, HOLA2, and HOLA6 over different look-ahead rates on the Tandem game.
(a)
(b)
LOLA
HOLA2
HOLA6
COLA
LOLA
HOLA2
HOLA4
128.0
131072
4.84e-14
0.57
0.58
0.60
0.5
12.81
14.05
12.35
2.62c-14
0.5
0.61
0,46
0.15
0.3
2.61
2.05
0.66
4.09e-14
0.3
0.92
0.51
0.72
0.1
0.08
9.13e-3
1.62c-6
6,55c-14
0.1
0.94
0.98
0.99
0.01
1.41e-5
2.10c-8
3.69c-14
8,58c-14 14
0.01
0.99
1.0
1.0
converging to mutual defection (see Figure 13 in Appendix
[.6].
CGD's update rule can be written
as
A0 A0
-a
Id
V
)
VIL L V2L²
V V2 L
ld
One can recover different orders CGD by approximating the inverse matrix via the series expan- sion |A| < 1 + (Id A)-1 = lim Ek A For example, at N=1, we recover a version called Linearized CGD (LCGD), defined via A0 == aV + 12V
METHOD AND THEORY
4.1 CONVERGENCE AND CONSISTENCY OF HIGHER-ORDEE LOLA
To begin, define and analyze iLOLA. In this section, we focus exact LOLA, but we provide a version of our definition and proof of consistency for Taylor LOLA in Appendix C HOLAn is defined by the recursive relation
h = a
h3 h2 a h1
with h hら 0, omitting arguments (0', 82) for convenience. In particular, HOLA0 coincides with simultaneous gradient descent while HOLA1 coincides with LOLA.
Definition 2 (iLOLA). If HOLAn (hT, h²) converges pointwise
oc, define
hp h
iLOLA == lim n-
as the limiting update.
We show in Appendix that HOLA does not always converge, even in simple quadratic games. the other hand, iLOLA satisfies criterion of consistency whenever HOLA does converge (under some assumptions), formally defined as follows:
Definition (Consistency). Any update functions h1 IR + Rd and h2: Rd + Rd are consistent (under mutual opponent shaping) if for all 0, e R O2 E R2, they satisfy
h = a V (T. (0,, 02 + h2))
h2 = a (L2 + (2,
(3)
Proposition 1. Let HOLAn = (hf h2) denote player i's exact n-th order LOLA update. Assume that lim,-+20 h. (0) h2(0) and lim,-x v,h", (,h exist for all 0 and E {1,2). Then iLOLA is consistent under mutual opponent shaping.
Proof. In Appendix B
4.2 CGD DOES NOT RECOVER HIGHER-ORDER LOLA
Schäffer & Anandkumar 2020) claim that "LCGD coincides with first order LOLA" (page 6), and moreover that the "serics-expansiie expansion [of CGD) would recover higher-order LOLA" (page 4). Unfor- tunately, prove that this is untrue in general games. L.GD coincides instead with Ahokd
4

---

Under review as a conference paper at ICLR 2022
Tandem
Matching Penriess
Litimacumm
Log connistenncy Loss
Lo-ke 8.5
Loq of Consictency
Log Consistency
-23
-25
Leerning ning Step
Learing Stop
Leaming Step
(a)
(c)
Tendem
Masching Pennies
106.03
Aucrogo Las2
3.33
Ruetogg LO35
Average Lese
AB00LL
0
46
212
100
104
502 143
Learning Stop
Loaming
Step
(d)
(I)
Figure 1: Subfigure (a), (b) and (c) depicts the log of the consistency loss over the training of the update functions for the Tandem, MP and Ultimatum games. Subfigure (d). (e) and (f) show the performance of COLA in comparison to HOLA:0.1, LOLA:0.1 and CGD:0.1. COLA:0.1 denotes COLA with a look-ahead rate of 0.1.
Zhang & Lesser 2010), an algorithm that lacks opponent shaping. Similarly, the series-expansion of CGD recovers high-order LookAhead but not high-order LOLA (neither exact nor Taylor).
Proposition 2. In general, CGD is inconsistent and does not coincide with iLOLA. In particular, the series-expansion of CGD does not recover HOLA (but does recover high-order LookAhead). Moreover, LCGD does not coincide with LOLA (but does coincide with LookAhead).
For the negative results, it suffices to construct a single counter-example: show that LCGD and LOLA differ almost-eveyywhert in the Tandem game (excluding set of measure zero). Proving that the series-expansion of CGD does not recover HOLA relies on noticing that this would imply CGD satisfying the consistency equations for a sufficiently small. We prove that this also fails humost-everywhee in the Tandem game. We then show that LCGD LookAhead and that the eeries-expansion of CGD recovers high-order Look in general games.
Proof. In Appendix D
4.3 COLA
iLOLA is consistent under mutual opponent shaping. However, HOLA does not always converge and, even when it does, it may be expensive to recursively compute HOLAn for sufficiently high to achieve convergence.
As alternative, we propose consistent LOLA (COLA). COLA finds consistent update functions and avoids an infinite regress by directly solving the equations in Definition Ionettioonnnumeeee numerically. To do so, define the consistency losses for pair of update functions (h₁, h2) parameterized by (01, Ø2), obtained for given 0 as the difference between RHS and LHS Definition 3
C₁ (1h, 62 02) = [0, 02) + ( (0,, 02 + h2 02))) C2( 62, 02) = h2(()), 02) + a (L + (,, 02). 02))
(4)
(5)
If both losses minimised to 0 for all 6, then the two update functions are consistent. For this paper, we define h and h2 as neural networks parameterized by Φi and Φ2 respectively, and numerically minimize the sum of both losses a region of interest using Adam (Kingma & Ba 2017).
5

---

Under review as a conference paper at ICLR 2022
Table (a) Comparison of consistency losses over multiple look-ahead rates on the MP game. (b) Cosine similarity between COLA and LOLA, HOLA2 and HOLA4 over different look-ahead rates on the MP game.
(a)
(b)
LOLA
HOLA2
HOLA4
COLA
LOLA
HOLA2
HOLA4
10
0.06
0.70
6.56
0.24
0.90
0.87
5
4,59c-3
0.03
0.15
9,47e-3
5
0.98
0.95
0.89
1.0
8.79e-6
3.25e-8
4.37e-9
2.35e-7
1.0
0.99
0.99
0.99
0.5
4.80c-7
2,53e-10
5.18c-12 12
1.30c-7
0.5
0.99
0.99
0.99
0.01
1.07e-13
5,58c-17
5.30c-17
6,99c-8
0.01
0.99
0,99
0.99
The parameter region of interest θ depends on the game being played. For game with probabilities as actions, we select an area that captures most of the probability space (e.g. we sample a pair of parameters (0), 02) ~ [-7, 7] as (7) s 1, where a is the Sigmoid function).
The expected aggregate consistency loss over the region then defined
C(ó1 )2) (e,, (() (01 222 02,02) + C2(01. 22 01,02)
(6)
We optimize this loss by sampling parameter pairs (01, uniformly from O and feeding them to the neural networks hn and hıg each outputting the parameter update for agent. We then update Φ1, d2 by taking a gradient step to minimize C.
We train the update functions until the loss has converged. We then the learned update functions to train a pair of agent policies in the given game.
4.4 THEORETICAL RESULTS ABOUT COLA
In this section, we provide theoretical results about COLA's uniqueness and convergence behavior, using the Tandem game (Letcher et al. 2019b) and the Hamiltonian game (Balduzzi et al.) 2018) as examples. These are simple 1-dimensional quadratic resp. bilinear games, with losses given in Section[3] Proofs for the following propositions can be found in E
respectively.
First, we show that solutions to the consistency equations are in general not unique, even when restricting to linear update functions in the Tandem game. Interestingly, empirically, COLA does seem to consistently converge to the same solution regardless (see Table in Appendix 1.3
Proposition 3. Solutions to the consistency equations are not unique, even when restricted to linear solutions; more precisely, there exist several linear consistent solutions to the Tandem game.
Second, show that consistent solutions do always preserve SFPs, contradicting the hypothesis that LOLA's 's failure to preserve SFPs is due it its inconsistency (see Section 3.2) We support this result experimentally in Section 6
Proposition 4. Consistency does imply preservation of stable fixed points: there is a consistent solution to the Tandem game with = 1 that fails to preserve any SFP. Moreover, for any a >> 0, there are no linear consistent solutions to the Tandem game that preserve more than one SFP.
Third, show that COLA have more robust convergence behavior than LOLA and SOS:
initial parameters and any LOLA and SOS have divergent iterates in the Hamiltonian game. By contrast, any linear solution to the consistency equations converges the origin for any initial parameters and any look-ahead rate O; moreover, the speed of convergence strictly increases with a.
Proposition 5. For any
5 EXPERIMENTS
We carry out investigation set of games from the literature (Balduzzi al. 2018 Letcher et al. 2019b) using SOS and CGD as baselines. For details on the training procedure of COLA, we refer the reader to Appendix

---

Under review as a conference paper at ICLR 2022
Variance over Consistency
Matching Pennies
COLA.10
1OLA4:10
LOLA-10
CGD 10
Log Variance
Average Loss
CooA_short
-5
COLA, long
0.0
HCLA1
-6
HOLAZ
-0.5
HOLA3
-8
HOLAS
HOLAS
-1.
-8
300
400
Log Consistency Loss
Learning Step
(a)
(b)
Figure/ 2: Training in MP look-ahead rate of 10. (a) Axes a log-scale. Increasing the consistency helps with decreasing the variance of the solution. (b) LOLA and HOLA find non- convergent diverging solutions, while COLA is convergent.
First, we compare HOLA and COLA on quadratic, general-sum games, including the Tandem game (Letcher et al. 2019b), where LOLA fails converge SFPs. Second, investigate non-quadratic games, such as the zero-sum Matching Pennies (MP) game, the general-sum Ultimatum game (Hut-
ter 2020) and the iterated prisoner's dilemma (IPD) (Axelrod 1984. Harper al. 2017).
We investigate the convergence behavior of HOLA and COLA by comparing the consistency losses over a range of look-ahead rates, where COLA retrained for each look-ahead rate to ensure fair comparison. To compare the solutions found by HOLA and COLA, we compute the cosine similarity between the two across randomly sampled parameters across our region of interest.
Quadratic and bilinear games. Losses in the Tandem game (Letcher et al. 2019b) given by
(' = (x + y)² 2x and L (z(xz)) = (2 y)² 2)² 2y
(7)
for agent and respectively. The Tandem game originally introduced to show that LOLA fails to preserve SFPs at æ + = 1 and instead converges to sub-optimal solutions (Letcher et al.) 2019b). Additionally the Tandem game, investigate the algorithms the Hamiltonian game, [' v) = ry and Lz y) (. = v 10ry (Balduzzi et al. 2018).
(x.y)
-y: and the Balduzzi game, where L Lz( y) $x²² + 10ry and
Matching Pennies. The payoff matrix for the Matching Pennies (MP) (Lee K 1967) game is shown in Appendix 1.3 in Table 6 Each policy is parameterized with single parameter, the log- odds of choosing heads Phends o (0A). In this game, the unique Nash equilibrium is playing heads half the time.
Ultimatum game. The binary, single-shot Ultimatum game (Güth et al. 1982 Sanfey et al. 2003
Oosterbeek et al. [2004] Henrich et al. (0066 is set up as follows. There are two players, player A and B. Player A has access to $10. They can split the money fairly with B (85 for each player) or they can split unfairly (88 for player A, $2 for player B). Player can either accept or reject the proposed split. If player B rejects, the reward is O for both players. If player B accepts, the reward follows the proposed split. Player A's parameter is the log-odds of proposing fair split Pfair x0))). Player B's parameter is the log-odds of accepting the unfair split (assuming that player always accepts fair splits) Paccept = (00))
VA 5ptir + 8(1 Pfair Paccept and VB 5ptair 2(1 Pfair Paccepp
(8)
We next investigate the infinitely iterated prisoners' dilemma with discount factor y = 0.96 and the usual payout function (see Appendix [66). An agent i is defined through 5 parameters, the log-odds of cooperating for the first time step and for the four possible tuples of past actions both players in the later steps.
IPD.
7

---

Under review as a conference paper at ICLR 2022
IPC
IPU3
COL 1P1
CUAMAM 10LA4
Log of Consistency
Aueraage Loss
2000
2002
2:48
1000
27030
2230
206
120
883
199
20
26
439
Piccooer stoon)ssweee
(a)
(c)
IPC
IPD
Log of Condistency Loxs
MIELE
Sverage La55
2033
4.00
SC3M
1205
Learning Stop
Picaoserationjeanee..oo aggent
(d)
(f)
Figure 3: Results are the IPD. Subfigure (a) / (d), show the consistency loss for look-ahead rate of 0.03 / 1.0 respectively, (b) / (e) the average loss and (c) / (f) the policy for the first player, both for the same pair of look-ahead rates. At low look-ahead HOLA defects and high ones it diverges, also leading to high loss.
RESULTS
Here, we outline our experimental results, providing evidence on the empirical behavior of COLA and comparing COLA HOLA and our baselines. Additional results can be found in Appendix ![]
First, we investigate how increasing the order of HOLA affects the consistency of its updates. As we can see Table and 3al HOLAA's updates become more consistent with increasing order below a certain look-ahead rate threshold. Above that threshold, HOLA's updates become less consistent with increasing order. The threshold is game-specific. In the Tandem game, it is around a look- ahead rate of 0.5, whereas for the MP it is around 5. Such threshold can be found empirically for all games that we evaluate on, as we show in Appendix [1 in Tables 4a 5 Sa and T0 the same Tables observe that COLA finds consistent updates below the look- ahead threshold, though the consistency losses are higher than HOLA's for non-quadratic games. Overall the consistency losses low enough constitute consistent solution. For the IPD, COLA's consistency losses are high compared to other games, but much lower than HOLA's consistency losses at high look-ahead rates. We leave it to future work find methods that obtain more consistent solutions on the IPD. In general, COLA finds consistent updates above the look-ahead threshold even when HOLA does not.
Second, are interested whether COLA and HOLA find similar solutions when HOLA's updates converge with increasing order. As we can see in Table 1b 26 and 3bb they find very similar solutions measured by the cosine similarity of the respective updates over θ. Above the threshold, COLA's and HOLA's updates become less similar with increasing order of HOLA, indicating that they do not find the same solution.
Third, we analyze the solutions found by COLA qualitatively and compare to those found by LOLA, HOLA, SOS and CGD. In the Tandem game (Figure we can see that COLA finds the same so- lution HOLA8, qualitatively confirming our observation from Table lb that they find similar solutions. Moreover, COLA does not recover SFPs, thus experimentally confirming Proposition 4 COLA finds convergent solution
high look-ahead rate (see COLA:0.8). whereas LOLA, HOLA and SOS do not (Figure 4b in Appendix [.T]. CGD is the only other algorithm in the com- parison that also shows robustness to high look-ahead rates in the Tandem game.
8

---

Under review as a conference paper at ICLR 2022
Table (a) Comparison of consistency losses over multiple look-ahead rates on the IPD game, (b) Cosine similarity between COLA and LOLA, HOLA2 and HOLA4 over different look-ahead rates, on the IPD game.
(a)
(b)
LOLA
HOLA2
HOLA4
COLA
LOLA
HOLA2
HOLA4
1.0
39.56
21.16
381.21
0.65
1.0
0.77
0.70
0.53
0.03
1.72c-3
4.72c-6
9.72c-8
0.33
0.03
0.96
0.98
0.98
On Matching Pennies at high look-ahead rates, SOS and LOLA mostly don't converge whereas COLA converges even faster with high look-ahead rate (see Figure Le and 2ap.
For the Ultimatum game, the qualitative comparison shows that COLA is the only method that finds the fair solution consistently at a high look ahead rate, whereas SOS and LOLA do not (see Figure 10d in Appendix 1.4.. At low look-ahead rates, all algorithms find the unfair solution (Figure Tf).
For further comparison, introduce the Chicken game in Appendix L.5 Both Taylor LOLA and
SOS crash, whereas COLA swerves at high look-ahe look-ahead rates (Figure 12d]. game results in catastrophic payout for both agents, whereas swerving results in a jointly preferable outcome.
Crashing in the Chicken
On the IPD, all algorithms find the Defect-Defect strategy low look-ahead rates (Figure (bb). At high look-ahead rates, COLA finds a strategy qualitatively similar to Tit-for-Tat, as displayed in Figure 3f though much more noisy. However, COLA still achieves close to the optimal joint loss, in comparison to CGD, which finds Defect-Defect even at high look-aheaa rate (see Figure 13 in Appendix|L66
To further motivate the point that increased consistency helps with robustness to wider range of look-ahead rates, we plot the variance over the consistency on the Matching Pennies game a high look-ahead rate. The variance is calculated over the trajectory of payoff's for an algorithm. The lower the consistency loss, the lower the variance of the solution. This further underlines, least empirically, the benefits of increased consistency.
Lastly, we find empirical evidence for Proposition in the Hamiltonian game (Figure 7b in Ap- pendix 1.2 where COLA converges faster at a higher look-ahead rate. Such behavior can also be seen for the Balduzzi game (Figure 66 in Appendix [.2] and the MP game (Figure Ie).
To conclude, COLA finds consistent and convergent updates over wider range of look-ahead rates than state-of-the-art general-sum learning algorithms, such as LOLA and SOS, Furthermore, finds qualitatively different solutions, sometimes with higher average rewards, like the Ultimatum, Chicken and IPD games.
7 CONCLUSION AND FUTURE WORK
In this paper we cleared up the relation between the CGD and LOLA algorithms. We also showed that iL.OAA solves part of the consistency problem of LOLA. We introduced Consistent LOLA, that finds consistent solutions without requiring many recursive computations like iLOLA. was believed that inconsistency leads to arrogant behaviour and lack of preservation for SFPs. We show that even with consistency, opponent shaping behaves arrogantly, pointing towards fundamental open problem for the method.
method, called
We empirically investigated the consistency behavior of higher-order LOLA and COLA and found that HOLA's updates do not converge with increasing order in each hyperparameter regime, even for low-dimensional games with polynomial losses. Moreover, we showed that consistency increases robustness to different look-ahead rates.
This work opens more questions for future work than it answers. Some fundamental questions are the existence of solutions to the COLA equations in general games and general properties of convergence and learning outcomes. Moreover, additional work is needed to scale COLA to large settings such as GANs or Deep RL, or settings with more than two-players. Another interesting axis is addressing further inconsistent aspects of LOLA as identified in Letcher et al. (2019b).


Reviews:
[{"review_id": "gPLgYsZ-2cD", "reviewer": "Reviewer_bkzQ", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "### Strengths\n- Paper is well written and provides a well motivated investigation into LOLA’s failure to preserve SFPs and corresponding ‘arrogant’ behavior.\n- Explanation of cases where CGD is not equivalent to iLOLA in general-sum games seems important and significant.\n- The motivation behind the proposed COLA method is well explained and justified, and the empirical results are thorough and support the authors’ claims. \n\n### Weaknesses\n- More thorough proof for CGD argument would strengthen the paper, as well as including it as a baseline in more of the empirical evaluations. ", "summary_of_the_paper": "The authors tackle the consistency problem of the original LOLA formulation. The paper investigates HOLA convergence, demonstrates that CGD does not correspond to high-order LOLA in general, and proposes COLA to directly address the consistency problem. The proposed method COLA seems more robust to different look-ahead values where HOLA diverges. The authors also find that COLA is still sometime susceptible to the ‘arrogant’ LOLA behavior, opening questions for future work. ", "summary_of_the_review": "This work attempts to overcome and investigate weaknesses of LOLA to tackle the consistency problem. Even with explicit consistency loss the authors still find that we still find that the arrogant behavior remains, so the insights from this investigation seem relevant for future work and open questions in this area.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "eLz4N4hKHRu", "reviewer": "Reviewer_ZQJ8", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper focuses on an interesting challenge in learning in the presence of opponents. \n\nOn the other hand, the contributions the paper makes do not meet the claims made throughout the paper. For example, take section 4.1: \"This is not a rigorous proof, but it should be intuitively clear...\" First of all, \"should\" has no meaning? What if it is not? Second, this is one of the main claims that the paper is built on. If you are not going to give a rigorous proof for this, what will you give a proof for? Too much is left to future work. \n\nThe paper is also filled with similar vague language. In addition to the wishy-washy language, central concepts like \"consistency\" and \"stability\" are used throughout the paper and for the most part without a clear definition (at least for a long time). And, even comparative form, e.g., \"more stable\" are used even though nothing had been made quantitative. \n\nWhile this shortcoming may be inherited from the literature, the assumptions (e.g., knowledge of the opponent's payoff functions, parameters, and gradients) made in the paper are just way too strict. Coupled with the lack of rigorous results, the insights established in the paper are at best limited.  \n\nThere is a proposition that gives the means to check whether a pair of update functions are consistent. On the other hand, it is not clear how one actually checks the condition for consistency given in the proposition.\n\nSome of the questions posed at the beginning of the results section are odd. It is not clear whether an empirical analysis can even ever answer such questions. As stated, only rigorous proofs would answer the questions (and the paper lacks those). Similarly, the discussion of the observations from the empirical results overgeneralizes. \n\n", "summary_of_the_paper": "The paper is on learning in a differential game setting by accounting for the ability of the opponent to learn. It displays several issues in previously existing methods, proposes a new methods, and demonstrates some of the features that appear to be superior to the existing methods. ", "summary_of_the_review": "The paper is on an interesting issue yet it is at best a starting point and far from prime time. \n\n----------------\n\nAfter the author response:\n\nThanks to the authors for the response. It unfortunately does not change my assessment. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "1: The main claims of the paper are incorrect or not at all supported by theory or empirical results.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "34hBLsS9cyF", "reviewer": "Reviewer_QYEL", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall, I like the paper. However the main issue for me was that I could not clearly see the relation between CGD and LOLA. This seems to be an important correction to existing claims. However, the paper says that this is not a rigorous proof of the correction. The problem is that if an existing claims is incorrect than it is useful to correct it as soon as possible. However, the proof of correction should be quite clear. I did not find that to be the case. Ideally, it would be nice to first say that the existing claim says that series expansion will look like this and while doing so they forgot about this particular term that seems to appear in LOLA’s loss and thus the correction to the existing claim. \nOverall, I think even just this correction could be a sufficient contribution for publication. \n\nThe paper claims that COLA follows a consistent update rule. However, empirically COLA does not converge to a a Tit-for-Tat strategy as desired (or as LOLA does). Then what is the motivation behind using COLA over LOLA?\n\nI am not sure of what is the original claim form the CGD paper and if it is correctly interpreted in this paper. It seems that the original claims from the CGD paper is series expansion of CGD recovers HOLA (high order LOLA). The paper says that this implies CGD is equal to iLOLA. I am not sure how this is true. \n\nWhile I have other minor points, but I think the claim regarding the original claim from CGD paper and its correction should be first made clear.", "summary_of_the_paper": "This paper deals with the problem of learning in differentiable games. Mainly the paper tackles the problem of learning in games while taking into account the learning of the opponent as well. The main contribution of the paper is to point out a flaw in the existing claims regarding correspondence between competitive gradient descent and iLOLA. The paper further gives a definition of consistent update rules for differentiable games and based on this definition show that iLOLA is update rule is consistent. The paper proposes a new algorithm COLA and shows that it find more consistent solutions empirically.\n", "summary_of_the_review": "I think my decision mainly depends on whether the claim that the paper makes a correction to the existing literature is true or not. And if the paper can it more clear. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "0-UKeGkXdGo", "reviewer": "Reviewer_hj7q", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**Strengths:** \n1. This paper studies closely related literature (i.e., LOLA, HOLA, CGD) and make interesting empirical observations to the community.\n2. COLA only requires up to second-order derivatives compared to iLOLA, which requires many higher-order derivatives.\n\n**Weaknesses/Concerns:**\n1. My main concern is COLA's benefit against SOS (Letcher et al., 2019). SOS not only has a theoretical convergence guarantee to SFPs while retaining the LOLA's opponent-shaping to achieve higher performance, if needed. However, COLA does not have a convergence guarantee and, COLA may perform worse than SOS when it does not converge to SFPs (e.g., COLA:0.1 in the Tandem game). Hence, it is unclear when COLA should be used instead of SOS. \n2. Could you clarify further on the consistency (Definition 1) regarding how it avoids the infinite regress problem? Specifically, Equation 5 is dependent on Equation 6 as Equation 5 includes $h_2$. Similarly, Equation 6 is dependent on Equation 5 as Equation 6 includes $h_1$. As a result, the infinite regress problem can arise when we replace $h_2$ in Equation 5 with Equation 6: to compute $h_1$ on the left-hand side of Equation 5, it requires $h_2$ in Equation 6, which then requires computation of $h_1$ in Equation 5 (and this recursion continues). \n3. While it is an interesting idea to learn the update functions $h_1$ and $h_2$ via neural networks (parameterized by $\\phi_1$ and $\\phi_2$), I am concerned about the scalability of this approach. When the dimension of $\\theta_1$ and $\\theta_2$ are small, then learning the update functions that output the dimension of $\\theta_1$ and $\\theta_2$ is possible. However, when $\\theta_1$ and $\\theta_2$ are policies represented by neural networks, then the dimension of $\\theta_1$ and $\\theta_2$ are large, which results in the difficulty of learning $h_1$ and $h_2$.\n4. In Figure 1, CGD is only compared in the Tandem domain. Why is CGD not compared in other domains, including matching pennies (competitive game)?\n5. This is minor, but it is difficult to understand the experimental results because Tables 1-2 and Figure 1 are not positioned near Section 6.", "summary_of_the_paper": "This paper investigates the inconsistency problem in LOLA: each LOLA agent assumes the other agent as a naive learner, resulting in LOLA agents not converging to SFPs in some games. This paper aims to address this problem by the infinite-order LOLA, which can have a consistent view of each other and empirically observes that HOLA may not resolve LOLA's convergence issues. Instead of HOLA, this paper proposes COLA that employs neural networks to explicitly minimize the consistency loss. COLA empirically shows that COLA finds the consistent solution when HOLA converges and finds more stable solutions when HOLA diverges. ", "summary_of_the_review": "I initially vote for a score of 3. While this paper finds interesting empirical observations to related works, I am unsure how it improves over the state-of-the-art approach in the literature, such as SOS. After reading the authors' responses to my questions, I am open to raising my score.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The main contribution of this paper is that it points out incorrect claims in the literature of multi-agent RL and provides new insight on the failure modes of current methods. Specifically, this paper investigates the inconsistency problem in LOLA (meaning it assumes the other agent as a naive learner, thus not converging to SFPs in some games). It then shows problems with two fixes in the literature: 1) HOLA addresses the inconsistency problem only when it converges; otherwise, HOLA does not resolve the issue. 2) GCD does not resolve the issue although it claims to do so. This paper then proposes a method COLA that fixes the inconsistency issue, which outperforms HOLA when it diverges. Reviewers generally agree that the insight from this work is interesting and important for the field. However, there were some concern on both the theory and the experiments. While the updated version addresses some of the concerns, it also made significant changes to both the theoretical and the empirical sections, and would benefit from another round of close review. Thus, I think the current version of this work is borderline.
Decision: Reject