Multi-agent cooperation through learning-aware policy gradients

Authors: Alexander Meulemans, Seijin Kobayashi, Johannes von Oswald, Nino Scherrer, Eric Elmoznino, Blake Aaron Richards, Guillaume Lajoie, Blaise Aguera y Arcas, Joao Sacramento
Primary area: reinforcement learning
Keywords: multi-agent learning, reinforcement learning, decentralized training, social dilemmas, cooperation, iterated prisoner's dilemma, melting pot

Abstract:
Self-interested individuals often fail to cooperate, posing a fundamental challenge for multi-agent learning. How can we achieve cooperation among self-interested, independent learning agents? Promising recent work has shown that in certain tasks cooperation can be established between ``learning-aware" agents who model the learning dynamics of each other. Here, we present the first unbiased, higher-derivative-free policy gradient algorithm for learning-aware reinforcement learning, which takes into account that other agents are themselves learning through trial and error based on multiple noisy trials. We then leverage efficient sequence models to condition behavior on long observation histories that contain traces of the learning dynamics of other agents. Training long-context policies with our algorithm leads to cooperative behavior and high returns on standard social dilemmas, including a challenging environment where temporally-extended action coordination is required. Finally, we derive from the iterated prisoner's dilemma a novel explanation for how and when cooperation arises among self-interested learning-aware agents.

Decision: accept (poster)
Reviewer scores: 6, 5, 8, 6, 8, 6

Reviews and discussion:
<thread>
creation date:
1730046598235

thread_type:
official_review

<thread_object>
creator: reviewer_ul6h

<content>
summary:
This work proposes a new paradigm for MARL that enables agents to be aware of inter-episode dynamics and presents compelling experimental results in both the iterated prisoner’s dilemma and a grid-world sequential social dilemma.

strengths:
- This work addresses a central challenge in MARL.
- The proposed framework (Figures 1 and 2) is important.
- The method parameters are thoroughly detailed in the appendix.
- Finding 1 is especially intriguing.

weaknesses:
- Line 114: The metric used in this work is ambiguous. Could you clarify which metric is applied in subsequent sections? What expectations should we have to claim that the proposed method outperforms other algorithms?
	- In Line 485, it appears the objective is solely the meta-agent's reward rather than equilibrium. Can we then say that this work is aimed at developing an algorithm to exploit naive agents?
	- Or is this an agent-based simulation method?

- Line 191: The definition states that the "state" in this game includes all agents' policy parameters. This creates an exponentially large space, especially when agents are assumed to use neural networks. In this case, the state encompasses the combined network parameters of all agents.
	- To implement a meta-agent in this setting, does the input of its policy network include the policy network parameters of other naive agents? If so, how is this optimized and implemented?
	- According to equation (4) and (5), I suppose that the meta agent does not input the others' parameters to its own policy network, but treats it by sampling the gradient. Then why is this estimation unbiased? Using sampling method does not seem to solve the non-stationarity issue. And this contradicts the motivation of this method.
	- If there are two meta-agents in the training phase, how do they treat each other? Are their gradient chains intertwined, or do they simply treat one another as naive agents?
- Line 998: The proof relies on Sutton’s policy gradient theorem, which assumes a fully observable environment. But Line 72 states that this environment is partially observable. Does the derivation still hold in this case? (I doubt the gradient computation is exact in this context, but I understand it may be an acceptable estimate for experimental purposes.)
	- Equation (4) shouldn’t be an equality but should have a scaling factor.
- Line 370: This experiment begins from a specific initialization point. The maximum expected reward is slightly lower than the cooperation reward of 1. Although this is a challenging case, what would results look like for different initialization points? Can a learning-aware agent achieve better outcomes (with an expected reward greater than 1)?
- Figure 3B and 3C: Does the proposed method require interaction with naive agents to initiate training?
- Why is there no comparison between COALA and M-FOS in Figure 5?

Minors:

- Why are all references in blue font? This formatting seems differ from other submissions.
- In Lines 14, 33, 49, 106, 122, 161, 185, 478, and 479, the single quotation marks should be replaced with double quotation marks.

questions:
Questions are mentioned in the weaknesses part.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730631693215

thread_type:
official_review

<thread_object>
creator: reviewer_mzki

<content>
summary:
The paper brings sound improvements over the current opponent shaping methods for non-cooperative general-sum games with self-interested learners. The core contributions over the existing methods are introducing a policy-gradient method (COALA-PG) capable of shaping other learners without making any assumptions on learners' optimization functions due to the sequential and batched nature of the expected return to be maximized. The method is evaluated on Iterated Prisoner's Dilemma and CleanUp environments. COALA-PG is compared to M-FOS and variants of itself as a baseline and investigation of how the pool of learners, whether they are meta or naive learners, affect reaching cooperation.

strengths:
* Introduction of a novel unbiased policy gradient formulation to shape naive learners that does not need to know the learners' optimization functions but can infer them by sequence modeling.
* Comparisons showing the effect of how learners are pooled (meta vs naive or meta vs meta etc.) give insight into how shaping is achieved.
* COALA-PG improves performance over M-FOS.
* The figures are informative.

weaknesses:
* There is insufficient explanation on why COALA-PG is so much better than batch-unaware COALA-PG which perform very similar to M-FOS. The credit assignment figure is a nice visualization to give intuition, but it does not provide concrete explanation and we have to speculate. Since batch-awareness is the main factor that makes COALA-PG's performance superior, it is difficult to attribute the success to sequence modeling and inferring the learning dynamics. There should be an investigation into how batch-awareness affect and change gradients and why batch-unaware COALA-PG is performs similar to MFOS.
* Baselines are insufficient. The only shaping method compared is the MFOS. Although mentioned in the paper, no comparison to Shaper is done in experiments. There is no comparison to LOLA either; even though MFOS is already expected to outperform LOLA, still a verification should have been done.
* There is no versus for different shaping methods, i.e. there is no experiment on how COALA-PG shapes M-FOS and vice versa.

questions:
* Why is there no experiment for LOLA?
* Why does batch-unaware COALA-PG perform so similar to M-FOS, while the batch-aware COALA-PG surpasses it? Did you investigate how gradients change and why the batch-aware gradients work so well?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730662662102

thread_type:
official_review

<thread_object>
creator: reviewer_fp5y

<content>
summary:
The paper introduces a novel policy gradient algorithm for learning-aware reinforcement learning, which allows agents to model the learning dynamics of other agents. This approach enables cooperative behavior among self-interested agents, even in complex scenarios like temporally extended action coordination. The algorithm avoids higher-order derivatives, and can handle mini-batched learning. Additionally, the paper provides a theoretical explanation for the emergence of cooperation in the iterated prisoner's dilemma based on learning awareness and agent heterogeneity.

strengths:
1. The paper tackles a core issue in multi-agent learning - fostering cooperation among self-interested agents.
2. The introduction of the first unbiased, higher-derivative-free policy gradient algorithm for learning-aware reinforcement learning is a significant contribution.
3. The proposed algorithm appears to outperform existing methods in achieving cooperation.
4.The paper proposes a novel explanation for cooperation emergence based on learning-awareness and agent heterogeneity in the iterated prisoner's dilemma.

weaknesses:
In my view, the “elegant” formulation and the batched co-player shaping POMDP appear similar to a parallel environment POMDP setup, while COALA-PG seems more like a delayed optimization applied after several episodes. This raises concerns about the true novelty and contribution of the work. I have a few specific questions regarding this point.

It’s entirely possible that I may not yet have fully understood the paper. However, improving the paper’s clarity and structure would make it more accessible and easier to follow.

I look forward to discussing these points with the authors, and I am open to raising my score if my concerns are addressed satisfactorily.

questions:
1.	What are the key differences between the proposed batched co-player shaping POMDP and a standard POMDP with parallel environments? Equation 3 appears to simply sum rewards across parallel environments, making it unclear what distinct advantages this formulation provides.
2.	The font size in the figures is too small, making it difficult to read. Enhancing font size and clarity would significantly improve readability.
3.	 There are well-known baseline methods in the mixed-motive game literature, particularly within the Cleanup environment. Why does the paper not include comparisons with these established methods?
4.       More information is needed on the simplified Cleanup environment. How does it differ from the standard Cleanup environment, and what are the implications of these differences for the study’s findings?
5.	 While the paper aims to address a mixed-motive game, the problem is formulated as a general-sum game. In my view, general-sum games are not fully equivalent to mixed-motive games. Could you clarify the rationale behind this formulation choice?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730712992348

thread_type:
official_review

<thread_object>
creator: reviewer_pfwy

<content>
summary:
To solve two challenges of general-sum games: 1. Non-stationarity of the environment, hard to choose a good equilibrium. The author propose an unbiased, higher derivative-free policy gradient algorithm for learning-aware RL, which considers how the action will influence the other agent's policy changing: They do policy gradient in meta-episode. They have extensive theoratic comparison of their meta policy gradient with prior works. And have interesting findings in the iterated prisoner's dilemma and a grid-world-like social dilemma "CleanUp".

strengths:
1. Clear writing, clear concept definition.
2. extensive theoratic comparison with prior works and experiments on two non-trivial settings.
3. enough details of implementation in the appendix.

weaknesses:
This may be difficult, but it would be great if you could show the efficiency of your method on more difficult environments of deep MARL beyond matrix game or grid world (like Agar.io[1])

[1]: Discovering Diverse Multi-Agent Strategic Behavior via Reward Randomization, ICLR 2021

questions:
None
</content>
</thread_object>

</thread>
<thread>
creation date:
1730719961449

thread_type:
official_review

<thread_object>
creator: reviewer_gxnn

<content>
summary:
This study presents a framework for multi-agent cooperation in partially observable general-sum games to enable agents to adaptively cooperate in non-stationary environments by conditioning their policies on past interactions. The COALA-PG method introduces improved policy calculation through accumulated gradients and variance reduction that enhances stability and computational efficiency. The framework is tested on benchmark tasks such as the Iterated Prisoner´s Dilemma and the Cleanup game, demonstrating cooperative behavior among decentralized agents.

strengths:
1. **History-Dependent Adaptation for Multi-Agent Cooperation:** The paper introduces a promising approach that enables agents to adaptively cooperate by conditioning policy updates on observation histories. This allows agents to respond to non-stationarity in general-sum games, specifically handling the evolving distributions of co-agent strategies as each agent independently learns and adapts over time. By incorporating these historical observations, the framework aims to maintain effective cooperation even as the behaviors of other agents shift dynamically, without explicitly modeling the non-stationarity or learning dynamics of other agents.
2. **Theoretical and Practical Advancements in Policy Gradient Estimation:** Theorems 3.1 and 3.2 present a robust policy gradient estimation method specifically designed for cooperative multi-agent learning. COALA-PG´s use of accumulated gradients and minibatch summation approach improves stability and adaptability without requiring higher-order gradients. This makes COALA-PG more scalable in comparison to methods like LOLA-DICE. Additionally, the use of value function baselines in gradient estimation reduces variance which increases COALA-PG´s practical applicability.
3. **Supporting Results Against Naive Learner Baselines:** Empirical comparisons demonstrate that COALA-PG outperforms naive, non-history-conditioned learners, demonstrating the benefit of history dependency in non-stationary environments.

weaknesses:
1. **Full History Dependency:** While history dependency enables adaptability, it may approximate full observability, especially in discrete environments. By accumulating state-action information over time, agents in discrete settings could essentially reconstruct the environment as if fully observable, reducing the framework´s applicability in scenarios where true partial observability is intended.
2. **Simplistic Experimental Scenarios:** The chosen experiments, such as the Iterated Prisoner’s Dilemma (IPD) and Cleanup, are relatively simple and do not fully demonstrate the framework´s ability to manage partial observability or complex, dynamic cooperation. IPD lacks multi-step state evolution, and while Cleanup provides more interaction, it still operates in a low-dimensional grid setting, which is easier for agents to handle than high-dimensional or real-world environments.
3. **Lack of Convergence Analysis:** COALA-PG lacks formal guarantees of stability or convergence in non-stationary environments. This leaves open questions about COALA-PG´s ability to adapt as agent strategies evolve. The study would benefit from additional theoretical or empirical validation to support its effectiveness in highly dynamic settings.

questions:
1. Given that full history dependency may reduce partially observable settings to fully observable ones in discrete environments, have the authors conducted a sample complexity analysis for handling true partial observability, where agents have limited access to or storage for historical data?
2. Could the authors elaborate on their choice of the Iterated Prisoner´s Dilemma and Cleanup as experimental benchmarks? 
3. Could the authors discuss whether any convergence properties have been considered for COALA-PG? Given the absence of a formal convergence analysis, how do the authors anticipate the framework will behave in non-stationary environments?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730725886805

thread_type:
official_review

<thread_object>
creator: reviewer_xxyh

<content>
summary:
This paper introduces a new learning-aware reinforcement learning rule derived as a policy gradient estimator. Instead of using long histories of samples, the policy gradients consider the stochastic minibatch updates used by other agents. The results show improvements in some mixed environments. Overall, the paper is well-written and well-organized. The notations are standard, and the theorems are sound.

strengths:
1. The paper is well-written and well-organized. 
2. Theoretical proofs are complete and sound.

