# Universal Policies to Learn Them All

Hassam Ullah Sheikh Department of Computer Science University of Central
Florida Orlando, Florida, United States<EMAIL_ADDRESS>Ladislau
Bölöni Department of Computer Science University of Central Florida Orlando,
Florida, United States<EMAIL_ADDRESS>
###### Abstract

We explore a collaborative and cooperative multi-agent reinforcement learning
setting where a team of reinforcement learning agents attempt to solve a
single cooperative task in a multi-scenario setting. We propose a novel multi-
agent reinforcement learning algorithm inspired by universal value function
approximators that not only generalizes over state space but also over a set
of different scenarios. Additionally, to prove our claim, we are introducing a
challenging 2D multi-agent urban security environment where the learning
agents are trying to protect a person from nearby bystanders in a variety of
scenarios. Our study shows that state-of-the-art multi-agent reinforcement
learning algorithms fail to generalize a single task over multiple scenarios
while our proposed solution works equally well as scenario-dependent policies.

##  1 Introduction

Recent research in deep reinforcement learning (RL) has led to wide range of
accomplishments in learning optimal policies for sequential decision making
problems. These accomplishments include training agents in simulated
environments such as playing Atari games Mnih et al. (2015), beating the best
players in board games like Go and Chess Silver et al. (2016) as well as
learning to solve real world problems. Similar to single agent reinforcement
learning, multi-agent reinforcement (MARL) is also producing break through
results in challenging collaborative-competitive environments such as OpenAI
(2018); Jaderberg et al. (2018); Liu et al. (2019).

The success in reinforcement learning has prompted interest in more complex
challenges as well as a shift towards cases in which an agent tries to learn
multiple tasks in a single environment. Formally this paradigm of learning is
known as multitask reinforcement learning Teh et al. (2017). The essence of
multitask reinforcement learning is to simultaneously learn multiple tasks
jointly to speed up learning and induce better generalization by exploiting
the common structures among multiple tasks.

Despite having success in single agent multitask reinforcement learning Borsa
et al. (2019); Teh et al. (2017), multitask multi-agent reinforcement learning
has been explored in only one recent study Omidshafiei et al. (2017). In this
paper, we are exploring an opposite problem where multiple reinforcement
learning agents are trying to master a single task across multiple scenarios.
Consider multiple RL agents trying to master a single task in multiple
scenarios. In order for the agents to generalise, they need to able to
identify and exploit common structure of the single task under multiple
scenarios. One possible structure is the similarity between the solutions of
the single task over multiple scenarios either in the policy space or
associated value-function space. For this, we build our solution upon two
frameworks. The first framework is universal value function approximators
(UVFAs) by Schaul et al. (2015) and the second framework is multi-agent deep
deterministic policy gradient (MADDPG) by Lowe et al. (2017). UVFAs are
extension of value functions that also include the notion of a task or a
scenario thus exploiting common structure in associated optimal value
functions. MADDPG is a multi-agent reinforcement learning algorithm that uses
the centralized training and distributed testing paradigm to stabilize
learning. The outcome of combining these two frameworks is a solution for
multi-agents that learn to generalize over both state space and a set of
multiple scenarios.

To investigate the emergence of collaboration in multi-scenario learning for
multi-agent learning agents, we designed a challenging environment with
simulated physics in Multi-Agent Particle Environment Mordatch and Abbeel
(2017). We have developed 4 different simulated scenarios representing a
challenging urban security problem of providing physical protection to VIP
from nearby bystanders of more than one different class. The complexity in our
environment arises primarily from the different moving patterns of these
bystanders that a standard state-of-the-art MARL algorithm such as MADDPG Lowe
et al. (2017) fail to capture. The goal here is to learn a stable and a
consistent multi-agent cooperative behavior across all the known scenarios.
Here, we are not dealing with unknown scenarios.

##  2 Background

Partially observable Markov Game Littman (1994) is a multi-agent extension of
MDP characterized by $\mathcal{S}$, $N$ agents with partial observations
$\mathcal{O}=\left\\{\mathcal{O}_{1},\ldots,\mathcal{O}_{N}\right\\}$ of the
environment with a collective action space of
$\mathcal{A}=\left\\{\mathcal{A}_{1},\ldots,\mathcal{A}_{N}\right\\}$, a
reward function $\mathcal{R}$ and a state transition function $\mathcal{T}$.
At every time step, each agent chooses an action $a_{i}$ from it’s policy
$\pi$ parameterized by $\theta_{i}$ conditioned on its private observation
$o_{i}$ i.e $a_{i}=\pi_{\theta_{i}}\left(o_{i}\right)$ and receives a reward
$r_{i}=\mathcal{R}\left(s,a_{i}\right)$ The goal of each agent is to maximise
its own total expected return
$\mathbb{E}\left[G_{i}\right]=\mathbb{E}\left[\sum_{t=0}^{T}\gamma^{t}r_{i}^{t}\right]$
where $r_{i}^{t}$ is the collected reward by agent $i$ at time $t$.

###  2.1 Policy Gradients

Policy gradient methods have been shown to learn the optimal policy in a
variety of reinforcement learning tasks. The main idea behind policy gradient
methods is to maximize the objective function by parameterizing the policy
$\pi$ with $\theta$ and updating the policy parameters in the direction of the
gradient $\nabla J{\left(\theta\right)}$ of the objective function
$J\left(\theta\right)=\mathbb{E}\left[{G}^{t}\right]$. The gradient is defined
as

$\nabla
J{\left(\theta\right)}=\mathbb{E}\left[\nabla_{\theta}\log\pi_{\theta}\left(a|s\right)Q^{\pi}\left(s,a\right)\right]$

Silver et al. (2014) has shown that it is possible to extend the policy
gradient framework to deterministic policies i.e.
$\pi_{\theta}:\mathcal{S}\rightarrow\mathcal{A}$. In particular we can write
$\nabla J\left(\theta\right)$ as

$\nabla
J{\left(\theta\right)}=\mathbb{E}\left[\nabla_{\theta}\pi\left(a|s\right)\nabla_{a}Q^{\pi}\left(s,a\right)|_{a=\pi\left(s\right)}\right]$

A variation of this model, Deep Deterministic Policy Gradients (DDPG)
Lillicrap et al. (2015) is an off-policy algorithm that approximates the
policy $\pi$ and the critic $Q^{\pi}$ with deep neural networks. DDPG also
uses an experience replay buffer alongside a target network to stabilize the
training.

Multi-agent deep deterministic policy gradients (MADDPG) Lowe et al. (2017)
extends DDPG for the multi-agent setting where each agent has it’s own policy.
The gradient of each policy is written as

$\nabla
J{\left(\theta_{i}\right)}=\mathbb{E}\left[\nabla_{\theta_{i}}\pi_{i}\left(a_{i}|o_{i}\right)\nabla_{a_{i}}Q_{i}^{\pi}\left(s,a_{1},\ldots,a_{N}\right)|_{a_{i}=\pi_{i}\left(o_{i}\right)}\right]$

where $s=\left(o_{1},\ldots,o_{N}\right)$ and
$Q_{i}^{\pi}\left(s,a_{1},\ldots,a_{N}\right)$ is a centralized action-value
function that takes the actions of all the agents in addition to the state of
the environment to estimate the Q-value for agent $i$. Since every agent has
it’s own Q-function, the model allows the agents to have different action
spaces and reward functions. The primary motivation behind MADDPG is that
knowing all the actions of other agents makes the environment stationary that
helps in the stabilization of the training, even though the policies of the
agents change.

The Universal Value Function Approximator Schaul et al. (2015) is an extension
of DQN Mnih et al. (2015) where it generalizes not only over a set of states
but also on a set of goals. At the beginning of the episode, a state-goal pair
is sampled from a probability distribution, the goal remains constant
throughout the episode. At each timestep, the agent receives a pair of current
state and goal and gets the reward $r^{t}=r_{g}\left(s^{t},a^{t}\right)$. As a
result, the Q-function is not only dependent on state-action pair but also on
the goal. The extension of this approach is straight forward for DDPG Marcin
et al. (2017) and MADDPG.

##  3 Multi-Agent Universal Policy Gradient

We propose multi-agent universal policy gradient: a multi-agent deep
reinforcement learning algorithm that learns distributed policies not only
over state space but also over a set of scenarios.

While generalization across multi-task in multi-agent reinforcement learning
has been studied in Omidshafiei et al. (2017), to our best knowledge we are
the first one to consider the multi-scenario multi-agent deep RL system. Our
approach uses Universal Value Function Approximators Schaul et al. (2015) to
train policies and value functions that take a state-scenario pair as an
input. The outcome are universal multi-agent policies that are able to perform
on multiple scenarios as well as policies that are trained separately.

The main idea is to represent the different value function approximators for
each agent $i$ by a single unified value function approximator that
generalizes of over both state space and a set of scenarios. For agent $i$ we
consider $V_{i}\left(s,g;\phi\right)\approx V_{i_{g}}^{*}\left(s\right)$ or
$Q_{i}\left(s,a,g;\phi\right)\approx Q_{i_{g}}^{*}\left(s,a\right)$ that
approximate the optimal unified value functions over multiple scenarios and a
large state space. These value functions can be used to extract policies
implicitly or as critics for policy gradient methods.

The learning paradigm we used is similar to the centralized training with
decentralized execution during testing used by Lowe et al. (2017). In this
setting, additional information is provided for the agents during training
that is not available during test time. Thus, extracting policies from value
functions is not feasible in this model. However, the value functions can be
used as critics in a multi-agent deep deterministic policy gradient setting.

Concretely, consider an environment with $N$ agents with policies
$\boldsymbol{\pi}=\\{\boldsymbol{\pi_{1}},\ldots,\boldsymbol{\pi_{N}}\\}$
parameterized by
$\boldsymbol{\theta}=\\{\boldsymbol{\theta_{1}},\ldots,\boldsymbol{\theta_{N}}\\}$
then the multi-agent deep deterministic policy gradient for agent $i$ can
written as

$\nabla
J{\left(\theta_{i}\right)}=\mathbb{E}\left[\nabla_{\theta_{i}}\pi_{i}\left(a_{i}|o_{i}\right)\nabla_{a_{i}}Q_{i}^{\pi}\left(s,a_{1},\ldots,a_{N}\right)|_{a_{i}=\pi_{i}\left(o_{i}\right)}\right]$

where $s=\left(o_{1},\ldots,o_{N}\right)$ and
$Q_{i}^{\pi}\left(s,a_{1},\ldots,a_{N}\right)$ is a centralized action-value
function parameterized by $\phi_{i}$ that takes the actions of all the agents
in addition to the state of the environment to estimate the Q-value for agent
$i$. We extend the idea of MADDPG with universal functional approximator,
specifically we augment the centralized critic with an embedding of the
scenario. Now the modified policy gradient for each agent $i$ can be written
as

$\displaystyle\begin{split}\nabla
J{\left(\theta_{i}\right)}&=\mathbb{E}_{s,a,g\thicksim\mathcal{D}}\Bigg{[}\nabla_{\theta_{i}}\pi_{i}\left(a_{i}|o_{i},g\right)\\\
&\qquad\nabla_{a_{i}}Q_{i}^{\pi}\left(s,a_{1},\ldots,a_{N},g\right)\Bigg{]}\end{split}$
(1)

where ${a_{i}=\pi_{i}\left(o_{i},g\right)}$ is action from agent $i$ following
policy $\pi_{i}$ and $\mathcal{D}$ is the experience replay buffer. The
centralized critic is $Q_{i}^{\pi}$ is updated as:

$\mathcal{L}\left(\phi_{i}\right)=\mathbb{E}_{s,a,r,s^{\prime},g}\left[\left(Q_{i}^{\pi}\left(s,a_{1},\ldots,a_{N},g\right)\right)-y\right]$

where $y$ is defined as:

$y=r_{i}^{g}+\gamma
Q_{\phi^{\prime}_{i}}^{\pi^{\prime}}\left(s^{\prime},a^{\prime}_{1},\ldots,a^{\prime}_{N},g\right)|_{a^{\prime}_{i}=\pi^{\prime}_{i}\left(o_{i}^{\prime},g\right)}$

where
$\boldsymbol{\pi^{\prime}}=\\{\boldsymbol{\pi^{\prime}_{1}},\ldots,\boldsymbol{\pi^{\prime}_{N}}\\}$
are target policies parameterized by
$\boldsymbol{\theta^{\prime}}=\\{\boldsymbol{\theta_{1}^{\prime}},\ldots,\boldsymbol{\theta^{\prime}_{N}}\\}$.

The overall algorithm to which we refer as multi-agent universal policy
gradient (MAUPG) is described in algorithm 1. Additionally, we refer the
learnt policies as universal policies. The overview of the architecture can be
seen in fig. 1.

Algorithm 1 Multi-agent Universal Policy Gradient

1:Sample a random scenario $g$

2:for episode = 1 to $M$ do

3: for t = 1 to episode–length do

4: For each agent $i$, select action
$a_{i}^{t}=\pi_{\theta_{i}}\left(o^{t}_{i},g\right)$

