Off-Beat Multi-Agent Reinforcement Learning
Authors: Wei Qiu
Weixun Wang
Rundong Wang
Bo An
Yujing Hu
Svetlana Obraztsova
Zinovi Rabinovich
Jianye HAO
Yingfeng Chen
Changjie Fan
Venue: NeurIPS 2022 Submitted (2022)
Keywords: multi-agent system
multi-agent reinforcement learning

Abstract: We investigate model-free multi-agent reinforcement learning (MARL) in environments where off-beat actions are prevalent, i.e., all actions have pre-set execution durations. During execution durations, the environment changes are influenced by, but not synchronised with, action execution. Such a setting is ubiquitous in many real-world problems. However, most MARL methods assume actions are executed immediately after inference, which is often unrealistic and can lead to catastrophic failure for multi-agent coordination with off-beat actions. In order to fill this gap, we develop an algorithmic framework for MARL with off-beat actions. We then propose a novel episodic memory, LeGEM, for model-free MARL algorithms. LeGEM builds agents’ episodic memories by utilizing agents’ individual experiences. It boosts multi-agent learning by addressing the challenging temporal credit assignment problem raised by the off-beat actions via our novel reward redistribution scheme, alleviating the issue of non-Markovian reward. We evaluate LeGEM on various multi-agent scenarios with off-beat actions, including Stag-Hunter Game, Quarry Game, Afforestation Game, and StarCraft II micromanagement tasks. Empirical results show that LeGEM significantly boosts multi-agent coordination and achieves leading performance and improved sample efficiency.

