Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper provides a general template for MARL algorithmic designs. They prove that algorithms derived from the HAML template satisfy the desired properties of the monotonic improvement of the joint reward and the convergence to Nash equilibrium. 
strength_and_weaknesses: +: The paper has nice result for the properties of a class of policies. 

-: The main issue is that achieving NE for cooperative games may not be the best strategy. We ideally want the cooperative equilibrium in a decentralized fashion. This aspect should be detailed better. 

-: The other issue is the comparisons. The entire area of CTDE is not considered for evaluations. See for instance the comparison strategies in recent NeurIPS paper: "PAC: Assisted Value Factorisation with Counterfactual Predictions in Multi-Agent Reinforcement Learning". Many of them are at https://github.com/hijkzzz/pymarl2 . 
clarity,_quality,_novelty_and_reproducibility: The paper is ok to read, while explicit list of assumptions would have helped. 
summary_of_the_review: This paper provides a general template for MARL algorithmic designs. They prove that algorithms derived from the HAML template satisfy the desired properties of the monotonic improvement of the joint reward and the convergence to Nash equilibrium. Expanding the reason for limiting to Nash equilibrium and better comparisons would have been good.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: Authors present a provably convergent MARL algorithmic template HAML, from which two existing MARL algorithms are derived as demonstration. In addition, further two MARL algorithms are cast as HAML instances to rid of their shortcoming defined as 'traps' in the paper. SMAC and MAMuJoCo evaluation shows better performance, or in cases of comparable reward levels, narrower confidence intervals.
strength_and_weaknesses: Paper's main strength lies in the provability of more stable convergence properties. Even though mirror learning concepts have been proposed in closely relevant previous works, extending those results to the multi-agent setting is far from trivial. Authors make a strong case for the correctness argument of HAMO and its monotonic improvement over the course of the training iterations.

Tracing the mirror learning idea back to the Kuba2022b paper does suggest that HAMO is meant to operate with policy gradient methods only, it would be nicer if a clear delimitation/disclaimer is made in the present paper. On a related note, some comments on representative value-based methods and/or communication-based MARL methods can help better position HAML and clarify which methods are/aren't HAMO's competitors.

The theorems and proofs support just exactly what is claimed earlier in the paper, but the current version reads a little like a dry array of correctly built up arguments. Insightful elaboration and a curated interpretation of what's between and beyond the equations would be an excellent addition. For example, at the bottom of page 5, what real-world implications do these two facts carry? Does HAMO collapse to a special case?

As is the case with provably convergent MARL algorithms, the training time/computation cost may have been the factor traded off for the convergence. Figures 1 to 3 are all plotted against environment steps, but one step of training a HAML instance would carry an expensive computation (Compute the advantage function A_\pi_k in Algorithm Template 1). Please comment on the computation overhead.
clarity,_quality,_novelty_and_reproducibility: Clarity
Concepts, even the borrowed ones, are well introduced. Theorems build up in an easy flow.
Results should be clarified or normalized against any computation overhead.

Quality
Evaluation environments and tested baselines are varied. Unresolved curiosities are mostly addressed in the appendix (except the training time / computation overhead). Position in literature is clear, and contribution to better understanding the growing number of MARL algorithms is an appealing argument.

Originality
To the best of my knowledge, HAMO, HAML, and HADF are original. However, it is almost easy to misread the paper as a 'part 2' or 'chapter 2' paper to the Kuba2022b mirror learning paper. Perhaps, after establishing a clear connection to that paper initially, the rest of this HAML paper could proceed with fewer references to the mirror learning paper and instead develop a detached and independent series of claims and logical arguments.
summary_of_the_review: Authors make a clearly positioned contribution to explain policy gradient MARL algorithms in terms of their convergence properties and empirically show their findings. Minor points of revision include: delimitation with respect to value-based/communication-based MARL, more interpretive technicalities such as in Definition 3, and some comments on training time / computation.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: Recently Kuba et al. (2022a) introduced two cooperative MARL algorithms, HATRPO and HAPPO, which employed the idea of using a version of a multiagent advantage function which captures agents updating their portion of a policy sequentially rather than simultaneously and showed that it provides a monotone policy improvement guarantee.  Also recently, Kuba et al. (2022b) introduced Mirror learning as a way of understanding why algorithms like TRPO and PPO have a monotone improvement property.  This paper combines the two ideas showing that a richer class of algorithms which have both sequential advantage-based updates and use Mirror-learning style control of updates have the monotone improvement property.  This is empirically demonstrated by showing that instances of A2C and DDPG using the sequential advantage updates outperform traditional versions.
strength_and_weaknesses: On the positive side, in combining these two ideas the paper provides additional insight into the (2022a) paper by both simplifying and generalizing the features needed and available (respectively) to guarantee policy improvement in cooperative MARL.  While this doesn’t require a lot of truly novel technical content, with the empirical demonstration of the benefits I think overall I would be happy to see these results in a good conference

On the negative side, the presentation is deficient in four respects.  First, the approach is presented as a monolithic whole, without identifying for readers some of the simplicity of the results.  In my view the whole inclusion of the drift functional / mirror learning is essentially a subsidiary result.  Theorem 1 holds even for the trivial drift functional, which means the key insight of the paper around the multi-agent advantage decomposition alone being sufficient is being buried under a lot of irrelevant technical detail.  Indeed, the HADF barely appears in the proof of Theorem 1 except as bookkeeping that could be replaced by 0.  In fact I think even greater generality is possible; the theorem requires a sequence of permutations over the agents while I believe it actually suffices that all agents be allowed to update an infinite number of times (although perhaps the permutation approach is more data efficient).  This detail is also irrelevant to the empirical results, which as the paper points out use neither HADFs nor neighborhood operators.  So while this material would be nice to include as an extension, it actually obscures and detracts from the main thrust of the paper.

