Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 3: Clear rejection
review_content: summary: Base on an observation that it is often difficult to determine the contribution a particular agent’s behavior has on the team when we have not well assessed other agents’ actions, this paper proposes a sequential credit assignment method (SeCA) which deduces each agent's contribution to the team's success one by one according to a particular order. Futher, according to this order, SeCA simplifies the computation of the advantage function of COMA (specifically, the expectation over other agents' actions) by fixing the preceding agents' actions. Finally, the sequence order is dynamically adjusted according to agents' contributions to the team deduced by integrated gradients.
main_review: 
$\textbf{Pros:}$
(1) The motivation is very clear. The paper clearly argues that a successful framework for sequential credit assignment has been a missing element of prior work on multi-agent RL. I encourage the authors to continue pursuing this study as it should make a valuable contribution.

(2) The paper is well organized and clearly written. 


$\textbf{Cons:}$

$\textbf{(1)} \text{ [Fatal error]}$ The implementation of SeCA has fatal errors. Specifically, as illustrated in Figure 3, when computing the expectation over agents' policies of the advantage function, i.e., $A^{a_{i}}=f_{\phi}\left(s ; u^{a_{1}}, u^{a_{2}}, \ldots, u^{a_{i}}, {\color{red}\pi^{a_{i+1}}, \ldots, \pi^{a_{n}}}\right)-f_{\phi}\left(s ; u^{a_{1}}, u^{a_{2}}, \ldots, u^{a_{i-1}}, {\color{red}\pi^{a_{i}}, \ldots, \pi^{a_{n}}}\right)$ (marked in red), the concrete implementation is absolutely wrong. 

After checking the code provided in the Appendix, I found the author tries to compute the expectation over agents' policies by simply taking the probabilities of selecting all valid actions as input. Directly takeing the probabilities of selecting all valid actions (called policy vectors in the paper) as the input of the Critic neural network doesn't mean you're calculating the expected value!

This incorrect implementation will lead to wrong conclusion which will seriously affect the later studies. 

I could understand that the author's purpose is to improve the efficiency of the expectation calculation. Correctness, however, must come first.

$\textbf{(2)}$ Based on the analysis in (1), the experimental evaluation results are not convincing.

$\textbf{(3)}$ [About the experimental results in SMAC] The experimental evaluation in SMAC is not significant. Most recently, the paper RIIT[1] shows that QMIX could consistantly achieve SOTA performance among all SMAC maps with some code level modification only, e.g., changing optimizer, incorporating TD($\lambda$) and enlarging exploration. So, I recommend the authors to re-implement SeCA based on pymarl-v2 (I call the optimized version of pymarl by Jian Hu in paper RIIT[1] as pymarl-v2) and show how it performs.

Overall, I vote for a rejection for current version of this paper. I may modify my rating if my concerns mentioned above are addressed.


$\textbf{Reference:}$
  * [1] Hu J, Jiang S, Harding S A, et al. RIIT: Rethinking the Importance of Implementation Tricks in Multi-Agent Reinforcement Learning[J]. arXiv preprint arXiv:2102.03479, 2021.
  * [2] Christianos F, Schäfer L, Albrecht S V. Shared experience actor-critic for multi-agent reinforcement learning[J]. arXiv preprint arXiv:2006.07169, 2020.
limitations_and_societal_impact: Please see the main review above.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper focuses on the problem of multi-agent credit assignment for cooperative multi-agent reinforcement learning. The problem is framed in a leader-follower manner, so it sees the agent actions in a sequential manner. The sequence is updated dynamically using integrated gradients as a measure of agent's contribution to state transition. The paper claims that this allows them to achieve state-of-the-art results on many star-craft (SMAC) benchmark tasks. 

main_review: **Strengths**

The prior of a specific ordering in the form of leader-follower definitely makes sense as a way to simplify the problem of credit assignment. Using integrated gradients to figure out the ordering dynamically is an even nicer trick. One important detail about the results that is not clarified in the paper itself is that these state of the art results are at the cost of more than an order of magnitude more samples than existing works. But it's a good exploration of how much data might be required for a lot of these methods to converge. The paper is also very clearly written (although gets a little repetitive with Boss-Staff analogies) and exploring alternative ideas for credit assignment in multi-agent reinforcement learning is quite pertinent to making these more practical.

**Weaknesses**

As [1,2] shows that these many samples are not necessary to achieve the performance that is being achieved. For example, [1] achieves 80% win rate on "3s vs 5z" with only 2million samples, while this paper seems to require 20 times more samples to reach 40% win rate. But improved credit assignment should definitely show up as lower sample complexity, so I am worried if the differences between the algorithms are not all just because of sub-optimal hyperparameters and difference in credit assignment is immaterial (I understand that there might be version differences in SMAC, but the other works [1,2] seem recent enough that it's unlikely that it's just a matter of version difference. I am not sure if following refs[5,39] leads to the best comparisons against other algorithms). Other figures only do ablation studies or comparison against COMA. In my own experience with these algorithms, COMA tends to underperform compared to just using a centralized baseline on most tasks. Moreover the proposed approach inherits the problem from COMA of not being able to scale to teams with larger number of agents.

[1] Witt et al. "Is Independent Learning All You Need in the StarCraft Multi-Agent Challenge?" https://arxiv.org/abs/2011.09533

[2] Hu et al. "Rethinking the Implementation Tricks and Monotonicity Constraint in Cooperative Multi-Agent Reinforcement Learning" https://arxiv.org/abs/2102.03479

Edit: Thanks to the authors for their comments. I'm still not convinced of the comparisons with off-policy methods but I'm not changing my positive impression of the paper.
limitations_and_societal_impact: The paper doesn't really discuss its own limitations explicitly. Adding a section would be quite helpful. There might be [more stochastic] scenarios that the sequential ordering may not make sense and might require leveraging ideas like coordination graphs [A,B,C] instead.

[A] W Böhmer et al. "Deep Coordination Graphs" https://arxiv.org/abs/1910.00091
[B] S Li et al. "Deep Implicit Coordination Graphs for Multi-agent Reinforcement Learning" https://arxiv.org/abs/2006.11438
[C] N Naderializadeh et al. "Graph Convolutional Value Decomposition in Multi-Agent Reinforcement Learning" https://arxiv.org/abs/2010.04740
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This work proposes a novel approach for addressing the challenge of credit assignment in the context of centralised training with decentralised execution (CTDE): sequential credit assignment (SeCA). The method proposes to calculate the counterfactual advantage for each agent in a sequential manner, as well as an approach based on integrated gradients to dynamically determine the order for evaluating the agents (i.e., in descending order of the agents' contributions to the state transition).
main_review: Originality: 
The work addresses an important problem in MARL, namely credit assignment. The work extends the idea of calculating counterfactual advantage values and also incorporates the integrated gradients method for a novel purpose.

Quality:
I do not agree with the presentation and some of the statements made in Section 3.2. At lines 137-138 the work introduces a random variable to model the event that the credit assignment study is precise. You then proceed to unfold the joint probability distribution according to the product rule, on the 3 agents example, which is fine. But in lines 153-155 it is stated that: "The sequential MARL framework reduces the complexity of the model with six dotted arrows that indicate correlations between agents’ evaluations in Figure 1(b) by half, as those three dotted lines in Figure 1(c)". This is incorrect and misleading. First of all, these are 'dependencies' and not 'correlations'. Secondly, Figure 1(c) is not correct. The top nodes are no longer just the variables O1, O2 and O3, but rather: O1, O2|O1 and O3|O2,O1, obtained from the sequential calculation of the terms in the product rule. 

Clarity: 
The paper is nicely written and organised. I find that perhaps the recurring CEO-Staff example takes too much space for the utility it brings to the paper. It might have been more interesting to present for example a short discussion on a testing episode (from the supplementary material). This would show on a real example how exactly the idea of agent contributions translates in practice.

Lines 178-179 state 'After assessing agent a, we fix its action and evaluate agents after it based on a’s fixed action', can you clarify how or to what do you fix the action of each agent during the sequential assessment.

Significance: 
I appreciate the ablation studies and comparisons with SOTA approaches. The study of the sequence adjustment frequency was interesting. I was wondering how the 10 and 20 values were selected for the stage adjustment? The experimental results show that SeCA performs well, on par or even better than the other considered approaches. 

----Post-rebuttal----
I thank the authors for the diligent clarifications. I have raised my score.
limitations_and_societal_impact: No potential negative societal impact.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The authors are studying cooperative marl with global reward,  and in particular the credit assignment problem. This is considering the sequential approach where one assign credit one agent at a time by marginalizing out its action akin to difference rewards. When there is a natural sequence of importance of the agents and whose contribution depends on whose actions. They use CEO and staff as an illustrative example of when it makes sense.

main_review: The key novelty in this paper is that they adjusts the sequence based on a particular way of measuring the contribution of each agent , integrated gradients, that has previously been introduced for this purposes (decomposing global Q into ind agents) in QPD under the extra assumption of a local reward being linearly related to the contribution to the total. Here such local rewards and assumptions about them are not relied on and instead this value is used to rank the agents for sequential credit assignment.

The empirical evaluation on SCII micromanagement tasks looks promising.

The paper is combing a few existing techniques in a particular manner that feels slightly ad-hoc, though not without some intuition.

It would be interesting to know if the sequential credit assignment also reinforces the chosen ranking of contributions in some way and make the learning, in any way, such that the lower rank learns to "consider" the higher ranked more than the other way around.

limitations_and_societal_impact: It is not clear to me if the sequential approach can be bad for all orderings in some situations, but I would guess that such exists.
review_title: null

Meta-review: The reviewers and AC discussed the paper. There was agreement that the approach is promising for dealing with sequential credit assignment in MARL. Nevertheless, there are concerns about the fairness of the experimental results and some of the technical details (e.g., the advantage function). It is great that the authors will do (or have already done) some additional experiments, but those are not currently visible. These results are necessary to understand the performance of the approach in the context of other state-of-the-art methods. Similarly, while the authors provide additional details about the approximation of the advantage function, this approach should be better motivated and clarified in the paper. In order to properly evaluate the paper, it needs significant updating and re-review. 
Decision: Reject