Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper proposes a new surrogate objective in joint policy optimization for coordination tasks in MARL, following single roll-out and sequential update schemes. The new surrogate depends on a new off-policy correction method similar to the one in (Munos et al., 2016), and retains the monotonic improvement guarantees on individual agent and overall performance, while also maintaining high sample efficiency. Furthermore, they empirically show that the order of the agents' update and an adaptive clipping on the importance sampling probabilities has a substantial effect on the overall performance. Finally, they provide extensive experimental results on four MARL benchmarks, where they outperform previous trust-region MARL methods. 

strength_and_weaknesses: #### $\textbf{Strength}$

1. The problem considered in the paper is well-motivated and the challenges are incrementally introduced, together with the relevant related work.
2. The proposed off-policy correction method is theoretically guaranteed to satisfy monotonic single-agent improvement and, as a consequence, overall monotonic improvement. 
3. The joint policy monotonic improvement is tighter than previous state of the art.
4. There are extensive experimental evaluations on well-known MARL benchmarks which clearly demonstrate the advantage of using A2PO. 
5. The authors further provide experimental justification for using semi-greedy agent selection and adaptive clipping in the estimated probabilities. 

#### $\textbf{Weaknesses/Questions}$

1. In the abstract it is claimed that A2PO improves sample efficiency, and in Table 1 it is again stated that the sample efficiency is high. What is meant by sample efficiency? Is it sample complexity? In any case, to my understanding, there is no subsequent result that shows an improvement of the sample efficiency in the paper. Is the statement based on a similar efficiency result imported from HAPPO since the rationale (at lease with respect to single roll-out usage) is similar? 
2. I would have liked to see some convergence guarantees of A2PO for single agent and/or multiple agents scenarios. Does A2PO converge to individual optimal policies for every agent (jointly), and if so, how fast compared to HAPPO or similar methods, in terms of agents number, episode length and epoch length? 
3. Can you elaborate on the importance of single-agent policy improvement in this setting? The reward function $r$ is the same for all agents, so there is no conflict of interest or notion of equilibrium, all agents are striving towards the same goal. If it wasn't for the improvement of joint monotonic bounds with respect to HAPPO, why should one care about single-agent policy improvement in this scenario? 

#### $\textbf{Suggestions}$

1. In some places such as first paragraph of Section 4 or Table 1, in-line equations may be improved to increase readability. 
2. In Section 3.1, either use the usual $\mathbb{P}$ notation for probability, or you may want to define what $Pr$ means. 
3. I suggest you define the sample trajectory right after the definition of the value function, since that is where you first use it.
4. In the sequential update scheme illustration (pipeline) in Section 3.2, you might want to define the surrogate objective $\mathcal{L}$.
clarity,_quality,_novelty_and_reproducibility: #### $\textbf{Clarity and Quality}$

The paper is well-written and not hard to follow. Although some definitions might be improved, this does not affect the overall clarity of the paper. Further, the problem is well-motivated and well-explained.  

#### $\textbf{Novelty}$

The novelty of the paper stands in the key insight of using the off-policy correction method into a sequential update scheme. This combination results in higher performance, both theoretically and empirically. Theoretical techniques are standard. 

#### $\textbf{Reproducibility}$

I did not check the code. 
summary_of_the_review: #### $\textbf{Summary}$

Overall, I find the contribution of the paper important to the MARL community. The authors provide an elegant solution to the single-agent policy improvement problem in trust region cooperative MARL using sequential update schemes. Furthermore, the extensive experimental results offer a complete picture of the benefits of A2PO, and also of the benefits of agent selection order.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper considers the sample efficiency and single-agent monotonic improvement guarantees in sequential (agent-by-agent) policy updates in cooperative multi-agent tasks. To retain the guarantees of monotonic improvement for single agent, the authors propose the PreOPC, which approximate the true advantage of an agent. With this single-agent monotonic bound, a tighter joint monotonic bound can be achieved. Then, by optimizing the surrogate objective with the approximated advantage, the authors propose the A2PO algorithm, which achieves better performance with two techniques: semi-greedy agent selection rule and adaptive parameter clipping. Experiments have shown the effectiveness of the proposed algorithm.
strength_and_weaknesses: Strength:
1.	The paper is well written and well organized.

2.	The paper provides the single-agent monotonic bound in the setting with single-rollout and sequential policy update.

3.	Experimental results are solid.

Weaknesses:
Some questions:
1.	It seems that the theoretical results are established on the condition that all agents can observe the global state and take this global state as input. I am somewhat unsure whether the theoretical results are fully satisfied by the experiments because in the environments such as SMAC, agents typically have access to local observation.

2.	Regarding the sequential update scheme, one concern is scalability, though the experiments in this work show that the sequential update scheme has better performance. This is because the update of an agent's policy can be done only when all preceding agents have updated their policies. When facing the settings with a large number of agents, this could be slow compared to simultaneous update schemes such as MAPPO. So, in this sense, I would like to know how long (wall clock time) it takes for the A2PO and other simultaneous update schemes such as MAPPO and CoPPO.

3.	Can the authors provide more explanations about the assumption on $\xi^i$ in Theorem 1 and 2? Compared to previous monotonic bounds, A2PO can achieve a tighter bound only given that $\xi^i$ is small enough. How to ensure this in experiments (please correct me if I have misunderstood or missed something)?

4.	Though this paper focuses on the policy-based methods, I think some discussion on the value-based methods such as QMIX and its variants is necessary (maybe in the appendix).

clarity,_quality,_novelty_and_reproducibility: Overall, I think this paper is good in clarity, quality, novelty, and reproducibility. The theoretical analysis and experimental results are solid and quite convincing.
summary_of_the_review: After reading the paper carefully, I think my comments and recommendation are accurate.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper proposed a new MARL training objective to improve training efficiency. In the experiment, the proposed method, A2PO, outperforms previous SOTA methods. 
strength_and_weaknesses: Strength:
1. I admit this paper has good writing and analysis.

Weakness:
1. The wall time may be increased due to the multiple updates. The authors should compare wall time usage of different methods.

2. The authors try to improve the sample efficiency problem of current MARL algorithms, but the performance improvements are not significant. Reasons below:

- a. The benchmarks are somewhat toy. For instance, SMAC is a well-studied benchmark, many methods have shown performance not worse than A2PO (such as MAT[1]).

- b. The author should consider MARL tasks that are really in the predicament of the sample efficiency, such as multi-agent competitive environments (such as Neural MMO[2]) and multi-agent visual navigation tasks.


 [1] Wen M, Kuba J G, Lin R, et al. Multi-Agent Reinforcement Learning is a Sequence Modeling Problem[J]. arXiv preprint arXiv:2205.14953, 2022.

 [2] Suarez, Joseph, et al. "The neural mmo platform for massively multiagent research." arXiv preprint arXiv:2110.07594 (2021).

clarity,_quality,_novelty_and_reproducibility: - Quality: Good.
- Clarity: Good.
- Originality: Good.
summary_of_the_review: This paper proposed a new MARL method and evaluated on some MARL benchmarks. But the improvements are not that satisfactory,
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper briefly reviews previous works of sequential updating schemes in multiagent trust region algorithms and points out the limitations of these works, which are either sample inefficient or lack of monotonic improvement guarantee for each agent. To achieve both sample efficiency and monotonic improvement guarantee for each agent, it proposes a new algorithm Agent-by-Agent Policy Optimization (A2PO) and analyzes its monotonic improvement bound. 
strength_and_weaknesses: **STRENGTHS**

This paper does a sufficient literature survey. It is well-structured and easy to follow. Mathematical statements and proofs look sound. Experimental results show improvements over baselines. 

WEAKNESSES

1) The motivation is a little confusing. Why should monotonic improvement for each agent be guaranteed? Is it possible that a better joint bound is obtained by giving up a monotonic improvement guarantee for each agent?

2) The sample-inefficient claim for RPISA may not be right. It is not necessary to drop $(n-1)/n$ of the collected sample. For example, [1] is an implementation of RPISA, which is proven to be sample efficient. It will be helpful to have further discussions on these algorithms both theoretically and empirically.

3) A2PO seems to take a lot of time in training. It is highly desired to elaborate on this issue.

[1] Jianing Ye, Chenghao Li, Jianhao Wang, and Chongjie Zhang. Towards Global Optimality in Cooperative MARL with Sequential Transformation. ArXiv, abs/2207.11143, 2022.


clarity,_quality,_novelty_and_reproducibility: A sound work with a clear presentation. The method also looks novel.
summary_of_the_review: This work discusses the limitations of previous multi-agent trust-region algorithms and proposes an interesting method, which empirically shows outperformance. However, some further discussions are needed to justify the significance of this work. A final recommendation will depend on how questions in WEAKNESS are clarified.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper proposes a sequential (agent by agent) policy gradient update algorithm (A2PO) in the MARL setting that guarantees monotonic policy improvement for each agent and also their joint policy. Theoretical guarantees are provided for monotonic improvement and experimental results also support the claims made in the paper. 

strength_and_weaknesses: This paper addresses an important problem in MARL. In prior work, the non-stationarity due to simultaneous policy update of agents in the multi-agent setting gives rise to high variance in the gradients, requiring more samples for convergence of each agent. Instead, the proposed A2PO algorithm uses importance sampling to weight off-policy samples used in sequential update of agent policies for the different agents in the team. 

In general, the paper is not easy to follow due to the use of several notations that are not properly defined before being referenced and therefore, forces the reader to go back and forth looking for the appropriate definitions. It would help to perhaps create a consolidated table for all the notations and symbols used in the paper. 

Specific comments about notation: 

- Page 3, Section 3.2 - what does the superscript $\mathcal{I}$ indicate in $\mathcal{L}^{\mathcal{I}}_{\hat{\pi}^{i-1}}$? 

- Page 6, first paragraph, second line after eq 6: $\mathcal{C}(\cdot,\cdot)$ has been used without first defining it. The definition is given in Page 7. 

Sec 4, Semi-greedy Agent Selection Rule: “purely greedy selection may lead to early convergence which harms the performance.” - Could you please elaborate this point? 

Sec 4, Adaptive Clipping Parameter: Could you please explain what is precisely meant by “balanced and sufficient” clipping ranges? 

Sec 5.2: The results in the ablation study are difficult to follow. The paragraph PreOPC compares to MAPPO and CoPPO with V-trace, also to HAPPO and RPISA-PPO : but these methods are not described in the main paper which makes it difficult to understand the results. 


clarity,_quality,_novelty_and_reproducibility: Although the proposed algorithm and the experimental results are interesting, the overall presentation of the paper is unsatisfactory. 


summary_of_the_review: I would recommend rejecting the paper in its current form, primarily because the presentation of the material is difficult to follow and the paper does not seem to be polished overall due to several typos, even in the appendix, that make it cumbersome to read. 

===========

After the rebuttal period, the authors' response to all the reviews has helped me understand the work more clearly. The authors have added a Table for consolidating all the notations used in the appendix. Although my initial reading of the paper gave me the impression that the paper is hard to follow and from a quick comparison of the latest version of the paper, it does not look like the authors have included any additional explanations in the text - I do not think the other reviewers had the same problem, so it might just be me. But I will agree that the authors have sufficiently addressed concerns regarding the main contributions of the paper in their response here to the reviewers and their experimental results are thorough and extensive. So, I am updating my score accordingly.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The reviewers agreed that the paper addresses an important problem in multi-agent settings and proposes a novel policy gradient update algorithm for multi-agent reinforcement learning. 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, which helped in answering their key questions. The reviewers have an overall positive assessment of the paper, and there is a consensus 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.
justification_for_why_not_higher_score: The paper could possibly be given a score of "Accept (spotlight)" based on score calibration with other accepted papers.
justification_for_why_not_lower_score: "Accept (poster)" is justified as the reviewers have an overall positive assessment, and there is a consensus for acceptance.
Decision: Accept: poster