Asynchronous Actor-Critic for Multi-Agent Reinforcement Learning
Authors: Yuchen Xiao
Weihao Tan
Christopher Amato
Venue: NeurIPS 2022 Accept (2022)

Abstract: Synchronizing decisions across multiple agents in realistic settings is problematic since it requires agents to wait for other agents to terminate and communicate about termination reliably. Ideally, agents should learn and execute asynchronously instead. Such asynchronous methods also allow temporally extended actions that can take different amounts of time based on the situation and action executed. Unfortunately, current policy gradient methods are not applicable in asynchronous settings, as they 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 policies in three standard training paradigms: decentralized learning, centralized learning, and centralized training for decentralized execution. Empirical results (in simulation and hardware) in a variety of realistic domains demonstrate the superiority of our approaches in large multi-agent problems and validate the effectiveness of our algorithms for learning high-quality and asynchronous solutions. 

Asynchronous Actor-Critic for Multi-Agent Reinforcement Learning
Yuchen Xiao
Weihao Tan
Khoury College of Computer Sciences
Khoury College of Computer Sciences Northeastern University Boston, MA 02115
Northeastern University
Boston, MA 02115
xiao x www..uuucccnoothhsterr...
w. www.anootteeetternncnom
Christopher Amato
Khoury College of Computer Sciences Northeastern University
Boston, MA 02115
c. amatoohhortheasterm.cco
Abstract
Synchronizing decisions across multiple agents in realistic settings problematic since it requires agents to wait for other agents to terminate and communicate about termination reliably. Ideally, agents should learn and execute asynchronously instead. Such asynchronous methods also allow temporally extended actions that can take different amounts of time based on situation and action executed. Unfortunately, current policy gradient methods are not applicable in asynchronous settings, as they assume that agents synchronously reason about action selection at every time step. To allow asynchronous learning and maaisinnmmaiin, formulate a set of asynchronous multi-agent actor-critic methods that allow agents directly optimize asynchronous policies in three standard training paradigms: decentralized learning, centralized learning, and centralized training for decen- tralized execution. Empirical results (in simulation and hardware) in variety of realistic domains demonstrate the superiority of our approaches in large multi-agent problems and validate the effectiveness of our algorithms for learning high-quality and asynchronous solutions.
Introduction
In recent years, multi-agent policy gradient methods using the actor-critic framework have achieved
impressive success in solving variety of cooperative and competitive domains [Baker et al. 2020
2019 Lowe et al. Du et al. 2019 Foerster et al. 2018 Du et al. 202T labal and Sha 2019 Li et al.
2017
Su et
al. 2021 Vinyals et 2019 Wang et 2020a 202 Yang et al. 2020a Zhou et al.
2020
However, as these methods assume synchronized primitive-action execution over agents, they
struggle to solve large-scale real-world multi-agent problems that involve long-term reasoning and asynchronous behavior.
Temporally-extende actions have been widely used in both learning and planning to improve scala- bility and reduce complexity. For example, they have come in the form motion primitives [Dalal et al.
2021 Stulp and Schaal 2011]. skills [Konidaris et al.) [001] 2018), spatial action maps [W He et al.) 2010 [Hsiao et al. 2010 Lee et al. 2021 Theocharous and actions has also been incorporated into multi- agent approaches. In particular, we consider the Macro-Action Decentralized Partially Observable
et al. 2020 or macro-actions
Kaelbling 2004]. The idea of cemporally-extendee
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Markov Decision Process (MacDec-POMDP) [Amato et al., 2014 2019]. The PeMMP a general model for cooperative multi-agent problems with partial observability and (potentially) different action durations. As a result, agents can start and end macro-actions at different time steps so decision-making can be asynchronous.
The MacDec-POMDP framework has shown strong scalability with planning-based methods (where the model is given) Amato et al. 2015a Hoang al. 2018 Omidshalici et al. 2016 2017a| In
terms of multi-agent reinforcement learning (MARL), there have been many hierarchical approaches, they don't typically address asynchronicity since they assume agents' have high-level decisions with the same duration Ide Witt et al. [2099] Han et al. 2019 Nachum et al, 2019 Wang et al.
2020b 2021b [Xu et al., [222]] et al. 2020b]. Only limited studies have considered asynchronic-
ity [Chakravorty et al.
2019 Menda et al. 2019 Xiao et al.) 2019]. yet, none of them provides a
general formulation for multi-agent policy gradients that allows agents to asynchronously learn and
execute.
In this paper, we assume a set of macro-actions has been predefined for each domain. This is well- motivated by the fact that, in real-world multi-robot systems, each robot is already equipped with certain controllers (e.g., navigation controller, and a manipulation controller) that can be modeled
as macro-actions [Amato et al., 2015a Omidshafiei et al. 2017a] Wu et al. 2021 a Xiao et al.) 2019]. Similarly, as it is common to assume primitive actions are given a typical RL domain, we assume the macro-actions are given in our case. The focus of the policy gradient methods is then on learning high-level policies over macro-actions!
Our contributions include a set of macro-action--aase multi-agent actor-critic methods that generalize their primitive-action counterparts. First, we formulate iincro-action-bueee independent actor-critic (Mac-IAC) method. Although independent learning suffers from a theoretical curse of environmental non-stationarity, it allows fully online learning and may still work well in certain domains. Second, we introduce a macro-action- -bsied centralized actor-critic (Mac-CAC) method, for the case where full communication is available during execution. We also formulate a centralized training for decentralized execution (CTDE) paradigm [Kaamme and Banerjee 2016 Olichock et al., 2008 variant of our method. CTDE has gained popularity since such methods can learn better decentralized policies by using centralized information during training. Current primitive-action accti---bto-- 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 's decentralized perspective. To this end, we first present a Naive Independent Actor with Centralized Critic (Naive IACC) method that naively uses a joint macro-action-vall -vauue function as the critic for each actor's 's policy gradient estimation; and then propose novel Independent Actor with Individual Centralized Critic (Mac-IAICC) method that learns individual critics using centralized information to address the above challenge.
We evaluate our proposed methods on diverse mucro-action- basdd multi-agent problems: a benchmark Box Pushing domain [Xiao et al. 2019) a variant of the Overcooked domain (Wu et al., 20216] and a larger warehouse service domain [iiao et al., 2019 Experimental results show that our methods are able to learn high-quality solutions while primitive-action- based methods cannot, and show the strength of Mac-IAICC for learning decentralized policies over Naive IAICC and Mac-IAC. Decentralized policies learned by using Mac-IAICC are successfully deployed on real robots to solve a warehouse tool delivery task in efficient way. To our knowledge, this is the first general formalization of macro-action-ban based multi-agent actor-critic frameworks for the three -tate-of-the-art multi-agent training paradigms.
2 Background
2.1 MacDec-POMDPs
The macro-action decentralized partially observable Markov decision process POMDP) [Amato et al. 2014 2019] incorporates the option framework (Sutton et al. 1999 into the Mec-POMDP by defining a set of macro-action actions for each agent. Formally, a DecPDDD is defined by a tuple (T, S, A, M, Ω C, T, R, O, 7, 7), where / is set of agents; S is the environ-
(MacDec-
'Our approach could potentially also be applied to other models with temporally extended actions Omid shafiei et al. 2017a
2

---

mental state space; A = Xier is the joint primitive-action space over each agent's primitive-action set A; M- AM; is the joint macro-action space over each agent's macro-action space M; Ω = xiens is the joint primitive-observatonn space over each agent's 's primitive-observation set D4 <= Xier<; the joint macro-observation space over each agent's macro-observation space 5: T() = P(s'le (s. a) is the environmental transition dynamics; and R(s, ā) is global re- ward function. During execution, each agent independently selects a macro-action my using a high-level policy w; 11,4 x M; + [0, and captures macro-observation =j Ç according to the macro-observation probability function (2,, m4 = P(z: m, 5') when the macro-action terminates in state s'. Each macro-action is represented
m, (Im,, Tm,, pm;): where the initiation set I,, C H.M defines how to imitiate a macro-action based on maaro--bserrvttion-tne history H.M at the high-level; km, H.A x A; + [o. 1] is the low-level policy for achieving a macro-action, and during the running, the agent receives a primitive-observation og E Ω based on the observation function O,(o;, 0; 5) = P(o,la,, s) at every time step; 3m: : H,a + [0, 1] is stochastic termination function that determines how to terminate a macro-action based on primitive-obeeraaionn-tttt history 11, at the low-level. The objective of solving MacDec-POMin
with finite horizon is to find a joint high-level policy v = Xier V that maximizes the value, $(0): गł, _ where r E [0, 1] is a discount factor, and H is the number of (primitive) time steps until the problem terminates (the horizon).
v (s)) = oo ((r(s())
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 The via gradient ascent the policy's s performance defined as (0) = Emo Ei
(o)] In POMDPs, the gradient w.r.t parameters of a
history-based policy (a h) is expressed as: JJJ = E V log (a Q)) (h, aa) where
is maintained by a recurrent neural network (RNN) [Hausknecht and Stone 2015). The actor-critic framework (Konda and Tsitsiklis 2000 learns on-policy action-value function Q (h, a) (critic)
via lemporalddifeeence (TD) learning [Sutton 1988 to approximate the action-value for the policy (actor) updates. Variance reduction is commonly achieved by training a history- vvaue function V (h) and using it as a baseline (Weaver and Tao [00T as well as bootstrapping to estimate the action-value. Accordingly, the policy gradient can written as:
(0) = E V
()) + VV (h²) - Va (h))
w
where, is the immediate reward received by the agent at the corresponding time step.
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 variance reduction version of independent actor-critic (IAC) with the policy gradient as follows:
((,)) = Exg Vo, log To, (a,(h:)( 7 VV (K)) - V (h.))
where, r is a shared reward over agents at every time step. 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 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 in independent learning approaches, centralized training for decentral- ized execution (CTDE) provides agents with access to global information during offline training while allowing agents to rely on only local information during online decentralized execution. Typically, the key idea of exploiting CTDE with actor-critic is train a joint action-vall value function, O (x, a). as the centralized critic and use it to compute gradients w.r.t. the parameters of each decentralized
3

---

2017 Although the centralized critic can facilitate the update of decentralized policies optimize global collaborative performance, it also introduces extra variance over other agents' actions [yy et al. 2021 Wang et al. 2021a]. Therefore, we consider the version of independent actor with centralized critic (IACC) with a general variance reduction 2021], the policy gradient of which is:
policy [Foerster et al. 2018 Lowe et al.
trick [Foerster et al. 2018, Su et al.
V. J0.) Fx Ve, log Te, (a: (r) 7 (x')
V (x))
where, x represents the available centralized information (e.g., joint observation, joint observation- action history, or the true state).
2.5 Learning Macro-Action-Bann Deep Q-Nets
Previous MARL methods for Dec-POMDPs cannot work with the asynchronicity of macro-action- based agents, where agents may start and complete their macro-actions at different time steps. Recently, macro-action-based multi-agent DQNs have been proposed for MacDec-POMDPP [Xiao
ct al. 20191.
For decentralized learning, new buffer, Macro-AAtion Concurrent Experience Replay Trajectories (Mac-CERTs), is designed for collecting each agent's 'ss macro-observation, macro-action, and reward information. In this buffer, the transition experience of each agent is represented
tuple (zi, m4, rf), where rf = Et= +Tmm-1 - r(t) is a cumulative reward of the macro-action taking Tm, time steps to be completed from its beginning time step lm.-- During training, a mini- batch of concurrent sequential experiences is sampled from Mac-CERT's. Each agent independently accesses its own sampled experiences and obtains 'squeezed' trajectories by removing the transitions in the middle of each macro-action execution, which produces a mini-batch of transitions when the corresponding macro-action terminates (i.e., removing time information). Updates for each macro-action-vallue function Qo, (hs, m4) take place only when the agent's macro-action is complete by minimizing TD loss over the 'squeezed' data. In the centralized learning case, the objective is to learn joint cer--aacctio-vuuuueeee function (h, m.. To this end, another special buffer called Macro-Action Joint Experience Replay Trajectories (Mac-JERTs) is developed for collecting agents' joint transition experience at every time step and each is represented as tuple (Z, m, z" F"), where r Et=ta -la+fa-1 (())) a shared joint cumulative reward from the beginning time step l. of the joint macro-accion m to its termination, defined as when any agent finishes its own macro-action after Fn time steps. In each training iteration, the joint macro-action-valus 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. In our antro-action-based actor-critic methods, we extend the above approaches to train critics on on-policy, and the trajectory squcezing is changed variously for each method in order to achieve improved asynchronous macro-action-bise basdd policy updates via policy gradient.
3 Approach
MARL with asynchronous macro-actions is more challenging as it difficult to determine when to update each agent's policy and what information to use. Although the macro-action-based DQN methods [Xiao et al., 2019) (in Section 2.55 give us the base to learn macro-action value functions, they do not directly extend to the policy gradient case, particularly in the case of centralized training for decentralized execution (CTDE). In this section, we propose principled formulations of on- policy macro-action-based multi-agent actor-critic methods for decentralized learning (Section 3.11. (.T). centralized learning (Section 3.2 and CTDE (Section B.3). In each case, we first introduce the version with valuee function as the critic and then present the variance reduction version
3.1 Macro-Actionn-Basee Independent Actor-Critic (Mac-IAC)
Similar the idea of IAC with primitive-actions (Section straightforward extension is to have each agent independently optimize its own macro-action based policy (actor) using local
We use h; to represent an agent's local macro-observaaiionactiioo history, and h to represent the joint history.

---

macro-action-ve action-value function (critic). Hence, we start with deriving macro-action-bass policy gradient theorem in Appendix by incorporating the general Bellman equation for the state values of
macro-action action-based policy [Sutton et al. 1999 into the policy gradient theorem in MDPs [Sutton
so that each agent can have the following policy gradient w.r.t. the parameters of its macro-action-base policy Ve, (m, as: [O,))
al. 2000], and then extend to MacDec-POMDD
Egg Ve, log "o,(m, h:)Q 2e (h;, ms) During training, each agent accesses its own trajectories
and squeezes them in the same way as the decentralized case mentioned in Section 2.3 train the critic Q%7 Vo (hg, m;) via on-policy TD learning and perform gradient ascent to update the policy when
the agent's macro- action terminates. In case, train local history value function Vi (h,) as each agent's 's critic and use it as a baseline to achieve variance reduction. The corresponding policy gradient is as follows:
Vo, ((,)) = BB, Vo, log Vo (m3 (rf + t Tm Vw: Ma, (h!) Vw:
Voo
(hul)
(4)
where, the cumulative reward rf is w.r.t the execution of agent i's macro-action my.
3.2 Macro-Action-Bassd Centralized Actor-Critic (Mac-CAC)
In the fully centralized learning case, we treat all agents as a single joint agent to learn a centralized actor ( h) with a centralized critic Q% a (h, m). and the policy gradient can be expressed as:
VoJ(0) = Ev, Ve log (m Q) (h, m) Similarly, to achieve lower variance optimization
for the actor, we learn a centralized history value function V. (h) by minimizing a TD-error loss over joint trajectories that are squeezed w.r.t. each joint macro-action termination (when any agent terminates its macro-action, defined in the centralized case in Section 2.5 Accordingly, the policy's updates are performed when each joint macro-action is completed by ascending the following gradient:
VoJ Ev, Vo log Vo(m (F + = (h/ V (f))
(5)
where the cumulative reward F w.r.t. the execution of the joint macro-action m.
3.3 Macro-Action-Based Independent Actor with Centralized Critic (Mac-IACC)
As mentioned earlier, fully centralized learning requires perfect online communication that is often hard guarantee, and fully decentralized learning suffers from environmental non-stationarity due to agents' changing policies. In order to learn better decentralized macro-action-ball policies, in this section, we propose two macro-action-basse actor-critic algorithms using the CTDE paradigm. The difference between a joint macro-action termination from the centralized perspective and a macro-action termination from each agent's local perspective gives rise to new challenge: what kind of centralized critic should be learned and how should it be used to optimize decentralized policies where some have completed and some have not, which we investigate below.
Naive Mac-IACC. A naive way of incorporating macro-actions into a CTDE-based actor-critic framework is to directly adapt the idea of the primitive-action-basse IACC (Section 2.4 to have
shared joint macro-action-valle function Q Ve (x, m) in each agent's decentralized macro-action-
based policy gradient as: Vo, J(,)) = E&g Vo, log Vo, (m: h hx)Q²
(x, m) To reduce variance,
with value function V. (x) as the centralized critic, the policy gradient w.r.t. the parameters of each agent's high-level policy can be rewritten as:
t Vo, J(O,) = Es Vo, log Vo (m, hz)(F" + + F (xx) - Vw (x))
(6)
Here, the critic is trained in the fully centralized manner described in Section while allowing to access additional global information (c.g., joint macro-observation-ateo history, ground truth
5

---

state or both) represented by the symbol x. However, updates of each agent's 's policy Vo, (m; h;) only oceur the agent's own macro-action termination time steps rather than depending on joint macro-action terminations in the centralized critic training.
Independent Actor with Individual Centralized Critic (Mac-TAICC). Note that naive Mac-IACC is technically incorrect. The cumulative reward F in Eq. 6 is based on the corresponding joint macro-action's termination that is defined as when any agent finishes its own macro-action, which
produces two potential issues: a) F + 7 Vw (xx) may not estimate the value of the macro-action 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 the aforementioned issues, we propose to learn separate centralized critic Vws (x') for
6 (xx) is computed by using the
each agent via TD TD-learning. In this case, the TD-error for updating reward rf that is 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-ben baaed policy gradient becomes:
V. Vo. (0,) B Ve, log Vo, (m4 hu) (rf + 7Tm Vw: (x)
Vw (x))
Now, from agent i's perspective, + y Vwv V for the macro-action m,, since both the reward, rf and the value function Vw: (x') depend on 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. m, 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 and take the advantage information sharing. The pscudocode and detailed trajectory squeezing process for each proposed method are presented in Appendix C
is able to offer a more accurate value prediction
Simulation Experiments
4.1 Domain Setup
(a) Box Pushing
(b) Overcooked-A
(c) Overcooked-B
(d) Overcooked Salad Recipe
Yout
W2
(e) Warchouse-A
(f) Warehouse-B
Warehouse-C
(h) Warehouse-D
Figure Experimental environments.
We investigate the performance of our algorithms over a variety of multi-agent problems with macro- actions (Fig. ID: Box Pushing [Xiao al., 2019]. Overcooked [Wu et al. 2021b), and a larger Warchouse Tool Delivery [Xiao et al.) 2019] domain. Macro-actions are defined by using prior domain knowledge they are straightforward in these tasks. Typically, we also include primitive- actions into macro-action set (as one-step macro-actions), which gives agents the chance to learn more complex policies that both when it is necessary. We describe the domains' key properties here and have more details in Appendix D
The optimal solution for the two agents is to cooperatively push the big box to the yellow goal area for a terminal reward, but partial observability makes this difficult. Specifically, robots have four primitive-actions: move forward, turn-left, turn-right and stay. In the macro-action
Box Pushing (Fig. Ta

---

case, each robot has three one-step acttoon Turn-left, Turn-right, and Stay, as well as three multi-step antrooactions: -ove-to-small-box() and Move-to-big-boxii navigate the robot to the red spot below the corresponding box and terminate with the rohot facing the box; Push causes the robot to keep moving forward until arriving at the world's boundary (potentially pushing the small box or trying to push the big one). The big box only moves if both agents push it together. Each robot can only observe the status (empty, teammate, boundary, small or big box) of the cell in front of it. A penalty is issued when any robot hits the boundary or pushes the big box alone.
Overcooked (Fig. lb Ic Three agents must learn to cooperatively prepare a eetuce-tomattoonicen salad and deliver it to the 'star' cell. The challenge is that the salad's 's recipe (Fig. [d] is unknown to agents. With primitive- achieve picking, placing, chopping and delivering by standing next to the corresponding cell and moving against (e.g., in Fig. [b] the pink agent can move right and then move up to pick up the tomato). We describe the major function of macro-actions below and full details (e.g., termination conditions) are included in Appendix D.2 Each agent's macro-action set consists of: a) five one-step macro-action that are the same the primitive ones; b) Chop, cuts raw vegetable into pieces when the agent stands next to cutting board and an unchopped vegetable is on the board, otherwise it does nothing; c) long-term navigation macro-actions: Get-Lettuce, Get- Get-Tomato, Get-Onion, Get--Plate-12. Go-Cut-Boarde and Deliver, which navigate the agent to the location of the corresponding object with various possible terminal effects (e.g., holding a vegetable in hand, placing chopped vegetable on a plate, arriving at the cell next to a cutting board, delivering an item to the star cell, or immediately terminating when any property condition does not hold, e.g., no path is found or the vegetable/plate is not found); d) Go-Counter (only available in Overcook-B, B, Fig. [c], navigates an agent to the center cell in the middle of the map when the cell is not occupied, otherwise, it moves to an adjacent cell. If the agent is holding an object or one is at the cell, the object will be placed or picked up. Each agent only observes the positions and status of the entities within a x 5 square centered on the robot.
(move up, down, left, right, and stay), agents can move around and
Warehouse Tool Delivery (Fig. le Th In each workshop (e.g.. W-0), a human is working on an assembly task (involving 4 sub-tasks that each takes number of time steps to complete) and requires three different tools for future sub-tasks to continue. A robot arm (grey) must find tools for each human the table (brown) and pass 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 robots, which has to be learned during training in order perform efficient delivery. A delayed delivery leads to a penalty. We consider variants with two or three mobile robots and two to four humans to examine the scalability of our methods (Fig. Ti Th.. We also consider one faster human (orange) to check if robots can prioritize him (Fig. g Mobile robots have the following macro-actions: Go- Go-W(i) W(i), moves to the waypoint (red) at workshop Go-TR, goes to the waypoint at the right side of the tool room (covered by the blue robot in Fig. Ig and Thp: and Get-Tool, navigates pre-allocated waypoint (that is different for each robot to avoid collisions) next to the robot arm and waits there until either receiving tool or 10 time steps have passed. The robot arm's 's applicable aeccoonctionsso are: Search-Tollii,, finds tool and places in staging area (containing at most two tools) on the table, and otherwise, it freezes the robot for the amount of time the action would take when the area is fully occupied; Pass-to-M(i), passes the first staged tool to mobile robot é; and Wait-M, waits for 1 time step. The robot arm only observes the type of each tool in the staging area and which mobile robot is waiting at the adjacent waypoints. Each mobile robot always knows its position and the type of tool that it is carrying, and can observe the number of tools in the staging area or the sub-task a human is working on only when at the tool room or the workshop respectively.
4.2 Results and Discussions
We evaluate performance of one training trial with a mean discounted return measured by periodically (every 100 episodes) evaluating the learned policies over 10 testing episodes. We plot the average performance of each method over 20 independent trials with one standard error and smooth the curves over 10 neighbors. We also show the optimal expected return in Box Pushing domain as a dash-dot line. More training details are in Appendix
Ad Advataaess of learning with macro-actions. We first present a comparison of our macro-action- based actor-critic methods against the primitive-action-basel methods in fully decentralized and fully centralized cases. We consider various grid world sizes of the Box Pushing domain (top row in Fig. 2 and two Overcooked scenarios (bottom row in Fig. 2 The results show significant performance
7

---

Mac-IAC
Mac-CAC
IAC
CAC
Box Pushing
Box Pushing 10x10
Overcoolicd
Overcooked
Resh Text Rebtuuuur
230
Moan Rettr
250
Moan Text Retur
Text Robumm.
150
-200
-10
-70
170
150
50
50
Episade
Spisode
Episode
Epiiode
Figure 2: Decentralized learning and centralized learning with macro-actions vs primitive-actions.
improvements of using macro-actions over primitive-actions. More concretely, in the Box Pushing domain, reasoning about primitive movements at every time step makes the problem intractable so the robots cannot learn any good behaviors in cemittvv-aationnbaseee approaches other than to keep moving around. Conversely, Mac-CAC reaches near-optimal performance, enabling the robots to push the big box together. Unlike the centralized critic which can access joint information, even in the macro-action case, it is hard for each robot's 's decentralized critic to correctly measure the responsibility for 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 the Overcooked domain, efficient solution requires the robots to asynchronously work on independent subtasks (e.g.. in scenario A, one robot gets a plate while another two robots pick up and chop vegetables; and in scenario B, the right robot transports items while the left two robots prepare the salad). This large amount of independence explains why Mac-IAC can solve the task well. This also indicates that using local information enough for robots to achieve high-quality behaviors. As a result, Mac-CAC learns slower because it must figure out the redundant part of joint information in much larger joint macro-level history and action spaces than the spaces in the decentralized case. The methods begin to learn, but perform poorly in such long- long-horizon tasks.
primitive-action-ban
Ad Advantages of having individual centralized crities. Fig, 3 shows the evaluation of our methods in all three domains. As each agent's observation is extremely limited in Box Pushing, we allow centralized crities in both Mac-IAICC and Naive Mac-IACC access the state (agents' poses and boxes' positions), but use the joint macro-obser maaro-observvtton. aacttoni history in the other two domains.
In the Box Pushing task (the left two in the top row in Fig. 3) Naive Mac-IACC (green) can learn policies almost as good as the ones for Mac-IAICC (red) for the smaller domain, but as the grid world size grows, Naive Mac-IACC performs poorly while Mac-IAICC keeps its performance near the centralized approach. From each agent's perspective, the bigger the world size is, the more time steps macro-actio action could take, and the less accurate the critic of Naive MaC- becomes since it is trained depending on any agent's ' macro-action termination. Conversely, Mac-IAICC gives each agent separate centralized critic trained with the reward associated with its own macro-action exccution.
In Overcooked-A (the third one the top row in Fig. as Mac-IAICC'S performance is determined by the training of three agents' critics, it learns slower than Naive Mac-IACC in the early stage but converges to a slightly higher value and has better learning stability than Naive MaC-IACC in the end. The result of scenario B (the last one at the top row in Fig. 3 shows that Mac-IAICC outperforms other methods in terms of achieving better sample efficiency, a higher final return and lower variance. The middle wall in scenario B limits each agent's 's moving space and leads to higher frequency of macro-action terminations. The shared centralized critic in Naive Mac-IACC thus provides more noisy value estimations for each agent's 's actions. Because of this, Naive Mac-IACC performs worse with more variance. Mac-IAICC, however, does not get hurt by such environmental dynamics change. Both Mac-CAC and Mac-IAC are not competitive with Mac-IAICC in this domain.
In the Warehouse scenarios (the bottom row in Fig. 3. Mac-IAC (blue) performs the worst due to its natural limitations and the domain's 's partial observability. In particular, it is difficult for the gray robot (arm) to learn an efficient way to find the correct tools purely based on local information and very delayed rewards that depend on the mobile robots' behaviors. In contrast, in the fully centralized Mac-CAC (orange), both the actor and the critic have global information so it can learn faster in the early training stage. However, Mac-CAC eventually gets stuck at local-optimum in all five scenarios
8

---

Mac-IAICC
Naive Mac-IACC
Mac-CAC
Mac-IAC
Pushing
Pushhing
Mian Tost Return
250
Moaa Test: Raturn
100
150
-10
120
120
Nean Tes:
Test
100-
0
10K
20K
35K
0K
25k
50c
100K
30K
60K Ephodd
120K
Epiodd
Spisade
Episode
Warchouse A
Warehouse 9
Warchouse
Warchouse D
Kean Test Return
Mean Test Retum
Mean Ruturn
360
125
180
1.00
250
-125
-200
25K
LOCK
Episode
Episode
Figure 3: Comparison of macro-action- asynchronous actor-critic methods.
due to the exponential dimensionality of joint history and action spaces over robots. By leveraging the CTDE paradigm, both Mac-IAICC and Naive Mac-IACC perform the best in warehouse A. Yet, the weakness of Naive Mac-IACC is clearly exposed when the problem scaled up in Warehouse B, C and D. In these larger cases, the robots' asynchronous macro-action executions (e.g., traveling between rooms) become more complex and cause more mismatching between the termination from each agent's 's local perspective and the termination from the centralized perspective, and therefore, Naive Mac-IACC's performance significantly deteriorates, even getting worse than Mac-IAC in Warehouse-D. In contrast, Mac-IAICC higher value with much lower variance, compared to other methods. This outcome confirms not only Mac-IAICC's scalability but also the effectiveness of having an individual critic for each agent to handle variable degrees of asynchronicity in agents' high-level decision-making
maintain its outstanding performance, converging
Mac-IAC
Mac-CAC
Mac-Dec-Q
Mac-Cen-Q
Pushing
Meenn Test Return
250
Mean Test Return
Tost nuturn
400
7201
125
120
Test
MAD
.800
180
-125
40
-250
160
-180
25K Episode
0K
75k
100K
-370
06
20K Episode
30K
45K
0K
20K
40%
50C
80C
Episoce
Episode
Figure 4: Comparisons of macro-action-basse based actor-critic methods and value-based methods.
Comparative analysis between actor-critic and value-based approaches. We also compare our actor-critic methods (Mac-IAC and Mac-CAC) with the current state-of-thh-art asynchronous decentralized and centralized MARL methods, the value-based approaches (Mac-Dec-Q and Mac- Cen-Q) [Xiao et al., 2019) shown in Fig. g The Box Pushing task requires agents to simultancously reach the big box and push together. This consensus rarely achieved when agents independently sample actions using stochastic policies in Mac-IAC and is hard to learn from pure on-policy data. By value-based approaches show much stronger sample efficiency than on- on-policy actor-critic approaches in this domain with a small action space (left figure). Such an advantage sustained by the decentralized value-based method (Mac-Dec-Q) but gets lost in the centralized one (Mac-Cen-Q) in the Overcooked domains due to a jointoint macro-action space (153). On the contrary, our actor-critic methods can scale large domains and learn high-quality solutions. This is particularly noticeable on Warchouse-A, where the policy gradient methods quickly learn high-
having replay-bufie

---

quality policy while the centralized Mac-Cen-OL is slow to learn and the decentralized Mac-Dec-O unable to learn. In addition, the stochastic policies in actor-critic methods potentially have better exploration property so that, in Warehouse domains, Mac-IAC can bypass an obvious local-optima that Mac-Dec-Q falls into, where the robot arm greedily chooses Wait-M to avoid more penalties.
Hardware Experiments
Figure 5: Collaborative behaviors generated by running the decentralized policies learned by Mac- IAICC where Turtlebot-O (T-0) is bounded in red and Turtlebor-1 (T-1) is bounded in blue. (a) After staging a tape measure at the left, Fetch looks for the 2nd one while Turtlebots approach the table; (b) T-0 deliveries a tap measure to W-0 and T-I waits for a clamp from Fetch; (c) T-1 deliveries a clamp to W-1, while T-0 carries the other clamp and goes to W-0, and Fetch searches for electric drill; (d) T-0 deliveries an electric drill (the last tool) to W-0 and the entire delivery task is completed.
We also extend scenario A of the Warehouse Tool Delivery task to hardware domain (details of experimental setup are referred to Appendix F Fig. S shows the sequential collaborative behaviors of the robots in one hardware trial. Fetch was able to find tools in parallel such that two tape measures (Fig. 5a). two clamps (Fig. 5b)) and two electric drills, were found instead of finding all three types of tool for one human and then moving Fetch's ' efficiency is also reflected in the behaviors such that it passed a tool to the Turtelbot who arrived first (Fig. 5b) and continued to find the next tool when there was Turtlebot waiting beside it (Fig. [c). Meanwhile, Turtlebots were clever such that they successfully avoid delayed delivery by sending tools one by one the nearby workshop (e.g., T-0 focused W-0 shown in Fig. 56 and [5d] and T-1 focused on W-1 shown in Fig. 5ch, rather than waiting for all tools before delivering. traveling a longer distance serve the human the diagonal, or prioritizing one the humans altogether.
the other which would result in one of the humans waiting.
Conclusion
This paper introduces general formulation for asynchronous multi-agent macro-action-basel policy gradients under partial observability along with proposing decentralized actor-critic method (Mac- IAC). a centralized actor-critic method (Mac-CAC), and two CTDE-based actor-critic methods (Naive Mac-IACC and Mac-IAICC). These are the first approaches to be able to incorporate controllers that may require different amounts of time complete mmacro-actions) in a general asynchronous multi- agent actor-critic framework. Empirically, our methods are able to learn high-quality macro-action- based policies allowing agents to perform asynchronous collaborations in large and long-horize problems. Importantly, our most advanced method, Mac-IAICC, allows agents to have individual centralized crities tailored to the agent's own macro-action execution. Additionally, the practicality of our approach is validated in a real-world multi-robot setup based on warehouse domain. This work provides a foundation for future macro-action-base MARL algorithm development, including other policy gradient-based methods well as methods which also learn the macro-actions.
Acknowledgments
We thank Chengguang Xu and Tian Xia for their participation in hardware experiments. This research supported in part by the U.S. Office of Naval Research under award number N00014-19-1-2131, Army Research Office award 1N11001000026 and NSF CAREER Award 2044993.
10

---

References
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.
Yali Du, Lei Han, Meng Fang. Tianhong Dai, Ji Liu, and Dacheng Tao. Liir: Learning individual intrinsic reward in multi-agent reinforcement learning. In Proceedings of the Conference on Neural Information Processing Systems, 2019.
Jakob Foerster, Gregory Farquhar, Triantafyllos Afouras, Nantas Nardelli, and Shimon Whiteson. Counterfactual multi-agent policy gradients. In Proceedings of the AAAI Conference on Artificial Intelligence, February 2018.
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 Proceedings of the International Conference on Autonomous Agents and Multiagent Systems, pages 456 464, 2021.
Shariq Iqbal and Fei Sha. Actor-attention-critie for multi-agent reinforcement learning. In Proceedings of the International Conference on Machine Learning, volume 97, pages 2961-2970, 2019.
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, Aviv Tamar, Jean Harb, Pieter Abbeel, and Igor Mordatch. Multi-agent actor- critic for mixed pooperativecoompeiiee environments. Proceedings of the Conference on Neural Information Processing Systems, 2017.
Jianyu Su, Stephen Adams, and Peter A Beling. Value-decompossition multi-agent actor-crities. In Proceedings of the AAAI Conference on Artificial Intelligence, 2021.
Oriol Vinyals, Igor Babuschkin, Wojciech M. Czarnecki, Michaël Mathieu, Andrew Dudzik, Junyoung 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 P. 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, Tobias Pfaff, Yuhuai Wu, Roman Ring, Dani Yogatama, Dario Wünsch, Katrina McKinney, Oliver Smith, Tom Schaul, Timothy Lillicrap, Koray Kavukcuoglu, Demis Hassabis, Chris Apps, and David Silver. Grandmaster level in starcraft II using multi-agen reinforcement learning. Nature., 575(7782): 350-354, 2019.
Jianhong Wang, Yuan Zhang, Tae- Kyun Kim, and Yunjie Gu. Shapley q-value: A local reward approach to solve global reward games. In Proceedings of the AAAI Conference on Artificial Intelligence, 2020a.
Yihan Wang, Beining Han, Tonghan Wang. Heng Dong, and Chongjie Zhang. DOP: Off-policy multi-agent decomposed policy gradients. In Proceedings of the International Conference Learning Representations, 2021a.
Jiachen Yang, Alireza Nakhaei, David Isele, Kikuo Fujimura, and Hongyuan Zha. Cm3: Cooperative multi-goal multi-stage multi-agent reinforcement learning. Proceedings of the International Conference on Learning Representations, 2020a.
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 on Neural Information Processing Systems, 2020.
Murtaza Dalal, Deepak Pathak, and Ruslan Salakhutdinov. Accelerating robotic reinforcement learn- ing via parameterized action primitives. In Proceedings of the Conference on Neural Information Processing Systems, 2021.
11

---

Freek Stulp and Stefan Schaal. Hierarchical reinforcement learning with movement primitives. In 11th BEEE-RAS International Conference on Humanoid Robots, 2011.
George Dimitri Konidaris, Scott Kuindersma, Roderic A. Grupen, and Andrew G. Barto. Autonomous skill acquisition on mobile manipulator. In Wolfram Burgard and Dan Roth, editors, Proceedings of the AAAI Conference on Artificial Intelligence, 2011.
George Dimitri Konidaris, Leslie Pack Kaelbling, and Tomás Lozano-Pérez. From skills to symbols: Learning symbolic representations for abstract high-level planning. Journal of Artificial Intelligence Research, 61:215-288 2018.
Jimmy Wu, Xingyuan Sun, Andy Zeng, Shuran Song, Johnny Lee, Szymon Rusinkiewicz, and Thomas Funkhouser. Spatial action maps for mobile manipulation. In Proceedings of the Robotics: Science and Systems Conference, 2020.
Ruijie He, Abraham Bachrach, and Nicholas Roy. Efficient planning under uncertainty for a target- tracking micro-aerial vehicle. In Proceedings of the International Conference on Robotics and Automation, 2010.
Kaijen Hsiao, Leslie Pack Kaclbling, and Tomas Lozano- Perez. Task-driven tactile exploration. In Proceedings of the Robotics: Science and Systems Conference, 2010.
Yiyuan Lee, Panpan Cai, and David Hsu. MAGIC: learning macro-actions for online POMDP planning. In Proceedings of the Robotics: Science and Systems Conference, 2021.
Georgios Theocharous and Leslie Kaelbling, Approximate planning in pomdps with macro-actions. In Advances in Neural Information Processing Systems, 2004.
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.
Christopher Amato, George D. Konidaris, Ariel Anders, Gabriel Cruz, Jonathan P. How, and Leslie P. Kaelbling. Policy search for multi-robot coordination under uncertainty. Proceedings of the Robotics: Science and Systems Conference, 2015a.
Christopher Amato, George D. Konidaris, Gabriel Cruz, Christopher A. Maynor, Jonathan P. How, and Leslie P. Kaelbling. Planning for decentralized control of multiple robots under uncertainty. In Proceedings of the International Conference on Robotics and Automation, pages 1241-1248, 2015b.
Trong Nghia Hoang, Yuchen Xiao, Kavinayan Sivakumar, Christopher Amato, and Jonathan How. Near-optimal adversarial policy switching for decentralized asynchronous multi-agent systems. In Proceedings of the International Conference on Robotics and Automation, 2018.
Shayegan Omidshafiei, Ali-akbar ggha-mohammadi, Christopher Amato, Shih- Yuan Liu, Jonathan P. How, and John Vian. Graph-based based cross entropy method for solving multi-robot decentralized POMDPs. In Proceedings of the International Conference on Robotics and Automation, 2016.
Shayegan Omidshafici, Ali-akbar agha-mohammadii Christopher Amato, and Jonathan P. How. Decentralized control of multi-robot partially observable markov decision processes using belief' space macro-actions. The International Journal of Robotics Research, 36(2):231-258, 2017a
Christian Schroeder de Witt, Jakob Foerster, Gregory Farquhar, Philip H. S. Torr, Wendelin Boehmer, and Shimon Whiteson. Multi-agent common knowledge reinforcement learning. In Proceedings of the Conference on Neural Information Processing Systems, 2019.
Dongge Han, Wendelin Böhmer, Michael J. Wooldridge, and Alex Rogers. Multi-agent hierarchical reinforcement learning with dynamic termination. In PRICAI (2), volume 11671 of Lecture Notes in Computer Science, pages 80-92. Springer, 2019.
12

---

Ofir Nachum, Michael Ahn, Hugo Ponte. Shixiang Shane Gu, and Vikash Kumar. Multi-agent manipulation via locomotion using hierarchical sim2real. In Proceedings of the Conference on Robot Learning, 2019.
Rose E. Wang, J. Chase Kew, Dennis Lee, Tsang- Wei Edward Lee, Tingnan Zhang, Brian Ichter, Jie Tan, and Aleksandra Faust. Model-based reinforcement learning for decentralized multiagent rendezvous. In Proceedings of the Conference on Robot Learning, 2020b.
Tonghan Wang, Tarun Gupta, Anuj Mahajan, Bei Peng, Shimon Whiteson, and Chongjie Zhang, Rode: Learning roles to decompose multi-agent tasks. In Proceedings of the International Conference on Learning Representations, 2021b.
Zhiwei Xu, Yunpeng Bai, Bin Zhang, Dapeng Li, and Guoliang Fan. HAVEN: hierarchical coop- erative multi-agent reinforcement learning with dual coordination mechanism. arXiv preprint. abs/2110.07246,, 2021.
Jiachen Yang, Igor Borovikov, and Hongyuan Zha. Hierarchical cooperative multi-agent reinforce- ment learning with skill discovery. In Proceedings the International Conference on Autonomous Agents and Multiagemt Systems, 2020b.
Jhelum Chakravorty, Patrick Nadeem Ward, Julien Roy, Maxime Shevalier-Boisverr Sumana Basu, Andrei Lupu, and Doina Precup. Option-critic in cooperative multi-agent systems. arXiv preprint, arXiv:1911. 12825,, 2019.
Kunal Menda, Yi-Chun Chen, Justin Grana, James W. Bono, Brendan D. Tracey, Mykel J. Kochen- derfer, and David H. Wolpert. Deep reinforcement learning for event-driven multi-agent decision processes. IEEE Trans. Intell. Transp. Syst. 20(():1259-14)) 1268, 2019.
Yuchen Xiao, Joshua Hoffman, and Christopher Amato. Macro-action- deep multi-agent reinforcement learning. In Proceedings of the Conference Robot Learning, 2019.
Jimmy Wu, Xingyuan Sun, Andy Zeng. Shuran Song, Szymon Rusinkiewicz, and Thomas Funkhouser. Spatial intention maps for multi-agent mobile manipulation. In Proceedings of the International Conference Robotics and Automation, 2021a.
Landon Kraemer and Bikramjit Banerjee. Multi-agent reinforcement learning as a rehearsal for decentralized planning. Neurocomputing, 190:82-94, 2016.
Frans A. Olichoek, Matthijs T. Spaan, and Nikos A. Vlassis. Optimal and approximate q-value functions for decentralized pomdps. Journal of Artificial Intelligence Research, 32:289-355 -338, 2008.
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 planning. Topics in Cognitive Science, 2021b.
R.S. Sutton, D. Precup, and S. Singh. Between MDPs and semi-MDPs: A framework for temporal abstraction in reinforcement learning. Artificial Intelligence, 11:1181-211, 1999.
Richard S Sutton, David A McAllester, Satinder P Singh, and Yishay Mansour. Policy gradient meth- ods for reinforcement learning with function approximation. In Advances in neural information processing systems, pages 1057-1063, 2000.
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.
Vijay R Konda and John N Tsitsiklis. Actor-critic algorithms. In Proceedings of the Conference Neural Information Processing Systems, pages 1008-1014, 2000.
Richard S. Sutton. Learning to predict by the methods of temporal differences. Mach. Learn., 3:9-44, 1988.
Lex Weaver and Nigel Tao. The optimal reward baseline for gradient-based reinforcement learning. In Proceedings of the Conference on Uncertainty Artificial Intelligence, pages 538-545. Morgan Kaufmann, 2001.
13

---

Xueguang Lyu. Yuchen Xiao, Brett Daley, and Christopher Amato. Contrasting centralized and decentralized crities in multi aggnt reinforcement learning. Proceedings of the International Conference on Autonomous Agents and Multiagent Systems, 2021.
Yoav Alon and Huiyu Zhou. Multi-agent reinforcement learning for unmanned aerial vehicle coordination by multi-critic policy gradient optimization. IEEE Trunsactions on Robotics, 2020.
Arbaaz Khan, Ekaterina I. Tolstaya, Alejandro Ribeiro, and Vijay Kumar. Graph policy gradients for large scale robot control. 2019.
Rupert Mitchell, Jenny Fletcher, Jacopo Panerati, and Amanda Prorok. Multi-vehicle mixed reality reinforcement learning for autonomous multi-lane driving. In Proceedings of the International Conference Autonomous Agents and Multiagent Systems, 2020.
Jin-Soo Park, Brian Tsang, Harel Yedidsion, Garrett Warnell, Dachyun Kyoung, and Peter Stone. Learning to improve multi-robot hallway navigation. In Proceedings of the Conference on Robot Learning, November 2020.
Peter Stone, Richard Sutton, and Gregory Kuhlmann. Reinforcement learning for RoboCup-soccen keepaway. Adaptive Behavior, 2005.
Caroline Strickland, David Churchill, and Andrew Vardy. A reinforcement learning approach to multi-robot planar construction. Proceedings of IEEE International Symposium on Multi-Robot and Mulli-Agent Systems, 2019.
Yichuan Charlie Tang. Towards learning multi-agent negotiations via self-play. In Autonomous Driving Workshop, IEEE International Conference on Computer Vision, 2019.
Yu Fan Chen. Hicrarchical decomposition of multi-agent markov decision processes with application to health aware planning. Master's thesis, Massachusetts Institute of Technology, 2014.
S. Luo, J. Kim, R. Parasuraman, J. H. Bae, E. T. Matson, and B. C. Min. Multi-robot rendezvous based on bearing-aided hierarchical tracking of network topology. Ad Hoc Networks, 2018.
Frans A. Oliehoek and Arouud Visser. A hierarchical model for decentralized fighting of large scale urban fires. In Proceedings of the AAMAS Workshop on Hierarchical Autonomous Agents and Multi-Agent Systems, 2006.
Shayegan Omidshafiei, Shih- Yuan Liu, Michael Everett, Brett T Lopez, Christopher Amato, Miao Liu, Jonathan P How, and John Vian. Semantic-level decentralized multi-robot decision-makien using probabilistic macro-observations. In Proceedings of the International Conference on Robotics and Automation, pages 871 971-878, 2017b.
Shiqi Zhang, Yuqian Jiang, Guni Sharon, and Peter Stone. Multirobot symbolic planning under temporal uncertainty. In Proceedings of the 16th International Conference on Autonomous Agents and Multiagent Sytems (AAMAS), 2017
Tianpei Yang. Weixun Wang. Hongyao Tang. Jianye Hao, Zhaopeng Meng. Hangyu Mao, Dong Li, Wulong Liu, Chengwei Zhang, Yujing Hu, Yingfeng Chen, and Changjie Fan. An efficient transfer learining framework for multiagent reinforcement learining. In Proceedings of the Conference on Neural Information Processing Systems, 2021.
Sanjeevan Ahilan and Peter Dayan. Feudal multi-agent hierarchies for cooperative reinforcement learning. arXiv preprint,
2019.
Alexander Sasha Vezhnevets, Yuhuai Wu, Remi Leblond, and Joel Z. Leibo. Options as responses: Grounding behavioural hierarchies in multi-agent rl. In Proceedings of the International Conference on Machine Learning. 2020.
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, loannis Antonoglou, Helen King, Dharshan Kumaran, Daan Wierstra, Shane Legg, and Demis Hassabis. Human-level control through deep reinforcement learning. Nature, 518:529-533, 2015.
14

---

Pierre-Luc Bacon, Jean Harb, and OPTdoina Precup. The option-critt architecture. In Proceedings of the AAAI Conference on Artificial Intelligence, pages 1726-1734, 2017.
Chevalier-Boisvert Maxime and Roy Julien. Teamgrid, 2020. URL https://github. com/ mila-iqia/teamgria
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, pages 1724-1734, 2014.
Melonee Wise, Michael Ferguson, Derek King, Eric Diehr, and David Dymesich. Fetch & freight: Standard platforms for service robot applications. In Workshop on Autonomous Mobile Service Robots, International Joint Conference on Artificial Intelligence, 2016.
Anis Koubaa, Mohamed-Foued Sriti, Yasir Javed, Maram Alajlan, Basit Qureshi, Fatma Ellouze, and Abdelrahman Mahmoud. Turtlebot office: service-oriented software architecture for personal assistant robots using ros. 2016 International Conference Autonomous Robot Systems and Competitions (ICARSC), pages 270-276, 2016.
B. Calli, A. Walsman, A. Singh, S. Srinivasa, P. Abbeel, and A. M. Dollar. Benchmarking in manipulation research: Using the Yale-CMU-Berkeley object and model set. IEEE Robotics Automation Magazine, 22(3):36-555 52, 2015.
Eitan Marder-Eppstein, Hric Berger, Tully Foote, Brian Gerkey, and Kurt Konolige. The office marathon: Robust navigation in an indoor office environment. In Proceedings of the International Conference on Robotics and Automation, 2010.
Marcus Gualtieri, Andreas ten Pas, and Ondrej Biza. Pointcloudspython, 2018. URL. https
David Coleman, Ioan A. Sucan, Sachin Chitta, and Nikolaus Correll. Reducing the barrier to entry of complex robotic software: moveit! case study. Journal of Software Engineering for Robotics.
Rosen Diankov and James Kuffner. Openrave: A planning architecture for autonomous robotics. Technical report, 2008
Ioan A. Şucan, Mark Moll, and Lydia E. Kavraki. The Open Motion Planning Library. IEEE Robotics & Automation Magazine, 1944:72-82, December 2012.
15

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] Please check Section +.2 where
we analyze the advantages and limitations of our methods over a variety of domains.
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [N/A]
(b) Did you include complete proofs of all theoretical results? [N/A]
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main exper- imental results (either in the supplemental material or URLY? [Yes] In supple- mentary materials, we include the code and README. txt file to reproduce the main experimental results.
(b) Did you specify all the training details (e.g.. data splits, hyperparameters, how they were chosen)? [Yes] All the training details including hyperparameters are in Appendix E
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes] Please check the first paragraph Section 4.2
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] The details of used computational resources are mentioned in Appendix
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you eite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you't 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
16


Reviews:
[{"review_id": "sA7cXEE1YN", "reviewer": "Reviewer_TCiE", "summary": "This paper presents a general formulation of macro action-based Multi-Agent Actor Critic framework by extending widely used methods in multi-agent actor critic literature to a Mac-DecPOMDP setting with asynchronous actions. This is desirable since agents can now update themselves asynchronously without having to wait for other agents. Macro-actions are designed such that it can include both temporally extended actions, as well as, primitive actions. \n\nExisting methods with macro-actions often rely on the assumption that agents behave synchronously and thus cannot be readily applied in the proposed setting. To this end, the authors propose a range of baselines (generalized from their primitive action counterparts) to compare with for evaluation purpose -- Mac-IAC, Mac-CAC, Naive IACC, and Mac-IAICC. The empirical results from three different environments and an additional real-life robotics application show significant performance and desirable behaviors in the agents.\n  ", "questions": "Q1. lines 74-75: Can the authors clarify how an agent's \"primitive-observation set\" is different from it's \"macro-observation space\". Isn't the latter a subset of the former? How does the environment have two different observation functions?\n\nQ2. lines 302-303: Even after having access to the (full) state information in the Box Pushing task, not only does Mac-CAC outperform Mac-IAICC, it also learns faster. How is this possible given that both models have the same input and CAC has a huge joint macro-action space?\n\nMinor Comments:\n\n1. The authors should try to add more clarity as to why they had to design and compare with their own baselines (and not with existing methods on Mac-DecPOMDP). While I understand that existing methods cannot be readily generalized to the asynchronous setting (which the authors have mentioned in bits and pieces throughout the paper), issuing a more concrete statement upfront would be useful for the readers to place this work in the context of other similar works.\n\n2. Lines 145-147: Please point to the appropriate sections in the Appendix.\n", "limitations": "In general, the authors have done well to highlight the limitations of the different proposed algorithms in Section 4.2. However, I felt that a general high-level discussion on the asynchronous updates in the algorithms is missing and the paper could benefit from placing this in the context of other potential approaches.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. Although the authors borrow the \"trajectory squeezing\" technique to achieve asynchronicity (as stated in Sec 2.5), the fact that it is adapted to an on-policy setting is pretty novel. Since, most practical applications in MARL display asynchronous behavior, the set of algorithms presented here are of significance to the MARL and the robotics community.\n\n2. The paper has a clear flow and is well written. I, at least, did not come across any technical or grammatical errors (Kudos to the authors for that !)\n\n3. The authors present their experimental results on three different environments each of which justify the use of one or another proposed macro-action paradigm (by showing clear improvements). Additionally, ablation studies were performed on a real-life robotic warehouse setting, which also clearly highlights desired behavioral aspects of the proposed methods. The authors have also submitted codes for reproduction (although I did not run them).\n\nWeaknesses:\n\n1. The \"squeezing\" process described in the main paper is a bit ambiguous, however, it is very clearly explained in the Appendix. Since the authors use this as an essential part of their training algorithm, perhaps it would be good to move the explanation from the Appendix to the main paper (just Figure 6 from Appendix would suffice). \n\n2. Section 4.2 (Advantages of learning with macro-actions): This seems to be an unfair comparison given that macro-actions are pre-specified and it is obviously convenient for the macro-action-based agents to learn faster and better than primitive-action-based agents. As such, the results are not all that appealing. Perhaps this should be pushed to the Appendix to make room for explaining the algorithm (from point 1. above) in more detail.\n\n3. The limitations of the proposed framework should be clearly highlighted. While the authors compare the shortcomings of each module in different environments, I felt that a general discussion of the algorithms performing asynchronous updates is missing. For instance, when you look at the trajectory squeezing process in the Appendix, is there any crucial information that the actor/critic misses out on during gradient updates, and if so, how can they be improved.  \n\nPlease note that I am considering the above-mentioned weaknesses as minor issues and authors are requested to make changes to address these issues in the main paper.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "O9MzlxEcjGZ", "reviewer": "Reviewer_vcLk", "summary": "This paper extends macro-action-based DQN to actor-critic methods to solve asynchronous hierarchical multi-agent cooperation tasks. Asynchronous learning, where the high-level decisions have different action durations, is an interesting and important topic for complex real-world applications. The motivation is clear, and the paper is well organized. The experiments are performed on both simulation environments and hardware platforms, which is convincing.", "questions": "The easiest method I can see to solve the duration problem is to set a maximal duration and set an idle action. Thus, the macro-actions have the same duration. What is the limitation of the easiest method?\n\nSince the formulation is similar to the settings of hierarchical RL, I am curious about the performance of existing hierarchical MARL methods although they do not specifically consider the asynchronicity problem. \n\nThe hardware experiments are fancy. Although there is a video in Appendix, it is hard to intuitively get the effectiveness of the proposed methods from Figure 5. ", "limitations": "The authors have discussed the limitations.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\nAsynchronous learning is meaningful to many real-world applications.\n\nThe motivation is clear, and the paper is well organized.\n\nThe experiments are extensive and demonstrate that learning with macro-actions is important in tasks requiring high-level planning. And the selected platforms are suitable to verify the effectiveness of asynchronous learning. \n\nI appreciate the section Mac-IAICC, where the duration issue is clearly discussed and specifically treated. \n\nWeaknesses:\n\nThe novelty is limited since the proposed methods seem to be directly extended from macro-action-based DQN.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "6BVHtHPxyVC", "reviewer": "Reviewer_6Bsf", "summary": "This paper develops an asynchronous multi-agent actor-critic approach that allows agents to directly optimize asynchronous strategies in three state-of-the-art multi-agent training paradigms: decentralized learning, centralized learning, and decentralized execution and centralized training.This paper also evaluates its methods in both simulation and hardware environments. The experiment results show the method can obtain high-quality and asynchronous solutions. ", "questions": "+ In the setting of this paper, the number, meaning and complexity of macro-actions are defined in advance. How much influence do different settings of macro-actions have on experiment results?\n  \n+ In line 343-346, the authors think the value-based approaches have better performance than actor-critic approaches because of their stronger sample efficiency. Why not compare with high sample-efficiency AC methods (such as MAPPO)?", "limitations": "The authors do not discuss limitations and potential negative societal impact of their work.", "rating": 4, "confidence": 5, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n+ The experimental design and discussion are very interesting. The experiments are implemented in both simulation and hardware environments, which demonstrates the powerful application ability of this method.\n+ The statement is clear and easy-reading.\n\n\nWeaknesses:\n\n+ The idea of utilizing macro-action in MARL methods is not novel. This paper just transfers the macro-action-based value evaluation in DQN method[1] to AC method. To some extent, the paper lacks originality.\n  \n\n[1] Yuchen Xiao, Joshua Hoffman, and Christopher Amato. Macro-action-based deep multi-agent  reinforcement learning. In Proceedings of the Conference on Robot Learning, 2019.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept