Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 4: Ok but not good enough - rejection
review_content: summary: The authors present a theoretical framework based on the fitted Q-iteration (FQI) method as a common tool in analyzing two popular value factorization approaches in cooperative deep multi-agent Q-learning. Linear value factorization (LVF) and Individual-Global-Max (IGM) value factorization methods are studied from the FQI perspective, and their convergence properties are explained in theoretical manner. Some didactic experiments support their findings, and numerous empirical performance figures are reported to be consistent with those in previous works as well as with the theoretical proofs delivered in the appendix.
main_review: Originality:
To the best of my knowledge, this work is the first in attempting to find and explain the common denominator among value factorization methods in SoTA MARL works based on the FQI framework. However, the authors do not make a strong case as to why FQI is the best candidate as the "frame" in the framework. Had the paper explained how FQI topped the authors' list of viable frame candidates, it would have been very helpful in understanding the motivation behind the framework development. I would imagine that one advantage of reverting to a non-deep classical method lies in the ease of deriving a closed-form solution, but I would rather read about it in the paper instead of having to rely on my guesswork.

One strong competitor would be deep convolutional graphs (DCG), which I really think should appear much earlier in the paper than in the conclusion. Despite DCG authors never calling the work a framework, by the standards of FMA-FQI, DCG would also qualify as one, but retaining the "deep" aspect of deep MARL as well as being capable of interpolating through all VDN, QMIX, and QTRAN/QPLEX and their corresponding classes of realizable value functions: additive, monotonic, and IGM.

Quality:
The paper is generally easy to follow, but some of the important proofs feel a bit too "offloaded" to the appendix, which forces the reader to repeat "believing and moving on" until the paper's end is reached. A sketch of proofs for Theorem 1 and Proposition 1 would have made the submission much more convincing.

A minor error:
Assumption 1: decentrailized --> decentralized

Clarity:
Sections 5.2 and 5.3 remain a blur even after going through the appendix. Exactly what are meant by "offline setting" and "\epsilon"?

Are the terms "offline" and "off-policy" used interchangeably in this paper? If not, Section 5.3.2 must be renamed to "online data collection..." because the "on-policy"-ness of the data collection has nothing to do with the local convergence guarantees. (e.g., an on-policy learner could still be offline when \epsilon=1.0).

If "offline" and "off-policy" are interchangeably used, (and so are the counterparts "online" and "on-policy"), then the following questions arise.
Figure 1c must be aptly renamed, as the \epsilon=1.0 case would clearly be "off-policy".
Does the \epsilon refer to the exploratory \epsilon? If so, a completely random exploration policy does not mean off-policy.
Does the \epsilon refer to the \epsilon-greedy policy of choosing the a' in s' when updating the Q-function? If so, \epsilon=1.0 would mean completely random action chosen in the next state: how does this translate to off-policy learning? In fact, for the learning process to qualify as off-policy, shouldn't the next action be chosen greedily? (\epsilon=0).

It's very difficult to say that Section 5.2 and 5.3 are convincing when the convergence guarantees seem to have little relevance to whether the learning is on- or off-policy. Rather, they only have to do with the randomness of how the next action (a') is chosen, which certainly isn't completely random in the off-policy setting, or even in the on-policy setting, unless its current policy is a completely random one as well.

On a separate note, it remains a question why the authors chose linear and IGM value factorization methods and left out monotonic value functions. It feels like quite a stretch to claim to have proposed a "unified framework" without even hinting at the generalizability/applicability of the said framework to the "middle" case of monotonic classes of functions, which would lie somewhere between linear and IGM in terms of subspace relations.

Some minor issues:
In Figure 1b, the QTRAN graph seems to be missing; so does \epsilon=0.1 in Figure 1c.

Significance:
The submission is partially successful in presenting what it set out to. However, a number of lines of research prevent the paper from really becoming a unified framework.
- Monotonic value factorization is not treated in depth. Works following QMIX outnumber others both in quantity and in citation, so it would be hard to justify leaving them out without even a hint as to how FMA-FQI can be applied to the settings of QMIX and its variants.
- Continuous action spaces are not studied. COMIX and COVDN (Schroeder de Witt et al., 2020) are examples of value-based methods modified to work with continuous action spaces. Nowhere in the FMA-FQI paper do the authors assume discrete actions, so the continuous-action counterparts must be studied accordingly if the proposed framework were to be general.
- Actor-critic settings are not studied. FACMAC (Schroeder de Witt et al., 2020) is one example of an actor-critic model incorporating value factorization. Since the authors do not assume a purely value-based setting, actor-critic counterparts deserve some attention.

