Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 4: Ok but not good enough - rejection
review_content: summary: The paper formally analyzes the variance of multi-agent policy gradients and propose a baseline (and a practical implementation) to reduce the variance. The problem considered is interesting, but the reviewer is concerned about some assumptions used by the authors and is confused about the experimental results. 
main_review: ### Quality
(1) Assumption: the authors assume that (1) critics (both centralized and decentralized versions) are accurate and can give exact value estimations, and (2) agents can observe the global state $s$. Based on the second assumption, the joint policy is decomposed as a multiplication of local policies. These two assumptions make the theoretical results provided in this paper less surprising. 

For example, lemma 1-3 can be obtained by using preliminary math given the second assumption. When Q is accurate, the proof of Theorem 1 does not give much insight, which can be finished by introducing a notation for the upper bound for the gradients and advantages. 

(2) In Fig. 2, the variance of the proposed method is very large, especially for complex tasks like SMAC and 2-Agent Walker. It is quite strange because the authors claim that they use an *optimal* baseline for MAPG methods. In contrast, state-of-the-art MAPG methods, like stochastic DOP [Wang et al., ICLR 2021], have much smaller variance. 

Moreover, the reviewer is confused about the experimental results. MAPPO performs well on 3s_vs_5z, but the authors report a win rate of 0. And, the confidence interval (or variance or std, the authors do not explain what's this in the main text) in Fig. 2 is quite strange. Why does QMIX not have shaded areas? And, for MAPPO w/o OB, why the intervals are very small when the mean value oscillates significantly. This does not make sense unless only two or three seeds are used when drawing the plots. 

### Clarity
(1) Line 43. Not all CTDE PG methods take actions as input to the critic, like COMA. And, the output is the expected return, not the reward.
(2) Line 142, although MADDPG learns deterministic policies, it is a multi-agent policy gradient method. The statement of "These methods are not of our interest, as they learn either a deterministic policy or a value function, thus not in the scope of MAPG methods." is not accurate.
limitations_and_societal_impact: The authors didn't discuss the limitations and potential impact of the proposed method.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper carefully analyzes the variance of multi-agent policy gradients and derives the multi-agent baseline estimation with the smallest possible variance, which also indeed leads to a lower variance of policy gradients of the state-of-the-art multi-agent PPO algorithm. 
main_review: This paper is clearly written with very intuitive explanations and thorough step-by-step derivations on the multi-agent variance. This is, to the best of my knowledge, the first paper that rigorously studies the variance of multi-agent policy gradient methods (although some empirical studies have been indeed investigated). The theoretical analysis starts from the simplest formulation and carefully goes through all the details, which makes the paper particularly easy to follow.

I enjoy reading this paper a lot and this paper indeed tackles an important problem in MARL. I'm happy to see it get accepted. 

limitations_and_societal_impact: Here are a few minor comments.

(1) I couldn't see the confidence interval in Fig2 (e)-(h). I would suggest the authors complete the results in the final version.

(2) I do like the variance analysis. However, these insights only hold under the ideal unbiased case while in practice, the biggest benefit of PPO is due to GAE. The paper could be even stronger if the authors could investigate how to incorporate GAE into the framework.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper theoretically studies the variance of multi-agent policy gradients. 

It shows that the extra variance that CTDE MAPG methods have compared to DT methods scales linearly on the number of agents, and quadratically on the local advantage of each agent. 

The paper further proposes the optimal baseline technique to reduce the variance of the MAPG estimator. While the analytic form of the optimal baseline is computational challenging to compute, the assumption that the policies are parameterized by neural networks with softmax layer is used to find a surrogate minimisation objective that is more tractable to compute/approximate. 

Experiments are conducted to confirm the effectiveness of the optimal baseline technique. 
main_review: Originality: The results presented in this paper are novel as far as I know.

Quality: The theorems and proofs look correct.

Clarity: The submission was very clearly written and well orgnaized. 

Significance: I think this work takes an important step towards understanding policy gradient methods for MARL. The theorem 1 and 2 are very insightful. 


limitations_and_societal_impact: My main concern is that the experimental results are a bit weak in terms of supporting the effectiveness of the optimal baseline technique. It seems to be clear that using the OB can further reduce variance of policy gradients. However, that doesn't seem to be directly translated into an increase of performance, as shown by experiments in SMAC except 2(e).
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper analyzes the variance of gradient estimates in policy-gradient-based multi-agent RL, specifically for standard multi-agent policy gradient (including both centralized and decentralized training) and for the COMA gradient. The paper then derives an optimal baseline (OB) as well as a tractable surrogate for variance reduction. The non-optimality of the variance of standard MAPG and COMA is shown. Numerically, lower variance of the OB is shown in an analytical example, and performance (in terms of reward and win rate) improvement is shown when the OB is implemented on top of MAPPO and COMA in the discrete-action StarCraft micromanagement scenarios and continuous-action multi-agent MuJoCo.
main_review: This is a timely paper, given the increasing attention on multi-agent learning and the existence of a number of empirical methods-centric work that builds on policy-gradient methods for MARL. The style of this work should remind a reader of the single-agent counterpart---Variance Reduction for Policy Gradient with Action-Dependent Factorized Baselines, Wu et al, ICLR 2018 (not cited)---but the analysis and multi-agent context are different enough from the single-agent case that this paper has sufficient originality.

Quality meets the bar (but see the detailed questions below). Overall, this work is a good and rare example of a paper in multi-agent RL that derives an algorithmic improvement from theoretical analysis and also provides empirical validation.

One point that the authors should clarify: could the left-hand side of the inequaltiy in Theorem 1 be negative, so that the variance of the decentralized estimator is higher than the centralized one? If not, the paper can be improved if the authors include a conceptual explanation for the reason. The centralized one uses the joint $Q(s,\mathbf{a})$ that receives the joint action as input, while the decentralized one uses $Q^i(s,a^i)$ that itself requires an expectation over the other agents' actions $a^{-i}$. Is there any intuition for one to have higher variance than the other?

The clarity of the paper's notation is appreciated. Providing reductions to known cases also helps a reader to check correctness.

It's not clear what the paper means by line 162: "a MARL problem can be considered as a sum of $n$ RL problems". At best, it's an unnecessary description of Lemma 1. At worst, it could confuse someone into thinking that decentralized training is sufficient for cooperation in MARL, which is obviously false.

It appears that the surrogate optimal baseline in equation (9) is not the one the paper actually uses in practice. Instead, the paper uses the form given in lines 249-250, which is consistent with the description in lines 274-275 that says "firstly, it evaluates the probability measure $x^i_{\psi^i_{\theta}}$, and then computes the expectation ...". It's not very clear how the expression in lines 249-250 is equivalent to equation (9). 

In lines 252-253, it's not clear where the "importance weight" arises; perhaps the authors do not mean it in the sense of importance sampling.

The claim in line 314 that OB improves MAPPO on all four tasks is incorrect: there is no significant difference between MAPPO with OB and without OB in 3-agent Hopper, Figure 2a.


Minor points:
1. There are numerous typos that the authors should fix: line 37 "single-agnet", line 236 "this this", line 245 "Hereafater", Table 1 caption "a numerical toy exmaple tha shows", line 272 "This gives as an estimator", line 279 "continuosu"

---------------------------------
Post rebuttal: The authors have responded in detail and addressed my questions, and I am keeping the score for this good paper.
limitations_and_societal_impact: The paper does mention that deterministic methods and value-function based methods are not in scope.
review_title: null

Meta-review: The paper studies how to reduce the variance of stochastic gradient estimates in policy gradient approaches to Multi-agent Reinforcement Learning (MARL). Focusing on the popular Centralized Training Decentralized Execution setting, the authors provide a theoretical analysis that quantifies excess variance and connects it to the number of agents and agents' local advantages. They build on these insights by empirically showing how these insights affect COMA, and by deriving a new optimal baseline (OB) which is empirically validated in StarCraft and multi-agent MUJOCO environments.

Reviewers were positive about the importance of the problem addressed in this work. They largely agreed that the question of policy gradient variance has not been widely studied in the MARL community, but has important implications and potential for impact. The paper was considered clear and well written.

At the same time, several concerns were raised. In particular, the assumptions of the analysis are idealised, and findings do not always translate into corresponding empirical gains. 

During the rebuttal and discussion phase, reviewers were generally satisfied with the clarifications provided by the authors and recommend acceptance. Unfortunately, the most negative reviewer did not engage beyond the initial review. Therefore, the AC examined the concerns raised in the initial review and judged these as sufficiently addressed by the authors.

The paper is assessed as meeting the bar for acceptance, based on the important theoretical insights and high potential for impact on the MARL community. The authors are strongly encouraged to take on board all reviewer comments to further improve clarity and potential for impact in the camera ready version.
Decision: Accept (Poster)