Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper investigates the problem of learning non-linear coordination graphs in multi-agent reinforcement learning. It proposes the first non-linear coordination graph by extending CG value decomposition beyond the linear case. It proposes the weighted max-sum algorithm to solve the greedy-action selection problem in the non-linear coordination graph.
strengths_and_weaknesses: Strengths: 

This paper investigates a very important problem in coordination graphs. Previous methods focus on the linear case, which has limited representation capacity on Q values. This paper proposes a novel method by using a mixing network, the active function is LeakyReLU.


Weaknesses: 

1. Using a mixing network to represent the coordination graph is not new. Previous work [1] uses GNN, which can seem like a mixing network, and ReLU or LeakyReLU can also be used in GNN.

2. The experiments are not strong, CASEC [2] is not compared.

3. More scenarios should be tested. As this paper considers the representation capacity issue, more experiments in complex scenarios, for example, the predator-prey task and SMAC in [3], should be conducted to show the merit of the method.

4. Some curves are not fully shown. For example, in Fig 3, the curves of NL-CG are not fully shown.

5. This paper is hard for me to follow. The writing can be improved.

[1] Deep Implicit Coordination Graphs for Multi-agent Reinforcement Learning

[2] CONTEXT-AWARE SPARSE COORDINATION GRAPHS

[3] Deep Coordination Graphs


questions: I have the following questions:

1. In lines 112-113, why is a DNN with piece-wise linear (PWL) activation functions (e.g. ReLU, LeakyReLU, PReLU) is equivalent to a PWL function? Did it motivate you to investigate the problem of the non-linear coordination graph?

2. In lines 141-142, when the mixing network is non-linear, maximizing Q_tot is NP-hard. Can you elaborate more? As far as I know, deep networks have capacities to learn good models.

3. Can you highlight your contributions in Alg. 1, 2 and 3? 

limitations: Please see the above comments.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper introduces a convex mixing network, that is learned using a QMIX-style hyper-network, for coordination graphs. The authors prove that a maximum over the piecewise-linear parts of the mixing network corresponds to the global maximum and introduce an iterative optimization method for larger mixing networks that converges to a local maximum piecewise-linear solution. The resulting algorithms are compared with DCG on some MACO benchmark, and show impressive improvements on some. The authors also compared the enumeration over all parts with their iterative method in ablation studies.
strengths_and_weaknesses: The reviewer liked the paper a lot, especially the theoretical part. Although the authors should better distinguish between the domain of a function and the inputs that "correspond" to a function (see detailed comments), the reviewer has checked the proofs thoroughly and believes they are correct. The authors should mention that their restrictions on the mixing network is almost identical to input-convex neural nets (ICNN, Amos et al., 2016). ICNN are a bit more general, but the theoretical analysis should still hold. In particular Lemma 1 looks as if it could have useful applications in other fields using ICNN.

Section 4 is not particularly illustrative, but the experimental experimental validation looks very well done and the results are very good on Aloha and Sensor. The biggest open question is scalability: a mixing network of size 10 might still be considered small. The authors could provide a better runtime comparison of their algorithm in comparison to DCG (see questions), and with number of network size and number of iterations of the approximate algorithm. 

**Detailed comments**

- eq.4+5: as the mixing network $f_n$ depends on $s$, so must $Q_{tot}$
- l.132: "extended to other activation functions like ReLU" -- ReLU is already a special case of LeakyReLU with $\alpha=0$
- l.150: the outputs $o_i$ can easily be confused with the observations $o_i$
- l.162ff: you should differentiate between the domain of affine function $\rho_k$, which is the entire input space (otherwise one could not compute the output), and the inputs $q$ that "correspond" to $\rho_k$, that is, where the forward pass produces $c^k$. The two words are currently nowhere properly defined and used synonymous (e.g. Lemma 1 or l.172). Maybe define the set $q \in Q_k$ in which the forward pass yields $c^k$ to be precise.
- Lemma 1 is really interesting, but should be expressed more precisely: for which class of functions does it hold, and how the $\rho$ functions are defined. This will allow easier transfer to other fields. You can also remove the $s\neq r$ restriction, as for $s=r$ the inequality still holds.
- l. 169: it took the reviewer some time to believe the claim $h^r_{ij} \geq h^s_{ij}$. It would help to emphasize that the two slope configurations are identical, except for entry ${ij}$, and that the output $o_{ij}$ is therefore the same in both functions. A sentence about how the inequality holds might also help.
- l.184: the word "infeasible" is unclear here; you need to establish the terminology as suggested above
- l.200: as you mentioned later, using the condition $c_{real} = c_p$ can lead to loops. Why don't you just use $\rho_{real}(q(a_{real})) = \rho_p(q(a_p))$?
- l.217: the "reward is invariant to the identity" only for the second decision
- l.221ff: the example is very unclear. How do the 5 equations look like? Why do you set $q_i(s_{2B}, A)=0$ (doesn't this already used up the equation for 0 action B's)? All together the reviewer did not see a large benefit of Section 4. 
- l.252: why 4 slopes? Shouldn't it be 3^2=8 slope configurations?
- l.252: it states that "$n_{max}=4$", but the Figure states $n_{max}=8$
- l.272f: it is unclear how you compare NL-CG with DCG in Figure 5. How does DCG get different entries on the x-axis? 
 
**References**

Amos et al., 2016: Input Convex Neural Networks; https://arxiv.org/abs/1609.07152
questions: 1) Is the wall-clock time of NL-CG simply DCG_time times num_iterations, or does the initialization with the optimal actions of previous iterations speed up the message passing?

2) Did you follow all the design decisions of the DCG implementation, or did you leave out some things (e.g. the state-dependend bias)?

3) Do you have an explanation why NL-CG performed so much better than DCG in Aloah and Sensor (but not in Gather)?

limitations: - A wallclock-time comparison to DCG would have been nice.
- It is unclear how well the algorithm scales to realistic applicatons with large action spaces, like the StarCraft2 experiments in the DCG paper.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper addressed the problem of cooperative multi-agent reinforcement learning by proposing an improvement over value decomposition method. They extend the concept of coordination graph to non-linear combination of value functions. 

The core of the method relies on coordination graph. In coordination graphs, an edge is drawn between two interacting agent and a joint value function is learned through reinforcement learning. Given such graph, a globally optimal joint action can be computed to maximize a combination of the edge value functions. Traditionally, those value functions are summed and we can use algorithms such as max-plus to find the joint action. The author extend this process to non-linear combinations with deep network using LeakyReLU activations.  

They extend the max-plus algorithm to this class of graphs by decomposing the problem as piecewise linear combinations. The first proposed algorithm has an exponential time complexity in the width of the mixing network due to enumerating all possible slope configuration but the authors propose an approximation which converge to a local optimum and rely on an annealing strategy to try to escape it. 

The experiments compare the performance of the whole algorithm on the MACO benchmark against two baselines: QMIX and DCG. 
A second set of experiments compare the optimality of the action selection only between the two propose algorithm,  DCG and a random baseline.

strengths_and_weaknesses: The problem of cooperative multi-agent RL has many societal applications and there is still a lot of progress to be done in being able to solve it efficiently. This paper contributes towards this goal by extending state of the art techniques based on value decomposition methods. 

Extending CGs to non-linear combination does intuitively increase the representation capability of the global value function, similarly to QMIX vs VDN, I believe the idea is sound. The author demonstrates this through the use of an example in section 4 and further validate it empirically. 

Overall the paper is well written and quite easy to follow. The algorithms are sound and clearly explained.

When extending the max-plus algorithm to piecewise linear combination, they clearly explain the results and the derivation seems correct. 

The weighted max-sum could be moved to appendix. 

The plots from figure 5 and 6 are quite hard to follow, and the axes are not clear at all. Even if the author try to explain their meaning in the caption, it would be wise to choose another type of representation that is more intuitive for the reader. Furthermore I believe there are some unclarity on the correctness of this experiment regarding the choice of Qtot (see questions). 

questions: 1. Is there an application that would lead to similar dynamics as the problem illustrated in section 4? It would be useful to provide an example to further motivate why we would need the extra complexity. 
2. The graph structure is barely discussed, in the original max-plus there are issues with graphs presenting cycles, how would your algorithm be affected? 
3. Why are the NL-CG method starting at higher position than the other methods in figure 2? 
4. The performance of QMIX is surprisingly low, why is that? It would have been useful to compare in another MARL where QMIX is not so bad e.g. starcraft. 
5. In figure 5, how can DCG be compared with the method since they should use different Qtot (linear vs non linear)? 

limitations: The authors do not explicitly mention any limitations of their method. I believe it would be valuable to add a paragraph. An obvious limitation to this family of method is that they require the graph structure to be known. Discussing different type of graph structure or sparsity would have been useful.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper proposes to extend the coordination graph framework to allow for non-linear mixing of agent payoffs/pairwise utilities, in a way similar to how the QMIX algorithm extends VDN by mean of mixing network. The problem of being able to solve the subsequent decentralized constraint optimization required to compute the optimal joint action is tackled by resorting to piece-wise neural network analysis, and nothing that it suffices to solve a linear DCOP for each possible slope configuration in order to find such optimal action. Moreover, an iterative version of this algorithm is proposed, possibly trading off optimality of the selected joint action with a reduced number of DCOPs to solve.
strengths_and_weaknesses: **Originality:** Up to the best of reviewer's knowledge, the idea of using a non-linear function to combine components in a coordination graph is novel, and so it is the algorithm proposed to identify the optimal joint action in such a non-linear representation. 

**Quality:** The paper is in general technically sound, and the methodological claims are well supported by experimental results. The set of experiments and analysis proposed is good, and is really capable of addressing most of the concerns a reader may come up with. I only have some remarks for the authors, mainly concerning some more in-depth explanation of experimental details or to provide support of some claims. For example, it is never explained what CG topologies are used for the proposed experiments (also valid for the DCG baseline), while I think this is a relevant detail that should be reported. Or, where did you get the $Q_{tot}$ used in Figure 5? This is never explicitly explained, but is an important information to understand what the figure is representing.

