Cooperation between self-interested individuals is a widespread phenomenon in the natural world, but remains elusive in interactions between artificially intelligent agents. Instead, naive reinforcement learning algorithms typically converge to Pareto-dominated outcomes in even the simplest of social dilemmas. An emerging literature on opponent shaping has demonstrated the ability to reach prosocial outcomes by influencing the learning of other agents. However, such methods differentiate through the learning step of other agents or optimize for meta-game dynamics, which rely on privileged access to opponents' learning algorithms or exponential sample complexity, respectively. To provide a learning rule-agnostic and sample-efficient alternative, we introduce Reciprocators, reinforcement learning agents which are intrinsically motivated to reciprocate the influence of opponents' actions on their returns. This approach seeks to modify other agents' $Q$-values by increasing their return following beneficial actions (with respect to the Reciprocator) and decreasing it after detrimental actions, guiding them towards mutually beneficial actions without directly differentiating through a model of their policy. We show that Reciprocators can be used to promote cooperation in temporally extended social dilemmas during simultaneous learning. Our code is available at https://github.com/johnlyzhou/reciprocator/.
Paper
Similar papers
Peer review
Summary
The paper proposes a method for including the influence of other agent’s into an agent’s own reward function, which is shown to promote cooperation in SSDs like IPD and the temporal version Coins. It also highlights that the method only requires first order RL algorithms, does not require access to privileged information, and does not require meta-learning.
Strengths
- The paper is well written. - The papers has clear comparisons with state-of-the-art methods. Despite lower scores in IPD against MFOS, the authors are clear to state that improvements include not only higher scores, but also in a reduction of steps required to reach cooperation, reduced complexity in opponent shaping methods, and the ability to cooperate without access to privileged information. First order RL algorithms and standard roll out processes make reproducibility and adoption of the method easier than higher order methods requiring privileged information or meta-learning.
Weaknesses
- Not all results are shown clearly for IPD-Rollout or Coins. I suggest a result matrix similar to IPD-Analytics or a clear explanation as to why it is not included, even if only in the Appendix. - Nit: Add titles to Section 5 Figure 2 and 3. - Nit: Section 5.2 Figure 2 description: percentage -> probability.
Questions
- LOLA vs. MFOS in Section 5.2 Table 1 does not match the original MFOS paper results. In MFOS Section 6.1, Table 4, LOLA vs. MFOS resulting in -2.09 for LOLA, while your section claims -1.02. Your result implies that LOLA has learned to cooperate with MFOS, when the MFOS paper shows that MFOS should learn a dominating strategy against LOLA. Where is the discrepancy coming from here? - Section 6 Figure 4 — Does each agent in this symmetric head-to-head receive the same reward and have the same probability of own coins? - Is there an experiment for Reciprocator vs. MFOS in Coin Game? - L 469: It’s unclear why the mean intrinsic reward begins as a negative number and converges to 0. I would have expected the intrinsic reward to decrease from a positive amount down to 0. - L 293: Is it possible that implementation details created a difference? - Will the codebase be made available upon acceptance? Concrete examples for your paper’s method will help future researchers implement baselines in accordance with your paper.
Rating
6
Confidence
3
Soundness
4
Presentation
4
Contribution
3
Limitations
Yes.
Summary
The authors develop a new intrinsic reward that tracks the balance of influence compared to a counterfactual baseline and provides positive/negative rewards to incentivize naive learners to cooperate. They test this algorithm in an iterated prisoner dilemma and a simplified coin game, showing positive results compared to some strong baselines on opponent shaping.
Strengths
This is a paper addresses an important topic in multi-agent reinforcement learning that will be of active interest to the NeurIPS community. The manuscript is well written and the results are well situated within the current literature. The algorithm is benchmarked against strong modern baselines and the results are discussed appropriately and clearly.
Weaknesses
- There are some missing implementation details (number of seeds, averaging methods). - I’d have liked to see more extensive evaluation on the grid environments where the RL results are more important. - The evaluation could be more robust and compare in more sophisticated games. Even the coin game is highly simplified compared to the original versions. - While the algorithm is novel in the RL literature this is highly reminiscent of the following work on commutative recipcority which develops analytical results for a similar approach. Ideally the methods here could be compared to the algorithm and analyses proposed in this work: Li, J., Zhao, X., Li, B., Rossetti, C. S., Hilbe, C., & Xia, H. (2022). Evolution of cooperation through cumulative reciprocity. Nature Computational Science, 2(10), 677-686.
Questions
- While MarkovTFT is discussed — how is this approach significantly different? Given that the algorithm learns a TFT like algorithm — when would this approach be preferred and how does it advance the literature? The authors should also discuss a more probabilistic approach to TFT published in this work: Kleiman-Weiner, M., Ho, M. K., Austerweil, J. L., Littman, M. L., & Tenenbaum, J. B. (2016). Coordinate to cooperate or compete: abstract goals and joint intentions in social interaction. In CogSci. - The opponent shaping work has the potential to shape towards a wide variety of goals and aims — this work seems more focused on just cooperation. Is that right? If so — this should be discussed in more detail as a limitation. - Unless the algorithm correctly models what it could be doing counterfactually — it won’t know how to accurately update the balance of influence. Will this always be learned rapidly? Could an adversary bias its learning away from forming an accurate model?
Rating
6
Confidence
5
Soundness
3
Presentation
4
Contribution
3
Limitations
Yes
Summary
The paper discusses an analysis of the effects of a combination of methods (1-step influence, debt mechanism and intrinsic reciprocal reward) on the emergence of cooperation in a society of artificial agents. The authors evaluate their approach for the case of n=2 using an IPD and the Coin game.
Strengths
- The reviewer personally believes that the study of cooperation in multi-agent systems is both interesting and timely. Despite the significant amount of work already conducted in this area, the reviewer welcomes further research and contributions
Weaknesses
- The contribution of each mechanism (1-step influence, debt mechanism, and intrinsic reciprocal reward) is not discussed and evaluated in the paper. In fact, the author essentially combines them without clearly showing evidence that all three are actually needed. There is also a key question about the actual improvement that is possible to obtain by introducing them (and with which parameters). The mechanisms themselves are not new. Value influence comes from (Wang et al., 2020) and the idea of debt comes from (Lerer & Peysakhovich, 2018). That is perfectly fine, but I think it is important to understand if and how they are needed for observing the emergence of cooperation. - In general, the reviewer would have welcome some discussions (in terms of intuitions) about the design choices that are at the basis of this paper. In fact, it is not completely clear *why* the proposed mechanisms should work (and also *how* in a sense). - The mechanism presented by the authors appears to be somewhat related to the idea of social learning presented in [1]. However, this work is not discussed by the authors, even though it seems closely related. I believe a discussion about the relationship between that class of approaches and the one presented in this paper would be beneficial. - It would be interesting to see a comparison with other mechanisms that foster the emergence of cooperation, particularly in the evaluation of the proposed method. Instead, the authors present comparisons with algorithms (like LOLA), which seem unrelated to the problem at hand. In fact, we know beforehand that these mechanisms do not lead to the emergence of cooperation. - The theory presented in the paper essentially refer to a multi-agent scenario. However, the authors present their results only for the case of $n=2$. This case is not really informative (also comparing with existing works in the literature cited by the authors). The emergence of cooperation with $n=2$ is a phenomenon that has characteristics quite different compared to the case of $n>2$ in my opinion. References [1] Jaques N, Lazaridou A, Hughes E, Gulcehre C, Ortega P, Strouse DJ, Leibo JZ, De Freitas N. Social influence as intrinsic motivation for multi-agent deep reinforcement learning. In International Conference on Machine Learning 2019 May 24 (pp. 3040-3049). PMLR.
Questions
- Do you have any results in terms of “ablation” considering the presence or not of the various mechanisms presented in the paper? - How does your work relate to the idea of social learning and the use of sort of social influence as intrinsic reward? - How does your work compare with Hughes et al. 2017? In fact it seems to me that the underlying mechanism might be similar to inequality aversion in a sense. - In Equation (1), the reviewer is not sure if there should be a sum over $a_i$: that appears to be an error. Could you please clarify the mathematical formulation? - Also in Equation (2), the sum over $a_i$ does not appear to be correct. Could you please discuss this formula as well? - In Section 4.4. you listed two “assumptions”. The reviewer wonders if it would have been preferable to validate them. Do you have results supporting these assumptions? - Why did you select LOLA, M-MAML, etc. as baselines? They do not appear to be relevant in a study about the emergence of cooperation. In fact, it seems to me that we know a priori that they do not lead to cooperation. It would have been more helpful to show comparison with other papers (like those that are cited in the related work) that actually lead to the emergence of cooperation. - Do you have results for the case of n>2? In fact, the theory is presented for n>2, but the evaluation is carried out for the case of n=2, which is very limiting and not sufficiently informative in my opinion.
Rating
3
Confidence
4
Soundness
2
Presentation
2
Contribution
1
Limitations
There is not a real discussion of the limitations of the work in terms of generalization to the case of the proposed approach to the case of $n>2$ (in terms of evaluation).
References
[1] Foerster, J. N. et al. Learning with Opponent-Learning Awareness. in Proceedings of the 17th International Conference on Autonomous Agents and Multiagent Systems (2018). doi:10.48550/arXiv.1709.04326. [2] Wang, T., Wang, J., Wu, Y. & Zhang, C. Influence-Based Multi-Agent Exploration. in Eighth International Conference on Learning Representations (2020). [3] Lerer, A. & Peysakhovich, A. Maintaining cooperation in complex social dilemmas using deep reinforcement learning. Preprint at https://doi.org/10.48550/arXiv.1707.01068 (2018). [4] Lu, C., Willi, T., Witt, C. A. S. D. & Foerster, J. Model-Free Opponent Shaping. in Proceedings of the 39th International Conference on Machine Learning 14398–14411 (PMLR, 2022). [5] Yang, J. et al. Learning to Incentivize Other Learning Agents. in Advances in Neural Information Processing Systems vol. 33 15208–15219 (Curran Associates, Inc., 2020).
As stated in the clarifying email sent by the conference PCs, “**Comments to paper and reviews will be fine. Comments can be seen in time. Please set the readers correctly when you post them. Reviewers are not required to take comments into consideration**.” However, we note that our follow-up comment was simply a list of references to the main rebuttal, making this a relatively minor point.
> However, the reviewer still has major concerns about this paper, especially with respect to the contribution of each specific mechanism and their inter-play. Essentially, it is unclear if all these mechanisms (and inherent complexity) are necessary. - Once again, we apologize for our lack of clarity and will use two motivating examples from the literature to further establish the basis of not just one specific mechanism, but all of them combined together to produce a single TFT-like strategy. - We reference amTFT, which seeks to achieve cooperation in SSDs by combining two pretrained strategies: one cooperative and one defective. amTFT monitors the partner's gains (debit) from deviating from a cooperative baseline and switches to defection for a fixed amount of time $k$ as punishment once the debit crosses a threshold, s.t. any gains from defection are fully neutralized. Our work takes a similar TFT-like approach, but tackles two key problems: 1) it is rarely possible to classify actions as purely cooperative or defective in temporally-extended SSDs such as Coins. 2) switching to defection for a fixed number of steps to neutralize a fixed debit threshold requires several manually selected parameters and does not generalize to complex environments. For the first problem, we use VI to assess the influence of one agent's action on another agent's expected return as a general measure of cooperativity. For the second, we develop the notion of an influence balance that is analogous to debit, but can be dynamically "paid off" via reciprocal influence at each timestep instead of an abrupt switch from cooperation to defection. - Our work can also be seen as a "cumulative reciprocator" (CURE; Li et al., 2022), which has been shown to improve the stability of cooperation compared to memory-1 TFT strategies, especially in the presence of errors (e.g., a stochastic policy). CURE depends on countable instances of cooperation and defection, which are used to compute the defection difference statistic $d(k)$ - maintaining a history of cooperation can improve stability by allowing agents to tolerate "accidental" defection from mostly cooperative opponents. While this works in simple matrix games such as IPD, it is more difficult to directly classify individual actions as cooperative or defective in temporally-extended games such as Coins, inspiring our use of the modified VI metric to measure continuous changes to expected return as a quantification of cooperation/defection. Our influence balance is then a continuous analogue to $d(k)$. - We hope that this context makes clear to the reviewer the contributions of each part **as generalized components within a single TFT-like strategy, rather than disparate mechanisms**. We would be happy to revise our manuscript to make this clearer. > With respect to the baselines, it seems to me that the type of "cooperation" in LOLA/MFOS is different from that defined by the authors. The authors of LOLA use "cooperation" as a term, but it is a different phenomenon from the emergence of cooperation of interest for the authors. - We would like to ask the reviewer for further clarification on specific reasons why it seems to them that these two types of cooperation are different. However, we provide our case here as to why we believe they are very similar. As stated in the paper and in our responses to other reviews, our method performs a form of opponent shaping (as do MFOS and LOLA) by influencing opponent returns following particular actions via reciprocation, with the goal of shaping policy updates towards actions that are favorable w.r.t. the Reciprocator's own expected return. - In social dilemmas, the environment's reward structure induces mutually defective behavior from naive learners, in which they myopically optimize for their own individual returns to converge to a Pareto-dominated outcome. Opponent shaping work such as LOLA, MFOS, and our work seek to take actions which guide opponents towards cooperative solutions, for the reason that **cooperative behavior from the opponent leads to increased return for the shaping agent** in SSDs. We distinguish this class of cooperation from a large body of work in MARL in which agent objectives are explicitly modified to include "altruistic" goals - which we once again stress fails to achieve cooperation and is exploited when faced with self-interested opponents. > With respect to the notation, I see what the authors mean, but I would suggest trying to improve/correct the notation in terms since those terms are not essentially defined in the formula, in my opinion. - We appreciate the reviewer's attention to detail - as stated in our initial rebuttal, we have updated our draft to define the unclear terms (the counterfactual reward function) and fixed the summation term. Additionally, we will clarify that $\mathbf{a}^{-i}$ denotes the vector of joint actions excluding that of agent $i$.
Many thanks for the further clarifications. Just a quick note: by doing opponent shaping, you do not have emergence of cooperation, but cooperation by design in my opinion. Again, LOLA and MFOS are generic frameworks in themselves, not designed for the problem of emergence of cooperation in my opinion.
We appreciate the reviewer's engagement in this process and address both our choice of baselines and our choice of verbiage for "emergent cooperation." Regarding our choice of baselines: - Because we position our work as an opponent shaping method with specific advantages over existing work (namely, improved sample efficiency, reliance only on first-order derivatives, and resistance to exploitation), we maintain that the baselines used in this paper such as LOLA and MFOS are appropriate. We are not aware of other shaping/cooperation-related baselines in the literature that are equally appropriate, keeping in mind that our method demonstrates cooperation in a setting of **simultaneous** learning in an **unmodified** environment. - Agents with modified prosocial objectives such as Empathic DQN (Bussmann et al., 2019), inequity aversion (Hughes et al., 2018), Altruistic Gradient Adjustment (Li et al., 2024) cannot induce cooperative behavior from self-interested opponents in SSDs and would therefore be trivial baselines. - Other opponent shaping methods such as LIO (Yang et al., 2020) and Learning to Penalize other Learning Agents (Schmid et al., 2021) explicitly modify the environment by expanding the action space to allow agents to directly influence the rewards of other agents, making them inapplicable to the original unmodified games. - The most similar works to ours are amTFT (Lerer & Peysakovich) and the hierarchical model of Kleiman-Weiner (2016) require a priori knowledge of cooperative and defective strategies and therefore cannot be extended to the simultaneous learning setting. - Finally, we note that shaping methods, unlike prosocial methods (as enumerated above), are typically evaluated head-to-head against a variety of other agent types. Our agent's resistance to exploitation and strong performance against higher-order shapers is a key result of this paper that would only be possible to demonstrate in these head-on comparisons against strong modern opponent-shaping baselines - the success of our method against prosocial agents would be trivial and of little interest to the community, in our opinion. Regarding our usage of the term "emergent cooperation": - We appreciate the reviewer's perspective and concede that "emergent cooperation" may be an overloaded term in the context of opponent shaping, since the mutual cooperation is induced by the reward structure of SSDs **combined** with opponent shaping abilities rather than the latter alone. Therefore, we have toned down the language regarding this claim in our current draft.
Summary
The authors introduce Reciprocators, RL agents that are intrinsically motivated to reciprocate the influence of other player's actions on the agent's returns. They show that this promotes cooperation in social dilemmas.
Strengths
Originality: - I do not believe this method has been proposed before Quality: - The results shown are strong. The fact that reciprocators are more resistant to extortion from MFOS is a previously unseen result. - The authors get strong results on the coin game, a challenging sequential social dilemma. Clarity: - The paper is clearly written. Significance: - As learning models become more prevalent, algorithms that learn to cooperate and are aware of each other's learning becomes increasingly important and significant. This paper proposes one such algorithm for this setting.
Weaknesses
This paper claims that it does not modify the reward structure of the environment. However, adding an intrinsic reward to cooperate seems like it very much does modify the reward of the agents. It's not particularly interesting that, when given reward for promoting cooperation, agents perform behaviors that promote cooperation. What makes prior work on opponent shaping interesting is that when given a *purely self-interested objective* (ie anticipating the opponent's learning updates), cooperation emerges naturally. In particular, the highlighting of results in Table 1 is misleading: The goal of prior works in opponent shaping is not to simply promote cooperation, but to promote *rational* cooperation (ie without being exploitable). For example, in Table 1, if I were self-interested and were told to pick an algorithm, I should always pick MFOS since it dominates all other choices. I do believe that this difference in intention between this work and the prior literature / baselines should be highlighted, as direct comparisons do not seem appropriate. Misc: The paper references the exponential sample complexity of M-FOS a few times. It might be good to reference the relevant paper [1] discussing that. Fung, K., Zhang, Q., Lu, C., Wan, J., Willi, T., & Foerster, J. Analysing the Sample Complexity of Opponent Shaping.
Questions
1. Have you considered trying your method on other SSD's beyond Coin Game? [1] discusses some of the downsides of using the coin game and introduces some new environments for doing so, available in [2] and [3]. I do not expect experiments to complete in time for the rebuttal, but it could be interesting for a camera-ready copy or future work. 2. For Line 212: doesn't augmenting coin game with the time remaining de-construct the social dilemma? At the very last time step, one should always defect. By induction, this then applies all the way back to the first time step. State aliasing prevents this from happening. [1] Khan, Akbir, et al. "Scaling Opponent Shaping to High Dimensional Games." [2] https://github.com/ucl-dark/pax [3] Rutherford, Alexander, et al. "JaxMARL: Multi-Agent RL Environments and Algorithms in JAX." Proceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems. 2024.
Rating
6
Confidence
3
Soundness
2
Presentation
2
Contribution
2
Limitations
The authors have addressed the limitations of their work.
I would like to thank the authors for their rebuttal. However, the reviewer still has major concerns about this paper, especially with respect to the contribution of each specific mechanism and their inter-play. Essentially, it is unclear if all these mechanisms (and inherent complexity) are necessary. With respect to the baselines, it seems to me that the type of “cooperation” in LOLA/MFOS is different from that defined by the authors. The authors of LOLA use “cooperation” as a term, but it is a different phenomenon from the emergence of cooperation of interest for the authors. With respect to the notation, I see what the authors mean, but I would suggest trying to improve/correct the notation in terms since those terms are not essentially defined in the formula, in my opinion. For these reasons, I will maintain my assessment of this work.
It seems that the authors also used two boxes for the answer - not sure if it is over the limit, I cannot check from the interface (for a general matter of fairness).
Thank you for the detailed response. I will discuss these responses with the other reviewers. I have no further questions at this time.
W1/2: It would be good to see the clarifications mentioned in the updated manuscript. That being said, the authors' response has largely addressed my concerns, so I will raise my score. W3: There was a typo on my end, where I put [1] I was referring to this paper: Fung, K., Zhang, Q., Lu, C., Wan, J., Willi, T., & Foerster, J. Analysing the Sample Complexity of Opponent Shaping.
We thank the reviewer for their consideration of our work and will be sure to include the clarifications in our future manuscript!
The authors have clarified my questions and I would like to maintain my score.
Decision
Accept (poster)