Status-Quo Policy Gradient in Multi-agent Reinforcement Learning
Authors: Pinkesh Badjatiya
Mausoom Sarkar
Abhishek Sinha
Nikaash Puri
Jayakumar Subramanian
Siddharth Singh
Balaji Krishnamurthy
Venue:  (2021)
Keywords: multi-agent rl
reinforcement learning
social dilemma
policy gradient
game theory

Abstract: Individual rationality, which involves maximizing expected individual return, does not always lead to optimal individual or group outcomes in multi-agent problems. For instance, in social dilemma situations, Reinforcement Learning (RL) agents trained to maximize individual rewards converge to mutual defection that is individually and socially sub-optimal. In contrast, humans evolve individual and socially optimal strategies in such social dilemmas. Inspired by ideas from human psychology that attribute this behavior in humans to the status-quo bias, we present a status-quo loss (SQLoss) and the corresponding policy gradient algorithm that incorporates this bias in an RL agent. We demonstrate that agents trained with SQLoss evolve individually as well as socially optimal behavior in several social dilemma matrix games. To apply SQLoss to games where cooperation and defection are determined by a sequence of non-trivial actions, we present GameDistill, an algorithm that reduces a multi-step game with visual input to a matrix game. We empirically show how agents trained with SQLoss on a GameDistill reduced version of the Coin Game evolve optimal policies. 

Under review as a conference paper at ICLR 2021
STATUS- QUO POLICY GRADIENT IN MULTI-AGENT REINFORCEMENT LEARNING
Anonymous authors Paper under double-blind review
ABSTRACT
Individual rationality, which involves maximizing expected individual return, does not always lead to optimal individual or group outcomes in multi-agent prob- lems. For instance, in social dilemma situations, Reinforcement Learning (RL) agents trained to maximize individual rewards converge to mutual defection that is individually and socially sub-optimal. In contrast, humans evolve individual and socially optimal strategies in such social dilemmas. Inspired by ideas from human psychology that attribute this behavior humans to the status-quo bias, we present status quo loss (SQ Loss) and the corresponding policy gradient al- gorithm that incorporates this bias in an RL agent. We demonstrate that agents trained with SQLoss evolve individually as well as socially optimal behavior in several social dilemma matrix games. To apply SQLoss to games where co- operation and defection are determined by sequence of non-trivial actions, we present Game Dislill, an algorithm that reduces a multi-step game with visual input to a matrix game. We empirically show how agents trained with SQLoss on a Game Distill reduced version of the Coin Game evolve optimal policies.
INTRODUCTION
In sequential social dilemmas, individually rational behavior leads to outcomes that are sub-optimal for each individual in the group (Hardin 1968; Ostrom 1990 Ostrom et al.) 1999 Dietz et al.)
2003}. Current state-of-the-ar Multi-Agent Deep Reinforcement Learning (MARL) methods that train agents independently can lead to agents that play selfishly and do not converge to optimal policies, even in simple social dilemmas (Foerster et al.] 2018 Lerer Peysakhovich 2017).
To illustrate why it is challenging to evolve optimal policies in such dilemmas, we consider the Coin Game (Foerster et al. 2018). Each agent can play either selfishly (pick all coins) or cooperatively (pick only coins of its color). Regardless of the other agent's behavior, the individually rational choice for an agent is to play selfishly, either to minimize losses (avoid being exploited) or to maxi- mize gains (exploit the other agent). However, when both agents behave rationally, they try to pick all coins and achieve an average long term reward of -0.5. In contrast, if both play cooperatively. then the average long term reward for each agent is 0.5. Therefore, when agents cooperate, they are both better off. Training Deep RL agents independently in the Coin Game using state-of-the-arn methods leads to mutually harmful selfish behavior (Section 2.2).
The problem of how independently learning agents evolve optimal behavior in social dilemmas has been studied by researchers through human studies and simulation models (Fudenberg & Maskin
1986 Green & Porter 1984 Fudenberg et al. 1994 Kamada & Kominers 2010 et al. | 1990).
A large body of work has looked the mechanism of evolution of cooperation through reciprocll
behaviour and indirect reciprocity (Trivers) 1971: Axelrod 1984 Nowak & Sigmund, 1992 1993
1998), through variants of reinforcement using aspiration (Macy & Flache 2002), attitude (Damer &
Gini 2008) multi-agent reinforcement learning (Sandholm & Crites 1996 Wunder et al. 20100).
and under specific conditions (Banerjee & Sen 2007) using different learning rates (de Cote et al,
2006) similar to WoLF (Bowling & Veloso, 2002) as well as using embedded emotion (Yu et al.
2015 social networks (Ohtsuki et al. 2006
Santos & Pacheco 2006).
However, these approaches do not directly apply to Deep RL agents (Leibo et al. 2017). Recent work in this direction (Kleiman- Weiner et al.) 2016)] Julinn et al.] Peysakhoihh & Lerer 2018) focuses letting agents learn strategies in multi-agent settings through interactions with

---

Under review as a conference paper at ICLR 2021
other agents. Leibo al. (2017) defines the problem of social dilemmas in the Deep RL framework and analyzes the outcomes of a fruit- gatheriggg game (Julien et al. 2017). They vary the abundance of resources and the cost of conflict in the fruit environment generate degrees of cooperation between agents. Hughes et al. (0188) defines an intrinsic reward (inequality aversion) that attempts to reduce the difference in obtained rewards between agents. The agents are designed to have an aversion to both advantageous (guilt) and disadvantageous (unfairness) reward allocation. This handcrafting of loss with mutual fairness evolves cooperation, but it leaves the agent vulnerable to exploitation. LOLA (Foerster et al. 2018) uses opponent awareness to achieve high cooperation levels in the Coin Game and the Iterated Prisoner's Dilemma game. However, the LOLA agent assumes access to the other agent's network architecture, observations, and learning algorithms. This access level is analogous to getting complete access to the other agent's private information and therefore devising strategy with full knowledge of how they are going to play. [Wagg et al.] (2019) proposes an cvolutionary Deep RL setup to evolve cooperation. They define an intrinsic reward that is based on features generated from the agent's 's past and future rewards, and this reward is shared with other agents. They use evolution to maximize the sum of rewards among the agents and thus evolve cooperative behavior. However, sharing rewards in this indirect way enforces cooperation rather than evolving it through independently learning agents.
Interestingly, humans evolve individual and socially optimal strategies in such social dilemmas with- out sharing rewards or having access to private information. Inspired by ideas from human psychol- ogy (Samuelson & Zeckhauser, 1988 Kahneman et al.) 1991 Kahneman [001 Thaler Sunstein 2009) that attribute this behavior in humans to the status-quo bias (Guney & Richter| 2018)) we present the SQLoss and the corresponding status-quo policy gradient formulation for RL. Agents trained with SQLoss evolve optimal policies in multi-agent social dilemmas without sharing re- wards, gradients, or using a communication channel. Intuitively, SQLoss encourages an agent to stick to the action taken previously, with the encouragement proportional to the reward received previously. Therefore, mutually cooperating agents stick to cooperation since the status-quo yields higher individual reward, while unilateral defection by any agent leads to the other agent also switch- ing to defection due to the status-quo loss. Subsequently, the short-term reward exploitation is overcome by the long-term cost of mutual defection, and agents gradually switch to cooperation.
To apply SQLoss to games where a sequence of non-trivial actions determines cooperation and defection, we present Gistlls an algorithm that reduces dynamic game with visual input to a matrix game. GomeDistill uses self superviseii and clustering to extract distinct policies from a sequential social dilemma game automatically.
Our key contributions can be summarised as:
1.
We introduce Ptatus-Quo loss (SQLoss, Section 2.3) and associated policy gradient- based algorithm to evolve optimal behavior for agents playing matrix games that can act in either cooperative or a selfish manner, by choosing between a cooperative and selfish policy. We empirically demonstrate that agents trained with the SQLoss evolve optimal behavior in several social dilemmas iterated matrix games (Section
2. We propose GameDistill (Section 2.4). an algorithm that reduces social dilemma game with visual observations to an iterated matrix game by extracting policies that implement cooperative and selfish behavior. We empirically demonstrate that Gistiistill extracts cooperative and selfish policies for the Coin Game (Section 4.2
3. We demonstrate that when agents GimeDistill followed by MARL game-play using S SQLoss. they converge to individually as well as socially desirable cooperative behavior in a social dilemma game with visual observations (Section 4.2p
2 APPROACH
2.1 SOCIAL DILEMMAS MODELED AS ITERATED MATRIX GAMES
To remain consistent with previous work, we adopt the notations from Foerster et al. (2018). We model social dilemmas as general-sum Markov (simultaneous move) games. A multi-agent Markov game is specified by G = (S, A, U. P.r, n, 7)- S denotes the state space of the game, denotes the
2

---

Under review as a conference paper at ICLR 2021
number of agents playing the game. At each step of the game, each agent a E A, selects an action u" E U. i7 denotes the joint action vector that represents the simultancous actions of all agents. The joint action ūī changes the state of the game from to s' according to the state transition function
P(s"(z,, 8) S x U x S + [0, 1]. At the end of each step, each agent a gets a reward according to the reward function r r'ss, 87 S U R. The reward obtained by an agent each step is function of the actions played by all agents. For an agent a, the discounted future return from time t defined as R2 Li=o 7'r%,1- where 7 [0, 1) is the discount factor. Each agent independently attempts to maximize its expected discounted return.
Matrix games are the special case of two-player perfectly observable Markov games (Foerster et al, 2018). Table [ shows examples of matrix games that represent social dilemmas. Consider the Prisoner's Dilemma game in Table Ta Each agent can either cooperate (C) or defect (D). Playing D is the rational choice for an agent, regardless of whether the other agent plays C or D. Therefore, both agents play rationally, they each receive a reward of 22 However, each agent plays C, then it will obtain reward of 1. This fact that individually rational behavior leads to sub-optimal group (and individual) outcome highlights the dilemma.
In Infinitely Iterated Matrix Games, agents repeatedly play particular matrix game against each other. In each iteration of the game, each agent has access to the actions played by both agents in the previous iteration. Therefore, the state input to an RL agent consists of both agents' actions in the previous iteration of the game. We adopt this state formulation as is typically done in such games (Press & Dyson 2012 Foerster al. 2018). The infinitely iterated variations of the matrix games in Table Trepreeet sequential social dilemmas. We refer to infinitely iterated matrix games as iterated matrix games in subsequent sections for ease of presentation.
2.2 LEARNING POLICIES IN ITERATED MATRIX GAMES: THE SELFISH LEARNER
The standard method to model agents in iterated matrix games is to model each agent as an RL agent that independently attempts maximize its expected total discounted reward. Several approaches to model agents in this way use policy gradient-based methods (Sutton et al. 2000 Williams 1992).
Policy gradient methods update an agent's policy, parameterized by 09, by performing gradient ascent on the expected total discounted reward E[R]]- Formally, let 6 denote the parameterized version of an agent's policy x" and Vol ,0 denote the total expected discounted reward for agent a.
Here, Va is function of the policy parameters (0), 8²) of both agents. In the 1th iteration of the game, each agent updates 0e to 0 such that it maximizes it's total expected discounted reward. 01 is computed as follows:
0 argmazgs
0?) and 6.1 argmaage (²,
For agents trained using reinforcement learning, the gradient ascent rule to update 0/44 is,
ful V V (0), 0?) and G!.1 0: (m!
where 8 is the step size of the updates. In the Iterated Prisoner's Dilemma (IPD) game, agents trained with the policy gradient update method converge to a sub-optimal mutual defection equilibrium (Fig- ure 3al Lerer & Peysakhovich (2017). This sub-optimal equilibrium attained by Selfish Learners motivates us to explore alternative methods that could lead to a desirable cooperative equilibrium. We denote the agent trained using policy gradient updates as Selfish Learner (SL).
2.3 LEARNING POLICIES IN ITERATED MATRIX GAMES: THE STATUS-QUU AWARE LEARNER (SQLoss)
Figure ! shows the high-level architecture of our approach.
2.3.1 SQLoss: INTUITION
Why do independent, selfish learners converge to mutually harmful behavior in the IPD? To under- stand this, consider the payoff matrix for a single iteration of the IPD in Table Ia In each iteration, an agent can play either C' or D. Mutual defection (DD) is worse for each agent than mutual coop- eration (CC). However, one-sided exploitation (DC or CD) is better than mutual cooperation for the exploiter and far worse for the exploited. Therefore, as long as agent perceives the possibility
3

---

Under review as a conference paper at ICLR 2021
Roncom supervised Encoder
Clustering
SCLLeamer
Felignal
Delection cluster
losued
Sana
Orida
Dhatk
Ooce
Reward
Cooperation ciucer
orade
Collection of daried from random gamuplay
GameDistill
Vecter
Figure 1: High-level architecture of our approach. Each agent runs GameDistill by performing steps (2), (3) individually to obtain two oracles per agent. During game-play( (4), each agent (with SQLoss) takes either the action suggested by the cooperation or the defection oracle
of exploitation, it is drawn to defect, both maximize the reward (through exploitation) and mini- mize its loss (through being exploited). To increase the likelihood of cooperation, it is important to reduce instances of exploitation between agents. We posit that, agents either mutually cooperate (CC) or mutually defect (DD), then they will learn to prefer C over D and achieve a socially desir- able equilibrium. (for a detailed illustration the evolution cooperation, see Appendix which is part of the Supplementary Material)
Motivated by ideas from human psychology that attribute cooperation in humans to the status-quo bias (Guney & Richter 2018), we introduce status-quo loss (SQLoss) for each agent, derived from the idea of imaginary game-play (Figure[) ( Intuitively, the loss encourages an agent to imag- ine an episode where the status-quo (current situation) is repeated for several steps. This imagined episode causes the exploited agent (in DC) to perceive a continued risk of exploitation and, there- fore, quickly move to (DD). Hence, for the exploiting agent, the short-term gain from exploitation (DC)) is overcome by the long-term loss from mutual defection (DD). Therefore, agents move towards mutual cooperation (CC) or mutual defection (DD). With exploitation (and subsequently, the fear of being exploited) being discouraged, agents move towards cooperation.
[an]
[a,)
(a:)*
Status-Quo
aware Learner [SQLeamer)
S2
Ss
30
a1
B2
F
S2
S2
Figure 2: Intuition behind Status Quo-aware learner. At each step, the SQLoss encourages an agent imagine the consequences of sticking to the status-quo by imagining episode where the status-quo repeated for i steps. Section 2.3 describes SQLoss in more detail.
2.3.2 SQLoss: FORMULATION
We describe below the formulation of SQLoss with respect to agent 1. The formulation for agent 2 is identical to that of agent 1. Let = (So. ug. uß. ro. .. ST, ut, u² r+) denote the collection of agent's experiences after T time steps. Let R/ (T,
Σt " - denote the discounted future return for agent starting at in actual game-play. Let `j denote the collection of an agent's 's imagined experiences. For a state St, where at s; and repeating ui-1- -²_ for Ke steps. This is equivalent to imagining
[0, an agent imagines an episode by starting
step repetition of already played actions. We sample K2 from Discrete Uniform distribution Uf1, 2} where 2 is prper-parameter 2 1. To simplify notation, let o, (St, fir) denote the ordered set of state, actions, and rewards starting time and repeated K; times for imagined game-play. Let R! (fz) denote the discounted future return starting at s, in imagined status- game-play.
(1 K2) = [S... ui-1, 2f r Dos (st, ut 1f ... (st, 4t 1s u² 1 1))m
4

---

Under review as a conference paper at ICLR 2021
è Ke), (st+1, u4 u2t1 144))a+1 (ST, up, uēi (r)++x-))
(4)
T
(((t))= -1- (Ti) =
r/11
(5)
Vi and V.J are approximated by (T)) and (() ) respectively. These V values
the expected rewards conditioned on both agents' policies (œ )²). For Foragent 1, the regular gradients and the Status-Quo gradients, Vga E. (())(T))) and V R [ (f)) can be derived from the policy gradient formulation
V p ( ([ (Ti) E
Vallogn (u!lst)
1=t
(6)
= E
o loga (B(()) b(s)))
VoI = E [ (1 Volloy
V
t Σ
E
V Vollogr (1))))
M Σ 1
1=t
(1-1-)) -
Σx'rt)
(7)
Vo LolgT (1/_1)
7
Imt.
E
V Volg (u
(m (1s)))))) (R)(t)) (R - b(si))
where b(s;) is a baseline for variance reduction.
Then the update rule fegl.p for the policy gradient-based Status-Quo Learner (SQL-PG) is,
fagtps = (a- (TT + 3 (oLE((((T))) 8
(8)
where a, B denote the loss scaling factor for REINFORCE, imaginative game-play play respectively.
2.4 LEARNING POLICIES IN DYNAMIC NON-MATRIX GAMES USING SQ AND Game
The previous section focused on evolving optimal policies in iterated matrix games that represent sequential social dilemmas. In such games, an agent can take one of a discrete set of policies at each step. For instance, IPD, an agent can either cooperate or defect at each step. However, in social dilemmas such as the Coin Game (Appendix A), cooperation and defection policies are composed of a sequence of dependep actions. To apply the Status-Qur policy gradient to these games, we present KkamDDistlle to a matrix game. Distill takes as input game-play episodes between agents with random policies and learns oracles (or policies) that lead distinct outcomes. Game Distill (Figure 1 works as follows.
self-supervised algorithm that reduces dynamic game with visual input
1. We initialize agents with random weights and play them against each other in the game. In these random game-play episodes, whenever an agent receives reward, we store the sequence of states along with the rewards for both agents.
2. This collection of state sequences is used to train the GameDistill network, which is self-supervised trajectory encoder. It takes as input a sequence of states and predicts the rewards of both agents during training.
3. We then extract the embeddings from the penultimate layer of the trained Bistill network for each state sequence. Each embedding is a mimen-dimmnsional representation of the corresponding state sequence. We cluster these embeddings using Agglomerative Clustering (Priedman et al., 200T). Each cluster represents a collection of state sequences that lead to consistent outcome (with respect rewards). For the Coin Game, when
5

---

Under review as a conference paper at ICLR 2021
T
C
D
C
(-1, -1)
(-3, 0)
(+1,-1)
(11,+1)
(0, O)
(-4, -1)
D
(0, -3)
(-2, 2)
T
(-1,+1)
(+1,-1)
D
(-1,
(-3, -3)
(a) Prisoners' Dilemma (PD)
(b) Matching Pennies (MP)
(c) Stag Hunt (SH)
Table 1: Payoff matrices for the different games used in our experiments. (X, Y) in cell represents reward of X the row and Y to the column player. C, D, H, and T denote the actions for the row and column players. In the iterated versions of these games, agents play against each other over several iterations. In each iteration, agent takes action and receives reward based the actions of both agents. Each matrix represents different kind of social dilemma.
the number of clusters 2, find that cluster consists of state sequences that represent cooperative behavior (cooperation cluster) while the other cluster represents state sequences that lead to defection (defection cluster).
4. Using the state sequences in each cluster, we train an oracle to predict the next action given the current state. For the Coin Game, the oracle trained on state sequences from the cooperation cluster predicts the cooperative action for given state. Similarly, the oracle trained on the defection cluster predicts the defection action for given state. Each agent uses Game Distill independently to extract a cooperation and defection oracle. Figure (Appendix (D.4) illustrates the cooperation and defection oracles extracted by the Red agent using GameDislile
During game-play, an agent can consult either oracle at each step. In the Coin Game, this is equiva- lent either cooperating (consulting the cooperation oracle) defecting (consulting the defection oracle). In this way, an agent reduces a dynamic game to its matrix equivalent using GameDistill We then apply the Status-Quu Quo policy gradient evolve optimal policies in this matrix game. For the Coin Game, this leads to agents who cooperate by only picking coins of their color (Figure 4a). It is important to note that for games such as the Coin Game, we could have also learned cooperation and defection oracles by training agents using the sum of rewards for both agents and individual reward, respectively (Lerer & Peysakhovich) 2017). However, GameDistill learns these distinct policies without using hand-crafted reward functions.
Appendix B provides additional details about the architecture and pseudo-code for Distill.
EXPERIMENTAL SETUP
In order to compare our results to previous work, we use the Normalized Discounted Reward or NDR = (1 7) Et= y'r,. A higher NDR implies that an agent obtains a higher re- ward in the environment. We compare approach (Status-Quo Aware Learnr SQLearner) to Learning with Opponent-Learning
Awareness (Lola-PG) (Foerster et al., 2018) and the Self- ish Learner (SL) agents. For all experiments, perform 20 runs and report average NDR, along with variance across runs. The bold line all the figures is the mean, and the shaded region is the standard deviation region around the mean. All of code is available at http:/thhh.....oeeea//aee/ wtt.:/cco/useeeeee 2AR223/MARL-S with-witthheee -wt.--wttt-SSSSssss
3.1 ITERATED MATRIX GAME SOCIAL DILEMMAS
For our experiments with social dilemma matrix games. we use the Iterated Prisoners Dilemma (IPD) (Luce& & Raiffa 1989). Iterated Matching Pennies (IMP) (Lee & Louis] 1967), and the Iterated Stag Hunt (ISH) (Fang al. 2002). Each matrix game in Table represents different dilemma. In the Prisoner's Dilemma, the rational policy for each agent is to defect, regardless of the other agent's s policy. However, when each agent plays rationally, each worse off. In Matching Pennies, an agent plays predictably, it is prone to exploitation by the other agent. Therefore, the optimal policy to randomize between H and T, obtaining an average NDR of O. The Stag Hunt game represents coordination dilemma. In the game, given that the other agent will cooperate, an agent's 's optimal action is to cooperate as well. However, each agent has an attractive alternative at each step, that of defecting and obtaining a guaranteed reward of 11 Therefore, the promise of safer alternative

---

Under review as a conference paper at ICLR 2021
-0.8
-1.0
Acarage Mermakaeee Diooourted
25
-12
2.0
1.6
Ldle
-18
SCLeame
-20
-2.2
500
1000
1500
2000
202
450
1500
Iterations
Itentioos
(a)
(b)
Figure 3: (a) Average NDR values for different learners in the IPD game. SQLearner agents obtain near-optimal NDR value (-1) for this game. (b) Average NDR values for different learners in the IMP game. SQLearner agents avoid exploitation by randomising between H and T to obtain near-optimal NDR value (0) for this game.
and the fear that the other agent might select the safer choice could drive an agent to select the safer alternative, thereby sacrificing the higher reward of mutual cooperation.
In iterated matrix games, at each iteration, agents take an action according to a policy and receive the rewards in Table To simulate an infinitely iterated game, we let the agents play 200 iterations of the game against each other, and do not provide an agent with any information about the number of remaining iterations. In an iteration, the state for an agent is the actions played by both agents in the previous iteration.
3.2 ITERATED DYNAMIC GAME SOCIAL DILEMMAS
social dilemma with extended actions, the Coin Game (Fig- ure 5ab (Foerster et al. 2018) and the non-matrix variant of the Stag Hunt (Figure 5b). We provide details of these games in Appendix due to space considerations.
For experiments
4 RESULTS
4.1 LEARNING OPTIMAL POLICIES IN ITERATED MATRIX DILEMMAS
We train different learners to play the IPD game. Figure 3a shows the results. For all learners, agents initially defect and move towards NDR of -200. This initial bias towards defection is expected, since, for agents trained with random game-play episodes, the benefits of exploitation outweigh the costs of mutual defection. For Selfish Learner (SL.) agents, the bias intensifies, and the agents converge to mutually harmful selfish behavior (NDR of -2.0). Lola-PG agents learn predict each other's behavior and realize that defection more likely to lead to mutual harm. They subsequently move towards cooperation, but occasionally defect (NDR of 1.2). contrast, SQLearner agents quickly realize the costs of defection, indicated by the small initial dip in the NDR curves. They subsequently move towards close to 100% cooperation, with an NDR 1.0. Finally, important to note that SQaarneer agents have close to zero variance, unlike other methods where the variance in NDR across runs is significant.
Iterated Prisoner's Dilemma (IPD):
Iterated Matching Pennies (IMP): We train different learners to play the IMP game. Figure 3b shows the results. SQLearner agents Iearn to play optimally and obtain NDR close to 0. Interestingly, Selfish Learner and Lola-PG agents converge to an exploiter-exploite equilibrium where agent consistently exploits the other agent. This asymmetric exploitation equilibrium is more pronounced for Selfish Learner agents than for Lola-PG agents. As before, we observe that SQLearner agents have close to variance across runs, unlike other methods where the variance in NDR across runs is significant.
Iterated Stag Hunt (ISH): Appendix D.5 shows additional results for the ISH game.

---

Under review as a conference paper at ICLR 2021
4.2
LEARNING OPTIMAL POLICIES IN ITERATED DYNAMIC DILEMMAS
10
25
-50
25 50
(a)
(b)
Figure 4: (a) Probability that agent will pick coin of its color in Coin Game. (b) Representation of clusters obtained after Game Distill. Each point is a t-SNE projection of the 100-dimensional feature vector output by the GameDiställ Distill network for input sequence of states. The figure on the left is colored based on rewards obtained by the Red and Blue agents. The figure on the right is colored based on clusters learned by Gimelistill.
GameDistill: To evaluate the Agglomerative clustering step in GameDislil we make two t- SNE (Maaten & Hinton, 2008) plots of the 100-dimensional feature vectors extracted from the penultimate layer of the trained Game:Dsstill network in Figure 4b In the first plot, we color each point (or state sequence) by the rewards obtained by both agents in the format Ti r1(r2- In the second, we color each point by the cluster label output by the clustering technique. Gistlistill correctly learns two clusters, one for state sequences that represent cooperation (Red cluster) and the other for state sequences that represent defection (Blue cluster). We experiment with different values for feature vector dimensions and obtain similar results (see Appendix B for details). Results on Stag Hunt using GameDiställ are presented in Appendix D.3 To evaluate the trained oracles that represent cooperation and defection policy, we alter the Coin Game environment to contain only a single agent (the Red agent). We then play two variations of the game. In the first variation, the Red agent is forced to play the action suggested by the first oracle. In this variation, we find that the Red agent picks only 8.4% of Blue coins, indicating high cooperation rate. Therefore, the first oracle represents cooperation policy. In the second variation, the Red agent is forced to play the action suggested by the second oracle. We find that the Red agent picks 99.4% Blue coins, indicating high defection rate, and the second oracle represents defection policy.
During game-play, at each step, an agent follows either the action suggested by its cooper- ation oracle the action suggested by its defection oracle. We compare approaches using the degree of cooperation between agents, measured by the probability that an agent will pick the coin of its color (Foerster al. 2018). Figure 4a shows the results. The probability that SQLearner agent will pick the coin of its color is close to 1. This high probability indicates that the other SQLearner agent is cooperating with this agent and only picking coins of its color. In contrast, the probability that a Lola-PG agent will pick a coin of its color is close to 0.8, indicating higher defection rates. As expected, the probability of agent picking its own coin is the smallest for the selfish learner (SL).
SQ Loss:
CONCLUSION
We presented status policy gradient inspired by human psychology that encourages an agent to imagine the counterfactual of sticking to the status quo. We demonstrated how agents trained with SQLoss evolve optimal policies in several social dilemmas without sharing rewards, gradients, or using a communication channel. To work with dynamic games, we proposed Game Distill, an algo- rithm that reduces a dynamic game with visual input to matrix game. We combined GameDistil and Loss to demonstrate how agents evolve optimal policies dynamic social dilemmas with visual observations.
8

---

Under review as a conference paper at ICLR 2021
REFERENCES
Dilip Abreu, David Pearce, and Ennio Stacchetti. Toward theory of discounted repeated games with imperfect monitoring. Econometrica, 5845):04111163,, 1990. ISSN 00129682, 14680262. URL http:httpp/tttt
Robert Axelrod. Robert Axelrod's (1984) The Evolution of Cooperation. Basic Books, 1984.
Dipyaman Banerjee and Sandip Sen. Reaching pareto-optimality in prisoner's dilemma using con- ditional joint action learning. Autonomous Agents and Mulii-Agent Systems, 15(1), August 2007.
ISSN 1387-2532.
Michael Bowling and Manuela Veloso. Multiagent learning using a variable learning rate. Artificial Intelligence, (66())22152550) April 2002. ISSN 0004-3702.
Steven Damer and Maria Gini. Achieving cooperation in minimally constrained environment. volume 1, pp. 57-62, 01 2008.
Enrique Munoz de Cote, Alessandro Lazaric, and Marcello Restelli. Learning to cooperate in multi- agent social dilemmas. In Proceedings of the Fifth International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS '06, 2006.
Thomas Dietz, Elinor Ostrom, and Paul C. Stern. The struggle govern the commons. Science, 302(5652) 2003. doi: 10.1 1at/science.1091011.
Christina Fang, Steven Orla Kimbrough, Stefano Pace, Annapurna Valluri, and Zhiqiang Zheng. On adaptive emergence of trust behavior the game stag hunt. Group Decision and Negotiation, 11(6):449 467, 2002.
Jakob Foerster, Richard Y Chen. Maruan Al-Shedivat, Shimon Whiteson, Pieter Abbeel, and Igor Mordatch. Learning with opponent-leaming awareness. In Proceedings of the 17th International Conference on Autonomous Agents and MultiA MentiAgent gent Systems, pp. 122-130. International Founda- tion for Autonomous Agents and Multiagent Systems, 2018
Jerome Friedman, Trevor Hastie, and Robert Tibshirani. The elements of statistical learning, vol- ume Springer series in statistics New York, 2001.
Drew Fudenberg and Eric Maskin. The folk theorem in repeated games with discounting or with incomplete information. Econometrica, 54(3):533-555 554, 1986. ISSN 00129682, 14680262.
Drew Fudenberg, David Levine, and Eric Maskin. The folk theorem with imperfect public in- formation. Econometrica, 62(5)9977-033, 1994. ISSN 00129682, 14680262. URL http:
7/www. jstor. wwtp:/oog//aaaaaa wtt.or//g..aa/eeeeeeeeeeeeee
Edward Green and Robert H Porter. Noncooperative Collusion under Imperfect Price Information. Econometrica, 52(1))87-100, 1984.
Begum Guney and Michael Richter. Costly switching from status quo. Journal of Economic Behavior & Organization, 156:55-70, 2018.
Garrett Hardin. The tragedy of the commons. Science, 12233 1968. doi: 10.1 Secence.122.385.. 1243.
Edward Hughes, Joel Z. Leibo, Matthew Phillips, Karl Tuyls, Edgar Dueñez Guzman, Anto- nio Gareía Castañeda, lain Dunning, Tina Zhu, Kevin McKee, Raphael Koster, Heather Roff, and Thore Graepel. Inequity aversion improves cooperation in intertemporal social dilemmas. In Proceedings of the 32Nd International Conference on Neural Information Processing Systems, NIPS' 18, 2018
Pérolat Julien, JZ. Leibo, V Zambaldi, C Beattie, Karl Tuyls, and Thore Graepel. A multi-agent reinforcement learning model of common-pont resource appropriation. In Proceedings of the 31 International Conference on Neural information Processing Systems, NIPS' 17, 12 2017.
Daniel Kahneman. Thinking, fast and slow. Macmillan, 2011.

---

Under review as a conference paper at ICLR 2021
Daniel Kahneman, Jack L Knetsch, and Richard H Thaler. Anomalies: The endowment effect, loss aversion, and status quo bias. Journal of Economic perspectives, 5(1): 206, 1991.
Yuichiro Kamada and Scott Kominers, Information can wreck cooperation: A counterpoint to kan- dori (1992). Economics Letters, 107:112-114, 05 2010. doi: 00.1016f.ccomlee.209...... 12.0000009.00.......
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014.
Max Klennan-Weiner, Mark K Ho, Joseph Austerweil, Michael Littman, and Joshua Tenen- baum. Coordinate to cooperate compete: abstract goals and joint intentions in social interac- tion. In CogSci, 2016.
King Lee and K Louis. The Application of Decision Theory and Dynamic Programming to Adaptive Control Systems. PhD thesis, 1967.
Joel Z. Leibo, Vinicius Zambaldi, Marc Lanctot, Janusz Marecki, and Thore Graepel. Multi-agent reinforcement learning in sequential social dilemmas. In Proceedings of the 16th Conference Autonomous Agents and MultiAgent Systems, AAMAS 117. International Foundation for Au- tonomous Agents and Multiagent Systems, 2017.
Adam Lerer and Alexander Peysakhovich. Maintaining cooperation in complex social dilemmas using deep reinforcement learning, 2017.
R Duncan Luce and Howard Raiffa. Games and decisions: Introduction and critical survey. Courier Corporation, 1989.
Laurens van der Maaten and Geoffrey Hinton. learning research, (NNo)):5579-2666 2008
Visualizing data using t-sne. Journal of machine
Dr Macy and Andreas Flache. Learning dynamics in social dilemmas. Proceedings of the National Academy of Sciences of the United States of America, 99 Suppl 3:7229-36, 06 2002. doi: 10.
1073/pnas.0920800 092080099.
Martin Nowak and Karl Sigmund. A strategy of win-stay, lose-shift that outperforms tit-for-tat in the prisoner's s dilemma game. Nature, 364:56-8, 08 1993. doi: 10.1038/364056a..
Martin A. Nowak and Karl Sigmund. Tit for tat heterogeneous populations. Nature, 355(6357); 250-253, 1992.
Martin A. Nowak and Karl Sigmund. Evolution of indirect reciprocity by image scoring. Nature, 393(6685):573-577, 1998.
Hisashi Ohtsuki, Christoph Hauert, Erez Lieberman, and Martin Nowak. A simple rule for the evolution of cooperation graphs and social networks. Nature, 441(7092):5025505 doi: 10.8//aarrr00 URL
2006. ISSN 1476-4687.
hature046051
E. Ostrom. Governing the commons- The evolution of institutions for collective actions. Political economy of institutions and decisions, 1990.
Elinor Ostrom, Joanna Burger, Christopher B. Field, Richard B. Norgaard, and David Policansky.
Revisiting the commons: Local lessons, global challenges. Science, 284(5412):278 282, 1999.
doi: 10.1 122./siieccce224554222....
Alexander Peysakhovich and Adam Lerer. Consequentialist conditional cooperation in social dilem- mas with imperfect information. In International Conference Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 May 3, 2018, Conference Track Proceedings, 2018.
William H Press and Freeman Dyson. Iterated prisoner's dilemma contains strategics that dominate any evolutionary opponent. Proceedings of the National Academy of Sciences, 109(26): 10409- 10413, 2012.
William Samuelson and Richard Zeckhauser. Status quo bias in decision making. Journal of risk and uncertainty, 1(1::7-59, 1988.
10

---

Under review as a conference paper at ICLR 2021
Tuomas W. Sandholm and Robert H. Crites. Multiagent reinforcement learning in the iterated pris- oner's dilemma. Bio Systems, 37 1-2:147-66 1996.
Felipe Santos and J Pacheco. A new route to the evolution of cooperation. Journal of evolutionary biology, 19:726-33, 06 2006. doi: 10.1111/1120--901..205 200..000........
Richard Sutton and Andrew G Barto. Reinforcement learning: introduction. 2011.
Richard Sutton, David McAllester, Satinder Singh, and Yishay Mansour. Policy gradient methods for reinforcement learning with function approximation. Advances in neural informa- tion processing systems, pp. 1057-1063, 2000.
Richard H Thaler and Cass R Sunstein. Nudge: Improving decisions about health, wealth, and happiness. Penguin, 2009.
Robert Trivers. The evolution of reciprocal altruism. Quarterly Review of Biology, 46:35-57, 57., 03 1971. doi: 10.1086/406755.
Jane X. Wang, Edward Hughes, Chrisantha Fernando, Wojciech M. Czarnecki, Edgar A. Duéñiez Guzmán, and Joel Z. Leibo. Evolving intrinsic motivations for altruistic behavior. Proceedings of the 18th International Conference Autonomous Agents and MultiAgent Systems, AAMAS '19, pp. 692. International Foundation for Autonomous Agents and Multiagent Systems, 2019. ISBN 978-1-4503-6339-9
Ronald J Williams. Simple statistical gradient-followin algorithms for connectionist reinforcement learning. Machine learning, 8(3-4):229-256, 1992.
Michael Wunder, Michael Littman, and Monica Babes. Classes of multiagent q-learning dynamics with e-greedy exploration. In Proceedings of the 27th International Conference on International Conference on Machine Learning, ICML' 10, 2010.
C. Yu, M. Zhang, F. Ren, and G. Tan. Emotional multiagent reinforcement learning in spatial social dilemmas. IEEE Transactions on Neural Networks and Learning Systems, 26(1 (611))30833306 2015.

---

Under review as a conference paper at ICLR 2021
Appendix for STATUS-QUE QUO POLICY GRADIENT IN MULTI-AGENT REINFORCEMENT LEARNING
A DESCRIPTION OF ENVIRONMENTS USED FOR DYNAMIC SOCIAL DILEMMAS
LP DOOON
(a)
(b)
Figure 5: Illustraiion two agents (Red and Blue) playing the dynamic games: (a) Coin Game and
the (b) Stag- Stag-Hunt Game
A.1 COIN GAME
Figure illiuusstsstes the agents playing the Coin Game. The agents, along with a Blue or Red coin. appear at random positions in 3 3 grid. An agent observes the complete 3 grid as input and can move either left, right, up, down. When an agent moves into cell with a coin, it picks the coin, and a new instance the game begins where the agent remains their current positions, but a Red/Blue coin randomly appears in one of the empty cells. If the Red agent picks the Red coin, gets a reward of +1, and the Blue agent gets no reward. If the Red agent picks the Blue coin, gets reward of +1, and the Blue agent gets reward of -2. The Blue agent's 's reward structure is symmetric to that of the Red agent.
A.2 STAG-HUNT
Figure 5b shows the illustration of two agents (Red and Blue) playing the visual Stag Hunt game. The STAG represents the maximum reward the agents can achieve with HARE in the center of the figure. An agent observes the full
grid input and can freely move across the grid in only the empty cells, denoted by white (yellow cells denote walls that restrict the movement), Each agent can either pick the STAG individually obtain reward of +4, or coordinate with the other agent to capture the HARE and obtain better reward of +25.
B GameDistill: ARCHITECTURE AND PSEUDO-CODE
B. Gistlistill: ARCHITECTURE DETAILS
Game Distill consists of two components.
The first component is the state sequence encoder that takes as input sequence of states (input size 4 x 3 x 3, where 4 x the dimension of the game state, and the first index the state input represents the data channel where each channel encodes data from both all the different colored agents and coins) and outputs fixed dimension feature representation. We encode each state in the sequence using common trunk of convolution layers with relu activations and kernel-size 3 x 3, followed by a fully-connected layer with 100 neurons to obtain representation. This unified feature vector, called the trajectory embedding, is then given input
feature
12

---

Under review as a conference paper at ICLR 2021
the different prediction branches of the network. We also experiment with different dimensions of this embedding and provide results Figure
The two branches, which predict the self-reward and the opponent-reward (as shown in Figure I independently use this trajectory embedding as input to compute appropriate output. These branches take as input the trajectory embedding and dense hidden layer (with 100 neurons) with linear activation to predict the output. We use the mean-squared error (MSE) loss for the regression tasks in the prediction branches. Linear activation allows to cluster the trajectory embeddings using linear clustering algorithm, such as Agglomeratio we can choose the number of clusters based on our desired level of granularity in differentiating out- comes, In the games considered in this paper, agents broadly have two types of policies. Therefore, we fix the number of clusters to two.
Clustering (Friedman et al. (00T). In general,
We use the Adam KKngmma & Ba 2014) optimizer with learning-rate of 3e 3. We also experiment with K-Means clustering in addition to Agglomerative Clustering, and it also gives similar results. We provide additional results of the clusters obtained using GameDistil in Appendix D
The second component is the oracle network that outputs an action given state. For each oracle network, we encode the input state using 3 convolution layers with kernel-size 2 x 2 and relu activa- tion. To predict the action, we use 3 fully-connected layers with relu activation and the cross-entropy loss. We use L2 regularization, and Gradient Descent with the Adam optimizer (learning rate 1e 13 for all our experiments.
B.2 GameDistin PSEUDO-CODE
Algorithm 1: Pseduo-code for GameDistill
Collect list of episodes with rrl, from random game play;
for agents do
Create dataset: plisddps myRewards, ) + (11011111
for episode in episodes do
for (s,a,r,s") ) in episode do
if r > 0 then
add sequence of last three states leading up to s' listEpisodes: add respective rewards to myRewards and opponentRewards
end end
10
11
end
12
Train Sequence Encoding Network;
13
Train with NetLoss;
Cluster embeddings using Agglomerative Clustering:
15
Map episode to clusters from Step 14;
Train oracle for each cluster.
17 end
C SQsoss: EVOLUTION OF COOPERATION
Equation (Section terms. The logn (u. term maximises the likelihood of reproducing the training trajectories [s (t- (St, ur rr), (St+1, Ue+1, (t.1)..... The return term pulls down trajectories that have poor return. The overall effect is to reproduce trajectories that have high returns. We refer to this standard loss as Loss for the following discussion.
describes the gradient for standard policy gradient. It has two
Lemma 1. For agents trained with random exploration in the IPD, (=()ss)) > Q~ (C(ss) for all
13

---

Under review as a conference paper at ICLR 2021
Let (a))s) denote the expected return of taking a, in st. Let (sz)s denote the expected return from state St-
(x(C)CC) (C000-0-00(())(((00000000000))00
Q+(DCCC) = -100--0))0(0)))++((()))))))
Qx(CCDD) -2 +03)+
Q=(D(CD) - [..])((())))(((0D)))
(9)
Q+(CIDC) = -2 VV(
Q+(D)DC) = (D(]((D))++((DDD))
Qx(CIDD) -2 (.)]
Qx(DIDD) = -1+ (DG)),(D)++(((D))))
Since V, (CC VCD VDCDC) V (DD) for randomly playing agents, (D(sss (x(C(ss) for all st.
Lemma 2. Agents trained to only maximize the expected reward in IPD will converge to mutual defection.
Agents initially collect trajectories from random exploration. They use these trajectories to learn a policy that optimizes for a long-term return. These learned policies always play D as described in Lemma
This lemma follows from Lemma !
Equation 7 describes the gradient for SQLoss. The logn' (u/_1ls; term maximises the likelihood of taking # 8t. The imagined episode return pulls down trajectories that have poor imagined return.
Lemma 3. Agents trained on random trajectories using only SQLoss oscillate between CC and DD.
For IPD, 8; (u/_1, 1) The SQLoss maximises the likelihood of taking u in 8 when the return of the imagined trajectory (f, ) is high.
Consider state CC, with u/_1 C. x (DICC) is randomly initialised. The SQLoss term reduces the likelihood (CICC) because (tt) < O. Therefore, n'' (D|CC) > x (CICC).
Similarly, for CD, the SQLoss term reduces the likelihood of x (CICD)) Therefore, (DICD) (CCCD). For DC, R.((tt) = therefore (DCDDD > (C)DC). Interest- ingly, for DD, the SQLoss term reduces the likelihood of π (DDDD) and therefore π (DIDD).
Now, if is CC or DD, then st41 is DD or CC and these states oscillate. If s; is CD or DC,, then 8141 is DD, 8142 is CC and again CC and DD oscillate. This oscillation is key the emergence of cooperation as explained in section 2.3.1.
Lemma 4, For agents trained using both standard loss and SQLoss, T(CCCO) > N (DICC).
For CD, DC, both the standard loss and SQLoss push the policy towards D. For DD, with sufficiently high K, the SQLoss term overcomes the standard loss and pushes the agent towards C. For CC, initially. both the standard loss and SQLoss push the policy towards D. However, as training progresses, the incidence of CD and DC diminish because of SQLoss described in Lemma 3. Therefore, V=(DD) = V=(DC" since agents immediately move from both states to DD. Intuitively, agents lose the opportunity to exploit the other agent. In equation 9, with VCD Va(DC), (CICC) > (D(CCC)) and the standard loss pushes the policy so that (CICC) > TDDCCC). This depends on the value k. For very low values, the standard loss overcomes SQLoss and agents defect. For very high values, SQLoss overcomes standard loss, and agents oscillate between cooperation and defection. For moderate values of i (as shown in our experiments). the two loss terms work together so that π (CICC) > (D|CC)).
14

---

Under review as a conference paper at ICLR 2021
D EXPERIMENTAL DETAILS AND ADDITIONAL RESULTS
D.1 INFRASTRUCTURE FOR EXPERIMENTS
We performed all our experiments on an AWS instance with the following specifications. We use a 64-bit machine with Intel(R) XR) Platinum 8275CL CPU @ 3.00GHz installed with Ubuntu 16.04LTS operating system. It had a RAM of 189GB and 96 CPU cores with two threads per core. We use the TensorFlow framework for our implementation.
D.2 SQLoss
For our experiments with the Selfish and Status-Quo Aware Learner (SQLearner), gradient-base learning to train an agent with the Actor- method (Sutton & Barto (001)). Each agent is parameterized with policy actor and critic for variance reduction in policy updates. During training, we use a 1.0 for the REINFORCE and 3 = 0.5 for the imaginative game-play. We use gradient descent with step size, 5 0.005 for the actor and 6 1 for the critic. We size of 4000 for Lola-PG (Foerster et al.] 2018) and use the results from the original paper. We use batch size of 200 for SQLearner for roll-outs and an episode length of 200 for all iterated matrix games. We use a discount rate (7) of 0.96 for the Iterated Prisoners' Dilemma, Iterated Stag Hunt, and Coin Game For the Iterated Matching Pennies, we use ? 0.9 be consistent with earlier works. The high value of allows for long time horizons, thereby incentivizing long-term rewards. Each agent randomly samples & from E (1, (z 10, discussed in Appendix D.7 at each step.
policy
hatch
D.3 Distil CLUSTERING
Figures 6 and shoow the clusters obtained for the state sequence embedding for the Coin Game and the dynamic variant of Stag Hunt respectively. In the figures, each point is a t-SNE projection of the
40
(a) 3-dimensional
(b) 4 dimensional
(c) 10-dimensional
(d) 100-dimensional
Figure 6: Representation of the clusters learned by GameDistill for Coin Game. Each point is a t-SNE projection of the feature vector (in different dimensions) output by the GameDistill network for an input sequence of states. For each of the sub-figures, the figure on the left is colored based on actual rewards obtained by each agent (ri (r2). The figure the right is colored based on clusters as learned by Game Distill. Game Distill correctly identifies two types of trajectories, one for cooperation and the other for defection.
feature vector (in different dimensions) output by the GameDistill network for input sequence
15

---

Under review as a conference paper at ICLR 2021
-40
-10
-10
Figure 7: t-SNE plot for the trajectory embeddings obtained from the Stag Hunt game along with the identified cooperation and defection clusters.
of states. For each of the sub-ligures, the figure on the left is colored based actual rewards obtained by each agent (ri(r2). The figure on the right is colored based on clusters, as learned by Game Distill. Game Distill correctly identifies two types trajectories, one for cooperation and the other for defection for both the games Coin Game and Stag-Hunt.
Figure also shows the clustering results for different dimensions of the state sequence embedding for the Coin Game. We observe that changing the size of the embedding does not have any effect on the results.
D.4 ILLUSTRATIONS TRAINED ORACLE NETWORKS FOR THE COIN GAME
Figure shows the predictions of the oracle networks learned by the Red agent using Game in the Coin Game We that the cooperation oracle suggests action that avoids picking the coin of the other agent (the Blue coin). Analogously, the defection oracle suggests a selfish action that picks the coin of the other agent.
Action predicted by the Cooperation Oracle 0/0
Action predicted by the Defection Oracle +1/-2
Figure 8: Illustratvee predictions of the oracle networks learned by the Red agent using Game Distill in the Coin Game. The numbers red/blue show the rewards obtained by the Red and the Blue agent respectively. The cooperation oracle suggests action that avoids picking the coin of the other agent while the defection oracle suggests an action that picks the coin of the other agent
16

---

Under review as a conference paper at ICLR 2021
D.5 RESULTS FOR THE ITERATED STAG HUNT (ISH) USING SQLOSS
We provide the results of training SQLearner agents the Iterated Stag Hunt game in Fig- ure In this game also, SQ SeLearner agents coordinate successfully to obtain a near-optimal NDR value (0) for this game.
-2
-15
300
355
400
Figure 9: NDR values for SQ Learnrn agents in the ISH game. SQLearner agents coordinate successfully to obtain near optimal NDR value (0) for this game.
D.6 RESULTS FOR THE CHICKEN GAME USING SQLOSS
We provide the results of training SQ agents the Iterated Chicken game in Fig- ure TO The payoff matrix for the game is shown in the Table From the payoff, it is clear that the agents may defect out of greed. In this game also, SQLearner agents coordinate successfully to
C
D
C
(-1, -1)
(-3, 0)
(0, -3)
(-4, -4)
Table 2: Chicken Game
obtain a near-optimal NDR value (0) for this game.
Results for "Chicken" game with SQLoss
-2.4
ndr >gento ndr_agent1
-2.6
200
400
600
800
1000
1200
1400
Figure 10: NDR values for SQLearner agents in the Chicken game. SQ agents coordinate successfully to obtain near optimal NDR value (-1.12) for the game.
17

---

Under review as a conference paper at ICLR 2021
D.7 SQLoss: EFFECT OF CONVERGENCE TO COOPERATION
We explore the effect of the hyper-parameter (Section 2 on convergence to cooperation, we also experiment with varying values of z. In the experiment, imagine the consequences of maintaining the status quo, each agent samples Kit from the Discrete Uniform distribution U1, A larger value of 2 thus implies larger value of 6₁ and longer imaginary episodes. We find that larger (and hence k) leads to faster cooperation between agents in the IPD and Coin Game This effect plateaus for > 10. However varying and changing K2 across time also increases the variance in the gradients and thus affects the learning. We thus use k = 10 for all our experiments.
D.8 SQLEARNER: EXPLOITABILITY AND ADAPTABILITY
Given that an agent does not have any prior information about the other agent, must evolve its strategy based its opponent's strategy. To evaluate SQLearner agent's ability to avoid ploitation by a selfish agent, we train one SQLearner agent against an agent that always defects in the Coin Game. We find that the SQLearner agent also learns to always defect. This persistent defection is important since given that the other agent is selfish, the SQ Learner agent can do no better than also be selfish. To evaluate an SQLearner agent's ability to exploit cooperative agent, we train one SQLearner agent with an agent that always cooperates in the Coin Game. In this case, we find that the SQLearner agent learns to always defect. This persistent defection is important since given that the other agent is cooperative, the SQ Learner agent obtains maximum reward by behaving selfishly. Hence, the SQarrrner agent both resistant to exploitation and able to exploit, depending the other agent's s strategy.
18


Reviews:
[{"review_id": "sgj36teIP7U", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper presents a new method for improving coordination in MARL by using the idea of the status quo. The approach uses a status quo loss and a method for converting multi-step games into matrix games (called GameDistill). The methods are described and experiments are given comparing the methods to other related work. \n\nCoordination is a problem in MARL. When multiple agents are learning at the same time, they can get stuck in poor equilibria. Therefore, ideas such as the status quo may be helpful in escaping these poor solutions. \n\nThe status quo loss is straightforward and of questionable use. The idea (in Equation 8) balances the regular RL loss witha  status quo loss that repeats the interaction (i.e., agent actions) for k steps. k is sampled from a distribution. There are weights for each of these losses to balance them out. This idea makes sense as a way to reduce the nonstationarity of decentralized learning, but it doesn't promote coordination. Why is this the right thing to do? What can be said about it theoretically? More motivation is needed for the approach. \n\nThe details of GameDistill are unclear and it also isn't clear how general it is. The method is described in text in the main paper and in pseudocode in the appendix, but each is high-level and not formal enough to understand the details. Furthermore, the approach clusters trajectories based on their rewards using random play. This seems unlikely to work well where exporation is an issue as random play may not be sufficient and in more complex games, you may need many clusters (and not know how many is needed). The paper should make it clear how general the method is. \n\nThe experiments show the method outperforms an independent learning and LOLA, but more extensive comparisons are needed. For example, the focus is on cooperative games. As such, methods that promote cooperation should also be discussed and compared to. This includes optimistic methods such as hysteresis and leniency as discussed in the paper below:\n\nWei, Ermo, and Sean Luke. \"Lenient learning in independent-learner stochastic cooperative games.\" The Journal of Machine Learning Research 17.1 (2016): 2914-2955.\n\nAlso, the results are a bit surprising. The status quo loss shouldn't favor one equilibrium over another so it isn't clear why the proposed method escapes the poor equilibrium for the good one (e.g., DD for CC). The paper should make it more clear what that is the case. Lastly, the results in Figure 4 are somewhat unfair since it appears that additional training was done by the proposed method for GameDistill before learning curve plot begins. \n\nThe paper is generally well written, but some details can be more clear as mentioned above. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "iFcnJJNygCb", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper focuses on the problem of multi-agent cooperation in social dilemmas, in which mutual defection is individually rational but collectively suboptimal. The authors use the bias toward status-quo in human psychology to motivate a new training method, called SQLoss: 1) for repeated matrix games, each agent is trained with additional imagined episodes in which the actions taken by both agents are repeated for a random number of steps; 2) for settings where cooperation and defection are associated with a sequence of actions, the authors provide a procedure called GameDistill based on trajectory encoding, clustering, and action prediction to arive at oracles for \"cooperative action\" and \"defection action\" at each state, which can then be used for the imagination episodes. Experiments show that SQL achieve better social welfare than LOLA and standard independent RL in classic iterated matrix games, as well as in the Coin Game with higher dimensional image observations.\nThis paper deserves a 6 mainly for showing that an agent based on a seemingly simple concept is sufficient for outperforming the well-known LOLA agent on standard benchmark matrix games. However, precisely because the method in this work seems to be so effective, there is a glaring need for improvement in many areas, and there are significant open questions for further research.\n\nThe introduction and motivation for SQLoss needs improvement. The \"status quo bias\" is the central concept in the paper. Hence, in the introduction, the authors must define it precisely (rather than simply relying on references, or even worse, relying on people's 'common sense' understanding of the term). The authors also should explain the main reason from human psychology that it leads to cooperation in social dilemmas. Currently, the text merely states the term and immediately explains their proposed SQLoss, saying that \"SQLoss encourages an agent to stick to the action taken previously\". I doubt \"status-quo bias\" exactly means \"stick to the action taken previously\". More importantly, the authors themselves say in Section 2.3.1 that \"this imagined episode causes the exploited agent in (DC) to perceive a continued risk of exploitation and, therefore, quickly move to (DD)\". Hence it is not correct to say that \"SQLoss encourages an agent to stick to the action taken previously\".\n\nThere is a key question: is there any hidden centralization at all in the method? SQLoss adds to a growing body of work that proposes methods to achieve multi-agent cooperation with decentralized training (Hughes 2018, Foerster 2018, Wang 2019, and two that the authors missed: Yang 2020 and Gemp 2020). However, there is some kind of implicit centralization in many of these works: e.g. in Hughes 2018, the centralized design of the intrinsic reward is imposed on agents prior to training; in Wang, training the reward is centralized; in Gemp 2020, all agents must \"agree\" before training to participate in updating the loss mixing matrix. To me, it seems that the implicit centralization required by SQLoss is in the GameDistill method, which is needed to generate the \"oracles\" from the temporally-extended game for use in imagination episodes. However, perhaps each agent can independently perform this preprocessing step of GameDistill, so that learning is really fully decentralized? The authors should clarify this important point.\n\nAnother key question: how does the method scale to more than two players?\n\nEquation (4) does not seem to match the text. Section 2.3.2 says $\\hat{\\tau_1}$ is a collection of agent's imagined experiences. The authors say that the imagined experiences only involves the repeated actions $u^1_{t-1}$ and $u^2_{t-1}$. But in equation (4), there are additional actions $u^1_{t+1},..., u^1_T$, which is confusing.\n\nThe largest experiments in the paper (Coin Game and non-matrix Stag Hunt) are still somewhat small, even for gridworlds. Do the authors see any potential difficulties in apply the method to larger social dilemma games such as Cleanup (Hughes et al. 2018)?\n\nAdditional comments:\n1) The authors use the word \"evolve\" in many places. This is imprecise and should be corrected, because the agents in question are learning via RL, not via evolutionary methods.\n2) The introduction mentions that LOLA requires complete access to the opponent, but this is not true since LOLA has been shown to work with opponent modeling.\n3) This paper used two clusters for GameDistill. Should the number always be 2?\n\nAdditional references:\nLearning to Incentivize Other Learning Agents. Yang et al. 2020\nD3C: Reducing the Price of Anarchy in Multi-Agent Learning. Gemp et al. 2020\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "Y1OY1CMZHK_", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 7, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "##########################################################################\n\nSummary:\nThis paper proposed a loss function that leads to cooperation between two individually optimized agents in a matrix game. The authors demonstrate this result in three matrix games. The authors further proposed a method to generalize this loss to non-matrix games and showed its effectiveness. \n\n##########################################################################\n\nReasons for score: \nOverall, I vote for acceptance. The idea is quite intuitive and simple while effective. The empirical result is strong and clearly demonstrates effectiveness. The authors addressed the generalization issue, which could have been a major concern, by proposing a method mapping non-matrix games to matrix games. \n \n##########################################################################\n\nPros: \n\n1.The writing is very clear and easy to follow. The paper is well-motivated and the contributions compared to previous work are clearly stated. \n \n2. The empirical results are strong compared to the considered baselines.\n\n3. The authors took care of the generalization issue by proposing GameDistill and presented empirical results. \n\n##########################################################################\n\nCons: \n\n1. I’m not sure what are the major differences between the three matrix games tested in the paper. It would be good to state the hypothesis and discuss what additionally we can learn from the results from different settings. Also, It seems to me that the matrix game is easily parameterized so that potentially the authors can test the loss under various parameters. Thus, though I am convinced by results from the presented three settings, it remains open whether there are bad conditions in which the loss might fail. \n\n#########################################################################\n\nOther questions/suggestions:\nIt is already quite interesting enough to only consider two agents scenario, but it seems to me that the method can be potentially extended to multi-agent (n>2) cases. It would be interesting to see a discussion or a quick experiment. I think that would make the paper even stronger. \n", "extra_scores": {}, "extra_text": {}}, {"review_id": "TmfBH-Hlzp", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "**Post-rebuttal update:** Thanks to the authors for engaging in the discussion and for the responses. The authors have provided a satisfying argument that with an appropriate choice of hyper parameters, the SQLoss does promote cooperative behaviors whenever all utilities are negative -- this addresses my main concern regarding the validity of the SQLoss objective. I remain skeptical of the value of the visual Coin game, because the results do not disentangle the usefulness of the cooperation objective and the clustering from GameDistill. I (and it seems, R1 and R3) had several concerns about the presentation of the material: mine in particular about lack of clarity, statements provided without motivation, and lack of details in Section 3, both for SQLoss and GameDistill. The authors have provided clarifications to some of these concerns in the response, but the new revision of the manuscript does not seem to reflect any of these changes. I would not be strongly opposed to acceptance, conditional on the visual coin game ablations and clarifications being added in the final version. Nevertheless, it is hard for me to recommend acceptance, given the number of unseen changes that still need to be made to the paper.  \n\n\n\n\n**Summary**: This paper studies the problem of learning cooperative behaviors in social dilemma problems for multi-agent deep RL with independent agents. The authors propose a simple loss that emphasizes the \"status quo\",  which increases the emphasis on the one-step reward, to force agents to avoid short-term exploitation. To extend this idea to a temporally-extended sequential setup, the authors introduce a clustering algorithm that reduces the game into a matrix game with \"cooperate\" and \"defect\" options.\n\n**Assessment:** The paper studies an interesting problem: without explicit communication between two agents, how to impose protocols that ensure convergence to cooperative / optimal behaviors. The paper is also generally well-written and quite easy to understand, which I appreciated. Nonetheless, the algorithmic contributions of the paper appear lacking and incomplete. The paper does not current convince me that the proposed solution SQLoss actually solves the cooperation problem (discussion below). The GameDistill algorithm is an interesting way to reduce general environments to matrix games, but seems highly instrumented for the current environments, and unlikely to work in more general environments (discussion below). Due to my concern and confusion about the effectivity of the algorithms proposed, I currently tend to reject the paper.\n\n**Major Concerns:** \n\n(SQLoss) From what I ascertained from SQLoss, it changes the policy gradient to re-weigh the reward at the current time-step higher than future rewards. The text does not make it clear to me why this should force / encourage cooperative behaviors. I do understand that SQLoss will \"cause an exploited agent (in DC) to ... quickly move to (DD)\", but what remains confusing to me is why SQLoss will force a system in (DD) to move to (CC). If the system originally starts in a place of mutual defection (or more generally, prefers mutual defection to mutual cooperation), how does the SQLoss incentivize either player to switch to a cooperative behavior? If each agent could reason about the other agent's learning procedure, then this behavior might emerge, but the PG update does not do this: it is conditional only on the other agent's current parameters, and not how it learns. With the PG update, even when the reward at the first time-step is emphasized, neither player is incentivized to increase the probability of cooperative behavior, since cooperative behavior has strictly lower future value. One experiment that might help resolve this confuion is to show that SQLoss also induces cooperation even when the initial agents prefer mutual defection.\n\n(GameDistill) The GameDistill algorithm is an interesting clustering method for turning a sequential game into a static game where strategies correspond to \"options\", but seems rather specific to the current tested environments. While the GameDistill algorithm handles discrete behaviors that \"cooperate\" or \"defect\" well, it doesn't seem to capture games where there are potentially multiple (and unknown number of) ways to cooperate or defect, or where there are graded levels of cooperation. A comment about how well GameDistill handles environment stochasticity / etc would also be helpful. Also, since it requires the practitioner to train several intermediary models (a trajectory encoder, a clustering model, an action predictor), it seems to me that the solution may be sensitive to hyperparameters, and thus not scale well to other environments. This final point is hard to judge in the current setup.\n\n(Experiments / GameDistill) It is unclear in the experimental section, whether the performance of the SQLearner agent is due to the GameDistill algorithm reducing the dimensionality of the problem to only choosing between two options, or if it is because the SQLoss actually promotes cooperativeness. Do the other baselines, e.g. Lola-PG and SL also use GameDistill?\n\n**Additional Comments:**\n\n- The derivation on Page 5 is incorrect: Equation (7) does not result from $\\nabla_\\theta \\mathbb{E}[\\hat{R}_0^1(\\tau_1)]$, since $\\hat{R}_0^1$ contains \"imagined\" trajectories only for the first time-step, and not for subsequent timesteps (that is, it does not contain any terms involving $\\hat{R}_t^1(\\tau_1)$ for $t > 0$). It is not immediately clear to me that there is a simple objective function for which (7) is the gradient. \n-  Why does the learning behavior of the SQLearner spike immediately to the optimal policy (after the initial period of being flat)?\n- The related work section appears to be comprehensive, but I am not well-versed with the multi-agent literature.\n- The code for running experiments is provided, which is a positive point for this paper.\n\n\n**Minor Comments:**\n\n- \"Each agent independently attempts to maximize its expected discounted return\": For this sentence in Section 2.1, what does the agent assume about the other agents? That the other agents are fixed? That the other agents can act adversarially?\n- The word loss is used throughout for referring to both \"a loss function\", and a \"bad reward\" -- this makes the discussion in places confusing\n- Use the math operator $\\log$ instead of $log$", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: In general there is agreement under reviewers that the ideas/method presented are somewhat interesting/promising but also that the paper lacks a lot of clarity. Reviewers agree that the paper needs more work (on the method) and more extensive experiments to be convincing, and that in its current form it is not mature enough for publication at ICLR.
Decision: Reject