Multi-agent cooperation through learning-aware policy gradients

We thank the reviewer for their thoughtful review, which helped us improve our work. We reply to the concerns and questions raised point-by-point below.

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?

We note that for the social dilemmas we focused on, equilibria with high sole agent rewards coincide with the highest global social welfare equilibria. As such, it is easy to define the metric, either using individual reward, or total rewards received by all involved meta agents. We nonetheless agree that this was unclear, and that it is in general not obvious how to define success in general-sum games.

To clarify the points raised, we have implemented the following changes in the paper:

• We clarify the metrics on the captions of Figs. 5 and 7. In general, for situations where a meta agent only plays against naive learners with the objective to shape them, we report the individual average reward of the meta agent. For situations where meta agents play against a mixed group of other meta agents and naive learners, we report the average global social welfare while evaluating meta agents against other meta agents in the group.
• We now clearly state in the beginning of Section 5 that our aims are twofold: to understand (i) when meta-agents succeed in exploiting naive agents, and (ii) when cooperation is achieved among meta-agents. Our method outperforms other baselines on these two fronts: (i) it is more successful in exploiting naive agents, and (ii), when playing with other COALA agents, it achieves cooperative equilibria which Pareto dominates (achieves strictly more reward for all meta agents involved) equilibria found by the M-FOS and batch-unaware baselines.

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?

Our COALA method is grounded in a POMDP setting. Specifically, even though the hidden state of the environment includes all agents’ policy parameters, the policy of the meta agent is only conditioned on the observation history, which we design to not include the other agents’ policy parameters. This allows us to overcome the problem of requiring access to the other agents’ parameters, while still having access to principled policy gradients. Instead of explicitly providing the parameters of co-players to the meta-agent policy, the sequence model meta-learns to infer “in-context” the parameters and learning algorithms employed by co-players based solely on observations including their past actions. Our approach is similar in spirit to the classic single-agent meta reinforcement learning methods due to Wang et al., 2016, and Duan et al., 2017. This is in fact one of the key strengths of our method, in contrast to e.g. LOLA [Foerster et al. 2017], or some of the implementations in M-FOS, which require explicit access to co-player parameters.

We will clarify this contrast in the final version of our manuscript.

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.

As we constructed a correct POMDP formulation of the co-player shaping setup, we can follow standard RL practices to derive an unbiased policy gradient estimator corresponding to this POMDP, using Monte Carlo samples and value function approximators (c.f. Appendix A and D). Note that we neither require access to the co-players’ parameters, nor require to sample gradient updates of co-players. For full transparency, we have rewritten Theorem 3.1 and its proof from scratch, and in full detail, without invoking prior work (c.f. Appendix D). The new proof should make it clear that the estimator is indeed unbiased, and exact.

We thank the reviewer for the constructive comments that has helped us improve our paper. We reply to each point separately below.

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. [...] 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?

We thank the reviewer for this excellent comment. To understand what is going on, it is helpful to differentiate the contributions to the policy gradient arising from the current inner episode return, and the contributions arising from future inner episode returns. The former provides a learning pressure to play well against the current policy of other agents, whereas the latter provides co-player shaping pressure. The main difference between COALA-PG and M-FOS (Eq. 3 vs Eq. 26) is that COALA-PG scales the return of the current inner episode by 1/B, whereas M-FOS does not. This scaling is crucial, as the the influence of an action on future inner episodes is of order O(1/B) because the naive learner averages its update over the B inner episode trajectories. Hence, by scaling the inner episode return by 1/B, COALA-PG ensures that both contributions (current and future episodes) have the same scaling w.r.t. B, and finally by summing the policy gradient over the minibatch instead of averaging, we end up with a policy gradient of O(1). M-FOS and batch-unaware COALA do not scale the current inner episode return, which causes the co-player shaping learning signal to vanish w.r.t. the current inner episode return, resulting in poor shaping performance. Ultimately, this problem can be traced back to a misspecification of the underlying POMDP, which does not take into account inner episode minibatches. The key message here is that the proposed batched co-player shaping POMDP with appropriate scaling solves the issue.

To clarify this we have implemented three changes in the paper:

• We now include an additional analysis comparing the contribution of the current and future episodes for the different learning rules considered in the paper. Specifically, figure 12 in appendix H.1 tracks throughout meta-training the contributions to the parameter update that stem from current vs. future episodes, with the latter measuring the shaping influence of an action on co-player learning. Our analysis shows that COALA-PG indeed balances the two contributions, maintaining an O(1) ratio, whereas the other learning rules do not.
• We have included a new visualization of the difference between the COALA-PG update and the batch-unaware policy gradient update (see Fig. 11 in App. G)
• We have rewritten Theorem 3.1 and the passage below to discuss this point. It now reads:

There are three important differences between COALA-PG and naively applying policy gradient methods to individual trajectories in a batch. (i) Each gradient term for an individual action $a_l^{i,b}$ takes into account the future inner episode returns averaged over the whole minibatch, instead of the future return along trajectory $b$ (see Fig. 2). This allows taking into account the influence of this action on the parameter update of the naive learner, which influences all trajectories in the minibatch after that update. (ii) Instead of averaging the policy gradients for each trajectory in the batch, COALA-PG accumulates (sums) them. This is important, as otherwise the learning signal would vanish in the limit of large minibatches. Intuitively, when a naive learner uses a large minibatch for its updates, the effect of a single action on the naive learner's update is small ($O(1/B)$), and this must be compensated by summing all such small effects. (iii) To ensure a correct balance between the return from the current inner episode $m_l$ and the return from future inner episodes, COALA-PG rescales the current episode return by $1/B$. Figure 12 in App. H shows empirically that COALA-PG correctly balances the policy gradient terms arising from the current inner episode return versus the future inner episode returns, whereas M-FOS (Lu et al., 2022) and a naive policy gradient that ignores the other parallel trajectories over-emphasize the current inner episode return, causing them to lose the co-player shaping learning signals.

We thank the reviewer for the constructive comments that have helped us improve the clarity of our paper. We reply to each point separately below.

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. 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?

In our batched co-player shaping POMDP, the hidden state does not only contain the environment state, but also the policy parameters and update rules of all naive co-players in the environment. Hence, even in simple discrete environments, our setup is a challenging partially observable setting, as we use modern sequence models as policies for all involved agents. It follows that our results from Section 5 provide empirical support that our COALA framework is applicable in scenarios with true partial observability.

To further address the reviewer’s concerns about the applicability of COALA to partially observable scenarios, we included a new proof of Theorem 3.1, showing from scratch that the COALA policy gradient is a correct policy gradient, even when the environment is not fully observable (see Appendix D).

Finally, we now include a more challenging version of the CleanUp-lite environment, extending it to a larger 2D grid, making it a harder partially-observable setting. More information on this point follows in the next section.

While we agree with the reviewer that a sample complexity analysis would be interesting, we argue that our theoretical results combined with the empirical verifications that our COALA-PG method works in true partially observable environments, are sufficient contributions to introduce our novel framework, and defer more theoretical work on sample complexity to future work.

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. Could the authors elaborate on their choice of the Iterated Prisoner´s Dilemma and Cleanup as experimental benchmarks?

Despite its simplicity, the iterated prisoner’s dilemma is still a challenging environment to reach cooperative equilibria, when agents use complex sequence models instead of simple tabular policies. Figure 5 shows that indeed, the iterated prisoner’s dilemma exhibits meaningful performance differences between our COALA-PG method and state-of-the-art baseline methods. CleanUp-lite introduces two new challenges: (i) cooperation or defection are now temporally extended action sequences instead of atomic actions, and (ii) the social dilemma becomes more challenging, combining a tragedy of the commons challenge (cleaning vs harvesting) with an iterated prisoner’s dilemma (zapping other agents). This allows us to see further differences between our COALA-PG method and state-of-the-art baselines.

We agree with the reviewer that scaling learning-aware multi-agent RL methods towards high-dimensional settings is an important current challenge of the field. We emphasize that in the current status of the field, we can already observe meaningful differences between different approaches on simple environments, providing us with useful insights on which approaches could scale well to more complicated environments.

To address the reviewer’s concern that our chosen environments might be too simplistic, we included results on a new environment: CleanUp-lite-2D. CleanUp-lite-2D increases the difficulty of our simplified CleanUp environment by turning it into a 2D grid world (see App. B.1 for the environment details). We show that COALA-PG finds high-rewarding cooperative solutions similar to those in the more simple CleanUp-lite environment, and outperform M-FOS and LOLA which fail to cooperate (see App. H2).

We thank the reviewer for their thoughtful feedback that has helped us improve our paper. We reply to the points raised below.

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.

The issue in prior work that we are addressing is not related to estimator variance per se, but to incorrect weighting of different elements in the total gradient. Both M-FOS (Eq. 26) and naive policy gradient methods ("batch-unaware”, Eq. 25) incorrectly balance the contributions to the total gradient that stem from the current episode, with those that stem from future episodes. The latter measures the co-player shaping effects of a given action. Although no explicit scaling factor is used for the future inner episode returns, this co-player shaping contribution to the policy gradient scales with O(1/B). This O(1/B) scaling arises because the naive learner averages its parameter update over the B inner episode trajectories, and hence an action in a single trajectory will only have a O(1/B) influence on the naive learner’s parameter update, which leads to an imbalance with the other contribution to the gradient from the current episode. By scaling the inner episode return by 1/B, COALA-PG ensures that both contributions have the same scaling w.r.t. B, and finally by summing the policy gradient over the minibatch instead of averaging, we end up with a policy gradient of O(1). In contrast, M-FOS and batch-unaware COALA do not scale the current inner episode return, which causes the co-player shaping learning signal to vanish w.r.t. the current inner episode, resulting in poor shaping performance. Ultimately, this problem can be traced back to a misspecification of the underlying POMDP, which does not take into account inner episode minibatches. The proposed batched co-player shaping POMDP solves the issue.

To clarify this we have implemented three changes in the paper:

• We now include a new experimental analysis measuring the present-episode vs. future-shaping contributions to the gradient for different estimators throughout meta-training, see Fig. 12 in App. H.1. COALA-PG balances the two, achieving a ratio of order one, whereas standard (batch-unaware) learning and M-FOS do not.
• We have included a new visualization of the difference between the COALA-PG update and the batch-unaware policy gradient update (see Fig. 11 in App. G)
• We have rewritten Theorem 3.1 and the passage below to discuss this point. It now reads:

There are three important differences between COALA-PG and naively applying policy gradient methods to individual trajectories in a batch. (i) Each gradient term for an individual action $a_l^{i,b}$ takes into account the future inner episode returns averaged over the whole minibatch, instead of the future return along trajectory $b$ (see Fig. 2). This allows taking into account the influence of this action on the parameter update of the naive learner, which influences all trajectories in the minibatch after that update. (ii) Instead of averaging the policy gradients for each trajectory in the batch, COALA-PG accumulates (sums) them. This is important, as otherwise the learning signal would vanish in the limit of large minibatches. Intuitively, when a naive learner uses a large minibatch for its updates, the effect of a single action on the naive learner's update is small ($O(1/B)$), and this must be compensated by summing all such small effects. (iii) To ensure a correct balance between the return from the current inner episode $m_l$ and the return from future inner episodes, COALA-PG rescales the current episode return by $1/B$. Figure 12 in App. H shows empirically that COALA-PG correctly balances the policy gradient terms arising from the current inner episode return versus the future inner episode returns, whereas M-FOS (Lu et al., 2022) and a naive policy gradient that ignores the other parallel trajectories over-emphasize the current inner episode return, causing them to lose the co-player shaping learning signals.

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

We now realize that the paper was not clear on this point, so we thank the reviewer for raising this question. We do learn value functions and use them to reduce gradient estimation variance. We have now included a new Appendix section devoted to this (see Appendix A) and we now discuss in the main text the advantage-based estimator that we developed for COALA-PG, and that we use in the simulations.

We thank the reviewer for the constructive comments that have helped us improve the clarity of our paper. We reply to each point separately below.

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. 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.

This is an important point, and we actually did attend to this matter with our controls, so we clarified it in the updated manuscript. In the manuscript, we referred to standard POMDPs with parallel environments as “batch-unaware”, because the parallel trajectories do not interact with each other. In contrast, in our batched co-player shaping POMDP, the parallel trajectories interact with each other through the parameter updates of the naive learner: after each inner episode, the naive learners update their parameters based on all the parallel current inner episodes. Hence, actions of the meta agent in parallel trajectory $b$ can influence the naive agent’s parameters used in other parallel trajectories $b’\neq b$. As a consequence, the COALA policy gradient (Eq. 3) averages future returns over all parallel batches after a specific action $a_l^{i,b}$, instead of only considering the future return of trajectory $b$ which would be the case in the batch-unaware POMDP (i.e. parallel environments).

The standard parallel environment POMDP leads to an update that undervalues the effect of an action on future-episode behavior of co-players, as it only includes a single trajectory in its calculation of the updates. In other words, it overemphasizes current-episode performance over shaping co-player learning. This results in poor performance of the batch-unaware COALA baseline on all experiments considered (c.f. Section 5), compared to our COALA-PG method that correctly handles the batched co-player POMDP, thereby further illustrating that our contribution of correctly formulating the batched co-player shaping POMDP is crucial for achieving good performance. To clarify this we have implemented three changes in the paper:

• We now include a new experimental analysis measuring the present-episode vs. future-shaping contributions to the gradient for different estimators throughout meta-training, see Fig. 12 in Appendix H.1. COALA-PG balances the two, achieving a ratio of order one, whereas standard (batch-unaware) learning and M-FOS do not.
• We have rewritten Theorem 3.1 and the passage below to discuss this point. It now reads:

There are three important differences between COALA-PG and naively applying policy gradient methods to individual trajectories in a batch. (i) Each gradient term for an individual action $a_l^{i,b}$ takes into account the future inner episode returns averaged over the whole minibatch, instead of the future return along trajectory $b$ (see Fig. 2). This allows taking into account the influence of this action on the parameter update of the naive learner, which influences all trajectories in the minibatch after that update. (ii) Instead of averaging the policy gradients for each trajectory in the batch, COALA-PG accumulates (sums) them. This is important, as otherwise the learning signal would vanish in the limit of large minibatches. Intuitively, when a naive learner uses a large minibatch for its updates, the effect of a single action on the naive learner's update is small ($O(1/B)$), and this must be compensated by summing all such small effects. (iii) To ensure a correct balance between the return from the current inner episode $m_l$ and the return from future inner episodes, COALA-PG rescales the current episode return by $1/B$. Figure 12 in App. H shows empirically that COALA-PG correctly balances the policy gradient terms arising from the current inner episode return versus the future inner episode returns, whereas M-FOS (Lu et al., 2022) and a naive policy gradient that ignores the other parallel trajectories over-emphasize the current inner episode return, causing them to lose the co-player shaping learning signals.

• We include a new visualization of the difference between the batched co-player shaping POMDP and the batch-unaware POMDP (Fig. 11 in Appendix G). We hope that these changes and additional explanations make the novelty and contribution of our work more clear. We remain open to address any further questions the reviewer might have on this important point.

Thanks for your response. Your response have solved most my questions. Thus, I will increase my score.

We thank the reviewer for the encouraging comments.

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])

While still being a grid world environment, we note that we have now included a more complicated 2D version of CleanUp-Lite in the paper (see Appendix H.2 in the updated pdf). Our previous findings hold in this more challenging setting. Scaling up learning-aware MARL methods beyond grid worlds is a general unsolved challenge in the field, which we (and other labs) aim to address in future work in the coming years.

We remain open to any other remarks to guide the improvement of our paper that can be addressed within the timeframe of the ICLR rebuttals.

Reviewer fP5Y

Main concerns and comments:

• Novelty of the batched co-player shaping POMDP. The reviewer raised concerns about the similarity between the batched co-player shaping POMDP, and a standard parallel-environment-POMDP setup.
• CleanUp-lite environment specifications. The reviewer asked for more information on the CleanUp-lite environment and how it differs from the CleanUp environment in Melting Pot.
• Comparison to reward-shaping methods. The reviewer asked why we do not compare our method against established reward-shaping methods.

Our responses and further discussion.

• Novelty of the batched co-player shaping POMDP. We clarified that in our batched co-player shaping POMDP, parallel trajectories interact with each other through the naive learners’ parameter updates, which use the full batch of current inner episodes. Correctly formulating this batched co-player shaping is crucial for obtaining a correct policy gradient, explaining the improved performance of COALA-PG compared to M-FOS which uses a biased policy gradient estimator. We included a new schematic (Figure 11) to clarify our setup.
• CleanUp-lite environment specifications. We added detailed environment specifications in Appendix B.1.
• Comparison to reward-shaping methods. We clarified that there are two main approaches in the mixed-motive multi-agent RL (MARL) literature to solve mixed-motive games: (i) learning-aware RL methods, and (ii) reward-shaping to change the incentive structure of the game, making cooperative equilibria easier to find. Our method is situated in the former field, motivating our choice of comparing it to other learning-aware MARL methods. To satisfy the reviewer’s request for more comparisons, we included an extra baseline: LOLA equipped with the state-of-the-art Loaded DiCE estimator.
• The reviewer acknowledged that we addressed most of their questions, and raised their score from 3 to 6.
• The reviewer raised a last question that they would still be curious about how the performance of our method compares to other reward-shaping methods. We clarified that the main motivation for our work (and the learning-awareness field in general) is fundamentally different from the reward-shaping field. We focus on how cooperation can be achieved from optimizing purely selfish objectives, without requiring privileged access to other agent’s rewards and without relying on all co-player to use pro-social reward-shaping. Hence, comparing to reward-shaping methods that change purely selfish objectives to pro-social objectives, would not fit well in our current work. We note that Reviewer MZki stressed the ‘sound improvements’ brought by our method in the most general setting, where no explicit assumptions need be made on the other agents’ learning algorithms and objective functions, thus covering the case of purely self-interested agents.