Asynchronous Multi-Agent Actor-Critic with Macro-Actions
Authors: Yuchen Xiao
Weihao Tan
Christopher Amato
Venue: ICLR 2022 Submitted (2022)

Abstract: Many realistic multi-agent problems naturally require agents to be capable of performing asynchronously without waiting for other agents to terminate (e.g., multi-robot domains). Such problems can be modeled as Macro-Action Decentralized Partially Observable Markov Decision Processes (MacDec-POMDPs). Current policy gradient methods are not applicable to the asynchronous actions in MacDec-POMDPs, as these methods assume that agents synchronously reason about action selection at every time-step. To allow asynchronous learning and decision-making, we formulate a set of asynchronous multi-agent actor-critic methods that allow agents to directly optimize asynchronous (macro-action-based) policies in three standard training paradigms: decentralized learning, centralized learning, and centralized training for decentralized execution. Empirical results in various domains show high-quality solutions can be learned for large domains when using our methods.

Under review as a conference paper at ICLR 2022
ASYNCHRONOUS MULTI-AGENT ACTOR-CRITIC WITH MACRO-ACTIONS
Anonymous authors Paper under double-blind review
ABSTRACT
Many realistic multi-agent problems naturally require agents to be capable of per- forming asynchronously without waiting for other agents to terminate (e.g., multi- robot domains). Such problems can be modeled Macro-Action Decentralized Partially Observable Markov Decision Processes policy gradient methods are not applicable agents' asynchronous decision- making over macor-actions in MaueDec-POMDDR as these methods assume that agents synchronously reason about action selection at every timestep. To al- low asynchronous learning and decision-making, we formulate a set of asyn- chronous multi-agent actor-critic methods that allow agents to directly optimize asynchronous imacro-action-basedd policies in three standard training paradigms: decentralized learning, centralized learning, and centralized training for decentral- ized execution. Empirical results in various domains show high-quality solutions can be learned for large domains when using our methods.
Current
INTRODUCTION
In recent years, multi-agent policy gradient methods using the actor-critic framework have achieved impressive success in solving a variety of cooperative and competitive domains (Lowe et al. 2017
Foerster et al. 2018 Du et 2019 Iabal Sha 2019 Vinyals et al. 2019 et 2019
Wang
et al. 2020 Yang et al. 2020 Zhou et al. 2020 Baker et al. 2220 Su et al. [021] Wang et al. 2021
Du al. 20221. However, as these methods assume synchronized primitive-action execution over agents, they struggle to solve tasks that involve long-term reasoning and asynchronous behavior, such as real-world multi-robot applications (e.g., search and rescue (Queralta et al. 2020), package
delivery (Choudhury et al.) 2021) and warchouse service (Xiao et al. (0220).
The Macro-Action Decentralized Partially Observable Markov Decision Process (MacDec- POMDP) (Amato et al. 2014 2019) provides general formalism for multi-agent asynchronous under uncertainty. Macro-actions represent temporally extended ac-
collaborative decision-malee tions that have (potentially) different durations. This introduces asynchronous high-level decision- making over agents, as agents can start and terminate macro-actions at different timesteps. Such asynchronicity actually makes multi-agent reinforcement learning (MARL) more challenging be- cause it is difficult to determine what information to use and when to update agents' policies from either the decentralized or centralized perspective.
Despite several efforts made recently to enable agents to learn asynchronous hierarchical policies such extending DQN (Mnih al. 2015) to learn macro-action-value functions (Xiao al. al. 2019). transferring MacDec-POMDI to event-driven processes with continuous timing (Menda et al.) 2019) and adapting a single-agent option-critic framework (Bacon al. (017) to multi multi-agent do- mains to learn all components (e.g. low-level policy, high-level abstraction, high-level policy) from scratch (Chakravorty et al., 2019), none of them provides principled way for optimizing macro- action-based policies via asynchronous policy gradients to solve general multi-agent problems with asynchronous making...
In this paper, propose group of macro-action-barl multi-agent actor-critic methods to general- ize the current primitive-action based multi-agen actor-critic methods to multi-agent problems with macro-actions well as allowing asynchronous policy optimization. First, we formulate macro- aation-based independent actor-critic (Mac-IAC) method. Although independent learning suffers from theoretical curse of environmental non-stationarity, allows fully online learning and may

---

Under review as a conference paper at ICLR 2022
still work well in certain domains. Second, we introduce a macro-action-basee centralized actor- critic (Mac-CAC) method, for the case where full communication is available during execution. We also formulate centralized training for decentralized execution (CTDE) paradigm (Kraemer & Banerjee| 2016 Oliehoek et al.] 2008) variant of our method. CTDE has gained popularity since such methods learn better decentralized policies by using centralized information during train- ing. Current primitie--cttonn-- based multi-agent actor-critic methods typically use a centralized critic to optimize each decentralized actor. However, the asynchronous joint macro-action execution from the centralized perspective could be very different with the completion time being very different from each agent's decentralized perspective. To this end, we first present a Naive Independent Actor function
with Centralized Critic (Naive IACC) method that naively uses joint macro-action-Ne as the critic for each actor's 's policy gradient estimation; and then propose an Independent Actor with Individual Centralized Critic (Mac-IAICC) method addressing the above challenge.
We evaluate our proposed methods on diverse macro-action-bass multi-agent problems: a bench- mark Box Pushing domain (Xiao et al. 2019), a variant of the Overcooked domain (Wu et al.] 2021) and larger warehouse service domain [iioo et al. 2019). Experimental results show that our meth- ods are able to learn high-quality solutions while primitive-action bbsed methods cannot, and show the strength of MaC-IAICC for learning decentralized policies over Naive IAICC and Mac-IAC. To our knowledge, this is the first general formalization of macro-action-baal multi-agent actor-critic frameworks considering the three state-of-the-art multi-agent training paradigms.
2 BACKGROUND
This section first introduces the formal definitions of the Dec-POMDP and the MacDec-POMPl and then reviews single-agent and multi-agent actor-critic policy gradient methods with primitive- actions. We also provide overview of basee MARL methods with macro-actions.
2.1 DEC-POMDPS AND MACDEC-POMDEI
The decentralized partially observable Markov decision processes (Dec-POMDP) (Oliehoek & Am- ato 2016) is a general framework to model fully cooperative multi-agent tasks, where agents make decisions in decentralized way based only local information. Formally, Dec-POMDP is de- fined by a tuple S, A, T, O, R, 7), where 7 is a set of agents; S is the environmental state space; A Xier A; is the joint primitive-action space over each agent's primitive-action set A₁; Ω = X2 is the joint primitive-observation space over each agent's 's primitive-observan
set Ω4 At every timestep, under a state s, agents synchronously execute a joint primitive-action ă Xie each individually selected by an agent using a policy æ; H x A, - [0, 1], mapping from local primitive observation-action history H.A to primitive-actions. The environment then transits to a new state s' according reward r(s, a') issued by a reward function R: : S 5 - RR and obtain a joint primitive-observatio o- Xigro; drawn from an observation function O ã, s') = P(ō ā, s') in state s'. The objective is to find joint policy मे = X; such that the expected sum of discounted rewards from an initial
state transition function T(s, c, 8¹)
P(s' | 8, s, Agents receive global
state, (s(o)) = E Σ ('r(st)), a (soo 7 gets optimized, where y E [0, 1] is a discount factor, and H is the number of (primitive) timesteps until the problem terminates (the horizon).
The macro-action decentralized partially observable Markov decision process (MacDec- POMDP) (Amato et al.) 2014 2019) incorporates the option framework (Sutton al. 1999) into the Dec-POMDP by defining each agent's 's macro-action as a tuple m, = (Im, Tm, : Bm,)) where
the initiation set Lm, C 11.39 defines how to initiate a macro-action based on macro-observation-
action history Hdddd at the high-level; Tm; H,A x A; - [0, is the low-level policy for the exccution of macro-action; and a stochastic termination function Bm, HH - [0, 1] determines how to terminate macro-action based on A MacDec-POMDE is thus formally defined by a tuple (1, S, A, M, 2, Ç, T, O, Z, R, HI, 7)), where S, A, S2 T, O, R, IiI and remain the same definitions as in the Dec-POMDP; M = XierM, is the joint macro-action space over each agent's 's macro- macro-action space Mú; Ç = Xserς, is the joint macro- observation space over each agent's 's maacro-observatie
history H.A at the low-level.
space Ç;: and 2 [Z,) is set of macro- observation likelihood models. During execution, each agent independently selects a macro-action my using high-level policy V. H.M x Mc [0, 1), a mapping from macro-ohservation-aciii his-
2

---

Under review as a conference paper at ICLR 2022
Ç, according to the macro-obsert macro-observation probability function (2, m,, s') = P(z m, s') when the macro-action terminates in a state s'. The objective of solving MlaeeecPOMMDD
tory macro-actions, and captures a macro-observation
with finite horizon is to find joint high-level policy T = XiEx V, that maximizes the value, / (s(0)) = E Ei= >'r (5)()))) 8(0) म.
2.2 SINGLE-AGENT ACTOR-CRITIC
In single-agent reinforcement learning, the policy gradient theorem (Sutton et al. 2000) formulates a principled way optimize parameterized policy me via gradient ascent the policy's performance defined as J(e) E [i== ('r(s(()) ((e))]- In POMDPs, the gradient w.r.t. parameters a observation-action history- saaory policy To(a ( h) is expressed as:
VoJ(0)= Emo Ve log Te(a (
where, h is often maintained by having RNN in the policy network (Hausknecht & Stone 2015).
The actor-critic framework (Konda & Tsitsiklis 2000) learns an on-policy action-value function Q*a (h, a) (critic) via temporal-difference (TD) learning (Sutton 1988) to approximate the action- value for the policy (actor) updates. Variance reduction is commonly achieved by training a history- value function V (h) and using it as a baseline (Weaver & Tao 2001) as well as bootstrapping to estimate the action-value. Accordingly, the actor-critic policy gradient can be written as:
(+) = E V log (a h)(r VV (h') VW (h))
(2)
where, is the immediate reward received by the agent at the corresponding timestep.
2.3 INDEPENDENT ACTOR-CRITIC
The single-agent actor-critic algorithm can be adapted to multi-agent problems in simple way such that each agent independently learns its own actor and critic while treating other agents as part of the world (Foerster et al. 2018). We consider a variance reduction version of independent actor-critic (IAC) with the policy gradient as follows:
Vo. Ex, Vo, log ne, (a; hr)(r + VW. (h.) VW! (ha))
(3)
where, r is a shared reward over agents at every timestep. Due to other agents' policy updating and exploring, from any agent's local perspective, the environment appears non-stationary which can lead to unstable learning of the critic without convergence guarantees (Lowe et al. 2017). This
instability often prevents IAC from learning high-quality cooperative policies.
2.4 INDEPENDENT ACTOR WITH CENTRALIZED CRITIC
To address the above difficulties existing in independent learning approaches, centralized training for decentralized execution (CTDE) provides agents with access to global information during offline training while allowing agents to rely only local information during online decentralized execu- tion. Typically, the key idea of exploiting CTDE with actor-critic is to train a joint valuee function, Q (x, d), as the centralized critic and each decentralized policy (Foerster al. 2018 Lowe al. 2017). which can be formulated as:
compute gradients w.r.t. the parameters of
Va, (0,)) = Ex, Ve, log (a: 1.) (x, a))
(4)
where, x represents the available centralized information (c.g., joint observation, joint observation- action history, or the true state). Although the centralized critic in Eq. 4 can facilitate the update of decentralized policies in the direction that optimizes global collaborative performance, it also introduces extra variance over other agents' actions (Lyu et al., [2021] Wang et al., (2021). Therefore, we consider the version of independent actor with centralized critic (IACC) with a general variance reduction trick (Foerster et al. 2018 Su et al. 2021), the policy gradient of which is:
Vo, [Os)) = Ex, Vo. log To, (a: (r) + +el1++VVVVVV V V (x((xx)
(5)
3

---

Under review as a conference paper at ICLR 2022
2.5 LEARNING MACRO-ACTION-BASSE DEEP Q-NETS
An essential aspect of macro-action-based multi-agent systems is the asynchronicity of macro-action execution over agents, where agents may start and complete their own macro-actions at different timesteps. Previous deep MARL methods for Dec-POMDPs cannot work in this case as they are all based on primitive actions synchronously executed by agents. In recent work, macro-action-bas multi-agent deep Q-learning methods have been proposed for MacDec-POMDDN (Xiao et al. 2019).
For decentralized learning, a new buffer, Macro-Action Concurrent Experience Reply Trajectories (Mac-CERT', is designed for collecting each agent's macro-observation, macro-action, and re- ward information. this buffer, the transition experience of each agent is represented as a tuple
(zi, my 24, rf), where r Eim +mm,+Tmm=1 7 7(=) is cumulative reward of the macro-action tak- ing Tm, timesteps to be completed from its beginning timestep 4m.- During training, mini-batch of concurrent sequential experiences sampled from Mac-CERTs. Each agent independently accesses its own sampled experiences and obtains a 'squeezed' trajectories by removing the transitions in the middle of each macro-action execution, which ends up with a mini-batch transitions when the corresponding macro-action terminates (i.e., removing time information). Updates for each macro- action-value function Qø (hs, m;) take place only when the agent's 's macro-action is complete by minimizing a TD loss over the 'squeezed' data. In the centralized learning case, the objective is to learn a joint macro- macro-action-ve vaction-valuee function Q² m). To this end, the other special buffer called Macro-Action Joint Experience Replay Trajectories (Mac-JERTs) is developed for collecting agents' joint transition experience at every timestep and each is represented as tuple (E, m, s", F²), where Satta -1 -f ry is a shared joint cumulative reward from the beginning timestep t. of the joint macro-action m to its termination, defined as when any agent finishes its own macro-action, after Fm timesteps. In each training iteration, the joint macro-action-value function is optimized over mini- batch of 'squeezed' (depending on each joint macro- action termination) sequential joint experiences via TD learning. Other choices for what information to retain are also possible (e.g.. the whole sequence of macro-actions or including time to complete) but this squeezing procedure was found to work well.
F" = Lt=fm
In our proposed macro-action- actor-critic methods, we extend the above approaches to train critics on-policy, and the trajectory squcezing is changed variously for each method in order to achieve improved asynchronous macro-action-bast policy updates via policy gradient.
3 APPROACH
Multi-agent deep reinforcement learning with asynchronous decision-making and macro-actions is more challenging as it is difficult to determine when to update each agent's policy and whar in- formation to use. Although the macro-action-basee deep Q-learning methods (Xiao et al.] 2019) (in Section 2.5) give us the base learn macro-action value functions, they do not directly extend to the policy gradient case, particularly in the case of centralized training for decentralized execu- tion (CTDE). In this section, we propose principled formulations of on-policy mucro-action-basee multi-agent actor-critic methods for decentralized learning (Section 3.1). centralized learning (Sec- tion 3.2). and CTDE (Section 3.3). In each case, we first introduce the version with a Q-value function as the critic and then present the variance reduction version in our implementation. We use h; to represent an agent's 's local macro-observation.ccom action history, and h to represent the joint history.
3.1 MACRO-ACTION-A
INDEPENDENT ACTOR-CRITIC (MAC-IAC)
Similar to the idea of IAC with primitive-action (Section 2.3 a straightforward extension is to have each agent independently optimize its own macro-action-basel policy (actor) using local macro- action-value function (critic). Hence, we start with deriving a mnacr-aaction-bate theorem in Appendix A. by incorporating the general Bellman equation for the state values of macro-action-based policy (Sutton et al. 1999) into the policy gradient theorem in MDPs (Sutton ct al., 2000), and then extend to MacDec- MacDec-POMDPs so that each agent can have the following policy gradient w.r.t. the parameters of its macro macro-action-
policy gradient
policy Vo, (hs as:
J(,.) = =E Vo, log (m, 1x)
Wo, (h2, m.)
(6)
4

---

Under review as a conference paper at ICLR 2022
During training, each agent accesses to its own trajectories and squeezes them in the same way as the decentralized case mentioned in Section 2.5 to train the critic Q3 (hs m²) via on-policy TD learning and perform gradient ascent using 6 update the policy when the agent's macro-action terminates. In our case, we train local history value function Vw. v= (h;) as each agent's critic and use as a baseline to achieve variance reduction. The corresponding policy gradient is as follows:
Vo = B Va, log Vo, (m44 hr) + 7 Vw. We, (M.) Vwl (hi))
where, the cumulative reward rf is w.r.t. the execution of agent i's macro-action my,
3.2 MACRO-ACTION- BASED CENTRALIZED ACTOR- ACTOR-CRITIC (MAC-CAC)
In the fully centralized learning case, treat all agents single joint agent to learn centralized actor (m h) with centralized critic Q (h, m), and the policy gradient can be expressed as:
VoJ = Ev, Vo log v (
h) 1)
" (h, m)
(8)
Similarly, in order to achieve low variance optimization for the actor, we learn a centralized history value function V (h) by minimizing a TD--rrrrr loss over joint trajectories that are squeezed w.rt. each joint macro-action termination (as long one of the agents terminates its macro-action, intro- duced under the centralized case in Section 2.5). Accordingly, the policy's updates are performed when each joint macro-action completed by ascending the following gradient:
VnJ(0)= EEv, Volog (o(m (F + Fmm V. (T') V (7))
where the cumulative reward Fr is w.r.t. the execution of the joint macro-action m.
3.3 MACRO-ACTION-BAAE BASED INDEPENDENT ACTOR WITH CENTRALIZED CRITIC (MAC-IACC)
mentioned earlier, fully centralized learning requires perfect online communication that is often hard to guarantee, and fully decentralized learning suffers from environmental non-stationarity due to agents' changing policies. order to learn better decentralized macro-action-ben policies, in this section, propose two macro-actions basodd actor-critic algorithms using the CTDE paradigm. Typically, the difference between a joint macro-action and macro-action's termination from each agent's 's local perspective gives rise what kind of centralized critic to learn and how to use it to optimize decentralized policies under such osymmetric asynchrony from the two perspectives, which mainly investigate below.
termination from the centralized perspective
challenge:
3.3. NAIVE MAC-IACC
A naive way of incorporating macro-actions into a CTDE-based actor-critic framework is directly adapt the idea of the primitive-action- IACC (Section 2.4) to have a shared joint macro-action- value function %¹²² (x, m) in each agent's decentralized incro-action-basee policy gradient as:
Ve. = E5 Ve, log Ve, (m; h2 5 (x, m)
(10)
To reduce variance, with value function V "xx) as the centralized critic, the policy gradient w.r.t. the parameters of each agent's high-level policy can be rewritten as the following format:
Wo (x))
((.)) = E3g Vo, log (m: h+)(F" + Fm (x') -
(11)
Here, the critic is trained in the fully centralized manner described in Section 3.2 while allowing it to access additional global information (e.g.. joint macro-observation-tt state both) represented by the symbol x. However, updates of each agent's policy Vo (m, h,) only occur at the agent's own macro-action termination timesteps rather than depending on joint macro-action terminations in the centralized critic training.
history, ground truth
5

---

Under review as a conference paper at ICLR 2022
3.3.2 INDEPENDENT ACTOR WITH INDIVIDUAL CENTRALIZED CRITIC (MAC-IAICC)
Note that naive Mac-IACC is technically incorrect. The cumulative reward F in Eq is based on the corresponding joint macro-action's 's termination that is defined as when any agent finishes its
own macro-action, which produces two potential issues: a) F + Fm 7 V (x') may not estimate the value the macro-action m. well as the reward does not depend on m, 's termination; b) from agent i's perspective, its policy gradient estimation may involve higher variance associated with the asynchronous macro-action terminations of other agents.
To tackle aforementioned issues, we propose to learn a separate centralized critic Vw. (x') for each
agent via TD-learning. In this case, each TD-error for updating Vw. (x') is computed by using the reward rf that accumulated purely based on the execution of the agent i's macro-action m,. With this TD-error estimation, each agent's decentralized macro-action cetroo-actoon-baseeeeee based policy gradient becomes:
Vo. Es Vo, log Vo, (m+ ha) (ri + 7 Vw. (x))
Vw! (x))
(12)
Now, from agent i's perspective, rf 7 Vw, (x') capable of offering more accurate value " prediction for the macro-action m,, since both the reward, rf and the value function Vw:" (x') depend agent i's macro-action termination. Also, unlike the case in Naive Mac-IACC, other agents' terminations cannot lead to extra noisy estimated rewards w.r.t. my anymore so that the variance on policy gradient estimation gets reduced. Then, updates for both the critic and the actor occur when the corresponding agent's 's macro-action ends as well as taking the ad advantage of information sharing.
The pseudo code and detailed trajectory squeezing process for each proposed method are presented in Appendix A.2
4
EXPERIMENTS
4.1 ENVIRONMENTS
We investigate the performance of proposed algorithms variety of multi-agent problems with macro-actions (Fig. [T: Box Pushing (Xiao et al. 2019). Overcooked (Wu et al. (021), and larger Warehouse Tool Delivery (Xiao al.) 2019) domain. Macro-actions in domains are defined by us using prior domain knowledge as they are straightforward in these tasks. We describe the key properties each domain here and leave more details in Appendix A.3
(a) Box Pushing
(b) Overcooked-A
(c) Overcooked-B
(d) Overcooked-C
(c) Warchouse-A
(f) Warehouse-B
(g) Warchouse-C
Figure 1: Experimental environments.
Box Pushing (Fig. [a). Two agents aim to cooperatively push the big box to the yellow goal area rather than pushing a small box on each own. Boxes can only be moved towards the north. Agents have four primitive-actions move forward, turn-left, turn-right and stay. In the macro-action-bass case, each agent has three one-step macro-actions: Turn-left, Turn-right, and Stay, as well as three multi-step macro-actions. Move-to-small-baxxe red spot below the corresponding box and terminate with agent facing the box; Push operates the agent to keep moving forward until arriving the world's boundary, touching the big box along or pushing small box to the goal. Each agent can only capture the status (emply, teammate, boundary,
and Move-to-big-boxtf navigate the agent to the

---

Under review as a conference paper at ICLR 2022
small or big box) of the cell in front of it as macrooobservvttin. When any box is pushed to the goal, the team receives a terminal reward (+300 for the big box and +20 for each small box). A penalty -00 is issued when any agent hits the boundary pushes the big box on its own.
Overcooked (Fig. DD-d). Two agents must learn to co- operatively prepare lettuce-tomato salad and deliver it to the 'star' cell as soon as possible. The challenge is that the recipe of making a lettuce-tomato salad (Fig. ( is unknown to agents. Agents have to learn the correct procedure in terms of picking up raw vegetables, chop- Figure 2: Lettuce-tomato salad recipe.
ping, and merging in a plate before delivering. With primitive-actions (up, down, left, right, and stay); agents can move around and achieve picking, placing, chopping and delivering by moving against the corresponding cell. The macro-action set consists of: a) five one-step macro-actions that are same as the primitive ones; b) Chop, takes three timesteps to cut a raw vegetable into pieces; c) long-term navigation macro-actions: Get-Lettuce, Get-Tomato, Get-Plate-112, Sio-Cut-Board-ll and Deliver, which move an agent to the location of the corresponding object with various possible terminal effects (e.g.. holding a vegetable in hand or placing chopped vegetable in plate); d) Go- Counter, navigates an agent to one of the middle counter cells as well as placing or picking an object there. Full details of macro-actions are listed in Appendix A.3.2] Agents only observe the positions and status of the entities within a 5 x egocentric view field. Reward mechanism involves: +0 for chopping a vegetable into pieces, +-200 terminal reward for delivering a lettuce-tomato salad, -5 for delivering any wrong entity that is then reset to the original position, and -0.1 for every timestep.
Warehouse Tool Delivery (Fig. D In each workshop (e.g., W-0), human is working on an assembly task (involving 4 sub-tasks that each takes a number of timesteps to be finished) and requires three particular tools for future sub-tasks to continue. A arm robot (grey) with the duty of finding tools for each human on the table (brown) and passing them to mobile robots (green, blue and yellow) who are responsible for delivering tools to humans. Note that, the correct tools needed by each human are unknown to robots, which has to be learned during training in order to perform timely delivery without letting humans wait there. We make the original problem more challenging by: adding one more human into the domain (Fig.D>) increasing the number of both agents and humans to further examine the scalability of our methods and the effectiveness of Mac-IAICC on handling more intricate asynchronous terminations over agents (Fig. ID: and including one faster human (orange) to check if agents can learn a priority for assisting him (Fig. TT.).
Mobile robots move around in certain speed in the continuous space by running one of the fol- lowing macro-actions: Go- W(i,, moves to the waypoint (red) at a workshop; Go-TR, goes to the waypoint at the right side of the tool room; and Get-Tool, navigates besides the arm robot and waits there until either receiving a tool or 10 timesteps have passed. Ap- plicable macro-actions for the arm robot involves: Search-Tool() lasts 6 timesteps find the tool i and place it in staging area (containing at most two tools), otherwise freezes the robot for the same amount of time when the area is fully occupied; Pass-to-M(i) costs timesteps to pass a tool to mobile robot from the staging area in a first-in-frst-ou order; and Wait-M, takes timestep to wait for mobile robots. Arm robot only observes the lype of each tool in the staging area and which mobile robot is waiting beside. Mobile robot always detects its position and the type of each tool carried by itself, while observes the number of tools in the staging area or the sub-task a human is working on only when locating at the tool room the workshop respectively. The team receives: + +10 for sending a correct tool to a human in time, -20 for a delayed delivery, - 10 for the arm robot running Pass-to-M(i) without mobile robot i being next it, and -1 every timestep.
pre-allocated waypoint
4.2 EXPERIMENTAL IMPLEMENTATION
All methods apply the same neural network architecture for both actor and critic, which consists of two fully connected (FC) layers with Leaky-Relu activation function, one GRU layer (Cho et al.) 2014) and one more FC layer followed by an output layer. In all methods, decentralized actors and decentralized critics have 32 units on FC and GRU layers, while the centralized have 64 units on the GRU layer due to dealing with larger joint macro- observvbbervttoon and macro- spaces. Exploration is deployed by applying linear decaying e-soft policy (Foerster et al. 2018). Hyper- ing uses grid search over a wide range of candidates (refer to Appendix A.5). The performance met- ric of one training trial is mean discounted return measured by periodically (every 100 episodes)
tun-
7

---

Under review as a conference paper at ICLR 2022
Mac-IAC
IAC
Mac-CAC
CAC
Benchmark Policy
Box Pushing
Box Pushing 10x10
Box Pushing 12x12
Mean Test Return
250
200
100
50
50
0K
10K
20K
30K
40K
0K
10K
20K
30K
40x
0K
10K
20K
30%
40K
Episode
Episode
Episode
Overcooked-A
Overcooked-B
Overcooked-C
175
175
175
Mean Return
1.40
140
1.40
105
1O5
105
70
70
70-
35
Mean
35
35
0K
50K
100K
0K
50%
100K
50K
100K
Episode
Episode
Episode
Figure 3: Decentralized learning and centralized learning with macro-actions primitive-actions.
evaluating the learned policies over 10 testing episodes. We plot the averaged performance of each method over 20 independent trials with one standard error and smooth the curves over 10 neighbors. The return of a benchmark policy created by using prior domain knowledge is also involved.
5 RESULTS AND DISCUSSIONS
Advantages of learning with macro-actions. We first present a comparison of our macro-action- based actor-critic methods against the primitive-action-bee based in fully decentralized and fully cen- tralized cases. We consider various grid world sizes of Box Pushing domain (top in Fig, 3 where the benchmark policy's 's return is the optima) and three Overcooked scenarios (bottom row in Fig. 3). The results show the significant outperformance of using macro-actions over primitive- actions. More concretely, in Box Pushing domain, reasoning about primitive movements at every timestep with such a limited observation setup makes this problem intractable agents so that they cannot learn any good behaviors other than to keep moving around. The necessary cooperation in this task is not required in the low-level navigation but at the high-level (c.g.. go to the big box and push) so that, with the macro-actions, Mac-CAC reaches near-optimal performance enabling agents to push the big box together. Unlike the centralized critic conditioning on joint information, even in the macro-action case, it is hard for each agent's ' decentralized critic to correctly measure the re- sponsibility for a penalty caused by teammate pushing the big box alone. Mac-IAC thus converges to local-optima of pushing two small boxes in order to avoid getting the penalty.
In Overcooked domain, an efficient solution requires agents to asynchronously work on independent subtasks (e.g., one agent goes to get plate while the other agent chops vegetables), which explains why Mac-IAC can solve the task well in cases, A and B. This also indicates that using local infor- mation is enough for agents achieve high-quality behaviors. As a result, Mac-CAC learns slower since it must figure out the redundant part of joint information in the larger joint macro-level history and action spaces and it sometimes leads to a local optimum. However, in case C, the challenge from the decentralized perspective is that agents cannot observe the status of the left side due to the limited view, and there is no immediate reward caused by the agent's action at the right side. The benefit of centralized learning emerges in this case so that Mac-CAC outperforms Mac-IAC. The methods begin to learn, but perform poorly in such long- bong-horizon tasks.
primitive-action-eee
Advantages of having individual centralized critics. Fig. 4 shows the evaluations of our macro- action-bass based multi-agent actor-critic methods in all three domains, where we mainly investigate the superiority of Mac-IAICC over Naive Mac-IACC on learning decentralized policies. As each agent's s observation is extremely limited in Box Pushing, we allow centralized critics in both Mac-IAICC and Naive Mac-IACC to access to the state (agents' poses and boxes" positions), but joint macro- observation-acee history in another two domains. In the Box Pushing task (Fig. Is top row), MacCIAICC and Naive Mac-IACC both show the quality of decentralized policies. However, with the growing grid world size, Naive Mac-IACC loses its value while Mac-IAICC keeps its perfor- mance the centralized one. This is because, from each agent's perspective, the bigger the world
8

---

Under review as a conference paper at ICLR 2022
Mac-IAICC
Naive Mac-IACC
Moc-CAC
Mac-IAC
Benchmark Palicy
Box Pushing BxB
Pushing 10x10
Box Pushing 12x12
Mean Test Return
Return
200
150
150
250
100
100
100
50
50
50-
0K
10K
20K
30K
40K
0K
10K
20K
50K
40x
0K
10K
20K
30K
40K
Episode
Episode
Episode
Overcooked-A
Overcooked-B
Overcooked-C
175
175
175
Mean Return
1.40
140
1.40
105
105
105
70
70-
70-
35
35
Mean
35
0K
50K
100K
0K
50K
100K
0K
50K
100K
Episode
Episode
Episode
600
Warehouse-A
800
Werehouse-8 B
800
Warehouse-C
Meen Return
Moo Return
600
600
400
400
150
200
200
-150
-200
-200
0K
20k
30K
40K
30K
60K
90K
30K
60K
90K
Episode
Episode
Episode
Figure 4: Comparison of asynchronous macro-action- actor-critic methods.
size is. the more timesteps a macro-action could take, and the less accurate value estimation the critic of Naive IAC- offers as it trained depending on any agent's macro-action termination. Con- versely, Mac-IAICC gives each agent a separate centralized critic trained with the reward associated with its own macro-action execution. In Overcooked-A and B (Fig. Is s mid row), as Mac-IAICC'S performance is determined by the training of two agents' critics, it learns slower than Naive Mac- IACC in the early stage but both converge to the same value in the end; and in the scenario C, better decentralized policies in Overcooked-C -CC, macro-ase aatronnccionn terminations from both centralized and decentralized perspectives become more frequent than that in A and B, which slows Naive Mac-IACC's learning but does hurt the sample efficiency of Mac-IAICC. Finally, in the large warehouse domain (Fig. last row), Mac-IAC performs the worst due to its natural limitations and the domain's 's partial observability. In particular, it is difficult for the gray robot to learn an efficient way to find correct tools purely based on local information and very delayed rewards depending on the mobile robots' behaviors. By leveraging joint information, Mac-IAICC performs the best over all three cases. Furthermore, Mac-IAICC's advantage over Naive Mac-IACC is more significant in the case B than in the case A where it converges to higher value with much lower variance. This result confirms Mac-IAICC's scalability and effectiveness on handling more complex asynchronous executions when more agents involved. As the difficulty for Mac-CAC discussed earlier in Overcooked, Mac-CAC also gets stuck at a local-optimum in Warchouse-A and B, and converges slightly slower than Mac-IAICC in the case C. Visualization of learned policies using Mac-IAICC are displayed in Appendix A.4
learned by the two CTDE-based methods. Because of the middle block
CONCLUSION
This paper introduces the first general formulation for asynchronous multi-agent macro-action- based policy gradients under partial observability along with proposing a decentralized actor-critic method (Mac-IAC), centralized actor-critic method (Mac-CAC), and two CTDE-based actor-critic meth- ods (Naive Mac-IACC and Mac-IAICC). Empirically, our methods are able to learn high-quality macro-action-basse policies allowing agents to perform asynchronous collaborations in large and long-horizon problems. Importantly in Mac-IAICC, the strength of allowing each agent to have an individual centralized critic associated with its own macro-acion executions clearly improves per- formance in many of the domains. This work provides a foundation for future macro-action-ben based MARL algorithm development, including other work on asynchronous execution as well as methods which also learn the macro-actions.

---

Under review as a conference paper at ICLR 2022
REFERENCES
Christopher Amato, George D. Konidaris, and Leslie P. Kaelbling. Planning with macro-actions in decentralized POMDPs. In Proceedings of the International Conference on Autonomous Agents and Multiagent Systems, 2014.
Christopher Amato, George Konidaris, Leslie Pack Kaelbling, and Jonathan P. How. Modeling and planning with macro-actions in decentralized pomdps. Journal of Artificial Intelligence Research, 64:817-859, 2019.
Pierre-Lue Bacon, Jean Harb, and OPTdoina Precup. of the AAAI Conference Artificial Intelligence, pp. 1726-1736 2017.
The option-critic architecture. In Proceedings
Bowen Baker, Ingmar Kanitscheider, Todor Markov. Yi Wu, Glenn Powell, Bob McGrew, and Igor Mordatch. Emergent tool use from multi-agent autocurricula. In Proceedings of the International Conference on Learning Representations, 2020.
Jhelum Chakravorty, Patrick Nadeem Ward, Julien Roy, Maxime Chevalier-Boisverr, Sumana Basu, Andrei Lupu, and Doina Precup. Option-critic in cooperative multi-agent systems, arXiv preprint, arXiv:1911.1282. 2019.
Kyunghyun Cho, Bart van Merrienboer, Çaglar Gülçehre, Dzmitry Bahdanau, Fethi Bougares, Holger Schwenk, and Yoshua Bengio. Learning phrase representations using RNN encoder- decoder for statistical machine translation. In Empirical Methods in Natural Language Processing EMNLP, pp. 1724-1734, 2014.
Shushman Choudhury, Kiril Solovey, Mykel J. Kochenderfer, and Marco Pavone. Efficient large- scale multi-drone delivery using transit networks. Journal of Artificial Intelligence Research, 70: 757-788, 2021.
Yali Du, Lei Han, Meng Fang, Tianhong Dai, Ji Liu, and Dacheng Tao. Lir: Learning individual intrinsic reward in multi-agent reinforcement learning. In Proceedings of the Conference on Neural Information Processing Systems, 2019.
Yali Du, Bo Liu, Vincent Moens, Ziqi Liu, Zhicheng Ren, Jun Wang, Xu Chen, and Haifeng Zhang- Learning correlated communication topology in multi-agent reinforcement learning. In Proceed- ings of the International Conference on Autonomous Agents and Multiagent Systems, pp. 456 464, 2021.
Jakob Foerster, Gregory Farquhar, Triantafyllos Afouras, Nantas Nardelli, and Shimon Whiteson. Counterfactual multi-agent policy gradients. In Proceedings of the AAAI Conference Artificial Intelligence, February 2018
Matthew Hausknecht and Peter Stone. Deep recurrent Q-learning for partially observable mdps. In AAAI Fall Symposium on Sequential Decision Making for Intelligent Agents (AAAI-SDMIA15), 2015.
Shariq Iqbal and Fei Sha. Actor-attention-ccitte for multi-agent reinforcement learning. In Proceed- ings of the International Conference on Machine Learning, volume 97, pp. 2961-2970, 2019.
Vijay R Konda and John N Tsitsiklis. Actor-critic algorithms. In Proceedings of the Conference Neural Information Processing Systems, pp. 1008-1014, 2000.
Landon Kraemer and Bikramjit Banerjee. Multi-agent reinforcement learning a rehearsal for decentralized planning. Neurocomputing, 190:82-94, 2016.
Shihui Li, Yi Wu, Xinyue Cui, Honghua Dong, Fei Fang, and Stuart Russell. Robust multi-agent reinforcement learning via minimax deep deterministic policy gradient. Proceedings of the AAAI Conference on Artificial Intelligence, 33:4213-4220, 07 2019.
Ryan Lowe, Yi Wu, Aviy Tamar, Jean Harb, Pieter Abbeel, and Igor Mordatch. Multi-agent actor- environments. Proceedings of the Conference on Neural
critic for mixed cooperative-comper Information Processing Systems, 2017.
10

---

Under review as a conference paper at ICLR 2022
Xueguang Lyu, Yuchen Xiao, Brett Daley, and Christopher Amato. Contrasting centralized and decentralized critics in multi-agent reinforcement learning. In Proceedings of the International Conference Autonomous Agents and Multiagent Systems, 2021.
Kunal Menda, Yi-Chun Chen, Justin Grana, James W. Bono, Brendan D. Tracey, Mykel Kochen- derfer, and David H. Wolpert. Deep reinforcement learning for event-driven multi-agent decision processes. IEEE Trans. Intell. Transp. Syst. 20(4): 2019.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A. Rusu, Joel Veness, Marc G. Belle- mare, Alex Graves, Martin Riedmiller, Andreas K. Fidjeland, Georg Ostrovski, Stig Petersen, Charles Beattie, Amir Sadik, Ioannis Antonoglou, Helen King, Dharshan Kumaran, Daan Wier- stra, Shane Legg, and Demis Hassabis. Human-level control through deep reinforcement learning. Nature, 518:529-533. 2015.
Frans A. Olichock and Christopher Amato. A Concise Introduction to Decentralized POMDPs. Springer Publishing Company, Incorporated. 2016.
Frans A. Oliehoek, Matthijs T. Spaan, and Nikos A. Vlassis. Optimal and approximate q- q-value functions for decentralized pomdps. Journal of Artificial Intelligence Research, 32:289-353, 2008.
J. P. Queralta, J. Taipalmaa, B. Can Pullinen, V. K. Sarker, T. Nguyen Gia, H. Tenhunen, M. Gab- bouj. J. Raitoharju, and T. Westerlund. Collaborative multi-rohot search and rescue: Planning, coordination, perception, and active vision. IEEE Access, 8: 8:191617-191643, 2020.
Jianyu Su, Stephen Adams, and Peter A Beling. Value-decompositionn multi-agent actor-crities. In Proceedings of the AAAI Conference on Artificial Inielligence, 2021.
Richard S. Sutton. Learning to predict by the methods of temporal differences. Mach. Learn.. 3: 9-44, 1988.
Richard S Sutton, David A McAllester, Satinder P Singh, and Yishay Mansour. Policy gradient methods for reinforcement learning with function approximation. In Advances in neural informa- tion processing systems. pp. 1057-1063, 2000.
R.S. Sutton, D. Precup, and S. Singh. Between MDPs and semi-MDPs: framework for temporal abstraction in reinforcement learning. Artificial Intelligence, 1 112:181-211 1999.
Oriol Vinyals, Igor Babuschkin, Wojeiech M. Czarnecki, Michaël Mathicu, Andrew Dudzik, Juny- oung Chung, David H. Choi, Richard Powell, Timo Ewalds, Petko Georgiev, Junhyuk Oh, Dan Horgan, Manuel Kroiss, Ivo Danihelka, Aja Huang, Laurent Sifre, Trevor Cai, John Agapiou, Max Jaderberg, Alexander Sasha Vezhnevets, Rémi Leblond, Tobias Pohlen, Valentin Dalibard, David Budden, Yury Sulsky, James Molloy, Tom Le Paine, Çaglar Gülçchre, Ziyu Wang, To- bias Pfaff, Yuhuai Wu, Roman Ring, Dani Yogatama, Dario Wünsch, Katrina McKinney, Oliver Smith, Tom Schaul, Timothy P. Lillicrap, Koray Kavukcuoglu, Demis Hassabis, Chris Apps, and David Silver. Grandmaster level in stareraft using aggett reinforcement learning. Nature., (5567782):350-354, 2019.
Jianhong Wang, Yuan Zhang, Kae-Kyun Kim, and Yunjie Gu. Shapley q-value: A local reward approach to solve global reward games. 2020.
Yihan Wang, Beining Han, Tonghan Wang, Heng Dong, and Chongjie Zhang. DOP: Off-policy multi-agent decomposed policy gradients. In Proceedingy of the International Conference on Learning Representations, 2021.
Lex Weaver and Nigel Tao. The optimal reward baseline for gradient-based reinforcement learning. In Proceedings of the Conference on Uncertainty in Artificial Intelligence, pp. 538-545. Morgan Kaufmann, 2001.
Sarah A. Wu, Rose E. Wang, James A. Evans, Joshua B. Tenenbaum, David C. Parkes, and Max Kleiman- Weiner. Too many cooks: Coordinating multi-agent collaboration through inverse plan- ning. Topics in Cognitive Science, 2021.
11

---

Under review as a conference paper at ICLR 2022
Yuchen Xiao, Joshua Hoffman, and Christopher Amato. forcement learning. In Proceedings of the Conference on Robot Learning, 2019.
deep multi-agent rein-
Yuchen Xiao, Joshua Hoffman, Tian Xia, and Christopher Amato. Learning multi-robot decen- tralized macro-action-basedd policies via a centralized q-net. In Proceedings of the International Conference on Robotics and Automation, 2020.
Jiachen Yang, Alireza Nakhaei, David Isele, Kikuo Fujimura, and Hongyuan Zha. Cm3: Cooper- ative multi-goal multi-stage aggett reinforcement learning. In Proceedings of the Interna- tional Conference on Learning Representations, 2020.
Meng Zhou, Ziyu Liu, Pengwei Sui, Yixuan Li, and Yuk Ying Chung. Learning implicit credit assignment for cooperative multi-agent reinforcement learning. In Proceedings of the Conference Neural Information Processing Systems, 2020.
12

---

Under review as a conference paper at ICLR 2022
A APPENDIX
A.1 MACRO-ACTION- BASED POLICY GRADIENT THROREM
As POMDPs can always be transformed to history-based MDPs, we can directly adapt the general Bellman equation for the state values of a hierarchical policy (Sutton et al. 1999) to a macro-action- based POMDP by replacing the state s with history h as follows (for keeping the notaion simple, we use r to represent the number of timesteps taken by the corresponding macro-action m, and we use h represent macro-observvtiionaaciio history):
(h(h) = Σ V (m]h)Q (h, m) Q*th, (h, m) = ( m) + Σ
(13)
P(Klk, M)) (N))
(14)
h
where,
fm + Σ t=tm
(h, = BB (m)
Ntr]]
(15)
P(h(h, = P(z/lh, =
(16)
=
Σ m()
(17)
= y
(18)
= (B))
(1))
[ Enjh |am, [P(2 m, 811]
(19)
Next, we follow the proof of the policy gradient theorem (Sutton et al. 2000):
Vo (h)
V
V (h)
(0
Σ V
(21)
V (4 +
Σ
(22)
\oWo(mlh)@" + (o(ml))
Σ P(klh, (oV"
(23)
P(h + " (after repeated unrolling)
beh k=0
m
(24)
Then, we can have: VoJ(O)= = VoV (ho)
(25)
Σ Σ P(ho + k, Vo) Σ [o
(26)
REH R=
m
(M)
VoVo(mll) (h, m)
(27)
h m
Σ p (h) Σ
" m)
(28)
m
Ev,
Vo (m (h, m)
(29)
13

---

Under review as a conference paper at ICLR 2022
A.2 ALGORITHM
In this section, we present the pesudo code of each proposed macro-action-based actor-critic algo- rithm with example show how the sequential experiences squeezed for training the critic and the actor. We describe all methods the on-policy learning manner while off-policy learning can be achieved by applying importance sampling weights and not resetting the buffer.
A.2.1 MAC-IAC
x
t+7
t+8
m
m
2
22
2
22
24
Agent,
m²
m
m
m
Agent,
Sh
Time
T-1
1-4
t-6
t-8
8
m
6
m²
Agent,
2²
2
10
0
8
Agent,
2
Figure 5: An example of the trajectory squeezing process in Mac-IAC. We collect each agent's high-level transition tuple every primitive-step. Each agent is allowed to obtain observation if and only if the current macro-action terminates, otherwise, the next macro-observation as same as the previous one. Each agent separately squeezes its sequential experiences by picking out the transitions when its macro-action terminates (red cells). Each agent independently train the critic and the policy using the squeezed trajectory.
macro-
Algorithm Mac-IAC
I: Initialize a decentralized policy network each agent Vo,
Was
2: Initialize decentralized critic networks for cach agent i: Vws
Initialize a buffer
4: for episode = 1 to M do
5:
t=0
6:
Reset cnv
while not reaching terminal state and < H do
4- ++1
9:
for each agent i do
10:
if the macro-action me is terminated then m, Wo, 1u;e)
11:
12:
else
13:
Continue running current macro-action m;
for each agent do
15:
Get cumulative reward rf, next macro-observation 2( Collect (#,, m,, 2/, rf) into the buffer D
16:
17:
if episode mod Junn = then
18:
for each agent do
19:
Squeeze agent i's trajectories in the huffer D
20:
Perform gradient decent step on L(w.) = (y Vw. (h:))) where y = rf + t
20,
(h()
w;
21:
Perform gradient ascent on: Vo. E, Vo, log Vo, (m. Tmm, V (h() Vw." 2o, (hh)))
22:
23:
Reset huffer
24:
if episode mod IangetUpaae then for cach agent do
25:
26:
Update critic target network w, f- W.
14

---

Under review as a conference paper at ICLR 2022
A.2.2 MAC-CAC
Time
t+]
t+2
t-3
I-d
t+5
t-6
t-?
t+8
t-9
Time
t-l
t+2
bod
Iw6
t-g
x
2'
Agent,
m
771
m
112
111
711
111
771
Agent;
m
111
m
171
24
x2
22
2a
23
23
2
2
z4
2²
2
24
=²
27
2
29
2
10
29
27
1
z
Agent,
m3
m
m
m
111
m
172
Agent,
112
m
172
m
172
m
="
11
Com
Figure 6: An example of the trajectory squeezing process Mac-CAC. Joint sequential experiences are squeezed by picking out joint transition tuples when the joint macro-action terminates, in that, any agent's ss macro-action termination (marked red) ends the joint macro-action at the timestep. For example, at & = 1, agents execute joint macro-action vi {m², mm² for one timestep; at t = 2, the joint macro-action becomes (m' mm² as Agent, finished m² at last step and chooses a new macro-action m Agent, finished its macro-action my at t = 2 and selects new macro-action m at = so that the joint macro-action switches to (m² _m² which keeps running until the 4th timestep. Therefore, the first two joint macro-actions have two single-step reward respectively, and reward of joint macro-action (m², mm) is an accumulative reward over two consecutive timestéps.
Algorithm Mac-CAC
Initialize a centralized policy network: Vo
2: Initialize centralized critic networks: Vw v Initialize a centralized buffer Mac-JERT',
4: for episode= = to do
5: ==0
6:
Reset cnv
7: while not reaching terminal state and < H do
<- +++
9:
if the joint macro-action m is terminated then
m7 (- undons;;)
11:
else
12:
Continue running current joint macro-action mi
13:
Get a joint cumulative reward F", next joint macro-observation z" Collect (E, m, z", (%) into the buffer D
14:
15:
if episode mod Jusi = 0 then
16:
Squeeze joint macro-level trajectories in the buffer D according to joint macro-action terminations
17:
Perform gradient decent step I-w) (y V (fi) 2 where F + yFa v.V (F''
18:
Perform a gradient ascent on (e) Ev, V log (o R) +n + v (T') V (h))
19:
Reset buffer D
20:
if episode mod Tangetppauee then Update the critic target network w
21:
W
where, 17 undonee is the joint-macro-action over the agents who have not terminated their macro- actions and will continue running.
15

---

Under review as a conference paper at ICLR 2022
A.2.3 NAIVE MAC-IACC
In the pscudo code of Naive Mac-IACC presented below, we assume the accessible centralized information x is joint macro-obserratiio-aatioo history in the centralized critic.
Train Policy,
Time
Train Centralized Critic
m0*
Time
X+
6-5
14
1-5
E46
1+]
Time
I-]
1+4
b-
1/2
202
112
mn²
m
2
27
Train Policy;
Aprr
ng
mi
Agent
my
Time
2-2
2-4
Buse
Agunt,
mn
Figure 7: An example of the trajectory squeezing process in Navie Mac-IACC. The joint trajectory is first squeezed depending on joint macro-action termination for training the centralized critic (line 18- 19 in Algorithm 3) Then, the trajectory is further squeezed for each agent depending on each agent's own macro-action termination for training the decentralized policy (line 20-23 in Algorithm 3
Algorithm Naive Mac-IACC
I: Initialize a decentralized policy network for each agent i: Ve.
2: Initialize centralized critic networks: VW v-
3: Initialize decentralized buffer D <- Mac-JERTs,
4: for episode to M do
t=
6:
Reset env
7: while not reaching terminal state and < H do
8:
++1
for each agent i do
10:
the macro-action m: is terminated then m, ~ We, ( (;;e)
11:
12:
clse
13:
Continue running current macro-action m,
14:
Get reward f accumulated based on current joint macro-action termination Get next joint macro-observations z
15:
Collect (E, m, z", ,75) into buffer D
if episode mod Arain then Squeeze joint macro-level trajectories in the buffer 2 according to joint macro-action terminations
18:
Perform gradient decent step on L(w) = V. (Te)) D where y , + 7 (T²) for cach agent do
20:
21:
Squeeze agent i's trajectories in the buffer D according to its own macro-action terminations Perform gradient ascent
22:
J(,) = E. Vo, log Wo, (mn(lhs)) + V ((()))))))) VW (
23:
24:
Reset buffer D if episode mod taggetiiduee then
25:
26:
Update the critic target network w
W
16

---

Under review as a conference paper at ICLR 2022
A.2.4 MAC-IAICC
In the pseudo code of Mac-IAICC presented below, assume the accessible centralized informa- tion x is joint macro-observation-actiin history in the centralized critic.
Train Agent, Centralized Critic
Train Policy,
29
f2²
mp2
90-
my
29
01-
102
R0-
Apert
X VT
Train Agent,'s 's Centralized Critic
16
Agene,
Time
L-]
Ixc
I+b
Train Policy,
g
Time
[-]
[-
t-
Agene
10
Agent
Figure 8: An example of the trajectory squeezing process in Mac-IAICC: each agent learns an individual centralized critic for the decentralized policy optimization. In order achieve better use of centralized information, the recurrent layer in each critic's s neural network should receive all the valid joint macro-obses cencco-obbervationactiii 20-22) and obtain new joint macro-observation) However, the critic's TD updates and the policy's updates still rely on each agent's 's individual macro-action termination and the accumulative reward the corresponding timestep (line 23-26). Hence, the trajectory squeezing process for training each critic still depends on joint-macro action termination but only retaining the accumulative rewards w.r.t. the corresponding agent's macro-action termination for computing the TD loss (the middle part in the above picture). Then, each agent's trajectory is further squeezed depending on its macro- action termination to update the decentralized policy.
information (when any agent terminates its macro-actio action (line
17

---

Under review as a conference paper at ICLR 2022
Algorithm 4 Mac-IAICC
I: Initialize a decentralized policy network for each agent it Mo
2: Initialize centralized critic networks for each agent i: Voli w.
3: Initialize a decentralized buffer
for episode = to do
5: t=
6: Reset cnv
7: while not reaching terminal state and < H do
+++1
9:
for each agent i do
10:
if the macro-action m, is torminated then (. h;:e)
11:
12:
else
Continue running current macro-action mi;
14:
for cach agent do
15:
Get a reward rf accumulated based on agent i's macro-action termination
Get next joint macro-observations z"
17:
Collect (Z, m, z' {ri,... ... ) into the buffer D
18:
if episode mod Jui = then
19:
for each agent do Squeeze trajectories in the buffer D according to joint macro-action terminations Compute the TD-emro of each timestep in the squcezed experiences:
20:
21:
T((::) (v Vw. (k)) 2
>> where y = rf y Tmme 2 ((²)
22:
23:
Perform gradient descent only over the TD-errors when agent i's macro-action terminated Squeeze agent i's trajectorics in the buffer D according to its own macro-action terminations Perform gradient ascent on:
24:
25:
((0,) = E,g Vo, log Vo, (mn(hes)) Tmm, " V.. (6))
26:
27:
Reset buffer D if episode mod TageeUpstte then for each agent i do
28:
29:
30:
Update the critic target network w, <- W;
18

---

Under review as a conference paper at ICLR 2022
A.3
DOMAIN DESCRIPTION AND RESULTS
A.3.1
BOX PUSHING
Domain Setup.
(a) 8x8
(h) 10x10
(c) 12x12
Figure 9; Experimental environments.
Goal. The objective of the two agents is to learn collaboratively push the middle big box to the goal area at the top rather than pushing small box each
State. The global state information consists of the position and orientation of each agent and each box's position grid world.
Primitive-Action Space. move forward, turn-left, turn-right and stay.
Macro-Action Space.
One-step macro-actions: Turn-left, Turn-right, and Stay.
Multi-step macro-actions: Move-to-smalllbox(( that navigates the agent to the red spot below the corresponding small box and terminate with agent facing the box; -ove-to-big-box(i that navigates the agent red spot below the big box and terminate with agent facing the big box; Push that op- erates the agent to keep moving forward and terminate while arriving the world's boundary. touching the big box along or pushing small box to the goal.
Observation Space. In both the cemitive-observatiin and macro-observation, each agent is only allowed capture one of five states the cell in front of it: empty, teammate, boundary, small box, big box.
Dynamics. The transition in this task is deterministic. Boxes can only be moved towards the north when the agent faces the box and moves forward. The small box can be moved by a single agent while the big box require two agents move it together.
Rewards. The team receives +300 for pushing big box to the goal area and +20 for pushing a small box the goal area. penalty -10 is issued when any agent hits the boundary or pushes the big box on its own
Episode Termination. Each episode terminates when any box is pushed the goal area, or when 100 timesteps has elapsed.
19

---

Under review as a conference paper at ICLR 2022
Results
Mac-IAC
IAC
Benchmark Policy
Box Pushing
Box Pushing 8x8
Box Pushing 10x10
300
300
300
Mean Test Return
Mean Test Return
Mean Test Return
240
240
240
180
180
180
120
120
120
60
-60
-60
0K
20K
40K
0K
20K Episode
40K
0K
20K Episode
30K
40K
Episode
Box Pushing 12x12
Box Pushing 14x14
300
300
Mean Test Retur
Mean Test Return
240
240
180
180
120
120
-60
-60
0K
20K Episode
30K
40K
0K
20K Episode
30K
40K
Figure 10: Decentralized learning with macro-actions vs primitive- acttios in Box Pushing domain.
Mac-CAC
CAC
Benchmark Policy
Box Pushing 6x6
Box Pushing 8x8
Box Pushing 10x10
300
300
300
Mean Test Retur
Mean Test Return
Mean Test Return
240
240
240
180
180
180
120
120
120
60
60
60
60
-60
-60
0K
40K
40K
Episode
Episode
Episode
Box Pushing 12x12
Box Pushing 14x14
300
300
Mean Test Return
Mean Test Return
240
240
180
180
120
120
60
60
-60
-60
20K Episode
40K
Episode
Figure 11: Centralized learning with macro-actions vs primitive- actions in Box Pushing domain.
20

---

Under review as a conference paper at ICLR 2022
Naive Mac-IACC
Mac-CAC
Benchmark Policy
Box Pushing 6x6
Box Pushing 8x8
Box Pushing 10x10
Mean Test Return
250
Mean Test Return
250
Mean Test Return
250
200
200
200
150
50
01
0-
0K
10K
20K
30K
40K
0K
10K
20K
30K
40K
0K
10K
20K
30K
40K
Episode
Episode
Episode
Box Pushing 12x12
Box Pushing 14x14
Mean Test Test Return
250
Mean Test Return
250
200
200
150
50
50
01
0-
0K
10K
20K Episode
30K
40K
0K
10K
20K
30K
40K
Episode
Figure 12: Comparison of macro-action- multi-agent actor-critic methods in Box Pushing.
A.3.2 OVERCOOKED
Domain Setup
(a) Overcooked-A
(b) Overcooked-BB
(c) Overcooked-C
(d) Lettuce-Tomato salad recipe
Figure 13: Experimental environments.
Goal.
Two agents need to learn cooperating with each other to prepare a Lettuce- Tomato salad and deliver it to the 'star' counter cell as
possible. The challenge is that the recipe of making a lettuce-tomato salad (Fig. 2 is unknown to agents. Agents have to learn the correct procedure in terms of picking up vegetables, chopping, and merging in plate before delivering.
State Space. The environment is a 7x7 grid world involving two agents, one tomato, one lettuce, two plates, two cutting boards and on delivery cell. The global state information consists of the location of each agent and above items, and the status of each vegetable: chopped, unchopped, or the progress under chopping.
Primitive-Action Space. Each agent has five primitive-actions: up, down, left, right and stay. Agents can move around and achieve picking, placing, chopping and delivering by moving against the corresponding counter cell (e.g. standing at the cell next to the lettuce and executing right to pick up.
21

---

Under review as a conference paper at ICLR 2022
Macro-Action Space.
One-step macro-actions:
Stay, stay at the current position and terminate.
Up, Down, Left and Right, each moves the agent to the corresponding nearby cell and terminate.
Multi-step macro-actions:
Get- and Get-Lettuce, navigate the agent to the latest observed position of the vegetable, the vegetable is there, pick it up. otherwise the agent moves to the initial position of the vegetable, and picks up if the vegetable is there, otherwise terminates the macro-action.
Termination conditions:
Case 1:
The agent next to the chopped/unchopped food and picks up. Case 2: The agent observes that the food is being held by the other agent or itself.
Case 3:
The agent is next to the unchopped food holding a plate or other food.
Case 4: The agent is next to the other agent and this agent is next to the food.
Case 5: The agent is next to the cutting board counter and the unchopped food is on the counter.
Case 6: The agent does not find the tomato/lettuce in the latest position it observed it. And the agent
goes to the initial position of the food and does not find it, either.
Case 7: Two agents attempt to enter the same cell. One agent stays and terminates according predefined priority.
Get-Plate-1/2, navigates the agent to the latest observed position of the plate. If the plate is there, pick it up, otherwise the agent moves to the initial position of the plate, and picks it up if the plate is there, otherwise terminates the macro-action.
Termination conditions:
Case 1:
The agent is next the plate and picks it up. The agent observes that the plate is being held by the other agent or itself.
Case 2:
Case 3: The agent next to the plate but holding another plate or unchopped food.
Case 4: The agent is next to the other agent and this agent is next to the plate.
Case 5: The agent does not find the plate the latest position it observed And the agent goes to the initial position of the plate and does not find it, either.
Case 6: Two agents attempt to enter the same cell. One agent stays and terminates according to predefined priority.
Go-Cut-Board 1/2, navigates the agent to the corresponding cutting board.
Termination conditions:
Case I:
The agent next to the cutting board counter without holding anything. Case 2: The cutting board is empty. The agent is next to the cutting board while holding plate or food, and then put on the cutting board.
Case 3:
There is plate food on the cutting board. The agent stops at the cell next the cutting board.
Case 4: The cutting board is being used by teammate, the agent stops the cell next the teammate.
Case 5: Two agents attempt to enter the same cell. One agent stays and terminates according to a predefined priority.
Chop, chops the raw vegetable into pieces, which takes three timesteps.
Termination conditions:
Case 1: The vegetable on the cutting board has been chopped into pieces.
Case 2: Immediately terminates when the agent is not next to cutting board.
Case 3: Immediately terminates when there is no unchopped food on the cutting board.
Case 4: The agent holds something.
22

---

Under review as a conference paper at ICLR 2022
Deliver, navigates the agent to the 'star' counter cell for delivering by putting down the in-hand object.
Termination conditions:
Case I: The agent is next to the delivery counter without holding anything.
Case 2: The agent is next the delivery counter holding object and put down the object the delivery counter cell.
Case 3: Teammate is standing in front of the delivery counter cell, the agent terminates at the cell
next to teammate.
Case 4: Two agents attempt enter the same cell. One agent stays and terminates according predefined priority.
Go-Counter, navigates the agent one empty counter cell in the middle the map. The priority of the targeting counter cell is from middle to the sides. This macro-action is only available in map B and C.
Termination conditions:
Case 1:
The agent next to the counter cell without holding anything. The agent is next to the counter cell that is not empty.
Case 2:
Case 3:
The agent next to the counter cell and puts in-hand object on it.
Case 4: Teammate is in front of the target counter cell, the agent then stops next to the teammate.
Case 5: Two agents attempt to enter the same cell. One agent stays and terminates according to predefined priority.
Observation Space: The macro-observation space for each agent is the same as the primitive ob- servation space. Agents are only allowed to observe the positions and status of the entities within 5 X 5 egocentric view field. The initial position of all the items are known to the agents.
Dynamics:
The transition in this task deterministic. If an agent delivers any wrong item, the item will be reset to its initial position. From the low-level perspective, chop vegetable into pieces on a cutting board, the agent needs to stand next to the cutting board and executes left three times. Only the chopped food can be put plate.
Reward: +0 for chopping vegetable, +200 terminal reward for delivering a lettuce-tomato salad, -5 for delivering any wrong entity, and -0.1 for every timestep.
Episode Termination: Each episode terminates either when agents successfully deliver a lettuce- tomato salad correct dish reaching the maximal timesteps, 200.
23

---

Under review as a conference paper at ICLR 2022
Results
Mac-IAC
IAC
Benchmark Policy
Overcooked-A
Overcooked-i
Overcooked-C
175
175
175
Mean Test Return
Meon Test Return
Mean Test Return
140
140
140
105
105
105
70
35
0
-35
-35
-35
0K
25K
50K Episode
75K
100K
25K
50K Episode
75K
100K
25K
50K Episode
75K
100K
Figure 14: Decentralized learning with macro-actions vs primitive-actions in Overcooked domain.
Mac-CAC
CAC
Benchmark Policy
Overcooked-A
Overcooked-8
Overcooked-C
175
Mean Test Return
Mean Test Return
Mean Test Return
140
140
140
105
105
105
70
70
70
35
35
0K
25K
50K Episode
75K
100K
0K
25K
50K Episode
75K
100K
0K
25K
50K Episode
75K
100K
Figure 15: Centralized learning with macro-actions vs primitive-actions in Overcooked domain.
Mac-IAICC
Naive Mac-IACC
Mac-CAC
Mac-IAC
Benchmark Palicy
Overcooked-A
Overcooked-B
Overcooked-C
175
175
175
Mean Test Return
Mean Test Return
Mean Test Return
140
140-
70
70
70
35
35
35
0
0K
25K
50K Episode
75K
100K
0K
25K
S0K Episode
75K
100K
0K
25K
50K Episode
75K
100K
Figure 16: Comparison of macro-action-basee multi-agent actor-critic methods in Overcooked.
24

---

Under review as a conference paper at ICLR 2022
A.3.3 WAREHOUSE TOOL DELIVERY
Domain Setup
Tool Room
Tool Room
Tool Room
W-0
W-O
W-1
W-o
W-1
W-1
W-2
(a) Warehouse-A
(b) Warehouse-B
(c) Warehouse-C
Figure 17: Experimental environments.
We In this Warehouse Tool Delivery domain, we consider three different scenarios shown in Fig. 17 make the original problem (Xiao et al., 2019) (only one human worker involved) more challenging by: 1) adding one more human into the environment (Fig. 17p): 2) increasing the number of agents and having three humans in the environment further examine the scalability of our methods and the effectiveness of Mac-IAICC on handling more noisy asynchronous terminations over agents (Fig. 17p): :); 3) having one faster human involved to check whether the agents can learn priority for delivering tool to him or not.
Goal. Under all scenarios, in each workshop, human is working
assembly task involving 4 subtasks to be finished (each subtask takes amount of primitive timesteps) and requires three particular tools for each future subtask continue. Humans either work in the same speed (Fig. (Pp- b) or have one of them working faster (the orange one in Fig (7p). The robot team includes a arm robot (grey) with the duty of finding tools for each human on the table (brown) and passing them to mobile robots (green, blue and yellow) who are responsible for delivering tools to the humans. The objective of the robots is to assist the humans to finish their assembly tasks as soon as possible by finding the correct tools in a efficient order. To make this problem more challenging, the correct tools that each human needs are unknown to the robots, which has to be learned during training in order to perform timely delivery without letting any human wait over there.
State. The environment is either 5 x 7 (Fig. 17a) or a 5 x (Fig. 17p-c) continuous space. A global state consists of the 2D position of each mobile robots, the execution status of the arm robot's current macro-action (e.g how munch steps are left for completing the macro-action, but in real- world, this should be the angle and speed of each arm's joint), the subtask each human is working with a percentage indicating the progress of the subtask, and the position of each tools (either on the brown table or carried by mobile robot). Note that, there enough tools for each human such that the number of each type of tool exactly matches with the number of humans in the environment. The initial state of every episode is always same shown in Fig. 17 where humans always start from the first step.
Macro-Action Space.
The available macro-actions for each mobile robot include:
Go-W(i) navigates the red waypoint at the corresponding workshop:
Go-TR, navigates to the red waypoint at the right side of the tool room;
Get-Tool, navigates to pre-allocated waypoint besides the arm robot and waits there until either 10 timesteps have passed or receiving a tool from the gray robot.
The available macro-actions for the robot include:
Search-Tool(i), takes 6 timesteps to find tool and place it in a staging area (containing at most two tools) when the area is not fully occupied, otherwise freezes the robot for the same amount of time;
Pass-to-Mii), takes 4 timesteps pass tool to mobile robot from the staging area in the order of first-i-ffist-oout,
Wait-M, takes timestep to wait for mobile robots coming.
25

---

Under review as a conference paper at ICLR 2022
Macro-Observation Space.
The arm robot's macro-observation include the information about the rype of each tool the staging area and which mobile robot is waiting beside.
Each mobile robot always observes its own position and the type of each tool carried by itself, while observes the number of tools in the staging area the subtask human working only when locating at the tool room or the workshop respectively.
deterministie. Each mobile robot moves in speed 0.8 and is only allowed receive tools from the arm robot rather than from humans. Each human is only allowed to possess the tool for the next subtask from mobile robot when the robot locates the corresponding workshop and carries the exact tool. In the Warehouse-A, each human takes 18 timesteps to finish each subtask; in the Warchouse-B, each human takes 40 timesteps finish each subtask; and in the Warchouse-C, each subtask takes the faster human 30 timesteps while taking the slower human 40 timesteps. Human cannot start the next subtask without obtaining the correct tool.
Dynamics. Transitions
Rewards. The team receives +100 reward when correct tool is delivered to human in time while getting an extra 20 penalty for delayed delivery such that the human has paused over there. A - 10 reward occurs when the grey robot does Pass-to-M(i) but the mobile robot i is not next to it, and 1 reward is issued every timestep.
Episode Termination. Each episode terminates when all humans obtained all the correct tools for all subtasks, otherwise, the episode will run until the maximal timesteps (200 for Warehouse-A and 250 for Warehouse-B and C).
Results
MaC-IAICC
Naive Mac-IACC
Mac-CAC
Mac-IAC
Benchmark Policy
Warehouse-A
Warehouse-B
Warehouse-C
600
800
800
Mean Test Return
Mean Test Return
Mean Test Return
600
600
300
200
200
-150
-200
-200
Episode
Episode
Episode
Figure 18: Comparison of macro-action-baste multi-agent actor-critic methods in Warehouse Tool Delivery domain.
26

---

Under review as a conference paper at ICLR 2022
A.4 BEHAVIOR VISUALIZATION
In the section, we display the decentralized behaviors learned by using Mac-IAICC under all con- sidered domains.
A.4.1 Box PUSHING
We show the behaviors learned under the grid world size 14 x 14 in Fig. 19 Although the averaged performance of the training is not near-optimal (Fig. 12). several runs can learn the optimal behavior.
Green agent executes Move- to-big-box(I) move left waypoint below the big box while the blue agent runs Move- to-big-box(2) to move to the right waypoint below the big box.
(b) After completing the previ- ous macro-actions, agents choose Push to move the big box to- wards the goal together.
(c) Agents finish the task by pushing the big box to the goal area.
Figure 19: Visualization of the optimal macro-action-basse based behaviors learned using Mac-IAICC in the Box Pushing domain under 14 14 grid world.
27

---

Under review as a conference paper at ICLR 2022
A.4.2 OVERCOOKED
Map A. In this map, simple collaborative strategy that agents pick up the tomato and lettuce, bring them to the cutting board, chop them into pieces, and then let one agent go to get one plate, put the chopped food on the plate and delivery it. While the agent getting the plate, the other agent has nothing to do, which waste some time. Our method learns more efficiently way, it makes one agent chop both the tomato and lettuce, meanwhile, the other agent goes pick up the plate. makes both of the agents work in parallel, which saves the time.
(a) The blue agent exe- cutes Get-Lettuce. The
(b) After the pink agent gets the tomato, it cutes Go-Cut-Board- to put the food on the cut- ting hoard.
(c) After the blue agent gets the lettuce, it cutes Car---ar-oddd to put the food on the cut-
(d) After the pink agent
puts the tomato the
pink agent executes Get- Tomato.
cutting board, executes
Get-Plate-1 to get plate.
ting board.
(e) blue agent puts the lettuce on the cutting board, it executes Chop chop the lettuee into pieces.
(f) After blue agent chops the lettuee into pieces, it executes Get- Tomato approach tomato.
(g) After blue agent front the tomato, exccutes Chop to chop the tomato into pieces.
(h) After the pink agent gets the plate, exccutes Get-Tomate to put the tomato the plate.
(i) After the blue agent chops the tomato into pieces, exccutes Get- plate, executes Get- plate, executes Deliver. Plate-2 avoid blocking Lettuce. pink agent's way.
(i) After the pink agent
(k) After the pink agent puts the lettuee the cessfully delivers the
(I) The pink agent suc-
puts the tomato the
lettuce-tomato salad.
Figure 20: Visualization of running decentralized policies learned by Mac-IAICC Overcooked-A.
28

---

Under review as a conference paper at ICLR 2022
Map B. In this map, the best strategy is that the pink agent should take the advantage of the middle counters to pass vegetables to the other agent. Our method learns a sub-optimal policy such that the blue agent still crosses the narrow passage to get the vegetable at the right side of the map.
(a) The blue agent cutes Get-Lettuce. The pink agent exccutes Get- Tomato.
(b) Atter the pink agent gets tomato, exe-
(c) After the blue agent gets lettuce, it exe-
(d) After the pink agent
puts tomato on the
cutes Gio-Cut-Board-4 to put the food on the cut- ting hoard.
cutes Co--Cut-ooard- to put the food on the cut-
cutting board, executes Chop to chop the tomato
ting board.
into pieces.
(c) After the pink agent chops the lettuce into pieces, executes Get- Plate-1.
(f) After the blue agent puts the lettuce on the cutting board, it executes Chop chop the let- tuce into pieces. Af- ter the pink agent gets the plate, it executes Go- Cut-Board-2 get the chopped tomato.
(g)After the blue agent chops the lettuce into
(g) After the pink agent
puts the tomato on the pieces, it executes Get- plate, it executes Get- Lettuce.
Plate-2 to avoid blocking
pink agent's 's way.
(h) After the pink agent puts the lettuee the cessfully delivers the plate, executes Deliver.
(i) The pink agent
lettuce- salad.
Figure 21: Visualization of running decentralized policies learned by Mac-IAICC in Overcooked-B.
29

---

Under review as a conference paper at ICLR 2022
Map C. In this map, the policy trained by method learns to use the macro-action Go-Counter to pass vegetables and plates to teammate.
(a) The blue agent ex- ecutes Go-Cut-board-2.. The pink agent executes Get- Tomato.
(b) The pink agent exe- cutes Go-Counter to put the tomato one of the middle counter cells.
(c) After the pink agent puts the tomato on the counter, it executes Get- Lettuce. The blue agent executes Get- Tomato.
(d) After the blue agent gets the tomato, it exe- cutes Coo-Cut-ooard-2.
(f) After the blue agent gets the lettuce, it puts the tomato the cutes Go-Counter the food on one of the
(c) After the pink agent
(g) After the pink agent puts the lettuce the counter, it executes Get- pieces, it executes Get- Plate-2.
(h) After the blue agent chops the tomato into
put
cutting board, executes
Chop to chop the food
Lettuce.
middle counter cells.
into pieces.
*
*
(i) The blue agent exe-
(j) After the blue agent
(k) After blue agent
(I) After the blue agent
cutes Go-Cut-Board-1 to put the lettuce the cut- ting board. pink agent executes Go-Counter to put the plate on the counter.
puts the lettuce on the
chops the lettuce into
holds the chopped let-
cutting board, it executes Chop to chop the food
pieces, it executes Get- tuce. it executes Go-
Lettuce pick up the chopped lettuce.
Counter to put the lettuce on the plate.
into pieces.
(m) After blue agent puts the lettuce on the
(n) After the blue agent puts the tomato on the plate, it exccutes Get- plate, it exccutes Deliver. Tomato.
(o) The blue agent successfully delivers the lettuce-tomatee tomcco salad.
Figure 22: Visualization of running decentralized policies learned by Mac-IAICC in Overcooked-C.
30

---

Under review as a conference paper at ICLR 2022
A.4.3 WAREHOUSE TOOL DELIVERY
Warehouse-A. In this domain, simple collaborative strategy is that two mobile robots separately assist a particular human (e.g. green robot always delivers tool to W-1 and blue robot always delivers tool W-2). However, according each human's 's working speed, this strategy causes all deliveries are late except the first one such that humans always wait after finishing each subtask, which results in many penalties. By using our method Mac-IAICC, robots learn more efficient collaboration shown below, which only leads to one delayed delivery but others are all in time.
Tool Room
W--
(a) Initial State.
(b) Mobile robots moves to- wards the table by running Get- Tool, and arm robot runs Search- Tool(O) to find Tool-O.
(c) Mobile robots wait there and arm robot keeps looking for the first tool.
(d) Arm robot executes Pass-to- M(Z) to pass the first tool the blue robot.
(c) Arm robot executes Search- Tool(I) to find Tool-1, and blue robot to workshop-1 by executing Go- W(I).
(f) Blue robot successfully deliv- Tool-O to workshop-l.
(g) Blue robot runs Get-Tool to back table, and arm robot exe- cutes Pass-to-M(() to pass Tool- to green robot.
(h) Green robot executes Go- W(O) and arm robot runs Search- Tool(2). Blue robot waits for tools.
(i) Green observes human-0 needs Tool-0 while it carries Tool-1, that it executes Go- W(I) to check human- needs Tool-1.
(i) Green robot successfully de- livers Tool-1 human-1.
(k) Arm robot executes Pass-to- M(I) to pass Tool-2 blue robot.
(I) Arm robot executes Search- Tool(0) to find the other Tool-0, and green robot Get-Tool to go back arm robot.
31

---

Under review as a conference paper at ICLR 2022
(m) Arm robot executes Pass-to- M(1) to pass Tool-O to blue robot, and blue robot carries Tool-O and Tool-2 now.
(n) Blue robot smartly runs Go- W(O) to first delivery Tool-O to human-O. and arm robot executes Search-Tooke Tool(I) find the other Tool-1.
(o) Blue robot successfully deliv- ers Tool-O to human-O, and hu- man starts working sub- task.
(p) Blue robot executes Go-W(I) and successfully delivers Tool-2 to human-1. Human-I have obtained all necessary tools.
(q) Arm robot executes Pass-to- M(0) to pass Tool-1 to green robot, and blue robot runs Get- Tool to go back table.
(r) Green robot runs Go-W(O) deliver Tool-1 to human-O, and arm robot executes Search- Tool(2) to find the Tool-2.
(s) Green robot successfully de- livers Tool-1 to human-0.
(t) Arm robot executes Pass-to- M(J) to give Tool-2 to blue robot, and green robot goes check human-1 by running Go- W(I).
(u) Blue robots directly goes to workshop-O by running Go- (()) and finishes the last tool delivery for human-O. The entire task done.
32

---

Under review as a conference paper at ICLR 2022
Warehouse-B. In this scenario, hand-coded strategy controls each mobile robot focus serving a particular workshop, which is able to finish the task without any delayed delivery. By using Mac-IAICC, robots learn another cooperative behaviors that achieve timely delivery for all tools by using only two mobile robots (the green one and the yellow one) and achieve the same return the hand-coded one.
Tool Room
WW-0
W-1
W-22
(a) Initial State.
(b) Both green and yellow robots move towards the table by running Get-Tool. Blue runs Go- W(O) to go to workshop-O. 0. Arm robot runs Search-Tool(0) to find Tool-O.
(c) Green and yellow robots wait there and robot keeps looking the Tool-O. Blue robot arrives at workshop-O.
Basa
(d) Blue robot runs Get-Tool to back the table.
(e) Arm robot executes Pass-to- M(2) Tool-0 yellow
(I) All mobile robots keep running Gool wait there for tools, and robot executes Search- Tool(0) to find the Tool-O.
rohot.
(g) Arm robot executes Pass-to- M(2) to pass the 2nd Tool-O to the yellow robot, Now yellow robut carries Tool-O..
(h) Arm robot executes Search- Tool(0) to find the 3rd Tool-O, while yellow robot runs Go-W(I) deliver Tool-O to the furthest workshop-1.
(i) Yellow robot successfully livers Tool-O to human-l.
(j) Yellow robot runs Go-W(2) to deliver the other Tool-0 human-
(k) Yellow robot successfully livers Tool-O to human-2. Green robot runs Go- to deliver Tool-O to human-0. Arm robot executes Search-Tool(1) to find Tool-1.
(I) Yellow robot runs Gei- to return tool room. Green robot keeps moving towards workshop- under the execution of Go- W(O). Arm robot is looking for Tool- under the running of previous macro-action.
2. and arm robot executes Pass- 10-M(0) pass the 3rd Tool-O to green robot.
33

---

Under review as a conference paper at ICLR 2022
(m) Arm robot exccutes Search- Tool(I) again to find the 2nd Tool-
(n) Green robot runs Get-Tool to go back table. Yellow robot is robot.
(o) Arm robot executes Pass-to- M(2) to pass a Tool-1 to yellow
1. Green robot successfully de-
waiting for tools.
livers Tool-0 human-0. Yellow robot moving towards table.
(p) Arm robot executes Pass-to- M(2) again to pass the other Tool- to yellow robot.
(g) Arm robot executes Search- Tool(1) to find the 3rd Tool-1, and yellow robot runs Go-W(I) to first deliver Tool-1 to the furthest workshop-1.
(r) Yellow robot successfully livers Tool-1 to human-l.
(s) Yellow robot runs Go- (o-)(() to deliver the other Tool-1 human- 2. and arm robot executes Pass- to-M(0) to pass the 3rd Tool-1 to green robot.
(t) Yellow robot successfully de- livers Tool-1 to human-2. Green robot runs Ge-W(0) to deliver Tool-1 to human-0. Arm robot executes Search-Tool(2) to find Tool-2.
Arm robot executes Search- Tool(2) again to find 2nd Tool- 2. Green robot successfully de- livers Tool-1 to human-O. Yellow robot moving towards table.
(v) Green robot runs Ger-Tool go back table. Yellow robot is robot.
(w) Arm robot executes Pass-to- M(2) to pass a Tool-2 to yellow
(x) robot executes Pass-to-
M(2) again to pass the other Tool-
waiting for tools.
2 to yellow robot.
34

---

Under review as a conference paper at ICLR 2022
(y) Arm robot executes Search- Tool(2) to find the 3rd Tool-2, and ycllow robot runs G(I) to first deliver Tool-2 to the furthest workshop-1.
(2) Yellow robot successfully livers Tool-2 to human-l.
(A) Yellow robot runs Go- W(2) to deliver the other Tool-2 to human- 2, and arm robot executes Pass- to-M(0) to the 3rd Tool-2 to green robot.
(B) Yellow robot successfully de- livers Tool-2 human-2. Green robot runs Go- W(0) to deliver Tool-2 to human-O.
(C) Green robot successfully de- livers Tool-2 human-2. Humans have received all tools, and for robots, the task is done.
35

---

Under review as a conference paper at ICLR 2022
Warehouse-C
In this scenario, the arm robot leans an efficient order to find correct tools that humans need in such way that first getting the proper tools for each human'' second subtask; second, getting the proper tools for each human's s third subtask; and finally getting the proper tools for each human's last subtask. Mobile robots are also clever such that the green robot focuses delivering tools to two workshops (0 and 2) and gives the priority to the faster human in workshop-0, meanwhile, the blue robot mainly focuses assisting the human-l in workshop-I (W-1) by delivering the correct tools one by one in time, but also helps delivering one tool to human-2.
Tool Room
WW22
(a) Initial State.
(b) Arm robot executes Search- Tool(O) to find Tool-O, two mobile robots are moving towards robot. Blue robot waits there for the table by running Get-Tool.
Arm robot executes Pass-to- M(0) to pass Tool-O green
tools.
(d) Green robot runs Go- W(O) to deliver Tool-0 the faster human, and arm robot executes Search- Tool(O) to find the Tool-O.
(e) Green robot successfully deliv- Tool-O human-0, and robot still under execution of previous macro-action.
(f) Arm robot executes Pass-to- M(I) give Tool-O blue robot, and green robot goes check human-2's status by running Go- W(2).
(g) Arm robot executes Search- Took(O) to find the 3rd Tool- towards workshop-1 by running Go- (Q) and green robot runs Get-Tool to go back arm robot.
(h) Arm robot executes Search- Tool(I) to find Tool-1. Mobile robots continue running the previ- ous macro-actions.
(i) Blue robot successfully deliv- ers Tool-O to human-l, and green robot waits there for next tool. Arm robot is under execution of previous macro-action
Blue robot
(i) Blue robot goes back table by running Tool.
(k) Arm robot passes the last Tool-
()) Arm robot executes Pass-to- M(0) again to give Tool-1 to green robot, and blue arrives table and waits for next tool.
0 to the green robot by execut- ing Pass-to-M(O), and blue robot
under the execution Get- Tool.
36

---

Under review as a conference paper at ICLR 2022
(m) Green rohot runs Go- (() first deliver Tool-1 to faster human, and arm rohot executes Search-Tool(I) to find the 2nd Tool-1.
(n) Green robot successfully de- livers Tool-1 to human-O, and arm rohot is still searching for Tool-1.
Arm robot executes Search- Tool(I) again to find last Tool-1, meanwhile, green robot successfully delivers Tool-0 to human-2 by running Go- W(2).
(p) Green robot Ge-W(I) to check the status human-1.
(q) Arm robot executes Pass-to- M(1) give Tool-1 blue robot, and green robot runs Get-Tool to go back table.
(r) Arm robot executes Pass-to- M(1) again to give the last Tool-1 to blue robot, now blue robot carries two Tool-1s.
(s) Arm robot executes Search- Tool(2) to find Tool-2. Green robot waits there for next tool, blue robot moves towards workshop-1 by running Go- (()) for delivery.
(t) Blue robot delivers Tool-1 to
(u) Arm robot executes Pass-to- M(0) give Tool-2 to green robot, and blue robot runs Go- ((-) send Tool-1 to workshop-2.
human-1 in time.
(v) Arm robot executes Search- Tool(2) find the 2nd Tool-2.
(w) Blue robot arrives at (x) Blue robot goes back tool
workshop-O to check the status
by running Get-Tool, and human-O by running Go)W(O), arm robot is under execution and am robot is still looking for Pass-to-M(OO.
Green robot keeps waiting there
for more tools by running Get- Tool again, and blue robot delivers Tool-1 to human-2 2 in time.
the 2nd Tool-2.
37

---

Under review as a conference paper at ICLR 2022
(y) Arm robot passes the 2nd Tool-2 green robat by execut- ing Pass-to-M(0)) and now green robot carries two Tool-2s. Blue robot is under the execution of previous macro-action.
(z) Green robot runs Go-W(O) to first send Tool-2 the faster human-O, and blue robot waits he-
(A) Green robot delivers Tool-2
human-O in time.
side tahle for next tool. Arm
robot executes Search-Tool(2) to find last Tool-2.
(B) Arm robot passes last Tool-2 to blue robot by execut- ing Pass-to-M(1). Green arrives workshop-2 right after human-2 finishes the second subtask and is going to start working on next subtask. According to the dynam- ics setup, at this timestep, human- 2 cannot possess the Tool-2 from the green robot.
(C) Green robot then goes to
(D) Blue robot arrives at
workshop-1 send Tool-2 to
workshop-1 and observes that
human-1 by exccuting Go-
human-1 has already obtained the last tool he needs. Blue robot
and successfully delivers it to human-l. Blue robot cannot ob-
decides send the Tool-2 human-2 by running Go- G(2).
serves this so still executes
Go- W(I) to send Tool-2 to human- 1.
(E) Blue robot successfully deliv- ers Tool-2 human-2. Humans have received all tools, and for robots, the task is done.
38

---

Under review as a conference paper at ICLR 2022
A.5 HYPER-PARAMERR PARAMETERS
In following subsections, we first list the hyper-parameier candidates used for tuning each method via grid search in the corresponding domain, and then show the hyper-parameter table with the parameters used by each method achieving the best performance. We choose the best performance of each method depending on its final converged value the first priority and the sample efficiency as the second.
A.5.1
BOx PUSHING
Table I: Hyper-parameter candidates for grid search tuning.
learning rate pair (actor,critic)
(Ie-3,3e-3), (1e-3,1e-3] (5e-4,3e-3), (5e-4,le-3) (5e-4,ee-4), (3e-4,3e-3) 16, 32
Episodes per train Target-net update freq (episode)
32, 64, 128 0, 3,5 5
N-step TD
Table 2: Hyper-parameter candidates for grid search tuning.
learning rate pair (actor,critic)
(1e-3,3e-3), (1e-3, le-3) (5e-4,3e-3), (5e-4,1e-3) (5c-4,5e-4), (3c-4,3e-3)
Episodes per train Target-net update freq (episode)
48
48, 144
N-step TD
0, 3, 5
Table 3: Hyper-parameters used for methods in Box Pushing 6 6.
Parameter
IAC
CAC
Mac-IAC
Mac-CAC
Mac-NIACC
Mac-IAICC
Training Episodes
40K
40K
40K
40K
40K
40K
Actor learning rate
0.001
0.0005
0.0005
0.001
0.0005
0.0003
Critic learning rate
0.003
0.001
0.003
0.003
0.001
0.003
Episodes per train Target-net update freq (episode)
8
32
32
32
32
32
128
32
64
32
128
N-step TD
5
3
0
0
Estart
1
1
1
Cend
0.01
0.01
0.01
0.01
0.01
0.01
(decay (episode)
4K
4K
4K
4K
4K
4K
Table 4: Hyper-parameters used for methods in Box Pushing 8 8.
Parameter
IAC
CAC
Mac-IAC
Mac-CAC
Mac-NIACC
Mac-TAICC
Training Episodes
40K
40K
40K
40K
40K
40K
Actor learning rate
0.001
0.001
0.0005
0.0003
0.0005
0.0003
Critic learning rate
0.003
0.003
0.003
0.003
0.001
0.003
Episodes per train Target-net update freq (episode)
48
32
32
32
32
128
48
32
128
64
N-step TD
0
Estart
1
1
Cend
0.01
0.01
0.01
0.01
0.01
0.01
(decay (episode)
4K
4K
4K
4K
4K
4K
39

---

Under review as a conference paper at ICLR 2022
Table 5: Hyper-parameters used for methods in Box Pushing 10 x 10.
Parameter
IAC
CAC
Mac-IAC
Mac-CAC
Mac-NIACC
Mac-IAICC
Training Episodes
40K
40K
40K
40K
40K
40K
Actor learning
0.001
0.001
0.001
0.0005
0.0005
0.0003
Critic learning rate
0.003
0.003
0.001
0.001
0.001
0.003
Episodes per train Target-net update freq (episode)
16
32
32
32
64
128
32
128
128
32
N-step TD
0
3
3
Estart
Cend
0.01
0.01
0.01
0.01
0.01
0.01
Edecay (episode)
6K
6K
6K
6K
6K
6K
Table Hyper-parameters used for methods in Box Pushing 12
Parameter
IAC
CAC
Mac-IAC
Mac-CAC
Mac-NIACC
Mac-IAICC
Training Episodes
40K
40K
40K
40K
40K
40K
Actor learning rate
0.001
0.001
0.001
0.001
0.0005
0.0003
Critic learning rate
0.003
0.003
0.003
0.003
0.0005
0.003
Episodes per train Target-net update freq (episode)
16
8
48
48
128
128
128
128
144
N-step TD
3
Estart
1
fend
0.01
0.01
0.01
0.01
0.01
0.01
<decay (episode)
6K
6K
6K
6K
6K
6K
Table 7: Hyper-parameters used for methods in Box Pushing 14 14.
Parameter
IAC
CAC
Mac-IAC
Mac-CAC
Mac-NIACC
Mac-IAICC
Training Episodes
40K
40K
40K
40K
40K
40K
Actor learning rate
0.001
0.001
0.001
0.001
0.0005
0.0005
Critic learning rate
0.003
0.003
0.001
0.001
0.0005
0.003
Episodes per train Target-net update freq (episode)
8
16
128
128
32
128
128
48
N-step TD
3
Estart
1
1
Gend
0.01
0.01
0.01
0.01
0.01
0.01
(decay (episode)
8K
8K
8K
8K
8K
8K
40

---

Under review as a conference paper at ICLR 2022
A.5.2 OVERCOOKED
Table 8: Hyper-parament candidates for grid search tuning.
learning rate pair (actor,critic) Episodes per train
(Ie-4, 3e-3) (3e-4,3e-3)
4
Target-net update freq (episode)
16, 32
N-step TD
3, 5
Table 9: Syper-parameter candidates for grid search tuning.
learning rate pair (actor,critic) Episodes per train
(Ic-4, 3e-3) (3c-4,3e-3) 8, 16
Target-net update freq (episode) N-step TD
16, 32, 64
3, 5
Table 10: Syyper-paramteer used for methods in Overcooked-A.
Parameter
IAC
CAC
Mac-IAC
Mac-CAC
Mac-NIACC
Mac-IAICC
Training Episodes
100K
100K
100K
100K
100K
100K
Actor learning rate
0.0003
0.0003
0.0003
0.0001
0.0003
0.0003
Critic learning rate
0.003
0.003
0.003
0.003
0.003
0.003
Episodes per train Target-net update freq (episode)
16
4
16
4
8
8
64
16
32
8
16
32
N-step TD
5
5
5
5
Cstart
1
1
0.05
0.05
0.05
0.05
0.05
0.05
Edecay (episode)
40K
40K
40K
40K
40K
40K
Table 11: Hyper-parameters used for methods in Overcooked-B.
Parameter
IAC
CAC
Mac-IAC
Mac-CAC
Mac-NIACC
Mac-IAICC
Training Episodes
100K
100K
100K
100K
100K
100K
Actor learning rate
0.0003
0.0001
0.0003
0.0001
0.0003
0.0003
Critic learning rate Episodes per train Target-net net update freq (episode)
0.003
0.003
0.003
0.003
0.003
0.003
8
8
8
8
32
16
64
16
32
N-step TD
5
5
5
3
Estart
fend
0.05
0.05
0.05
0.05
0.05
0.05
Edecay (episode)
40K
40K
40K
40K
40K
40K
41

---

Under review as a conference paper at ICLR 2022
Table 12: Hyper- used for methods in Overcooked-C.
Parameter
IAC
CAC
Mac-IAC
Mac-CAC
Mac-NIACC
Mac-IAICC
Training Episodes
100K
100K
100K
100K
100K
100K
Actor learning rate
0.0003
0.0003
0.0003
0,0001
0.0003
0.0003
Critic learning rate
0.003
0.003
0.003
0.003
0.003
0.003
Episodes per train Target-net update freq (episode)
16
8
16
4
16
4
64
32
32
32
64
32
N-step TD
5
5
5
3
Estart
1
1
1
1
fend
0.05
0.05
0.05
0.05
0.05
0.05
(decay (episode)
40K
40K
40K
40K
40K
40K
A.5.3
WAREHOUSE TOOL. DELIVERY
Table 13: Hyper-parametee candidates for grid search tuning.
learning rate pair (actor,critic) Episodes per train
(1e-3,1e-3), (5e-4, le-3) (5e-4,5e-4) (3e-4.3e-3)
Target-net update freq (episode)
8, 16, 32, 64 0, 5
N-step TD
Table 14: Hyper-parameter candidates for grid search tuning.
learning rate pair (actor,critic) Episodes per train
(le-3,1e-3), (5e-4, 1e-3) (5e-4,5e-4) (3e-4,3e-3)
16
Target-net update freq (episode)
16, 32, 64
N-step TD
0, 3, 5
Table 15: Hyper-parameters used for methods in Warehouse-A.
Parameter
Mac-IAC
Mac-CAC
Mac-NIACC
Mac-IAICC
Training Episodes
40K
40K
40K
40K
Actor learning rate
0,0005
0.0003
0.0003
0.0005
Critic learning rate
0.0005
0.003
0.003
0.0005
Episodes per train Target-net update freq (episode)
16
64
16
64
N-step TD
5
Estart
1
Eend
0.01
0.01
0.01
0.01
Edecay (episode)
10K
10K
10K
10K
42

---

Under review as a conference paper at ICLR 2022
Table 16: pyper-parameters used for methods in Warehouse-BB
Parameter
Mac-IAC
Mac-CAC
Mac-NIACC
Mac-IAICC
Training Episodes
90K
90K
90K
90K
Actor learning rate
0.0005
0.0003
0.0003
0.0003
Critic learning rate
0.0005
0.003
0.003
0.003
Episodes per train Target-net update freq (episode)
8
8
4
4
32
64
N-step TD
5
5
Estart
1
fend
0.01
0.01
0.01
0.01
Edocay (episode)
10K
10K
10K
10K
Table 17:
used for methods in Warehouse-C.
Parameter
Mac-IAC
Mac-CAC
Mac-NIACC
Mac-IAICC
Training Episodes
90K
90K
90K
90K
Actor learning rate
0.0005
0.0005
0.0003
0.0003
Critic learning rate Episodes per train Target-net update freq (cpisode)
0.001
0.001
0.003
0.003
4
4
4
64
64
N-step TD
5
5
Cstar
1
Eend
0.05
0.05
0.05
0.05
Edecay (episode)
10K
10K
10K
10K
43


Reviews:
[{"review_id": "WNtCytoVtH", "reviewer": "Reviewer_jJtb", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "Strengths:\nThe paper focuses on a domain that is common in practice but not well studied, and the proposed methods show clear improvements. \n\nWeakness:\nThe major concern I have is the lack of comparison on other macro-action-based methods (like those mentioned in the third paragraph in section 1). The proposed extensions are natural generalizations from their original forms (which could be a strength), and improvements are expected when compared with methods not designed for the Mac-POMDP.  It would be more interesting to see the comparisons with methods designed for the same domain.", "summary_of_the_paper": "The paper proposes several extensions of the existing multi-agent independent actor-critic, centralized actor-critic, and independent actor with centralized critic to the MacDec-POMDP for solving multi-agent problems with asynchronous actions. The proposed methods show significant improvements compared with their original forms in several MacDec-POMDP problems.", "summary_of_the_review": "While the technical contribution and the experiment results are, in my opinion, not super significant, the paper indeed introduces a practical research direction and brings several intuitive first steps towards this direction. Thus, I recommend acceptance of the paper.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "ST6Q_tEkI2l", "reviewer": "Reviewer_Exb6", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "The paper gives a relatively clear definition of the domain of interest and its value/applicability. The algorithms are mostly clear and seem sensible. There is some significant novelty in the use of central critics with independent gradients particularly when those central critics have to be individualised. The need for centralisation does limit this in the number of agents that can be coordinated though and this could be more clearly commented on. The experiments comparing macro-action based methods are clear and well interpreted with some interesting findings. Finally, for the strengths, I do think that these methods may have some viability for use in industrial applications.\n\nThere are a couple of things that I think weaken the paper. The first of these is quite general and relates to the framework in which all this is being done. There seems to be an unusual asymetry to how the two levels of the action hierarchy are treated. There are different policies of course, but the action sets are strictly macro actions, which means that all primitive action decisions must be part of an option. This has implications for generalisation across the same task or from one task to another, as it forces the option to contain both reusable skill information as well as global task information. More surprising to me, observations are split into low level and high level and I cannot see the justification for that. One consequence of this asymmetry emerges in the tested environments. For instance the box pushing environment requires macro actions of length 1 to be defined, which mimic three of the primitive actions.\n\nA second weakness of the paper relates to the ambiguity in some of the descriptions. In particular, the definition of squeezed trajectories and how these are incorporated into each of the proposed algorithms could be much clearer. Another thing that could be clearer is that this paper presents methods for the macro-actions and how to induce coordination with these. It doesn't address how the options might be learned or developed, nor how such things as initiation sets and termination conditions should be defined - a non-trivial thing see (Jong et al., 2008) . As such there is a serious gap between what is proposed here and the use of these methods in practice. See (Konidaris and Barto, 2007; Bacon et al. , 2017) for examples of works which might address this concern.\n\nFinally, there is a weakness in the experiments in terms of fair comparison. In the experiments, there is quite a lot of pre-encoded knowledge in the macro actions. Not least the one-step macro actions, but also examples like: the get-tomato-like actions in the Overcooked domain, or the Move-to-big-box action in the Box Pushing. It seems to me that these options are already predefined as deterministic policies, as no reward structure is given to these nor is there a mechanism for propagating global rewards back in time to relevant option executions (a better approach). Am I right that these macro action methods are given their options at the start? In which case, the comparison between macro-action based methods (Mac-CAC, Mac-IACC and Mac-IAICC) and primitive action based methods (IAC and IACC) would be demonstrably biased towards the macro-action based methods. I would argue that this knowledge injection is at least partly responsible for the big difference between the two types of methods seen in Figure 3. A fairer comparison would be to have options learned as they go for the macro-action methods.\n\n## Notes\n\nSome more detailed notes/comments are as follows:\n\nIn Sec 2, what is mathbb H in the definitions? And why does this relate to finite horizon? Ah, is it an integer? This could be clearer.\n\nThe authors state that:\n> asynchronicity of macro-action execution over agents, where agents may start and complete their own macro-actions at different time-steps\n\nBut argue that:\n> Previous deep MARL methods for Dec-POMDPs cannot work in this case as they are all based on primitive actions synchronously executed by agents.\n\nHowever the formulism given in section 2 does model joint actions at each time step which are cross products over all agents in the task. So the primitive actions are taken synchronously (at least as treated by the environment). This should be clarified.\n\nThe explanation of squeezed trajectories in Sections 2.5 and 3 are not clear enough. I would recommend the authors include some mathematical equations or definitions to make this clearer.\n\nIn Equation (8) it's not clear how the $\\vec{h}$ and $\\vec{m}$ objects are constructed. As argued already, the macro actions are initiated and terminated asynchronously but the $\\vec{m}$ is a joint macro action, so what is that? For instance, at primitive time $t$, does the joint macro action use all the options that agents are in, even if they initiated this some steps ago? How does this asynchronicity influence the convergence properties of the critic and policy gradient optimisation?\n\nIt seems odd that you need to explicitly manufacture exploration decay. You say:\n> Exploration is deployed by applying a linear decaying $\\epsilon$-soft policy.\n\nBut the actor-critic paradigm is one which, it is argued, controls the exploration/exploitation trade-off. This should really be justified more clearly in the paper.\n\n## References\n(Jong et al., 2008) Nicholas K. Jong Todd Hester Peter Stone (2008). The Utility of Temporal Abstraction in Reinforcement Learning. AAMAS 08.\n(Konidaris and Barto, 2007) George Konidaris and Andrew Barto (2007). Building Portable Options: Skill Transfer in Reinforcement Learning.\n(Sutton et al., 1999) Richard Sutton, Doina Precup, and Satinder Singh (1999). Between MDPs and Semi-MDPs: A Framework for Temporal Abstraction in Reinforcement Learning. Artificial Intelligence 112:181–211.\n(Bacon et al. , 2017)  Pierre-Luc Bacon, Jean Harb and Doina Precup (2017). The Option-Critic Architecture. AAAI 2017.", "summary_of_the_paper": "The paper presents a method for learning policy gradient based methods on macro-actions in environments where multiple agents initiate and terminate actions at different timesteps. The paper identifies a suitable framework (MacDec-POMDPs) for these tasks and develops a series of actor-critic mechanisms to allow agents to coordinate asynchronous macros actions. Four main macro-action algorithms are proposed:\n* Mac-IAC - that applies a variance reduced version of actor critic directly to the multi-agent domain\n* Mac-CAC - which treats all agents as a single global agent\n* Mac-IACC - described as naive, which uses a centralised critic but derives independent policy gradients for each agent\n* Mac-IAICC - which again uses a centralised critic like mechanism but one where the termination times of the individual agent correct the traces used to train this central critic. Again this derives independent policy gradients for each agent.\n\nThe experimental section presents three models: box pushing, overcooked and warehouse. From my reading of the paper, these models provide predefined options to all agents (so all agents have access to all options), where some options are extended and some are single step. Rewards are defined that are broadcast to all agents, and are used to learn the coordination policy (high level) but not the low level options, in the case of the macro action algorithms. Two non-macro action methods are evaluated against Mac-IAC and Mac-CAC on Box-pushing and Overcooked. This finds that macro-action methods are better than the primitive action methods (less interesting - see notes) and that there are situations in which Mac-IAC is better but more typically Mac-CAC outperforms Mac-IAC when there is a significant need for coordination. The next series of experiments compares the four macro-actions methods and show (most pertinantly) that the Mac-IAICC method achieves better coordination than Mac-IAC, nearing the performance of Mac-CAC even in the most coordination intensive conditions. Naive Mac-IACC improves upon Mac-IAC in terms of coordination but suffers in coordination intensive tasks. This supports the authors' argument that the variance in the shared critic for Naive Mac-IACC is damaging and that the proposed individual centralised critic approach for Mac-IAICC significantly improves upon this.", "summary_of_the_review": "The main contribution is relatively interesting and contains some novelty. It is a challenging domain and there is a clear industrial application for those that can get this right. I think there are some weaknesses in explanations and definitions in the main paper which weaken it though. The interpretation of the  experiments as it relates to macro-action methods is clear and insightful and convinces me that there is value in these ideas. However, the comparison with individual action methods does not acknowledge the high level of manual code/knowledge injection that favours the macro action methods. As such, I am falling below the acceptance threshold for this paper. However, I would encourage the authors to continue with the work as it is interesting and promising.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "M1lqX0c44iq", "reviewer": "Reviewer_7V3B", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "**Pros**:\n* Writing: The writing in the paper was largely clear.\n* Experimental setup: The experimental setup was exhaustive and the 3 environments used to evaluate the framework was interesting.\n\n**Cons**:\n* Presentation of the Mathematical ideas: In Section 3, the presentation of the framework could have been made clearer. Upon reading the update rule for the policy gradient in the new framework, It was non-trivial to get the intuition behind the formulation. Perhaps some more discussion on the differences between IAC/CAC algorithms to the presented framework could bring out the fundamental changes in a formulation more clearly. I think at least the algorithmic block pertaining to MAC-IAC can be brought to the main paper from the appendix, as it is the first time the new framework is being presented. The following subsections of Section 3, where MAC-CAC and MAC-IACC are introduced can include more intuitive discussions on how each technique differs in their update equations. At the moment, this section is a little difficult to parse.\n\n* Novelty: The presented framework is interesting but still requires additional work in its analysis -- such as the limitations of the gradient updates, sample efficiency of the proposed methods, and uniform framework for analysis of the 3 proposed variants. At the moment, the framework shows potential but can be refined further.\n\n* Baselines used: I felt the baselines used for comparison were limited to the presented techniques and primitive action-based techniques. How do the algorithms presented under primitive actions fair when they are also presented with high-level macro actions in their action set? This might be a fairer comparison to evaluate the technique upon. I am also curious to know how the presented framework performs in an adversarial/competitive setting. Is this framework even applicable in such a setting?\n\n**General Comments**\nOverall, the presented ideas show promise in scaling up asynchronous learning of macro-action-based multi-agent policies in cooperative environments. However, at the moment the presentation of the paper can be improved and the ideas presented need to be elaborated upon further. The extension seems only incremental at the moment. The experimental framework presented seems exhaustive in the cooperative setting though.\n\n*Originality*: Moderate\n\n*Clarity*: Moderate\n\n*Quality*: Moderate\n\n*Significance*: Moderate to High", "summary_of_the_paper": "The paper tackles the problem of learning asynchronous multi-agent policies with macro-actions. The authors present a set of asynchronous multi-agent Actor-Critic methods in order to solve the problem, which allows agents to `directly' optimize policies that are asynchronous and macro-action based. They apply the framework in 3 standard multi-agent learning paradigms: decentralized learning, centralized learning and centralized learning for decentralized execution. They also empirically show the utility of the methods over the standard individual actor-critic method and centralized actor-critic method on 3 multi-agent cooperative tasks: Box pushing, Overcooked and Warehouse.", "summary_of_the_review": "Overall the paper showed promise in scaling up the learning of asynchronous macro-action-based multi-agent policies. However, it still requires further work in improving the presentation and performing elaborate analysis of the framework on the three settings discussed -- such as limitations of the gradient updates derived. The work seems to be only incremental in comparison to prior work. Hence, I am inclined to reject it at the moment.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "6VXXxXPXZrl", "reviewer": "Reviewer_fiq5", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "•\tStrengths:\n\nThis paper considers an important problem of asynchronism of action in MARL. The main contribution of this paper is integrating the macro-action-value from the Q-value-based macro-action MARL method into multi-agent policy gradient. \n\n•\tWeaknesses: \n\nThe reviewer has some concerns of this paper:\n1.\tWhat is asynchronism in MARL? Can you define it in this paper? The main concern of this paper is that it introduces the asynchronism of actions in MARL, however, with macro-actions which is built on top of the option in hierarchical RL, this paper mainly introduces a MARL method with macro-action. The main concern is it seems the proposed methods are off-topic \n2.\tThe integration of macro-action-value from previous MARL work is straightforward, the main challenge has been discussed in Xiao et al., 2019. This may make the integration a bit weak. Or can the author highlight the challenge in the paper?\n3.\tEnvironmental scenarios evaluated in the experimental section are mainly on hierarchical MARL and multi-task MARL, it hard to find the asynchronism of actions in these scenarios, which is the main contribution of this paper.\n4.\tThere some hierarchical MARL methods [1, 2, 3, 4, 5], and some role-learning [6] methods, can you also compare the proposed methods with some of these methods and discuss these methods?\n5.\tIt seems that related works on asynchronism of actions in MARL is missing.\n\nReference:\n\n[1] Hierarchical Cooperative Multi-Agent Reinforcement Learning with Skill Discovery\n\n[2] Feudal Multi-Agent Hierarchies for Cooperative Reinforcement Learning\n\n[3] Multi-Agent Common Knowledge Reinforcement Learning\n\n[4] OPtions as REsponses: Grounding Behavioural Hierarchies in Multi-Agent Reinforcement Learning\n\n[5] HAVEN: Hierarchical Cooperative Multi-Agent Reinforcement Learning with Dual Coordination Mechanism\n\n[6] RODE: Learning Roles to Decompose Multi-Agent Tasks\n\n", "summary_of_the_paper": "This paper considers the problem of MacDec-POMDPs where it requires agents to be capable of performing asynchronously without waiting for other agents to terminate. As there is no multi-agent policy gradient method with macro-actions for MacDec-POMDPs, this paper fill this gap and integrates the macro-action-value into multi-agent policy gradient and proposes (i) macro-action-based independent actor-critic (Mac-IAC) method, (ii) macro-action-based centralized actor-critic (Mac-CAC) method, (iii) Naive Independent Actor with Centralized Critic (Naive IACC) as well as Independent Actor with Individual Centralized Critic (Mac-IAICC) via CTDE. Experimental results show that the proposed methods outperforms vanilla baselines.", "summary_of_the_review": "The writing is ok. This is paper is easy to follow. It would be great if the author can make videos to visualize the learned results presented in the appendix. I would like to increase the score to Week Accept if the authors can address the above concerns during the review session.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper provides an "asynchronous" method for multi-agent actor-critic with macro-actions. A major contribution of this paper is the integration of the macro-action-value from the Q-value-based macro-action MARL method into multi-agent policy gradient. Although it appears an interesting contribution, reviewers found that several parts of the paper were not clear enough and there is a lack of fair comparison with previous works.
Decision: Reject