Also, I have some small concerns about the performance of the iterative algorithm. For example, when using NL-CG with an embedding of 4 units in Figure 2, is there any evidence that the iterative algorithm is performing well because it is indeed a good approximation and not because it is simply solving the constraint at every possible slope configuration? This should be assessed before claiming that is is reducing the number of solved slope configurations as you are doing.

**Clarity:** The work is in general clearly written, and given the reader all of the required information to correctly understand both the proposed methodology and the experimental results, with just some minor exceptions (see **Questions** below).

Perhaps the explanation of the adaptation of Max-Sum to the non-linear DCOP setting may be a bit improved: what do you mean exactly by a joint action $\mathbf{a}$ falling outside a given piece $\rho_k$ on line 164? Perhaps you mean that the $q_i,q_{ij}$s generated by the joint action $\mathbf{a}_k$ (I think these are $\mathbf{q}_k$ in your notation) generates a different slope configuration $\mathbf{c}^{m\=k}$?

**Significance:** The presented idea is indeed significant, and advances our understanding of the field. With the great interest that both value-decomposition methods (with a and growing impact of higher-order decompositions)  and non-linear mixing architectures are gaining, this is a valuable contribution and could possibly allow for even better application of mixing techniques to coordination graph learning (that has proved indeed useful in learning better representations [Castellini et al., 2021](https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=&ved=2ahUKEwj92tifi634AhU6RPEDHUIuBXUQFnoECBoQAQ&url=https%3A%2F%2Fresearch.tudelft.nl%2Ffiles%2F94310595%2FCastellini2021_Article_AnalysingFactorizationsOfActio.pdf&usg=AOvVaw0pSTZXIivp-1y3apJsQhMH).
questions: - [Castellini et al., 2021](https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=&ved=2ahUKEwj92tifi634AhU6RPEDHUIuBXUQFnoECBoQAQ&url=https%3A%2F%2Fresearch.tudelft.nl%2Ffiles%2F94310595%2FCastellini2021_Article_AnalysingFactorizationsOfActio.pdf&usg=AOvVaw0pSTZXIivp-1y3apJsQhMH), is such an extremely relevant citation here, showing the benefits of higher-order factorizations on tackling an exponential number of joint actions over both centralized controllers and independent learners.
- Your explanation of relative overgeneralization is a bit not-on-point (indeed, each agents is not supposed to know the actions of the others). Relative overgeneralization occurs when agents are pushed towards favouring a suboptimal behaviour because this gives, on average, a higher reward than the optimal coordinated behaviour. This happens because the concurrent learning process of the other agents shadows the optimal strategy with its exploration (equilibrium shadowing), rendering it less attractive than a suboptimal one.
- It may not be immediately clear how you decompose LeakyReLU$(\mathbf{o}_i)$ as $\mathbf{c}_i\circ \mathbf{o}_i$, where $c_i$ is simply the multiplication coefficient of the LeakyReLU (so either $\alpha$ or $1$). Therefore a reader may be a bit surprired of the definition of the slope configuration $\mathbf{c}\in\{\alpha,1\}^m$. Please clarify what $\mathbf{c}_i$ is and where do you get it.
- What do you mean exactly by a joint action $\mathbf{a}$ falling outside a given piece $\rho_k$ on line 164? Perhaps you mean that the $q_i,q_{ij}$s generated by the joint action $\mathbf{a}_k$ (I think these are $\mathbf{q}_k$ in your notation) generates a different slope configuration $\mathbf{c}^{m\not=k}$? This should be better clarified.
- What are the CG topologies for the different experiments for both your method and DCG? Why have you come up with such topologies?
- In Figure 2, when using NL-CG with an embedding of 4 units, is there any evidence that the iterative algorithm is performing well because it is indeed a good approximation and not because it is simply solving the constraint at every possible slope configuration (thus reducing to the enumeration algorithm in practice)? This should be shown somewhere, possibly in an Appendix if the space constraints are too limiting (although I would prefer to see such a figure rather than the very lengthy Algorithms 1, 2 and 3, that are not really adding much to the method explanation, that is already quite clear).
- In Figure 4, how do you guarantee that the iterative method is only solving the constrained problem for 16 slope configurations and not more?
- In Figure 5, what $Q_{tot}$ are you using as a reference? Are you using the one from NL-CG with enumeration? Or perhaps you are computing some sort of ground-truth Q-function? That should be specified for a reader to clearly understand and appreciate the results.
limitations: The possible limitations of the proposed method are actually never discussed in depth. The authors should make an effort and address this, trying to identify possible situations in which the proposed method could not perform as expected, and the reasons for this being the case.
review_title: null

Meta-review: metareview: This paper is a very clear accept. The reviews had only minor quibbles, which I trust the authors will address in their final version.
confidence: Certain
Decision: Accept