5: Execute actions $\textbf{a}_{t}=\left[a^{t}_{1},\ldots,a^{t}_{N}\right]$

6: For each agent $i$, get next observation $o_{i}^{t+1}$

7: end for

8: Sample an additional scenario $k$

9: for t = 1 to episode–length do

10: for agent i = 1 to N do

11: Get reward $r_{i}^{t}\coloneqq r^{g}_{i}\left(o^{t}_{i},a^{t}_{i}\right)$

12: Store $\left(o^{t}_{i},a^{t}_{i},r_{i}^{t},o^{t+1}_{i},g\right)$ in replay
buffer

13: /* Hindsight Replay */

14: Get reward $r_{i}^{t}\coloneqq r^{k}_{i}\left(o^{t}_{i},a^{t}_{i}\right)$

15: Store $\left(o^{t}_{i},a^{t}_{i},r_{i}^{t},o^{t+1}_{i},k\right)$ in replay
buffer

16: end for

17: end for

18: Set $g=k$

19: for agent $i=1$ to $N$ do

20: Sample minibatch of size S
$\left(\textbf{s}^{j},\textbf{a}^{j},\textbf{r}^{j},\textbf{s}^{{}^{\prime}j},\textbf{g}^{j}\right)$

21: $\textbf{w}\coloneqq\left(\pi^{\prime}_{\theta_{i}}(o^{\prime
j}_{i},g^{j}),\ldots,\pi^{\prime}_{\theta_{N}}(o^{\prime j}_{N},g^{j})\right)$

22: $\left(a^{\prime}_{1},\ldots,a^{\prime}_{N}\right)\coloneqq\textbf{w}$

23: Set $y^{j}=r_{i}^{j}+\gamma
Q_{\phi^{\prime}_{i}}^{\pi^{\prime}}\left(\textbf{s}^{{}^{\prime}j},a^{\prime}_{1},\ldots,a^{\prime}_{N},\textbf{g}^{j}\right)$

24: Update critic by minimizing
$\frac{1}{S}\sum_{j}\left(y^{j}-Q_{\phi_{i}}^{\pi}\left(\textbf{s}^{j},a^{j}_{1},\ldots,a^{j}_{N},\textbf{g}^{j}\right)\right)$

25:
$\theta_{i}+=\sum_{j}\frac{\nabla_{\theta_{i}}\pi_{i}\left(a_{i}|o_{i}^{j},g^{j}\right)\nabla_{a_{i}}Q_{\phi_{i}}^{\pi}\left(\textbf{s}^{j},a^{j}_{1},..,a^{j}_{N},\textbf{g}^{j}\right)}{S}$

26: end for

27: Update target network parameters for each agent $i$
$\displaystyle\theta^{\prime}_{i}\leftarrow\tau\theta_{i}+\left(1-\tau\right)\theta^{\prime}_{i}$
$\displaystyle\phi^{\prime}_{i}\leftarrow\tau\phi_{i}+\left(1-\tau\right)\phi^{\prime}_{i}$

28:end for

(a) An overview of the mutli-agent decentralized actor with centralized critic
represented by a universal value function approximator.

(b) Representation of the single centralized critic by a universal function
approximator.

Figure 1: An overview of the multi-agent universal policy gradient
architecture where both actors and critics are augmented with the goal that
the agents are trying to achieve.

(a) Random Landmarks

(b) Shopping Mall

(c) Street

(d) Pie-in-the-face

Figure 2: Visual representation of the four different scenarios. Emergence of
complex behavior can be clearly seen where the bodyguards(in blue) have
positioned themselves between the VIP(in brown) and the bystanders(in red)
shielding from potential threat.

(a) Random Landmarks

(b) Shopping Mall

(c) Street

(d) Red Carpet

Figure 3: Learning curve of the scenarios in terms of average cumulative
reward for the bodyguards. Notice that start-of-the-art multi-agent
reinforcement learning algorithms such as COMA and Q-MIX fail to even take off
in most of the challenging scenarios. MADDPG was the only consistent algorithm
that was able to learn in the environment.

##  4 Experimental Setup

###  4.1 The VIP Protection Problem

To demonstrate the effectiveness of our proposed algorithm, we simulated an
urban security problem of VIP protection where a team of learning agents
(bodyguards) are providing physical protection to a VIP from bystanders in a
crowded space. This problem is briefly explored in Sheikh and Bölöni (2018a,
b).

We are considering a VIP moving in a crowd of bystanders
$\mathcal{B}=\left\\{b_{1},b_{2},\ldots,b_{M}\right\\}$ protected from assault
by a team of bodyguards $R=\left\\{r_{1},r_{2},\ldots,r_{N}\right\\}$. To be
able to reason about this problem, we need to quantify the threat to the VIP
at a given moment from the nearby bystanders–the aim of the bodyguards is to
reduce this value.

Two agents $x$ and $y$ have a line of sight $LoS(x,y)\in\left[0,1\right]$ if
$x$ can directly observe $y$ and with no obstacle between them. A bystander
$b$ can only pose a threat to the VIP if it is closer than the safe distance
$\mathrm{SafeDist}$. The threat level $\mathrm{TL}\left(\mathrm{VIP},b\right)$
Bhatia et al. (2016) is defined as the probability that a bystander $b$ can
successfully assault the VIP, defined as a value exponentially decaying with
distance:

$\mathrm{TL}\left(\mathrm{VIP},b\right)=\exp^{-A\left(\mathrm{Dist}(\mathrm{VIP},b)\right)/B}$
(2)

where the VIP should be in line of sight of $b$ and
$\mathrm{Dist}(\mathrm{VIP},b)<\mathrm{SafeDist}$. $A$ and $B$ are positive
constants that control the decay rate of the threat level.

The residual threat $RT\left(VIP,\mathcal{B},R\right)$ is defined as the
threat to the VIP at time $t$ from bystanders $\mathcal{B}$. Bodyguards can
block the line of sight from the bystanders, thus the residual threat is
always smaller than the threat level and depends on the position of the
bodyguards with respect to the bystanders and the VIP. The cumulative residual
threat to the VIP from bystanders $\mathcal{B}$ in the presence of bodyguards
$R$ over the time period $[0,T]$ is defined as:

$\mathrm{CRT}=\intop_{0}^{T}1-\prod_{i=1}^{k}\left(1-RT\left(VIP,b_{i},R\right)\right)dt$
(3)

Our end goal is to minimize $\mathrm{CRT}$ through multi-agent reinforcement
learning.

###  4.2 Simulation and Scenarios

We designed four scenarios inspired from possible real world situations of VIP
protection and implemented them as behaviors in the Multi-Agent Particle
Environment( fig. 2) Mordatch and Abbeel (2017).

In each scenario, the participants are the VIP, 4 bodyguards and 10 bystanders
of one or more classes. The scenario description contains a number of
landmarks, points on a 2D space that serve as a starting point and
destinations for the goal-directed movement by the agents. For each scenario,
the VIP (brown disk) starts from the starting point and moves towards the
destination landmark (green disk). The VIP exhibits a simple path following
behavior, augmented with a simple social skill metric: it is about to enter
the personal space of a bystander, it will slow down or come to a halt.

The scenarios differ in the arrangement of the landmarks and the behavior of
the different classes of bystanders.

  1. A

Random Landmark: In this scenario, 12 landmarks are placed randomly in the
area. The starting point and destination for the VIP are randomly selected
landmarks. The bystanders are performing random waypoint navigation: they pick
a random landmark, move towards it, and when they reached it, they choose a
new destination. A set of fixed seeds were used for placement of landmarks and
a different set of seeds were used for spawning bystanders in the environment.

  2. B

Shopping Mall: In this scenario, 12 landmarks are placed in fixed position on
the periphery of the area, representing shops in a market. The bystanders
visit randomly selected shops and were spawned using a fixed set of random
seeds.

  3. C

Street: This scenario aims to model the movement on a crowded sidewalk. The
bystanders are moving towards waypoints that are outside the current area.
However, due to their proximity to each other, the position of the other
bystanders influence their movement described by laws of particles motion
Vicsek et al. (1995).

  4. D

Pie-in-the-Face: While the in other scenarios the bystanders treat the VIP as
just another person, in this “red carpet” scenario the bystanders take an
active interest in the VIP. We consider two distinct classes of bystanders
with different behaviors. Rule-abiding bystanders stay behind a designated
line observing as the VIP passes in front of them. Unruly bystanders break the
limit imposed by the line and try to approach the VIP (presumably, to throw a
pie in his/her face).

#### Observation and Action Space

Following the model of Multi-Agent Particle Environment Mordatch and Abbeel
(2017), the action space $\mathcal{A}_{i}$ of each bodyguard $i$ consists of
2D vector of forces applied on the bodyguard and to promote collaboration and
cooperation Mordatch and Abbeel (2017), a c dimensional communication channel.

The observation of each bodyguard is the physical state of the nearest
$m\subset M$ bystanders, all the $N$ bodyguards in the scenario and their
verbal utterances such that $o_{i}=\left[x_{j,\ldots N+m},c_{k,\ldots
N}\right]\in\mathcal{O}_{i}$ where $x_{j}$ is the observation of the entity
$j$ from the perspective of agent $i$ and $c_{k}$ is the verbal utterance of
the agent $k$.

In this problem, we are assuming that all bodyguards have identical
observation space and action space. Moreover, each scenario embedding $g$ is
represented as a one hot vector.

###  4.3 Reward Function

Using the definitions of threat level and cumulative residual threat defined
in eq. 2 and eq. 3 respectively, the reward function $r_{b}$ for bodyguard $i$
can be written as

$r_{b}=-1+\prod_{i=1}^{k}\left(1-\mathit{RT}\left(VIP,b_{i},R\right)\right)$
(4)

To encourage the bodyguards to stay at a limited distance from the VIP and
discourage them to attack the bystanders, a distance regularizer $\mathcal{D}$
is added to eq. 4 to form the final reward function.

$\mathcal{D}\left(\mathit{VIP},x_{i}\right)=\begin{cases}0&m\leq\left\|x_{i}-\mathit{VIP}\right\|_{2}\leq
d\\\ -1&\text{otherwise}\\\ \\\ \end{cases}$ (5)

where $m$ is the minimum distance the bodyguard has to maintain from VIP and
$d$ is the $\mathrm{SafeDist}$ mentioned in section 4.1. The final reward
function is represented as

$\displaystyle r_{b}=$
$\displaystyle\alpha\left(-1+\prod_{i=1}^{k}\left(1-\mathit{RT}\left(VIP,b_{i},R\right)\right)\right)$
(6)
$\displaystyle+\beta\left(\mathcal{D}\left(\mathit{VIP},x_{i}\right)\right)$

Depending upon on the scenario $g$, different values of $\alpha$, and $\beta$
were chosen for the optimal performance. A different value of $\alpha$ and
$\beta$ also fulfills the requirement of a different reward function to train
a UVFA.

##  5 Experiments and Results

In this section, we first evaluate the usefulness of multi-agent reinforcement
learning on the given problem by comparing it’s results with an hand-
engineered solution for the VIP problem. Then we demonstrate the inability of
the state-of-the-art MARL algorithms to generalize over different scenarios.
Finally we compare the results of scenario dependant policies with the results
of universal policies. Our primary evaluation metric is Cumulative Residual
Threat (CRT) defined in eq. 3.

###  5.1 Multi-Agent Reinforcement Learning vs Quadrant Load Balancing

In order to verify that multi-agent reinforcement learning solutions are
better than explicitly programmed behavior of the bodyguards, we evaluate
policies trained on individual scenarios with quadrant load balancing
technique (QLB) introduced in Bhatia et al. (2016).

To identify the best MARL algorithm to compete with the hand-engineered
solution, we trained five state-of-the-art MARL algorithms such as Q-Mix, VDN,
IQL, COMA111https://github.com/oxwhirl/pymarl/ and MADDPG on our environment.
It can be seen in fig. 3 that MADDPG was the only algorithm that was
successful in learning in our environment while other algorithms fail even to
take off. Therefore, we dropped the CRT graphs.

We then compared the results of MADDPG with quadrant load-balancing (QLB).
From the results in fig. 4 we can see that the outcome are different depending
on the characteristics of the scenario. For the Pie-in-the-face scenario,
where most of the bystanders stay away behind the lines, both the RL-learned
agent and the QLB model succeeded to essentially eliminate the threat. This
was feasible in this specific setting, as there were four bodyguard agents for
one “unruly” bystander. For the other scenarios, the average cumulative
residual threat values are higher for both algorithms. However, for the Random
Landmark and Shopping Mall scenarios the RL algorithm is able to reduce the
threat to less than half, while in the case of the Street scenario, to less
than one ninth of the QLB value.

Figure 4: Comparing the average cumulative residual threat values of MADDPG
and QLB on four different scenarios.

Overall, these experiments demonstrate that the multi-agent reinforcement
learning can learn behaviors that improve upon algorithms that were hand-
crafted for this specific task.

###  5.2 Universal Policies Vs Scenario-Dependant Policies

