Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper addresses the problem of learning to fulfill a task described by programs designed for parallelization with multiple agents. To this end, the paper proposes a framework that can infer the structure of parallelism from programs and efficiently allocate subtasks by enforcing cooperation and division of labor among agents. The experiments on the overcooked domain, where agents need to collaborate to make dishes, show that the proposed framework outperforms baselines and achieves higher task completion rates and better generalization. Ablation studies suggest that the proposed feasibility predictor, reachability predictor, and cost-to-go predictor all contribute to the improved performance. I believe this work studies a promising problem and presents an interesting framework with sufficient evaluation. Yet, I still have some concerns detailed in the following section.
strengths_and_weaknesses: ## Paper strengths and contributions
**Motivation and intuition**
I believe learning to fulfill a task described by programs designed for parallelization with multiple agents is an important problem and has a wide range of applications.

**Novelty**
To the best of my knowledge, this is the first work researching following program instructions with multiple agents.

**Technical contribution**
- The DSL used in this work seems like a reasonably good DSL for describing the overcooked domains.
- The proposed task allocator learning reachability, feasibility, and cost-to-go seems effective.

**Clarity**
The overall writing is clear.

**Ablation study**
Ablation studies are helpful for understanding thecontributionsn of each component (i.e. reachability, feasibility, and cost-to-go) of learning to allocate tasks.

**Experimental results**
The experimental results show that the proposed framework outperforms a state-of-the-art multi-agent reinforcement learning baseline (MAPPO) and a baseline that is instructed by natural language description.

## Paper weaknesses and questions

**Fully observability**
While not explicitly stated in the paper, this work seems to assume the agents operate in a fully observable environment and the same observation is shared across all agents. This could fundamentally limit applying the proposed framework to more realistic domains.

**Task example**
There are very few task (program) examples given in the main paper and the supplementary material. It is tough to judge the performance of the proposed framework and the baselines without knowing the tasks used to evaluate them. How easy are the easy tasks? How hard are the hard tasks? How different are the tasks used for learning and the tasks used for evaluating zero-shot generalization?

**How to obtain tasks/programs**
This work studies how to fulfill tasks described by programs. It would make more sense to shed some light on how such programs can be obtained in the first place to motivate the problem. I suggest the authors include a discussion on program synthesis works that aim to produce such programs, such as RobustFill: Neural Program Learning under Noisy I/O (ICML 2017), Neural Program Synthesis from Diverse Demonstration Videos (ICML 2018), Execution-Guided Neural Program Synthesis (ICLR 2019), Learning to Describe Scenes with Programs (ICLR 2019), Latent Execution for Neural Program Synthesis (NeurIPS 2021), etc.

questions: Described in Strengths And Weaknesses section.
limitations: Described in Strengths And Weaknesses section.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper introduces a new method “E-MAPP” , a framework which utilizes a centralized program to issue subtasks to agents within a team to achieve tasks which require long-term planning. EMAPP contains a central programmatic controller which issues goals to a team of subagents. These agents are goal-conditioned policies who are trained specifically to solve these subgoals. The paper evaluates their claims on the Overcooked environment and evaluates against baselines such as MAPPO. Another notable addition is the increased complexity added to the game dynamics within the Overcooked environment.

strengths_and_weaknesses: The paper is well written and the diagrams are exceptionally useful to articulate the approach being taken. The approach seems original (in the context of MultiAgent systems) however I can not comment on how novelly it extends Program use within Single Agent RL.
 
My main criticism of this work is the sheer complexity of the proposed approach, the limited analysis of its improvement over baselines, and its overall usefulness. 

1. It is unclear how much information is arbitrarily being hardcoded into the program executor (what decides the perception and behavior primitives), nor is it clear how you devise the Possible Subroutine Set. Hardcoding such components reduces the ability for this approach to be applied to any novel task. Thus this approach does not help discover/explore novel solutions to the game of Overcooked.

