1

Deep Reinforcement Learning for Event-Driven
Multi-Agent Decision Processes

arXiv:1709.06656v1 [cs.AI] 19 Sep 2017

Kunal Menda, Yi-Chun Chen, Justin Grana, James W. Bono, Brendan D. Tracey,
Mykel J. Kochenderfer, David Wolpert

Abstract—The incorporation of macro-actions (temporally extended actions) into multi-agent decision problems has the
potential to address the curse of dimensionality associated with
such decision problems. Since macro-actions last for stochastic
durations, multiple agents executing decentralized policies in
cooperative environments must act asynchronously. We present
an algorithm that modifies Generalized Advantage Estimation
for temporally extended actions, allowing a state-of-the-art policy
optimization algorithm to optimize policies in Dec-POMDPs in
which agents act asynchronously. We show that our algorithm is
capable of learning optimal policies in two cooperative domains,
one involving real-time bus holding control and one involving
wildfire fighting with unmanned aircraft. Our algorithm works
by framing problems as “event-driven decision processes,” which
are scenarios where the sequence and timing of actions and
events are random and governed by an underlying stochastic
process. In addition to optimizing policies with continuous
state and action spaces, our algorithm also facilitates the use
of event-driven simulators, which do not require time to be
discretized into time-steps. We demonstrate the benefit of using
event-driven simulation in the context of multiple agents taking
asynchronous actions. We show that fixed time-step simulation
risks obfuscating the sequence in which closely-separated events
occur, adversely affecting the policies learned. Additionally, we
show that arbitrarily shrinking the time-step scales poorly with
the number of agents.

I. I NTRODUCTION
N cooperative multi-agent environments, policies become
difficult to optimize using reinforcement learning due to
the curse of dimensionality. Additionally, the delay between
accrued rewards and responsible action is a significant problem
in cooperative multi-agent systems, where one agent may
receive undeserved reward from favorable actions performed
by other agents. A possible way to address these problems is
to have agents learn multi-step macro-actions, rather than the
low-level primitive actions typically considered in reinforcement learning algorithms.

I

K. Menda and M.J. Kochenderfer are with the Aeronautics and Astronautics Department at Stanford University, Stanford, CA USA (e-mail:
{kmenda,mykel}@stanford.edu).
Y. Chen is with the Institute for Computational and Mathematical Engineering at Stanford University, Stanford, CA USA (email: yichunc@stanford.edu).
J. Grana is with the Santa Fe Institute, Santa Fe, NM USA (email:
justin.grana@santafe.edu).
J.W. Bono is with Economists Incorporated, San Francisco, CA USA
(email: jwbono@gmail.com).
B.D. Tracey is with the Santa Fe Institute, Santa Fe, NM USA, and
is associated with the MIT Department of Aeronautics and Astronautics,
Cambridge, MA USA (email: btracey@santafe.edu).
D. Wolpert is with the Santa Fe Institute, Santa Fe, NM USA, and
is associated with the MIT Department of Aeronautics and Astronautics,
Cambridge, MA USA, as well as Arizona State University, Tempe, AZ USA
(email: david.h.wolpert@gmail.com).

Suppose we were to use reinforcement learning to learn a
policy to fly an unmanned aircraft to a nearby forest. Learning
the precise actuator commands from the single reward of
whether or not we got there would be intractable. Macroactions are typically defined by a policy that maps observations
to primitive actions and a set of conditions specifying when the
macro-action terminates [1]. We can pre-train macro-actions
to perform higher level tasks such as way-point tracking, and
have a policy learn to use them to navigate to our goal.
When considering cooperative multi-agent environments,
the problem of mapping a single reward for successful cooperation to each individual agent’s primitive actions becomes
exponentially more difficult as we scale the number of agents.
For this reason, the use of macro-actions becomes substantially
more necessary. For example, consider a problem in which
many unmanned aircraft must cooperate to extinguish multiple
fires. By restricting our action space to only high-level macroactions (such as fly to a specified fire, or attempt to extinguish a
fire), we can rely on traditional controllers to execute the lowlevel control policies required by these macro-actions. With
macro-actions, we can substantially reduce the size of the state
space (as many of the degrees-of-freedom pertaining to the
pose of any given aircraft may not be relevant at this level of
abstraction), as well as significantly reduce reward-delays and
ease credit assignment. We can now attribute the rewards of
extinguishing a large fire to the fact that we attempted to do so
alongside a supporting agent, as opposed to a long sequence
of low-level observations and actuator inputs.
Even when considering only decentralized policies in which
each agent makes an independent decision based on their
partial observation of the environment, a challenge arises
when extending the use of macro-actions to cooperative
multi-agent domains. Since macro-actions are temporally extended, agents executing decentralized policies must act asynchronously. However, few off-the-shelf reinforcement learning
algorithms consider the problem of multiple-agents acting
asynchronously. To address asynchronicity, we view such a
multi-agent decision process as event-driven, where agents
choose a new macro-action when prompted by an event in
some set of events occurring in the environment (such as
completion of the currently executed macro-action, or the
availability of new information). This article presents a method
for learning optimal macro-action policies for event-driven
decision processes.
In many real world problems, the duration macro-actions
are active are drawn from continuous distributions. However,
current methods for planning and learning with macro-actions

2

in multi-agent settings simulate the environment by discretizing time into fixed time-steps, as well as using discretized
state and action spaces [2] [3] [4] [5]. When using macroactions in multi-agent environments, temporal discretization
poses a unique problem because assuming a fixed time step
may group more than one temporally distinct event within a
single time step. We refer to this as a race condition. In these
race conditions, information about the relative timing of the
events is lost, and learning with such a simulation environment
can lead to optimized policies that transfer poorly to the real
world.
As an example in which event-sequences can affect the
policy learned, consider two aircraft which can each fly to one
of two locations or remain in place. If they choose the same
location to fly to, they both accrue a large negative reward (as
they may collide and crash). If they choose different locations,
they accrue a small positive reward. Given this, we may have
that one agent chooses a location first, and the other observes
that choice and decides to fly to the other location. However,
if the time-step was large enough such that both agents always
had to choose their action simultaneously, they may be forced
to learn a strategy in which they both always choose the safe
option of remaining in place.
At the cost of computation time, one could mitigate the
risk of race conditions by arbitrarily shrinking the time-step.
However, we will demonstrate that in order to maintain a
chosen threshold for the probability of a race condition, one
must decrease the time-step quadratically with the number of
agents. Since the computation time for a simulation is typically
inversely related to the time-step, the computation time also
scales quadratically with the number of agents.
Representing policies as deep neural networks has shown
success in the domain of decentralized multi-agent decision
making [6], and allows for the representation of continuous
state-spaces when trained with policy gradient methods. This
paper presents an extension of the PS-TRPO algorithm [6] to
accommodate temporally extended actions, which both allows
for continuous state-space representation and does not assume
a fixed time-step. By using such an algorithm, we can simulate
event-driven processes using event-driven simulators, which
step from event to event as opposed to from time-step to timestep. By making use of such simulators, we can eliminate race
conditions and scale the number of agents while only linearly
scaling the computation time of the simulation.
This article presents two key contributions. The first contribution is a modification to the PS-TRPO algorithm that allows
it to optimize macro-action policies. In addition to interfacing with event-driven simulation and continuous state/action
spaces, the algorithm does not require any expert demonstrations for policy optimization, unlike a state-of-the-art algorithm in this domain [3]. We demonstrate that our algorithm is
able to learn optimal policies in cooperative multi-agent environments, including real-time bus holding control and wildfire
fighting with unmanned aircraft. The second contribution is a
pair of experiments on the wildfire domain that demonstrate
the utility of moving from fixed time-step simulations to eventdriven simulations. The first of these experiments shows that
large time-steps can result in race conditions that cause poor

policy transfer between simulation and the real world, and the
second demonstrates that mitigating the risk of race conditions
forces a quadratic decrease in time-step with the number of
agents.
To our knowledge, in addition to being able to interface with
event-driven simulators, our algorithm will be the first that uses
deep reinforcement learning to optimize decentralized macroaction policies in multi-agent environments. While other research on macro-actions allow for planning over multiple
levels of hierarchy, this paper will focus on the case in which
learning is over macro-actions that exist at a single level of
hierarchy, leaving the extension to full hierarchical learning to
future work.

II. P RELIMINARIES

AND

R ELATED W ORK

A. Generalized Advantage Estimation and TRPO
Policy gradient methods are widely used for optimizing
policies through reinforcement learning. In these methods, we
define a policy as a mapping from a history of observations
o0:k to a distribution over actions at the kth decision-instant.
A policy ψθ (o0:k ) is parameterized using some parameter
vector θ. Policy gradient methods update θ by estimating the
gradient direction that improves performance the most. Generalized Advantage Estimation (GAE) is a method for computing
approximate policy gradients from simulation trajectories [7].
Previous policy-gradient methods, though providing unbiased
estimates of the policy gradient, result in gradient estimates
with high variance that worsen with long time-horizons. Further, it is argued that GAE, which is a method specified by
two hyper-parameters γ and λ, reduces this variance while
maintaining a tolerable level of bias [7].
GAE defines the advantage function A(sk , ak ) to be the
difference between V (sk ) and Q(sk , ak ), where V (sk ) is the
value being in state s at the decision-instant k and Q(sk , ak ) is
the value of taking action a from state s at the decision-instant
k ∈ N. They incorporate the hyper-parameter γ as follows:
γ

V (sk ) := Esk+1:∞ ,ak:∞

"

∞
X

Qγ (sk , ak ) := Esk+1:∞ ,ak+1:∞

l

γ rk+l

l=0
"∞
X

Aγ (sk , ak ) := Qγ (sk , ak ) − V

#

γ l rk+l

l=0
γ
(sk )

(1)
#

(2)
(3)

where rk is the reward received from taking action ak from
state sk . The discounted approximation to the policy-gradient
is then defined as:
"∞
#
X
γ
γ
g := Es0:∞ ,a0:∞
A (sk , ak )∇θ log ψθ (ak | sk )
(4)
k=0

When a policy is used to simulate a batch of episodes in
one training epoch, the GAE advantages are estimated by
first computing δkV , which is an estimate of the immediate

3

advantage of action of ak , and then the GAE advantage
GAE(γ,λ)
estimate Ak
as follows:
δkV : = rk + γV (sk+1 ) − V (sk )
∞
X
GAE(γ,λ)
V
Ak
=
(γλ)l δk+l

(5)
(6)

l=0

Here, V (sk ) is the approximate value function, referred to as a
baseline, and λ is a hyper-parameter that is used in addition to
γ to control the bias-variance trade-off in gradient estimation.
The baseline V (sk ) is also a function approximator (such as
a linear mapping or neural network) parameterized by some
vector φ. Once the advantages are computed, an algorithm
such as Trust-Region Policy Optimization (TRPO) updates
the parameters θ by constraining the KL-divergence between
the previous and new function approximations, and updates
φ by training the baseline model with supervised learning to
map states to their average discounted returns in the set of
trajectories [8].

Planning over macro-actions in Dec-POMDPs can be formalized as a MacDec-POMDP [9]. Since macro-actions can
extend over arbitrary time horizons, we must treat our decision
process as a semi-MDP and find an optimal policy ψ that maps
an agent’s observation history to a macro-action. The current
state-of-the-art model-free reinforcement learning algorithm
for optimizing policies in the MacDec-POMDP setting is
the PoEM algorithm [3]. This algorithm aims to optimize a
finite state controller (FSC) that represents a macro-action
policy using expectation-maximization (EM). The algorithm
is shown to scale linearly with the number of agents, but
quadratically with the number of nodes in the FSC, a number
which is proportional to the discretization of the observation
and action space. Additionally, the algorithm generates experience histories by requiring demonstrations from an expert
heuristic controller. In this paper, we will extend the PSTRPO algorithm to optimize policies in MacDec-POMDPs,
preserving the algorithms’ ability to optimize over continuous
state and action spaces and requiring no expert demonstrations
for policy optimization.

B. Dec-POMDPs and PS-TRPO
Initial efforts to extend the partially observable Markov
decision process (POMDP) framework to multi-agent settings
attempted centralized control over the joint state and action
spaces of all agents, making planning intractable. To address
this problem, efforts have been dedicated to solving decentralized versions of the same problems, in which each agent
has access to only some local observation of the state space
(which may include additional information communicated by
other agents), and must choose their action based on only that
observation. PS-TRPO is an extension to the TRPO algorithm
to cooperative multi-agent domains modeled as decentralized
POMDPs (Dec-POMDPs), in which multiple agents act in
a single environment with decentralized execution of the
same policy ψθ [6]. Here agent i’s kth action is given by
ai,k ∼ ψθ (oi,0:k ), where oi,0:k is the ith agent’s observation
history. The parameters θ of ψθ are then updated by the
TRPO algorithm using advantages computed from all agents’
trajectories. They assume a reward structure in which all
rewards are shared jointly by agents.
C. MacDec-POMDPs and The PoEM Algorithm
A policy in a Dec-POMDP is a mapping from an agent’s
local observations to their local action. However, we may
want to optimize a policy in an environment in which the
observation spaces high-dimensional. There often exists a
natural hierarchical abstraction over the policy space, in which
high-level controllers issue commands to low-level controllers,
which lead to the development of the options framework [1].
An agent i’s option, or macro-action space Mi is defined as
containing macro-action tuples mi = hIim , βim , πim i, where
for each macro-action mi ∈ Mi , Iim specifies a set of states
from which the macro-action can be initiated, βim specifies
the probability of the action terminating in any given state
after having been initiated, and πim specifies the low-level
controller corresponding to that macro-action, mapping the
agent’s observation to a primitive (non-macro) action.

III. E XTENDING PS-TRPO T O M AC D EC -POMDP S
To extend the PS-TRPO algorithm to optimize macroaction policies, we must address the fact that actions are
asynchronous and temporally extended. We begin by framing
a MacDec-POMDP as an event-driven process, allowing us to
associate decision instants to discrete events. With this framework, we can modify GAE to allow PS-TRPO to optimize a
policy with trajectories generated from MacDec-POMDPs.

A. MacDec-POMDPs as Event-Driven Processes
Similar to the definition of the option presented in Section II-C, we define the macro-action space as the tuple
hIim , Eim , πim i. For each macro-action m, Iim and πim are
the set of states from which agent i can take the macroaction and the lower-level controller the macro-action specifies, respectively. However, Eim now specifies a set of events,
the triggering of any of which terminates the macro-action,
prompting the agent to select another macro-action given a
new observation. In our example where unmanned aircraft
coordinate to extinguish fires, the macro-action chosen by one
aircraft may be to fly to a particular fire. A lower-level policy
tuned to optimally carry out this order would take over control
until a relevant event occurs, such as receiving information that
the fire being flown to was just extinguished. When such an
event occurs, the agent would be given a new observation and
the opportunity to choose a new action.
Unlike conventional MDPs, agents may receive rewards at
any instant in time, not just when an event prompts them to
act. For example, if rewards were given to the whole team for
accomplishments, one agent may accrue a reward for the team
without triggering an event that prompts the another agent to
choose a new action. Hence, we adopt a convention by which
all rewards accrued by an agent over the duration ∆ti,k , in
which macro-action mi,k is being carried out, can be collected

4

into a single reward to associate with that macro-action. We
let:
Z ∆ti,k
Jk
X
e−γt ci,k (Ti,k + t)dt
(7)
e−γ∆τj ρj +
ri,k =
0

j=0

Ti,k =

k−1
X

Stop 1

∆ti,j

(8)

j=0

Here, ρ0:Jk are the Jk discrete rewards accrued by agent i at
times Ti,k +∆τ0:Jk , ci,k (t) is a continuous-time reward generator over the interval that the macro-action is being executed,
and γ is the continuous-time discount rate. The rewards ρ0:Jk
are accrued on events occurring in the environment during the
time when an agent’s kth macro-action is active.
B. Adapting GAE for Temporally Extended Actions
A simulation episode will now generate a trajectory
h. . . , oi,k , mi,k , ∆ti,k , ri,k , . . .i for each agent i. With these
trajectories, we can modify Equations 5 and 6 in GAE to
account for the temporal extension of actions. We will refer
to GAE modified for macro-actions as M-GAE. The modified
equations are:
V
δi,k
= ri,k + e−γ∆ti,k V (oi,k+1 ) − V (oi,k ) (9)
∞
X
M−GAE(γ,λ)
V
Ai,k
=
e−γλ(Ti,l −Ti,k ) δk+l
(10)
l=0

The modifications now factor in the duration over which
macro-actions are active into the discounted sum of rewards
that is associated to the taking of each macro-action, as
opposed to assuming every action lasts a single time-step.
Using M-GAE, the PS-TRPO algorithm can now optimize
policies in MacDec-POMDPs framed as event-driven processes.

Stop 2

Stop 3

...

Stop K

Fig. 1. An example bus corridor.

Even though not every real-world environment is eventdriven, modeling one as an event-driven process does not
necessarily sacrifice much simulation fidelity. For example,
suppose that we have two aircraft, intending to fly to two
different fires. We can simulate their individual flights by
sampling a duration for each aircraft from a distribution
dependent on their desired flight path and average velocities.
We can then assert that after those durations have elapsed, each
aircraft will have reached their respective fires. By doing so,
we can treat the initiation and termination of each agent’s flight
as distinct events, allowing the simulator to skip simulating
anything in-between. In this example, we do, however, lose
the ability to simulate the influence flight paths have on each
other. This simplification may be benign because we want to
learn high-level policies that may not need to take into account
these details.
To motivate the use of event-driven simulation, in the latter
part of the next section we will demonstrate that the choice
of step-size can have adverse affects on the quality of policy
learned in simulation. Though we can always shrink the stepsize by a sufficient amount to ensure high-fidelity simulation,
we will show through a set of Monte-Carlo experiments that
doing so causes the computational cost of simulation to scale
poorly with the number of agents compared to an event-driven
simulation.
V. P ERFORMANCE E XPERIMENTS

IV. E VENT-D RIVEN S IMULATORS
Many methods for learning policies in multi-agent settings
assume that simulations are performed with some fixed stepsize. However, in reality, the timings of the various agents’
decisions may be drawn from continuous, stochastic distributions. As mentioned earlier, using simulators with fixed
time-steps leaves the possibility open that more than one
relevant event can occur in the same time-step. Consequently,
a fixed time-step simulation obfuscates the relative timing of
these events, and may result in policies being learned on the
simulator that transfer poorly to the real world, where the
sequences may be important.
A key advantage of framing MacDec-POMDPs as eventdriven processes is that it allows us to use event-driven simulation. Event-driven simulators, such as the Python module
SimPy [10], step the environment from event to event as
opposed to from one time-step to the next. Underlying the
simulation is the assumption that all entities cycle through first
performing some instantaneous processing, and then yielding
until some event they specify occurs, which could be the lapse
of some specified amount of time.

The experiments in this section validate the claim that the
PS-TRPO algorithm with M-GAE is able to optimize policies
in multi-agent environments where agents select from a space
of temporally extended actions. The real-time bus holding
problem will be used to validate this claim. This section also
shows the benefit of using event-driven simulators over fixed
time-step simulators in the wildfire fighting problem.
A. Real-Time Bus Holding
Consider a fleet of buses servicing the bus-corridor, shown
in Figure 1. Buses sequentially visit a set of stops numbered
1 though K, returning to Stop 1 after the loop completes, unloading all passengers, and repeating the cycle. A phenomenon
called bus bunching can occur, in which buses queue to visit a
set of stops, leaving no time between their arrivals, after which
a long delay occurs until the bunch cycles back to the stop.
This phenomenon leads to unreliable and sub-optimal service,
and the research community has explored a strategy called
bus holding to mitigate the issue. In this control strategy, a
bus is instructed to hold at its current stop for some specified
amount of time, in addition to the time it waits for passenger

5


0



1
ai,k (hi,k ) =

2



3

if
if
if
if

hi,k > T1
T2 < hi,k < T1
T3 < hi,k < T2
hi,k < T3

TABLE I
E NVIRONMENT PARAMETERS USED IN R EAL -T IME B US H OLDING
EXPERIMENTS

Parameter

Value

N
K
Lmax
rtk={1,..,10}
ta
tb
H
Thold

6
10
75
180
1.8
3.0
6.0
30.0

Stop

qk

1
2
3
4
5
6
7
8
9
10

1.0
0
0.1
0.25
0.25
0.5
0.5
0.1
0.75
0.1

Unit

νk

Buses
Stops
pax
s
s
s
min
s
 pax 
min

1.5
2.25
1.4
4.5
2.55
1.8
1.43
1.05
0.75
0.45

TABLE II
PARAMETERS USED FOR MLP POLICY REPRESENTATION AND TRAINING
IN R EAL -T IME B US H OLDING EXPERIMENTS
Parameter

Value

Unit

MLP Hidden Size
γ
λ
TRPO Max Step
Batch Size

32
10−5
2.0
0.01
540

neurons
s−1
episodes
epoch

was average return under the same reward function used to
optimize the MLP policy with the same episode length.
2) Results: As shown in Figures 2 and 3, the optimized
MLP policy is able to achieve an average total return per
episode that is substantially greater than those of the No Holding and Optimized Thresholds policies, though the Optimized
·106
0
−1
Average Return

boarding and alighting. The problem has previously been
framed as a Dec-POMDP, and effective decentralized policies
have been discovered through reinforcement learning [11]. We
will follow the problem formulation described by Chen et al.
[11], and show that PS-TRPO with M-GAE generates polices
that match their results in performance.
1) Problem Specification: Our environment consists of a
bus corridor of N buses and K bus stops. All agents are
initialized in a queue for access to Stop 1, with Bus 1 being
the first in the queue and Bus N being the last. Upon arrival
at Stop k, Ui,k = ⌊qk · Li,k ⌉ passengers will attempt to
alight the bus, where qk ∈ [0, 1] and Li,k ∈ [0, Lmax ] is the
load of the bus when reaching Stop k. Here, ⌊·⌉ is used to
indicate rounding to the nearest integer. Additionally, Bi,k =
min(⌊νk · hi,k ⌉, Lmax − Li,k + Ui,k ) passengers will attempt to
board the bus, where νk ∈ [0, ∞) is the passenger arrival rate,
and hi,k is the headway between Bus i and Bus i − 1 ahead
of it, defined as the time elapsed between the departure of
Bus i−1 and the arrival of Bus i at Stop k. The bus will wait a
nominal amount of time of Si,k = max(ta Ui,k , tb Bi,k ), where
ta and tb are the rate at which passengers alight and board,
respectively. The bus will then wait an additional amount of
time chosen from its action space before departing from the
stop. The bus will then travel for time rtk+1 to Stop k + 1,
and join the queue for arrival at that stop.
Upon arriving at a stop, Bus i will receive an observation
of [z1 , z2 , z3 , z4 ], where z1 is the current stop’s index, z2
is the headway hi,k , z3 is the current load Li,k , and z4 is
the sojourn-time elapsed between its current and previous
observations. The bus then selects a holding time as some
multiple ai,k ∈ {0, 1, 2, 3} of the parameter Thold . The goal of
policy optimization is for each bus to choose actions in such
a manner that all headways hi,k are as close as possible to
the planned headway H. Hence, whenever a bus i arrives at
a stop k, a reward of −νk |hi,k − H|2 will be accrued by all
agents.
The parameters for the bus corridor environment used in
our experiments are summarized in Table I. All policies are
trained on maximum episode lengths of three simulated hours,
which corresponds to four to five cycles of all buses through
the corridor. The policy trained using PS-TRPO with MGAE is represented by a Multi-Layer Perceptron (MLP). The
parameters to represent the policy and train it using PS-TRPO
with M-GAE are summarized in Table II.
As benchmarks for comparison, we compare the trained
MLP policy to the performance of not holding at all, which we
refer to as No Holding, and a policy that we call Optimized
Thresholds. In this policy, a set of three ordered thresholds
T1 > T2 > T3 are given, and the action chosen is:

λ = 1.0
λ = 2.0
λ = 4.0
Optimized Thresholds
No Holding

−2
−3
−4

(11)

The values T1:3 are optimized using the SciPy implementation of differential evolution [12] [13]. The optimization target

0

100

200
300
400
Training Epoch

500

Fig. 2. Training curves for MLP policy on the Real-Time Bus Holding
Environment, for various values of the parameter λ.

6

·106

TABLE III
E NVIRONMENT PARAMETERS USED IN THE WILDFIRE FIGHTING PROBLEM

0

EXPERIMENTS

Average Return

−1
−2
540 Episodes/Epoch
230 Episodes/Epoch
120 Episodes/Epoch
Optimized Thresholds
No Holding

−3
−4

0

100

200
300
400
Training Epoch

500

Fig. 3. Training curves for MLP policy on the Real-Time Bus Holding
Environment, trained with various batch sizes.

Thresholds policy is itself a substantial improvement over
No Holding. In Figure 2, we see that λ slightly influences
the total return, but the tested values produce policies that
are relatively similar in performance when compared to the
Optimized Thresholds. In Figure 3, we do, however, observe
that decreasing the batch size degrades convergence. This
degradation is due to the fact that the estimated gradients are
noisier with smaller batches.
Figures 4 and 5 show that the No Holding policy results
in the fleet of buses moving together as a single bunch, as
expected. The entire load is borne by the leading bus, which
saturates to being full, and the buses behind it remain almost
empty. On the other hand, the Optimized Thresholds policy
has similar steady-state performance as the optimized MLP
policy, but takes approximately 200 minutes from the start
of the episode to achieve uniformity in bus arrivals at stops,
while the optimized MLP policy requires only around 100
minutes. Neither of these two policies saturate the load of any
bus in steady-state operation, but the optimized MLP policy
maintains lower variance in the distribution of loads over buses
when they reach any given stop. Though the variance in the
distribution of loads over buses is not explicitly optimized for,
the variance occurs as a consequence of non-uniformity in
arrival times. Hence, smaller variance in this distribution of
loads suggests that the optimized MLP policy is mitigating
the adverse effects of bus-bunching more effectively than
Optimized Thresholds can. This experiment provides evidence
that the PS-TRPO algorithm using M-GAE is well suited to
optimize policies with continuous observation spaces in eventdriven, multi-agent environments.
B. Wildfire Fighting Problem
The goal of this experiment is to demonstrate the utility
of using event-driven simulations, which step from eventto-event, over fixed time-step simulations. We introduce a
wildfire fighting environment. We will learn policies on both
an event-driven simulation of this environment, which makes

Parameter

Value (±σ)

N
K
vuav
Thold
Thealth
Tmax
rext
rpen

3
9
0.015
3.0 (±0.3)
3.0
265
1.0
20.0

Unit
Aircraft
Fires
m/s
s
s
s
points
points

no assumption regarding time-step, as well as fixed timestep simulations of the environment, where events that occur
within the same time-step are considered to have occurred
simultaneously. We will then test all learned polices on the
event-driven simulation to examine whether approximation
errors introduced by temporal discretization can degrade the
performance of the policy in the event-driven environment. As
the time-step goes to zero, the simulation should be effectively
identical to the event-driven simulation. Thus, it is expected
that a sufficiently small time-step should lead to minimal to
no degradation in the performance of the policy, when tested
on the event-driven simulator.
1) Problem Specification: There are N unmanned aircraft
that are tasked with extinguishing K fires. At a decisioninstant, an aircraft can choose any of the five closest fires
to move straight toward at velocity vuav , or to hold its current
location for a time Thold . If an aircraft is currently at a fire,
and it chooses to hold, it will attempt to extinguish the fire.
Each fire is given a health Thealth , which is the amount of
time aircraft must collectively attempt to extinguish the fire
before it is extinguished. When any fire is extinguished, all
agents receive a reward of rext . If an aircraft is moving toward
a fire or currently attacking it, it is considered interested in
the fire. However, if an aircraft attempts to extinguish a fire
that another aircraft is currently attempting to extinguish, all
agents receive a penalty of rpen at the instant it makes that
decision.
At any decision instant k, aircraft i receives an observation
oi,k consisting of its own x and y location, its distance to the
five closest fires, the interest in each of those fires, whether
each of those fires has already been extinguished, and the remaining health of each of the fires. A simulation episode lasts
a maximum simulated duration of Tmax . The parameters used
by our simulation environment are summarized in Table III.
The nine fires form three clusters of three, with the cluster
centroids evenly spaced 0.99 m from the origin, and with the
fires evenly spaced 0.01 m from their centroids. The initial
locations of the aircraft are randomized uniformly within the
bounds of [−1, 1] m at the start of each episode. Once again,
an MLP is used to represent the decentralized policy. The
parameters used to train policies using PS-TRPO with M-GAE
are summarized in Table IV.
2) Results: To ensure that intelligent policies can be learned
in this problem domain, we first trained a policy on the
event-driven simulation for an excessive 3000 epochs. The

7

Optimized MLP Policy

Optimized Thresholds

8

8

6

6

6

4
2

Stop

8

Stop

Stop

No Holding

4

4

2

0

2

0
0

100
200
300
Arrival Time [mins]

0
0

100
200
300
Arrival Time [mins]

(a)

0

100
200
300
Arrival Time [mins]

(b)

(c)

Fig. 4. Arrival times of the six buses at the ten stops, under (a) a policy that uses no holding, (b) a policy learned via PS-TRPO using M-GAE, and (c) a
policy that optimizes three headway thresholds for selecting between the actions.
Optimized Thresholds

Optimized MLP Policy

No Holding

80

80

40

20

60

Load at Arrival [pax]

60

Load at Arrival [pax]

Load at Arrival [pax]

60

40

20

40

20

0

0
0

2

4
Stop

6

8

0

2

(a)

4
Stop

6

8

0

2

4
Stop

6

8

(c)

(b)

Fig. 5. Load at arrival of the six buses as they arrive at the 10 stops, under (a) a policy that uses no holding, (b) a policy learned via PS-TRPO using M-GAE,
and (c) a policy that optimizes three headway thresholds for selecting between the actions. Results are displayed for the buses’ fourth cycle through the stops
to show the steady-state behavior.

At live fire?

Average Discounted Return

2.8

yes
yes
Other interest?

p ∼ U(0, 1) < 0.27?
yes

no
p ∼ U(0, 1) < 0.84?

yes
Hold

no
Choice of Fire To Fly To

2.2
2

Thealth = 2.9999

1.8

0

0 1.

5

FS
-1

0 0.

00

FS
-1

FS
-1

0.
5

0−

1.
0

FS
-1

no
0.2

0−

0.4

FS
-1

ED

Probability

2.4

1.6

0.6

no

2.6

Training Simulator

0
1

2

3

4

5

nth Closest Fire

Fig. 6. Approximated behavior of the learned MLP policy in the wildfire
fighting problem.

Fig. 7. Performance when tested on the Event-Driven (ED) simulator of
policies learned on the (ED) simulator and Fixed Step-size (FS) simulations of
various step sizes. Performance drops substantially when the FS-100 simulator
has Thealth = 2.9999 instead of Thealth = 3.0.

8

TABLE IV
PARAMETERS USED FOR MLP POLICY REPRESENTATION AND TRAINING
IN THE WILDFIRE FIGHTING PROBLEM EXPERIMENTS

Parameter

Value

MLP Hidden Size
γ
λ
TRPO Max Step
Batch Size

32
0.02
1.0
0.01
600∼1200

Unit
neurons
s−1
episodes
epoch

learned behavior was then examined to see if actions taken
by the policy match intuition. Since there is a large penalty
for attempting to hold at a fire that another agent is currently
holding at, intuition would suggest that doing so when we
observe another agent’s interest in the fire should be avoided.
Meanwhile, it would be sensible to hold at a fire if it does
not have another agent interested in it. We find that agents
only hold at a fire that has another agent interested in it 27%
of the time, while they hold at a fire that has no other agent
interested in it 84% of the time. If the agent chooses another
fire to target, we find that it chooses the closest and second
closest fires 15% of the time, respectively, while choosing the
third closest fire 68% of the time. Since fires are arranged in
clusters of three, and the separation between clusters is much
larger than the separation between the fires within them, agents
appear to choose the closest cluster of fires 98% of the time.
It is important to note that if an agent is currently at a fire,
then moving to the closest fire is equivalent to staying where
it is and immediately making a new decision. Though it is
peculiar that the third closest fire is being chosen with the
highest probability, there is little cost to moving to another
fire when already at a cluster.
We encode a policy with the behaviors listed in the previous
paragraph as follows. If the agent is at a live fire, it will hold
with 84% probability if there is no other interest. If there is
other interest, it will hold with 27% probability. If it does not
hold, will fly to other fires with the probabilities listed above.
A flowchart representing this policy is shown in Figure 6.
When testing this simpler approximation of the learned policy,
we find that it performs 28% worse than the learned policy
when compared on average discounted return. Thus, although
this simpler policy seems to approximate the learned policy
in important ways, there appear to be subtleties in the learned
policy that improve performance.
With confidence that policies training in this problem domain learn intelligent behaviors, we compare the effects of
varying the fixed time-step of simulation on the policy learned.
All policies were trained for 300 epochs, after which all training curves had reached asymptotes as policies settled to local
optima. For each simulation environment, five separate policies
were trained from scratch, to account for variation in the
local optima on which they may settle. Each of these policies
were then tested on the event-driven simulation environment,
and the average discounted returns for each of policies were
averaged to estimate the performance of a policy learned on
that simulation environment and tested on the event-driven
environment.

Figure 7 shows performance statistics for fixed time-step
simulation environments with time-steps ∆T ranging from
0.1s to 10.0s. We see that when the time-step is less than one
second, the learned policies perform as well as those learned
on the event-driven simulation. However, if the time-step
is greater than one second, the performance is substantially
degraded. Since the nominal value for Thold is 3.0 ± 0.03s,
and the value for Thealth is 3.0s, half of agents’ attempts to
extinguish fires would require them to make an additional
attempt at doing so, since the fire would not have been
extinguished in the single attempt. However, if the simulation
time-step is greater than one second, the time held at a fire by
any agent is rounded to a value greater than 3.0s, resulting in a
policy learned expecting that any agents’ attempt to extinguish
a fire will result in it being extinguished. This expectation
causes the performance of policies learned on simulations with
these time-steps to degrade when tested on the event-driven
simulator.
To confirm that this is the cause of policy degradation,
we modify the value of Thealth to be 2.9999. Previously, the
approximation made by a time-step of 1s computed the fire
to still be alive when it was supposed to be. However, with
the modified value of Thealth , this is no longer the case. That
is, with this change, aircraft attempting to extinguish fires in
the ∆T = 1s simulator will always see fires extinguished in
a single attempt. As expected, this causes the performance
of the policy to degrade when tested on the event-driven
environment.
This experiment provides an example of how the assumed
time-step can force a policy to be learned that transfers poorly
to an event-driven simulation, or the real-world, where temporal approximations are not made. While this experiment was
tailored to demonstrate the problem, we can generally expect
the choice of time-step to cause poor policy transfer if it is
large enough to obfuscate the sequence in which events occur.
In the Wildfire Fighting Problem, the performance degradation
occurs because the order between the event of a hold-action
ending and the fire being extinguished are obfuscated. If
restricted to using fixed time-step simulation, we would thus
hope to maintain a time-step that is much smaller than the
typically duration that separates important events.
C. Scaling the Time-Step to avoid Race-Conditions
Above, we defined a race condition to be a time-step in
which more than one event occurs. For an N -agent problem,
we can assume that the time at which events pertaining to
the N agents occur are drawn from some distribution p(t) for
t ≥ 0. Hence, for N samples from p(t), a race condition occurs
if any two samples fall into the same interval of size ∆T . We
can always shrink ∆T arbitrarily so that the probability of a
race condition is less than some threshold δ. However, since
this comes at the cost of computation time, it is of interest
to examine how ∆T must shrink as we increase N . We do
so by selecting some example distribution, sampling 10,000
sets of N samples from the distribution, and for each set of
N samples, we check for a race condition by seeing if more
than two of the N samples fall in the same interval of some

9

TABLE V
R ELATIONSHIP BETWEEN ∆T

AND N , FOR MAINTAINING CONSTANT δ,
AS THE TIMING OF EVENTS ARE DRAWN FROM VARIOUS DISTRIBUTIONS

Distribution

Parameters

β (Std. Error)

Exponential
Chi-Squared
Gamma

λ=1
k=5
k = 5, θ = 1

2.216 (0.055)
2.213 (0.045)
2.219 (0.037)

chosen ∆T . We then vary ∆T until the probability of a race
condition is less than some threshold value of δ = 0.1. To
determine a relationship for each distribution tested, we vary
N from 2 to 20, solve for the corresponding ∆T , and fit the
functional form:
∆T = αN β
(12)
Table V shows that for various example distributions, ∆T
varies inversely with approximately N 2.2 . For a fixed duration
simulation, computation time scales inversely with the timestep. Hence, we find that computation time in fixed time-step
simulations of event-driven process scales approximately as
N 2.2 with the number of agents N , assuming we maintain a
fixed low-probability of race conditions. Though the underlying distribution p(t) of an arbitrary environment is unlikely
to exactly be any of the example distributions chosen, this
experiment suggests that an arbitrary distribution will also
have β ≈ 2.2, or at the very least, β > 1. Event-driven
simulators, on the other hand, will process a number of events
which are in many cases linearly related to the number of
agents, providing a substantial computational advantage when
simulating large-scale multi-agent problems.
VI. C ONCLUSION
This paper presented an algorithm for learning neural network policies for control in cooperative multi-agent environments with asynchronous and temporally extended actions.
The novelty of this contribution is that it extends an algorithm
called PS-TRPO that does not require discretization of the
observation space. This contrasts with existing algorithms
tackling the same class of problem. Section V-A showed that
our algorithm is able to learn an optimal policy for realtime bus holding, and is able to achieve better qualitative and
quantitative performance than a sensible baseline policy.
The approach to extending PS-TRPO involves framing the
decentralized multi-agent decision problem as event-driven,
allowing us to in many circumstances model our environment using event-driven simulation. Using such a simulator
does not require assuming a fixed time-step, allowing us to
eliminate race conditions. Section V-B showed that these
artifacts from temporal discretization obfuscated the event
sequences and can result in learning policies that are sensitive
to the time-step. Further, Section V-C showed that arbitrarily
shrinking the time-step to avoid these artifacts scales poorly
with the number of agents, motivating the use of event-driven
simulation. The source code for this work can be found at
https://github.com/sisl/event-driven-rllab. The algorithm presented in this paper is built as a modification to the TRPO
framework in rllab [14].

The work presented here borrows inspiration from hierarchical reinforcement learning, which attempts to simplify learning
problems by stratifying decisions in levels of abstraction. However, the problem of simultaneously optimizing high and lowlevel policies is an open area of research. Our framework has
assumed that we are only attempting to optimize a high-level
policy, but the logical next step is to relax this assumption.
ACKNOWLEDGMENT
This work is based on work supported by NASA Grant No.
NNXI4AIlIG and ARO Grant No. W911NF-15-1-0127. The
authors acknowledge the support of Guillaume P. Brat from
the NASA Ames Research Center, as well as the patient help
from Jayesh K. Gupta. The authors would also like to thank
the anonymous reviewers for their helpful comments.
R EFERENCES
[1] R. S. Sutton, D. Precup, and S. Singh, “Between MDPs and SemiMDPs: A framework for temporal abstraction in reinforcement learning,”
Artificial Intelligence, vol. 112, no. 1-2, pp. 181–211, 1999.
[2] M. Ghavamzadeh, S. Mahadevan, and R. Makar, “Hierarchical multiagent reinforcement learning,” International Conference on Autonomous
Agents and Multiagent Systems (AAMAS), vol. 13, no. 2, pp. 197–229,
2006.
[3] M. Liu, C. Amato, E. P. Anesta, J. D. Griffith, and J. P. How, “Learning
for decentralized control of multiagent systems in large, partiallyobservable stochastic environments.” in AAAI Conference on Artificial
Intelligence (AAAI), 2016, pp. 2523–2529.
[4] J. Shen, G. Gu, and H. Liu, “Multi-agent hierarchical reinforcement
learning by integrating options into MAXQ,” in International MultiSymposiums on Computer and Computational Sciences (IMSCCS),
vol. 1. IEEE, 2006, pp. 676–682.
[5] D. M. Clement and M. Huber, “Temporal and agent abstractions in
multiagent reinforcement learning,” in IEEE International Conference
on Systems, Man, and Cybernetics (SMC), 2016, pp. 002 190–002 195.
[6] J. K. Gupta, M. Egorov, and M. J. Kochenderfer, “Cooperative multiagent control using deep reinforcement learning,” in Adaptive Learning
Agents Workshop (ALA), 2017.
[7] J. Schulman, P. Moritz, S. Levine, M. Jordan, and P. Abbeel, “Highdimensional continuous control using generalized advantage estimation,”
International Conference on Learning Representations (ICLR), 2016.
[8] J. Schulman, S. Levine, P. Abbeel, M. Jordan, and P. Moritz, “Trust
region policy optimization,” in International Conference on Machine
Learning (ICML), 2015, pp. 1889–1897.
[9] C. Amato, G. D. Konidaris, and L. P. Kaelbling, “Planning with macroactions in decentralized POMDPs,” in International Conference on
Autonomous Agents and Multiagent Systems (AAMAS), 2014, pp. 1273–
1280.
[10] K. Müller and T. Vignaux, “SimPy: Simulating Systems in Python,”
2002–. [Online]. Available: https://pypi.python.org/pypi/simpy
[11] W. Chen, K. Zhou, and C. Chen, “Real-time bus holding control on a
transit corridor based on multi-agent reinforcement learning,” in IEEE
International Conference on Intelligent Transportation Systems (ITSC),
2016, pp. 100–106.
[12] R. Storn and K. Price, “Differential evolution–a simple and efficient
heuristic for global optimization over continuous spaces,” Journal of
Global Optimization, vol. 11, no. 4, pp. 341–359, 1997.
[13] E. Jones, T. Oliphant, P. Peterson et al., “SciPy: Open source scientific
tools for Python,” 2001–. [Online]. Available: http://www.scipy.org/
[14] Y. Duan, X. Chen, R. Houthooft, J. Schulman, and P. Abbeel, “Benchmarking deep reinforcement learning for continuous control,” in International Conference on Machine Learning (ICML), 2016.