weaknesses:
1. The motivation for proposing COALA-PG is unclear. It’s not obvious whether the issue is related to variance or other issues when using mini-batches. The authors suggest that larger mini-batches could pose a problem, but this may lead to higher variance in reward summation. However, these points are not extensively discussed in the manuscript. Additionally, compared to M-FOS, it appears that COALA-PG uses the 1/B term to scale rewards, but it seems that this scaling is still related to controlling the policy gradient’s variance.

2. Why not use a Q-function instead of summing rewards?

3. In Theorem 3.1, what is the advantage of using batches of inner episode histories instead of a long history? Are there any theoretical insights supporting this approach?

questions:
please see the weaknesses
</content>
</thread_object>

</thread>
<thread>
creation date:
1732145608080

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
General reply to all reviewers

comment:
We thank all reviewers for their useful comments, which helped us improve our paper. Triggered by their questions and concerns, we carried out a number of additional experiments and analyses, and edited the paper to improve its clarity. We summarize the main changes below.

**Detailed proof, restatement and discussion of Theorem 3.1 (COALA policy gradient) + experimental gradient decomposition analysis.** Several reviewers asked us to clarify the differences between COALA-PG, M-FOS, and a naive policy gradient calculation where every batch element is treated independently, and to explain the scaling with minibatch size in more detail. We addressed this recurring issue with a number of changes:
* The appendix now includes a self-contained, detailed derivation of the COALA-PG rule (Appendix D).
* We now present Theorem 3.1 in a form that decomposes current-episode vs. future-episode shaping returns, emphasizing the correct scaling of the two contributions as a function of minibatch size.
* Making use of this decomposition, we expanded the discussion of the theorem, contrasting our rule to M-FOS and naive applications of the policy gradient theorem, which result in improper scaling of each term.
* Lastly, we ran an experimental analysis tracking the relative size of the current-episode vs. future-episode shaping contributions throughout training for COALA-PG, M-FOS, and the naive policy gradient rule. This experiment confirms that while our rule maintains the balance between current-episode and shaping returns, the baseline methods do not (see App. H.1).

**New LOLA baseline.** Reviewer MZki asked us to extend our theoretical link between  COALA-PG and LOLA with experiments with the latter. We now added LOLA results to our experiments, including a 2D version of CleanUp-lite. First, we find that when equipping LOLA with the state-of-the-art Loaded-DiCE higher-derivative estimator [Farquhar et al. 2019], and searching for good hyperparameters, we can make LOLA cooperate on the iterated prisoner’s dilemma with sequence model policies, in contrast to what previous findings suggest [Zhao et al. 2022]. When scaling to the more complex CleanUp-lite-2D environment (see below), the LOLA baseline is outperformed by our COALA-PG estimator, suggesting that the model-free COALA-PG approach is more suitable to scale to larger environments (see Fig. 13 in App. H.2).

**CleanUp-lite-2D.** As requested by multiple reviewers, we increased the difficulty of our simplified CleanUp environment by turning it into a 2D grid world and show that COALA-PG agents find cooperative solutions, in contrast to M-FOS and LOLA (see App. H2). The Appendix now also contains an extended discussion of the environment (see App. B.1). We are still running some additional baselines on this new environment, and will move it from the appendix to the main manuscript once those are done.

**Analysis of the emergence of cooperation with LOLA.** The new version of the paper includes a novel analysis of the emergence of cooperation between agents trained with the LOLA algorithm. Our analysis reveals a crucial role played by a hyperparameter of the algorithm, namely the number of simulated co-player learning steps (often referred to as ``look-ahead steps”). As this number increases, LOLA agents transition from cooperation to extortion strategies resulting in mutual defection. Our analysis explains the origin of this phenomenon, and the similarities and differences between LOLA and COALA.

**Extended results on the analytical iterated prisoner’s dilemma.** Encouraged by Reviewer UL6h, we added new results on the analytical iterated prisoner’s dilemma, showing that meta agents learn extortion strategies similar to the Zero-Determinant extortion strategies first discovered by Dyson & Press (2012), and that unconditional defection is not a Nash equilibrium anymore in the mixed group training setup, allowing meta agents to escape (see App. C.1).

**Advantage/value estimation.** Upon request of reviewer xxyH, we added an Appendix section describing in detail the value and advantage function estimators we developed, and how COALA-PG can be used in combination with the standard A2C and PPO reinforcement learning algorithms.

**Improved figure clarity.** All experimental figures were decluttered, and replotted with larger line and font sizes.

**Updated manuscript.** We included all mentioned changes in an updated version of the manuscript.
</content>
</thread_object>

</thread>
<thread>
creation date:
1733138767411

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Final call for action

