Social dilemmas, where mutual cooperation can lead to high payoffs but participants face incentives to cheat, are ubiquitous in multi-agent interaction. We wish to construct agents that cooperate with pure cooperators, avoid exploitation by pure defectors, and incentivize cooperation from the rest. However, often the actions taken by a partner are (partially) unobserved or the consequences of individual actions are hard to predict. We show that in a large class of games good strategies can be constructed by conditioning one's behavior solely on outcomes (ie. one's past rewards). We call this consequentialist conditional cooperation. We show how to construct such strategies using deep reinforcement learning techniques and demonstrate, both analytically and experimentally, that they are effective in social dilemmas beyond simple matrix games. We also show the limitations of relying purely on consequences and discuss the need for understanding both the consequences of and the intentions behind an action. Deep reinforcement learning (RL) is concerned with constructing agents that start as blank slates and can learn to behave in optimal ways in complex environments.1 A recent stream of research has taken a particular interest in social dilemmas, situations where individuals have incentives to act in ways that undermine socially optimal outcomes (Leibo et al., 2017; Perolat et al., 2017; Lerer & Peysakhovich, 2017; Kleiman-Weiner et al., 2016) . In this paper we consider RL-based strategies for social dilemmas in which information about a partner's actions or the underlying environment is only partially observed.The simplest social dilemma is the Prisoner's Dilemma (PD) in which two players choose between one of two actions: cooperate or defect. Mutual cooperation yields the highest payoffs, but no matter what one's partner is doing, one can get a higher reward by defecting. A well studied strategy for maintaining cooperation when the PD is repeated is tit-for-tat (TFT, Axelrod (2006) ). TFT behaves by copying the prior behavior of their partner, rewarding cooperation today with cooperation tomorrow. Thus, if an agent commits to TFT it makes cooperation the best strategy for the agent's partner. TFT has proven to be a heavily studied strategy because it has intuitive appeal: 1) it is easily explainable, 2) it begins cooperating, 3) it rewards a cooperative partner, 4) it avoids being exploited, 5) it is forgiving.In Markov games cooperation and defection are not single actions, but rather temporally extended policies. Recent work has considered expanding TFT to more complex Markov games either as a heuristic, by learning cooperative and selfish policies and switching between them as needed (Lerer & Peysakhovich, 2017) , or as an outcome of an end-to-end procedure (Foerster et al., 2017c) . TFT is * Both authors contributed equally to this paper. Author ordering was determined at random. 1 This approach has been applied to domains including: single agent decision problems (Mnih et al., 2015) , board and card-based zero-sum games BID15 BID13 Heinrich & Silver, 2016) , video games (Kempka et al., 2016; BID17 Ontanón et al., 2013; BID16 Foerster et al., 2017a) , multi-agent coordination problems (Lowe et al., 2017; Foerster et al., 2017b; BID7 BID14 Peysakhovich & Lerer, 2017) , and the emergence of language (Lazaridou et al., 2017; Das et al., 2017; Evtimova et al., 2017; Havrylov & Titov, 2017; Jorge et al., 2016) .an example of a conditionally cooperative strategy -that is, it cooperates when a certain condition is fulfilled (ie. the partner's last period action was cooperative). TFT , however, has a weakness -it requires perfect observability of a partner's behavior and perfect understanding of each action's future consequences.Our main contribution is to use RL methods to construct conditionally cooperative strategies for games with imperfect information. When information is imperfect, the agent must use what they can observe to try to estimate whether a partner is acting cooperatively (or not) and determine how to respond. We show that when the game is ergodic, observed rewards can be used as a summary statistic -if the current total (or time averaged) reward is above a time-dependent threshold (where the threshold values are computed using RL and a form of self play) the agent cooperates, otherwise the agent does not 2 . We call this consequentialist conditional cooperation (CCC). We show analytically that this strategy cooperates with cooperators, avoids exploitation, and guarantees a good payoff to the CCC agent in the long run.We study CCC agents in a partially observed Markov game which we call Fishery. In Fishery two agents live on different sides of a lake in which fish appear. The game has partial information because agents cannot observe what happens across the lake. Fish spawn randomly , starting young and swim to the other side and become mature. Agents can catch fish on their side of the lake. Catching any fish yields payoff but mature fish are worth more. Therefore, cooperative strategies are those which leave young fish for one's partner. However, there is always a temptation to defect and catch both young and mature fish. We show that CCC agents cooperate with cooperators, avoid exploitation, and get high payoffs when matched with themselves.Second, we show that CCC is an efficient strategy for more complex games where implementing conditional cooperation by fully modeling the effect of an action on future rewards (eg. amTFT (Lerer & Peysakhovich, 2017) ) is computationally demanding. We compare the performance of CCC to amTFT in the Pong Player's Dilemma (PPD). This game is a modification of standard Atari pong such that when an agent scores they gain a reward of 1 but the partner receives a reward of −2. Cooperative payoffs are achieved when both agents try hard not to score but selfish agents are again tempted to defect and try to score points even though this decreases total social reward. We see that CCC is a successful, robust, and simple strategy in this game.However, this does not mean CCC completely dominates forward looking strategies like amTFT. We consider a version of the Pong Players' Dilemma where when a player scores, instead of their partner losing 2 points deterministically they lose 2/p points with probability p. Here the expected rewards of non-cooperation are the same as in the PPD and so expected-future-reward based methods (eg. amTFT) will act identically. However, when p is low it may take a long time for consequentialist agents to detect a defector. Empirically we see that in short risky PPD games CCC agents can be exploited by defectors but that amTFT agents cannot. We close by discussing limitations and progress towards agents that can effectively use both intention and outcome information effectively in navigating the world. In this work we have introduced consequentialist conditionally cooperative strategies and shown that they are useful heuristics in social dilemmas, even in those where information is imperfect either due to the structure of the game or due to the fact that we cannot perfectly forecast a partner's future actions. We have shown that using one's own reward stream as a summary statistic for whether to cooperate (or not) in a given period is guaranteed to work in the limit as long as the underlying game is ergodic. Note that this sometimes (but not always) gives good finite time guarantees. In particular, 4 For simplicity for this experiment we use theπ C andπ D strategies trained in the standard PPD for the risky PPD, this is because the risky PPD is the same (in expectation) as the PPD. the time scale for a CCC agent to detect exploitation is related to the mixing time of the POMG and the stochasticity of rewards; if these are large, then correspondingly long games are required for CCC to perform well.We have also compared consequentialist and forward-looking models. As another simple example of the difference between the two we can consider the random Dictator Game (rDG) introduced by Cushman et al. (2009) . In the rDG, individuals are paired, one (the Dictator) is given an amount of money to split with a Partner, and chooses between one of two dice, a 'fair' die which yields a 50 − 50 split with a high probability and an unfair split with a low probability and an 'unfair' die which yields a 50 − 50 split with low probability. Consequentialist conditional cooperators would label a partner a defector if an unfair outcome came up (regardless of die choice) whereas intention-based cooperators would look at the choice of die, not the actual outcome.For RL trained agents, conditioning purely on intentions (eg. amTFT) has advantages in that it is forward looking and doesn't require ergodicity assumptions but it is an expensive strategy that is complex (or impossible) to implement for POMDPs and requires very precise estimates of potential outcomes. CCC is simple, works in POMDPs and requires only information about payoff rates (rather than actual policies), however it may take a long time to converge. Each has unique advantages and disadvantages. Therefore constructing agents that can solve social dilemmas will require combining consequentialist and intention-based signals.Interestingly, experimental evidence shows that while humans combine both intentions and outcomes, we often rely much more heavily on consequences than 'optimal' behavior would demand. For example, experimental subjects rely heavily on the outcome of the die throw rather than die choice in the rDG (Cushman et al., 2009) . This is evidence for the notion that rather than acting optimally in each situation, humans have social heuristics which are tuned to work across many environments BID6 Hauser et al., 2014; Ouss & Peysakhovich, 2015; BID1 Mao et al., 2017; Niella et al., 2016) . There is much discussion of hybrid environments that include both artificial agents and humans (eg. BID11 Crandall et al. (2017) ). Constructing artificial agents that can do well in such environments will require going beyond the kinds of optimality theorems and experiments highlighted in this and related work.In addition, we have defined cooperative policies as those which maximize the sum of the rewards. This seems like a natural focal point in symmetric games like the ones we have studied but it is well known that human social preferences take into account factors such as inequity (Fehr & Schmidt, 1999) and social norms BID8 . To be successful, AI researchers will have to understand human social heuristics and construct agents that are in tune with human moral and social intuitions BID4 BID6 6 TECHNICAL APPENDIX 6.1 PROOF OF MAIN THEOREM We will use this basic property of almost sure convergence. If a sequence of random variables X n converges to X almost surely then DISPLAYFORM0 The intuition behind the proof is as follows: first, we show that if the CCC agent's partner plays π C then for any R s > 0 there exists a time t s at which the CCC agent's total payoff exceeds the threshold t s T by at least R s with high probability. Intuitively this is because the rate T is lower than ρ CC which is weakly lower than the rate guaranteed to a CCC agent whose partner behaves according to π C always.Second, we will show that for sufficiently large R s , if the CCC agent's total payoff exceeds the threshold by R s then the CCC agent also only plays π C from that point on with high probability.Together this implies that if the partner plays according to π C then with high probability the CCC agent behaves according to π D only a finite amount of times and thus the rates of payoffs for both agents converge to ρ CC .
We show how to use deep RL to construct agents that can solve social dilemmas beyond matrix games. Learning to play two-player general-sum games with state with imperfect information Specifies a trigger strategy (CCC) and corresponding algorithm, demonstrating convergence to efficient outcomes in social dilemmas without need for agents to observe each other's actions.