2. To further this, the additional auxiliary tasks used to shape the policy network (feasibility, reachability, cost-to-go) are also hardcoded heuristics to evaluate sub-agent fitness for a task. In new problem domains it is unclear how you can devise this. In particular the Criteria for subtask allocation confuses me. Surely simple reward maximizing would lead to this criteria naturally arising within the Task Allocator.  

3. There is no discussion on the computationally complexity or feasibility of this approach versus baselines. In comparison to the baselines this seems to contain significantly more networks, a search for legal subtask allocation which scales O(n!) to the number of subtasks and finally a curriculum which requires pre-training a state on ground truth sub-goals, training n agents separately and finally then training the joint n-agents. 

4. Given the complexity of E-MAPP it is unclear where to attribute performance gains to. In particular the baseline of “Natural language–guided model” is never explained. A comparison of the goals provided by the Natural Language (or vocab size) vs the Task Allocator (and number of primitives) would be useful.

5. E-MAPP fundamentally is a centralised execution algorithm (a joint policy is learnt) - so to compare to decentralised execution algorithms such as MAPPO seems disingenuous. A much better comparison would be a centralised agent. Such a comparison would help justify the claim of “time efficiency” presented in the abstract.

6. Given the sheer amount of biases and knowledge bestowed into E-MAPP it seems trivial to outperform MAPPO or other methods on discovering winning strategies for harder tasks.  

7. The choice of rewards (0.2 for subtask, 1 for task) provided in the “Average Scores” seem arbitrary. Please provide reasoning for these.

questions: 
Mostly stated above the in the weaknesses section:

1. I find it very hard to understand what the Program Executor actually suggests or how this is synthesised. Can you provide examples of the programs devised.

2. Analysis of queries asked and performance of the state encoder on producing correct answers would be useful to understand how well the Program Executor /State Encoder is working.

3. Understanding the number of unfeasible tasks produced would be useful.

4. It is unclear why E-MAPP performs imperfectly in the easy environment. Can the authors add some comments on this. 

5. Ablation analysis of E-MAPP (as it has many components) in general would be appreciated, it's unclear where to attribute performance gains to currently.


