Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper proposes Heterogeneous-Agent Trust Region Policy Optimisation (HATPRO), in which: (1) agents do not share parameters (2) there is no assumption on the  decomposability of the joint value function. Two adaptive algorithms are introduced to enable sequential updating that benefit from a monotonic improvement guarantee.
main_review: The problem is well-formulated, but difficult to follow in some sections. Experiments are validating the claims authors made in the paper. I have the following concerns and questions regarding this paper. I can adjust my score accordingly after the authors reply to these questions:

(1) I have a bit of difficulty understanding Lemma 2 intuitively. Is there any guarantee on the positive update to happen? What if $L_\pi^{i_{1:m}}(.,.)-CD_{\mathrm{KL}}^{{\mathrm{max}}}(\pi^{i_m}_k,\pi^{i_m})$ is negative? In other words, is the  joint policy improvement guarantee based on a positivity assumption?

(2) Algorithm 1, line 7, based on my understanding from Lemma 2, inside the argmax the compliment sign should be used as: $CD_{\mathrm{KL}}^{\mathrm{max}} (.,\pi^{-i_m})$ 
not
 $CD_{\mathrm{KL}}^{{\mathrm{max}}}(.,\pi^{i_m})$. Could you correct me if I am wrong?

(3) Some intuitions are required before/after Proposition 2 to let the reader know the outcome of this proposition. In fact, based on Appendix C.3, some more auxiliary definitions are required to prove the Nash equilibrium. Also I have some doubts regarding the one-shot Markov game definition, could you elaborate?

(4) Doesn’t proposition 3 violate the assumption of HATPRO on “agents do not share parameters” and “there is no assumption on the  decomposability of the joint value function”?

(5) There are many grammatical mistakes in this paper that require a thorough proofread. E.g. 
Permutaion, theorm, enviornment,...

summary_of_the_review: The paper is strong in theoretical presentation and experiments are sufficient. However, the readability of the paper is an issue and requires some modifications.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper introduces a trust region policy optimization method for cooperative multiagent reinforcement learning with a improvement guarantee. This is accomplished by imposing an arbitrary hierarchy on the players so that each player optimizes its policy w.r.t. the players who updated before it in the hierarchy. To my knowledge, this is the first extension of PPO and TRPO to the MARL setting with an improvement guarantee. Experiments demonstrate the efficacy of the approach.
main_review: Strengths: This paper tackles a very important problem in cooperative MARL and provides a simple, elegant solution. The paper is strong theoretically. Unfortunately, the SMAC experiments could not distinguish the approaches compared, but the MuJoCo experiments revealed strong performance from the proposed approach.

Weaknesses:
1) The abstract says "even in cooperative games", but it's not clear that this is the primary setting until later. Cooperative MARL is not as general as MARL, so I would advise clarifying this distinction earlier on. Similarly, Markov games typically model non-cooperative games as well, i.e., each agent has their own reward function $r_i$. It would help to make this distinction clear here too (at the start of section 2 rather than right above the definition of $J(\pi)$). If "Cooperative" fits in the title, that would be great.
2) Please show the steps for arriving at $\hat{g}$ right before section 4.2. I was surprised to see the coefficient $\frac{\pi_{\theta}}{\pi_{\theta_k}} - 1$ disappear. It's fine if this goes in the appendix, but it should be derived fully somewhere. Sorry if I missed it.
3) In Figure 3, MADDPG appears to be starting to learn late in some of the experiments (e.g., d, e, f) to the point where it may surpass the performance of HATPRO which appears to asymptote. Can you include longer runs in the appendix?
4) The approach of imposing a hierarchy on players was also proposed at last years ICLR in EigenGame which solves PCA as an n-player game. The hierarchy is drawn randomly at the beginning of the game and held fixed for all time whereas you draw a new one at every iteration. It was also critical there for (proving) and accelerating convergence to the equilibrium. Maybe this is a more general principle for n-player games that is worth discussing in your paper.
5) I am also curious to see a discussion of the optimal hierarchy and what performance might be lost by randomly sample a hierarchy uniformly at every iteration.