On a different note, the following statement raises a question. Section 6 "Recall that the unbounded divergence of linear value factorization is caused by the projection error induced from the limited function expressiveness of Q^{LVF}." This statement suggests that Proposition 2 relies on Proposition 1; however, the appendix shows that the proof of Proposition 1 actually relies on Proposition 2 being true (and hence the counterexample brought about by P2). In other words, the paper itself states that P2 being true is caused by P1 being true, but the appendix carries P1's proof by counterexample, which could exist only if P2 were true. The two proofs need to be refined.
limitations_and_societal_impact: If the FQI tool is found to be unfit to extend to i) monotonic value factorization methods, ii) continuous action spaces, or iii) actor-critic settings, then the authors should acknowledge the limitations accordingly.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper theoretically analyses the popular linear joint Q value factorization methods via a multi-agent fitted Q-iteration framework. The results reveal the connections between the value decomposition and counterfactual credit assignment. The authors also have discussed the impacts of on/off policy training on the value decomposition methods and conducted the experiments on SC2 micromanagement tasks to examine the theoretical results.
main_review: The main contributions of the paper are:
1. A new perspective to theoretically analyze the cooperative multi-agent Q-learning with value factorization. 
2. The study on the well-known IGM condition shows its global convergence under some assumptions.

Cons:
The authors claimed that IGM value factorization can enjoy the global convergence guarantee. However, both QTRAN and QPLEX have implemented the FQI-IGM, but they have quite different performances in many experiments. Therefore, it would be better to further clarify the connection between different factorization structures and where is the performance gap comes from.  
limitations_and_societal_impact: N/A
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper investigates Q-learning algorithms that factorise the joint-action Q-values in a cooperative MARL setting under CTDE.
Specifically, a fitted Q-iteration framework is used in order to focus on the theoretical properties associated with these approaches.
The theoretical analysis provides a better understanding of linear value factorisation: how it can be viewed as performing implicit credit assignment, situations where it can diverge, and the stabilising effect of training with on-policy data. Additionally, the paper theoretically demonstrates the benefits of being able to represent a wider class of joint-action Q-values by proving convergence in the same setting. 
main_review: I liked this paper overall, but would like to see the presentation adjusted to mention the links with existing work and the importance of some results. I am open to increasing my score based on the rebuttal (and on the other reviews) since I do think this paper makes a valuable contribution to the literature. 

Is the setting of a Dec-ROMDP really important for the analysis in this paper, or would an MMDP suffice? 
In Appendix A.2 you mention that it is used for "bypassing the barrier of partial observability in theoretical analyses".
It doesn't appear that the particular structure/dimensionality of the observation space is used in the analysis so I don't see the necessity of using the Dec-ROMDP formalism over a simpler formalism that drops the partial-observability entirely.
Furthermore, since you make additional assumptions that only the most recent observation is required to know all about the true state I don't see much of an actual difference between your setting and just assuming full observability.

This paper is entirely missing the links to the relevant work done in the Weighted QMIX paper.
The analysis done there is very similar to the FMA-FQI considered here, except it doesn't include an explicit notion of a dataset D and instead assumes all state-action pairs are updated. I appreciate that considering the dataset brings additional complexity and richness to the analysis, but it seems an oversight to completely ignore it since it is very related prior work.
Line 360 in the conclusion suggests that the theoretical properties of QMIX have not been investigated at all in this kind of framework, but they have been in the Weighted QMIX paper.
Furthermore, for a lot of the analysis the role the dataset/exploratory policy plays is very mild which brings the two analyses even closer. 
I'm not saying that there is a lack of novelty in this paper, just that there is very related work that should be also mentioned.

Could you expand on the extra importance weight (n-1)/n, and why it is more consistent/meaningful in Line 214?
In the scenario where all joint-actions lead to the same rewards, then assigning 0 is the intended behaviour of COMA (i.e. no advantage to taking any action compared to a baseline policy). I don't see why assigning 1/n to each agent is necessarily beneficial in that scenario.

For Proposition 1, could the same argument/example as in Weighted QMIX be used to show this in a much simpler manner (Section 3.1, under the paragraph "T^∗_{Qmix} is not a contraction")? Essentially that there isn't necessarily a unique minimiser of the loss.
Related to this, how do you establish which entry of the argmin to take in Eqns 3 and 6 when there are multiple?
I see that Assumption 3 buried deep in the appendix rules this out, it should be included more prominently in the main paper with a short discussion on its relevance. In particular, how strong of an assumption it is in this multi-agent setting. For example, it rules out a very simple 2 agent, 2 action matrix game in which the payoffs are the identity matrix.

In Theorem 2, the quantifier 'locally' makes the statement rather weak. Theorem 4 (formal version of Thm 2) makes this clearer: If your current policy is already sufficiently close to the optimal one, then you'll converge. 
I don't quite see the importance of this result since it feels rather vacuous. However, the pages of derivation for it suggest that it is non-trivial to prove. Some extra discussion on its purpose/importance would be welcomed. Are there analogous situations in which this type of local convergence cannot be guaranteed for instance?

