Multi-agent Reinforcement Learning in Sequential Social Dilemmas

Introduction

Social dilemmas expose tensions between collective and individual rationality . Cooperation makes possible better outcomes for all than any could obtain on their own. However, the lure of free riding and other such parasitic strategies implies a tragedy of the commons that threatens the stability of any cooperative venture .

The theory of repeated general-sum matrix games provides a framework for understanding social dilemmas. Fig. 1 shows payoff matrices for three canonical examples: Prisoner’s Dilemma, Chicken, and Stag Hunt. The two actions are interpreted as cooperate and defect respectively. The four possible outcomes of each stage game are $R$ (reward of mutual cooperation), $P$ (punishment arising from mutual defection), $S$ (sucker outcome obtained by the player who cooperates with a defecting partner), and $T$ (temptation outcome achieved by defecting against a cooperator). A matrix game is a social dilemma when its four payoffs satisfy the following social dilemma inequalities (this formulation from ):

$R>P$ Mutual cooperation is preferred to mutual defection. $\ (1)$

$R>S$ Mutual cooperation is preferred to being exploited by a defector. $\ (2)$

$2R>T+S$ This ensures that mutual cooperation is preferred to an equal probability of unilateral cooperation and defection. $\ (3)$

either greed: $T>R$ Exploiting a cooperator is preferred over mutual cooperation or fear: $P>S$ Mutual defection is preferred over being exploited. $\ (4)$

Matrix Game Social Dilemmas (MGSD) have been fruitfully employed as models for a wide variety of phenomena in theoretical social science and biology. For example, there is a large and interesting literature concerned with mechanisms through which the socially preferred outcome of mutual cooperation can be stabilized, e.g., direct reciprocity , indirect reciprocity , norm enforcement , simple reinforcement learning variants , multiagent reinforcement learning , spatial structure , emotions , and social network effects .

However, the MGSD formalism ignores several aspects of real world social dilemmas which may be of critical importance.

Real world social dilemmas are temporally extended.

Cooperation and defection are labels that apply to policies implementing strategic decisions.

Cooperativeness may be a graded quantity.

Decisions to cooperate or defect occur only quasi-simultaneously since some information about what player 2 is starting to do can inform player 1’s decision and vice versa.

Decisions must be made despite only having partial information about the state of the world and the activities of the other players.

We propose a Sequential Social Dilemma (SSD) model to better capture the above points while, critically, maintaining the mixed motivation structure of MGSDs. That is, analogous inequalities to (1) – (4) determine when a temporally-extended Markov game is an SSD.

To demonstrate the importance of capturing sequential structure in social dilemma modeling, we present empirical game-theoretic analyses of SSDs to identify the empirical payoff matrices summarizing the outcomes that would arise if cooperate and defect policies were selected as one-shot decisions. The empirical payoff matrices are themselves valid matrix games. Our main result is that both of the SSDs we considered, Gathering and Wolfpack, have empirical payoff matrices that are Prisoner’s Dilemma (PD). This means that if one were to adhere strictly to the MGSD-modeling paradigm, PD models should be proposed for both situations. Thus any conclusions reached from simulating them would necessarily be quite similar in both cases (and to other studies of iterated PD). However, when viewed as SSDs, the formal equivalence of Gathering and Wolfpack disappears. They are clearly different games. In fact, there are simple experimental manipulations that, when applied to Gathering and Wolfpack, yield opposite predictions concerning the emergence and stability of cooperation.

More specifically, we describe a factor that promotes the emergence of cooperation in Gathering while discouraging its emergence in Wolfpack, and vice versa. The straightforward implication is that, for modeling real-world social dilemmas with SSDs, the choice of whether to use a Gathering-like or Wolfpack-like model is critical. And the differences between the two cannot be captured by MGSD modeling.

Along the way to these results, the present paper also makes a small methodological contribution. Owing to the greater complexity arising from their sequential structure, it is more computationally demanding to find equilibria of SSD models than it is for MGSD models. Thus the standard evolution and learning approaches to simulating MGSDs cannot be applied to SSDs. Instead, more sophisticated multiagent reinforcement learning methods must be used (e.g ). In this paper we describe how deep Q-networks (e.g ) may be applied to this problem of finding equilibria of SSDs.

Definitions and Notation

We model sequential social dilemmas as general-sum Markov (simultaneous move) games with each agent having only a partial observation onto their local environment. Agents must learn an appropriate policy while coexisting with one another. A policy is considered to implement cooperation or defection by properties of the realizations it generates. A Markov game is an SSD if and only if it contains outcomes arising from cooperation and defection policies that satisfy the same inequalities used to define MGSDs (eqs. 1 – 4). This definition is stated more formally in sections 2.1 and 2.2 below.

For temporal discount factor $\gamma\in$ we can define the long-term payoff $V^{\@vec{\pi}}_{i}(s_{0})$ to player $i$ when the joint policy $\@vec{\pi}=(\pi_{1},\pi_{2})$ is followed starting from state $s_{0}\in\mathcal{S}$.

Matrix games are the special case of two-player perfectly observable ($O_{i}(s)=s$) Markov games obtained when $|\mathcal{S}|=1$. MGSDs also specify $\mathcal{A}_{1}=\mathcal{A}_{2}=\{C,D\}$, where $C$ and $D$ are called (atomic) cooperate and defect respectively.

The outcomes $R(s),P(s),S(s),T(s)$ that determine when a matrix game is a social dilemma are defined as follows.

where $\pi^{C}$ and $\pi^{D}$ are cooperative and defecting policies as described next. Note that a matrix game is a social dilemma when $R,P,S,T$ satisfy the inequalities (1) – (4).

2 Definition of Sequential Social Dilemma

This definition is based on a formalization of empirical game-theoretic analysis . We define the outcomes $(R,P,S,T):=$ $(R(s_{0})$, $P(s_{0})$, $S(s_{0})$, $T(s_{0}))$ induced by initial state $s_{0}$, and two policies $\pi^{C},\pi^{D}$, through their long-term expected payoff (5) and the definitions (6) – (9). We refer to the game matrix with $R$, $P$, $S$, $T$ organized as in Fig. 1-left. as an empirical payoff matrix following the terminology of .

Definition: A sequential social dilemma is a tuple $(\mathcal{M},\Pi^{C},\Pi^{D})$ where $\Pi^{C}$ and $\Pi^{D}$ are disjoint sets of policies that are said to implement cooperation and defection respectively. $\mathcal{M}$ is a Markov game with state space $\mathcal{S}$. Let the empirical payoff matrix $(R(s),P(s),S(s),T(s))$ be induced by policies $(\pi^{C}\in\Pi^{C},\pi^{D}\in\Pi^{D})$ via eqs. (5) – (9). A Markov game is an SSD when there exist states $s\in\mathcal{S}$ for which the induced empirical payoff matrix satisfies the social dilemma inequalities (1) – (4).

Learning Algorithms

Most previous work on finding policies for Markov games takes the prescriptive view of multiagent learning : that is, it attempts to answer “what should each agent do?” Several algorithms and analyses have been developed for the two-player zero-sum case . The general-sum case is significantly more challenging , and algorithms either have strong assumptions or need to either track several different potential equilibria per agent , model other players to simplify the problem , or must find a cyclic strategy composed of several policies obtained through multiple state space sweeps . Researchers have also studied the emergence of multi-agent coordination in the decentralized, partially observable MDP framework . However, that approach relies on knowledge of the underlying Markov model, an unrealistic assumption for modeling real-world social dilemmas.

In contrast, we take a descriptive view, and aim to answer “what social effects emerge when each agent uses a particular learning rule?” The purpose here then is to study and characterize the resulting learning dynamics, as in e.g., , rather than on designing new learning algorithms. It is well-known that the resulting “local decision process” could be non-Markovian from each agent’s perspective . This is a feature, not a bug in descriptive work since it is a property of the real environment that the model captures.

We use deep reinforcement learning as the basis for each agent in part because of its recent success with solving complex problems . Also, temporal difference predictions have been observed in the brain and this class of reinforcement learning algorithm is seen as a candidate theory of animal habit-learning .

Modern deep reinforcement learning methods take the perspective of an agent that must learn to maximize its cumulative long-term reward through trial-and-error interactions with its environment .

During learning, to encourage exploration we parameterize the $i$-th agent’s policy by

where $\mathcal{U}(\mathcal{A}_{i})$ denotes a sample from the uniform distribution over $\mathcal{A}_{i}$. Each agent updates its policy given a stored batchThe batch is sometimes called a “replay buffer” e.g. . of experienced transitions $\{(s,a,r_{i},s^{\prime})_{t}:t=1,\dots T\}$ such that

This is a “growing batch” approach to reinforcement learning in the sense of . However, it does not grow in an unbounded fashion. Rather, old data is discarded so the batch can be constantly refreshed with new data reflecting more recent transitions. We compared batch sizes of 1e5 (our default) and 1e6 in our experiments (see Sect. 5.3). The network representing the function $Q$ is trained through gradient descent on the mean squared Bellman residual with the expectation taken over transitions uniformly sampled from the batch (see ). Since the batch is constantly refreshed, the $Q$-network may adapt to the changing data distribution arising from the effects of learning on $\pi_{1}$ and $\pi_{2}$.

In order to make learning in SSDs tractable, we make the extra assumption that each individual agent’s learning depends only on the other agent’s learning via the (slowly) changing distribution of experience it generates. That is, the two learning agents are “independent” of one another and each regard the other as part of the environment. From the perspective of player one, the learning of player two shows up as a non-stationary environment. The independence assumption can be seen as a particular kind of bounded rationality: agents do no recursive reasoning about one another’s learning. In principle, this restriction could be dropped through the use of planning-based reinforcement learning methods like those of .

Simulation Methods

Results

In this section, we describe three experiments: one for each game (Gathering and Wolfpack), and a third experiment investigating parameters that influence the emergence of cooperation versus defection.

The goal of the Gathering game is to collect apples, represented by green pixels (see Fig. 3A). When a player collects an apple it receives a reward of 1 and the apple is temporarily removed from the map. The apple respawns after $N_{\text{apple}}$ frames. Players can direct a beam in a straight line along their current orientation. A player hit by the beam twice is “tagged” and removed from the game for $N_{\text{tagged}}$ frames. No rewards are delivered to either player for tagging. The only potential motivation for tagging is competition over the apples. Refer to the Gathering gameplay videohttps://goo.gl/2xczLc for demonstration.

Intuitively, a defecting policy in this game is one that is aggressive—i.e., involving frequent attempts to tag rival players to remove them from the game. Such a policy is motivated by the opportunity to take all the apples for oneself that arises after eliminating the other player. By contrast, a cooperative policy is one that does not seek to tag the other player. This suggests the use of a social behavior metric (section 2.2) that measures a policy’s tendency to use the beam action as the basis for its classification as defection or cooperation. To this end, we counted the number of beam actions during a time horizon and normalized it by the amount of time in which both agents were playing (not removed from the game).

By manipulating the rate at which apples respawn after being collected, $N_{\text{apple}}$, we could control the abundance of apples in the environment. Similarly, by manipulating the number of timesteps for which a tagged agent is removed from the game, $N_{\text{tagged}}$, we could control the cost of potential conflict. We wanted to test whether conflict would emerge from learning in environments where apples were scarce. We considered the effect of abundance $(N_{\text{apple}})$ and conflict-cost $(N_{\text{tagged}})$ on the level of aggressiveness (beam-use rate) that emerges from learning. Fig. 4A shows the beam-use rate that evolved after training for 40 million steps as a function of abundance $(N_{\text{apple}})$ and conflict-cost $(N_{\text{tagged}})$. Supplementary video https://goo.gl/w2VqlQ shows how such emergent conflict evolves over the course of learning. In this case, differences in beam-use rate (proxy for the tendency to defect) learned in the different environments emerge quite early in training and mostly persist throughout. When learning does change beam-use rate, it is almost always to increase it.

We noted that the policies learned in environments with low abundance or high conflict-cost were highly aggressive while the policies learned with high abundance or low conflict-cost were less aggressive. That is, the Gathering game predicts that conflict may emerge from competition for scarce resources, but is less likely to emerge when resources are plentiful.

To further characterize the mixed motivation structure of the Gathering game, we carried out the empirical game-theoretic analysis suggested by the definition of section 2.2. We chose the set of policies $\Pi^{C}$ that were trained in the high abundance / low conflict-cost environments (low aggression policies) and $\Pi^{D}$ as policies trained in the low abundance and high conflict-cost environments (high aggression policies), and used these to compute empirical payoff matrices as follows. Two pairs of policies $(\pi_{1}^{C},\pi_{1}^{D})$ and $(\pi_{2}^{C},\pi_{2}^{D})$ are sampled from $\Pi^{C}$ and $\Pi^{D}$ and matched against each other in the Gathering game for one episode. The resulting rewards are assigned to individual cells of a matrix game, in which $\pi_{i}^{C}$ corresponds the cooperative action for player $i$, and $\pi_{j}^{D}$, the defective action for player $j$. This process is repeated until convergence of the cell values, and generates estimates of $R,P,S,$ and $T$ for the game corresponding to each abundance / conflict-cost $(N_{\text{apple}},N_{\text{tagged}})$ level tested. See Figure 5 for an illustration of this workflow. Fig. 6A summarizes the types of empirical games that were found given our parameter spectrum. Most cases where the social dilemma inequalities (1) – (4) held, i.e., the strategic scenario was a social dilemma, turned out to be a prisoner’s dilemma. The greed motivation reflects the temptation to take out a rival and collect all the apples oneself. The fear motivation reflected the danger of being taken out oneself by a defecting rival. $P$ is preferred to $S$ in the Gathering game because mutual defection typically leads to both players alternating tagging one another, so each gets some time alone to collect apples. Whereas the agent receiving the outcome $S$ does not try to tag its rival and thus never gets this chance.

2 Experiment 2: Wolfpack

The Wolfpack game requires two players (wolves) to chase a third player (the prey). When either wolf touches the prey, all wolves within the capture radius (see Fig. 3B) receive a reward. The reward received by the capturing wolves is proportional to the number of wolves in the capture radius. The idea is that a lone wolf can capture the prey, but is at risk of losing the carcass to scavengers. However, when the two wolves capture the prey together, they can better protect the carcass from scavengers and hence receive a higher reward. A lone-wolf capture provides a reward of $r_{\text{lone}}$ and a capture involving both wolves is worth $r_{\text{team}}$. Refer to the Wolfpack gameplay videohttps://goo.gl/AgXtTn for demonstration.

The wolves learn to catch the prey over the course of training. Fig. 4B shows the effect on the average number of wolves per capture obtained from training in environments with varying levels of group capture bonus $r_{\text{team}}/r_{\text{lone}}$ and capture radius. Supplementary video https://goo.gl/vcB8mU shows how this dependency evolves over learning time. Like in the Gathering game, these results show that environment parameters influence how cooperative the learned policies will be. It is interesting that two different cooperative policies emerged from these experiments. On the one hand, the wolves could cooperate by first finding one another and then moving together to hunt the prey, while on the other hand, a wolf could first find the prey and then wait for the other wolf to arrive before capturing it.

Analogous to our analysis of the Gathering game, we choose $\Pi^{C}$ and $\Pi^{D}$ for Wolfpack to be the sets of policies learned in the high radius / group bonus and low radius /group bonus environments respectively. The procedure for estimating $R,P,S,$ and $T$ was the same as in section 5.1. Fig. 6B summarizes these results. Interestingly, it turns out that all three classic MGSDs, chicken, stag hunt, and prisoner’s dilemma can be found in the empirical payoff matrices of Wolfpack.

3 Experiment 3: Agent parameters influencing the emergence of defection

So far we have described how properties of the environment influence emergent social outcomes. Next we consider the impact of manipulating properties of the agents. Psychological research attempting to elucidate the motivational factors underlying human cooperation is relevant here. In particular, Social Psychology has advanced various hypotheses concerning psychological variables that may influence cooperation and give rise to the observed individual differences in human cooperative behavior in laboratory-based social dilemmas . These factors include consideration-of-future-consequences , trust , affect (interestingly, it is negative emotions that turn out to promote cooperation ), and a personality variable called social value orientation characterized by other-regarding-preferences. The latter has been studied in a similar Markov game social dilemma setup to our SSD setting by .

Obviously the relatively simple DQN learning agents we consider here do not have internal variables that directly correspond to the factors identified by Social Psychology. Nor should they be expected to capture the full range of human individual differences in laboratory social dilemmas. Nevertheless, it is interesting to consider just how far one can go down this road of modeling Social Psychology hypotheses using such simple learning agentsThe contrasting approach that seeks to build more structure into the reinforcement learning agents to enable more interpretable experimental manipulations is also interesting and complementary e.g., .. Recall also that DQN is in the class of reinforcement learning algorithms that is generally considered to be the leading candidate theory of animal habit-learning . Thus, the interpretation of our model is that it only addresses whatever part of cooperative behavior arises “by habit” as opposed to conscious deliberation.

Experimental manipulations of DQN parameters yield consistent and interpretable effects on emergent social behavior. Each plot in Fig. 7 shows the relevant social behavior metric, conflict for Gathering and lone-wolf behavior for Wolfpack, as a function of an environment parameter: $N_{\text{apple}},N_{\text{tagged}}$ (Gathering) and $r_{\text{team}}/r_{\text{lone}}$ (Wolfpack). The figure shows that in both games, agents with greater discount parameter (less time discounting) more readily defect than agents that discount the future more steeply. For Gathering this likely occurs because the defection policy of tagging the other player to temporarily remove them from the game only provides a delayed reward in the form of the increased opportunity to collect apples without interference. However, when abundance is very high, even the agents with higher discount factors do not learn to defect. In such paradisiacal settings, the apples respawn so quickly that an individual agent cannot collect them quickly enough. As a consequence, there is no motivation to defect regardless of the temporal discount rate. Manipulating the size of the stored-and-constantly-refreshed batch of experience used to train each DQN agent has the opposite effect on the emergence of defection. Larger batch size translates into more experience with the other agent’s policy. For Gathering, this means that avoiding being tagged becomes easier. Evasive action benefits more from extra experience than the ability to target the other agent. For Wolfpack, larger batch size allows greater opportunity to learn to coordinate to jointly catch the prey.

Possibly the most interesting effect on behavior comes from the number of hidden units in the neural network behind the agents, which may be interpreted as their cognitive capacity. Curves for tendency to defect are shown in the right column of Fig. 7, comparing two different network sizes. For Gathering, an increase in network size leads to an increase in the agent’s tendency to defect, whereas for Wolfpack the opposite is true: Greater network size leads to less defection.

This can be explained as follows. In Gathering, defection behavior is more complex and requires a larger network size to learn than cooperative behavior. This is the case because defection requires the difficult task of targeting the opposing agent with the beam whereas peacefully collecting apples is almost independent of the opposing agent’s behavior. In Wolfpack, cooperation behavior is more complex and requires a larger network size because the agents need to coordinate their hunting behaviors to collect the team reward whereas the lone-wolf behavior does not require coordination with the other agent and hence requires less network capacity.

Note that the qualitative difference in effects for network size supports our argument that the richer framework of SSDs is needed to capture important aspects of real social dilemmas. This rather striking difference between Gathering and Wolfpack is invisible to the purely matrix game based MGSD-modeling. It only emerges when the different complexities of cooperative or defecting behaviors, and hence the difficulty of the corresponding learning problems is modeled in a sequential setup such as an SSD.

Discussion

In the Wolfpack game, learning a defecting lone-wolf policy is easier than learning a cooperative pack-hunting policy. This is because the former does not require actions to be conditioned on the presence of a partner within the capture radius. In the Gathering game the situation is reversed. Cooperative policies are easier to learn since they need only be concerned with apples and may not depend on the rival player’s actions. However, optimally efficient cooperative policies may still require such coordination to prevent situations where both players simultaneously move on the same apple. Cooperation and defection demand differing levels of coordination for the two games. Wolfpack’s cooperative policy requires greater coordination than its defecting policy. Gathering’s defection policy requires greater coordination (to successfully aim at the rival player).

Both the Gathering and Wolfpack games contain embedded MGSDs with prisoner’s dilemma-type payoffs. The MGSD model thus regards them as structurally identical. Yet, viewed as SSDs, they make rather different predictions. This suggests a new dimension on which to investigate classic questions concerning the evolution of cooperation. For any to-be-modeled phenomenon, the question now arises: which SSD is a better description of the game being played? If Gathering is a better model, then we would expect cooperation to be the easier-to-learn “default” policy, probably requiring less coordination. For situations where Wolfpack is the better model, defection is the easier-to-learn “default” behavior and cooperation is the harder-to-learn policy requiring greater coordination. These modeling choices are somewhat orthogonal to the issue of assigning values to the various possible outcomes (the only degree of freedom in MGSD-modeling), yet they make a large difference to the results.

SSD models address similar research questions as MGSD models, e.g. the evolution of cooperation. However, SSD models are more realistic since they capture the sequential structure of real-world social dilemmas. Of course, in modeling, greater verisimilitude is not automatically virtuous. When choosing between two models of a given phenomenon, Occam’s razor demands we prefer the simpler one. If SSDs were just more realistic models that led to the same conclusions as MGSDs then they would not be especially useful. This however, is not the case. We argue the implication of the results presented here is that standard evolutionary and learning-based approaches to modeling the trial and error process through which societies converge on equilibria of social dilemmas are unable to address the following important learning related phenomena.

Learning which strategic decision to make, abstractly, whether to cooperate or defect, often occurs simultaneously with learning how to efficiently implement said decision.

It may be difficult to learn how to implement an effective cooperation policy with a partner bent on defection—or vice versa.

Implementing effective cooperation or defection may involve solving coordination subproblems, but there is no guarantee this would occur, or that cooperation and defection would rely on coordination to the same extent. In some strategic situations, cooperation may require coordination, e.g., standing aside to allow a partner’s passage through a narrow corridor while in others defection may require coordination e.g. blocking a rival from passing.

Some strategic situations may allow for multiple different implementations of cooperation, and each may require coordination to a greater or lesser extent. The same goes for multiple implementations of defection.

The complexity of learning how to implement effective cooperation and defection policies may not be equal. One or the other might be significantly easier to learn—solely due to implementation complexity—in a manner that cannot be accounted for by adjusting outcome values in an MGSD model.

Our general method of tracking social behavior metrics in addition to reward while manipulating parameters of the learning environment is widely applicable. One could use these techniques to simulate the effects of external interventions on social equilibria in cases where the sequential structure of cooperation and defection are important. Notice that several of the examples in Schelling’s seminal book Micromotives and Macrobehavior can be seen as temporally extended social dilemmas for which policies have been learned over the course of repeated interaction, including the famous opening example of lecture hall seating behavior. It is also possible to define SSDs that model the extraction of renewable vs non-renewable resources and track the sustainability of the emergent social behaviors while taking into account the varying difficulties of learning sustainable (cooperating) vs. non-sustainable (defecting) policies. Effects stemming from the need to learn implementations for strategic decisions may be especially important for informed policy-making concerning such real-world social dilemmas.

The authors would like to thank Chrisantha Fernando, Toby Ord, and Peter Sunehag for fruitful discussions in the lead-up to this work, and Charles Beattie, Denis Teplyashin, and Stig Petersen for software engineering support.

References