Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: Summary:

The paper proposed a simple but powerful idea of assuming a linear decomposition structure of the centralized critic into individual critics. It demonstrated 2 existing problems in the baseline MAPG agents (COMA, MADDPG), namely "centralized-decentralized mismatch" problem and credit assignment issues, and offers a theoretically motivated solution with carefully conducted experiment results including ablation studies as well as comparison with sota gradient-based and value-based algorithms.

##########################################################################

Reasons for score: 
 
The paper is very well written. Its proposal is simple but theoretically motivated to solve existing problems in MAPG algorithms. The experiment results support its claims and provides additional insightful analysis. Therefore I recommend "accept". However, its theoretical justification is weakened by assuming a tabular case of pi and Q functions which is rarely the case in practice. Furthermore, in Proposition 1, the conditioning just above Eq. 11 looks quite particular and I'm not sure how general it is satisfied in practice. Last but not least, it would be nice to see comparisons with more recent value decomposition algorithms such as NDQ and QTRAN/QPLEX. Overall I gave it a score 7.
 
##########################################################################

Pros: 

1. The paper is organized in very clear fashion. It is well motivated by existing problems and provides a simple and effective solution. 
2. It conducted clever experimental analysis that made the advantages of DOP very obvious and understandable.
3. Its method of linear decomposition of the central critic into individual critics is simple yet powerful. The paper gave adequate theoretical support to this method. 
 
##########################################################################

Cons: 

1. Both the tabular assumption on functions pi and Q, and especially the conditioning of Proposition 1 weaken the theoretical guarantee that the algorithm will converge to local optima.
2. The paper did not compare with more recent value decomposition algorithms such as NDQ and QTRAN/QPLEX. It's unclear that the baselines are the SOTA results on the chosen domains.
 
##########################################################################

Questions during rebuttal period: 

 Please address the two points in "Cons" above.


review_title: Review of DOP

final_score: rating: 9: Top 15% of accepted papers, strong accept
review_content: This works motivates the use of a factorized critic for multi-agent policy gradient.   The technique is well-motivated, and the exposition anticipates and answers readers' likely concerns.   The experiment section is well-organized, supports the paper's major claims, and is empirically compelling.

The policy improvement claims in section 4.1.2 are initially unintuitive, but ultimately are intelligible as an agent-block-coordinate local optimality statement.  However this reviewer is not clear on the quality of these local optima (i.e., when do we get "trapped"?).  For example, is it possible to design a task where the local optima are all very poor?   Of course, the experiment section indicates many benchmark tasks are amenable to this decomposition; but perhaps reasoning about this would help in (re)defining multi-agent problems to encourage success, e.g., it would be interesting if adding actions that communicate information directly between agents mitigates the local optima problem.



 
review_title: Superlative work

final_score: rating: 3: Clear rejection
review_content: This paper focuses on the problem of multi-agent reinforcement learning (MARL) for CTDE scenario which is well studied in recent literature.  The work discusses shortcomings of actor-critic methods for MARL and proposes a solution using linearly factored critic. The paper is somewhat difficult to read and can be made better by deferring the details about previous methods to appendix. However my main concern is with the problem of centralized-decentralized mismatch (CDM) motivated in the paper and its proposed solution itself. 

1. How exactly is a regular critic bad? As such a critic is supposed to be "true" to the policy, the requirement of decentralization has little bearing on the variance of policy gradients. Gradient noise increases with number of agents irrespective of whether there is centralized or decentralized execution. 

2. The so called problem of CDM seems rather redundant (see 1 above), for example the authors say in page 3, 3rd para from bottom in line 3 that if the critic expectation under policy is negative, then individual policy performance is hurt. Such problem can easily be fixed using baselines, see Sutton and Barto, 2018 for example.

3. How is a linear factored critic compatible with an arbitrary joint policy? In general this not true and requires many strong assumptions, see for ex. Bhatnagar, 2009. While the authors acknowledge this, bypassing the actual complexity for modelling a joint critic with a linear one will in general render it insufficient to model inter-agent interactions. This puts into serious question, whether coordination is required in the experiment domains in the first place and if the performance improvement is just coming due to a biased but albeit easier to learn critic. 

4. There are some unsupported claims which need better explanation like "This becomes problematic because a negative feedback loop is created, in which the joint critic is affected by the suboptimality of agent i, which disturbs policy updates of other agents" How is that so? The updates in principle can affect the policies of already suboptimal agents, which might fix them?

5. "Learning the decomposed critic implicitly realizes multi-agent credit assignment, because the individual critic provides credit
information for each agent to improve its policy in the direction of increasing the global expected return" again how so? claims like this need to be well supported.

6. Expectations are usually sampled so in principle even the $O(|A|^n)$ can be estimated with fewer samples incurring some variance, it might not be necessary to bias the critic drastically for this.

7. The authors need to shed more light on when the precondition $Q_i(\tau, a_i) > Q_i(\tau, a_i') \iff \beta_{a_i, \tau}\geq \beta_{a_i', \tau}$ in Prop. 1 holds beyond tabular settings. It seems a rather strong assumption to hold for all trajectory and 
$O(|A|^n)$ inputs. Right now it seems rather grab bag to show policy improvement.

8. Why isn't comparison on SC2 done against more recent baselines like QTRAN, MAVEN, ROMA etc.?
review_title: More clarity needed as problem discussed is not well motivated

final_score: rating: 7: Good paper, accept
review_content: In the context centralized training distributed execution in cooperative multi-agent reinforcement learning (MARL), the paper proposes an architecture to learn a decomposed action value function expressed as a weighted sum of the agent's individual functions (plus an additional weight). Those weights are themselves learned and depend on the observed history. Thanks to this decomposition, gradients can be decomposed over each agent. The authors propose to use a combination of off-policy (using tree backup) and on-policy (using TD(\lambda) methods for estimating the decomposed critic. They formulate both a deterministic and stochastic decomposed policy gradients, which are analyzed theoretically to some extent and evaluated experimentally.

PROS

The paper contributes to the active effort of designing more efficient MARL algorithms. The authors introduce the idea of value decomposition, which was investigated first in the value-based methods, to the actor-critic scheme. The experimental results suggest that the proposed combination of value decomposition and off-policy critic training has a good performance.

The writing of the paper is clear. The identification of the issue of centralized-decentralized mismatch and how it is tackled by the proposed methods are useful and interesting.


CONS

The formulation of Prop. 1 is hard to understand. What is Q_i^{\phi_i}? Is it the value function wrt \pi or \pi^0? Besides, how do we ensure that the strict inequality about Q_i^{\phi_i} holds?

Some theoretical analyses (e.g., A3 or C) are only loosely related to the actual proposed method, although I agree that a direct analysis would be difficult to conduct.
review_title: Value decomposition and off-policy critic training for multi-agent RL with good experimental performance

Meta-review: The paper presents a decomposition of the value function in the context of CCDA.

Most reviewers find this paper clear and well written, although one reviewer suggests to change the paper structure.

The method presented in this paper is simple and well justified by a theoretical section. Experiments on several domains, including Starcraft 2 micro-management tasks, are supporting the claims of that section. After some reviewers pointed out that the tabular setup is not useful in practice, the authors have extended the empirical and theoretical results to a more general setup.

Some reviewers point out that some theoretical results may not be directly related to the experimental findings. In particular, reviewer 3 does not support a central claim of the paper, and find that CDM is misleading and not provably representing the core problem.
In general, reviewer 3 does not support acceptance of this paper, but I still believe this paper should be accepted based on the other reviews (clearly in favour of acceptance). I hope that the authors and reviewer 3 will be able to further discuss and reach understanding, which hopefully should lead to fruitful results.
Decision: Accept (Poster)