Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: Authors present an imaginary coordinator agent that executes graph selection as its action based on possible combinations of pairwise edges and the underlying individual and pairwise utilities. The results show some effectiveness of the presented method, SOP-CG, in simple examples.
main_review: The main strength of the paper lies in its algorithm being of polynomial-time nature, and that characteristic needs much more emphasis in both text and figures. Does SOP-CG reach peak performance faster? Is its peak performance higher? could be some guideline questions when structuring the paper contents around the polynomial-time algorithm.

Q1. I would appreciate if the authors would discuss the relevance of a WWW 2020 paper: How Much and When Do We Need Higher-order Information in Hypergraphs? A Case Study on Hyperedge Prediction by Yoon et al. I think it could also provide some useful insights as to how high of an order the hyperedges need to be, to save some function expressiveness (i.e., representational capacity) at the cost of time complexity.

Q2. How did the authors go about designing the didactic examples? How simple of a task is the "sweet spot" for SOP-CG? As task complexity is altered, when does SOP-CG begin losing its simplicity advantage? When do other models take over? Which measures would you say most greatly determine the task complexity, which in turn, compromises SOP-CG's performance?

Q3. How would you position SOP-CG in the MARL research? Since the graph selector agent is there at both training at execution times, would SOP-CG be a centralized training centralized execution work? If it is, comparison against CTDE works such as VDN and QMIX would not be fair. It is as though a "free" centralized coordinator is helping out the SOP-CG agents at execution time as well. It may be a good idea to compare against some communication-enabled MARL works.

Q4. Despite starting out strong, the paper seems to fall off rather dramatically, especially when it comes to the didactic nature of the examples, tied in with the page 6 remark that SOP-CG would perform best (given its tradeoff) in tasks where the restricted graph classes are enough to express the coordination dependencies. This remark really sounds like going back on the VDN-QMIX-QTRAN line of research, whose focus was about covering a richer class of joint action-value functions. Going back on that trend now only to pursue the polynomial-time nature of the running algorithm would in my opinion require far more diverse evaluation examples, backed by a stronger motivation highlighting real-world threats of all the other MARL algorithms taking longer than polynomial time. As is, SOP-CG does not contend amazingly against other MARL algorithms that chose the "NP-hard? Curse of dimensionality? Fine. We'll approximate, approximate, approximate." path rather than the "Polynomial time is our topmost priority; function expressiveness can wait." path. That leads me back to the question of why pursue polynomial time at the cost of losing both the function expressiveness and the peak performance in the apparent trilemma.
summary_of_the_review: My biggest concern is the "imaginary" agent freely collecting information, making decisions, and delivering those decisions to all the agents at both the training and execution times. Comparison against the chosen baselines is not fair, even when the chosen evaluation task is a simple enough one, in which SOP-CG's limited representational capacity would not appear that pronounced.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper proposes an extension of deep coordination graph, called Self-Organized Polynomial-time Coordination Graphs (SOP-CG). Instead of pre-specified graph topology used in DCG, their method allows graph topology to be state-dependent, which is achieved by a coordinator agent, and the optimization of this agent is incorporated in a modified temporal difference learning paradigm. Two pre-specified undirected acyclic graph classes are used to ensure polynomial-time graph selection and accurate greedy action selection. The result on sensor network, grid world and MPE shows that such a trade-off between the representational capacity of graph topology and the computational accuracy can improve the performance of MARL and learn meaningful graph topology.
main_review: **Strengths**
1. To determine state-dependent coordination graph is interesting.
2. Incorporating graph selection into TD learning is desirable. 

**Concerns/Questions**
1. State-dependent coordination graph needs to be determined at each time step in both training and execution,  which means SOP-CG is a centralized method. Thus, a baseline of single-agent RL is desired for comparison in experiments. 
2. It is not clear how $q_i$ and $q_{ij}$ are learned. Are they parameter-sharing for agents?
3. The operation $\arg\max$ in equation 4 takes $O(n^3)$ for $\mathcal{G}_P $. It may be too costly for both training and execution. One evidence is that each run of SOP-CG  takes up to 2.5 days in these simple experimental tasks. 
4. Since both DCG and CASEC include SMAC experiments, it would be better to also include it here to show the performance of SOP-CG in complex environments. 

In summary, it is currently hard to see the benefit of determining the coordination graph in a centralized way. Moreover, the proposed method is not verified in complex environments. 



**Minor Comments**
1. As claimed in Appendix C, a graph relabeling technique is used to solve the extra overestimation error introduced by additional max operator over graphs.  However, this paper is currently missing an ablation to validate this point.




summary_of_the_review: State-dependent coordination graph is important. However, the paper currently has several weaknesses as mentioned above. It seems clearly below the bar of ICLR.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper introduced a novel method called Self-Organized Polynomial-time Coordination Graphs (SOP-CG), aiming to handle the decentralized constraint optimization problem (DCOP). This paper is well organized and the experiments are explicitly presented. Therefore, I think the work of this paper is very interesting and the contributions are sufficient. 

main_review: The detailed comments regarding the quality of this paper are listed as follows:
1. In the Introduction section, one of the biggest concerns is that this paper cannot tell the novelty of the proposed SOP-CG compared with the methods in peer researches. Besides, the illustration of experimental results is not convincible to prove the advantages of the proposed SOP-CG in this section.
2. Somewhere in the paper, the authors' presentation is unclear and is worth being improved. For example, in the Background section, the meanings of some symbols in the model are not clear. Furthermore, the authors should give the purposes of introducing formula (2).
3. What is the intuition behind the process of investigating polynomial-time coordination graphs in the Section 4? Or, is there any intuition at all? How did you come up with that idea? Have you borrowed this idea from somewhere else? It is better to give a detailed explanation about polynomial-time coordination graphs.
4. In page 6, the authors proposed Self-Organized Polynomial-Time Coordination Graphs. Whatever techniques are used in the manuscript, there is a need to tabulate computational cost of the proposed algorithm in this paper. 
5. In the Experiments Sections, the authors claimed that the graph structures learned by SOP-CG definitely match the ground-truth demands for effective collaboration. However, it is not clear to us why the method can be used in demonstrating the ability of the proposed approach to organizing coordination relations. Therefore, the authors should provide a detailed explanation about the above issue. 

summary_of_the_review: The work presented is indeed interesting and relevant to the real scenarios. I recommend that this paper could be accepted.
review_title: null

Meta-review: Description of paper content:

The paper studies the problem of achieving coordination among a group of agents in a cooperative, multi-agent task. Coordination graphs reduce the computational complexity of this problem by reducing the joint value function to a sum of local value functions depending on only subsets of agents. In particular, the Q-function of the entire system is “expanded” up to second-order in agent interactions: Q = \sum_{i \in [n]} q_i + \sum_{(i,j) \in G} q_{ij}, where the q_i is function of the i-th agent’s history and current action, and q_{ij} is a function of two agents’ histories and current actions. As G does not include higher-order (third and above) terms, the algorithm does not have exponential dependence on the number of agents. If G includes only a subset of pairs of agents, then the computational complexity is reduced to less than quadratic. Since the coordination problem is cooperative, the authors propose a meta-agent (“coordinator”) that selects the graph G in a dynamic (state-by-state) fashion in order to maximize return. The optimization problems of the meta-agent and the sub-agents are performed by deep Q-learning.

Summary of paper discussion:

The critical comment made by one reviewer was: “Going back on that trend now only to pursue the polynomial-time nature of the running algorithm would in my opinion require far more diverse evaluation examples, backed by a stronger motivation highlighting real-world threats of all the other MARL algorithms taking longer than polynomial time. As is, SOP-CG does not contend amazingly against other MARL algorithms that chose the "NP-hard? Curse of dimensionality? Fine. We'll approximate, approximate, approximate." path rather than the "Polynomial time is our topmost priority; function expressiveness can wait." path. That leads me back to the question of why pursue polynomial time at the cost of losing both the function expressiveness and the peak performance….”

Comments from Area Chair:

Looking at the experiments, the number of agents in the empirical problems is not large. For example, there are 15 agents in "Sensor." Any focus on computational complexity at this scale is hard to justify, especially with algorithms that are approximate. It seems favorable at this small scale to use function approximators that can take in all the agents' histories and actions. This obvious baseline is not included in comparisons. It is hard to justify inclusion of this paper in the conference.
Decision: Reject