Coordinated Exploration via Intrinsic Rewards for Multi-Agent Reinforcement Learning
Authors: Shariq Iqbal
Fei Sha
Venue:  (2020)
Keywords: multi-agent reinforcement learning
multi-agent
exploration
intrinsic motivation
MARL
coordinated exploration

Abstract: Solving tasks with sparse rewards is one of the most important challenges in reinforcement learning. In the single-agent setting, this challenge has been addressed by introducing intrinsic rewards that motivate agents to explore unseen regions of their state spaces. Applying these techniques naively to the multi-agent setting results in agents exploring independently, without any coordination among themselves. We argue that learning in cooperative multi-agent settings can be accelerated and improved if agents coordinate with respect to what they have explored. In this paper we propose an approach for learning how to dynamically select between different types of intrinsic rewards which consider not just what an individual agent has explored, but all agents, such that the agents can coordinate their exploration and maximize extrinsic returns. Concretely, we formulate the approach as a hierarchical policy where a high-level controller selects among sets of policies trained on different types of intrinsic rewards and the low-level controllers learn the action policies of all agents under these specific rewards. We demonstrate the effectiveness of the proposed approach in a multi-agent gridworld domain with sparse rewards, and then show that our method scales up to more complex settings by evaluating on the VizDoom platform.

Under review as a conference paper at ICLR 2020
COORDINATED EXPLORATION VIA INTRINSIC RE- WARDS FOR MULTI-AGENT REINFORCEMENT LEARN- ING
Anonymous authors Paper under double-bling review
ABSTRACT
Solving tasks with sparse rewards is of the most important challenges in rein- forcement learning. In the single-agent setting, this challenge has been addressed by introducing intrinsic rewards that motivate agents to explore unseen regions of their state spaces. Applying these techniques naively to the multi-agent set- ting results in agents exploring independently, without any coordination among themselves. We argue that learning in cooperative multi-agent settings can be accelerated and improved if agents coordinate with respect to what they have ex- plored. In this paper we propose approach for learning how dynamically select between different types intrinsic rewards which consider not just what individual agent has explored, but all agents, such that the agents can coordi- nate their exploration and maximize extrinsic returns. Concretely, we formulate the approach as hierarchical policy where high-level controller selects among sets of policies trained on different types of intrinsic rewards and the low-level controllers learn the action policies of all agents under these specific rewards. We demonstrate the effectiveness of the proposed approach in a multi-agen gridworld domain with sparse rewards, and then show that our method scales up to more complex settings by evaluating on the VizDoom (Kempka et al., 2016) platform.
INTRODUCTION
Recent work in deep reinforcement learning effectively tackles challenging problems including the board game Go (Silver et al. 20166), Atari vidco games (Mnih et al., 2015), and simulated robotic continuous control (Lillicrap et al. 2016); however, these successful approaches often rely on fre- quent feedback indicating whether the learning agent performing well, otherwise known as dense rewards. In many tasks, dense rewards can be difficult specify without inducing locally optimal but globally sub-optimal behavior. As such, it is frequently desirable to specify only a sparse reward that simply signals whether agent has attained success failure on given task. Despite their desirability, sparse rewards introduce their own set of challenges.
When rewards are sparse, determining which of an agent's actions led to a reward becomes more difficult, a phenomenon known in reinforcement learning as the credit-assignment problem. Further- more, if rewards cannot be obtained by random actions, an agent will never receive signal through which it can begin learning. As such, researchers have devised methods which attempt to provide agents with additional reward signals, known as intrinsic rewards, through which they can learn meaningful behavior (Oudeyer & Kaplan 2009). A large subset of these works focus on learning intrinsic rewards that encourage exploration of the state space (Pathak al. 2017: Houthooft al., 2016 Burda et al. 2019 Ostrovski et al. 2017 Tang et al. (017).
Exploring the state space provides a useful inductive bias for many sparse reward problems where the challenge lies in "finding" rewards that may only be obtained in parts of the state space that are hard to reach by random exploration. These poploratioo-focussee approaches frequently formulate their intrinsic rewards to measure the "novelty" of state, such that agents are rewarded for taking actions that lead to novel states. Our work approaches the question of how to apply novelty-based intrinsic motivation in the cooperative multi-agent setting.

---

Under review as a conference paper at ICLR 2020
Directly applying -ovee intrinsic motivation the multi-agent setting results in agents each exploring their shared state space independently from one another. In many cases, independent exploration may not be the most efficient method. For example, consider task where multiple agents are placed in a maze and their goal is to collectively reach all of the landmarks that are spread out through the maze. It would be inefficient for the agents to explore the same areas redundantly. or avoid redundant
Instead, it would be much more sensible for agents to dividd-anddconquee exploration. Thus, an ideal intrinsic reward for this task would encourage such behavior; however, the same behavior would not be ideal for other tasks. For example, take the same maze but change the task such that all agents need to reach the same landmark. divide-and-conquer would no longer be an optimal exploration strategy since agents only need to find one landmark and they all need to reach the same one. Cooperative multi-agent reinforcement learning can benefit from sharing information about exploration across agents; however, the question of what to do with that shared information depends on the task at hand.
In order to improve exploration in cooperative multi-agent reinforcement learning, we must first identify what kinds inductive biases can potentially be useful for multi-agent tasks and then devise intrinsic reward functions that incorporate those biases. Then, must find way to allow our agents to adapt their exploration to the given task, rather than committing to one type of intrinsic reward function. In this work, we first introduce candidate of intrinsic rewards for multi- agent exploration which hold differing properties with regards to how they explore the state space. Subsequently, we present a hierarchical method for simultancously learning policies trained on dif- ferent intrinsic rewards and selecting the policies which maximize extrinsic returns. Importantly, all policies are trained using shared replay buffer, drastically improving the sample efficiency and effectiveness of learning in cooperative multi-agen aggett tasks with sparse rewards.
2 RELATED WORK
Single-Agent Exploration In order to solve sparse reward problems, researchers have long worked on improving exploration in reinforcement learning. To achieve these means, prior works commonly propose reward bonuses that encourage agents to reach novel states, In tabular domains, reward bonuses based on the inverse state-action count have been shown to be effective in speeding up learning (Strehl& & Littman 2008). In order to scale count- count-based approaches to large state spaces, many recent works have focused on devising pseudo state counts use as reward bonuses (Belle- mare et 2016 Ostrovski et al. 2017 Tang et al., 2017). Alternatively, some work has focused on defining intrinsic rewards for exploration based on inspiration from psychology (Oudeyer Kaplan 2009 [Schmidhuber] 2010)). These works use various measures of novelty as intrinsic rewards in- cluding: transition dynamics prediction error (Pathak et al. 2017), information gain with respect to a learned dynamics model (Houthoofi et al. 2016). and random state embedding network distillation error (Burda et al.) 2019).
Multi-Agent Reinforcement Learning (MARL) Multi-agent reinforcement learning introduces several unique challenges that recent work has attempted to address. These challenges include: multi-agent credit assignment in cooperative tasks with shared rewards (Sunchag et al.) 2018 Rashid et al. 2018 Foerster et al., (2018), non-stationarity of the environment the presence other learn- ing agents (Lowe et al. [011]] Foerster et al. 20188] Iqbal & Sha, 2019), and learning of communi-
cation protocols between cooperative agents [Forster et al. 2016 Sukhbaatar et al. 2016 Jiang &
Lu 2018).
Exploration in MARL While the fields of exploration in RL multi-agent RL are popular, rel-
atively little work has been done at the intersection of both. Carmel & Markovitch (1997) consider
exploration with respect to opponent strategies in competitive games, and Verbeeck et al. (2005)
consider exploration of a large joint action space in a load balancing problem. jaaues et al. (2018)
define an intrinsic reward function for multi-agent reinforcement learning that encourages agents to take actions which have the biggest effect on other agents' behavior, otherwise referred to as "social influence." " Agogino & Tumer (2008) Define metries for evaluating the efficacy of reward functions in multi-agent domains. These works, while important, do not address the problem of exploring large state space. and whether this exploration can be improved in multi-agent systems. A recent approach to collaborative evolutionary reinforcement learning (Khadka al. 2019) shares some similarities with our approach. As in our work, the authors devise a method for learning a pop- ulation of diverse policies with shared replay buffer and dynamically selecting the best leamer;
2

---

Under review as a conference paper at ICLR 2020
however, their work is focused on single-agent tasks and does not incorporate any notion of intrinsic rewards. As such, this work is not applicable to sparse reward problems in MARL.
BACKGROUND
Dec-POMDP's In this work, consider the setting of decentralized POMDPs (Oliehoek al. 2016), which are used to describe cooperative multi-agent tasks. A decentralized POMDP (Dec- POMDP) defined by tuple: (S, 7, O, O, R, n, In this setting we have n total agents. is the set of global states in the environment, while O &ie (I...) O; is the set of joint observations for each agent and A (I.()....) A, the of possible joint actions for each agent. specific joint action one time step is denoted as a {ai..... an. A and a joint observation for....,0%) E O. T' is the state transition function which defines the probability P(s'|s, a),, and O the observation function which defines the probability Pooja, s'). R the reward function which maps the combination of state and joint actions to single scalar reward. Importantly, this reward shared between all agents, so RecDPSSDPs always describe cooperative problems. Finally, ? is the discount factor which determines how much the agents should favor immediate reward over long-term gain.
Soft Actor-Critic Our approach uses Soft Actor-Critic (SAC) (Haarnoja et al. 2018) as its under- lying algorithm. SAC incorporates entropy term in the loss functions for both the actor and critic, in order to encourage exploration and prevent premature convergence to a sub-optimal deterministic policy. The policy gradient with an entropy term is computed follows:
V VoJ( = D, Ve log (o((s)) (- log No (als))
+ (Q)(s,a) b(s)
(1)
where D is replay buffer that stores past environment transitions, v are the parameters of the learned critic, b(s) is a state dependent baseline (e.g. the state value function V(s)), and is a reward scale parameter determining the amount of entropy in optimal policy. The critic is learned with the following loss function:
(Q( = E [[Qp a) --
(2)
r(s,a) + (lg' Qu(o',a)) (a'(s((d'ls)))
(3)
where y are the parameters the target critic which an exponential moving average of the past critics, updated as: ub <- (1 7) + Tv/ and is hyperparameter that controls the update rate.
Centralized Training with Decentralized Execution A number of works in deep multi-agent reinforcement learning have followed the paradigm of centralized training with decentralized exe- cution (Lowe et al. 2017 Foerster et al. 2018 Sunehag al. [0188] Rashid et al. 2018 Igbal & Sha 2019). This paradigm allows for agents to train while sharing information (or incorporating information that is unavailable at test time) but act using only local information, without requiring communication which may be costly at execution time. Since most reinforcement learning appli- cations use simulation for training, communication between agents during the training phase has relatively lower cost.
INTRINSIC REWARD FUNCTIONS FOR MULTI-AGENT EXPLORATION
In this section we present set of intrinsic reward functions for exploration that incorporate infor- mation about what other agents have explored. These rewards assume that each agent (indexed by has a novelty function fi that determines how novel an observation is to it, based on its past expe- rience. This function can be an inverse state visit count in discrete domains, or, in large/continuous domains, it can represented by recent approaches for developing novelty- based intrinsic rewards in complex domains, such as random network distillation (Burda et al. 2019). Note that we assume that all agents share the same observation space so that each agent's 's novelty function can operate on all other agents' observations.
3

---

Under review as a conference paper at ICLR 2020
Table I: Multi-agent intrinsic rewards for agent i, with ulo;) 1.2 Σ, f5(0:)
INDEPENDENT
MINIMUM
COVERING
BURROWING
LEADER-POLLOWER
S(o)) (o,)) ((())) p(o:)] [i(o)) (f((,)) < plo.)]
See text
JE JE(...))
In Table 1 we define the intrinsic rewards that we use in our experiments. INDEPENDENT rewards are analagous to single-agent approaches to exploration which define the intrinsic reward for an agent as the novelty of their new and own observation that occurs as result of an action. The remainder of intrinsic reward functions that we consider use the novelty functions of other agents, in addition their own, further inform their exploration.
MINIMUM rewards consider how novel all agents find a specific agent's observation and rewards that agent based on the minimum of these novelties. This method leads to agents only being rewarded for exploring areas that no other agent has explored, which could be advantageous in scenarios where redundancy exploration not useful or even harmful. COVERING rewards agents for exploring areas that it considers more novel than the average agent. This reward results in agents shifting around the state space, only exploring regions as long as they are more novel to them than their average teammate. BURROWING rewards do the opposite, only rewarding agents for exploring areas that it considers less novel than the average agent. While seemingly counterintuitive, these rewards encourage agents to further explore areas they have already explored with the hope that they will discover new regions that few or no other agents have seen, which they will then consider less novel than average and continue explore. As such, these rewards result in agents continuing to explore until they exhaust all possible intrinsic rewards from a given region (i.e. hit dead end), somewhat akin depth-first search. LEADER-FOLLOOWE uses burrowing rewards for the first agent, and covering rewards for the rest of the agents. This leads to an agent exploring a space thoroughly, and the rest of the agents following along and trying to cover that space.
Note that these are not meant to be a comprehensive set of intrinsic reward functions applicable to all cooperative multi-agent tasks but rather set of examples of how exploration can be centralized in order to take other agents into account. Our approach, described in the following sections, is agnostic to the type of intrinsic rewards used and, as such, can incorporate other reward types not described here, as long as they can be computed off off-pylicy.
5 LEARNING POLICIES FOR MULTI-AGENT EXPLORATION
For many tasks, it is impossible to know a priori which intrinsic rewards will be the most helpful one. Furthermore, the type of reward that is most helpful could change over the course of training the task is sufficiently complex. In this section we present our approach for simultaneously learning policies trained with different types of intrinsic rewards and dynamically selecting the best one.
Simultaneous Policy Learning In order to learn policies for various types of intrinsic rewards in parallel, we utilize a shared replay buffer and off-policy learning to maximize sample efficiency. In other words, we learn policies and value functions for all intrinsic reward types from all collected data, regardless of which policies it was collected by. This parallel learning is made possible by the fact that we can compute our novelty functions off- off-policy, given the observations for each agent after each environment transition, which are saved in a replay buffer. For each type of reward, we learn a different "head" for our policies and critics. In other words, we learn a single network for each agent's ' set of policies that shares early layers and branches out into different heads for each reward type. For critics, we learn single network across all agents that shares early layers and branches out into separate heads for each agent and reward type. We learn separate heads for intrinsic and extrinsic rewards, as in Burda al. (2019). We provide diagram of our model architecture in Figure [
We index agents by E {1...n) n and intrinsic reward types by j E {1 (1...m) m. where is the total number of intrinsic reward types that we are considering. The policy for agent i, trained using reward j (in addition to extrinsic rewards), is represented by T/. It takes as input agent i's observation, o,, and outputs distribution from which we can sample the action 0z. The parameters of this policy
4

---

Under review as a conference paper at ICLR 2020
Q (s, a)
Qiyy (s,
ग. (as los)
i E {l................. f1...17 n E [l...m}
0²
i.j
sashare
a
Oshare
shared across agents and reward types
shared across reward types
S
O
specific to each agent and reward combination
Critics
Policies
Diagram of model architecture, showing how parameters for actors and critics shared. i indexes agents, while indexes reward types.
Figure 1:
O (Orhare 02) where Ophore shared base/input (for agent i) in a neural network and of is a head/output specific to this reward type.
The extrinsic critic for policy head कद is represented by Q It takes as input the global state and the actions of all other agents a,,, and outputs the expected returns under policy Tद for each possible action that agent can take, given all other agents' actions. The parameters of this critic are V = Suhru v where whhare a shared base across all agents and reward types. critic with similar structure exists for predicting the intrinsic returns of actions taken by n/ represented by Q which uses the parameters: T (uhshure v }. Note that the intrinsic crities share the same base parameters sharee
We remove the symbols representing the parameters of the policies (0) and the crities (V) for read- ability. our notation we use the absence of subscript or superscript to refer to a group. For example n², refers to all agents' policies trained on intrinsic reward j. We train our critics with the following loss function, adapted from soft actor-critic:
m n
VV E(s.o.ans'
ΣΣ
(8, - vi (Q") a)) v.t.." )2
(4)
log न (a)lo())
36. , (s, t
(s',
(5)
a
(s',aa) log(T (aflo))
v (o)) + =
where refers to the target Q-function, an exponential weighted average of the past Q-functions, used for stability, and it are similarly updated target policies. The intrinsic rewards laid out in Table are represented as a function of the observations that results from the action taken, in (of) where specifies the type of reward. Importantly, intrinsic and extrinsic returns for all policies given a single environment transition, allowing us to learn multiple policies for each agent in parallel. We train each policy head with the following
calculate these loss functions for expected
5

---

Under review as a conference paper at ICLR 2020
gradient:
log A2
V ((T)) D.s.))-D.amm
oi log n. (a,los))
a
(8, a) (8, BQ (8, - (s)
(s( E T(d(lo)) fa/. ax)) + SQT (s. a.)))
EAA
where 8 is scalar that determines the weight of the intrinsic rewards, relative extrinsic rewards, and A is multi-agent advantage function (Foerster al. 2018 Iqbal helping with multi-agent credit assignment.
Sha 2019), used for
Dynamic Policy Selection Now that we have established a method for simultaneously learning policies using different intrinsic reward types, must devise means of selecting between these policies. In order to select policies to use for environment rollouts, we must consider which policies maximize extrinsic returns, while taking into account the fact that there may still be "unknown un- knowns," or regions that the agents have not seen yet where they may be able to further increase their extrinsic returns. As such, we must learn aneea-policy that, the beginning of each episode, selects between the different sets of policies trained on different intrinsic rewards and maximizes extrinsic returns without collapsing to a single set of policies too early. We parameterized the selector policy II with vector, 6. that contains an entry for every reward type. The probability of sampling head j is: IT()) x exp(@li)) Unlike the action policies, this high-level policy does not take any inputs, simply want to learn which set of policies trained on the individual intrinsic reward functions has the highest expected extrinsic returns from the beginning of the episode.
The most sensible metric for selecting policies is the expected extrinsic returns given by each policy head. We can use policy gradients to train the policy selector, II, to maximize this value using the returns received when performing rollouts in the environment. We use the following gradient train II:
(- log II)h)
VII = EA-I
V [og
R
bn
(10)
1]
m
(1 (o))
bn Σ
11(h))m
(11)
where H4, is running mean of the returns received by head h in the past, and 17 a parameter similar to for the low-level policies, which promotes entropy in the selector policy. Entropy in the policy selector is important order to prevent it from collapsing onto a single exploration type that does well at first but does not continue to explore as effectively as others. As such, diverse set behaviors based on various multi-agent intrinsic reward functions and select the one that maximizes performance the task hand at any point during training, while continuing to consider other policies that may lead to greater rewards.
learn
6 EXPERIMENTS
We begin by describing our evaluation domains and then present experimental results which demon- strate the effectiveness our approach. We provide additional details in the appendix and will share code for both the model and environments.
We use a maximum of four agents in gridworld and two agents VizDoom. We encode several tasks in both domains related to collecting the items (displayed in yellow in Figure 2 which each require different types of exploration: TASK Agents must cooperatively collect all treasure on the map in order to complete the task; TASK 2 Agents must all collect the same treasure. The first agent to collect a treasure during an episode determines the goal for the rest of the agents. TASK 3 Agents must all collect the specific treasure that is assigned to them. The two agent version of each task uses agents 1-2 and treasure A-B, while the three agent versions use 1-3, A-C, and the four agent versions use 1-4, A-D. Agents receive negative time penalty towards extrinsic rewards

---

Under review as a conference paper at ICLR 2020
(a)
(b)
(c)
Figure 2: (Left) Rendering of our gridworld domain. Agents start each episode in the central room and complete various tasks related to collecting the yellow treasures placed around the map. (Center) Top- Top-Down view of VizDoom "My Way Home" map, modified for multi-agent experiments (Right) Egocentric view in VizDoom used for agents' observations
at each step, so they are motivated to complete the task as quickly as possible. The only positive extrinsic reward comes from any agent collecting treasure that is allowed by the specific task, and rewards are shared between all agents. The optimal strategy in TASK is for agents to spread out and explore separate portions of the map, while in TASK 2 they should explore the same areas, and in TASK 3 they should explore independently.
6.1 GRIDWORLD DOMAIN
We first test our approach using a multi-agent gridworld domain (pictured in Fig. 2a which allows us to design environments where the primary challenge lies in combination of exploring the state space efficiently and coordinating behaviors.
The environment includes two sources of stochasticity: random transitions and black holes. At each step there is 10% chance of an agent's action being replaced by random one. Furthermore, there several "black holes" placed around the map which have a probability of opening at each time step. This probability changes at each step using a biased random walk such that moves toward one, until the hole opens and it resets will be sent back to their starting position. The spaces colored as black are holes that are currently open, while the gray spaces holes that have the possibility of opening the next step (the darker they are, the higher the probability). We set the rate of black holes dropping out to be higher in TASK 1 than the other 2 tasks, in order to balance the difficulty.
If an agent steps into black hole when it is open, they
The novelty function for each agent ft. which is used for calculating the intrinsic rewards in Table defined as NT. where N is the number of times that the agent has visited its current cell and is a decay rate selected as a hyperparameter (we find that ( 0.7 works well for our purposes).
6.2 VIZDOOM DOMAIN
In order to test our method's ability to scale to more complex environments with similarly chal- lenging exploration tasks, we implement tasks analogous to those in our gridworld environment (i.e. extrinsic rewards are defined identically) in the VizDoom framework (Kempka et al., 2016). We the "My Way Home" map, which has been used as a test bed for single agent exploration tech- niques (Pathak et al. 2017), and modify it for multi-agent tasks (pictured in Figure 2 Since the agents moved to central location closer to their rewards than in the original map, lower the action repeat from to 2, in order to force agents to take twice as many steps in order to explore the same areas, maintaining the challenging nature of exploration in the original task.
As in the gridworld setting, we use count-based intrinsic rewards for VizDoom; however, since VizDoom is a discrete domain, we separate agents' (xr, y) positions into discrete bins and use the counts for these bins. We again find that Ç 0.7 to work well in our experiments.

---

Under review as a conference paper at ICLR 2020
2.00
200
Variat
1.75
1.75
Multi
indegendet
Mon Texains Found
Varianz
Mean Tressre Foued
Poliy)
3.25
Multi
1.15
Muhi (Al Indepandent]
indeeenden
Contral
1.00
(No Entrepp)
Covoiing
Burrosiig
0.75
0.50
Loaden
0.50
0.23
Step
Figure 3: (Left) Mean number of trasures found per episode on TASK with 2 agents in the gridworld domain. Shaded region is 68% confidence interval across 6 runs of the running mean over the past 100 episodes. Our approach PEIITT--XPPOAAAAEE same number of environment samples without any prior knowledge provided. (Right) Ablations of our model in the same setting. We show that both aspects of our approach (the meta-policy selector and the diverse intrinsic reward functions) are crucial for successful completion of exploration tasks requiring coordination.
is competitive with the hest individual intrinsic reward function, using the
6.3 MAIN RESULTS
Figure 3a demonstrates the results of our approach over the course of training on the 2 agent version of TASK in gridworld, and the final results on each task/agent/domain combination can be found in Table The full training curves for all settings can be found in the appendix (Section A.44. We train a team of agents using each of the multi-agent intrinsic reward functions defined in Table [] individually, and then test our dynamic policy selection approach. We find that our approach is competitive with, or outperforms the best performing individual exploration method in nearly all tasks. This performance is exciting since our method receives no prior information about which type of exploration would work best, while each type carries its own inductive bias. Notably our learned policy selector learns to select the policies trained on intrinsic rewards that do well individually on the tasks. For instance, on TASK 1 with agents, we find that our policy selector consistently selects BURROWING and MINIMUM rewards, the two best performing reward functions that task. Furthermore, we find that our results on the more complex VizDoom domain mirror those in the gridworld, indicating that our methods are not limited to discrete domains, assuming that reliable way for measuring the novelty of observations exists.
Interestingly, our approach is sometimes able significantly surpass the performance of the best individual reward function on TASK 3. This task requires agents to collect the specific reward as- signed to them, so expect independent exploration be the most effective; however, exploration types that perform "divide-and aanide--addcouuuuer" type behavior such as BURROWING and MINIMUM have the potential to drastically speed up the exploration process they happen divide the space cor- rectly, leading to a stark success-failure contrast in runs of these types. Since our method MULTI can select policies trained on these rewards, and otherwise fall back on INDEPENDENT policies they are not working, find that our method is able to surpass all individual reward types.
We find that our approach unable to match the performance of the best individual method on TASK 2 in some settings (gridworld with 3 agents and VizDoom). This lack of success may be an indication that these particular settings require commitment to specific exploration strategy early in training. highlighting limitation of our approach. Our method requires testing out all policies until we find one that reaches high extrinsic rewards, which can dilute the effectiveness of exploration early on.
6.4 ANALYSIS
Characteristics of Different Intrinsic Rewards In order to better understand how each reward type encourages agents to explore the state space, we visualize their exploration in videos, viewable InDepeNDent rewards, expected, result in agents exploring the whole state space without taking other agents into consideration. As a result, on TASK 1, which
at the anonymized link below |
8

---

Under review as a conference paper at ICLR 2020
Table of treasures found with standard deviation across 6 runs. Scores where the best mean score falls within one standard deviation of the score distribution are bolded.
GRIDWORLD
Intrinsic reward type (fixed or adaptive as in our approach MULTI)
Task
INDEPENDENT
MINIMUM
COVERING
BURROWING
FLAD-FOLLOW
MULTI
2
0.14 + 0.05
1.62 = 0.59
0,13 + 0.12
1.98 + 0.06
0,18 + 0.24
2.00 + 0.00
1,16 + 0.11
1.49 - 0.76
0.00 + 0.00
2.06 1.05
0.34 + 0.45
2.23 = 0.73
0.84 + 0.29
1.78 0.44
0.00 0.00
1.90 0.49
1.17 + 0.39
2.04 = 0.61
2
2.00 1 0.00
0.92 0.10
1.11 + 0.99
0.98 0.05
1.73 + 0.66
1.83 1 0.41
2.66 0.80
1.11
0.54 0.80
1.80 0.29
3,00 0.00
1.80 1 0.71
1.83 + 1.08
0,93 = 0.13
0.22 0.18
1.99 + 0.67
2.66 + 2.06
2.54 - 1.21
3
1.39
0.94
0.67 +
0.29 + 0.37
0.67
1.03
0.83
0.67
2.00 + 0.00
1.68 + 0.70
0.60 + 0.73
0.09 + 0.08
1.35 1.16
1.59 + 0.83
2.21 + 0.91
4
1.12 + 0.47
1.36 = 0.71
0,05 + 0.05
2.14 + 1.49
0.68 + 0.53
1.73 = 0.47
VIzDooM
0.94 0.54
1.57 + 0.74
0.16 + 0.17
1.94 0.10
0.61 + 0.43
1.98 + 0.03
2
1.52 + 0.75
1.53 + 0.74
0.70 + 1.00
0.63 + 0.04
1.93 + 0.10
1.23 + 0.65
3
0.18 + 0.19
0.64 + 1.05
0.45 + 0.46
0.29 + 0.25
0.20 + 0.17
1.64 + 0.63
requires coordination between agents to spread out and explore different areas, INDEPENDENT wards struggle; however, on TASK 3, where agents receive individualized goals, independent explo- ration usually performs better, relative the other methods. TASK also requires coordination, but the rate of black holes dropping out in the gridworld version is lower on that task, making explo- ration easier. As a result, INDEPENDENT rewards perform well on TASK 2; however, we find that LEADER-FOULD FOLLOWER also performs well on this task, expecially when more agents are involved, indicating that these rewards good job of biasing agents toward exploring similar regions of the environment.
MIMIMUM rewards prevent agents from exploring the same regions redundantly but can lead to situations where one of the agents is the first to explore all regions that provide sparse extrinsic rewards. these cases, other agents are not aware of the extrinsic rewards and are also not motivated to explore for them since another agent has already done so. COVERING rewards, as expected, lead to behavior where agents are constantly switching up the regions that they explore. While this behavior does not prove to be useful in the tasks we test since the switching slows down overall exploration progress, it may be useful in scenarios where agents are required to spread out. Finally, BURROWING rewards cause agents each explore different subregions and continue to explore those regions until they exhaust their options. This behavior is particularly effective on TASK 1, where agents are best served by spreading out and exploring the whole map in mutually exclusive fashion.
Ablations We compare a baseline meta-policy which simply selects the action policies uni- formly at random. We find that our approach is significantly superior to this baseline (see Figure 33b Multi (Uniform Meta- Pelaa-o..cyy). Furthermore, we test version of our method where all policies (with different random initializations) are trained on independent rewards (Multi (All Independent)), The purpose of this ablation is test the degree which the specific multi-agent intrinsic reward functions are helpful, opposed to simply providing multiple options at each episode. Again, we find that our method outperforms the baseline, indicating that both aspects of our approach (diverse intrinsic reward functions which share information across agents, and a meta-policy selector that maximizes extrinsic rewards) are crucial for success multi-agent exploration tasks.
We perform two further ablations/compparsons.. Results on task with 2 agents in GridWorld are viewable in Figure 3b] and results on tasks and 3 with 2 agents are viewable in the Appendix (..5). In the first (Centralized) we compute intrinsic rewards under the assumption that all agents are treated as one agent. In other words, we use the inverse count the number of times that all agents have jointly taken up their combined positions, rather than considering agents independently. While this reward function will ensure that the global state space is thoroughly searched, lacks the inductive biases toward spatial coordination that reward functions incorporate. As such, it does

---

Under review as a conference paper at ICLR 2020
not learn efficiently as method. In the second (Multi (No Entropy)) we remove the entropy term from the head selector loss function in order to test its importance. We find that this ablation is unable to match the performance of the full method, indicating that entropy is crucial in making sure that our method does not converge early to a suboptimal policy selector.
CONCLUSION
We propose set of multi-agent intrinsic reward functions with differing properties, and compare them both qualitatively (through videos) and quantitatively on several multi-agent exploration tasks in both a gridworld domain as well as in VizDoom. Overall, we can see that cooperative multi-agent tasks can, in many cases, benefit from intrinsic rewards that take into account what other agents have explored, but there are various ways to incorporate that information, each with differing properties. As such, we propose a method for learning policies for all intrinsic reward types simultaneously while dynamically selecting the most effective ones. We show that our method is capable of match- ing or surpassing the performance of the best performing intrinsic reward type on various tasks while using the same number of samples collected from the environment. In future work hope to intro- duce methods for directly learning the multi-agent intrinsic reward functions, rather than selecting from set.
REFERENCES
Adrian K Agogino and Kagan Tumer. Analyzing and visualizing multiagent rewards in dynamic and stochastic domains. Autonomous Agents and Multi-Agent Systems, 17(2):200-338 2008
Mare Bellemare, Sriram Srinivasan, Georg Ostrovski, Tom Schaul, David Saxton, and Remi Munos. Unifying count-based exploration and intrinsic motivation. In Advances in Neural Information Processing Systems, pp. 1471-1479, 2016.
Yuri Burda, Harrison Edwards, Amos Storkey, and Oleg Klimov. Exploration by random network distillation. In International Conference Learning Representations, 2019. URL https: d= d= 1JJnR5
//openrevi ew.
David Carmel and Shaul Markovitch. Exploration and adaptation in multiagent systems: A model- based approach. In ISCA/ (1), pp. 606-611, 1997.
Jakob Foerster, Ioannis Alexandros Assael, Nando de Freitas, and Shimon Whiteson. Learning to communicate with deep multi-agent reinforcement learning, In Advances in Neural Information Processing Systems, pp. 2137-2145, 2016.
Jakob Foerster, Gregory Farquhar, Triantafyllos Afouras, Nantas Nardelli, and Shimon Whiteson. Counterfactual multi-agent policy gradients. In AAAI Conference on Artificial Intelligence, 2018.
Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor. In Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research. pp. 1861-1870, Stockholmsmssan, Stockholm Sweden, 10-15 Jul 2018.
Rein Houthooft, Xi Chen, Yan Duan, John Schulman, Filip De Turck, and Pieter Abbeel. Vime: Variational information maximizing exploration. In Advances in Neural Information Processing Systems, pp. 1109-1117, 2016.
Shariq Iqbal and Fei Sha. actor-attention-critic for multi-agent reinforcement learning. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 2961-2970, Long Beach, California, USA. 09-15 Jun 2019. PMLR. URL http:tttt///ccceet//// press/v97/iqpal/
mlr.
html
Natasha Jaques, Angeliki Lazaridou, Edward Hughes, Caglar Gulcehre, Pedro A Ortega, D Strouse, Joel Z. Leibo, and Nando de Freitas. Social influence as intrinsic motivation for Multi- Agent deep reinforcement learning, arXiv preprint 0rXiv:1810.08644 October 2018.
Jiechuan Jiang and Zongqing Lu. Learning attentional communication for multi-agent cooperation.
arXiv preprint arXiv: arXiv:1805.007 180500733, 2018.
10

---

Under review as a conference paper at ICLR 2020
Michat Kempka, Marek Wydmuch, Grzegorz Runc, Jakub Toczek, and Wojciech Jaskowski. ViZ- Doom: A Doom-based AI research platform for visual reinforcement learning. In IEEE Confer- on Computational Intelligence and Games, pp. 341-348, Santorini, Greece, Sep 2016. IEEE. URL wwwphhttt///iwii.ppot
abs/ 605. 02097 The best paper award.
Shauharda Khadka, Somdeb Majumdar, Santiago Miret, Evren Tumer, Tarek Nassar, Zach Dwiel, Yinyin Liu, and Kagan Tumer. Collaborative evolutionary reinforcement learning. arXiv preprint arXiv: hwtp:9905.09900 00976, 2019.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In International Conference on Learning Representations, 2014.
Timothy P Lillicrap, Jonathan Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra. Continuous control with deep reinforcement learning. In Inter- national Conference on Learning Representations, 2016.
Ryan Lowe, Yi Wu, Aviv Tamar, Jean Harb, OpenAl Pieter Abbeel, and Igor Mordatch. Multi-agent actor-critic for mixed cooperative-compettivv environments. Advances in Neural Information Processing Systems, pp. 6382-6393, 2017.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Mare Belle- mare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning. Nature, 518(7540):59,, 2015.
Frans A Olichoek, Christopher Amato, al. A concise introduction to decentralized POMDPs, volume 1. Springer, 2016.
Georg Ostrovski, Marc Bellemare, Aäron van den Oord, and Rémi Munos. Count-based ex- ploration with neural density models. In Proceedings of the 34th International Conference Machine Learning-Volle Volume 70, pp. 2721-2730. JMLR. org, 2017.
Pierre-Y Yves Oudeyer and Frederie Kaplan. What is intrinsic motivation? typology of computa- tional approaches. Frontiers in neurorobotics, 1:6, 2009,
Deepak Pathak, Pulkit Agrawal, Alexei A. Efros, and Trevor Darrell. Curiosity- -rivenn exploration by self-supervised prediction. In Doina Precup and Yee Whye Teh (eds.), Proceedings of the 34th International Conference on Machine Learning, volume Research, pp. 2778-2787, International Convention Centre, Sydney, Australia, 06-11 Aug 2017. PMLR. [RRptttpp//prooeeeee
Proceedings of Machine Learning
mlr www...pee///7///aaaa..... attmml...mmmmlll
Tabish Rashid, Mikayel Samvelyan, Christian Schroeder, Gregory Farquhar, Jakob Foerster, and Shimon Whiteson. QMIX: Monotonic value function factorisation for deep multi-agent rein- forcement learning. In Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 4295-4304, Stockholmsmssan, Stockholm Sweden, 10-15 Jul 2018.
Jürgen Schmidhuber. Formal theory of creativity, fun, and intrinsic motivation (1990-2010). IEEE Transactions on Autonomous Mental Development, 2(3): 2010.
David Silver, Aja Huang, Chris Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, loannis Antonoglou, Veda Panneershelvam, Mare Lanctot, et al. Mastering the game of go with deep neural networks and tree search. Nature, 529(7587):484-448) 2016.
Alexander L. Strehl and Michael L. Littman. An analysis of model-based interval estimation for markov decision processes. Journal of Computer and System Sciences, 74(8):1309 1331, doi: https///ooiorg/1100111//./....s www. sc www.cceenceeo www.eciiiiiccc.cccc rect. com/ http://cwneeerrcc.ee////////0000 ing Theory 2005.
2008. ISSN 0022-0000.
009. URL http://
Learn-
Sainbayar Sukhbaatar, Rob Fergus, et al. Learning multiagent communication with backpropaga- tion. In Advances Neural Information Processing Systems, pp. 2244-2252, 2016.

---

Under review as a conference paper at ICLR 2020
Peter Sunehag, Guy Lever, Audrumas Gruslys, Wojciech Marian Czarnecki, Vinicius Zambaldi, Max Jaderberg, Mare Lanctot, Nicolas Sonnerat, Joel Z. Leibo, Karl Tuyls, and Thore Graepel. Value- decomposition networks for cooperative multi-agent learning based on team reward. In Proceed- ings of the 17th International Conference on Autonomous Agents and guliiAgent Systems, AA- MAS 18, pp. 2085-2087, Richland, SC, 2018. International Foundation for Autonomous Agents and Multiagent Systems.
Haoran Tang, Rein Houthooft, Davis Foote, Adam Stooke, OpenAl Chen, Yan Duan, John Schul- man, Filip DeTurck, and Pieter Abbeel. # exploration: A study of count-based exploration for deep reinforcement learning. In Advances in neural information processing systems, pp. 2753- 2762, 2017.
Katja Verbeeck, Ann Nowé, and Karl Tuyls. Coordinated exploration in multi-agent reinforcement learning: application to load-balancing. In Proceedings of the fourth international joint con- ference on Autonomous agents and multiagent systems, pp. 1 1105-1106. ACM, 2005.
A APPENDIX
A.1 ENVIRONMENT DETAILS
A.1.1 GRIDWORLD
The black holes which send agents back to their starting positions if they stepped into an important aspect of the environment, as they add difficulty to exploration. The probability, p. of black hole opening at each step, evolves as such: Pr+1 Ps + (N,, where μ 0.05 for TASK 1 and / a 0.005 for 2 and 3.
Agents observe their global position in (x. coordinates (scalars), well as local information regarding walls in adjacent spaces, the probability of their adjacent spaces opening into black hole, the relative position other agents (if they are within 3 spaces), as well as information about which treasures the agent has already collected in the given episode. The global state is represented by the (xr, v) coordinates of all agents, as one-hot encoded vectors for x and y separately, as well as the local information of all agents regarding black holes, walls, and treasures collected. Each agent's action space consists of the cardinal directions as well as an option to not move, which is helpful in cases where agent is waiting for black hole to be safe cross.
A.1.2 VIZDOOM
Agents receive their egocentric view (Figure 2c) in the form of 48x48 grayscale images as obser- vations along with an indicator of which agents (if any) have collected each reward, and we use vector based global state which includes all agents' (x, y) positions and velocities, their orientations, as well as the same indicator of which agent has collected each reward. As in the gridworld setting, we use count-based intrinsic rewards for VizDoom; however, since VizDoom is not discrete do- main, we separate agents' (x. y) positions into discrete bins and use the counts for these bins. There are 30 bins in the x dimension and 26 in the y dimension. (æ,, y) positions in the global state rep- resented both as scalars and one-hot vectors indicating which bin the agents are currently occupying. Each agent can choose from 3 actions at each time step: turn left, turn right, go forward.
A.2 TRAINING DETAILS
The training procedure is detailed in Algorithm | and all hyperparameters are listed in Tables 3 and Hyperparameters were selected by tuning one parameter at time through intuition on task with agents and then applying to the rest of the settings with minimal changes. Where hyperparameters differ between settings, make footnote denoting them as such.
12

---

Under review as a conference paper at ICLR 2020
Algorithm Training Procedure for Multi-Explore w/ Soft Actor-Critic (Haarnoja et al. 2018)
1: Initialize environment with agents
2: Initialize replay buffer,
3: fupdate <- 0
4: tep f- max cp length
5: for = 1... total steps do
6: if' episode done or tep == max ep length then
7: for j 1.... num updates do
8:
UPDATESELECTOR(R h)
Eqs 10-11 11-11 in main text
9:
end for
10:
8,0 f- RESETENV
h~ll II
Sample policy head
12:
tep + R 5
14:
end if
Select actions a, nH (-lo,) for each agent,
16:
Send actions to environment and get O,
17:
R R+ 7/1 r
18:
Store transitions for all environments in D
19:
fupdate +
20:
lep
21:
if
(update = steps per update then
for j 1... num updates do
23:
Sample minibatch, B (PDATECRITIC(L) UPDATEPOLICIES(B) Update target parameters:
24:
Eqs 4-6 in main text
25:
Eqs 7-9 in main text
V = T)
θ = 7 (1-
27:
end for
Tupdate
29:
end if
30:
end for
13

---

Under review as a conference paper at ICLR 2020
Table Hyperparameter settings across all runs in gridworld.
Name
Description
Value
Q
learning rate for centralized critic
0.001
Q optimizer
optimizer for centralized critic
Adam (Kingma & Ba 2014)
r Ir
learning rate for decentralized policies optimizer for decentralized policies learning rate for policy selector optimizer for policy selector target function update rate batch size
0.001
optimizer
Adam
Ir
0.04
II optimizer
SGD
r
0.005
bs
1024
total steps
number of total environment steps
le6
steps per update
number of environment steps between updates
100
niters
number of iterations per update maximum length of an episode before resetting
50
max ep length
500
coefficient for weight decay
V penalty
0.001
parameters of Q-function
coefficient L2 penalty on pre-softmax
+ penalty
0.001
output of policies
coefficient for weight decay
8 penalty
0,001
parameters of policy selector
|D]
maximum size of replay buffer
1e6
a
action policy reward scale selector policy reward scale discount factor
100
5
0.99
8
relative weight of intrisic rewards to extrinsic decay rate of count-based rewards
0.1
0.7
Table 4: Hyperparameter settings across all runs in VizDoom (only where different from Table
Name
Description
Value
Q Ir
learning rate for centralized critic
0,0005
π Ir
learning rate for decentralized policies
0.0005
bs
batch size
128
D
maximum size of replay buffer
5e5
A.3 NETWORK ARCHITECTURES
In this section we list, in pscudo-code, the architectures we used for all policies and critics
A.3.1 GRIDWORLD
@ohare (shared for policy heads):
obs_size size observations shape [1]
fel Linear (in_dim-obs_size out_dim= n1 ReLU ()
of (specific to each policy head):
act shape
14

---

Under review as a conference paper at ICLR 2020
fc2 Linear (in dim=fcl.out dim, dat=3)
n12 ReLU ()
fe3 Linear (in_dim=ff22ouu_ssin cut_dim=n_acs)
gishure (shared critics for all agents and reward types):
state_size states. shate [1]
fel ninear sin_dimsstate_siee cut_dim-128)
n1l ()LU()
Vi, (specific each agent/policy head combination, same architecture for extrinsic and intrinsic crities):
n_acs actions. shape [1]
fe2 takes other agents' actions as input
fc2 Linear (in_dim=fcl..ut_ddl + (num_agents 1) n_acs, out_dim= 28)
n12 ReLU ()
fc3 Linear (in_dim=fo2.out. cut_dim-n_acs)
A.3.2 VIZDOOM
gehare (shared for policy heads belonging agent):
vector observation encoder
oos size = vector vector_ooserveee
observations. shape [1]
vect fc Linear (in (in_dim=obs dim=obs size, cut dim=3) vect_nl ReLU()
image observation encoder
img mmg_obb_channcll =
shape [1]
padl = ReflecttinPaddingg
convl Conv2D http://iiiaaameeeeggggooooo.ooed chw.nnellhaannls out_channels=33,
filter_size-3, stride=2)
conv = ReLU()
pad2 = ReflectionPaddin (size=1)
conv2 Conv2D htwp::/a.w.aaaeeaaaaootooooooooe
out_cnannels=32,
filter_aize-3, stride=2)
conv_n12 R)IU()
pad3 -
conv3 = Conv2D (in www.eeessccom.cttttoooooo
out_ channels=32,
filter_size=3] stride=2)
conv m13 ReLU()
pad4 = Refloctioonssddinggeee (sizo=1)
conv4 = Conv2D
out_channels-32,
filter_size=3, stride=2)
conv_n14 ReLU()
conv_flatten Flatten + flatten cutput of conv layers
conv_fc Linear www.aonoooalaataaee flnt conv_fc_ni ReLU()
oum_ out_dim-128)
0f (specific to each policy head):
acs actions shape []]
takes concatenation of image and vector encodings as input fo fo_outl = Linear (in www.conv_fcccoom din + vect fc. din, out dim=3)) fo_out_ni ReLU () fo_out2 Linear fin_dim
out_dimen_acs)
Sishare (shared across critics for all agents and reward types):
15

---

Under review as a conference paper at ICLR 2020
state size states. shape
fel Linear iin_diistttte_seee cut_dim=256)
n11 ()LU
Vi, (specific to each agent/policy head combination, same architecture for extrinsic and intrinsic crities):
n acs = actions, shape [1]
fc2 takes other agents' actions as input
fo2
Linear (in dim=fel. dim (num (num_agents a_acs, out dim=256)
m12 ReLU()
fe3 Linear (in_dim=fo2.on out_dim, cut_dim=n_acs)
A.4 TRAINING CURVES
A.4.1 GRIDWORLD
1.75
Main Tressures Found
1.50
Variant
Mean Episode Length
460
Multi
1.25
Independent
1.00
Minimum
300
Burrowing
Feader-Falliowe
200
0.25
100
20000
800000
1000000
200000
400000
600000
800000
1000000
Step
Stop
Figure 4: Results Task 1 Gridworld with agents.
Varint
Multi
Moan Treasures Tound
Minimum
Length
Covering
Rurrowing
Follower
600
1000000
Step
Step
Figure 5: Results on Task Gridworld with agents.
16

---

Under review as a conference paper at ICLR 2020
Vanant
Multi
Independent
Moan Traasins Found
Minimum
Length
1.5
Covering
Burrowing
6090
4090
0.5
494
0.0
400
Stop
Stop
Figure 6: Results on Task Gridworld with agents.
2,00
Veriant
500
Independent
Misi Treasumes Found
1,50
Minimum
Mean Episodl Length
400
Covering
1.25
Bunnoiing
Leader Follower
300
0.75
300
0.50
1001
0.00
2000O00
200000
SQ1TRO
1000ИИ0
Step
Stop
Figure 7: Results on Task 2 in Gridworld with agents.
3.0
Varint
Multi
2.5
Moan Tressures Tound
Minimum
Length
2.0
Covering
Rurrowing
1.5
Felle-Fellweer
1.0
0.5
1000000
Step
Step
Figure 8: Results on Task 2 Gridworld with agents.
17

---

Under review as a conference paper at ICLR 2020
Vanant Multi
3.0
Independent
430
Moann Tratsirs Found
2.5
Minimum
Length
Covering
Burrowing
830
1.5
1.0
Stop
Stop
Figure 9: Results on Task 2 Gridworld with agents.
2,00
Veriant
500
Independent
Misi Treasums Found
1,50
Minimum
Mean Episodle Length
400
Covering
1.25
Bumnwinn
Leader Follower
300
0.75
2001
0.50
100
0.00
2000O00
200000
БЛЛОКИ
SOUTROO
1000000
Step
Stop
Figure 10: Results on Task 3 in Gridworld with agents.
Varint
Multi
Moan Treasures Tound
2.0
Minimum
Covering
1.5
Rurrowing
1.0
0.5
1000000
Step
Step
Figure 11: Results on Task Gridworld with agents.
18

---

Under review as a conference paper at ICLR 2020
Vanant
Multi
Independent
Moann Traazins Found
2.11
Minimum
Length
430
Covering
Burrowing
1.5
600
1.0
300
0.0
Stop
Stop
Figure 12: Results on Gridworld agents.
A.4.2 VIZDOOM
2,00
500
1.75
Independent
Multi
450
Mean Trazairs Found
Minimum
Meem Epieode Length
4001
Covering
1.25
Burruing
360
Leader Leader-Follover Follover
200
0.75
0.30
250
200
0.00
150
200000
600000
800000
1000000
200000
400000
600000
500000
Step
Step
Figure 13: Results on Task Vizdoom.
2,00
Variant Multi
500
1.75
450
Independent
Moin Trazsire Found
Mein Epieade Lengha
400
Covering
1.25
Burrwing
350
1.00
Leader
300
250
0.50
200
0.25
150
1030000
Step
Step
Figure 14: Results Task in Vizdoom.
19

---

Under review as a conference paper at ICLR 2020
Veriant
1.75
Multi
Independent
Moan Treasures Found
1.50
Minimum
Mean Episadl Length
400
Covering
Burrowing
350
1,00
LeaderFollooer
3001
0.75
2601
11.25
200
160
НИОКИИ
1001000
200000
1000000
Step
Stop
Figure 15: Results Task in Vizdoom.
A.5 MORE ABLATIONS
In this section we consider two ablations/comparioons to our model across all three tasks in the the first (Centralized) we compute intrinsic rewards under the as-
agent version gridworld. sumption that all agents are treated as one agent. In other words, we use the inverse count of the number of times that all agents have jointly taken up their combined positions, rather than consid- ering agents independently. While this reward function will ensure that the global state space is thoroughly searched, it lacks the inductive biases toward spatial coordination that our reward func- tions incorporate. As such, it does not learn efficiently the second (Multi (No Entropy)) we remove the entropy term from the head selector loss function in order to test its importance. We find that this ablation is unable to match the performance of the full method, indicating that entropy crucial in making sure that our method does not converge early to suboptimal policy selector.
method in any of the three tasks. In
2,00
500
1.75
Moan Trazsins Found
Mean Epieade Length
4011
1.25
1.00
300
0.50
Veriant
200
Multi
0.25
Multi Entrogy)
100
500000
1000000
1000000
Step
Step
Figure 16: Ablations on Task Gridworld with agents.
20

---

Under review as a conference paper at ICLR 2020
1.75
Moan Treasires Found
1.50
Meen Episade Length
1,00
2001
Vaniatt
11.25
Cantralized
100
Multi (No Entropy)
5000
НИOКИИ
1001000
200000
1000ИИ0
Step
Stop
Figure 17: Ablations Task 2 in Gridworld with 2 agents.
2,00
500
1.75
Moan Trazsirs Found
Mein Episade Length
1.25
1.00
300
0.50
Veriant
Multi
0.25
Multi Entrogy)
500000
1000000
1030000
Step
Step
Figure 18: Ablations on Task 3 Gridworld with agents.
21

---

Under review as a conference paper at ICLR 2020
A.6 ANALYZING META-POLICY
0.8
Head Indepeedent
Polabity
Independent
Miximam
Probabiity
0.8
Covering il Hhurowwing
0.4
Berrosing
Fiepline
Lecapidee
0.0
Mean Traggrts Foard
Menn Treaure Found
0.5
0.3
0.0
0.0
100000
200000
330003
922003
100000
20000
(30000)
520000 (00300 720000
Stop
Step
(a)
(b)
Figure 19: runs of our method GridWorld Task 3 with agents. Top row shows evolution of meta-policy's probability of selecting each policy head. Bottom row shows the number of treasures found per episode.
In Figure 19 we analyze the behavior of the meta-policy in two separate runs. We evaluate on Task 3, since find that method is able to surpass the best individual reward function. This task assigns specific goals to each agent. As such, one might expect that independent exploration would work most effectively in this setting. While independent exploration is effective (see Figure 10, find that our method can outperform when the agents finally learn how solve the task; however, not necessarily successful when deployed on their own. This lack of success is likely due to the fact that these rewards cause the agents pick region and commit exploring for the duration of training. As such, the agents may pick the "wrong" region at first and never be able to recover. On the other hand, using our methods, the meta-policy can wait until the burrowing exploration regions align with the assigned rewards and then select the policies trained on these rewards. This usually ends up being more efficient than waiting for the agents to explore the whole map using independent rewards.
In both runs, we find that burrowing rewards are selected
find that burrowing rewards
22


Reviews:
[{"review_id": "rJeoQlwTKB", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Overall I like the approach in the paper. It proposes a nice 2 pronged method for exploiting exploration via intrinsic rewards for multi-agent systems. The parts that a bit lacking with the current version of the paper in this are the evaluation tasks are few and a bit simple and I think there needs to be more discussion on the \"coverage\" of the intrinsic reward types. Are the ones proposed motivated by the tasks in the paper or are they sufficient for tasks in general?  Last using a more recent novelty metric could allow the method to work on more interesting/complex tasks.\n\nMore detailed feedback:\n- It would be good to include more learning curves in the main text for the paper.\n- The fact that applying intrinsic motivation to multi-agent simulations seems like a natural idea would be to convert the problem to a \"single\" agent problem to compare against the \"normal\" application of intrinsic rewards. This might be another baseline to consider for comparison.\n- It says that all agents share the same replay buffer. Does this also imply that every agent is performing the same task there are just many agents? This does not make the problem very multi-agent with different goals. Would it affect the algorithm significantly to work on an environment where the agents have various types of goals?\n- As is noted in the text, this method appears to work well in the centralized training scheme that many have adopted recently. However, It makes me wonder if there is a way to employ these exploration schemes in a non-centralized training form. The ability to ask other agents in the world about there preferences and novelty of states appears to be a strong assumption, especially in a multi-agent robotics problem.\n- While the authors note that the intrinsic rewards used in this work are not comprehensive it would be good to note how comprehensive they are. Are there a few that were left out on purpose. Do the authours believe this set is sufficient. This statement makes it seem like the authors just tried a few options and found one that worked. It would be good to expand on this discussion more.\n- More detail for Figure 1 would be helpful to understand the overall network design. While that figure it helpful maybe it would be good to include a version that goes into detail for the 2 agent environment. Then a more compressed n agent version can also be shown.\n- The paper describes a policy selector that is a type of high-level policy for HRL. This design seems rather unique in that this part of the policy can optimizing for which intrinsic reward to toggle based on the extrinsic rewards observed. I like it. It is noted that entropy is important for this design. Can this be analyzed in an empirical way? Is this true for most environments/tasks?\n- Task 2 seems a bit contrived. Is there another instance of this type of task elsewhere in another paper? It would be better to use more standard tasks if they are available.\n- Before section 6.1 the paper is discussing rewards the are received. It would be good to more explicit about where these rewards are coming from. I think it is meant that these rewards are the extrinsic rewards but it does not say.\n- As noted just before section 6.1 it seems for the collection of tasks 1-3 it is already obvious what types of intrinsic rewards should be used. It would be good to include more tasks where this decision is less obvious.\n- Why are there \"black holes\" in the environment? Also if an agent steps into a black hole they are crushed never to be seen again. What you describe sounds more like a wormhole where one end is non-stationary... Also, can the agents detect the presence of a black hole in some way?\n- It appears the novel metric is count based. While this can work in practice it seems a rather simple metric. Is it possible to use something more like ICM or RND that was referenced in the paper? Especially for the VizDoom environment?\n- In table 2 where are some of the numbers bold? It would be good to include this information in the caption for the table.\n- I am not sure if the discussion on the behaviours the intrinsic reward functions result in are very surprising. Maybe there is a more interesting behaviour that results from the combination of two intrinsic rewards?\n", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "SkgAf17b9H", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\nThe paper proposes a method for coordinating the exploration efforts of agents in a multi-agent reinforcement learning setting. The approach has two main components: (i) learning different exploration policies using different \"joint\" intrinsic rewards; and (ii) learning a higher-level policy that selects one of the exploration policies to be executed at the beginning of each episode.\n\nEach agent has its own novelty function which quantifies the novelty of observation seen by that agent. To coordinate exploration, these novelty functions are combined using aggregation functions to produce intrinsic reward for the agent. Each such aggregating function yields a different intrinsic reward. The authors propose several such aggregating functions as examples, however the method is applicable to other aggregating functions as well, as long as they can be computed off-policy.\n\nDuring training, the higher level policy selects one of the exploration policies which is then executed for the entire episode. The episode data is used in two ways: (i) to train the higher-level policy using policy gradients for maximizing extrinsic rewards along with an entropy term; and (ii) to train each exploration policy using soft actor-critic on its own intrinsic reward function (and extrinsic reward) in an off-policy manner.\n\nExperiments done on grid-world and VizDoom environment for three different tasks demonstrate that, on most tasks, the proposed approach performs at least as well as separately trained individual intrinsic rewards. Further ablation studies confirm that both the hierarchical setup and the \"joint\" intrinsic rewards are useful.\n\n\nQuestions to the Authors:\n\n1. The second sentence in section 5 is not clear - \"Furthermore, the type of reward ... sufficiently complex\". The high-level policy selects an exploration strategy at the beginning of each episode and then sticks to it for the entire duration of the episode. Changing the exploration strategy over the course of training might be useful in cases when agent needs to switch to a different exploration strategy after reaching a particular bottleneck state. However, this would require the exploration strategy to be changed in the middle of an episode which is not supported. Could you give an example where the exploration strategy must be changed over time even if one only selects the strategy at the beginning of each episode? Also, why not select the exploration strategy after every fixed number of time steps within each episode (by making high-level policy a function of the current state)? \n\n2. Analyzing the role of high-level policy and its evolution over time on different tasks would be a very nice addition to the paper. Qualitative experiments demonstrating that it provides a curriculum which helps the agents in surpassing the performance of individual intrinsic rewards would be helpful.\n\n3. Should \\Pi in (10) also depend on i?\n\nThough paper is reasonably well written I find the contributions are very marginal. If authors can position the paper well with the existing literature and bring out the impact of the contributions it will be helpful. \n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "N/A"}, "extra_text": {}}, {"review_id": "H1xJLKdhKH", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Contribution:\n\nThe paper proposes to use a set of handcrafted intrinsic rewards that depend on the novelty of an observation as perceived by the rest of the other agents. For each pair of reward and agent, they learn a policy and a value through actor critic method, and then a meta-policy choses at the beginning of each episode which intrinsic rewards to use, meaning that the policy used by the agents corresponds to the one that maximizes the reward chosen.\n\n\n\nReview:\n\n\nThe major limitation of the paper in my opinion is the fact that the \"coordination\" that occurs here is only happening at training time, not at execution time. The agents eventually learn whatever trajectory they need to perform, and then proceed to do so without any interaction with the other agents. In a sense, they don't even learn to explore collaboratively. In other words, agents trained on task 1 in a given maze would not be able to solve task 2 on the same maze without essentially relearning everything from scratch.\nThe other corollary of the fact that each agent learns its own policy is that the number of agents is fixed at training time, preventing testing with a different number of agents, as sometimes done in the literature ([1] [2]).\n\nGiven this limitation the scope of the work basically reduces to the exploration of a fixed environment when the action space can be factored into different agents. This \"multi-agent\" formulation is presumably meant to break down the computational complexity of having a joint observation/action space. However, the experiments are conducted only with a very limited number of agents (only 2 in the non toy environment of vizdoom). This small scale doesn't, in my opinion, demonstrate the advantage of the decomposition of the MDP over say SOTA single-agent exploration methods applied to the cartesian product of all the agents action spaces (in vizdoom the paper considers only 3 actions, so with two agents it would amount to 9 actions, which is still very tractable). Once the trajectories of both agents are found, they can be distilled to each of them individually so that they only depend on the local observation.\n\n\nRegarding the experiments on the Vizdoom environment, it appears that the traditional evaluation setup [3] doesn't involve providing the global position (x,y) to the agents as part of the observations (they must be inferred from the visual feed), contrary to the experimental setup presented in this paper.\nIn my opinion, this weakens the claim that the method \"scales to more complex environments\" since providing the position essentially makes the environment similar to a grid-world (arguably the visual feed isn't even needed to solve the task.\n\n\nThe use of a dynamic policy selection is somewhat interesting, but would benefit better investigation. Firstly, it is not clear to me if all the selection of the policy to use during training affects all the trajectories of the batch, or if different episodes of the batch may have a different policy.\nSecondly, it seems that the setting is typically the one of a (non-stationary) bandit, since there is no state and the \"reward\" is the return obtained by the policy. Could you share the reason behind the choice of an actor-critic algorithm over classical bandit algorithms? One obvious advantage of the latter are provable regret bounds.\nIn all, the selection policy seems to be useful during training, since it sometimes yields better solutions than any of the individual reward schemes. It suggests that some form of curriculum over the rewards is occurring during training, but if this is really what is going on, then it's possible that the relevant literature about curriculum learning may offer more stable and principled solutions than an actor critic, for example population based training. This could potentially solve the issues observed in task 2.\n\n\n[1] Relational Deep Reinforcement Learning, Zambaldi et al, https://arxiv.org/abs/1806.01830\n[2] A Structured Prediction Approach for Generalization in Cooperative Multi-Agent Reinforcement Learning, Carion et al, https://arxiv.org/abs/1910.08809\n[3] Curiosity-driven Exploration by Self-supervised Prediction, Pathak et al, ICML 2017\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors present a method that utilizes intrinsic rewards to coordinate the exploration of agents in a multi-agent reinforcement learning setting.   The reviewers agreed that the proposed approach was relatively novel and an interesting research direction for multiagent RL.  However, the reviewers had substantial concerns about writing clarity, the significance of the contribution of the propose method, and the thoroughness of evaluation (particularly the number of agents used and limited baselines).  While the writing clarity and several technical points (including addition ablations) were addressed in the rebuttal, the reviewers still felt that the core contribution of the work was a bit too marginal.  Thus, I recommend this paper to be rejected at this time.
Decision: Reject