Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: multi-agent RL problem can be generally solved in 3 stages: 1) given the current state, a centralized planning problem is formulated, the problem is about which agent should do what (on a high level). 2) the planning problem is solved, allocating each agent with their respective high-level goal. 3) the agents individually carry out the high level goal using low-level controls.

this paper takes these 3 stages, and 1) make them end-to-end and 2) make it decentralized. the result is a model architecture and a training method with an inductive bias towards planning. the authors demonstrate that when agents are trained this way they often do better than the baselines.
strength_and_weaknesses: strength : the technique is sound on a cursory glance (of the math), and the evaluation is thorough, showing (for the most part) good performance when compared with baseline algorithms.

weakness: I think the aspects of interpretability and transferability should be further explored. here's some comments:

1) on interpretability, the author only looked at a simple navigation environment where the interpretation is rather intuitive (or "obvious") -- distance is useful. I would like to see if a similar kind of intuition can be seen in the starcraft environment. The interpretability aspect is also not vetted against 3rd party users (i.e. crowd-workers) but rather the authors themselves, which lowers the validity of the "interpretability" claim. One could imagine a small survey on a crowd-worker setting where behaviours of several different algorithms were demonstrated, and the workers asked to describe them. Then, one can measure whether the descriptions agree with each-other as a proxy for interpretability. also, what about a video? I used to play a lot of starcraft and I'm actually in a good position to judge if the agents are behaving in a predictable way if only I can see a few videos, but all I get is success ratio, which hides away a lot of the details (did they succeed without taking any damage? did they do it fast or really dragged it out? did they focus fire? did they pull back the unit that was hurt? did they reposition themselves to a favorable flank before engaging? did protoss learn to abuse the fact that shields regenerate while HP do not?) these are the kind of "interpretation" that I would like to see. 

Does the LP problem, invented by the neural network from end-to-end training, reflect these interpretable strategies? You can imagine an intervention, where the end-user is allowed to control these LP problems with some instrumentation, which should result in behavioural changes to the agents. This is similar in spirit to giving the user a slide-bar on some latent disentagled vector representation and have them slide it over. Can a similar experiment be constructed?

2) on transferability. what about 20m_vs_20m? what about 12 stalkers vs 24 zealots? there's actually quite a bit of combinatorial space of match ups, and presumeably fairly easy to set-up and run. You might discover the agents need to adopt different strategies after a certain "critical points" -- for instance, 2 stalkers can probably brute-force kill 2 zealots, but against 4 you really need to kite.
clarity,_quality,_novelty_and_reproducibility: quality : normal

clarity : good

originality : good. I liked the idea of taking this 3 step process "make a planning problem, solve the planning problem, execute the plan" into end-to-end and distributed.

evaluation : needs work. "interpretation" can be significantly expanded upon, "transferability" can be significantly expanded as well. at the bare minimum, show some starcraft playing videos.
summary_of_the_review: overall, the paper is technically sound (as far as I could tell), and the quantitative results are comparable with baseline algorithms.

however, the qualitative claim on interpretation is bit of a stretch, as their notion of interpretability is essentially "the authors themselves looked at the resulting multi-agent strategy, and decided that 'yep, it made sense'". A 3rd party judgement would be good, extending the analysis on interpretability to starcraft would be good.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper considers training a multi-agent reinforcement learning (MARL) model with sparse reward. It proposes a linear programming-based hierarchical MARL for the considered problem. It claims that the proposed approach learns an optimal agent-task allocation and also a local cooperative policy for agents in sub-groups. 
strength_and_weaknesses: Strength: 
1. The proposed LP-based approach for agent-task allocation is novel to me. The paper discusses how the LP formulation can be generated using GNN and how to train it in an end-to-end manner with implicit function theorem. 
2. The mathematical formulation in this paper is clearly written.

Weakness:
1. The motivation of this work is not clear to me. The problem definition, challenges, and background are not discussed in a clear manner.
2. It does not contain theoretical justification of why the proposed approach works as desired.
clarity,_quality,_novelty_and_reproducibility: The quality of this paper is fair. The clarity needs to be improved. The proposal of LP-based approach is novel to me.
summary_of_the_review: The motivation of this paper is not clear to me. The problem definition, challenge, and background needs to be discussed in more detail. The proposed LP-based approach is novel and the paper provides a complete end-to-end training diagram for the proposed approach. However, it lacks theoretical justification of why it works as desired.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper introduces the LPMARL framework to address the sparse reward challenge in MARL. Specifically, LPMARL consists of two hierarchical decision-making parts: 1) the high-level part solves the agent-task assignment as the LP problem, and 2) the low-level part solves local games among agents with the same task. To enable decentralized execution, the paper also develops Dec-LPMARL by amortizing the task allocation of LPMARL. Empirical evaluations in cooperative navigation and SMAC domains show the effectiveness of the proposed approach. 
strength_and_weaknesses: **Strengths:** 
1. Formulating the high-level agent-task allocation problem as LP is novel. 
2. The interpretability and transferability are beneficial properties of LPMARL. 