limitations: It would be useful to discuss limitations in computation resources and scalability of this approach. Overcooked is neither a game of many players or many coordination conventions.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This work introduces Efficient Multi-Agent Reinforcement Learning with Parallel Program Guidance (E-MAPP), a methodology designed to enable multi-agent, long-horizon task completion. Toward this goal, E-MAPP structures tasks as (parallelizable) programs using a hand-designed domain-specific language (DLS) which specifies behavior subtasks (e.g. chop a tomato) and "perception primitives" (e.g. is anything on fire); a top-level controller then uses these perceptual primitives, along with the given program, to assign agents to subtasks so as to efficiently complete the overall task. E-MAPP is evaluated using a novel extension of the Overcooked gridworld from prior work (in Overcooked, multiple agents must work together to compose dishes. Compared to competing baselines (MAPPO and a variant of MAPPO with language guidance), E-MAPP produces agents that are substantially more competent at solving challenging, long-horizon, tasks in the Overcooked environment even when those tasks were not seen during training.

strengths_and_weaknesses: ## Strengths

This paper studies an interesting and challenging problem (long-horizon planning in the cooperative multi-agent setting). The proposed E-MAPP framework makes several non-trivial extensions to the idea of program-guided single-agent task completion introduced in prior work. The presented empirical results suggest that E-MAPP can be quite effective, especially when compared to standard "end-to-end" multi-agent RL methods (e.g. MAPPO) which do not use programs as an inductive bias. The paper is well-written grammatically although, as I note below, some work can be done to improve overall clarity.

## Weaknesses

While I very much appreciate the core goal of this paper, I do believe there are a few weaknesses that temper my enthusiasm (described below).

- Many pretrained components

This work appears to depend on a very large number of pretrained components: perception modules, single-agent policies, and each of the three auxiliary functions (reachability, feasibility, and cost-to-go). That these all must be trained in different phases with separate datasets and different training techniques (e.g. self-imitation learning) seems to make it quite challenging to E-MAPP in new settings.

- Efficiency of subtask allocation

The current strategy for subtask allocation, from my understanding, requires searching over a search space that grows exponentially in the number of tasks and agents (M^N possible allocations of N agents to M tasks). This appears to limit the applicability of E-MAPP to tasks with larger numbers of agents.

- Fully observed and low-dimensional

The need to train many separate components to high levels of accuracy suggests that E-MAPP may not work well in complex, high-dimensional, environments (e.g. learning from pixels or learning in partially observed environments) where even training the perception modules may be very challenging.

- Clarity

While the paper is quite easy to read from a grammatical standpoint, I found several parts of the paper to be needlessly vague. For instance:

1.  The continuous control experiment is essentially completely unexplained, no results are even mentioned in the main paper and the appendix provides little additional detail.
2. The inputs given to the various baseline models (MAPPO and the model with NL guidance) is unclear in the main paper. Even reading the appendix I'm unsure how the goal is encoded and given to the MAPPO agent.
3. Several figures take up quite a lot of space (e.g. Fig 2/3/5) while the heart of the paper, namely the description of how exactly the E-MAPP framework works (e.g. pointer allocation and when/how the auxiliary functions are used) is largely relegated to the appendix.

## Line-by-line notes

Here are a few minor line-by-line notes:

- Line 33
    * "different feasibility" sounds odd.

- Line 64
    * Factorization approaches have also been investigated on the policy side, see e.g. "A Cordial Sync: Going Beyond Marginal ..." Jain et al. (ECCV'20)
 
- Line 65
    * It seems a bit strange to not highlight imitation learning, and related ideas, as an approach for solving long-horizon tasks and the sparse reward problem. E.g. generative adversarial imitation learning.

- Line 152-153
    * "...to a subtask that requires to be..." -> "...to a subtask that must be..."
 
- Line 155
    * "a perceptive query is responded" -> "a response to a perceptive query is received"
 
- Lines 156-159
    * Things are quite vague, give an example.

- Lines 181-182
    * An ablation of this choice would be nice.
 
- Line 208
    * "reducing the binary" -> "minimizing the binary"

- Lines 227-228
    * Why apply log to feasibility and reachability and not cost-to-go?

- Lines 247-249
    * The phrasing here is a bit confusing, it almost seems like your extension is a whole new environment. You should rephrase to make more clear that you didn't build a new gridworld but you adapted an existing one.
 
- Line 259
    * What's the definition of "novel" here?

- Line 266
    * "accumulative" -> "cumulative"
 
- Line 292
    * "find removing" -> "find that removing"

- Table 3
    * The error bars for the average scores seem huge?
 
- Appendix Lines 562-567
    * Do you also use self-imitation learning with the MAPPO baseline? If not, what is the impact of self-imitation learning alone?
 
- Appendix Lines 624
 - "sclae" -> "scale"

questions: Currently, I lean towards rejection as the weaknesses I've listed above seem quite substantial when considering applying E-MAPP to a new domain. I would be more than happy to increase my rating if strong arguments could be given as to why I might be mistaken. I would be particularly interested in hearing responses to my concerns regarding the number of pretrained components and the requirements for full observability / low dimensional states. I have also included a few, more minor, questions in my line-by-line notes above.

limitations: Assuming the weaknesses I've flagged above are true weaknesses, it would be great to be upfront and add these to the limitations section. I don't believe there are any substantive ethical concerns for this work.
review_title: null

Meta-review: metareview: This paper deals with complex long-horizon tasks with multi-agent RL. The authors propose E-MAPP method that leverages parallel programs to guide multiple agents with goals to accomplish the task jointly.
Generally, this paper is with an interesting idea and has sound technical contributions. The presentation is a bonus point of this paper. The rebuttal mostly eases the concerns of the reviewers. As a result, all the reviewers vote for an acceptance of this paper.
The major weakness of the proposed method lies in the inconvenience of applying E-MAPP to a new environment or task since it requires a huge amount of work. Maybe due to this reason, the experiment is conducted on overcooked v2 environment only.
In sum, I think this is an interesting paper tackling a type of challenging task and thus recommend an acceptance of this paper.

confidence: Certain
Decision: Accept