Title: COORDINATED EXPLORATION VIA INTRINSIC RE-WARDS FOR MULTI-AGENT REINFORCEMENT LEARN-ING

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 (Kempka et al., 2016) platform.

1. INTRODUCTION:

Recent work in deep reinforcement learning effectively tackles challenging problems including the board game Go (Silver et al., 2016) , Atari video games (Mnih et al., 2015) , and simulated robotic continuous control (Lillicrap et al., 2016) ; however, these successful approaches often rely on frequent feedback indicating whether the learning agent is performing well, otherwise known as dense rewards. In many tasks, dense rewards can be difficult to 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 an agent has attained success or failure on a 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. Furthermore, if rewards cannot be obtained by random actions, an agent will never receive a 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 et al., 2017; Houthooft et al., 2016; Burda et al., 2019; Ostrovski et al., 2017; Tang et al., 2017) .

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 exploration-focused approaches frequently formulate their intrinsic rewards to measure the "novelty" of a 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.

Directly applying novelty-based intrinsic motivation to 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 a 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. Instead, it would be much more sensible for agents to "divide-and-conquer," or avoid redundant 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, we must find a 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 a candidate set of intrinsic rewards for multiagent exploration which hold differing properties with regards to how they explore the state space. Subsequently, we present a hierarchical method for simultaneously learning policies trained on different intrinsic rewards and selecting the policies which maximize extrinsic returns. Importantly, all policies are trained using a shared replay buffer, drastically improving the sample efficiency and effectiveness of learning in cooperative multi-agent 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-based approaches to large state spaces, many recent works have focused on devising pseudo state counts to use as reward bonuses (Bellemare et al., 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 including: transition dynamics prediction error (Pathak et al., 2017) , information gain with respect to a learned dynamics model (Houthooft 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 (Sunehag et al., 2018; Rashid et al., 2018; Foerster et al., 2018) , non-stationarity of the environment in the presence of other learning agents (Lowe et al., 2017; Foerster et al., 2018; Iqbal & Sha, 2019) , and learning of communication protocols between cooperative agents (Foerster et al., 2016; Sukhbaatar et al., 2016; Jiang & Lu, 2018) .

Exploration in MARL While the fields of exploration in RL and multi-agent RL are popular, relatively 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. Jaques 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 metrics for evaluating the efficacy of reward functions in multi-agent domains. These works, while important, do not address the problem of exploring a large state space, and whether this exploration can be improved in multi-agent systems. A recent approach to collaborative evolutionary reinforcement learning (Khadka et al., 2019) shares some similarities with our approach. As in our work, the authors devise a method for learning a population of diverse policies with a shared replay buffer and dynamically selecting the best learner; 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.

3. BACKGROUND:

Dec-POMDPs In this work, we consider the setting of decentralized POMDPs (Oliehoek et al., 2016) , which are used to describe cooperative multi-agent tasks. A decentralized POMDP (Dec-POMDP) is defined by a tuple: (S, A, T , O, O, R, n, γ). In this setting we have n total agents. S is the set of global states in the environment, while O = ⊗ i∈{1...n} O i is the set of joint observations for each agent and A = ⊗ i∈{1...n} A i is the set of possible joint actions for each agent. A specific joint action at one time step is denoted as a = {a 1 , . . . , a n } ∈ A and a joint observation is o = {o 1 , . . . , o n } ∈ O. T is the state transition function which defines the probability P (s |s, a), and O is the observation function which defines the probability P (o|a, s ). R is the reward function which maps the combination of state and joint actions to a single scalar reward. Importantly, this reward is shared between all agents, so Dec-POMDPs 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 underlying algorithm. SAC incorporates an 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 as follows:

EQUATION

where D is a replay buffer that stores past environment transitions, ψ 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 an optimal policy. The critic is learned with the following loss function:

L Q (ψ) = E (s,a,r,s )∼D (Q ψ (s, a) -y) 2

(2)

y = r(s, a) + γE a ∼π(s ) Q ψ (s , a ) - log(πθ(a |s )) α (3)

where ψ are the parameters of the target critic which is an exponential moving average of the past critics, updated as: ψ ← (1 -τ ) ψ + τ ψ, and τ is a 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 execution (Lowe et al., 2017; Foerster et al., 2018; Sunehag et al., 2018; Rashid et al., 2018; Iqbal & 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 applications use simulation for training, communication between agents during the training phase has a relatively lower cost.

4. INTRINSIC REWARD FUNCTIONS FOR MULTI-AGENT EXPLORATION:

In this section we present a set of intrinsic reward functions for exploration that incorporate information about what other agents have explored. These rewards assume that each agent (indexed by i) has a novelty function f i that determines how novel an observation is to it, based on its past experience. This function can be an inverse state visit count in discrete domains, or, in large/continuous domains, it can be 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 novelty function can operate on all other agents' observations. 

i ) = 1 n j f j (o i ) INDEPENDENT MINIMUM COVERING BURROWING LEADER-FOLLOWER fi(oi) min j∈{1...n} fj (oi) fi(oi)1 [fi(oi) > µ(oi)] fi(oi)1 [fi(oi) < µ(oi)] See text

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 a result of an action. The remainder of intrinsic reward functions that we consider use the novelty functions of other agents, in addition to their own, to 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 in exploration is 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 to 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 a dead end), somewhat akin to a depth-first search. LEADER-FOLLOWER 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 a 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-policy.

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 if 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-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 a 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 et al. (2019) . We provide a diagram of our model architecture in Figure 1 .

We index agents by i ∈ {1 . . . n} and intrinsic reward types by j ∈ {1 . . . m} where m 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 π j i . It takes as input agent i's observation, o i , and outputs a distribution from which we can sample the action a i . The parameters of this policy are

Θ j i = {θ share i , θ j i },

where θ share i is a shared base/input (for agent i) in a neural network and θ j i is a head/output specific to this reward type.

The extrinsic critic for policy head π j i is represented by Q ex i,j . It takes as input the global state s and the actions of all other agents a \i , and it outputs the expected returns under policy π j i for each possible action that agent i can take, given all other agents' actions. The parameters of this critic are Ψ ex i,j = {ψ share , ψ ex i,j } where ψ share is a shared base across all agents and reward types. A critic with similar structure exists for predicting the intrinsic returns of actions taken by π j i , represented by Q in i,j , which uses the parameters: Ψ in i,j = {ψ share , ψ in i,j }. Note that the intrinsic critics share the same base parameters ψ share .

We remove the symbols representing the parameters of the policies (Θ) and the critics (Ψ) for readability. In our notation we use the absence of a subscript or superscript to refer to a group. For example π j , refers to all agents' policies trained on intrinsic reward j. We train our critics with the following loss function, adapted from soft actor-critic:

L Q (Ψ) = E (s,o,a,r,s ,o )∼D   m j=1 n i=1 (Q ex i,j (s, a) -y ex i,j ) 2 + (Q in i,j (s, a) -y in i,j ) 2   (4)

y ex i,j = r ex (s, a) + γE a ∼π j (o ) Qex i,j (s , a ) - log(π j i (a i |o i )) α (5)

y in i,j = r in i,j (o i ) + γE a ∼π j (o ) Qin i,j (s , a ) - log(π j i (a i |o i )) α (6)

where Q refers to the target Q-function, an exponential weighted average of the past Q-functions, used for stability, and π are similarly updated target policies. The intrinsic rewards laid out in Table 1 are represented as a function of the observations that results from the action taken, r in i,j (o i ) where j specifies the type of reward. Importantly, we can calculate these loss functions for expected 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 gradient:

EQUATION

A j i (s, a) = Q ex i,j (s, a) + βQ in i,j (s, a) -V j i (s) (8) V j i (s) = a i ∈Ai π j i (a i |o i )(Q ex i,j (s, {a i , a \i }) + βQ in i,j (s, {a i , a \i })) (9)

where β is a scalar that determines the weight of the intrinsic rewards, relative to extrinsic rewards, and A j i is a multi-agent advantage function (Foerster et al., 2018; Iqbal & Sha, 2019) , used for helping with multi-agent credit assignment.

Dynamic Policy Selection Now that we have established a method for simultaneously learning policies using different intrinsic reward types, we must devise a 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 unknowns," 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 a meta-policy that, at 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 Π with a vector, φ, that contains an entry for every reward type. The probability of sampling head j is: Π(j) ∝ exp(φ[j]). Unlike the action policies, this high-level policy does not take any inputs, a we 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, Π, to maximize this value using the returns received when performing rollouts in the environment. We use the following gradient to train Π:

∇ φ J(Π) = E h∼Π ∇ φ log Π(h) - log Π(h) η + R ex h -b Π (10) R ex h = T t=0 γ t r ex (s t , a t )|a ∼ π h (o t ), b Π = m h Π(h )µ h (11)

where µ h is a running mean of the returns received by head h in the past, and η is a parameter similar to α for the low-level policies, which promotes entropy in the selector policy. Entropy in the policy selector is important in 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, we can learn a diverse set of behaviors based on various multi-agent intrinsic reward functions and select the one that maximizes performance on the task at hand at any point during training, while continuing to consider other policies that may lead to greater rewards.

6. EXPERIMENTS:

We begin by describing our evaluation domains and then present experimental results which demonstrate the effectiveness of 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 in 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 1 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 a negative time penalty towards extrinsic rewards 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 a treasure that is allowed by the specific task, and rewards are shared between all agents. The optimal strategy in TASK 1 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 a 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 a 10% chance of an agent's action being replaced by a random one. Furthermore, there are 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 it moves toward one, until the hole opens and it resets to zero. If an agent steps into a black hole when it is open, they will be sent back to their starting position. The spaces colored as black are holes that are currently open, while the gray spaces are holes that have the possibility of opening at 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.

The novelty function for each agent f i , which is used for calculating the intrinsic rewards in Table 1 , is defined as 1 N ζ , 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 challenging 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 use the "My Way Home" map, which has been used as a test bed for single agent exploration techniques (Pathak et al., 2017) , and modify it for multi-agent tasks (pictured in Figure 2b ). Since the agents are moved to a central location closer to their rewards than in the original map, we lower the action repeat from 4 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 not a discrete domain, we separate agents' (x, y) positions into discrete bins and use the counts for these bins. We again find that ζ = 0.7 to work well in our experiments. Shaded region is a 68% confidence interval across 6 runs of the running mean over the past 100 episodes. Our approach (MULTI-EXPLORATION) is competitive with the best individual intrinsic reward function, using the 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.

6.3. MAIN RESULTS:

Figure 3a demonstrates the results of our approach over the course of training on the 2 agent version of TASK 1 in gridworld, and the final results on each task/agent/domain combination can be found in Table 2 . The full training curves for all settings can be found in the appendix (Section A.4). We train a team of agents using each of the multi-agent intrinsic reward functions defined in Table 1 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 2 agents, we find that our policy selector consistently selects BURROWING and MINIMUM rewards, the two best performing reward functions on 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 a reliable way for measuring the novelty of observations exists.

Interestingly, our approach is sometimes able to significantly surpass the performance of the best individual reward function on TASK 3. This task requires agents to collect the specific reward assigned to them, so we expect independent exploration to be the most effective; however, exploration types that perform "divide-and-conquer" type behavior such as BURROWING and MINIMUM have the potential to drastically speed up the exploration process if they happen to divide the space correctly, 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 if they are not working, we find that our method is able to surpass all individual reward types.

We find that our approach is 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 a specific exploration strategy early on in training, highlighting a 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 at the anonymized link below.1 . INDEPENDENT rewards, as expected, result in agents exploring the whole state space without taking other agents into consideration. As a result, on TASK 1, which requires coordination between agents to spread out and explore different areas, INDEPENDENT rewards struggle; however, on TASK 3, where agents receive individualized goals, independent exploration usually performs better, relative to the other methods. TASK 2 also requires coordination, but the rate of black holes dropping out in the gridworld version is lower on that task, making exploration easier. As a result, INDEPENDENT rewards perform well on TASK 2; however, we find that LEADER-FOLLOWER also performs well on this task, expecially when more agents are involved, indicating that these rewards do a 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. In 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 to 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 a mutually exclusive fashion.

Ablations We compare to a baseline meta-policy which simply selects the action policies uniformly at random. We find that our approach is significantly superior to this baseline (see Figure 3b Multi (Uniform Meta-Policy)). Furthermore, we test a 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 to test the degree to which the specific multi-agent intrinsic reward functions are helpful, as 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 in multi-agent exploration tasks.

We perform two further ablations/comparisons. Results on task 1 with 2 agents in GridWorld are viewable in Figure 3b , and results on tasks 2 and 3 with 2 agents are viewable in the Appendix (A.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 of 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, it lacks the inductive biases toward spatial coordination that our reward functions incorporate. As such, it does not learn as efficiently as our 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.

7. CONCLUSION:

We propose a 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 matching 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 we hope to introduce methods for directly learning the multi-agent intrinsic reward functions, rather than selecting from a set.

Peter Sunehag, Guy Lever, Audrunas Gruslys, Wojciech Marian Czarnecki, Vinicius Zambaldi, Max Jaderberg, Marc Lanctot, Nicolas Sonnerat, Joel Z. Leibo, Karl Tuyls, and Thore Graepel. Valuedecomposition networks for cooperative multi-agent learning based on team reward. In Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems, AA-MAS '18, pp. 2085 -2087 , Richland, SC, 2018. International 

A APPENDIX:

A.1 ENVIRONMENT DETAILS

A.1.1 GRIDWORLD:

The black holes which send agents back to their starting positions if they are stepped into are an important aspect of the environment, as they add difficulty to exploration. The probability, ρ, of a black hole opening at each step, t, evolves as such: ρ t+1 = ρ t + N (µ, σ), where µ = σ = 0.05 for TASK 1 and µ = σ = 0.005 for 2 and 3.

Agents observe their global position in (x, y) coordinates (scalars), as well as local information regarding walls in adjacent spaces, the probability of their adjacent spaces opening into a black hole, the relative position of 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 (x, y) 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 4 cardinal directions as well as an option to not move, which is helpful in cases where an agent is waiting for a black hole to be safe to cross.

A.1.2 VIZDOOM Agents receive their egocentric view (Figure 2c ) in the form of 48x48 grayscale images as observations along with an indicator of which agents (if any) have collected each reward, and we use a 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 a discrete domain, 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. (x, y) positions in the global state are represented 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, or go forward.

A.2 TRAINING DETAILS:

The training procedure is detailed in Algorithm 1, and all hyperparameters are listed in Tables 3 and 4 . Hyperparameters were selected by tuning one parameter at a time through intuition on task 1 with 2 agents and then applying to the rest of the settings with minimal changes. Where hyperparameters differ between settings, we make a footnote denoting them as such. 

A.5 MORE ABLATIONS:

In this section we consider two ablations/comparisons to our model across all three tasks in the 2 agent version of gridworld. 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 of 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, it lacks the inductive biases toward spatial coordination that our reward functions incorporate. As such, it does not learn as efficiently as our method in any of the three tasks. 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. 

:

https://sites.google.com/view/multi-exploration-iclr2020/home

Figures and Tables:

Figure 1: Diagram of our model architecture, showing how parameters for actors and critics are shared. i indexes agents, while j indexes reward types.

Figure 2: (Left) Rendering of our gridworld domain. Agents start each episode in the central room and must complete various tasks related to collecting the yellow treasures placed around the map. (Center) Top-Down view of VizDoom "My Way Home" map, modified for multi-agent experiments (Right) Egocentric view in VizDoom used for agents' observations

Figure 3: (Left) Mean number of trasures found per episode on TASK 1 with 2 agents in the gridworld domain.

Figure 4: Results on Task 1 in Gridworld with 2 agents.

Figure 7: Results on Task 2 in Gridworld with 2 agents.

Figure 12: Results on Task 3 in Gridworld with 4 agents.

Figure 13: Results on Task 1 in Vizdoom.

Figure 16: Ablations on Task 1 in Gridworld with 2 agents.

Figure 17: Ablations on Task 2 in Gridworld with 2 agents.

Multi-agent intrinsic rewards for agent i, with µ(o

Table content: <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.

Table content: <table><tr><td/><td/><td/><td colspan="2">GRIDWORLD</td></tr><tr><td/><td/><td colspan="4">Intrinsic reward type (fixed or adaptive as in our approach MULTI)</td></tr><tr><td colspan="3">Task n INDEPENDENT MINIMUM</td><td>COVERING</td><td colspan="2">BURROWING LEAD-FOLLOW MULTI</td></tr><tr><td>1</td><td>2 0.14 ± 0.05</td><td colspan="3">1.62 ± 0.59 0.13 ± 0.12 1.98 ± 0.06</td><td>0.18 ± 0.24</td><td>2.00 ± 0.00</td></tr><tr><td/><td>3 1.16 ± 0.11</td><td colspan="3">1.49 ± 0.76 0.00 ± 0.00 2.06 ± 1.05</td><td>0.34 ± 0.45</td><td>2.23 ± 0.73</td></tr><tr><td/><td>4 0.84 ± 0.29</td><td colspan="3">1.78 ± 0.44 0.00 ± 0.00 1.90 ± 0.49</td><td>1.17 ± 0.39</td><td>2.04 ± 0.61</td></tr><tr><td>2</td><td>2 2.00 ± 0.00</td><td colspan="3">0.92 ± 0.10 1.11 ± 0.99 0.98 ± 0.05</td><td>1.73 ± 0.66</td><td>1.83 ± 0.41</td></tr><tr><td/><td>3 2.66 ± 0.80</td><td colspan="3">1.11 ± 0.29 0.54 ± 0.80 1.80 ± 0.29</td><td>3.00 ± 0.00</td><td>1.80 ± 0.71</td></tr><tr><td/><td>4 1.83 ± 1.08</td><td colspan="3">0.93 ± 0.13 0.22 ± 0.18 1.99 ± 0.67</td><td>2.66 ± 2.06</td><td>2.54 ± 1.21</td></tr><tr><td>3</td><td>2 1.39 ± 0.94</td><td colspan="3">0.67 ± 1.03 0.29 ± 0.37 0.67 ± 1.03</td><td>0.83 ± 0.67</td><td>2.00 ± 0.00</td></tr><tr><td/><td>3 1.68 ± 0.70</td><td colspan="3">0.60 ± 0.73 0.09 ± 0.08 1.35 ± 1.16</td><td>1.59 ± 0.83</td><td>2.21 ± 0.91</td></tr><tr><td/><td>4 1.12 ± 0.47</td><td colspan="3">1.36 ± 0.71 0.05 ± 0.05 2.14 ± 1.49</td><td>0.68 ± 0.53</td><td>1.73 ± 0.47</td></tr><tr><td/><td/><td/><td>VIZDOOM</td><td/></tr><tr><td>1</td><td>2 0.94 ± 0.54</td><td colspan="3">1.57 ± 0.74 0.16 ± 0.17 1.94 ± 0.10</td><td>0.61 ± 0.43</td><td>1.98 ± 0.03</td></tr><tr><td>2</td><td>1.52 ± 0.75</td><td colspan="3">1.53 ± 0.74 0.70 ± 1.00 0.63 ± 0.04</td><td>1.93 ± 0.10</td><td>1.23 ± 0.65</td></tr><tr><td>3</td><td>0.18 ± 0.19</td><td colspan="3">0.64 ± 1.05 0.45 ± 0.46 0.29 ± 0.25</td><td>0.20 ± 0.17</td><td>1.64 ± 0.63</td></tr></table>

Foundation for Autonomous Agents and Multiagent Systems. Ann Nowé, and Karl Tuyls. Coordinated exploration in multi-agent reinforcement learning: an application to load-balancing. In Proceedings of the fourth international joint conference on Autonomous agents and multiagent systems, pp.1105 -1106 . ACM, 2005.   .

Table content: <table><tr><td>Haoran Tang, Rein Houthooft, Davis Foote, Adam Stooke, OpenAI Xi Chen, Yan Duan, John Schul-</td></tr><tr><td>man, Filip DeTurck, and Pieter Abbeel. # exploration: A study of count-based exploration for</td></tr><tr><td>deep reinforcement learning. In Advances in neural information processing systems, pp. 2753-</td></tr><tr><td>2762, 2017.</td></tr><tr><td>Katja Verbeeck,</td></tr></table>

Hyperparameter settings across all runs in gridworld.

Table content: <table><tr><td>Name</td><td>Description</td><td>Value</td></tr><tr><td>Q lr</td><td>learning rate for centralized critic</td><td>0.001</td></tr><tr><td>Q optimizer</td><td>optimizer for centralized critic</td><td>Adam (Kingma &amp; Ba, 2014)</td></tr><tr><td>π lr</td><td>learning rate for decentralized policies</td><td>0.001</td></tr><tr><td>π optimizer</td><td>optimizer for decentralized policies</td><td>Adam</td></tr><tr><td>Π lr</td><td>learning rate for policy selector</td><td>0.04</td></tr><tr><td>Π optimizer</td><td>optimizer for policy selector</td><td>SGD</td></tr><tr><td>τ</td><td>target function update rate</td><td>0.005</td></tr><tr><td>bs</td><td>batch size</td><td>1024</td></tr><tr><td>total steps</td><td>number of total environment steps</td><td>1e6</td></tr><tr><td colspan="2">steps per update number of environment steps between updates</td><td>100</td></tr><tr><td>niters</td><td>number of iterations per update</td><td>50</td></tr><tr><td>max ep length</td><td colspan="2">maximum length of an episode before resetting 500</td></tr><tr><td>Ψ penalty</td><td>coefficient for weight decay on parameters of Q-function</td><td>0.001</td></tr><tr><td>Θ penalty</td><td>coefficient on L 2 penalty on pre-softmax output of policies</td><td>0.001</td></tr><tr><td>θ penalty</td><td>coefficient for weight decay on parameters of policy selector</td><td>0.001</td></tr><tr><td>|D|</td><td>maximum size of replay buffer</td><td>1e6</td></tr><tr><td>α</td><td>action policy reward scale</td><td>100</td></tr><tr><td>η</td><td>selector policy reward scale</td><td>5</td></tr><tr><td>γ</td><td>discount factor</td><td>0.99</td></tr><tr><td>β</td><td>relative weight of intrisic rewards to extrinsic</td><td>0.1</td></tr><tr><td>ζ</td><td>decay rate of count-based rewards</td><td>0.7</td></tr></table>

Hyperparameter settings across all runs in VizDoom (only where different from Table3).

Table content: <table><tr><td/><td colspan="2">Name Description</td><td>Value</td></tr><tr><td/><td>Q lr</td><td>learning rate for centralized critic</td><td>0.0005</td></tr><tr><td/><td>π lr</td><td colspan="2">learning rate for decentralized policies 0.0005</td></tr><tr><td/><td>bs</td><td>batch size</td><td>128</td></tr><tr><td/><td>|D|</td><td>maximum size of replay buffer</td><td>5e5</td></tr><tr><td colspan="3">A.3 NETWORK ARCHITECTURES</td></tr><tr><td colspan="4">In this section we list, in pseudo-code, the architectures we used for all policies and critics</td></tr><tr><td colspan="2">A.3.1 GRIDWORLD</td><td/></tr><tr><td>θ share i</td><td colspan="2">(shared for policy heads):</td></tr><tr><td colspan="3">obs_size = observations.shape[1]</td></tr><tr><td colspan="3">fc1 = Linear(in_dim=obs_size, out_dim=128)</td></tr><tr><td colspan="2">nl1 = ReLU()</td><td/></tr><tr><td colspan="3">θ j i (specific to each policy head):</td></tr><tr><td colspan="3">n_acs = actions.shape[1]</td></tr></table>

Peer review (iclr2020):
Contribution: The 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. Review: The 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. The 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]). Given 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. Regarding 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. In 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. The 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. Secondly, 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. In 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. [1] Relational Deep Reinforcement Learning, Zambaldi et al, https://arxiv.org/abs/1806.01830 [2] A Structured Prediction Approach for Generalization in Cooperative Multi-Agent Reinforcement Learning, Carion et al, https://arxiv.org/abs/1910.08809 [3] Curiosity-driven Exploration by Self-supervised Prediction, Pathak et al, ICML 2017