comment:
A gentle reminder that today is the last day for the reviewers to respond to our rebuttals. To the best of our knowledge, we have addressed all the main concerns and comments raised during the reviews and the discussion period with new results and clarifications, which we have added to our manuscript.

These improvements have been acknowledged by reviewer pFwY, who maintained their score of 8, and they led reviewers MZki to raise from 5 to 8 and fP5Y to raise from 3 to 6. To name a few highlights, these reviewers praised the paper's 'extensive theoretical comparisons to prior work' and 'interesting findings', 'excellent presentation', 'sound improvements over current opponent shaping methods with self-interested learners', the 'introduction of the first unbiased, higher-derivative-free policy gradient algorithm for learning-aware RL, a significant contribution', 'the proposal of a novel explanation for cooperation', and that the paper 'tackles a core issue in multi-agent learning, fostering cooperation among self-interested agents'.

We kindly ask reviewers **xxyH, GXnN, fP5Y and UL6h** to respond whether there are any remaining concerns that we haven't adequately addressed, or new concerns that arose after reading our rebuttal, that would prevent the reviewers from further raising their score.

Below we briefly summarize the main concerns of reviewers xxyH, GXnN, fP5Y and UL6h and how we addressed them with new results and clarifications.

**_Reviewer xxyH_**

**Main concerns and comments:**
* **Unclear motivation for COALA-PG:** The reviewer questioned the specific issue that COALA-PG addresses, asking whether it's related to variance or other problems arising from the use of mini-batches.
* **Comparison to Q-function:** The reviewer asked why we didn't use a Q-function instead of summing rewards.
* **Batching versus concatenation:** The reviewer asked why we use batches of inner episode histories instead of concatenating inner episodes into a single long history.

**Our responses:**
* **Clarified motivation:** We explained that the issue is not about estimator variance but about incorrect weighting of gradient contributions from current and future episodes in prior work. We provided a detailed explanation of how COALA-PG correctly balances these contributions, which we supported with a new experimental analysis (Figure 12 in Appendix H.1). We also included a new visualization of the difference between the COALA-PG update and the batch-unaware policy gradient update (Figure 11 in Appendix G).
* **Comparison to Q-function:** We acknowledged that the original paper lacked clarity on this point and added a new Appendix section (Appendix A) detailing the value and advantage function estimators we developed, including the advantage-based estimator used with COALA-PG.
* **Batching versus concatenation:** We clarified the practical advantages of using batches, such as avoiding prohibitively long sequence model contexts and simplifying the learning of the meta agent.
The reviewer acknowledged reading our responses, but maintains their score, without providing any explanation on which further concerns remain that prevent them from further raising their score. 

**_Reviewer GXnN_**

**Main concerns and comments:**
* **Partial Observability:** The reviewer was concerned that full history dependency might reduce the applicability of our framework to truly partially observable scenarios.
* **Simplistic Environments:** The reviewer found the experimental scenarios too simplistic and not fully demonstrative of the framework's ability to handle complex, dynamic cooperation in partially observable environments.
* **Lack of Convergence Analysis:** The reviewer pointed out the absence of a formal convergence analysis for COALA-PG in non-stationary environments.

**Our responses:**
* **Partial Observability:** We addressed this by (i) including a new proof of Theorem 3.1, showing that COALA-PG remains valid in partially observable settings (Appendix D), and (ii) introducing a more challenging 2D version of the CleanUp-lite environment (Appendix B.1, H.2).
* **Simplistic Environments:** We added results on the new, more complex CleanUp-lite-2D environment, demonstrating the effectiveness of COALA-PG in a harder partially observable setting (Appendix B.1, H.2).
* **Lack of Convergence Analysis:** We responded by (i) providing a detailed empirical analysis of learning trajectories on the iterated prisoner's dilemma (Section 4), (ii) adding new results on the convergence behavior of meta-agents (Appendix C.1), and (iii) highlighting the non-stationary nature of our experiments in Section 5 (Figure 5C and Figure 7)
</content>
</thread_object>

</thread>


Metareview:
metareview:
The reviewers acknowledged that the paper studies an interesting problem of cooperation among self-interested learning agents in multi-agent systems,  and the proposed method of learning-aware policy gradients is novel with significant contributions. However, the reviewers also raised several concerns and questions in their initial reviews. We want to thank the authors for their responses and active engagement during the discussion phase. The reviewers appreciated the responses and have an overall positive assessment of the paper for acceptance. The reviewers have provided detailed feedback, and we strongly encourage the authors to incorporate this feedback when preparing the final version of the paper.