Second, the paper presents as novel insights things which have long been known in the cs/econ literature on multiagent learning.  At least as far back as the 1996 Monderer and Shapley “Potential Games” paper, the convergence of dynamics where one agent at a time improves to Nash equilibrium in identical interest games has been well known.  Similarly, the problems of miscoordination when multiple agent update at the same time (which is explained in a needlessly complex way in Proposition 2) are well understood.  See, for example, Example 2 from “The Logit-Response Dynamics” by Alos-Ferrer and Netzer.  So while there is certainly some technical novelty in bringing these ideas to the richer cooperative MARL setting, the ideas themselves are not new.  Similarly, the limitations of homogeneous policies are well known.

Third, this exemplifies a broader issue where the paper overstates its significance.  This happens at a low level with word choices which are excessive such as “fundamental theorem”, “endow MARL researchers”, and .  At a higher level, it is misleading to say in the introduction that CDTE methods lack “convergence results of any kind”.  COMA certainly comes with a convergence proof.  Kuba et al. 2022a are more careful, pointing out rather that COMA doesn’t provide any trust-region-style control of the step size and so is less stable.  But while this paper enables that, it doesn’t have any theory to establish how using it guarantees better stability.  So in that sense I don’t think the convergence theory in this paper is any stronger than in COMA.  While this sort of update does empirically seem to promote stability, as already mentioned the experiments in this paper don’t use it!  The paper also fails to give due credit to the two Kuba et al. 2022 papers.  The proof of Theorem 1 is straightforward and seems largely the same as the proof of the main result from the 2022a paper, but no technical credit is given to that paper for this.  The material in 4.1 is essentially a direct generalization of the material in the 2022b paper, and Lemma 2 is a direct generalization of their Lemma 3.3.  Yet that paper is mentioned only once in passing in that part.

Fourth, there are a number of small errors, unclear notation, and issues with definitions that should be corrected.  See details below.

clarity,_quality,_novelty_and_reproducibility: Equation (1) uses the advantage with 2 arguments without explaining the intent that the implicit third argument is the (lack of) action for an empty set of agents.

While Proposition 2 is technically correct, its inclusion is misleading.  It is being used to critique agents merely finding an “improving direction.”  But the Proposition actually assumes agents all take the full step to their best response.  If the agents actually take a small enough step then it really will be an improvement even without coordination.  Perhaps there is a more subtle point to be made here about the importance of step size control, but this example is simply too blunt as a critique of standard multiagent policy gradient methods.  In particular, it is incorrect to claim without further evidence that MAA2C and MAPPO get “caught” or “fall into the trap of Proposition 2”

There lack of comparison to COMA at 3.2 seems an omission given the discussion above regarding the relative convergence guarantees.

The notation \mathbb{P} doesn’t appear to be defined.  I assume it means powerset?

The arguments do the HADF are not clearly explained.  It is ambiguous which policy is which.  The role of \mathbb{P}(-i) is not explained.  Presumably this is how we get the j on the right hand side?  But note that we need an order for j per the definition of that notation and sets are unordered.

More broadly the definition of a HADF is hard to parse.  It would help to break the giant sentence that runs through most of the definition environment into smaller, more manageable pieces.

Lemma 2 should require (5) to hold for all choices of m in addition to all choices of s.

The proof of Theorem 1 is in appendix C, not A.

In the proof of Proposition 2, the derivation before (8) is for \pi_old, not \pi_new

In the first eqnarray of the proof of Lemma 2, the expectation over actions gets lost in the middle two lines.

summary_of_the_review: Acceptable results, but presentation that is deficient in key ways.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper studies MARL problems and proposes the Heterogeneous-Agent Mirror Learning (HAML) framework that enjoys monotonic improvement of the joint reward and convergence to NE. They show that HAML includes HATRPO and HAPPO as special instances. They provide HAML extensions of A2C and DDPG and show their effectiveness in experiments. 
strength_and_weaknesses: ## Strength
- This paper is well-written and nicely organized. The proofs seem to be theoretically sound to me.
- The topic of this paper, designing good MARL algorithms that enjoys proper convergence and reward improvement property, is the core of the relevant literature and is of great significance.  
- The proposed framework is novel to me and is nicely motivated. The theoretical guarantee is strong.
- The experiments are extensive and convincing.

## Weaknesses
- The maximization step of HAML seems to be the bottleneck of computational complexity. The authors remark that a few steps of gradient ascent are used in this process. The characterization of the number of steps needed is missing. It would be helpful if the authors could provide discussions on this part to complete the store of the framework.


clarity,_quality,_novelty_and_reproducibility: This paper is of nice quality and is doing good in clarity and novelty. 
summary_of_the_review: In summary, this paper is well-written and the topic is of great importance. The proposed framework is nicely motivated and enjoys a strong theoretical guarantee. The framework includes important SOTA algorithms as special instances. The extensions of the framework are achieving competitive performance in experiments.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: Summary:
This paper combines ideas from two recent paper to show that a richer class of algorithms which have both sequential advantage-based updates and use Mirror-learning style control of updates have the monotone improvement property in MARL. This is empirically demonstrated by showing that instances of A2C and DDPG using the sequential advantage updates outperform traditional versions.

Strength:
- the proposed algorithm may have more stable convergence properties. 
-  simplifying and generalizing existing ideas
-  empirical demonstration of the benefits

Weakness:
- The presentation makes the paper hard to read
- Novelty: ideas might be known in the literature long time ago
justification_for_why_not_higher_score: The reviewers identifies a number of issues while the authors did not adequately address them. The biggest concern is the presentation of the paper. The current version does not seem to be in a good shape to be published in ICLR.
Decision: Reject