In order to verify the claim that MARL algorithms trained on specific scenario
fail to generalize over different scenarios, we evaluate policies trained via
MADDPG on specific scenario and test them on different scenarios. Policies on
specific scenarios were trained using the same settings and configurations
from experiments performed in section 5.1.

Figure 5: A confusion matrix representing the average residual threat values
of MADDPG policies trained on specific scenario when tested on different
scenarios over 100 episodes. Figure 6: Comparing the average cumulative
residual threat values for universal policy agents with MADDPG and QLB agents

From the results shown in fig. 5 we can see that MADDPG policies trained on
specific scenarios performed poorly when tested on different scenarios as
compared to when tested on same scenario with different seeds. In order to
tackle the generalization problem, we train the agents using multi-agent
universal policy gradient and compare its results with the results of
scenario-dependant MADDPG policies.

From the results in fig. 6 we can see that our proposed method performs better
than policies trained on specific scenarios as well as quadrant-load
balancing. Overall, these experiments demonstrate that start-of-the-art MARL
algorithms such as MADDPG fail to generalize a single task over multiple
scenarios while our proposed solution MAUPG learn policies that allows a
single task to be learnt across multiple scenarios and improve upon the start-
of-the-art multi-agent reinforcement learning algorithm.

##  6 Ablation Study

The first natural question that can be asked here is that why can’t we just
sample scenarios during training of a standard MADDPG? To answer this question
and to see the effect of UVFA and hindsight replay used in MAUPG, we perform
an ablation study in which we gradually add important building blocks to
MADDPG to transform the solution into MAUPG. First to answer the question, we
trained a MADDPG and sampled different scenarios. Second we replaced the
standard centralized critic with an UVFA and finally we added the hindsight
replay step. All the training settings and hyperparameters were kept same
across all the experiments.

From figs. 7 and 8, we can see that MADDPG does not learn half as good as
MAUPG with or without the hindsight replay step. MAUPG learns better and
faster than MAUPG without hindsight replay. This happens because MAUPG with
hindsight replay benefits from replaying trajectories from one scenario in
other scenarios(see lines 14 and 15 of algorithm 1) thus providing more
experience to learn efficiently.

Figure 7: Learning curves of the ablated version of MAUPG. Notice the increase
in performance in terms of average cumulative reward with an addition of UVFAs
and hindsight replay step.  Figure 8: Learning curves of the ablated version
of MAUPG. Notice the decline in average cumulative residual threat with an
addition of UVFAs and hindsight replay step.

##  7 Conclusion

In this paper, we highlighted the issue with MARL algorithms of failing to
generalize a single task over multiple known scenarios. To solve the
generalization problem, we proposed multi-agent universal policy gradient, a
universal value function approximator inspired policy gradient method that not
only generalizes over state space but also over set of different scenarios. We
also built a 2D challenging environment simulating an urban security problem
that can be used as a benchmark for similar problems. Experimental studies
have demonstrated that our proposed method generalizes well on different
scenario and performs better than MADDPG when trained on different scenarios
individually.

## References

  * Bhatia et al. (2016) T.S. Bhatia, G. Solmaz, D. Turgut, and L. Bölöni.  Controlling the movement of robotic bodyguards for maximal physical protection.  In Proc. of the 29th International FLAIRS Conference, pages 380–385, May 2016.
  * Borsa et al. (2019) Diana Borsa, Andre Barreto, John Quan, Daniel J. Mankowitz, Hado van Hasselt, Remi Munos, David Silver, and Tom Schaul.  Universal successor features approximators.  In International Conference on Learning Representations, 2019.
  * Jaderberg et al. (2018) Max Jaderberg, Wojciech M. Czarnecki, Iain Dunning, Luke Marris, Guy Lever, Antonio Garcia Castaneda, Charles Beattie, Neil C. Rabinowitz, Ari S. Morcos, Avraham Ruderman, Nicolas Sonnerat, Tim Green, Louise Deason, Joel Z. Leibo, David Silver, Demis Hassabis, Koray Kavukcuoglu, and Thore Graepel.  Human-level performance in first-person multiplayer games with population-based deep reinforcement learning.  arXiv preprint arXiv: 1807.01281, 2018.
  * Lillicrap et al. (2015) Timothy P. Lillicrap, Jonathan J. Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra.  Continuous control with deep reinforcement learning.  In Proc. of the 3rd Int’l Conf. on Learning Representations (ICLR), 2015.
  * Littman (1994) Michael L. Littman.  Markov games as a framework for multi-agent reinforcement learning.  In Proc. of the 11th Int’l Conf. on Machine Learning(ICML), pages 157–163. Morgan Kaufmann, 1994.
  * Liu et al. (2019) Siqi Liu, Guy Lever, Nicholas Heess, Josh Merel, Saran Tunyasuvunakool, and Thore Graepel.  Emergent coordination through competition.  In International Conference on Learning Representations, 2019.
  * Lowe et al. (2017) Ryan Lowe, Yi Wu, Aviv Tamar, Jean Harb, Pieter Abbeel, and Igor Mordatch.  Multi-agent actor-critic for mixed cooperative-competitive environments.  In Advances in Neural Information Processing Systems 30, pages 6379–6390, 2017.
  * Marcin et al. (2017) Andrychowicz Marcin, Wolsk Filip, Ray Alex, Schneider Jonas, Fong Rachel, Welinde Peter, McGrew Bob, Tobin Josh, Pieter Abbeel, and Zaremba Wojciech.  Hindsight experience replay.  In Advances in Neural Information Processing Systems 30, pages 5048–5058, 2017.
  * Mnih et al. (2015) Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A. Rusu, Joel Veness, Marc G. Bellemare, Alex Graves, Martin Riedmiller, Andreas K. Fidjeland, Georg Ostrovski, Stig Petersen, Charles Beattie, Amir Sadik, Ioannis Antonoglou, Helen King, Dharshan Kumaran, Daan Wierstra, Shane Legg, and Demis Hassabis.  Human-level control through deep reinforcement learning.  Nature, 518(7540):529–533, 02 2015.
  * Mordatch and Abbeel (2017) Igor Mordatch and Pieter Abbeel.  Emergence of grounded compositional language in multi-agent populations.  arXiv preprint arXiv:1703.04908, 2017.
  * Omidshafiei et al. (2017) Shayegan Omidshafiei, Jason Pazis, Christopher Amato, Jonathan P. How, and John Vian.  Deep decentralized multi-task multi-agent reinforcement learning under partial observability.  In Proc. of the 34th Int’l Conf. on Machine Learning(ICML), pages 2681–2690, 2017.
  * OpenAI (2018) OpenAI.  OpenAI Five, 2018.  https://blog.openai.com/openai-five/.
  * Schaul et al. (2015) Tom Schaul, Daniel Horgan, Karol Gregor, and David Silver.  Universal value function approximators.  In Proc. of the 32st Int’l Conf. on Machine Learning(ICML), pages 1312–1320, 2015.
  * Sheikh and Bölöni (2018a) H. U. Sheikh and L. Bölöni.  Designing a multi-objective reward function for creating teams of robotic bodyguards using deep reinforcement learning.  In Prof. of 1st Workshop on Goal Specifications for Reinforcement Learning (GoalsRL-2018) at ICML 2018, July 2018.
  * Sheikh and Bölöni (2018b) H. U. Sheikh and L. Bölöni.  The emergence of complex bodyguard behavior through multi-agent reinforcement learning.  In Proc. of Autonomy in Teams (AIT-2018) workshop at ICML-2018, July 2018.
  * Silver et al. (2014) David Silver, Guy Lever, Nicolas Heess, Thomas Degris, Daan Wierstra, and Martin Riedmiller.  Deterministic policy gradient algorithms.  In Proc. of the 31st Int’l Conf. on Machine Learning(ICML), pages 387–395, 2014.
  * Silver et al. (2016) David Silver, Aja Huang, Christopher J. Maddison, Arthur Guez, Laurent Sifre, George van den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Marc Lanctot, Sander Dieleman, Dominik Grewe, John Nham, Nal Kalchbrenner, Ilya Sutskever, Timothy Lillicrap, Madeleine Leach, Koray Kavukcuoglu, Thore Graepel, and Demis Hassabis.  Mastering the game of Go with deep neural networks and tree search.  Nature, 529:484–503, 2016.
  * Teh et al. (2017) Yee Teh, Victor Bapst, Wojciech M. Czarnecki, John Quan, James Kirkpatrick, Raia Hadsell, Nicolas Heess, and Razvan Pascanu.  Distral: Robust multitask reinforcement learning.  In Advances in Neural Information Processing Systems 30, pages 4496–4506. 2017.
  * Vicsek et al. (1995) Tamás Vicsek, András Czirók, Eshel Ben-Jacob, Inon Cohen, and Ofer Shochet.  Novel type of phase transition in a system of self-driven particles.  Physical review letters, 75(6):1226, 1995.