Minor:
- Choice of "sequential": it was not clear to me initially that this referred to the update being sequential across the players. Maybe the word "hierarchical" or being more explicit about what is meant by sequential could help.
- Definition 1: Should you add $m < n$?
- I found it a bit confusing to use $L$ for something we want to maximize. Why not $f, g, U$?
- Theorem 1: The expectation $\mathbb{E}_{s \sim \rho_\pi}$ is defined w.r.t. an improper distribution. Can you be more rigorous (proper) here?
- Above definition 2: "assuming agent $i_1$ takes an action $\bar{a}^{i_m}$ such that $A^{i_m}(\ldots) > 0$". Can you comment on feasibility here? I expect it is always possible to find $A \ge 0$. When only $A=0$ is available for all agents, then the agents have reached a local max. Otherwise, there is room for improvement. Can you add a discussion like that if that is correct?
- Definition 2: You say let "$\bar{\pi}^{i_{1:m-1}}$ be some other joint policy". I guess the emphasis should be on "other" here. Can you not explicitly define $\pi = \prod_{n=1}^N \pi^{i_n}$ and $\bar{\pi}^{i_{1:m-1}} = \prod_{n=1}^{m-1} \hat{\pi}^{i_n}$? The details here are important and it was a bit hard to visually follow all the subscripts. Any help you can give the reader would be appreciated.
- Given this is a cooperative MARL paper, I found the Nash result interesting, but unnecessary and possibly a distraction. I suggest it can be moved to the appendix if you need space.
- Please define "one-shot" games. Are these not just multi-armed bandits? Looking at the appendix, under equation (17) on p. 20, it seems you should replace $s_t$ with $s$ or explicitly define a "one-state" game as $s_t = s \forall t$.
- typo "vaires" at the bottom of page 6
summary_of_the_review: In my opinion, this is an important theoretical result for cooperative MARL with good empirical support from experiments.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The goal of this work is to extend to the multi-agent framework the guarantee that the policy is improved monotonically after each update, as provided by TRPO for the single-agent case. The authors develop two practical algorithms where this guarantee is ensured. The algorithms are supported by a theoretical basis that explains the expansion in the multi-agent framework and relax the agents' homogeneity assumption present in the related works. An experimental evaluation showing the advantages of the proposed approach over state-of-the-art methods is provided.
main_review: Pro: 
- The paper clearly explains the related works and the improvement with respect to them. To me, the authors extend successfully a well-known state-of-the-art algorithm for single-agent RL problems in the multi-agent framework, providing potentially a new competitive algorithm also in this scenario. Claim supported by the results of the comparison with MADDPG, which is a state-of-the-art algorithm for the multi-agent problem.
- I think that giving support for heterogeneous agents is a relevant problem in order to cover more realistic problems.
- This paper provides a good number of experiments to support their claims, comparing their algorithms with the related works in many environments. Moreover, they provide the hyperparameters used in the experiments allowing results reproducibility.

Cons:
- In my opinion, it is not clearly highlighted why it is important to guarantee that the policy improves monotonically.
- The proposed algorithms work only for the cooperative setting, with a shared reward function, while MADDPG is working in both cooperative and competitive scenarios, and the letter is known to be a much harder problem. This could be potentially a weak point even if the developed algorithms show better performance in the evaluated experiments.
- The fact that the proposed approach works in cooperative scenarios only is not immediately clear neither from the title nor from the abstract and introduction. Since this represents a significant assumption, it should be made clear as soon as possible.
- The definition of Nash equilibrium for cooperative games seems quite unneeded. If all the agents share the same objective they aim at achieving the Pareto optimal solution and, given that they share the same reward, are never induced to unilaterally deviate from this solution. Can the authors explain why this definition is needed?
- The phrase "one-shot Markov game" is employed in Proposition 2, but never defined. Can the authors clarify?

Minor Issues:
- Assumption 1: this assumption is prescribing that every action is played with non-zero probability. It seems to me that this prevents from converging to deterministic policies, which can be considered a limitation of the approach. Can the authors clarify?
- Plots are not readable in grayscale, I suggest using different linestyles and/or markers
- Ticks on the plot axis are too small
summary_of_the_review: Overall, although the theoretical analysis adapts well-known tools from the safe-learning literature, I think that the proposed algorithms represent an advancement for the cooperative multi-agent setting and the experimental results are able to highlight the advantages of the proposed approach.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper proposes two algorithms, HATRPO and HAPPO, which extend TRPO and PPO to cooperative multi-agent settings, respectively. Unlike existing MARL algorithms such as IPPO and MAPPO, HATRPO/HAPPO can guarantee monotonic policy improvements,  taking advantage of the proposed multi-agent advantage decomposition lemma and sequential policy update scheme. In addition, HATRPO/HAPPO can be applied to heterogeneous agents and does not require the joint value function being decomposable. Experimental results on Mulit-Agent MuJoCo demonstrate the competitive performance of the proposed methods. 
main_review: - Strengths:
	- The paper is well motivated and clearly written overall. 
	- Compared to existing methods (e.g., IPPO and MAPPO), HATRPO/HAPPO can maintain the monotonic policy improvement guarantee of trust region learning in multi-agent reinforcement learning. This is a very nice theoretical property (I did not carefully check the proof though). The idea of updating each agent's policy sequentially while taking into account all previous updates is very interesting. 
	- Experimental results on Multi-Agent MuJoCo look quite nice. 
- Weaknesses:
	- For the experiments, I think it's important to test IPPO and MAPPO without parameter sharing to better demonstrate the advantages of the proposed methods. Also, no state-of-the-art multi-agent value-based methods are compared against. 
	- On SMAC, HATRPO/HAPPO does not perform significantly better than MAPPO overall. The authors argue that it is probably because non-parameter sharing is not required in this domain, it'd then be nice to verify this hypothesis by testing MAPPO/IPPO without parameter sharing. Also, I think the results would be more impressive if the advantages of HATRPO/HAPPO over IPPO and MAPPO can be shown in another domain other than Multi-Agent MuJoCo.
- Main questions:
	- In proposition 1, why is the optimal joint reward $2^n$? Also, this means that the reward can grow without bound as the number of agents increases, what kind of (realistic) multi-agent tasks have this property? 
	- The paper mentions that the proposed methods allow for flexible scheduling on the policy update order for agents at each iteration. How was this update order scheduled in the experiments?
	- On SMAC, why is IPPO and MADDPG not compared against (as in Multi-Agent MuJoCo)?
	- What is the level of partial observability (e.g., can agents see each other) in the Multi-Agent MuJoCo environments?
	- I found it a little bit surprising that HATRPO performs much better than HAPPO in most Multi-Agent MuJoCo tasks. The authors mention that it is because "the hard KL constraint in HATRPO, compared to the clipping version in HAPPO, relates more closely to Algorithm 1 that attains monotonic improvement guarantee." I don't fully understand why this makes HATRPO perform better. Can the authors comment a bit more about this?
	- The authors argue that one key advantage of HATRPO/HAPPO is that they do not need "any restrictive assumptions on decomposibility of the joint value function." I think the authors should make it clearer that this is just an advantage against most multi-agent value-based methods. I think QPLEX [1] does not place any restrictions on the decomposability of joint action-value function either. Furthermore, in a multi-agent actor-critic framework (say MAPPO), the joint value/action-value function can be decomposed in any manner too if you want to. 

**Post-rebuttal:**

I would like to thank the authors for their rebuttal. It's nice to see that the authors provided some results on MAPPO/IPPO without parameter sharing. It seems that MAPPO without parameter sharing performs significantly better than MAPPO with parameter sharing. I suggest the authors to provide results on all tested Multi-Agent MuJoCo tasks, rather than on just 2 tasks in Appendix G. Overall, I think it's a good paper. I maintain my score. 

[1] QPLEX: Duplex Dueling Multi-Agent Q-Learning. Wang et al.  ICLR 2021.
summary_of_the_review: I'm leaning towards accepting the paper as the proposed methods seem novel and have nice theoretical guarantee. But I'm not very confident as I believe that the paper would merit a stronger empirical section.
review_title: null

Meta-review: The submission proposes a new approach to deriving a policy gradient type algorithm for multi agent RL (MARL) where the agents are interested in a common objective but with potentially different action spaces. It extends the monotone improvement property for single agent trust-region based methods like TRPO to a multi agent update setting where the updates are performed in sequence by the agents, and uses this idea to derive new multi agent analogues of TRPO and PPO. These algorithms are shown to be competitive with existing strategies for MARL on a Starcraft environment, and superior in the case of common Mujuco benchmarks. 

All reviewers are unanimous in their appreciation for the paper's contributions. The initial concerns about clarity of the technical results, especially the improvement guarantee of the key lemma, that some reviewers had were addressed adequately by the author responses. Hence, I gladly recommend acceptance.
Decision: Accept (Poster)