E-MAPP: Efficient Multi-Agent Reinforcement Learning with Parallel Program Guidance
Authors: Can Chang
Ni Mu
Jiajun Wu
Ling Pan
Huazhe Xu
Venue: NeurIPS 2022 Accept (2022)
Keywords: multi-agent reinforcement learning
program guided agents
long-horizon tasks

Abstract: A critical challenge in multi-agent reinforcement learning(MARL) is for multiple agents to efficiently accomplish complex, long-horizon tasks. The agents often have difficulties in cooperating on common goals, dividing complex tasks, and planning through several stages to make progress. We propose to address these challenges by guiding agents with programs designed for parallelization, since programs as a representation contain rich structural and semantic information, and are widely used as abstractions for long-horizon tasks. 
Specifically, we introduce Efficient Multi-Agent Reinforcement Learning with Parallel Program Guidance(E-MAPP), a novel framework that leverages parallel programs to guide multiple agents to efficiently accomplish goals that require planning over $10+$ stages. 
E-MAPP integrates the structural information from a parallel program, promotes the cooperative behaviors grounded in program semantics, and improves the time efficiency via a task allocator. We conduct extensive experiments on a series of challenging, long-horizon cooperative tasks in the Overcooked environment. Results show that E-MAPP outperforms strong baselines in terms of the completion rate, time efficiency, and zero-shot generalization ability by a large margin.

E-MAPP: Efficient Multi-Agent Reinforcement Learning with Parallel Program Guidance
Can Chang 1.2 Ni Mu Jiajun Wu', Ling Pan Huazhe Xul
IIS, Tsinghua University Shanghai Qi Zhi Institute Southeeatt University
4 Stanford University Mila, Université Montréal cc22@mails co22@mails.tsinnhuua tsinghua edu, en, xuhuazhe 12wgma2l.c..oommm
Abstract
A critical challenge in multi-agent reinforcement learning (MARL) is for multiple agents to efficiently accomplish complex, long-horizon tasks. The agents often have difficulties in cooperating planning through several stages to make progress. We propose to address these challenges by guiding agents with programs designed for parallelization, since programs as a representation contain rich structural and semantic information, and are widely used abstractions for long-horizon tasks. Specifically, we introduce Efficient Multi-Agent Reinforcement Learning with Parallel Program Guidance (E- MAPP), novel framework that leverages parallel programs to guide multiple agents to efficiently accomplish goals that require planning over 10+ stages. E- MAPP integrates the structural information from a parallel program, promotes the cooperative behaviors grounded in program semantics, and improves the time efficiency via a task allocator. We conduct extensive experiments on series of challenging,
common goals, dividing complex tasks, and
cooperative tasks in the Overcooked environment. Results show that E-MAPP outperforms strong baselines in terms of the completion rate, time efficiency, and zero-shot generalization ability by a large margin.
Introduction
Multi-agent reinforcement learning (MARL) has achieved significant progress by advancing the co- operation of multiple agents accomplish complex tasks, e.g., multi-robot control [20), autonomous driving [48 [4], and video games [50 4 Most recent advances in MARL focus on tasks that feature behavior coordination [39] or joint motion planning 41.. However, for long-horizon tasks such as preparing a dish, existing methods often suffer from the inability to understand the task compo- sitionality and subtasks' dependencies, resulting inefficient cooperation and frequent conflicts. Therefore, natural question to ask here is how we can solve long-horizon tasks in MARL, in the face of large state/action spaces and sparse feedback.
Long-horizon tasks are usually blessed with rich structure, and thus can be divided into a sequence of subtasks that be resolved separately. Previous work [45 52 has introduced programs as instructions to help a single agent understand the task hierarchy and accomplish the task. Inspired by them, we develop a general multi-agent framework, where agents can leverage programs for accomplishing long-horizon tasks together. This is challenging problem, and three substantial issues will emerge multiple agents are naively enforced to follow sequential programs: first, sequential programs do not explicitly express the dependencies among subtasks, thus hindering the division
Project page: http:://stes.goglle..om//wevw/es
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

of jobs among agents; second, different agents might have different abilities to accomplish certain subtasks or lines of programs; third, when assigned subtask together, multiple agents might need to collaborate without blocking resources with each other.
As modern CPUs dispatch instructions parallel processors, propose new multi-agent frame- work, Efficient Multi-Agent Reinforcement Learning with Parallel Program Guidance (E-MAPP), guiding cooperation and execution by automatically inferring the structure of parallelism from pro- grams. Specifically, we first design domain-specific language (DSL) for multi-agent cooperation, and use multi-stage learning to ground subroutines of given program into the agents' policy. Then, we learn feasibility functions, which entail the ability of agents to complete specific subroutines in the program in the status quo. Finally, we leverage the learned task structure to automatically enforce cooperation and division of labor among agents.
We conduct experiments on gradually more difficult challenges in the Overcooked (50) environment. The Overcooked environment requires the agents to cooperate on very long-horizon tasks, such as preparing dishes, while avoiding conflicting behaviors. Our method significantly outperforms other strong baselines in completion rates and efficiency. The program structure also enables E-MAPP to deliver superior compositional generalization to novel scenes.
Our main contributions can be summarized as follows:
We formulate a novel task of learning multi-agent cooperation via the guidance of parallel programs.
We present a novel framework for program grounding and long-horizon planning and instantiate the framework into practical multi-agent reinforcement learning algorithms.
We demonstrate the effectiveness of E-MAPP in completion rates and generalization ability over existing strong baselines and provide empirical analysis in long-horizon tasks.
2 Related Work
Cooperative Multi-Agent Reinforcement Learning. In multi-agent cooperative game, agents collaborate with each other on a common goal [33]. Researchers have investigated many ways
to facilitate agent coordination [21 12 53
34
19]. Value-based MARL algorithms engage in
discovering the relationship between global value function and local value functions 46 38), while volicy-based MARL algorithms use centralized critic [51 26 to coordinate agent behaviors. More specifically, MAPPO [5T] and MADDPG (26) leverage fully-observable central critic to solve the issue of non- -tatioattnn
33 Value factorization approaches [38] 46 (37 decompose the global
value function into a combination of local agent-wing wise utilities to cope with scalability, while policy factorization approaches
[8
factorize the joint action space to coordinate marginal policies.
Reinforcement Learning for Long-horizon Tasks. Reinforcement learning agents usually lack the ability to plan and reason over long time horizon due to sparse rewards [49] [14] 40 [55 30). Goal-conditioned reinforcement learning (36] is one of the popular paradigms to address the sparse supervision problem. Imitation learning 17 [6 is another approach to solving the sparse reward problem. Another line of work has presented automatic goal generation and selection algorithms [ 24, 9]; however, this introduces new challenges to design suitable goal space that enjoys rich semantic meanings [13] By contrast, our work uses the subtasks corresponding to possible subroutines in program as goals, which are associated with domain knowledge. Hierarchical reinforcement learning [HRL; 47 42 28
35
43 29] is another path to solve long-horizon tasks, using high-level policy for long-term planning and low-level policies for motion planning or specific behaviors. While our work is related to multi-agent hierarchical reinforeement learning (27). which explicitly provides the directed acyelic task graph and the necessity of cooperation of each subtask, we focus on learning task structure such as subtask dependencies, loops, and branchings from the program and judging the necessity of cooperation without additional information.
Instruction-Guided Agents. Many recent advances have testified the advantages of leveraging
structured prior knowledge such as task graphs [2].. natural languages (2 23) and programs [45]
52 to promote efficient policy learning. In contrast to other structured priors, programs stand out
because of their strictly formatted and composable subroutines
5 7 Previous works leverage
programs to enable a single agent to learn complex tasks by following programs
45 52 However,
plethora of new challenges have been introduced, including task dependencies, collaboration schemes,

---

G peattel:
+ (Orion)
PNLSMEE-nn (ret)
pointer
+ IntardEfonatts) (efitee)) Branching Queries
Prepons(wiaat)
Senwehatte)
(TTombo))
Possible Subtasks
trgpretTiontt))
Program Exccutor
4:
Perception
Task
Joint Action
Module
Allocator
xO
Pollccy Module
State
The overall framework of E-MAPP. E-MAPP includes four components: 1) A perception module that maps query q and the current state s to boolean responses. 2) A program executor that maintains pool of possible subtasks and updates them according to the perceptive results. 3) task allocator that chooses proper subtasks from the subtask pool and assigns those to agents. 4) A policy module that instructs agents taking actions to accomplish specific subtasks.
Figure 1:
and others; hence, it difficult to trivially extend the existing works in the MARL settings. To enable multi-thread orderless policy execution, we leverage "plug-and-play" auxiliary functions to infer the relationships among subtasks.
3 Problem Statement
3.1 Program Guided Cooperative Markov Game
,L...., N An infinite-horizon Markov Game is defined by tuple (N, S,A, T. R, where N
denotes the set of N engaging agents, S denotes the state space, A A x ... x A denotes the Cartesian product of all the N agents' action space, T: S from current state to the next state s' for the joint action a = (a',.... "a'.....a"" ).,, R = R x ... x R denotes the Cartesian product of all the agents' reward functions, where each R2 determines the factor.
denotes the state transition function
immediate reward for the i-th agent from the current state and joint action and y is the discount
At each time I, each agent i observes the current state st. makes the decision af, and re- ceives the reward rt- In cooperative game, the collective goal is optimize the joint pol- icy S + A to maximize the sum of each agent's expected cumulative discounted rewards B
Ee 7 (sr, at)
A program gongram-guided Markov game is Markov game with a factorized state space. Specifically, state S=S. S. Sp. where S. the common state space of the environment and S, is the multi moitter program space (section 3.2). Accordingly. the state transition function takes as input the current compounded states (Se, 8p) and joint actions a and then returns the next joint state (8/, s5)). this study, the transition function of the program space is based on predefined rules.
3.2 Parallel Programs
The program space consists of three components: a domain-specific language (DSL. that contains all the possible subroutines, set of pointers that point relevant subroutines, and a control flow that manages the pointers. A complete specification of the DSL used by our framework is in the Appendix A Inside this DSL, subroutine is a minimal executable unit the program that corresponds to subtask in the domain (e.g., Chop( Tomato)). As in previous works [5] [22] we consider two types of subroutines: perception primitives (e.g., IsOnFire()), which query about the status of the environment; and behavior primitives (e.g., Chop(Tomato), which issue an instruction. Control flow involves branching statements (if/lse)) loops (for/while), and parallelism indicators (repeat/parullel), The parallelism indicators are designed for multi-thread execution. The subroutines in a parallel block are possible not guaranteed run concurrently, i.e., the agents should reason about what subroutines in parallel block can be executed concurrently. The

---

Modulation
True
Perceptive Output
State Encoder
Encoder
CNN/MLP
State
Multiply
IsOnFire()?
Add
Perception
Sigmold Function
Primitive
Goal Encoder
Goal Embeddings
Figure 2: The perception module. The perception module encodes the perception primitive into mod- ulation parameters, which operate on the state embeddings to get the goal goal-conditioned embeddings. These embeddings then fed into another encoder, followed sigmoid function. The output is real number in [0, 1). and will be binarized for branching selection by the program executor.
subroutine a repeat block can be executed many times simultaneously. We summarize all the current subroutines that are possible and executable as the Possible Subroutine Set. The of pointers points to all the subroutines in this set.
3.3 Multi-Agent RL with Parallel Programs
In our study, we aim to develop a framework for optimizing the joint policy parallel program- guided cooperative Markov game. To this end, the agents must keep track of the pointers in the program, learn to reason the primitives to choose the right branches, and perform the action either collaboratively or individually to pursue high efficiency.
Method
Our goal is enable multiple agents cooperate to solve long-horizon tasks guided by parallel programs. There are three important factors we should consider: first, the agents should learn subtask- conditioned policies that can be composed together accomplish long-horizon tasks and further generalize compositionally to unseen tasks; second, the agents should reason about task dependencies so that they can automatically parallelize tasks among them; and third, the agents should distinguish between cooperative tasks and cooperprea tasks that can be achieved by single agent to avoid competition for common resources.
We propose Efficient Multi-Agent Reinforcement Learning with Parallel Programs (E-MAPP). a multi-agent reinforcement learning framework where agents can cooperate solve long-horizon tasks by following program guidance. As shown in Figure | E-MAPP includes four components: perception module that able judge whether the queried status exists in the state; parallel program executor that keeps track of subroutines and updates them based on the perception module output; task allocator, which extracts queries of interest and obtains the corresponding subtasks from the program executor, and assigns tasks to agents; and a multi-agent policy module, which agents make their decisions based the input subtask. The following of this section will introduce these four key components of E-MAPP. The complete algorithm is shown in Appendix A.3
of possible
4.1 Parallel Program Executor
The program executor keeps a set of pointers pointing to possible subroutines in a domain-specie Possible Subroutine Set. There are four types of control flows: irrrutnnne while-routine, parallel- routine, and repeat-routine. Meanwhile, there are two types of subroutines our program: behavior primitives and perception primitives.
Control flows. An io-uute contains condition statement (usually a perception primitive) and subroutines in the corresponding blocks. A while-routine contains condition statement and looping

---

State Encoder
x1 x0
x1
State Embedding
Value
State
Altruistic Goal Encoder
Action
Aux Func
Fused Feature
Merge(Plate, Onion)
Perception Primitive
Assistive Determinator
Goal
Independent Goal Encoder
Embeddings
The policy module. We adopt goal-conditioned reinforcement learning framework to determine the policy. We encode goals with a goal encoder and fuse them into the state features. an agent is assistive, the goal is encoded with an altruistic goal encoder instead. The network has three outputs, including the value function, the action distribution, and the auxiliary functions.
Figure 3:
block of subroutines. A parallel-routine contains parallel blocks of subroutines that are possible be executed simultaneously. A repeat-routine contains an unconditioned block of subroutines that can be executed multiple times by different agents.
Subroutines. A behavior primitive (e.g., Chop(Tomatol) corresponds to a subtask that must be completed by the agents. As for perception primitive (e.g-, IsOnFire()), it is query that requires boolean response.
After action is performed response to perceptive query is received, the program executor up- dates its pointers and the Possible Subroutine Set. Detailed updating rules are shown in Appendix AA2 We note that if achieved subtask does not correspond any subroutine in the Possible Subroutine Set, the program executor will terminate the program immediately. This guarantees that no exceptions will occur due to violating the instructed order of subtasks.
4.2 Perception Module
The perception module learns to map query and the current state s; to a boolean answer ø(q. St). For example, when a perception primitive IsOnFire() is passed the perception module, it learns to check the existence of fire in the environment and returns true/false. The architecture is shown in Figure Specifically, hyg as the training dataset and train the network & in a supervised manner. We use binary cross entropy hgg:) the objective, where /tpred denotes the perception
randomly sample states, queries, and the ground-truth perception
(BCE) loss Eperceepiin BC E.C..ooc F. output. In terms of architecture, we encode the perception primitive 8p and the common state 8 with neural encoder. The encoded primitives are represented as y and 3 modulate the encoded common state. At the last layer, we use a sigmoid function to obtain the binary output. Training details and detailed architecture descriptions can be found in Appendix A.5 In this way, this module can determine whether the queried primitive exists in the state to aid the agents' decision-making
4.3 Policy Module
The policy module grounds agents' actions with the programs and encourages cooperation in complet- ing the tasks. The overall policy learning procedure ad advocates a learning framework as shown Figure Our algorithm backbone MAPPO [5T] and consists of two stages. More concretely, we first learn policy for each agent where other agents' policies are fixed. The input is the state and the encoded subtask. The reward signal is based on whether subroutine is executed correctly. Then we enable multiple agents to coordinate by learning joint policy for accomplishing collective goals cooperatively and efficiently, with the help of auxiliary functions and task allocator. We use the same architecture to fuse state and goal features as that in the perception module in Figure We also leverage self-imitation learning to tackle the challenge of sparse rewards, which is shown in Appendix A.4
reinforcement
5

---

reach
Thay get out the
can
Laan delver
Fan claser
(a) reachability
(b) feasibility
(c) cost-to-go
Figure 4: The auxiliary functions. Figure 4a shows the reachability that indicates if an agent can reach object. Figure/4b shows the feasibility that indicates whether a subtask can be achieved by the agents collectively. Figure 4c shows the cost-to-go function that indicates time consumption.
Learning cooperate subtask. After obtaining single-agent policies, then encourage agents to accomplish harder tasks that require cooperation. When assigned cooperative subtask, one of the agents is in charge of finalizing the task. The rest of the agents assistive. For example, the assistive agents might pass an onion to the leading agents to chop. In practice, we randomly appoint one agent as the leading agent and the others the assistive agents. The leading agent is rewarded if this subtask is completed. The reward function for the assistive agents is calculated based on the reachability improvement of the leading agent. We defer the formal definition of this reward function to Section 4.4 Such reward function encourages the assistive agents to help the leading agents obtain rewards. Then, we use MAPPO-style algorithm to obtain cooperation policy. We also encode the leading agent's s goal into the observation space of the assistive agents to enhance information sharing.
4.4
Task Allocator
The task allocator assigns subtasks to each agent to accomplish long-horizon task together. Specifi- cally, we design the task allocator for efficient coordination based on the following principles: 1) only assigns subtasks that are feasible for the agent(s) (S) without additional prerequisite subtasks. 2) If subtask is cooperative, the task allocator would assign the subtask to a number of agents. 3) assigns subtask to the agent that has the lowest cost in terms of execution time.
To facilitate the task allocation, we propose learn three auxiliary functions: a reachability function, feasibility function, and a cost-to-go function as illustrated in Figure Training details of the auxiliary functions Appendix A.6
Reachability. The reachability function freach = freach (St. i, T) is defined as a boolean value complete task alone at the state 8t. For cooperative subtask and
to indicate if agent selected leading agent i, extrinsic reward freach assistive agents for learning altruistic behaviors. To train this reachability function, we randomly sample triplets (st, i) and obtain the ground-truth value I through running the pre-trained non-cooperative policy. Then optimize the network by minimizing the binary cross entropy BCE( (pree s
freach (8t, 4, 7) is provided to the
Feasibility. The feasibility function fyeas feas r) is defined as a boolean variable indi- cating if an agent i can complete subtask with others' assistance at the state s;. The training procedure of the feasibility function is similar to that of the reachability function, except that we leverage the cooperative policy instead of the single agent policy to collect training data.
Cost-to-go. The cost-to-go function Sonst Senst-to-go (St, i, denotes the remaining timesteps for agent i to accomplish the subtask from the state 8,. We leverage trajectories generated by pre-trained intermediate cooperative policy from E-MAPP to train this cost function. Specifically, randomly sample triplets (sc, i, and execute the pre- mre-trained cooperative policy in Section 4.3

---

to obtain the ground-truit truth timesteps go to complete the subtask т. Then we optimize the network by reducing the Mean Squared Error (MSE) Leost-to-go = MSB (SE(Seosstttooaeee cost-to-gor cost-to-go)
pered for
Criteria for subtask allocation. For specific Possible Subroutine Set (TI...., Tm) we denote legal subtask allocation as (Ti, . Tm) such that
is list of n, agents where n4 [T:)- The agents are those in the agent set (1...., N) who aim at completing the subtask T;
For all i E {1,..., .m), if n, is larger than one, then the agent T. is selected as the leading agent and the agent(s) T?? ....., TT" are selected as the assistive agent(s).
For 1 < < I m, we have that T, n T 0, which means no agent is assigned two subtasks simultaneously.
We compute the cost of each possible subtask allocation {Tr T2, T as the sum of three terms
Ctotal
Creas
+ Coost-to-go + Creach
(I)
.where
m
Cíeas
n2 Winss log freas (s, [T(11,,7]]
(2)
Coost-to-go
WeWeost onaa (s, T: Ti)
(3)
m
Creach
Mm =
1 Wrechh log freach (8, Ti[1], TT)
(4)
W feas. Wreach. and Weost are tunable hyperparameters and I[-] is the indicator function. The feasibility term encourages the agents to choose the feasible subtasks, the cost-to-go term encourages the agents to choose the less costly subtasks, and the reachability term guarantees that the subtask assigned to only one agent is non-cooperative. The log operator operating on value approximating will induce huge cost, thus preventing the allocation of an infeasible or unreachable subtask to an agent. We search from the possible allocations T2, Tm) and apply the one with minimal cost as the final allocation.
In practice, we also use two hyperparametens: to be subtracted from the cost-to-go function to encourage the agents to finish their ongoing subtasks, and & to be added to the cost-to-go function to avoid allocating subtasks agent who can never accomplish task within timeout threshold to-
4.5 Complexity Analysis
In an environment with M subtasks and N agents, the brute force search for an optimal allocation indeed has complexity of O). However, the practical complexity is much smaller than it. The reasons are as follows:
1. In a certain stage of long- Long-horizon task. only a small amount of subtasks are feasible. Thus, the subtask amount M can be pruned into a smaller number I. by checking the feasibility function O(M x N) times and ignoring the subtasks whose feasibility functions are less than a given threshold.
2. The engaging N agents be classified into C roles. The agents sharing the same role have the same reachability functions. C is often a property of the task that does not scale with N. For example, in the overcooked environment, C can be the number of connected components of the map. Note that, in E-MAPP, the assistive agents aim to increase the reachability of the leading agents. We define C L new subtasks (7, c), where 7 comes from the L feasible subtasks and e comes from the C' roles. The goal of each new subtask (T.c) to help agents with role e to gain reachability on subtask 7. We can obtain new subtask set of size O(C x L) by extending the original subtask set with these newly defined subtasks. Assume that the number of agents is smaller than the number of feasible subtasks (otherwise, idle agents will inevitably emerge). Under this assumption, each agent will choose to either complete subtask alone or assist certain group of agents with the same role, and each subtask in the new subtask set is allocated to at most one agent to avoid
7

---

conflict. Then the task allocation problem turns into finding the best matching of N agents and O L) subtasks with the smallest total cost, which can be solved by the Hungarian algorithm. The computational complexity is O((N + - O((N + (M)) that scales well.
Experiments
In this section, we aim to investigate the following key questions. First, the program guidance helpful for agents to understand Long-horizon tasks in comparison with other structured information guidance? Second, are the parallel structures in the programs bring forth cooperative behaviors among the agents? Third, does the task allocator improve the completion rates and the time efficiency of the long-horizon tasks by virtue of the auxiliary functions?
5.1 Environment Description
To evaluate the proposed framework, we adapted the previous envi- romment mimicking the video game to a more challenging one "Overcooked v2". Concretely, we extend temporally for the horizon length of a task by adding additional behaviors such "wash dishes" and "put out fire". As shown in Figure agents can navigate through the grid world, interact with objects (e.g., tomatoes, knives), and deliver the dishes to the customers (the yellow star). The goal of the agents is to serve dishes according to the given recipes that can be divided into subtasks, More details about the environment can be found in Appendix A.7
x
x
x1
5.2
Setup
State
Tasks. We test the agents on a variety of tasks with different difficulty levels. The easy tasks contain only one subroutine for verification. The medium tasks contain two or three subroutines. The hard task requires the agents to complete multiple dishes that require at least two subroutines each while putting out the randomly appearing fire. We conduct evaluation in two different patterns, based on seen or unseen tasks. Note that both evaluation scheme are conducted on novel maps, which makes the task more challenging. The unseen tasks share the subroutines with the seen tasks but is never used as a goal during training. The unseen tasks are used to test whether the methods can generalize compositionally. We also note that for the tasks with a repeal command (e.g., repeatedly pick an onion from the supply), targeted repeat number preset.
Figure 5: A sample from the
Overcooked environment.
Metrics. We use the completion rates and the average scores as the metrics. The completion rate defined the percentage of tasks that can be completed in episode. The average score the discounted cumulative rewards in an episode across all testing tasks. Agents will receive a reward of 1 when the final goal is achieved and receive reward 0.2 when a correct subtask completed. Each algorithm is tested in 1000 environments and we report their average in the tables.
Baselines. We compare our model with two basclines: MAPPO 51 and natural language language-guided agent. Detailed descriptions are in Appendix A.9
5.3 Results
Results with seen tasks in novel maps. Table [ shows the completion rate and average scores on seen tasks in novel maps, demonstrating that E-MAPP excels at understanding the structure of complex tasks. As expected, the end-to-end MAPPO model performs well on short-horizon tasks, but suffers from significant performance drop when the task becomes complex. The natural language-guided model also has large performance drop when the horizon of the tasks becomes longer. We attribute this to the agents" failure to understand the complex task structure described in natural language without explicit structure. By contrast, E-MAPP performs well even when the tasks have a long horizon with various accidental events happening.

---

Table 1: Results on the seen tasks novel maps. Completion rates and average scores of seen tasks in the Overcooked environment with three difficulty levels.
Completion Rates
Average Scores
Methods
Easy
Medium
Hard
Easy
Medium
Hard
E-MAPP (ours)
98.0%
97.5%
56.3%
1.06++0.17
1.12++0.22
1.58++0.60
Natural language guidance
81.9%
48. 1%
1.01%
0.87+-0.43
0.63+0.51
0.82 + 0.31
MAPPO [51]
100.0%
65.7%
0.00%
1.11+0.04
0.79++0.31
0.59+ 0.27
Generalization with unseen tasks in novel maps. Table 2 shows the results the zero-shot generalization scheme. The scenarios and tasks are very different from the training domain, posing an extra challenge all the algorithms, including the auxiliary functions of E-MAPP. We find that E- MAPP is significantly better than both the previous multi-agent RI. algorithms and a language-guides agent. We attribute the success of E-MAPP to the fact that programs have better compositionality and less ambiguity. In the training time, E-MAPP learns certain subroutines from other tasks; it applies the behavior compositionally achieve goals never seen during training. More visualized results in Appendix A.8
Table 2: Results on the unseen tasks in novel maps. Completion rates and average scores of unseen tasks with two difficulty levels.
Completion Rates
Average Scores
Methods
Medium
Hard
Medium
Hard
E-MAPP (ours)
100.0% %
43.7%
1.13 + 0.10
0.99
0.22
Natural language-guin guided model
58.4%
0.0%
0.58 + 0.50
0.48 + 0.21
Ablation of auxiliary functions. We analyze the significance of the proposed key components in our model by comparing our model with the variants that removes 1) the feasibility predictor 2) the reachability predictor 3) the cost-to-go predictor. The completion rates and the average scores are shown in Table B] We find that all the components are important to E-MAPP. Specifically, we find that removing the reachability predictor from E-MAPP leads to a significantly increased average timestep, and this is the component that provides the largest performance gain. We attribute this to the reachability function that pointed out the subtasks that can be completed individually, providing an impetus for agents to parallelize.
Ablation of parallelism in the programs. We compare the proposed parallel programs with sequential programs in the same environments. In Table 3 we find that the agents with parallel programs use 15% fewer time steps accomplish the same goal as those with sequential programs. These results show that the parallel programs are central to E-MAPP in terms of time efficiency.
Table 3: Ablation study, Completion rates, average scores, and timesteps when one of the key components of E-MAPP is removed.
Completion Rates
Average Scores f
Average Timesteps
E-MAPP
56.3%
1.58
0.60
17.6
w/o feasibility predictor w/o reachability predictor
38.5%
1.42 0.56
21.24
43.8%
1.45 + 0.50
23.37
w/o cost-to-go predictor sequential program
52.0%
1.46 0.45
20.42
48.8%
1.51 + 0.47
20.33
Partially observable environments. We conduct an experiment to show that E-MAPP can still outperform other methods in a partially observable environment. In the new setting, the observation of each agent only part of the map within reach. Table shows the results. Under the new setting, E-MAPP can still learn to allocate sub-tasks to agents and accomplish tasks efficiently.

---

Table Additional experiment in partially observable environments we conduct an experiment to show that E-MAPP can still outperform other methods in a partially observable environment.
model
score
completion rate
E-Mapp(partial obs)
1.01=0.38
27.1% %
E-MAPP(original)
56.3% 1.58+0.60
MAPPO
0.59# 0.27
0.0%
5.4 Visualization of Learned Behaviors
pertllet
Chelosted +
ServeDsie)
(a) parallel
(b) repeat
assist
Figure 6: Learned behaviors of E-MAPP. Figure 6a shows that two agents are assigned two subtasks concurrently. Figure shows that both agents are trying to repeatedly perform the same task. Figure 6c shows that one agent is passing an onion to the agent who can chop it.
In Figure we show the representative learned behaviors of E-MAPP. In Figure o(a), the two subroutines are allocated to two agents separately. This demonstrates the effectiveness of the feasibility function, with which the task allocator successfully identified the parallelizable subtasks that can be executed concurrently. We note that the purallel indicator in the program only suggests the agent trying to identify what subtasks are parallelizable rather than providing a ground-truth task structure. In Figure b[b), we find that the two agents are performing the same task in repeat subroutine independently. We show the allocator can assign tasks to multiple agents that are reachable to the goal. In Figure we show that an assistive agent is passing onion to the leading agent to chop. This shows how the agents learn to cooperate with each other. More visualizations can be found in Appendix A.8
5.5 Scalability to New Domains
We also investigate whether E-MAPP can be effective on tasks with continuous action space based on the Stacking environment. More details and demos in Stacking can be found in Appendix 10 We discuss some potential parallel-pe prralle-program synthesis approaches when applying E-MAPP to a new domain in Appendix(A.12 A.14
6 Conclusion
In this paper, we first formulate the problem of program-guides multi-agent tasks. We propose Efficient Multi-Agent Reinforcement Learning with Parallel Programs (E-MAPP). effective framework that uses type of parallelism-aware program for multi-agent collaboration and task allocation strategy via of learnable auxiliary functions. The results show that our algorithm can infer the task structure and significantly boost completion rates, efficiency, and generalization ability on long-horizon tasks.
Limitations. Our current framework does not consider more challenging scenarios such as dynamic or generalization novel objects. We believe that this work opens welcoming avenue this research direction, and more future works will address additional challenges.
Acknowledgements. writing suggestions.
We thank Yuping Luo and Zhecheng Yuan for their careful proofreading and
10

---

References
[1] Christopher Agia, Krishna Murthy Jatavallabhula, Mohamed Khodeir, Ondrej Miksik, Vibhay Vineet, Mustafa Mukadam, Liam Paull, and Florian Shkurti. Taskography: Evaluating robot task planning over large 3d scene graphs, In Aleksandra Faust, David Hsu, and Gerhard Neumann, editors, Proceedings of the 5th Conference on Robot Learning, volume 164 of Proceedings of Machine Learning Research, pages 46-58. PMLR, 08-11 Nov 2022.
[2] Michael Ahn, Anthony Brohan, Noah Brown, Yevgen Chebotar, Omar Cortes, Byron David, Chelsea Finn, Keerthana Gopalakrishnan, Karol Hausman, Alex Herzog, Daniel Ho, Jasmine Hsu, Julian Ibarz, Brian Ichter, Alex Irpan, Eric Jang, Rosario Jauregui Ruano, Kyle Jeffrey, Sally Jesmonth, Nikhil Joshi, Ryan Julian, Dmitry Kalashnikov, Yuheng Kuang. Suang-Huee Lee, Sergey Levine, Yao Lu, Linda Luu, Carolina Parada, Peter Pastor, Jornell Quiambao, Kanishka Rao, Jarek Rettinghouse, Diego Reyes, Pierre Sermanet, Nicolas Sievers, Clayton Tan, Alexander Toshev, Vincent Vanhoucke, Fei Xia, Ted Xiao, Peng Xu, Sichun Xu, and Mengyuan Yan. Do as can and not as i say: Grounding language in robotic affordances. In arXiv preprint arXiv:2204.01693 01661, 2022.
[3] Marcin Andrychowicz, Filip Wolski, Alex Ray, Jonas Schneider, Rachel Fong. Peter Welinder, Bob McGrew, Josh Tobin, OpenAI Pieter Abbeel, and Wojeiech Zaremba. Hindsight experience replay. Advances in neural information processing systems, 30, 2017.
[4] Kai Arulkumaran, Antoine Cully, and Julian Togelius. Alphastar: An evolutionary computation perspective. In Proceedings of the genetic and evolutionary computation conference companion, pages 314-315, 2019.
[5] Rudy Bunel, Matthew Hausknecht, Jacob Devlin, Rishabh Singh, and Pushmeet Kohli. Lever- aging grammar and reinforcement learning for neural program synthesis. arXiv preprint arX1v:1805.04277, 2018.
[6] David Chen and Raymond Mooney. Learning to interpret natural language navigation instruc- tions from observations. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 25, pages 859-865, 2011.
[7] Xinyun Chen, Chang Liu, and Dawn Song. Execution-guided neural program synthesis. In International Conference on Learning Representutions, 2018.
[8] Xinyun Chen, Dawn Song, and Yuandong Tian. Latent execution for neural program synthesis, 2021.
[9] Todor Davchev, Oleg Sushkov, Jean- Baptiste Regli, Stefan Schaal, Yusuf Aytar, Markus Wulfmeier, and Jon Scholz. Wish you were here: Hindsight goal selection for long-horizon dexterous manipulation. In Deep RL Workshop NeurlPS 2021, 2021.
[10] Jacob Devlin, Ming-Was Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint arXiv: arXiv:1810.04 1810.04805 2018.
[1I] Jacob Devlin, Jonathan Uesato, Surya Bhupatiraju, Rishabh Singh, Abdel-rahman Mohamed, and Pushmeet Kohli. Robustfill: Neural program learning under noisy i/o. In International conference on machine learning, pages 990-998. PMLR, 2017.
[12] Ziluo Ding, Tiejun Huang, and Zongqing Lu. Learning individually inferred communication for multi-agent cooperation. Advances in Neural Information Processing Systems, 33:22069-22079, 2020.
[13] Zach Dwiel, Madhavun Candadai, Mariano Phielipp, and Arjun K Bansal. Hierarchical policy learning is sensitive to goal space design. arXiv preprint arXiv:1905.00
2019.
[14] Scott Emmons, Ajay Jain, Misha Laskin, Thanard Kurutach, Pieter Abbeel, and Deepak Pathak. Sparse graphical memory for robust planning. Advances in Neural Information Processing Systems, 133:5251-5266 2020.

---

[15] Ben Eysenbach, Russ R Salakhutdinov, and Sergey Levine. Search on the replay buffer: Bridging planning and reinforcement learning. Advances in Neural Information Processing Systems, 32, 2019.
[16] Abhishek Gupta, Vikash Kumar, Corey Lynch. Sergey Levine, and Karol Hausman. Relay policy learning: Solving long-horizon tasks via imitation and reinforcement learning. In Conference on Robot Learning, pages 1025-1037. PMLR, 2020.
[17] Jonathan Ho and Stefano Ermon. Generative adversarial imitation learning. Advances in neural information processing systems, 29, 2016.
[18] Unnat Jain, Luca Weihs, Eric Kolve, Ali Farhadi, Svetlana Lazebnik, Aniruddha Kembhavi, and Alexander Schwing. cordial syne: Going beyond marginal policies for multi-agent embodied tasks. In European Conference on Computer Vision, pages 471 471-490. Springer, 2020.
[19] Natasha Jaques, Angeliki Lazaridou, Edward Hughes, Caglar Gulcehre, Pedro Ortega, DJ Strouse, Joel 7. Leibo, and Nando De Freitas. Social influence as intrinsic motivation for multi-agent deep reinforcement learning. In International Conference on Machine Learning. pages 3040-3044 PMLR, 2019.
[20] Christian Jestel, Harmtmut Surmann, Jonas Stenzel, Oliver Urbann, and Marius Brehler. Ob- taining robust control and navigation policies for multi-robot navigation via deep reinforcement learning. In 2021 7th International Conference on Automation, Robotics and Applications (ICARA), pages 48-54. IEEE, 2021.
[21] Jiechuan Jiang and Zongqing Lu. Learning attentional communication for multi-agent coopera- tion. Advances in neural information processing systems, 31, 2018
[22] Kishor Jothimurugan, Suguman Bansal, Osbert Bastani, and Rajeev Alur. Compositional reinforcement learning from logical specifications. Advances in Neural Information Processing Systems, 34, 2021.
[23] Russell Kaplan, Christopher Sauer, and Alexander Sosa. Beating atari with natural language guided reinforcement learning. arXiv preprint arXiv:1704.05539 2017.
[24] Yunfei Li, Yilin Wu, Huazhe Xu, Xiaolong Wang, and Yi Wu. Solving compositional rein- forcement learning problems via task reduction. In International Conference on Learning Representations, 2020.
[25] Yunchao Liu and Zheng Wu. Learning to describe scenes with programs. In International conference on learning representations, 2019.
[26] Ryan Lowe, Yi Wu, Aviv Tamar, Jean Harb, OpenAl Pieter Abbeel, and Igor Mordatch. Multi-agent actor-critic for mixed cooperaivvecomppttine environments. Advances in neural information processing systems, 30, 2017.
[27] Rajbala Makar, Sridhar Mahadevan, and Mohammad Ghavamzadeh. Hierarchical multi-agent reinforcement learning. In Proceedings of the fifth international conference on Autonomous agents, pages 246-253, 2001.
[28] Shie Mannor, Ishai Menache, Amit Hoze, and Uri Klein. Dynamic abstraction in reinforcement learning via clustering. In Proceedings of the twenty-first international conference on Machine learning, page 71, 2004.
[29] Ofir Nachum, Shixiang (Shane) Gu, Honglak Lee, and Sergey Levine. Data-efficient hierarchical reinforcement learning. Bengio, H. Wallach, Larochelle, K. Grauman, N. Cesa- Bisac,ia and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018
[30] Soroush Nasiriany, Huihan Liu, and Yuke Zhu. Augmenting reinforcement learning with behavior primitives for diverse manipulation tasks. IEEE International Conference on Robotics and Automation (ICRA), 2022.
12

---

[31] Junhyuk Oh, Yijie Guo, Satinder Singh, and Honglak Lee. Self-imitation learning. In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 3878 3887. PMLR, 10-15 Jul 2018.
[32] Junhyuk Oh, Yijie Guo, Satinder Singh, and Honglak Lee. Self-imitation learning. In Interna- tional Conference on Machine Learning, pages 3878-3887. PMLR, 2018.
[33] Afshin Oroojlooyjadid and Davood Hajinezhad. A review of cooperative multi-agent deep reinforcement learning. CoRR, (12111988.099999 2019.
[34] Peng Peng, Ying Wen, Yaodong Yang, Quan Yuan, Zhenkun Tang, Haitao Long, and Jun Wang. Multiagent biddreetionally-ccooinne nets: Emergence of human-level coordination in learning to play starcraft combat games. arXiv preprint arXiv: 1703. 10069, 2017.
[35] Silviu Pitis, Harris Chan, Stephen Zhao, Bradly Stadie, and Jimmy Ba. Maximum entropy gain exploration for long horizon multi-goal reinforcement learning. In International Conference on Machine Learning, pages 7750-7761. PMLR, 2020.
[36] Matthias Plappert, Marcin Andrychowicz, Alex Ray, Bob Megrew, Bowen Baker, Glenn Powell, Jonas Schneider, Josh Tobin, Maciek Chociej, Peter Welinder, al. Multi-goal reinforcement learning: Challenging robotics environments and request for research. 2018. URL https://arxiv. org/pdf/1800 09464. pdf. 2018.
[37] Tabish Rashid, Gregory Farquhar, Bei Peng, and Shimon Whiteson. Weighted qmix: Expanding monotonic value function factorisation for deep multi-agent reinforcement learning. Advances in neural information processing systems, 13:10199-10210, 2020.
[38] Tabish Rashid, Mikayel Samvelyan, Christian Schroeder, Gregory Farquhar, Jakob Foerster, and Shimon Whiteson. Qmix: Monotonic value function factorisation for deep multi-agent reinforcement learning. In International Conference on Machine Learning, pages 4295-4304. PMLR, 2018
[39] Mikayel Samvelyan, Tabish Rashid, Christian Schroeder De Witt, Gregory Farquhar, Nan- tas Nardelli, Tim GJ Rudner, Chia-Man Hung. Philip HS Torr, Jakob Foerster, and Shimon Whiteson. The starcraft multi-agent challenge. arXiv preprint NXX.::1992.004333 2019.
[40] Nikolay Savinov, Alexey Dosovitskiy, and Vladlen Koltun. Semi-parametric topological memory for navigation. In International Conference on Learning Representations, 2018.
[41] Samaneh Hosseini Semnani, Hugh Liu, Michael Everett, Anton De Ruiter, and Jonathan P How. Multi-agent motion planning for dense and dynamic environments via deep reinforcement learning. IEEE Robotics and Automation Letters, 5(2):3221-3226, 2020.
[42] Satinder Singh, Richard L Lewis, Andrew G Barto, and Jonathan Sorg. Intrinsically motivated reinforcement learning: An evolutionary perspective. IEEE Trunsactions on Autonomous Mental Development, 2(2):70-82, 2010.
[43] Martin Stolle and Doina Precup. Symposium on abstraction, reformulation, and approximation, pages 212-223. Springer, 2002.
Learning options in reinforcement learning. In International
[44] Shao-Hua Sun, Hyeonwoo Noh, Sriram Somasundaram, and Joseph Lim. Neural program synthesis from diverse demonstration videos. International Conference on Machine Leurning, pages 4799- PMLR, 2018
[45] Shao-Hua Sun, Te-Lin Wu, and Joseph J Lim. Program guided agent. Conference Learning Representations, 2019.
International
[46] Peter Sunehag, Guy Lever, Audrunas Gruslys, Wojciech Marian Czarnecki, Vinícius Flores Zambaldi, Max Jaderberg, Mare Lanctot, Nicolas Sonnerat, Joel Z Leibo, Karl Tuyls, et al. Value-decomposition networks for cooperative multi-agent learning based on team reward. In AAMAS, 2018.
13

---

[47] Richard S. Sutton and Andrew G. Barto. Reinforcement Learning: An Introduction. The MIT Press, second edition, 2018.
[48] Eugene Vinitsky, Aboudy Kreidieh, Luc Le Flem, Nishant Kheterpal, Kathy Jang, Cathy Wu, Fangyu Wu, Richard Liaw, Eric Liang, and Alexandre M Bayen. Benchmarks for reinforcement learning in mixed-autonomy traffic. In Conference on robot learning, pages 499-409. PMLR, 2018.
[49] Ruosong Wang, Simon S Du, Lin F Yang, and Sham M Kakade. Is long horizon reinforce- ment learning more difficult than short horizon reinforcement learning? arXiv preprint arXiv:2005.00527, 2020.
[50] Sarah A Wu, Rose E Wang, James A Evans, Joshua B Tenenbaum, David C Parkes, and Max Kleiman-Weiner. Too many cooks: Bayesian inference for coordinating multi-agent collaboration. Topics in Cognitive Science, 13(2):414 432, 2021.
[51] Chao Yu, Akash Velu, Eugene Vinitsky, Yu Wang, Alexandre Bayen, and Yi Wu. The surprising effectiveness of ppo in cooperative, multi-agent games. arXiv preprint arXiv:2103.0199 2021.
[52] Zelin Zhao, Karan Samel, Binghong Chen, et al. Proto: Program-guided transformer for program-guidee ggiiddd tasks. Advances in Neural Information Processing Systems, 34, 2021.
[53] Ming Zhou, Jun Luo, Julian Villella, Yaodong Yang, David Rusu, Jiayu Miao, Weinan Zhang, Montgomery Alban, Iman Fadakar, Zheng Chen, al. Smarts: Scalable multi-agent rein- forcement learning training school for autonomous driving. arXiv preprint arXiv:2010.09776. 2020.
[54] Ming Zhou, Jun Luo, Julian Villella, Yaodong Yang. David Rusu, Jiayu Miao, Weinan Zhang, Montgomery Alban, IMAN FADAKAR, Zheng Chen, Chongxi Huang, Ying Wen, Kimia Hassanzadeh, Daniel Graves, Zhenghang Zhu, Yihan Ni, Nhat Nguyen, Mohamed Elsayed, Haitham Ammar, Alexander Cowen-Rivers Sanjeevan Ahilan, Zheng Tian, Daniel Palenicek, Kasra Rezaee, Peyman Yadmellat, Kun Shao, dong chen, Baokuan Zhang, Hongho Zhang, Jianye Hao, Wulong Liu, and Jun Wang. Smarts: An open-source scalable multi-agent rl training school for autonomous driving. Jens Kober, Fabio Ramos, and Claire Tomlin, editors, Proceedings of the 2020 Conference on Robot Learning, volume 155 of Proceedings of Machine Learning Research, pages 264-285 PMLR, 16-18 Nov 2021.
14

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A] Our work focus on designing an algorithm for boosting the performance and generalization
ability, rather than specific real-world application.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full of assumptions all theoretical results? [N/A]
(b) Did you include complete proofs of all theoretical results? [N/A]
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed reproduce the main ex- perimental results (either in the supplemental material or as URL)? [Yes] In the supplementary material
(b) Did you specify all the training details (c.g.. data splits, hyperparameters, how they were chosen)? [Yes] In the suppicmentary material
(c) Did you report error bars (e.g.. with respect the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [Yes] In the supplementary material
4. If you using existing assets (e.g., code, data, models) or curating/releasing
assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes]
(c) Did you include any assets either in the supplemental material URL? [Yes]
(d) Did you discuss whether and how consent obtained from people whose data you're 'rure using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
15


Reviews:
[{"review_id": "hJBx41_JTt9", "reviewer": "Reviewer_KHSD", "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.\n", "questions": "\nMostly stated above the in the weaknesses section:\n\n1. 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.\n\n2. 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.\n\n3. Understanding the number of unfeasible tasks produced would be useful.\n\n4. It is unclear why E-MAPP performs imperfectly in the easy environment. Can the authors add some comments on this. \n\n5. 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.\n\n", "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. \n", "rating": 6, "confidence": 3, "soundness": 1, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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.\n \nMy 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. \n\n1. 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.\n\n2. 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.  \n\n3. 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. \n\n4. 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.\n\n5. 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.\n\n6. 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.  \n\n7. The choice of rewards (0.2 for subtask, 1 for task) provided in the “Average Scores” seem arbitrary. Please provide reasoning for these.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "MGMt1ghKVa", "reviewer": "Reviewer_GMQT", "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.\n", "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.\n", "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.\n", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strengths\n\nThis 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.\n\n## Weaknesses\n\nWhile I very much appreciate the core goal of this paper, I do believe there are a few weaknesses that temper my enthusiasm (described below).\n\n- Many pretrained components\n\nThis 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.\n\n- Efficiency of subtask allocation\n\nThe 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.\n\n- Fully observed and low-dimensional\n\nThe 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.\n\n- Clarity\n\nWhile the paper is quite easy to read from a grammatical standpoint, I found several parts of the paper to be needlessly vague. For instance:\n\n1.  The continuous control experiment is essentially completely unexplained, no results are even mentioned in the main paper and the appendix provides little additional detail.\n2. 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.\n3. 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.\n\n## Line-by-line notes\n\nHere are a few minor line-by-line notes:\n\n- Line 33\n    * \"different feasibility\" sounds odd.\n\n- Line 64\n    * Factorization approaches have also been investigated on the policy side, see e.g. \"A Cordial Sync: Going Beyond Marginal ...\" Jain et al. (ECCV'20)\n \n- Line 65\n    * 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.\n\n- Line 152-153\n    * \"...to a subtask that requires to be...\" -> \"...to a subtask that must be...\"\n \n- Line 155\n    * \"a perceptive query is responded\" -> \"a response to a perceptive query is received\"\n \n- Lines 156-159\n    * Things are quite vague, give an example.\n\n- Lines 181-182\n    * An ablation of this choice would be nice.\n \n- Line 208\n    * \"reducing the binary\" -> \"minimizing the binary\"\n\n- Lines 227-228\n    * Why apply log to feasibility and reachability and not cost-to-go?\n\n- Lines 247-249\n    * 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.\n \n- Line 259\n    * What's the definition of \"novel\" here?\n\n- Line 266\n    * \"accumulative\" -> \"cumulative\"\n \n- Line 292\n    * \"find removing\" -> \"find that removing\"\n\n- Table 3\n    * The error bars for the average scores seem huge?\n \n- Appendix Lines 562-567\n    * Do you also use self-imitation learning with the MAPPO baseline? If not, what is the impact of self-imitation learning alone?\n \n- Appendix Lines 624\n - \"sclae\" -> \"scale\"\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "JmjhIdXayWV", "reviewer": "Reviewer_uuPM", "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.", "questions": "Described in Strengths And Weaknesses section.", "limitations": "Described in Strengths And Weaknesses section.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Paper strengths and contributions\n**Motivation and intuition**\nI 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.\n\n**Novelty**\nTo the best of my knowledge, this is the first work researching following program instructions with multiple agents.\n\n**Technical contribution**\n- The DSL used in this work seems like a reasonably good DSL for describing the overcooked domains.\n- The proposed task allocator learning reachability, feasibility, and cost-to-go seems effective.\n\n**Clarity**\nThe overall writing is clear.\n\n**Ablation study**\nAblation studies are helpful for understanding thecontributionsn of each component (i.e. reachability, feasibility, and cost-to-go) of learning to allocate tasks.\n\n**Experimental results**\nThe 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.\n\n## Paper weaknesses and questions\n\n**Fully observability**\nWhile 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.\n\n**Task example**\nThere 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?\n\n**How to obtain tasks/programs**\nThis 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.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept