arXiv:1803.09928v1 [cs.LG] 27 Mar 2018

Entropy Controlled Non-Stationarity for Improving Performance of
Independent Learners in Anonymous MARL Settings

Tanvi Verma, Pradeep Varakantham and Hoong Chuin Lau
School of Information Systems, Singapore Management University, Singapore
tanviverma.2015@phdis.smu.edu.sg, pradeepv@smu.edu.sg,hclau@smu.edu.sg

Abstract
With the advent of sequential matching (of supply and demand) systems (uber, Lyft, Grab for
taxis; ubereats, deliveroo, etc for food; amazon prime, lazada etc. for groceries) across
many online and offline services, individuals
(taxi drivers, delivery boys, delivery van drivers,
etc.) earn more by being at the ”right” place
at the ”right” time. We focus on learning techniques for providing guidance (on right locations to be at right times) to individuals in the
presence of other ”learning” individuals. Interactions between indivduals are anonymous,
i.e, the outcome of an interaction (competing
for demand) is independent of the identity of
the agents and therefore we refer to these as
Anonymous MARL settings.
Existing research of relevance is on independent learning using Reinforcement Learning
(RL) or on Multi-Agent Reinforcement Learning (MARL). The number of individuals in aggregation systems is extremely large and individuals have their own selfish interest (of
maximising revenue). Therefore, traditional
MARL approaches are either not scalable or
assumptions of common objective or action coordination are not viable. In this paper, we
focus on improving performance of independent reinforcement learners, specifically the
popular Deep Q-Networks (DQN) and Advantage Actor Critic (A2C) approaches by exploiting anonymity. Specifically, we control nonstationarity introduced by other agents using entropy of agent density distribution. We demonstrate a significant improvement in revenue for
individuals and for all agents together with our
learners on a generic experimental set up for aggregation systems and a real world taxi dataset.

1

Introduction

Systems that aggregate supply to ensure a better matching of demand and supply have significantly improved
performance metrics in taxi services, food delivery and
grocery delivery. From the individual perspective (taxi
drivers, delivery boys, delivery van drivers), learning to
be at the ”right” place at the ”right” time is essential to
maximize their revenue. From an individual perspective,
this learning problem is challenging because of the uncertainty about demand (which will determine the revenue
earned) and the locations of other ”learning” individuals
(which will determine whether the demand is assigned to
the current individual).
Given the presence of multiple learning agents, a key
focus area of relevance is Multi-Agent Reinforcement
Learning (MARL) [Littman, 1994; Claus and Boutilier,
1998; Busoniu et al., 2008], where multiple agents are
learning to maximize their individual rewards. There are
two main issues with such an approach in case of multiagent sequential matching problems: (a) The definition
of fairness when learning for multiple agents is unclear
as the agent actions are not synchronised, agents can
have different starting beliefs and demand is dynamic or
non-stationary. (b) The scale of matching problems is
typically very large (with thousands of agents) and hence
computing policies for all agents is computationally very
challenging.
A thread of MARL has also focussed on teams of agents
that maximize the global reward [Perolat et al., 2017;
Nguyen et al., 2017] or agents cooperate to achieve a common goal [Hausknecht and Stone, 2015; Foerster et al.,
2016]. The learning approaches there are also limited in
scalability with respect to number of agents. Furthermore,
the problems of interest in this paper are focussed on individual agents that are maximizing their own revenue
rather than a team revenue. Therefore, existing MARL
approaches are not suitable for the problem and hence we
focus on improving performance of independent learners

(ILs) in this paper.
Our work is motivated by the recent success of use entropy
regularizers in improving performances of reinforcement
learning algorithms [Mnih et al., 2016; Haarnoja et al.,
2017b; Schulman et al., 2017]. We use entropy of agent
population distribution as the regularizer. The intuition
is, as the agents are competing for resources, the policy which encourages even agent population distribution
is more advantageous for individual as well collective
agents.
Existing work [Verma et al., 2017] in multi-agent sequential matching problems has employed Reinforcement
Learning (RL) for each individual to learn a decision making policy. However, this line of work has assumed that
other agents employ stationary and fixed strategies, rather
than adaptive strategies. Due to the non-stationarity introduced when multiple agents learn independently, the performance of traditional table based Q-learning approaches
is extremely poor.
The use of deep neural networks (instead of table based
representations) has become hugely popular in the reinforcement learning community [Mnih et al., 2015; Silver et al., 2016, 2017]. Policy gradient methods and
Q-learning methods have been successfully used in deep
neural networks.
We make the following key contributions:
• Extending on past work in multi-agent planning under uncertainty [Varakantham et al., 2012, 2014], we
describe the notion of interaction anonymity in the context of multi-agent reinforcement learning.
• We then provide mechanisms to exploit interaction
anonymity by extending the well known DQN (Deep QNetwork) and A2C (Advantage Actor-Critic) methods.
Specifically, we control the non-stationarity introduced
by other agents by finding policies that also maximize
or minimize the entropy on agent count distribution.
• To demonstrate the utility of our approaches, we performed extensive experiments on a synthetic data set
(that is representative of multiple multi-agent sequential matching problems) and a real taxi data set. We
observe that our individuals learners based on DQN
and A2C are able to learn policies that are reasonably
fair (minor differences in value) and most importantly,
the individual and joint (social welfare) values of the
learning agents are significantly higher than existing
benchmarks.

2

Motivating Problems

This paper is motivated by the following matching problems, where there are multiple agents and matching of

agents to customer demand has to be done on a continuous basis. We refer to these problems as Multi-Agent
Sequential Matching Problems (MSMPs) and our focus
is on enabling individual agents to learn effectively and
efficiently.
Taxi Aggregation: Companies like Uber, Lyft, Didi,
Grab etc. all provide taxi supply aggregation systems.
The goal is to ensure wait times for customers is minimal
or amount of revenue earned is maximized by matching
taxi drivers to customers on a regular basis. However,
these goals of the aggregation companies may not be correlated to the individual driver objective of maximizing
their own revenue. The methods provided in this paper
can be used to guide individual drivers based on their
past experiences of customer demand and taxi supply (obtained directly/indirectly from the aggregation company),
while also considering that other drivers are learning to
improve their revenue.
Food or Grocery Delivery: Aggregation systems have
also become very popular for food delivery (Deliveroo,
Ubereats, Foodpanda, DoorDarsh etc.) and grocery delivery (AmazonFresh, Deliv, RedMart etc.) services. They
offer access to multiple restaurants/grocery stores to the
customers and use services of delivery boys/delivery vans
to deliver the food/grocery. Similar to taxi aggregation
systems, our work can be used to guide delivery boy/van
to improve their individual revenue based on current location and presence of other delivery boys/vans near that
location (obtained directly/indirectly from the aggregation
company).
Supply Aggregation in Logistics: More and more online buyers now prefer same day delivery services and
tradition logistic companies which maximize usage of
trucks, drivers and other resources are not suitable for it.
Companies like Amazon Flex, Postmates, Hitch etc. connect shippers with travellers/courier personnels to serve
same day/on-demand delivery requests. The courier personnels in this system can employ the proposed method
to learn to be at ”right” place at ”right” time by learning
from past experiences.
Sensor Networks: Another motivating problem is target
tracking by a team of sensors [Nair et al., 2005]. Each
sensor node can scan in one of the four directions. To
track a target accurately and receive the associated reward, a small number of sensors must scan the target
simultaneously. Every sensor can interact with only a
limited number of neighbour sensors. In this example
having more number of sensors scanning same location
is required for high reward as opposed to the previous
examples where more number of agents decrease individual rewards. Hence, by modifying our proposed methods
slightly, it can be used by individual sensors to learn to

align in a direction based on past rewards and alignments
of neighbouring sensor nodes.

3

Background: Reinforcement Learning
(RL)

In this section, we briefly describe the Reinforcement
Learning (RL) problem and leading approaches (of relevance to this paper) for solving large scale RL problems.
The RL problem for an agent is to maximize the long run
reward while operating in an environment represented as
a Markov Decision Process (MDP). Formally, an MDP is
represented by the tuple S, A, T , R , where S is the set
of states encountered by the agent, A is the set of actions,
T (s, a, s0 ) represents the probability of transitioning from
state s to state s0 on taking action a and R(s, a) represents the reward obtained on taking action a in state s.
The RL problem is to learn a policy that maximizes the
long term reward while only obtaining experiences (and
not knowing the full reward, R and transition, T models) of transitions and reinforcements. An experience is
defined as (s, a, s0 , r) and typically there is an episode
of experiences that ends when s0 is a terminal state. In
this paper, we are interested in episodic problems (ex: an
episode ends once the taxi driver gets a customer).
We now describe three approaches that are of relevance
to work described in this paper.
3.1

Q-Learning

One of the most popular approaches for RL is Qlearning Watkins and Dayan [1992], where the Q function
is represented as a table (and initialised to arbitrary fixed
values) with an entry in the table for each state and action combination. Q-values are updated based on each
experience given by (s, a, s0 , r):
0

0

Q(s, a) = R(s, a) + γ ∗ max
Q(s , a ) − Q(s, a) (1)
0
a

3.2

Deep Q-Networks (DQN)

Instead of a tabular representation for Q function employed by Q-Learning, the DQN approach Mnih et al.
[2015] employs a deep network to represent the Q function. Unlike with the tabular representation that is exhaustive (stores Q-value for every state, action pair), a deep
network predicts Q-values based on similarities in state
and action features. This deep network for Q-values is
parameterised by a set of parameters, θ and the goal is to
learn values for θ so that a good Q-function is learnt.
We learn θ using an iterative approach that employs gradient descent on the loss function. Specifically, the loss
function at each iteration is defined as follows:
L(θ) = E(e∼U (J )) [(y DQN − Q(s, a; θ− ))2 ]
where y DQN = r + γmaxa0 Q(s0 , a0 ; θ− ) is the target
value computed by a target network parameterised by
previous set of parameters, θ− . Parameters θ− are frozen
for some time while updating the current parameters θ. To
ensure independence across experiences (a key property
required by Deep Learning methods to ensure effective
learning), this approach maintains a replay memory J
and then samples experiences from that replay memory.
Like with traditional Q-Learning, DQN also typically
employs an -greedy policy.
3.3

Advantage Actor Critic (A2C)

DQN learns the Q-function and then computes policy
from the learnt Q-function. A2C is a policy gradient
method that directly learns the policy while ensuring that
the expected value is maximized. To achieve this, A2C
employs two deep networks, a policy network to learn
policy, π(a|s; θp ) parameterized by θp and a value network to learn value function (and not Q function) of the
computed policy, V π (s; θv ) parameterized by θv .
The policy network parameters are updated based on the
policy loss, which in turn is based on the advantage associated with the value function. Formally, the policy loss
is given by:

To ensure a good explore-exploit tradeoff, an -greedy
policy is typically employed.

π(s) =


arg maxa∈A Q(s, a), with probability 1 − 



a

a1 , with probability  ∗ P e 1 ak
e

a2 , with probability  ∗




...

ai ∈A
ea 2

P

ai ∈A

ea k

Q-learning is guaranteed to converge to the optimal solution for stationary domains Watkins and Dayan [1992].

L(θp ) = ∇θp logπ(a|s; θp )A(s, a; θv )
where
A(s, a; θv ) =

i=k−1
X

γ i rt+i + γ k V (sk ; θv ) − V (s; θv )

i=0

(2)
The first term in equation 2 is the k-step (or till the end
of the episode) discounted reward following the current
policy and using a discount factor γ.

are dependent on other agents but only on counts. We
focus on developing independent learners for Anonymous
MARL settings.
Dynamic Bayes Network (DBN) in Figure 1 provides a graphical representation for MSMPs of interest. As can be observed from the DBN, agents
are independent of each other given the agent
counts vector, D = hD1 , D2 , . . . Dt , . . .i, where Dt =
(dt (s1), dt (s2), . . .).
In this paper, our focus is on learning the policy from past
experiences when the reward and transition functions are
not known. Transition and reward functions are unknown
or uncertain because of two reasons: (i) Matching of
an agent to customer demand is done by aggregation
companies like Uber and hence individual agents may not
be aware of what demand is assigned to them; and (ii)
Due to uncertainty in future demand, individual agents
are not aware of the consequences of moving to a specific
state.
Experience for each agent is given by
hs, d(s), a, r, s0 , d(s0 )i,
Figure 1: A DBN depicting relationship between policy
of agents and agent population density distribution Dt .
Where rti is the immediate reward received agent i by
taking action ait in state Sti at time t.

4

Exploiting Anonymity for Independent
Learning

In the Multi-agent Sequential Matching Problems
(MSMPs) described in Section 2, we have individual
agents learning to improve their expected reward in presence of other learning agents. The model for an individual agent, i is the same as in RL, i.e., S, A, T , R .
However, the key difference is that reward and transition functions are dependent on other agents and more
specifically on counts of agents. The reward function,
R(s, a, d(s)) refers to the reward for taking action a in
state s when there are d(s) other agents in state s 1 . The
transition function, T (s, a, s0 , d(s)) refers to the transition to s’ on taking action a from state s, when there are
d(s) other agents in state s. In the literature Varakantham et al. [2012, 2014], this dependence of reward and
transition functions on agent counts is referred to as interaction anonymity. We refer to these as Anonymous
MARL problems, as the reward and transition functions
1
This can be easily extended to consider count of number
of agents in same or relevant state, action pairs as described in
Kumaret al. Kumar and Varakantham [2017]

where d(s) and d(s’) represent the count of other agents2
in states s and s0 respectively.
The RL agent learning in MSMPs is faced with nonstationarity due to changing policies of other learning
agents (that are dependent on policy of the RL agent).
However, the useful structure in MSMPs is that each
agent is affected in the same way (through rewards and
transitions that are dependent on agent counts) by every
other agent due to interaction anonymity. We exploit the
interaction anonymity for independent learning using four
key steps.
First, to ensure better learning, we normalize each agent
counts vector into a probability distribution. That is to
say, d(s) will
Pnow refer to the the fraction of agents in
state s. and s d(s) = 1.
Second, we make policy, Q-function and V-function dependent on distribution of agent count. This is to ensure
that the learnt policy or value function captures any dependency3 on observed agent counts in states. That is to
say:
π : S × A × [0, 1] → [0, 1],
where π(a|s, d(s)) is the probability of taking action a in
2
These counts can typically be obtained directly (provided
by the aggregation company) or indirectly (through customer
application).
3
If there is no dependency on observed counts, then this
method should return same policies as without observed counts
in state space

state s when there is d(s) fraction of agents in state s.
Q : S × A × [0, 1] → R
where Q(s, a, d(s)) is the Q-value for taking action a in
state s when there are d(s) fraction of agents in state s.
V : S × [0, 1] → R,
where V (s, d(s)) is the value for state s.
Third, we modify deep network architectures employed
by Deep RL approaches such as DQN and A2C to exploit
anonymity captured through agent counts vector. Figure
3 shows how architecture of DQN can be modified into
Density Entropy (explained later in the section) based
DQN (DE-DQN). Similarly, figure 3 depicts transformation of standard A2C network into Density Entropy based
A2C (DE-A2C). Similar to DQN, DE-DQN estimates
action-value function. Unlike DQN, DE-DQN predicts
agent density distribution, D(s0 |s, d(s); θ) based on past
experience.
Similarly, apart from maintaining policy and value estimates, DE-A2C (figure 3) also maintains an estimate of
agent population density distribution. We use a softmax
layer to predict D. In the deep network π, V, Q and D are
parameterised by the network parameter θ as shown in
the figures 2 and 3.

policy output and a shared network for state-action/value
output and density prediction output.
Finally and most importantly, apart from maximizing the
value of the independent learner, we also maximize (or
minimize) entropy of the agent density distribution, D.
Entropy for the agent count distribution, D is given by:
X
HD = −
D(s0 |s, d(s); θ)log(D(s0 |s, d(s); θ)
s0 ∈S

As described in literature Haarnoja et al. [2017a], individual policy entropy is maximized so as to deal with
non-stationarity introduced by environments (which ensures we have different policies that work for different
scenarios of non-stationarity). However, in anonymous
MARL settings of interest in this paper, non-stationarity
for a learning agent is also introduced by other learning
agents. Therefore, depending on domain characteristics4 ,
we maximize/minimize density entropy to control the nonstationarity introduced by other agents. In other words,
we find a policy that will ensure other agents choose policies that will force density distribution to have high/low
entropy depending on the domains.
We now provide specific changes required to the target
value and the loss function to maximize density entropy
in DQN and A2C.
4.1

Figure 2: DQN and DE-DQN networks

DE-DQN

As we wish to maximize the density entropy, we augment
the reward with the density entropy. β is the hyperparameter which controls the effect of density entropy term. The
target value y for a given experience can be computed as
follows
(
r + βHD if s0 is terminal
y=
r + βHD + γmaxa0 Q(s0 , a0 , d(s0 ); θ− ) otherwise
θ− is the network parameter for the target network.
DE-DQN optimizes a single combined loss Lθ with respect to the joint parameter θ. Lθ combines Q-loss LQ
and D-loss LD :
Lθ = LQ + λLD

(3)

λ is the weightage term used for the density prediction
loss. Q-loss is computed using standard mean squared
Figure 3: A2C and DE-A2C networks
All the output layers can either have separate non-output
layers each or they can share the non-output layers. Without loss of generality, we assume separate network for

4

For taxi aggregation, food/grocery delivery and supply aggregation in logistics, revenue is reduced if agents are present
in one state and hence entropy needs to be maximized for those
settings. For sensor network (and other coverage) problems,
revenue is increased if more agents are present in one state and
hence entropy needs to be minimized in those cases.

error loss as given in equation 4. Equation 5 shows how
LD is computed using local observation .
LQ = E(e∼U (J )) [(y − Q(s, a, d(s); θ))2 ]
0

0

LD = −E(e∼U (J )) [d(s )logD(s |s, d(s); θ)]

(4)
(5)

As the agent does not have full observation of the density
distribution LD , we computes partial loss for the current
experience.
Algorithm 1 DE-DQN
1: Initialize replay memory J
2: Initialize counter T = 0
3: Initialize action-value function Q(s, d(s), a; θ) and population density distribution function D(.|s, d(s); θ) with
random weight θ
4: Initialize target network parameters θ− = θ
5: repeat
6:
T ←T +1
7:
Take action at using -greedy policy according to
Q(st , d(st ), a; θ) and observe rt , st+1 and d(st+1 )
8:
Store transition < st , d(st ), at , rt , st+1 , d(st+1 ) > to
the replay memory.
9:
if T mod Iupdate == 0 then
10:
dθ ← 0
Sample
batch
of
transitions
<
11:
s, d(s), a, r, s0 , d(s0 ) >from the replay memory
12:
Accumulate gradients wrt θ : dθ ← dθ + ∇θ Lθ
13:
Update θ based on dθ
14:
if T mod Itarget == 0 then
15:
Update target network parameter, θ− ← θ
16:
if T mod Ireplay == 0 then
17:
Reset replay memory
18: until T > Tmax

Algorithm 1 shows detailed steps of DE-DQN. Network
parameters are updated after every Iupdate steps. Itarget
is the number of fixed steps after which target network
parameter is updated and J is reset after every Ireplay
steps.

4.2

equation 8.

DE-A2C

Similar to A2C algorithm, DE-A2C maintains a policy
output π(a|s, d(s); θp ) and an output for the value function estimate V (s, d(s); θv ). It also maintains a density
prediction output D(s0 |s, d(s); θv ). We want to update
the policy such that the density entropy is maximized,
hence we add the entropy to the advantage term. A small
replay memory is also used which contains episodes generated from π(a|s, d(s); θp ) and replay memory is reset
after every update of θp . The value network loss Lθv
is combination of V-loss LV and D-loss LD as given in

LV = E(e∼U (J ) [(R − V (s, d(s); θv ))2 ]

(6)

LD = −E(e∼U (J ) [d(s0 )log(D(s0 |s, d(s); θv )])

(7)

Lθv = LV + λLD

(8)
(9)

Algorithm 2 shows the steps for DE-A2C.
Algorithm 2 DE-A2C
1: Initialize replay memory
2: Initialize counter T = 0
3: Initialize value function V (s, d(s); θv ) with random weight
θv
4: Initialize policy function π(a|s, d(s); θp ) with random
weight θp
5: repeat
6:
tstart ← T
7:
repeat
Take action at according to policy π(st , d(st ); θp )
8:
and observe rt , st+1 and d(st+1 )
9:
T ←T +1
10:
until (
terminal or T − tstart == k
0
if st is terminal
11:
R=
V (st , d(st ); θv ) otherwise
12:
for i ∈ T − 1, ..., tstart do
13:
R ← ri + γR
14:
add < si , di , ai , R, si+1 , d(si+1 ) > to J
15:
if T mod Iupdate == 0 then
16:
sample batch of experience from J
17:
Accumulate gradients wrt θp : dθp ← dθ +
∇θp logπ(a|s, d(s); θp )(R + βHD − V (s, d(s); θv ))
18:

Accumulate gradients wrt θv : dθv ← dθv +∇θv Lθv

19:
Update θp and θv using dθp and dθv respectively.
20:
Clear replay memory J .
21: until T > Tmax

5

Experiments

To demonstrate the performances of DE-DQN and DEA2C, we simulate a multi-agent taxi domain in grid world.
The grids are associated with a demand arrival rate and
multiple agents roam in the grid world to satisfy these
demands. The revenue of an agent can be affected by
various features of the taxi domain.
• Demand-to-Agent Ratio (DAR): This is the average
number of customers per time step per agent.
• Trip pattern: The average length of trips can be uniform
for all the grids or there can be few grids which always
get longer trips (for ex. airports which are usually
outside the city) whereas few grids get relatively shorter
trips (city center).
• Demand pattern: The demand can be uniformly spread
across all the grids (dispersed demand) or there might

be few grids where high demand is present and few
grids where there is no demand ( concentrated demands)
• Demand arrival rate: The Poisson arrival rate of demand can be either homogeneous (static arrival rate) or
non-homogeneous (dynamic arrival rate)
We perform experiments by varying values of these
features using various dimensions of the grid and
different number of agents. The experiments are done
on two sets of data. The first set is synthetic data and
we control how demand arrival rate, reward and cost is
generated. The second dataset is a one month data from a
real-world taxi fleet from a developed Asian city. From
the real world data set we compute demand between
zones and represent each zone as a grid. Travel time
between zones is also computed from the data set. We
evaluate the performances on two metrics:
(1) Revenue of IL agents present in the domain.
(2) Average revenue of all the ILs present in the domain.
Taxi Simulation Domain: Figure 4 shows an example
grid world with 6 × 6 grids. The numbers displayed in
the grids are the Poisson arrival rate of demand in the
corresponding grid. There are no demand in the grids
with no number in it. Demands are generated with a timeto-live value and the demand expires if it is not served
within time-to-live time periods. Furthermore, to emulate
the real-world taxi fares, the trip fares are generated based
on distance of the trip (distance between the origin and
destination grids) plus a fixed starting fare. At every time
step, it is tried to assign a trip to the agents based on the
agent population density at the grid.

Hyperparameters For DQN algorithms we used Adam
optimizer with a learning rate of 1e-4, whereas for A2C
algorithms we used RMSprop optimizer with learning rate
of 1e-5 for policy network and 1e-4 for value network.
Two hidden layers are used with 128 nodes per layer.
Density entropy regularizer β was set to 1e-2, whereas
weigtage of D-loss λ was set to 1e3. We also used policy
entropy regularizer for A2C algorithms and the regularizer
was set to 1e-3.

6

Experimental results

In this section, we benchmark the performance of our
approaches (DE-DQN and DE-A2C) with respect to tabular Q-learning, DQN/A2C without density distribution
input and finally DQN/A2C with density distribution input. One evaluation period consists of 1000 (1e3) time
steps5 and revenue of all the agents is reset after every
evaluation period. All the graphs plotted in the upcoming
sub-sections provide running average of revenue over 100
evaluation periods (1e5 time steps). Unless specified, the
number of agents employed was 20.
Tabular Q-Learning, Standard DQN and Standard
A2C: Figure 5 shows the comparison between tabular
Q-learning, DQN; with and without agent density input
and A2C;with and without agent density input. We used
medium demand-to-agent ratio with non-uniform trip pattern as explained in section 6. We can see that DQN with

Figure 5: Comparison of tabular Q-learning, standard
DQN and standard A2C .

Figure 4: A taxi grid world with demand arrival rates.
In our experiments we make a realistic assumption that
agents do not take action at every time step and they can
go to any grid from any grid and time taken to travel
between grids is proportional to the shortest distance between the grids. These on-way/on-trip agents are not a
candidate for the trip assignment and they do not contribute to the agent population density distribution computation. Hence D is prediction of agent population density
distribution of active learning agents.

agent density input and A2C with agent density input perform significantly better than the other three algorithms.
Even for other demand we obtained similar results. Therefore, we do not include tabular Q-learning, DQN and
A2C without agent density input in the following results.
Henceforth, DQN refers to DQN with density input and
A2C refers to A2C with density input.
Low DAR (Demand-to-Agent Ratio) uniform trip pattern and dispersed demand: In this case, static demand
5
A time step represents a decision and evaluation point in
the simulator. From a learner perspective, an episode is typically
multiple time steps long.

(a) Models

(b) DQN

(c) DE-DQN

(d) A2C

(e) DE-A2C

Figure 6: Low demand-to-agent ratio.
arrival rate was used. The effective demand-to-agent ratio
was 0.5. Figures 6a(b) and 6 provide the joint and individual normalized rewards obtained by different approaches.
Here are the key observations: (1) DE-DQN and DQN
perform better than A2C and DE-A2C. This can be attributed to the static nature of the domain.
(2) DE-DQN, A2C and DE-A2C all provide a reasonably
fair distribution of revenues for individual revenues, with
DE-DQN providing higher individual revenues.
Medium DAR with concentrated demand:
In this setting, there were few grids with high demand
whereas remaining grids did not have any demand and the
overall demand-to-agent ratio was 0.8. The poisson arrival rate was homogeneous and uniform trip pattern was
used. Here are the key observations: (1) Figure 7a shows
that both DE-A2C performs better than other algorithms,
with DE-DQN providing the second best performance.
(2) DQN, DE-DQN and A2C provide reasonably fair distribution of individual revenues, with DE-A2C providing
slightly uneven distribution of revenues for individual
agents.
Medium DAR with non-uniform trip patterns: In this
setting, we employed a demand-to-agent ratio of 0.8 and
non-uniform trip patterns. Arrival of demand was generated based on homogeneous poisson rates and to generate
a non-uniform trip pattern, we associated each grid cell
with a maximum range for destination grids for trips originating from the grid cell. Here are the key observations:
(1) We observed that as we increase complexity of demand
pattern, the performance of DE-DQN starts improving
with respect to DQN. Graph in figure 8a compares the
performances of all the algorithms.
(2) Figure 8 shows that DE-DQN and A2C provide low
variance across individual revenues.
High DAR with non-uniform trip patterns: We generated high demand-to-agent ratio (1.2) in this setting.
Once again, we observe that in Figues 9a and 9, DE-DQN
provides better joint revenue and less variance across individual agent revenues.
Medium DAR with dynamic demand arrival rate: To

simulate peak and off-peak hours we divided the evaluation period (1e3 time steps) into three parts. The demand for the first and third part is generated based on low
demand-to-agent ratio (0.6) and for the second part it is
generated using high demand-to-agent ratio (1.2).
Figure 10 shows that the performances are similar to what
we have seen for other settings, with DE-DQN providing
higher values while having lower variance across individual agents.
Taxi domain simulated using real-world data set For a
more realistic simulation of the taxi domain, we used realworld data to compute mean demand between two grids.
First, based on the GPS data of taxi-fleet, we divided the
map into 110 zones and represented each zone as a grid
in a 10 × 11 grid world. Since we focus on independent
learners, our learning is very scalable. However, simulating thousands of learning agents at the same time requires
extensive computer resources and with the academic resources available, we could not perform a simulation with
1000 agents. Hence, we computed proportional demand
for 100 agents and simulated for 100 agents. Time steps
taken to travel between two grids is also approximated by
computing average travel time between two zones using
the real-world dataset.
Figures 11a and 11c show that DE-DQN again performs
better than other approaches while having very small
variance across individual revenues. DE-A2C and other
approaches had a significant amount of variance across
individual revenues.
Summary of Results Our two contributions, DE-DQN
and DE-A2C that employ density entropy have significantly improved over the well known DQN and A2C algorithms in all the simulation settings and the real world
taxi data set. In addition, DE-DQN provides revenues
of individual agents which are very similar, thereby representing a fair learning approach from an MARL perspective. In other words, if there is an application that
provides guidance based on DE-DQN then the individual
agents following the advice will all be treated fairly.

(a) Models

(b) DQN

(c) DE-DQN

(d) A2C

(e) DE-A2C

Figure 7: Medium demand-to-agent ratio with concentrated demand pattern.

(a) Models

(b) DQN

(c) DE-DQN

(d) A2C

(e) DE-A2C

Figure 8: Medium demand-to-agent ratio with non-uniform trip pattern.

(a) Models

(b) DQN

(c) DE-DQN

(d) A2C

(e) DE-A2C

(d) A2C

(e) DE-A2C

Figure 9: High demand-to-agent ratio.

(a) Models

(b) DQN

(c) DE-DQN

Figure 10: Dynamic demand arrival rate.

(a) Models

(b) DQN

(c) DE-DQN

(d) A2C

Figure 11: Simulation using real-world data set

(e) DE-A2C

References
Busoniu, L., Babuska, R., and De Schutter, B. (2008).
A comprehensive survey of multiagent reinforcement
learning. IEEE Trans. Systems, Man, and Cybernetics,
Part C, 38(2):156–172.
Claus, C. and Boutilier, C. (1998). The dynamics of reinforcement learning in cooperative multiagent systems.
AAAI/IAAI, 1998:746–752.
Foerster, J., Assael, Y., de Freitas, N., and Whiteson, S.
(2016). Learning to communicate with deep multiagent reinforcement learning. In Advances in Neural
Information Processing Systems, pages 2137–2145.
Haarnoja, T., Tang, H., Abbeel, P., and Levine, S. (2017a).
Reinforcement learning with deep energy-based policies. arXiv preprint arXiv:1702.08165.
Haarnoja, T., Zhou, A., Abbeel, P., and Levine, S. (2017b).
Soft actor-critic: Off-policy maximum entropy deep
reinforcement learning with a stochastic actor.
Hausknecht, M. and Stone, P. (2015). Deep reinforcement
learning in parameterized action space. arXiv preprint
arXiv:1511.04143.
Kumar, R. R. and Varakantham, P. (2017). Exploiting anonymity and homogeneity in factored dec-mdps
through precomputed binomial distributions. In Proceedings of the 16th Conference on Autonomous Agents
and MultiAgent Systems, pages 732–740. International
Foundation for Autonomous Agents and Multiagent
Systems.
Littman, M. L. (1994). Markov games as a framework
for multi-agent reinforcement learning. In Machine
Learning Proceedings 1994, pages 157–163. Elsevier.
Mnih, V., Badia, A. P., Mirza, M., Graves, A., Lillicrap,
T., Harley, T., Silver, D., and Kavukcuoglu, K. (2016).
Asynchronous methods for deep reinforcement learning. In International Conference on Machine Learning,
pages 1928–1937.
Mnih, V., Kavukcuoglu, K., Silver, D., Rusu, A. A., Veness, J., Bellemare, M. G., Graves, A., Riedmiller, M.,
Fidjeland, A. K., Ostrovski, G., et al. (2015). Human-

level control through deep reinforcement learning. Nature, 518(7540):529.
Nair, R., Varakantham, P., Tambe, M., and Yokoo, M.
(2005). Networked distributed pomdps: A synthesis
of distributed constraint optimization and pomdps. In
AAAI, volume 5, pages 133–139.
Nguyen, D. T., Kumar, A., and Lau, H. C. (2017). Policy
gradient with value function approximation for collective multiagent planning. In Advances in Neural
Information Processing Systems, pages 4322–4332.
Perolat, J., Leibo, J. Z., Zambaldi, V., Beattie, C., Tuyls,
K., and Graepel, T. (2017). A multi-agent reinforcement learning model of common-pool resource appropriation. In Advances in Neural Information Processing
Systems, pages 3646–3655.
Schulman, J., Abbeel, P., and Chen, X. (2017). Equivalence between policy gradients and soft q-learning.
arXiv preprint arXiv:1704.06440.
Silver, D., Huang, A., Maddison, C. J., Guez, A., Sifre, L.,
Van Den Driessche, G., Schrittwieser, J., Antonoglou,
I., Panneershelvam, V., Lanctot, M., et al. (2016). Mastering the game of go with deep neural networks and
tree search. nature, 529(7587):484–489.
Silver, D., Schrittwieser, J., Simonyan, K., Antonoglou,
I., Huang, A., Guez, A., Hubert, T., Baker, L., Lai, M.,
Bolton, A., et al. (2017). Mastering the game of go
without human knowledge. Nature, 550(7676):354.
Varakantham, P., Adulyasak, Y., and Jaillet, P. (2014).
Decentralized stochastic planning with anonymity in
interactions. In AAAI, pages 2505–2512.
Varakantham, P., Cheng, S.-F., Gordon, G., and Ahmed,
A. (2012). Decision support for agent populations in
uncertain and congested environments. In AAAI.
Verma, T., Varakantham, P., Kraus, S., and Lau, H. C.
(2017). Augmenting decisions of taxi drivers through
reinforcement learning for improving revenues. In
International Conference on Automated Planning and
Scheduling, pages 409–417.
Watkins, C. J. and Dayan, P. (1992). Q-learning. Machine
learning, 8(3-4):279–292.