Despite the recent successes of MARL, learning effective multi-agent coordination policies for 28 complex multi-agent systems remains challenging. One key challenge is the off-beat actions, i.e., all actions have pre-set execution durations and during the execution durations, the environment changes Off-Beat Multi-Agent Reinforcement Learning
Anonymous Author(s) Affiliation Address
email
Abstract
We investigate model-free multi-agent reinforcement learning (MARL) in environ- ments where off-beat actions are prevalent, i..., all actions have pre-set execution durations. During execution durations, the environment changes are influenced by, but not synchronised with, action execution. Such a setting is ubiquitous many real-world problems. However, most MARL methods assume actions executed immediately after inference, which is often unrealistic and can lead to catastrophic failure for multi-agent coordination with off-beat actions. In order fill this gap, we develop an algorithmic framework for MARL. with off-beat ac- tions. We then propose novel episodic memory, LeGEM, for model-free MARL algorithms. LeGEM builds agents' episodic memories by utilizing agents' indi- vidual experiences. It boosts multi-agent learning by addressing the challenging temporal credit assignment problem raised by the off-beat actions via our novel reward redistribution scheme, alleviating the issue of non-Markovian reward. We evaluate LeGEM on various multi-agen scenarios with off-beat actions, including Stag-Hunter Game, Quarry Game, Afforestation Game, and StarCraft microman- agement tasks. Empirical results show that LeGEM significantly boosts multi-agen coordination and achieves leading performance and improved sample efficiency.
2
6
10
11
12
13
14
15
16
17
Introduction
18
In Multi-Agent Reinforcement Learning (MARL), multiple agents act interactively and complete tasks sequential decision decision-making manner with Reinforcement Learning (RL). has made remarkable advances in many domains, including autonomous systems [8] 19] and real-time strategy (RTS)
20
22 video games [58]. By the virtue of the centralised training with decentralised execution (CTDE) [3 paradigm, which aims to tackle the scalability and partial observability challenges in MARL, many
24
CTDE-based MARL methods are proposed [13 49 62
63 23 35). With these methods, an
agent executes actions only via feeding its individual observations independently and optimizes its own policy with access to global trajectories centrally.
26
27
30 are influenced by, but not synchronised with, action execution (an illustrative scenario shown in Fig. D. However, Dec-POMDD (2). which underpins many CTDE-baseh MARL methods, hinges 32 on the assumption that actions are executed momentarily after inference, leading to catastrophic failure for centralized training on various off- beat multi-agen scenarios (OBMAS). To fill this gap,
34 we study MARL in settings where off-beat actions are prevalent. Such setting is very common in many real-world problems. For example, in the traffic light control problem, traffic lights in the conjunctions of the road network have pre-set execution time which set asynchronously.
36
RL literature torm execution durations, which is self-consistent with off-beat actions defined in Sec.
d action execution durations are called delays of actions. In this paper, we use the
Submitted to 36th Conference on Neural Information Processing Systems (NeurIPS 2022). Do not distribute.

---

Test Catch of
100
100
hunter 0
stag
hunter
75
KL-LCGEN
75
50
50-
25
tomesingas
20
40
60
80
100
20
40
60
80
100
hunter
hunter
Test Catch de
1100
100
Hunters shoot arrows at different timesteps.
Arrows hit the stag at the same timestep. (hunter and 1: 9)
75
75-
-50
50-
[hunter 0, hunter
25
OTRMX
CTTAN LUGEN
25
CMUS L0320
GMX
Action durations
Hunter D:
takes 9 timestops to hit the stag
takes timesteps to the stag
Steps (K)
100
Steps (K)
40
100
Figure I: An illustrative scenario: two -ognnttt stag-hunter game, where two agents (hunters) have only partial observations, different durations of the shoot action, and cannot communicate. The goal is to catch the stag and they are rewarded when their shot hits- as in, completion of the action is synchronised, the stag at the same time. Both agents can see the stag. As the shoot action durations of the two agents are different, to catch the stag, the two agents should shoot the arrow different timesteps given the distances. Though the scenario is easy for human beings, it is hard for MARL agents due to the action duration. Experiment results: in this scenario, the optimal policy for agent 0 is to shoot the arrow at timestep 0 while the optimal policy for agent is to shoot the arrow at timestep 5. Such asynchronous property of OBMAS motivates agents to lcarn tacit policies. The curves show that VDN and IQL fail to learn coordination policies even in this simple scenario. With LeGEM, MARL methods gain enhanced performances as well as improved sample efficiency.
37 The problem of off-beat actions in MARL has yet to be investigated and tackled. Training MARL policies in OBMAS is challenging: (i) Each agent's 's actions can have a variety of execution durations, which augments the order of complexity of OBMAS during decentralized execution, resulting
38
39
40 in failure of the coordination; (ii) The action durations are unknown to agents during individual executions, and communication is constrained and not always feasible, making non- con-trivial model the environment; (iii) During training, both the temporal credit assignment with TD-learning [S]] and the inter-agent credit assignment with value decomposition methods [T] cannot perform well due to the displaced rewards in multi-agent replay. With off-beat actions, the nonstationarity issue, which mainly stems from rewards' time dependency on the agents' past actions, is exacerbated.
41
42
43
44
45
46
While actions durations are ubiquitous, existing works only focus on single-agent settings, i.e. delay, in RL. Many approaches (59] 39 66) augment the state space with the queuing actions be executed into the environment. However, such state-augmentation trick leads to exponentially increasing training samples with the growing action duration, making training intractable [TT. Chen et al. [TO]
47
48
49
50
extend the delayed MDP (39] and propose Delayed Markov Game for MARL. However, on one hand, such augentationnn treatment is confined to short delays, e.g., one timestep delay; on the other hand, the delayed timestep of the actions is privileged information, which is not available 67 68 introduce asynchronous actions by
51
52
53 in many scenarios. Recent works on macro-actions designing macro-actions with prior environment knowledge. Macro- incro-actioos are different from options in hierarchical RL (HRL) [52 in that the later not manually designed but learned. The key difference between macro-actions and off-beat actions is that macro-actions are high-level actions while off-beat actions are primitive actions. Unfortunately, the inter-agent credit assignment still a challenge of HRI. in OBMAS and the asynchronous 2 nature of off-beat actions undermines the temporal credit assignment of centralized training, causing poor sample efficiency and unsatisfactory performance (more discussions can be found in the related works section in Sec. 7
54
55
56
57
58
59
61 We aim to address the aforementioned issues. We first propose off- Dec-POMDP. We then instan- tiate new class of episodic memory, LeGEM, for model-free MARL algorithms. LeGEM boosts multi-agent learning by addressing the challenging temporal credit assignment problem raised by the off-beat actions via our novel levelled graph-based temporal recency reward redistribution scheme. Specifically, each agent maintains LeGEM and during centralized training, each agent searches the pivot timestep given observations from its graph. The pivot timestep is the timestep wherein the off- beat reward relates to the given node. The pivot timesteps of each agent are ranked, in which the final pivot timestep will be chosen by recency and later used for reward redistribution and target estimation
62
63
64
65
66
67
68
89 in TD-learning. We evaluate our method on Stag-Hunter Game, Quarry Game, Afforestation Game, and StarCraft II micromanagement tasks. Empirical results show that our method significantly boosts multi-agent coordination and achieves leading performance as well as improved sample efficiency.
71
We clarify the term asynchronous: actions that simultaneously committed into the environment by all agents in MARL will not complete their respective action durations at the same time in future timesteps.

---

72
2
Preliminaries
73
Dec-POMDP. A cooperative MARL problem can be modeled as a decentralised partially observable
74
U, P. R, O,N, 7), Markov decision process (Dec-POMDP) which can be formulated as a tuple (s,u,
where 8 E S denotes the state of the environment. Each agent E A = {1. ..... ] chooses an action U, E U at each timestep. forming joint action vector, == [u, i-1 U The Markovian
75
77 transition function can be defined as P(s'|s, [88 u): S x U x S - [0. 1], transiting one state of current
78 timestep to the state of next timestep conditioned on current state and joint action. Every agent shares the reward and the reward function is Ri(s, u) : S x U + R. 7 [0. 1) is the discount factor. 80 Due to partial observability, each agent has individual partial observation o E O, according to the observation function Os.. i) S x A + O. The goal of each agent is optimize its own policy T. (u)):: : T x U + fo, 1] given its ceciio-observation-rewaae
81
82
history TÜ E T == (O x U).
83
Multi-Agent Reinforcement Learning. MARL aims to learn optimal policies for all the agents
the team. With TD-learning and a global Q value proxy Qlot for the optimal Q-, (Q:)) N
84
optimized via minimizing the loss [65 31:: 0" = arg ming- (() == ED [vt - (8t, s=1 are
)²)
86 where yt + Y max Q3 ($2+1, u²) and 0 is the parameters of the agents. 0 is the parameter of the target Quoe and is periodically copied from 0. D' is a sample from the replay buffer D.
3 Off-Beat Dec-POMDP
88
We introduce our formulation for OBMAS. We first define the off-beat actions for multi-agent 90 scenarios; then we propose the Off-Beat Dec-POMDP. All the proofs can be found in Appx. A
Definition 1 (Off-Beat Actions). Off-beat action ã U characterizes OBMAS where the action ūy taken by agent i has execution duration ma, ~ A(m i. i) A E A, m E {0. 1, ... MM and M < T. where T is the maximum duration and A is the action duration distribution. It is distribution and takes ûj and the index of the agent as parameters. A can be either stochastic or deterministic. The joint off-beat action is ū J.N The execution duration is decided at the time the action was committed to the environment. Thus, the execution duration of an action ū, initiated timestep t is m. {m J.M
91
92 Note that for each agent, m can be different. At timestep i, there are least action and most 99 N actions being initiated (committed to the environment for execution), leading to asynchronicity of
the joint actions. Next, we propose the Off-Beat Dec-POMDP for OBMAS and discuss its properties.
Definition 2 (Off- Beat POMDP.. Off- Off-Beat Rec-POMDP extends Dec-POMDR such that (1) state space is S; (2) joint action space is UN, (3) action duration space is AA;
(4) transition function is P(s' s, u, m) S x n x x A + [0, 1]. and m is the action durations of the joint action;
(5) the reward function is R(s,, û, m) : S x U x A + R;
(6) we call reward oef- reward when any its ma; 2 1, ma, E m, and + 0.
96 In OBMAS, at each timestep f, the environment receives actions that agent initiates for execution in the environment. The initiated actions ú, are instantaneous actions inferred by agents' policies given individuals' observations. The joint reward is the consequence of the committed joint actions of current timestep and previous timesteps, depending on the actions' duration. The asynchronicity
98
99
100
is an inherent feature of the environment, which is different from asynchronicity incurred by com-
munication delays in many video games (asynchronous gameplay ( We discuss some properties of -fft Dec-POMDP below.
101
102
'Asynchronictty is prevalent in worldworld multi-agent scenarios. including asynchronicity in observations. actions and communication. etc. In this paper, we focus the asynchronicity of actions in multi-agent scenarios. For brevity, we name the asynchronicity of actions in MARL. as off-beat.
'We will omit i in the rest of the paper for brevity.
We note that agents have a special NO-OP action available.
/tttps::/www..r whatgamesare com 2t1///21111////// http://////yyccoooooosss or www.ooocccnoooo--o-ccocooooo initiiiinonn.....
html
3

---

103
Remark 1.
When the durations for all actions are identical. off beat Dec-POMDP reduces to Delayed Dec- Dec-POMDP and there is no bef-beat actions in
104
105
Remark 2. There exists u that is synchronous since duration of agents' actions can be m 0.
106
When m of all actions is zero, off-beat Dec-POMDP reduces to Dec-POMDP.
107 In Delayed Dec-POMDP, actions have the same delayed timesteps, which is different from off- beat actions where actions have different action durations or delays. In order to investigate the problem, we consider the deterministic setting of the transition function and the reward function.
108
109
110
Remark 3 (Non-episodic Reward). In our formulation, the reward not episodic reward [[
Remark 4 Mon-MMakoovann Reward). With off- actions, the Markovian property of the reward
112
function R(s, ü, m) does not hold.
113
With off-beat actions, the shared rewards can be readily displaced, causing non- Mon-Markovian rewards. Solving Off-Beat Dec-POMDP challenging as discussed in Sec. []] tackle aforementioned challenges.
114
We propose our methods to
115
4
The Journey is the Reward: A Collective Mental Time Travel Method
116
117
We propose two methodological elements for Off-Beat MARL. The first, LeGEM, presented in this section, is a form of episodic memory that facilitates discovery of pivotal timestep for off- beat rewards; and the second. presented in Sec.5] redistribution of the off-beat reward to the pivot timestep when the relevant off-beat actions were initialised.
118
119
120
121
4.1
LeGEM: A Levelled Graph Episodic Memory for Off-Beat MARL
122
Human learning relies on retrospecting our detailed memory of the past 55
48
For example,
123
while exploring a new scenic area, we do not just remember a multitude of specific spots there, but can recall the paths that connect them with junctions and turns. However. there is MARL method that can explicitly recall the past and identify key states that lead to future rewards. Such "mental time travel" 24 ability is vital for tackling the challenges in OBMAS. Inspired by the recent progress in RI. with episodic memory 18 5 17] that is based on the memory prosthesis proposed by neuroscientists (55 48), we propose our method of episodic memory representation for MARL. Unlike previous episodic memory methods that train a parameterized memory by either augmenting the policy inputs for execution [88] or regularizing the TD learning [17 for RL, our method utilizes the levelled graph data structure 4 a well established structure for data storage and retrieval, to represent an agent's 's individual episodic memory.
125
126
127
128
129
130
131
132
133
We propose our novel episodic memory, Levelled Graph Episodic Memory method (LeGEM), via the levelled graph data structure. LeGEM memorizes each agent's past trajectories which are partial observations and the unilateral action of the agent. During training, each agent i collects its individual trajectories T.. We then define ",....
134
135
136
137
of agent as Ti [[o], "",""""""""""""""""""""" (o,-11 7f , [f]])], where T is the length of the trajectory and the triplet (of, u. r') represents the observation, action and reward of timestep t. Note that r' is globally shared between agents. We define agent i's LeGEM as a directed graph of T where + is the set of graphs of agent i and of the t-th graph of D, E {0.- : T - 1}. Each of consists of tuple of (V) where is the set of nodes and E represents the set of edges that connect nodes in the graph. To model an agent's behaviour explicitly and make the trajectories of agents easy to represent, we create T graphs for each agent and let .. ( ) where T is the maximum level of all graphs and the maximum length of the episode as well. The maximum level of øf is t + 1. The node contains key, visit count and pointers connecting the precursors (node at the previous level) and the successors (node at the next
138
139
140
141
Sub-graph
Subgguup
142
The maximum level of the graph 7. Circles indicate the nodes and num- hers indicate the visit count.
Figure 2:
143
144
145
146
147
148
149
the key [18, 24], we resort to afterstate (36). That is, we use agent i's observation of and action at timestep 4, 7 to define
level). Unlike many parameterized episodic memory using state/observation
151
the key (of, 7t) ).) We provide an example to showcase the relationship between sub-graph and the graph in Fig. For complex and continuous state scenarios, for example StarCraft II scenarios,
152

---

Algorithm 1: SearchPivvoTTimsstoss (p)
Algorithm 2: Scarch Scheme! I
Input: ④, Y and Search (scheme I or II);
Input: w. A," Tis r' Y and Ø;;; Initialize: et: a list whose values are all and its size is the number of paths in A!";
Initialize: an empty list store pivot timesteps;
// Length of T and 7; are equal.
1 <- length(r;:)11
for L 0 to (e)gth(r)-11 do
1. + $ [w];
if r' * 0 (r' r) then // Def- reward for i + 1 to N do
vc + VisitCount (A (Alg.
4
s foreach path A, [j] E A." do
eq + UL ( [,], vc, T.) (Alg.
Get from T;
4.3.t + LUCA, [j], ve, T.) (Alg.
6: - +.10; + - gi.gNooo (oi, ut):
if if 1e.. + -1 then
e <- cio
10
Find all the paths A,d from node e to the node at level 0:
else if ci # then
10
Get the discretized episode return pld
11
e t -
Get the index from T with r'::: et + Search (w, Mi, Ts, r' b,);
else
13
e [j] + t; Summarize(e (Alg.
13
14
Get es (Eqn. and append et to ns:
14
e
15
Return: K.
Return: oj.
use SimHash [9] to discretize the key (of, 7.). This technique has been widely used in commercial search engines and RL [54]. Visit count indicates the total visits made by agent to the node. It initial value is 1. Note that nodes are bidirectional since is helpful for searching (see Sec. 4.2p.
154
155
158
157
Given a Ti with the length of T, if the node is already in the graph at level f, we then increase the visit count by 1. Otherwise, we create new node for level f of the graph and update its pointers. Meanwhile, sub-graphs will be also created and updated. The process of updating LeGEM is in Alg. We provide an example of Alg. 3 in Fig. ? Appx. [B.]] It is worth noting that T; is generated via the interaction of the agent with the environment, and there is no extra interaction needed to collect т). The generated trajectories saved in the experience replay and later sampled for MARL training.
159
160
161
162
163
4.2
Multi-Agent Collective Mental Time Travel with LeGEM
164
With structured agent's past experiences, it can be used search the pivot timestep when actions that triggered the rewarded state were executed. For example, with LeGEM, we can find the pivot timestep, E 5. when agent shoots the arrow in Fig. []
185
186
Fact 1. (Action-Reward Association) When an off-beat reward ri exists in the trajectory Ti (i (1. .,),, T₁ E Tú, off-beat action uy exists (t' < t) in the trajectory set {T where {TA LN constitutes the global trajectory of all agents.
187
188
{=
189
170
As the reward function and transition function are deterministic in our setting, Fact FactD holds. Intuitively, once we find an bff- reward in a trajectory, we are sure that the action which triggered the reward can be found in the trajectory. With more experiences collected by the agents, such pattern is obvious and significant. It motivates us to propose a method to leverage the association property of the off- beat action-reward data and search the pivot timestep for timesteps when off-beat rewards occur, which can further help to redistribute the reward backward to mitigate the temporal credit assignment issue fc.f. Sec. 55. Therefore, we first propose a search method to search the pivot timestep and then propose a proximal ranking method to estimate the pivot timestep that invokes the future reward.
171
173
174
175
178
177
Collective Mental Time Travel. The displaced rewards in the replay buffer hinder multi- agent learning. It is essential for each agent to search the pivot timestep when the potential off- action that triggered the rewarded state was committed the environment. Therefore, we propose two search schemes to find the pivot timestep for all agents given an off-beat reward.
179
180
181
Scheme I: For agent i, given T1 E T4, episode return pii of Tr, of = 2 [(] and = [w] agent& searches from the node (the key is (of, ( and of E Tr, uf E T at level t in sub-graph of to find the pivot timestep e for rr. Concretely, we propose our bi-directional search method. The first one is called Low-Up (LU) search, which traverses from the given node at level / upwards to the node at level O. The second one named UpwLow (UL.) search which traverses from the node at level 0
182
183
184
186
downwards to the given node level f. LU traversing ends when the pattern of increasing visit count
5

---

concstenate the results
sampled
TD Learning J- Q
Central Miner
N1 [ef)
trajectories
reward redistribttion
Search f for each d Identify
Rank R; across agents
D--12 [ k=
samples
Replay Buffer
Centralized Training: The Loss
((s, M4, Sces (e:]Esd)
[q:]ee
Search for each agent:
save
actions
policy
%
Get paths
updato the graphs
20--0-0 -0-66-000 B.0
(5 Ir. Reas
Agent
[(ra]ieb)
experiences
Env
Decentralized Execution: Policy
[ol.2f
agont
Centrolized Training: LeGEM
agentt
ail agents
Online interaction
agent
Figure 3: Our framework: LeGEM, the loss and the agent's policy.
188
ends and the corresponding level is the candidate pivot timestep. On the contrary, UL traversing ends when the pattern of decreasing visit count ends and the corresponding level is the candidate
189
pivot timestep. In Alg. [ we first get visit count (Line 4) and then apply UL traversing (Line 6
190
and LU traversing (Line 7). We summarize the results (Line [4] by select the pivot timestep that has the maximum count. UL traversing has a higher searching priority than its counterpart. The reason is that there exists pattern that the visit count is decreasing from the node at level O and such pattern ends at the pivot timestep. In practise, works well in scenarios whose trajectories are single-off-beat-eeward beaat- trajectories (there is only one off off-beat reward) and the accuracy of Scheme I is over 90% in grid world scenarios. For scenarios, especially complex scenarios, whose trajectories are trajectories, we apply Scheme II. We put Alg. Alg. 5 Alg. and Alg. 7 in Appx. B.T as these algorithms are intuitive and easy to understand literally. The time complexity is (n m) (a slight notation abuse) where n is the size of each A, and m (1 S m S n) is the average distance between the level of the given node the level of the node the pivot timestep.
192
193
194
195
196
multiple-off-beat-ee
198
199
200
201
Scheme II: Scheme
a simplified version of scheme for scenarios that have multiple-off-beat reward trajectories, which searches the pivot timestep by finding the nearest timestep in the most visited path. The node the nearest timestep has the maximum visitcount in that path. Despite the simplicity, it works effective and the time complexity is (n)) where n is the number of paths in A.A.
203
204
205
The pseudo code is shown in Alg. g in Appx. B.1
Given a node at level f, agents collectively search from the node to find the pivot time step (Line 13 206
in Alg. D. The visit count is vital for search methods. In MARL, we use e-greedy [31] for agents to explore the environment and collect individual trajectories. The collected trajectories will be used to build the memory and train the policy. We apply annealing to (in Appx.
208
Ranking the Pivot Timesteps. With our two search schemes, we can search the pivot timesteps for each global trajectory 7 = {(s", ū², "'r''," s('1)) We define the pivot timesteps of each global trajectory T as (e 0 S e, < t, where e, indicates the pivot timestep of t when 213 r is the consequence of actions committed before timestep t. We first get e, by aggregating all the
1). Then, each agent gets x; {ei) In order to subserve 215 the inter-agent credit assignment [13 K can be collectively calculated via proximity:
214
searching outcomes (Line 13 in Alg.
e min 1.. et....... .....,,, et i (1, ,1, ,N
(1)
The pseudo code is shown in Alg. [ For each sampled global trajectory T, we extract for each agent Line 7 then we get e for each agent and aggregate k in line 14aand line [5] respectively.
217
Reward Redistribution for Off-Beat Multi-Agent Reinforcement Learning
218
219
in OBMAS. We utilize TD learning to train MARL policies. The TD error is the difference between the TD target and the prediction. TD targets can be estimated with n-step target, TD(A) and other techniques 12 56]. Unfortunately, current n-step target and TD(A) methods are far from accurate estimating TD targets. They even
Searching in LeGEM leverages the collective intelligence 225 15
220
222
223
incur underestimation with off-beat trajectories. In essence, to train MARL policies in OBMAS, one
224
should accurately estimate the TD target where the reward plays the key role [46] 70). We resolve the
aforementioned conundrum by redistributing rewards to their pivot timesteps. The key idea is that
226
can pull the outcome of one joint oef- action back to the timestep when it was committed the environment, which can dramatically enhance learning despite the long-term reward delays incurred
227
by bef- actions. We utilize e, to update the reward of the transit (8"), t 7 8 s((+)
fr
L(e 2 t) r I[et < <) res
(2)

---

229
where 1()) is the indicator function.Such update rule is conducted iteratively from t =
is a very small positive hyperparameter. To stabilize learning and circumvent the overestimation of the TD target. Tt also updated after Eqn. 2 via Pt
231
[e, t) (1 - B)) ry. It also
avoids aggregated biased/wrong estimation of TD target being back propagated in Bellman Equation.
232
Formally, we define the reward redistribution operator as IIg. L.e,, e HIpp(r', 8, ú), and then
234
define the Bfat Bellman operator I':
(TQ" (s, ū) == Ellla R(s, u, m) + max Q'' (s',ū'))
(3)
235
With the -fft Bellman operator r, we propose its contraction property. Proposition r Q ~ Q is y-contraction.
236
237
Therefore, we can utilize fe, for centralized training in TD-learning:
-D (0) = En Q ( ))²} where yes = f + max Q (s (1 u').
(4)
"2"
238
Our method can be easily incorporated into any model-free MARL method for OBMAS. We present
239
the pseudo code of incorporating our method into model-free MARL methods in Alg. 9 Appx.
240
We also provide pictorial view of our framework in Fig. to show the whole pipeline.
Experiments
241
We perform experiments various multi-agent scenarios with off-beat actions. We introduce off-beat actions in Stag-Hunter Game, Quarry Game, Afforestation Game and StarCraft II microman- agement tasks 44] and use them as testbeds in our experiments. We aim to answer the following questions: Q1: Can our LeGEM improve the multi-agent coordination of many MARL methods
243
245
in OBMAS? Q2: Can our LeGEM outperform previous parameterized episodic memory (EM) for MARL? Q3: Can bootstrapping method of RL help? Q4: Can our LeGEM outperform the multi-agent exploration and mulli-agent risk-sensitive (Ex-Risk) methods?
247
Test Catch 96
QMIX-LaGEM QNIX
IQI-LaGEM
VON-LaGEM
25
LIGEM
50
50
QTRAN
50-
50
25-
25
25-
25
BOOK
Steps
Steps
Steps
Steps
Figure 4: The test catch rate of the stag on the Stag-Hunter Game with off-beat actions.
6.1
Experiment Setup
Categories
Methods
hunter C
sandstorm
QMIX [4] VDN 49 IQL (53) QTRAN 47
MARL (Q1)
desert
QPLEX 66
Stag Hunteer Game
250
bomb
forest
EM (Q2)
EMC 771
agont
QUarTY
1
famer farmer 1
Bootstrap (Q3)
N-step Retuur
MAVEN (8 EMC
Quarryy Gime
Afforestation Game
Ex-Risk (Q4)
RMIX 38
Figure 5: Stag- Hunter Game, Quarry Game and Afforesta- tion Game. More information can be found Appx. C
Table Baseline algorithms.
251
Baselines and scenarios. We list all baselines in table T including the corresponding research questions to be answered. We implement our method on PyMARL [44] and use 10 random seeds to train each method on all environments. We do not use macro-action methods [67] 68) as the baseline because it is hard to make fair comparison between macro-actions methods and our method.
252
253
254
255
As discussed in Sec. [ macro-actions rely on manually designed macro-actions, i.e., designing
256
the pacro-actions by utilizing the simulator settings and domain knowledge, which is different from learning options (3) Designing macro- iacro-actions is not feasible in scenarios where domain knowledge and simulator settings are unknown, such as the OBMAS scenarios. In OBMAS, the agent
257
258
has no idea of the durations of other agents' actions, which is challenging for designing macro-actions.
280
We conduct experiments on Stag-Hunter Game, Quarry Game, Afforestation Game (Fig. 5) and
StarCraft II micromanagement tasks 44 where off-beat action are introduced.
7

---

262
Training settings. We use opensourced code of baselines publicly by the corresponding authors on Github all experiments. We resort to mean-std values our performance evaluation measurement in all figures where the bold line and the shaded area indicate the mean value and one standard D and [ for more information on our environment, baselines, training method, training platform and empirical results.
263
265
deviation of the episode return, respectively. Readers can refer to Appx. C
266
Test Completion
200-
100
25-
LoGEM
50
50
50-
50
VDN-iaGEM
QTRAN-LaGEM
LMIX
25-
25
VDN
25
QTRAN
25
QMIX
200K
400K
BoOk
BooK
3M
200K
4006
bOOK
BoOk
5ook
BOOK
IN
200K
400K 6OOK Steps
BOOK
IN
Steps
Steps
Steps
Figure 6: The test task completion rate of Quarry Game with off afft actions.
Stage Hunter Game
Tesk Completion %
Quarry Same
Completion
Afforestation Game
Test Catch %
15
25
200c
400K
600K
BOOK
1M
200K
400K
6bOK
BDOK
1M
0
200K
400K
6OOK
BOCK
1M
Steps
Staps
Staps
Figure 7: Performance of MARL methods
267
6.2
Experiment Results
268
The Effectiveness of LeGEM. We answer Q1. With LeGEM, MARL methods get enhanced performance shown in Fig. 4 Without LeGEM, all methods perform poorly in Stag- Hunter Game; IQL and VDN's final final results are even O. By incorporating LeGEM, all of them can get converged performance and improved sample efficiency. We are also interested in finding if LeGEM could reinforce the performance of simple methods. As depicted in Fig. [ with LeGEM, both VDN and QMIX outperforms QPLEX, which a state-of-the-at MARL method armed with various advanced techniques, including attention network (57), ducling network [64] and advantage function.
270
272
273
274
Performance of Episodic Memory method. We answer Q2 by presenting the performance curves of EMC in Fig. 7 EMC is an episodic memory MARL method with curiosity-driven exploration. utilizes the episodic memory from RL [74] With LeGEM, QMIX outperforms EMC. EMC even
276
278
fails to converge in Htag-Hunter Game
Table 2: Results (mean and std) of n-step return (left) and TD(A) (right) on Htng-Hutter Game
12
10
15
X
0.8
0.9
0.99
1
QMIX 60.0 + 40% O + 0 0
0+0
QMIX 100 + 0% 100 + 0% 89 + 10% 61 37%
VDN 0+0 0
0 ++0 O 0 + O 0+0 0 VDN 0 o 0
0+0
0+0
Performance of n-step return and TD(A) methods. To answer Q3, we use n-step return and
280
TD(A) to estimate the TD-target. As shown Table. 2 with n-step return, both QMIX and VDN 15. Surprisingly, with TD(A), QMIX can achieve good performance with {0.8, 0.9, 0.99, 1). However, we cannot find such outcome on VDN and there no guarantee of good results on using TD(A).
fail to learn good policies even with
282
284
Performance of Multi-Agent Exploration and Risk- Sensitive MARL methods. We also provide results of exploration methods for MARL and risk- sensitive MARL
100
QMIKI #GEM
285
VON-LaGEM
286
Test Win %
IQI-LeGEM
LEGEM
method to answer Q4. MAVEN utilizes mutual information to learn latent space for exploration and RMIX aims to learning risk- policies for MARL.. In Fig. 7 RMIX even fails to Iearn. Mainly because the potential loss of reward is displaced by off-beat actions. Overall, MAVEN is stabler than EMC and RMIX. QMIX-LeGEM is stable in all scenarios and outperforms MAVEN. With LeGEM, even simple method such VDN can perform well and out- performs many MARL methods with complex and advanced components. Indeed, exploration in OBMAS is beneficial for multi-agent learning. However, the key challenge of temporal credit assignment can not be easily addressed merely with exploration.
286
50
VON
IOL
25
290
0-
0.2M
0.4M
0.6M
0.3M
292
Steps
Figure The performance of MARL meth- ods on 2m vs 1z.
294
296
287
298
SMAC. We also conduct experiments on SMAC 44 We train MARL methods and our method on 2m, Iz where are two agents combating with one opponent. To overcome the issue of
8

---

300
high dimension continuous state space, We utilize simhash 99 to calculate the hash value of the
301
key. We only select the attack action and set the action duration with 9. As illustrated in Fig. g incorporated with our novel episodie memory, QMIX, IQL. and VDN illustrate enhanced performance, demonstrating the superiority of our method on complex multi-agent scenarios.
302
303
Related Works
304
Action Delay in RL. Conventionally, the execution of actions in RL is instantaneous and the execution duration is neglected. Katsikopoulos et al. [20] propose the Delayed MDP where actions have delays
306
and Walsh et al (59] propose a model-based method for the Delayed MDP, To optimize the delayed MDP, many RL. approaches [59] (39 66) 69] augment the state space with the queuing actions to
308
be executed into the environment. However, this augeeetumentttion trick is intractable [I]. Chen
310
et al. [10] extend the delayed MDP (39] and propose a Delayed Markov Game However, the state-augmentation treatment is confined to short delays and neglects the off-beat actions in multi- agent scenarios. Recently, Bouteiller et al. [6] apply replay buffer correction method. However, the delayed timestep is privileged information. It is not available for agents in many scenarios. Simply applying this single-agent trajectory correction in MARL cannot attain satisfactory performance due to off-beat actions; devising inter-agent trajectory correction methods for OBMAS is non-trivial.
311
312
313
314
315
316
Credit Assignment in RL. Credit assignment [00 52 tackles long- long-horizon sequential decision- making problem by distributing the contribution of each single step over the temporal interval. TD learning [5T] is the most established credit assignment method, which is the basis of many RL methods.
318
319
RUDDER (2 redistributes the episodic return to key timesteps in the episode [14 42 40). Klissarov
320
et al. (22) propose a reward propogation method via graph convolutional neural network (21]. Another
line of works utilize episodic memory (EM) 33 (5) 73 27
74 to recall key events and aggregate
322
information of the past for decision-makee
or learning. However, simply applying EM of RL to
323
MARL cannot perform well in OBMAS due to the non-stationarity and the displaced rewards.
324
Multi-Agent RL. Many MARL methods focus on factorizing the global Q value to train agents' However, these existing works assume actions are
325
policies via CTDE 13, 49 executed synchronously. Messias et al. 30 propose an event-driven, asynchronous formulation of the multi-agent POMDP. However, the assumption of free communication
41 47
60
63 35
326
[61] is limited and the 34 in the paper is confined to the design of events and did not propose methods on solving challenging credit assignment issue in OBMAS. Recently, Amato et al. D
328
asynchronous execution
329
330
and Xiao et al. 667 68 propose macro-action methods, which are similar to hierarchical methods. Macro-actions are manually designed via abstracting primitive actions. However, macro-action decision-making and assume the environment can use manually pre-defined methods for state transition. Unfortunately, the above works either focus on synchronous actions or defining specific asynchronous execution components with human knowledge. Learning coordination in OBMAS remains a challenge.
332
methods mainly focus on macro-action selection during multi-timestep
333
334
335
Conclusion
336
In this paper, we investigate model-free MARL with off-beet actions. To address challenges in OBMAS, we first propose Off-Beat Dec-POMDP. Then, we propose a new class of episodic memory, LeGEM, for model-free MARL algorithms. LeGEM addresses the challenging temporal credit assignment problem raised by off-beat actions in TD-learning via the novel reward redistribution
338
340
scheme. We evaluate method on various OBMAS scenarios. Empirical results show that our method significantly boosts the multi-agent coordination and achieves leading performance as well as improved sample efficiency.
342
343
344
Limitations and Future Work. Searching from a graph-structured episodic memory takes much overhead in LeGEM. Scaling up LeGEM to complex OBMAS is our future direction. Recently. there is a growing interest in model-based planing [45) Leveraging LeGEM for model-based planning
345
346
is also our future work. Our paper focuses on Dec-POMMPP- MARL methods. We leave it to future work for investigating beat actions in frameworks like Markov Game (26] and MMDP 77]
348
We are also interested in finding the merit of our method in worldworld problem in our future work.
350 such as scheduling [29] with off-beat settings.

---

References
351
352
[1] C. Amato, G. Konidaris, L. P. Kaclbling, and J. P. How, Modeling and planning with macro- actions in decentralized pomdps. Journal of Artificial Intelligence Research, 64:817-859, 2019.
354
355
[2] J. A. Arjona-Medina, M. Gillhofer, M. Widrich, T. Unterthiner, J. Brandstetter, and S. Hochreiter. RUDDER: Return decomposition for delayed rewards. In Advances in Neural Information Processing Systems, volume 32, 2019.
356
357
358
[3] P.-.. Bacon, J. Harb, and D. Precup. The option-critic architecture. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 31, 2017.
359
360
[4] N. Biggs, E. K. Lloyd, and R. J. Wilson. Graph Theory, 1736-1936. Oxford University Press, 1986.
361
362
[5] M. Botvinick, S. Ritter, J. X. Wang, Z. Kurth-Nelson, C. Blundell, and D. Hassabis. Reinforce- ment learning. fast and slow. Trends in Cognitive Sciences, 23(5):408 422, 2019.
363
364
66] Y. Bouteiller, S. Ramstedt, G. Beltrame, C. Pal, and Binas. Reinforcement learning with random delays. In International Conference on Learning Representations, 2020.
365
77] C. Boutilier. Planning learning and coordination in multiagent decision processes. In Proceed- ings of the 6th Conference on the Theoretical Aspects of Rationality and Knowledge, pages 195-210, 1996.
387
[8] Y. Cao, W. Yu, W. Ren, and G. Chen. An overview of recent progress in the study of distributed multi-agent coordination. IEEE Transactions on Industrial Informatics, 9(1):427-433 2012.
370
371
99] M. S. Charikar. Similarity estimation techniques from rounding algorithms. In Proceedings of the thiry-fourth Annual ACM Symposium on Theory of Computing, pages 380-388, 2002.
372
373
[10] B. Chen, M. Xu, Z. Liu, L.. Li, and D.. Zhao. Delay-aware multi-agent reinforcement learning for cooperative and competitive environments. arXiv e-prints, pages arXiv-2005, 2020.
374
375
[11] E. Derman, G. Dalal, and S. Mannor. Acting in delayed environments with non non-stationary
378
Markov policies. In International Conference on Learning Representations, 2020.
377
[12] L. Espeholt, H. Soyer, R. Munos, K. Simonyan, V. Mnih, T. Ward, Y. Doron, V. Firoiu, T. Harley, I. Dunning, et al. Impala: Scalable distributed deep-RL RL with importance weighted actor-learner architectures. In International Conference on Machine Learning, pages 1407-1416, 2018
378
379
380 [13] J. Foerster, G. Farquhar, T. Afouras, N. Nardelli, and S. Whiteson. Counterfactual multi-agent policy gradients. arXiv preprint arXiv: 08926, 2017.
[14] T. Gangwani, Y. Zhou, and J. Peng. Learning guidance rewards with trajectory-space smoothing. Advances in Neural Information Processing Systems, 33:822-833 832, 2020.
383
384
[15] D. Ha and Y. Tang. Collective intelligence for deep learning: A survey of recent developments. arXiv preprint arXhv:2111.1337, 2021.
[16] B. Han, Z. Ren, Z. Wu, Y. Zhou, and J. Peng. Off-policy reinforcement learning with delayed rewards. arXiv preprint arXiv: 206. 1854, 2021.
387
388
[17] H. HU, J. Ye, G. Zhu Z. Ren, and C. Zhang. Generalizable episodic memory for deep reinforcement learning. In Proceedings of the 38th International Conference on Machine Learning, pages 4380-4390, 18-24 Jul 2021.
389
380
391
[18] C.-C. Hung, T. Lillicrap, J. Abramson, Y. Wu, M. Mirza, F. Carnevale, A. Ahuja, and G. Wayne. Optimizing agent behavior over long time scales by transporting value. Nature Communications, 10(1):1-12, 2019.
382
383
[19] M. Hüttenrauch, A. Šošić, and G. Neumann. Guided deep reinforcement learning for swarm systems. In AAMAS 2017 Autonomous Robots and Multirobot Systems (ARMS) Workshop, 2017.
395
10

---

397
[20] K. V. Katsikopoulos and S. E. Engelbrecht. Markov decision processes with delays and asynchronous cost collection. IEEE Transactions on Automatic Control, 48(4):568- -7088857,4540 2003.
396
399
[21] T. N. Kipf and M. Welling. Semi-supervised classification with graph convolutional networks arXiv preprint 1rXiv:1609002900 2016.
401
[22] M. Klissarov and D. Precup. Reward propagation using graph convolutional networks, Advances
402
in Neural Information Processing Systems, 33, 2020.
[23] J. G. Kuba, R. Chen, M. Wen, Y. Wen, F. Sun, J. Wang, and Y. Yang. Trust region policy optimisation multi-agent reinforcement learning. arXiv preprint arXiv:2109. 12511, 2021.
404
405
[24] A. K. Lampinen, S. C. Chan, A. Banino, and F. Hill. Towards mental time travel: a hicrarchical memory for reinforcement learning agents. In A. Beygelzimer, Y. Dauphin, P. Liang, and J. W. Vaughan, editors, Advances in Neural Information Processing Systems, 2021.
407
408
[25] J. Z. Leibo, E. D. nez Guzmán, A. S. Vezhnevets, P. Agapiou, P. Sunehag, R. Koster, J. Matyas, C. Beattie, Mordatch, and Graepel. Scalable evaluation of multi-agent reinforcement learning with melting pot. PMLR, 2021.
409
[26] M. L. Littman. Markov games framework for multi-agent reinforcement learning. In Machine Learning Proceedings 1994, pages 157-163. Elsevier, 1994.
412
413
[27] X. Ma and W.-J Li. State-based episodic memory for multi-agent reinforcement learning. arXiv preprint 10.00917 2021.
414
415
[28] A. Mahajan, T. Rashid, M. Samvelyan, and S. Whiteson. MAVEN: Multi-agent variational exploration. In Advances in Neural Information Processing Systems, pages 7613-7624, 2019,
[29] H. Mao, M. Schwarzkopf, S. B. Venkatakrishnan, Z. Meng, and M. Alizadeh. Learning scheduling algorithms for data processing clusters. In Proceedings of the ACM special interest group data communication, pages 270-288. 2019.
418
420
[30] V. Messias, M. T. Spaan, and P. U. Lima. Multiagent pomdps with asynchronous execution. In Proceedings of the 2013 International Conference on Autonomous Agents and Multi-agent Systems, pages 1273-1274, 2013.
421
422
423
[31] V. Mnih, K. Kavukcuoglu, D. Silver, A. A. Rusu, J. Veness, M. G. Bellemare, A. Graves, M. Riedmiller, A. K. Fidjeland, G. Ostrovski, et al. Human-level control through deep rein- forcement learning. Nature, 518(7540):529-533 2015.
425
426
[32] F. A. Oliehoek, C. Amato, et al. A Concise Introduction to Decentralized POMDPs, volume 1. Springer, 2016.
427
428
[33] A. Oliehoek, M. T. Spaan, and N. Vlassis. Optimal and approximate vavuu functions for decentralized POMDPs. Journal of Artificial Intelligence Research, 32:289-3553 2008
[34] S. Omidshafiei, A.-A. Agha- Mohammaiiaa,ii, C. Amato, and J. P. How. Decentralized control of partially observable markov decision processes using belief space macro-actions. In 2015 IEEE International Conference on Robotics and Automation (ICRA), pages 5962-5969, 2015.
431
432
433
[35] L. Pan, Rashid, B. Peng. L. Huang, and S. Whiteson. Regularized softmax deep multi-agent q-learning Advances in Neural Information Processing Systems, 34, 2021.
434
[36] W. B. Powell. Approximate Dynamic Programming: Solving the curses of dinensionality,
436
volume 703. John Wiley & Sons, 2007.
437
[37] A. Pritzel, B. Uria, S. Srinivasan, A. P. Badia, O. Vinyals, D. Hassabis, D. Wierstra, and
438
C. Blundell. Neural episodic control. In International Conference on Machine Learning, pages 2827-2836, 2017.
439
[38] W. Qiu, X. Wang, R. Yu, R. Wang. X. He, B. An, S. Obraztsova, and Z. Rabinovich. RMIX: Learning seskssens policies for cooperative reinforcement learning agents. Advances in Neural Information Processing Systems, 2021.
441

---

443
[39] S. Ramstedt and C. Pal. Real-time reinforcement learning, Advances in Neural Information Processing Systems, 32:3073-3082, 2019.
444
[40] D. Raposo, S. Ritter, A. Santoro, G. Wayne, T. Weber, M. Botvinick, H. van Hasselt, and Song. Synthetic returns for long-term credit assignment. arXiv preprint arXiv:2102.. 12425, 2021.
446
448
[41] Rashid, M. Samvelyan, C. Schroeder, G. Farquhar, Foerster, and S. Whiteson. QMIX: Monotonic value function factorisation for deep agget reinforcement learning. In Interna- tional Conference on Machine Learning, pages 4295-4304, 2018.
450
[42] Z. Ren, R. Guo, Y. Zhou, and J. Peng. Learning long-term reward redistribution via randomized return decomposition. arXiv e-prints, pages arXiv-2111, 2021.
452
[43] R. T. Rockafellar, S. Uryasev, al. Optimization of conditional value-at-risk Journal of Risk, 2:21-42 2000.
454
[44]
M. Samvelyan, T. Rashid, C. S. de Witt, G. Farquhar, N. Nardelli, T. G. J. Rudner, C.-M. Hung, H. S. Torr, J. Foerster, and S. Whiteson. The StarCraft Multi-Agent Challenge. CoRR, abs/1902.04444,, 2019.
456
457
458
[45] J. Schrittwieser, I. Antonoglou, T. Hubert, K. Simonyan, L. Sifre, S. Schmitt, A. Guez, E. Lock- hart, D. Hassabis, T. Graepel, al. Mastering atari, go, chess and shogi by planning with learned model. Nature, 588(783))6044609, 2020.
459
480
[46] D. Silver, S. Singh, D. Precup, and R. S. Sutton. Reward is enough. Artificial Intelligence, 299: 299:103535, 2021.
462
463
[47] K. Son, Kim, W. Kang, D. Hostallero, and Y. Yi. QTRAN: Learning factorize with transformation for cooperative multi-agent reinforcement learning. In International Conference on Machine Learning, pages 5887-588 5896, 2019.
464
465
[48] T. Suddendorf, D. R. Addis, and M. C. Corballis. Mental time travel and the shaping of the human mind. Philosophical Transactions of the Royal Society B: Biological Sciences, 364(1521): 2009,
467
469
[49] Sunehag, G. Lever, A. Gruslys, W. M. Czarnecki, V. Zambaldi, M. Jaderberg, M. Lanctot, N. Sonnerat, J. Z. Leibo, K. Tuyls, et al. Veloo-decoooooiiiion networks for cooperative multi-agent learning. arXiv preprint arXiv: 2017.
471
[50] R. S. Sutton. Temporal credit assignment in reinforcement learning. PhD thesis, University of Massachusetts Amherst, 1984.
473
[51] R. S. Sutton and A. G. Barto. Reinforcement Learning: An Introduction. MIT press, 2018.
475
[52] R. S. Sutton, D. Precup, and S. Singh. Between mdps and semi-mdps: A framework for temporal abstraction in reinforcement learning. Artificial intelligence, 112(1-2):111-21, 1999.
476
477
[53] A. Tampuu, T. Matiisen, D. Kodelja, I. Kuzovkin, K. Korjus, J. Aru, J. Aru, and R. Vicente.
478
Multiagent cooperation and competition with deep reinforcement learning. PLoS ONE, 12(4), 2017.
479
480
[54] H. Tang, R. Houthooft, D. Foote, A. Stooke, O. Xi Chen, Y. Duan, J. Schulman, F. DeTurek, and P. Abbeel. # exploration: A study of count- based exploration for deep reinforcement learning. Advances neural information processing systems, 30, 2017.
481
482
483
[55] E. Tulving. Memory and consciousness. Canadian Psychology/Psychologge Canadienne, 26(1):1, 1985.
484
[56] H. van Hasselt, S. Madjiheurem, M. Hessel, D. Silver, A. Barreto, and D. Borsa. Expected eligibility traces. Proceedings of the AAAI Conference on Artificial Intelligence, number 11, pages 9907-, 2021.
486
12

---

488
[57] A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, L. Kaiser, and I. Polosukhin. Attention is all you need. In Advances in Neural Information Processing Systems, pages 5998-6008, 2017.
489
[58] O. Vinyals. I. Babuschkin, W. M. Czarnekki, M. Mathieu, A. Dudzik, J. Chung, D. H. Choi, R. Powell, T. Ewalds, P. Georgiev. et al. Grandmaster level in StarCraft II using multi-agent reinforcement learning. Nature, 575(7782):300-335) 2019.
492
[59] T. J. Walsh, A. Nouri, L. Li, and M. L.. Littman. Learning and planning in environments with delayed feedback. Autonomous Agents and Multi-Agent Systems, 18(1):83-005, 2009.
485
496
[60] J. Wang, Z. Ren, T. Liu, Y. Yu, and C. Zhang. QPLEX: Duplex dueling multi-agent q-learning. arXiv preprint arXiv:2008. 00002, 2020.
497
496
[61] R. Wang, X. He, R. Yu, W. Qiu, B. An, and Z. Rabinovich. Learning efficient multi-agent communication: An information bottleneck approach. In International Conference on Machine Learning, pages 9908-9918 PMLR, 2020.
489
500
501
[62] W. Wang. T. Yang. Y. Liu, J. Hao, X. Hao, Y. Hu, Y. Chen, C. Fan, and Y. Gao. Action semantics network: Considering the effects of actions in multiagent systems. arXiv preprint 1rXiv 11611,1161112 2019.
503
[63] Y. Wang, B. Han, T. Wang. H. Dong, and C. Zhang, DOP: Off-policy multi-agent decomposed policy gradients. In International Conference on Learning Representations, 2021.
504
505
506
[64] Z. Wang. T. Schaul, M. Hessel, H. Hasselt, M. Lanctot, and N. Freitas. Dueling network
507
architectures for deep reinforcement learning. In International Conference on Machine Learning. pages 1995- 2003, 2016.
508
509
[65] C. J. Watkins and P. Dayan. Q-Learning. Machine Learning, 8(3-4)279-299,, 1992.
510
[66]
T. Xiao, E. Jang, D. Kalashnikov, S. Levine, J. Ibarz, K. Hausman, and A. Herzog. Think- ing while moving: Deep reinforcement learning with concurrent control. In International Conference on Learning Representations, 2019.
512
513
[67] Y. Xiao, J. Hoffman, and C. Amato. Macro-action-based deep multi-agent reinforcement learning. In Conference on Robot Learning, pages 1 1146-1161. PMLR, 2020.
514
515
[68] Y. Xiao, J. Hoffman, T. Xia, and C. Amato. Multi-agent/robot deep reinforcement learning with macro- aaccoonatiioss (student abstract). In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 13965-13966, 2020.
516
517
518
[69] Y. Yuan and R. Mahmood. Asynchronous reinforcement learning for real-time control of physical robots. arXiv preprint M.XXi::2003.227555 2022.
[70] T. Zahavy, B. O' O'Donoghue, G. Desjardins, and S. Singh. Reward is enough for convex mdps. Advances in Neural Information Processing Systems, 34, 2021.
521
522
171] L. Zheng, J. Chen, J. Wang, J. He, Y. Hu, Y. Chen, C. Fan, Y. Gao, and C. Zhang. Episodic multi-agent reinforcement learning with curiosity-driven exploration. Advances in Neural Information Processing Systems, 34, 2021.
523
524
525
[72] M. Zhou, J. Luo, Villella, Y. Yang. D. Rusu, J. Miao, W. Zhang, M. Alban, I. Fadakar, Z. Chen, et al. Smarts: Scalable multi-agent reinforcement learning training school for autonomous driving, arXiv preprint arXiv:2010.09770 2020.
526
527
[73] Y. Zhou, D. E. Asher, N. R. Waytowich, and J. A. Shah. On memory mechanism in multi-agent reinforcement learning. arXiv e-prints, pages arXiv-1909, 2019.
529
530
[74] G. Zhu, Z. Lin, G. Yang, and C. Zhang. Episodic reinforcement learning with associative memory. In International Conference on Learning Representations, 2020.
531
13

---

Checklist
532
533
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
535
contributions and scope? [Yes] See Sec. 4
536
(b) Did you descrihe the limitations of your work? [Yes) See Sec. g
537
(c) Did you discuss any potential negative societal impacts of your work? [No] Our method does not have negative social impacts.
538
539
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
542
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See the statements.
543
544
(b) Did you include complete proofs of all theoretical results? [Yes] See Appx.
545
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed reproduce the main ex- perimental results (either in the supplemental material or as a URL)? [Yes] See the supplementary files.
547
519
(b) Did you specify all the training details (c.g.. data splits, hyperparameters, how they were chosen)? [Yes] See Appx. E
550
(c) Did you report error bars (e.g.. with respect the random seed after running experi- ments multiple times)? [Yes] See Sec. Appx. F
552
559
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [Yes] See Appx. [B]
4. If you using existing assets (e.g., code, data, models) or curating/releasing new assets...
556
(a) If your work uses existing assets, did you cite the creators? [Yes] We cited, see Sec. 6
(b) Did you mention the license of the assets? [Yes] See Appx. B
(c) Did you include any assets either in the supplemental material URL? [Yes]
559
See the supplementary files.
580
(d) Did you discuss whether and how consent was obtained from people whose data you'l 're using/curating? [N/A]
561
562
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
564
5. If you used crowdsourcing conducted research with human subjects...
565
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
567
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
588
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
570
14


Reviews:
[{"review_id": "tkFPsBX7ku", "reviewer": "Reviewer_Y4Go", "summary": "This work introduces a novel generalization of Dec-POMDPs that also takes different execution durations for actions into account. Furthermore, the authors propose a novel approach that uses graph algorithms to search for critical points in agent trajectories. These points are used to assign rewards to the corresponding action. In a series of multi-agent tasks, which are modified such that they exhibit off-beat actions, LeGEM enhanced algorithms are compared to baselines. The baseline algorithms span simple MARL algorithms to memory enhanced, more sophisticated approaches.", "questions": "- The experiments only involve a few agents. How is the performance influenced by adding more agents, e.g. up to 100's? It would be valuable to have one experiment that explores this.\n- From the experiments you run, how much overhead is approximately introduced by the graph updates/search?", "limitations": "The authors admit that their approach introduces a large computational overhead and that scalability was not addressed in this paper.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Originality\n\nThe paper introduces off-beat Dec-POMDPs, a novel generalization of delayed MDPs and Dec-POMDPs. The approach uses levelled-graphs to represent the episodic memory. This apprears to be a novel combination of levelled-graphs and deep MARL methods.\n\n*Minor Remark:* While you include [74] in the experiments section, it should also be cited in section 4.1 as another approach that uses graphs to structure EM.\n\n**Strengths:**\n\n- Novel application of established data structures/algorithms to deep RL\n\n**Weaknesses:\n-**\n\n## Quality\n\nThe approach seems to be valid in general. The experimental evaluation is a major strength of this paper. First, the authors identify relevant questions to address. The experiment design is adequate as it demonstrates the efficacy of their approach along several dimensions, such as performance improvements of existing approaches and comparisons to alternative episodic memory approaches. Thus, the experiments undermine the claimed contributions.\nIt would have been interesting to see how much computational overhead (e.g. training time) is induced by the graph updates and the search. You may consider to include some comparisons in this direction to other EM approaches. Furthermore, investigating the performance of LeGEM in many-agent tasks would be important.\n\n**Strengths:**\n\n- Algorithms appear to be sound\n- Well formulated questions to answer\n- Strong experimental evaluation: well chosen baselines and experiments\n\n**Weaknesses:**\n\n- No experiment addressing computational overhead\n- Experiments only involve a few ($\\leq$ 3) agents.\n\n## Clarity\n\nIn general, the paper is well written. However, the notation that is introduced is rather heavy (many indices, sub-indices, etc...) and uses many symbols. This is especially true for section 4 and the algorithm pseudo code. Also, $\\Upsilon$ is not defined in the main paper, only in the appendix. Also, the training procedure (Fig. 3) could be addressed more clearly.\nBrowsing through the code helped when trying to understand the algorithms. However, it would have been nice to also include a file that runs an experiment or trains a policy. Why did you not include the training script?\n\n**Strengths:**\n\n- Generally well written paper.\n- Code was provided.\n\n**Weaknesses**:\n\n- The amount of symbols and indexed symbols makes it somewhat hard to read.\n- No training script/executable included.\n\n## Significance\n\nThe problem addressed in the paper, off-beat actions, is novel and most probably important for real world applications of RL. Furthermore, the proposed approach could be a stepping stone for other works exploring this new problem setting. Also the evaluation of other algorithms on this kind of problem is valuable. \nThe performance was demonstrated on simple tasks. The results could be more convincing if you would include an experiment with more agents (e.g. 20).\n\n**Strengths:**\n\n- Significant problem with plausible real-world connection\n\n**Weaknesses:**\n- The tasks that were solved are rather simplistic.", "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": "oJL3lyeKd70", "reviewer": "Reviewer_eRuo", "summary": "This paper addresses the issue in off-beat multi-agent reinforcement learning, where the actions have pre-set execution durations. During execution, the environment changes are influenced by, but not synchronized with, action execution. This off-beat issues exit in scenarios, such as traffic lights and video games. To mitigate this issue, the authors propose an episode memory module, i.e., Levelled Graph Episodic Memory (LeGEM) method. The authors propose a search method to search the pivot timestep and utilize a proximal ranking method to estimate the pivot timestep, which invokes the future reward. The authors evaluate the proposed method in different scenarios, including Stag-Hunter Game, Quarry Game, Afforestation Game, and StarCraft II micromanagement tasks. The empirical experimental results show that LeGEM can boost the performance of existing RL such as IQL, VDN, QTRAN, and QMIX. ", "questions": "* How does LeGEM compare to other credit assignment methods, such as RUDDER?\n* How does the training time of IQL, VDN, QTRAN, and QMIX compare to the training time of IQL-LeGEM, VDN-LeGEM, QTRAN-LeGEM, and QMIX-LeGEM?\n* Does LeGEM also improves the performance in the general environments without the off-beat issue?", "limitations": "* The proposed method seems limited to the off-beats scenarios. It would be better if the proposed method improves the performance in the general environments.\n* LeGEM introduces additional computational overhead. It might be difficult to utilize LeGEM in large scale settings.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The strengths of the paper:\n\n* The paper is well motivated and the problem is well defined. \n* The proposed memory module shares connections with the human learning process and shows performance improvement in the experiments. \n* The paper is well structured and well written. The figures in the paper help the reader to understand the idea. \n\nThe weaknesses of the paper:\n\n* The baselines used in the experiments are relatively “weak”, including IQL, VDN, QTRAN, and QMIX, in the sense that they are not specially designed to solve the off-beat problem. Stronger baselines should be used. For example, the methods, which tackle the credit assignment problem should be compared, such as RUDDER [Arjona-Medina et al, 2019].  \n* The LeGEM module includes the search process. I have concerns about the training time. \n* The off-beats problem exits but not very general.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "fGhtpX0FEw8", "reviewer": "Reviewer_dJd4", "summary": "This paper looks at the problem of coordination games where actions may have a delayed impact on the environment, which are referred to as \"off-beat actions\". To appropriately credit these off-beat actions they proposed a graph-based memory structure (LeGEM). It works by building a count-based graph of possible histories and searches for differences in graphs to assign future rewards to off-beat actions. They demonstrate their algorithm's ability to encourage coordination on three analytic games and the StarCraft II micromanagement task suite. Their results suggest LeGEM leads to a higher probability of successful coordination. ", "questions": "1. Could the authors explain how modelling the actions as having a delayed effect on the transition dynamics is usefully different here than just considering that the reward might be delayed?\n\n2. It seems like the multi-agent aspect of this problem is simply that there are decentralized unit-actions. Why did the authors not consider comparing this work to single-agent off-beat algorithms? It seems that they might be applied directly or with small modifications and provide reasonable baselines. \n\n3. I am hoping the authors might better justify their choice of model for off-beat actions. Initially the exposition introduces them like a sub-system within the environment dynamics, but they're modelled as a process that occurs prior to transition. Moreover, the off-beat calculation is ego-tistically considering only a single agent. However, this paper focus is on games, should off-beat actions not consider other-agents and their influence on delays? \n\n4. Could the authors please clarify how their model \"find[s] an off-beat reward in a trajectory\" (L171). All formalisms seem to suggest that an agent receives a single scalar reward at each timestep, but it's not clear how this could be decomposed into rewards from multiple co-occurring off-beat action rewards? \n\n5. Nit: the line spacing on page 6 is off.\n\n6. L124-5: \"there is no MARL method that can explicitly recall the past and identify key states that lead to future reward\" This seems like a pretty large claim that I don't think is genuine. Tabular methods have explicitly built state-return mappings in the past. \n\n7. Could the authors please comment on how this method compares to reward shaping. It seems like reward shaping methods might be comparable baselines as it could amount to modifying the credit assignment pattern for an agent. \n\n8. Do the authors have any analysis or ablation studies on the different components of their algorithm? It would be interesting to see which search patterns / heuristic are useful and under what settings a practioneer may want to use them (or not).", "limitations": "The authors should include their limitation discussion to note that (a) this method only works for strictly cooperative games, and (b) methods where all information can be perfectly shared across all agents. ", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n- Addresses, indirectly, a challenging problem of ascribing delayed-credit to actions. \n\n**Weaknesses**\n- As a non-expert on \"off beat\" systems I found the introductory exposition challenging to read. An \"off beat\" action is not fully defined until page 3. I would suggest the authors provide motivating examples and describe the particular problem of \"off beat\" actions that they will study much earlier in the paper. \n- There are many claims that are not appropriately supported. Non-exhaustive list of examples: L38-44 contains many \"challenges' of OBMAS that is neither cited nor proven why this is a quality and problem unique to OBMAS; L52-53, it's not super clear at this point what is meant by \"delayed timestep of the actions\" or why this might be privileged information and why this is meaningful; L236 Proposition 1 is not proved, you could imagine an adversarial reward redistribution that prevents a contraction.\n- The experiments are focused around \"outperforming\" various MARL methods, but not on understanding the method and problem proposed. ", "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": "FugpZ_VAhsq", "reviewer": "Reviewer_CAwi", "summary": "This paper aims to address the delayed action problem in multi-agent reinforcement learning. The authors propose LeGEM, a episodic memory structure that improves the temporal credit assignment by searching for the pivot timestep and reward redistribution. The method is evaluated on four game domains.", "questions": "Please see the weakness 2-6 and comments on the experiments.", "limitations": "The authors address some of the limitations and I do not see the potential negative societal impact.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths:**\nThis paper looks at an interesting and practical perspective of MARL, namely the delayed action. While it has been explored in the single-agent domain, there are fewer studies in the multi-agent domain. \n\n**Weaknesses:**\nI found it is overall hard to follow the paper:\n1. The search scheme I part (Section 4.2) lacks explanation and intuition. There is little to no explanation of the notations in the algorithms., for example, $\\Upsilon, \\mathbf r^{l, i}, e^i_t[j]$, the meaning of -1 in Algorithms 2 etc. (and there are more examples like these in the paper). The missing information greatly impedes understanding. \n2. Many new concepts come up without further mentioning or explanation, such as “subserve the inter-agent credit assignment”. What exactly is inter-agent credit assignment? How does it help?\n3. Line 195: “the accuracy of Scheme I is over 90% in grid world scenarios.” What does “grid world” refer to? How is the accuracy defined?\n4. I do not quite understand why Scheme II, a simplified version of Scheme I is able to deal with “more complex scenarios, whose trajectories are multiple-off-beat-reward trajectories”. \n5. What is the role of $\\beta$ in Equation (2)? How to interpret it?\n6. Why does the off-beat bellman operator enjoy contraction property?\n\nThe experiment part is not convincing either:\n* If the key is to identify the pivot timestep, shouldn’t there be some experiments to investigate the accuracy of that? \n* The experiment environments are simple, with a maximum of three agents, short horizons, and small actions space. Could this be related to the scalability of the graph search method?", "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: Reject