For the Offline RL experiments, have you ruled out problems such as over-estimation being the cause of bad performance? In appendix G.2 when the performance of some algorithms declines over the course of training, that suggests there might be other reasons for the relatively bad performance other than the representational capacity of the methods.
Related to the experiments in Section 6.3, your theoretical results suggest that the closer to training on-policy VDN is the better/more stable it is. Are you able to empirically confirm that in the same offline RL setting, by say reporting the results of training on datasets that get increasingly on-policy?

In Appendix H, can you elaborate further on why QMIX also diverges even though it is not restricted to a linear factorisation? Is it down to the particular choice of non-linearity in the mixing network (ELU) which results in a largely linear mixing? Would using a tanh change this for example?

### Minor Points

39: Since QTRAN doesn't maintain IGM (consistency between joint and individual policies) like VDN, QMIX and QPLEX do it seems a little off to mention it like this.

339: Again I don't quite agree that QTRAN acheives Q^{IGM} like QPLEX does. Unless QTRAN's optimisation problem is appropriately solved, it has no guarantee of maintaining IGM. This is in stark contrast to QPLEX which always maintains IGM by its architecture/parametrisation of Q_{tot}. 

208: Reiterate that the Q_i do not have unique solutions even though Q_tot might do. Furthermore, are you sure there is always a unique minimiser (related to the point about Prop 1 earlier)?

In Appendix G, that increasing the capacity/parameters of the networks for QMIX can't help in some situations like this has already been established in other papers on this exact matrix game (see QTRAN, MAVEN and Weighted QMIX papers).

25: factorizable -> factorized

250: Convergence can be proved in other ways without contraction arguments (see "Increasing the Action Gap: New Operators for Reinforcement Learning").

### Typos

In the statement of Theorem 4, why besides? Do you mean according to Lemma 3?

# Post-rebuttal

Thanks for your replies and for clearing up some of my misunderstandings. I'm raising my score to 6 based on these. I'm not raising it to 7 because there are quite a few areas where the presentation/discussion needs to be improved that have been noted in the reviews. Whilst the authors have been receptive to making the changes, I would want to see the revision before advocating more strongly for acceptance. I realise this is a bit unfair since this review process doesn't allow for revisions.

I also still have some lingering issues about the offline experimental results. 
I'm still not entirely convinced that the offline experiments are a great way to try and demonstrate the benefits of being able to represent more. Since there are many other things that could be affecting the results such as severe over-estimation which doesn't necessarily stem from the restricted function class. Whilst you cannot rule all potential problems, making sure there isn't something obvious like overestimation happening would help (graph the max Q-values or the loss or something relevant to ease a cynical reader's mind).

The difference in performance between QTRAN and QPLEX also shows that there are important considerations that aren't captured by the analysis which leaves the reader with more questions. Arguably, properly investigating these is best left for future work since it would likely focus more on the deep learning side of things, but they should be discussed a bit more.
limitations_and_societal_impact: Can you comment more on the results in Figure 2, specifically the scenarios where QTRAN significantly outperforms QPLEX.
Do you have any hypotheses for why this is the case? Is it a failing on the optimisation part of QPLEX (nn architectures), or is it related to the way QPLEX always maintains IGM consistency whereas QTRAN does not? I ask because this is an opportunity to discuss the potential limitations of the theory. Although QTRAN and QPLEX can both theoretically represent the same function class, their empirical performance can differ significantly. Specifically, what aspects of their respective algorithms does your theory not capture that could be useful for future work/analysis.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper proposes the multi-agent version of fitted q learning to analyze two kinds of value decomposition. They prove that on-policy training or richer joint value function classes can improve its local or global convergence properties.
main_review: The method is interesting, and the paper is easy to follow. The authors provide the theoretical view of some existing methods, like VDN and QTRAN. There are some concerns.

1. Since QMIX is one of the most popular value decomposition methods, is it possible to analyze it by the theoretical framework? Any conclusion?
2. Since the analysis is based on FQI, is it possible to directly compare  FQI-LVF and FQI-IGM rather than deep versions of them? Then the result would be more convincing.

limitations_and_societal_impact: Yes
review_title: null

Meta-review: The reviewers and AC discussed the paper. There was agreement that the approach leads to useful insight about value function decomposition in MARL. The author response was also very helpful in clarifying several points about the paper. Still, a number of improvements need to be made. Some of these updates have already been discussed in the author response (e.g., clarifications to the theory and fitted Q-iteration, discussion of QTRAN and QPLEX), but the authors should thoroughly update the paper as suggested by the reviewers.
Decision: Accept (Poster)