**Weaknesses and Concerns:**
1. My biggest concern is possible unfair comparisons against baselines. In particular, LPMARL is centralized training & centralized execution approach, and the baselines are centralized training & decentralized execution approach. Therefore, comparing Dec-LPMARL (centralized training & decentralized execution) against the baselines for fairness, it is unclear whether Dec-LPMARL is a clear winner (e.g., HSD performs better than Dec-LPMARL in Table 1). 
2. The clarity of the paper generally needs improvement. For example, this paper uses (hierarchical) Dec-POMDP as the base framework, so each agent receives observation $o_{i,t}$ not the state $s_t$. However, LPMARL uses the state information (see Figure 1, where the input is the state) to construct the agent-task score, and it is unclear how the state can be constructed based on observations. Similarly, the paper uses $s_i$, but it should be $o_{i}$. Lastly, Equation 8 uses the state to decide the low-level action, but it should be $o_i$. 
3. Regarding the non-hierarchical MARL baselines, it is unclear why the weighted sum of the high- and low-level rewards is used to train them. Wouldn't it be fairer to train them with the environment rewards only?

**Minor:**  
1. In Figure 1, instead of "ag", "agent" can improve readability. 
2. Typo: "Dec-LPMLARL" to "Dec-LPMARL"
3. Could you clarify what high-level action space is in the cooperative navigation domain? 
clarity,_quality,_novelty_and_reproducibility: **Clarity:** The paper needs improvement with using consistent notations throughout the paper.   
**Quality & Novelty:** I agree that the high-level task allocation part is novel.    
**Reproducibility:** The source code is not provided, so it is not trivial to reproduce the results.
summary_of_the_review: I would like to initially vote for 5 due to the concerns above. After the authors' response to my concerns and questions, I will make a final decision on the recommendation.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This introduces a hierarchical framework for multi-agent reinforcement learning. It formulates agent-task assignments as a linear programming problem. With the solution of LP, it generates a low-level policy to solve each sub-task in a cooperative manner. Some empirical experiments are performed to demonstrate the effectiveness of the proposed method.
strength_and_weaknesses: Strength

• The idea of leveraging techniques for differentiation of black box combinatorial solvers for MARL is unique and interesting.

• Experiments are extensive. Fig.1 and Fig.3 are the good visualizing explanation.

Weakness
main comments:
• what is the advantage of using a differentiable LP layer (GNN and a LP solver) as a high-level policy, shown in Eq. 10?

– compare it to [1] that considers the LP optimization layer as a meta-environment?

– compare it to an explicit task assignment protocol (e.g. not implicit).

E.g. a high-level policy that directly outputs task weightings instead of the intermediary C matrix?

• How does this method address sparse reward problems in a better way? From the experiments, this does not support well. in practice, the proposed method requires sub-task-specific rewards to be specified, which would be similar to providing a dense reward signal that includes rewards for reaching sub-goals. If given the sum of low-level reward as the global reward, will the other methods (Qmix) solve the sparse-reward tasks as well?

minor comments:
• It is hard to determine whether the solution to the matching problem (learned agent-task score matrix C) optimized by LP is achieving global perspective over the learning process.

• When the lower-level policies are also trained online, the learning could be unstable. Details on how to solve the instability in hierarchical learning are missing.

• What is the effect of the use of hand-defined tasks on performance? what is the effect of the algorithm itself? maybe do an ablation
study.

• Section 5.2 ”training low-level actor-critic” should be put in the main text.

[1] Carion N, Usunier N, Synnaeve G, et al. A structured prediction approach for generalization in cooperative multi-agent reinforcement learning[J]. Advances in neural information processing systems, 2019, 32: 8130-8140.

clarity,_quality,_novelty_and_reproducibility: The writing of the paper is OK and the idea of the paper is somehow understandable.
summary_of_the_review: This paper is a resubmission of their work from last year.  Compared with last year's submission, the contribution and novelty are marginal.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: I thank the authors for their submission and active engagement during the discussion period.  This is a borderline paper.  On the positive side, reviewers acknowledge  that the method is sound [fFLH], novel [vJe1,VRWi], interesting [LMn4], clear [vJe1], and has the desired properties of interpretability [VRWi], and the empirical evaluation is thorough [fFLH,LMn4]. On the negative side, reviewers noted that comparison to baselines is not fair [VRWi], the clarity of the paper should be improved [vJe1,VRWi] and the method doesn't seem to beat baselines [fFLH]. Given this and the observation that the author's rebuttal doesn't seem to have addressed the concerns of reviewers fFLH and VRWi sufficiently, I believe the weaknesses currently outweigh the strengths of this paper. Therefore, I recommend rejection.
justification_for_why_not_higher_score: Not sufficient support by reviewers. Comparison to baseline would have to be stronger and overall clarity of the paper needs to be improved.
Decision: Reject