Influence-Based Multi-Agent Exploration
Authors: Tonghan Wang*
Jianhao Wang*
Yi Wu
Chongjie Zhang
Venue:  (2020)
Keywords: Multi-agent reinforcement learning
Exploration

Abstract: Intrinsically motivated reinforcement learning aims to address the exploration challenge for sparse-reward tasks. However, the study of exploration methods in transition-dependent multi-agent settings is largely absent from the literature. We aim to take a step towards solving this problem. We present two exploration methods: exploration via information-theoretic influence (EITI) and exploration via decision-theoretic influence (EDTI), by exploiting the role of interaction in coordinated behaviors of agents. EITI uses mutual information to capture the interdependence between the transition dynamics of agents. EDTI uses a novel intrinsic reward, called Value of Interaction (VoI), to characterize and quantify the influence of one agent's behavior on expected returns of other agents. By optimizing EITI or EDTI objective as a regularizer, agents are encouraged to coordinate their exploration and learn policies to optimize the team performance. We show how to optimize these regularizers so that they can be easily integrated with policy gradient reinforcement learning. The resulting update rule draws a connection between coordinated exploration and intrinsic reward distribution. Finally, we empirically demonstrate the significant strength of our methods in a variety of multi-agent scenarios.

Published as a conference paper at ICLR 2020
BELLUENCE-BASEE MULTI-AGENT EXPLORATION
Tonghan Wang, Jianhao Wang", Yi Wu & Chongjie Zhang
Institute for Interdisciplinary Information Sciences Tsinghua University Beijing, China
wangth1 8@mails tsinghua. edu. en, w 1200 www ericeggmiill com
jxwuyieopenai. com, chongjie@tsinghua edu.cn on
ABSTRACT
Intrinsically motivated reinforcement learning aims to address the exploration challenge for sparse-reward tasks. However, the study exploration methods in transition-dependet multi-agent settings is largely absent from the literature. ww methods: exploration via cnnommtiion-hhorree influence (EITI) and exploration via decision- decision-thcorette thcoretic influence (EDTD, by exploiting the role of interaction coordinated behaviors of agents. EITI mutual information interdependence between the transition dynamics of agents. EDTI uses a novel intrinsic reward, called Value of Interaction (Vol), characterize and quantify the influence of one agent's 's behavior on expected returns of other agents. By optimiz- ing EITI or EDTI objective as a regularizer, agents are encouraged to coordinate their exploration and learn policies to optimize the team performance. We show how to optimize these regularizers so that they can easily integrated with pol- icy gradient reinforcement learning. The resulting update rule draws a connection between coordinated exploration and intrinsic reward distribution. Finally, we empirically demonstrate the significant strength of our methods in variety of multi-agent scenarios.
We aim to take a step towards solving this problem. We present two exploration
capture the
INTRODUCTION
Reinforcement learning algorithms aim to learn a policy that maximizes the accumulative reward from an environment. Many advances of deep reinforcement learning rely dense shaped reward function, such as distance to the goal (Mirowski et al.) 2216 Wu et al. 2018). scores in games (Mnih) al. 2015) or expert-designed rewards (Wu Tian 2016 Open 2018). but they tend to strug- gle in many real-world scenarios with sparse rewards (Burda et al.
2019). Therefore, many recent
works propose to introduce additional intrinsic incentives to boost exploration, including pseudo- counts (Bellemare et al. 2016 Tang et al. [011]] Ostrovski et al. 2017), model-learning improve- ments (Burda et al. [2019; Pathak et al.] [017) Burda al.) 2018). and information gain (Florensa) et al. Gup7a et al.) 2018 Hyoungseok Kim 2019). These works result in significant progress many challenging tasks such as Montezuma Revenge (Burda et al., (018). robotic manipula- tion (Pathak et al.] 2018 Riedmiller al. 2018), and Super Mario games (Burda et al. 2019
Pathak et 2017).
Notably, most of the existing breakthroughs on sparse-reward environments have been focusing on single-agent scenarios and leave the exploration problem largely unstudied for multi-agent settings it is common in real-world applications that multiple agents are required to solve a task in coordi- nated fashion (Cao et al. 2012] Nowé et al. [2012] [Zhan & Lesser 2011). This problem has recently attracted attention and several exploration strategies have been proposed for transitioniidepeenie cooperative multi-agent settings (Dimakopoulou & Van Roy 2018 Dimakopoulou et al.) [2018 8 Bar- giacchi et al. 2018 Iqbal & Sha (2019b). Nevertheless, how to explore effectively in more general scenarios with complex reward and transition dependency among cooperative agents remains an open research problem.
"Equal Contribution.

---

Published as a conference paper at ICLR 2020
This paper aims to take step towards this goal. Our basic idea is to coordinate agents' exploration by taking into account their interactions during their learning processes. Configurations where in- teraction happens (interaction points) lie at critical junctions in the state-action space, through these critical configurations can transit to potentially important under-explored regions. To exploit this idea, propose exploration strategies where agents start with decentralized exploration driven by their individual curiosity, and are also encouraged to visit interaction points to influence the ex- ploration processes of other agents and help them get more extrinsic and intrinsic rewards. Based on how to quantify influence among agents, we propose two exploration methods. Exploration via information eeeormattion-hhoretiic influence (EITI) uses mutual information (MI) to capture the interdependence between the transition dynamics of agents. Exploration via prrcision-theoreed further and uses a novel measure called value of interaction (Vol) to disentangle the effect of one agent's s state-action pair on the expected (intrinsic) value of other agents. By optimizing MI or Vol as a regularizer to the value function, agents are encouraged to explore state-action pairs where they can exert influences other agents for learning sophisticated multi-agent cooperation strategies.
influence (EDTI) goes
To efficiently optimize MI and Vol, we propose augmented policy gradient formulations so that the gradients be estimated purely from trajectories. The resulting update rule draws connection between coordinated exploration and the distribution of individual intrinsic rewards among team members, which further explains why our methods are able to facilitate multi-agent exploration.
We demonstrate the effectiveness of our methods on a variety of sparse-reward cooperative multi- agent tasks. Empirical results show that both EITI and EDTI allow for the discovery of influential states and EDTI further filter out interactions that have no effects on the performance. Our results also imply that these influential states are implicitly discovered as subgoals in search space that guide and coordinate exploration. The video of experiments is available at https: /tep:::/sstes.. google. ccnm//iew//Lfluueeee--e
2 SETTINGS
In our work, we consider a fully cooperative multi-agent task that can be modelled by a factored multi-agent MDP G = (N, S, A, T. n), where N = f1.2,..., n the finite set of agents, S = X; is the finite set of joint states and S; is the state set of agent i. At each timestep, each agent selects an action a; E A, at state s, forming a joint action a E A = XieN resulting in shared extrinsic reward r(s, a)) for each agent and the next state s' according to the transition function T(s'{s,a).
The objective of the task is that each agent learns policy (a,ls);) jointly maximizing team performance. The joint policy T= Nn) induces an action-value function, Qezt, a)= E, oo 1 r'(s0=s, a -a.aaaa т.. and value function Vext, (s) maxa Qext.T (s, a), where T is the episode trajectory and is the horizon.
We adopt a centralized training and decentralized execution paradigm, which has been widely used in multi- aalti-ageett&e deep reinforeement learning (Foerster al. 2016 Lowe et al. 2017 Foerster al., 2018 Rashid et al. (2018). During training, agents are granted access to the states, actions, (intrinsic) rewards, and value functions of other agents, while decentralized execution only requires individual states.
3 INFLUENCE-BASEE BBSSED COORDINATED MULTI- EXPLORATION
Efficient exploration is critical for reinforcement learning, particularly in sparse-reward tasks. In- trinsic motivation (Oudeyer& & Kaplan 2009) is crucial mechanism for behaviour learning since provides the driver of exploration. Therefore, to trade off exploration and exploitation, it is com- mon for RL agent to maximize expected intrinsic reward. Curiosity is one of the extensively-studice intrinsic rewards to encourage an agent explore according to its uncertainty about the environment, which can be measured by model prediction error (Burda et al. 2019 Pathak et al. 2017 Burda et al. 2018) or state visitation count (Bellemare et al. 2016: Tang et al. 2017 2017]Ostrovsk et 2017).
objective of the expected extrinsic reward augmented by the
While such an intrinsic motivation as curiosity drives effective individual exploration, is often not sufficient enough for learning in collaborative multi-agent settings, because it does not take
2

---

Published as a conference paper at ICLR 2020
into account agent interactions. To encourage interactions, propose influence value aims to quantify one agent's s influence on the exploration processes of other agents. Maximizing this value will encourage agents visit interaction points more often through which the agent team reach configurations that are rarely visited by decentralized exploration. In next sections, we will provide two ways formulate the influence value with such properties, leading two exploration strategies.
Thus, for each agent i, our overall optimization objective is:
Ja, | -i, Po] = Vezt," (8o) + Vini. (so) + +.3.19 1
where Po (su) is the initial state distribution, .h; the joint policy excluding that of agent and vrant, (s) is the intrinsic value function of agent i, _= is the influence value, 3 > 0 a weighting term. this paper, we use the following notations:
fs a) = r(s, a) + uu(s;, a:),
(2)
(s) yext (s) + V.int, (s).
(3)
Q7 a) = (s + Σ T(s'ss
(4)
where us(s;, at) curiosity-derived intrinsic reward, (s, a) sum of intrinsic and extrinsic rewards, (s) and QT (8, a) here contain both intrinsic and extrinsic rewards.
3.1 EXPLORATION VIA INFORMATION- ANTORATTONN-HEORETIIC THEORETIC INFLUENCE
One critical problem in our learning framework presented above to define the influence value I. For simplicity, we start with a two-agent case. The first method we propose is to use mutual information between agents' trajectories to measure one agent's influence on other agents' learning processes. Such mutual information can be defined as information gain of one agent's 's state transition given the other's state and action. Without loss of generality, we define it from the perspective of agent 1:
M S1, S1,
A2) =
Σ 8.0.3,E(8.AAA85)
(s, a, s/) [logp" (s/ls, a) log (s// 82, a2)]
(5)
where s (s1, $2) is the joint state, a (01, a2) is the joint action, and St and A; are the random variables of state and action of agent subject to the distribution induced by the joint policy л. So we define | as MI (S); S1, A A2) that captures transition interactions between agents. Optimizing this objective encourages agent to visited critical points where it can influence the transition probability of agent 2. We call such an exploration method exploration via information- theoretic influence (EITI).
Optimizing M1 with respect to the policy parameters 01 of agent I is a little bit challenging, because is expectation with respect distribution that depends 0,. The gradient consists of two terms:
pl (
Ve, MI (S:: S1; 51, A1 A2)
Σ
V (p a, (2)) log
p ( az)
(6)
p pa as 5/) log nd (5/ 02)
Σ
s,
While the second term is an expectation over the trajectory and can be shown to be zero (see Ap- pendix B.T), 1, it unwieldy to deal with the first term because it requires the gradient of the stationary distribution, which depends on the policies and the dynamics the environment. Fortunately, the gradient can still be estimated purely from sampled trajectories by drawing inspiration from the proof of the policy gradient theorem (Sutton et al. 2000).
The resulting policy gradient update is:
Vo, Jo, (1) = (it - V ((+))) Va, log ne, (ails))
(7)
3

---

Published as a conference paper at ICLR 2020
where (st) is an augmented value function of R1
Σx 21'= Pf and
Af = r' + ut + log p(5 2 14 83. aj ab)
(8)
p(32 1s5. ab)
The third term, which we call EITI reward, is 0 when the agents are transition-indeeendenn, i.e., when p(62 p(s2+*1sf |s] 222 ai, ab) p(sh- 1s4 ab), and is positive when si: of increase the probability of agent translating to $2 Therefore, the EITI reward an intrinsic motivation that encourages agent I to visit more frequently the state-action pairs where it can influence the trajectory of agent 2. The estimation of p(s "10 si. af at) and p [s,, a²) are discussed in Appendix C We assume that agents know the states and actions of other agents, but this information is only available during centralized training. When execution, agents only have access their local observations.
3.2 EXPLORATION VIA -HISOEETTII INFLUENCE
Mutual information characterizes the influence of agent's trajectory that of the other and captures interactions between the transition functions the agents. However, it does not provide the value of these interactions identify interactions related to more internal and external rewards (f). To address this issue, we propose exploration via decision-theeretiic influence (EDTI) based on a decision-theorete measure of I, called Value of Interaction (Vol), which disentangles both transition and reward influences. Vol is defined as the expected difference between the action-value function of one agent (e.g., agent 2) and its counterfactual action-valle function without considering the state and action of the other agent (e.g., agent I):
Volz)(15 S1, A1 A2) A2)=
a² (0 a, - Q2i (52, 02 sb) E.
E
where 82) ())(())))) is the expected rewards (including intrinsic rewards) of agent 2 defined as:
(8 a, 22) = (2( +
(10)
and the counterfactual action-value function Q (also includes intrinsic and extrinsic rewards) can be obtained by marginalizing out the state and action of agent 1:
Q21 (s2, a2, s/)
Σ pr (s |2 (2) s2 oj a2) )))+ +y Σ plsssssss aj 02, V. (s').
(11)
Note that the definition of Vol is analogous to that of MI and the difference lies in that p(-)
measures the amount of information while Q measures the action value. Although Vol can be ob- tained by learning Q (s, a) and Q (82, 02) and calculating the difference, propose explicitly marginalize out si and aj utilizing the estimated model transition probability p" (s/ (82, 02) and
p(s/]s, s, a) to get more accurate value estimate (Feinberg al., 2018). The performance of these two formulations are compared in the experiments.
Value functions and V used in Vol contains both expected external rewards and internal rewards, which will not only encourage coordinated exploration by the influence between intrinsic rewards but also filter out meaningless interactions which can not lead to extrinsic reward after intrinsic reward diminishes. To facilitate the optimization of Vol, we rewrite it as an expectation over state- action trajectories.
Vol, (Sg: A, A2) E, 72(s, 1 (s2, 02) + (1- p (66)022,,))) a2) 11--pp333.,100 p(>)(s,a)
V (s')
(12)
where r (82, 02) ) is the counterfactual immediate reward. The detailed proof is deferred to Appendix B.2 From this definition, we can intuitively see how Vol reflects the value of interactions. iz(8, a) ro (32, 02) and 1 pr (s/2122 s2, dz)/p(sá) ( s, a) measure the influence of agent on the immediate reward and the transition function of agent and V (s') serves
scale factor in terms of future value. Only when agent and agent are both transition- and reward-indepent swwrrd-iddependett, i.e.. when p (56182, a2) p( 8, a. and r ($2,00 02) r2(8, a) will Vol equal O. In particular, maximizing
4

---

Published as a conference paper at ICLR 2020
Vol with respect to policy parameters 01 will lead agent to meaningful interaction points, where V/2 (s") is high and $1, a1 can increase the probability that is reached.
In this learning framework, agents initially explore the environment individually driven by its curiosity, during which process they will discover potentially valuable interaction points where they influence the transition function and (intrinsic) rewarding structure of each other. Vol highlights these points and encourages agents to visit these configurations more frequently. As intrinsic re- ward diminishes, Vol can gradually distinguish those interaction points which are necessary get extrinsic rewards.
3.2.1 POLICY OPTIMIZATION WITH Vol
We want to optimize Jø, with respect to the policy parameters 0,, where the most cumbrous term Ve, Vol-iji- For brevity,
consider a two-agent case, e.g., optimizing Vol2i1 with respect to the policy parameters 0j. Directly computing the gradient VoT211 is not stable, because Volya1 contains policy-dependent functions r (52, a2), pr (s/2 82, a2), and V.r (s') (see Eq. 12 To stabilize training, a commonly used technique in deep RL (Mnih et al. 2015). With this approximation, we denote
target functions to approximate these policy-dependent functions, which
(2 a) F2 a) -2 (82, 02) + +7 Σ T(s'|s, (1 (1-
p (0/2 82, (2) ((s5)s,a))
V2 (51, 82). (13)
where pT and 1/2_ are corresponding target functions. As these target functions are only period- ically updated during the learning, their gradients over O1 can be approximately ignored. Therefore, from Eq. 12 we have
Vo, (o (S); A2)
A2)
Σ
(s,
(14)
8,EE(S,A)
Similar to the calculation of Ve, MI, we get the gradient at every step (see Appendix B.3 for proof):
Va, Jo, (1) ( (s.)) Va, log Te, (ails)),
(15)
where (st) is an augmented value function regressed towards R? Eb of' and
f1 r² wi + 3 ub + 7 (1
(0 (82 1o ab))
p
V/ Vz (5f 1 s6t12
(16)
p(s2* |s| 8/2 aj ab)
We call u¹ +7 7 (1
p (a (2))
Vo (olt2, =1 the EDTT reward.
pla 1
3.3 DISCUSSIONS
Scale to Large Settings: For cases with more than two agents, the Vol of agent i on other agents can be defined similarly Eq. [ which is annotated with Vol (S", A,|S-,, A A-i). where S-, and A-; are the state and action sets of all agents other than agent i. In practice, agents teraction can often be decomposed to pairwise interaction so Vol", A, A-) is well approximated by the sum of values of pairwise value of interaction:
A,S
Σ JEN
S,,
(17)
Relationship between EITI and EDTI: EITI and EDTI gradient updates are obtained by information- and becision-theoretical influence respectively. Therefore, is nontrivial to derive that part of the EDTI reward is lower bound of the EITT reward:
p(s' 1|s_ ami)
a)
S log p p(5'_1s-i,, a)))
Vs, s'
(18)
p(s'_,88,
18, a)
which easily follows given that log 2 1/2 for Vx > This draws connection between EITI and EDTI reward.
5

---

Published as a conference paper at ICLR 2020
Table 1: Baseline algorithms. The third column is the reward used train the value func- tion of PPO. u, and vhen are curiosity about individual state 8, and global state 8, Ti = log (p(s',,ss a) a)/p(s',,s i, a)). T2
p(sss'' i.a 3/pps's a), and AQ ((8. a
Q-i(s, a) - Q-i(s-i,a-2) Social influence (Jaques et al. 2018 and COMA (Foerster et al. 2018 are augmented with curiosity.
Alg.
Reward
Description
EITI
+ u4 ST1
tnfouence-theoreticc influence
Ours
EDTI
+ u + 3(u 1044+990 +T24)
Decision-theoretic influence
Other
random
r
Pure PPO
Exploration
cen
r + Ueen
Decentralized PPO with cen curiosity
dec
+
Decentralized PPO with dec curiosity Centralized PPO with cen curiosity
Methods
cen_control
r + Ween
Linfflunnce
r + u, + Bu.s
Disentangle reward interaction Use other agents' value functions PPO with shared V and cen curiosity
Plus
+ U; + 3V.,
Ablations
shared critic
r + theen
Q-Q
+ us + (AQ-:(ss
EDTI without explicit counterfactual
social
By Jaques al. (2018)
Related
COMA
By Foerster ct al. (0188)
Works
Multi
By Iqbal & Sha (0199
Comparing EDTI to Centralized Methods: Different from a centralized method which directly includes value functions of other agents in the optimization objective, (i.e., by setting total reward
A = r + u, + $(u=; + >V-4), which is called plusV henceforth), the EDTI reward for agent i disentangles its contributions difference important for quantifying influence because the value another agent does not just contain the contributions from agent but also those of itself and third-party agents. Therefore, EDTI is a kind of intrinsic reward assignment. Our experiments in the next section will compare the performance of plusV against our methods, which verify the importance of the intrinsic reward assignment.
values of another agents using counterfactual formulation. This
4 EXPERIMENTAL RESULTS
Our experiments aim answer the following questions: (1) Can EITI and EDTI rewards capture interaction points? If they can, how do these points change throughout exploration? (2) Can exploit- ing these interaction points facilitate exploration and learning performance? (3) Can EDTI filter out interaction points that are not related to environmental rewards? (4) What if only reward influence between agents are disentangled? We evaluate our approach on of multi-agent tasks with sparse rewards based on discrete version of multi-agent particle world environment (Lowe et al. (017). PPO (Schulman al., 2017) is used the underlying algorithm. For evaluation, all experiments are carried out with 5 different random seeds and results are shown with 95% confidence interval. Demonstrative videos are available online.
Baselines We compare our methods with various baselines shown in Table In particular, we carry out the following ablation studies: i) iiiffuunnee disentangles immediate reward influence between agents, (derivation of the associated augmented reward can be found in Appendix B.4] Reward influ- ence in long term not considered because inevitably involves transition interactions) ii) PlusV as described in Sec. 3.3] iii) Shared_critt _rriti uses decentralized PPO agents with shared centralized value function and thus is cooperative version of MADDPG (Lowe et al.) (0017) augmented with intrin- sic reward of curiosity. iv) Q-Q is similar EDTI but without explicit counterfactual formulation, as described in Sec. 3.2 We also note that EITT is an ablation of EDTT which considers transition interactions. PlusV, shared_crine critic, Q-Q, and cen_con contoolol have access global or other agents' value functions during training. When execution, all the methods except cen_control only require local state.
https://sites: httpss//sitees.goglleoooo////// http://w..pogggl.cccoo///////eee wwwp:/uwweneeeedddeeeeeeeaa meaaeddm--exlllrationn

---

Published as a conference paper at ICLR 2020
Performance Ablations pass
agent A
switch 2
agent A
switch 2
door
Team Performance
800
agent B
agent
600
Play
share-_orik
switch
94
door
door 2
200
switch
switch
switch
door 3
-200
Updates
8000
Figure 1: Didactic examples. Left: task Pass. Two agents starting the upper-left corner are only rewarded when both of them reach the other room through the door, which will open only when at least of the switches is occupied by one or more agents. Middle: Secret-Room. An extension of Pass with 4 rooms and switches. When the switch 1 is occupied, all the three doors turn open. And the three switches on the right only control the door of its room. The agents need reach the upper right room to achieve any reward. Right: comparison of our methods with ablations on Pass.
4.1 DIDACTIC EXAMPLES
We present two didactic examples of multi-agent cooperation tasks with sparse reward to explain how EITI and EDTI work. The first didactic example consists of a 30 x 30 maze with two rooms and a door with two switches (Fig. [ left). In the optimal strategy, one agent should first step on switch help the other agent pass the door, and then the agent that has already reached the right half should further go to switch to bring the remaining agent in. There are two pairs of interaction points in this task: (switch door) and (switch 2, door), i.e., transition probability of the agent near door is determined by whether another agent is on one of the switch.
Fig. right and Fig. top show the learning curves of our methods and all the baselines, among which EITI, EDTI, r influence, Multi, and centralized control can learn the winning strategy and ours learn much more efficiently. Fig. bbottom gives a possible explanation why our methods work. EITI and EDTI rewards successfully highlight the interaction points (before 100 and 2100 updates, respectively). Agents are encouraged explore these configurations more frequently and thus have better chance to learn the goal strategy. EDTI reward considers the value function of the other agent, so converges slower than the EITI reward. In contrast, directly adding the other agent's intrinsic rewards and value functions is noisy (see "plusV reward") and confuses the agent because these contain the effect the other agent's 's exploration. As for centralized control, global curiosity encourages agents try all possible configurations, so can find environmental rewards in most tasks. However, visiting all configurations without bias renders it inefficient - external rewards begin dominate the behaviors of agents after 7000 updates even with the help of centralized learning algorithm. Our methods use the same information as centralized exploration but take advantages of agents' interactions accelerate exploration.
In order to evaluate whether EDTI can help filter out noisy interaction points and accelerate explo- ration, we conduct experiment, in a second didactic task (see Fig. I middle). also navigation task in 25 x 25 maze where agents are rewarded for being in a goal room. However, in this exper- iment, we consider case where there are four rooms and the upper right one is attached to reward. This task contains 6 pairs of interaction points (switch with each of the doors, each switch with the door of the same room), but only two of them are related to external rewards, i.e., (switch 1, door 1) and (switch 2, door 1). As Fig. right shows, EITI agents treat three doors equally even after 7400 updates (see Fig. righht 7400 updates, top row). In comparison, although EDTI reward suffers from noise in the beginning, it clearly highlight two pairs of valuable interaction points (see Figghti 7400 updates, bottom row) as intrinsic reward diminishes. This can explain why EDTI outperforms EITI (Fig. left).

---

Published as a conference paper at ICLR 2020
Phase Learning Dynamics
Reward
Phase Exploration by exploiting interaction points
Phase Oatimel Policy
1000
2100
7000
800
600
random
can
dec
contro
Influacce
200
-200
7000
Updates
Agent Received
Agent 2 Received
Agent 1 Received
Agent Received
Agent Received
Agent 2 Received
0.06
0.06
0.26
EITI
Reward
0.03
0.13
0.06
0.06
0.26
EDTI Reward
0.03
0.03
0.13
0.00
0.00
0.00
4.00
5.00
PlusV Reward
0.40
2.00
2.50
0.000
0.00
0..00
Figure 2: Development of performance of our methods compared to baselines and intrinsic reward terms of EITI, EDTI, and PlusV over the training period of 9000 PPO updates segmented into three phases. "Team Reward" shows averaged team reward gained in episode, with maximum of 1000. shows that only EITI, EDTI, and centralized control and Multi can learn the strategy during this stage. "EITI reward", "EDTI reward", and "plus reward" demonstrate the evolving of correspond- ing intrinsic rewards.
Team Performance
400
2000
4000
6000
Agent I
Agent
Agent
Agent
Agent
Agont
Updates
100 Updates
2900 Updates
7400 Updates
Figure 3: Left: performance comparison between EDTI and EITI Secret-Room over 7400 PPO updates. Right: EITI and EDTI terms of two agents after 100, 2900, and 7400 updates.
push-box
island
large-island
Team Parformance
Performance
Team Performance
EDTI
75
100
inffuencce plusv shared_critic
50
50-
Q-Q
2500
5000 Updates
7500
25000
5000
7500
1000
2000 3000 4000
Updates
Up cates
Figure 4: Comparison our methods against ablations for Push-Box, Island, and Large-Island. Comparison with baselines is shown in Fig. g in Appendix D
8

---

Published as a conference paper at ICLR 2020
4.2 EXPLORATION IN COMPLEX TASKS
Next, we evaluate the performance of our methods on more complex tasks. To this end, we use three sparse reward cooperative multi-agent tasks depicted in Fig. of Appendix DD and analyzed below. Details of implementation and experiment settings are also described in Appendix D
Push-Box: A 15 15 room is populated with agents and box. Agents need to push the box to the wall in 300 environment steps to get reward of 1000. However, the box is so heavy that only when two agents push it in the same direction at the same time can it be moved a grid. Agents need to coordinate their positions and actions for multiple steps to earn reward. The purpose of this task is to demonstrate that EITI and EDTI can explore long-term cooperative strategy.
Island: This task is a modified version of the classic Stag Hunt game (Peysakhovich & Lerer 2018) where two agents roam a 10 x 10 island populated with 9 treasures and a random walking beast for 300 environment steps. Agents can collect treasure by stepping on it to get team reward of 10 or, by attacking the beast within their attack range, capture it for a reward of 300. The beast would also attack the agents when they are too close. The beast and agent have maximum energy of and 5 respectively, which will be subtracted by 1 every time attacked. Therefore, an agent is too weak to beat the beast alone and they have to cooperate. In order learn optimal strategy in this task, one method has to keep exploring after sub-optimal external rewards are found.
Large-Island: Similar Island but with more agents (4), more treasures (16), and a beast with more energy (16) and a higher reward (600) for being caught. This task aims to demonstrate feasibility of our methods in cases with more than 2 agents.
Push-Box requires agents to take coordinated actions at certain positions for multiple steps to get rewarded. Therefore, this task is particularly challenging and all the baselines struggle to earn any reward (Fig. 3 left and Fig. 8 left). Our methods are considerably more successful because interaction happens when the box is moved - agents remain unmoved when they push the box alone but will move by grid if push it together. In this way, EITI and EDTT agents are rewarded intrinsically to move the box and thus are able to quickly find the optimal policy.
In the Island task, collecting treasures is a aasily-attainable local optimal. However, efficient trea- sures collecting requires the agents to spread on the island. This leads to a situation where attempting to attack the beast seems bad choice since it is highly possible that agents will be exposed to the beast's attack alone. They have to give up profitable spreading strategy and take the risk of being killed to discover that if they attack the beast collectively for several timesteps, they will get much more rewards. Our methods help solve this challenge by giving agents intrinsic incentives to appear together in the attack range of the beast, where they have indirect interactions (health is part of the state and it decreases slower when the two are attacked alternatively). Fig. Iin Appendix D demon- strates that our methods learn catch the beast quickly, and thus have better performance (Fig. right).
Finally, outperformance of our methods on Large-Island proves that they can successfully handle cases with more than two agents.
In summary, both of our methods are able to facilitate effective exploration on all the tasks by exploiting interactions. EITI outperforms EDTI in scenarios where all interaction points align with extrinsic rewards. On other tasks, EDTI performs better than EITT due its ability to filter out interaction points that can not lead to more values.
We also study EDTI with only intrinsic rewards, discussion and results are included in Appendix
5 RELATED WORKS
Single-agent exploration achieves conspicuous success recently. Provably efficient methods are pro- posed, such as upper confidence bound (UCB) (Jaksch et al.) 2010 Azar et al., 2017 Jin et al. 2018) and posterior sampling for reinforcement learning (PSRL) Strrnss] 2000 Osband al.) 2013 Osband & Van Roy 2016: Agrawal & Jia 2017). Given that these methods do not scale well to large or continuous settings, another line of research has been focusing
certoosty-driivee explo- ration (Schmidhuber) [991; Chentanez et al. 20055] Oudeyer et al.) 2007; (arto 2013 Bellemare
et al. 2016, Pathak al. 2017 Ostrovski al. 2017). and have shown impressive results (Burda

---

Published as a conference paper at ICLR 2020
et al. 2019
2018:
Hyoungseok Kim 2019). In addition, methods based variational informa-
tion maximization (oouhoooft et 2016 Barron et al. 2018) and mutual information (Rubin et al.
2012 Still & Precup 2012 Salge et al. Mohameed & Rezende 2015 Hyoungscok Kim 2019
have been proposed for single-agent intrinsically motivated exploration.
Although multi-agent reinforcement learning (MARL) has been making significant progresses in
recent years (Foerster et al.] 2018 Lowe et al. [2017: Wen et al. [019]] Iqbal & Sha 2019a [Sune-
hag et al., 2018||Son et al. [019;; Rashid et al. (0188) less attention has been drawn multi-agent
exploration. Dimakopoulou & Van Roy| (2018) and Dimakopoulou et al. (2018) propose poste-
rior sampling methods for exploration of concurrent reinforcement learning in coverage problems, Bargiacchi et al. (2018) presents a multi-agent upper confidence exploration method for repeated single-stage problems, and Sha (219b) investigates methods to combine several decentral- ized curiosity-driven exploration strategies. All these works focus on transitioniindepeddee set- tings. Another Bayesian exploration approach has been proposed for learning in stateless repeated games (Chalkiadakis & Boutilier 2003). In contrast, this paper focuses more general multi-agent sequential decision making problems with complex reward dependencies and transition interactions among agents.
In the literature of MARL, COMA (Foerster et al. 2018) shares some similarity with our decision- theoretic EDTI approach in that both of them use the idea of counterfactual formulations. However, they are quite different in terms of definition and optimization: (1) conceptually, EDTI measures the influence of one agent on the value functions of other agents, while COMA quantifies individual contribution to the team value; (2) EDTI is defined on counterfactual Q-value over state-action pairs of other agents given its own state-action pair, while COMA uses the counterfactual Q-value just over its own action without considering state information, which is critical for exploration; (3) we explicitly derive the gradients for optimizing EDTI influence for coordinated exploration in the policy gradient framework, which provides more accurate feedback. while COMA uses the counterfactual Q value as a critic. Another line of relevant works (Oliehoek et al.) 2012 de Castro) et al. 2019) propose influence-basee based abstraction to predict influence sources to help local decision making of agents. In contrast, this paper presents two novel approaches that quantify and maximize the influence between agents for enabling coordinated multi-agent exploration.
In addition, some previous MARL work has also studied intrinsic rewards. One notably relevant work Jsquus et al. 2018), ), which models the social influence of one agent on other agents' policies. In contrast, EITI measures the influence of one agent on the transition dynamics of other agents. Accompanying this distinction, EITI includes states of agents in the calculation of influence while social influence dos not. Apart from that, the optimization methods are also different we directly derive the gradients of mutual information and incorporate its optimization in the policy gradient framework, while Jaques et al. (2018) adds social influence reward to the immediate environmental whileJaques
reward for training policies. Hughes al. (2018) proposes an inequality aversion reward for learning in intertemporal social dilemmas. [Strouse et al. (2088) uses mutual information between goal and states or actions as an intrinsic reward train the agent to share or hide their intentions.
CLOSING REMARKS
In this paper, we study the multi-agent exploration problem and propose two influence-basee meth- ods that exploits the interaction structure. These methods are based on two interaction measures, MI and Value of Interaction (Vol), which respectively measure the amount and value of one agent's influence on the other agents' exploration processes. These two measures can be best regraded as exploration bonus distribution. We also propose an optimization method in the policy gradient framework, which enables agents to achieve coordinated exploration in a decentralized manner and optimize team performance.
REFERENCES
Shipra Agrawal and Randy Jia. Optimistic posterior sampling for reinforcement learning: worst-case regret bounds. In Advances in Neural Information Processing Systems, pp. 1184-1194, 2017.
Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax regret bounds for reinforce- ment learning. I Proceedings of the 34th International Conference on Machine Learning- Volume
10

---

Published as a conference paper at ICLR 2020
70, pp. 263 272. JMLR. org, 2017.
Eugenio Bargiacchi, Timothy Verstraeten, Diederik Roijers, Ann Nowé, and Hado Hasselt. Learning to coordinate with coordination graphs in repeated single-stage multi-agent decision problems. In International Conference Machine Learning, pp. 491-499, 2018.
Trevor Barron, Oliver Obst, and Heni Ben Amor. Information maximizing exploration with latent dynamies model. arXiv preprint /rXiv:/8044
2018.
Andrew G Barto. Intrinsic motivation and reinforcement learning. In Intrinsically motivated learn- ing in natural and artificial systems, pp. 17-47. Springer, 2013.
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. arXiv preprint arXiv: / 12894, 2018.
Yuri Burda, Harri Edwards, Deepak Pathak, Amos Storkey, Trevor Darrell, and Alexei A Efros. Large-scale study of curiosity-driver learning. International Conference on Learning Represen- fations, 2019.
Yongcan Cao, Wenwu Yu, Wei Ren, and Guanrong Chen. An overview of recent progress in the study of distributed multi-agent coordination. IEEE Transactions on Industrial informatics, 9(1): 427-438, 2012.
Georgios Chalkiadakis and Craig Boutilier. Coordination in multiagent reinforcement learning: A bayesian approach. In Proceedings of the Second International Joint Conference on Au- tonomous Agents and Multiagent Systems, AAMAS '03, pp. 709-716, New York, NY, USA, 2003. ACM. ISBN 1-58113 13-68-88. doi: 0011455866075.8806666 URL http: acm.
org/ 10. 1el.l1145/88800 0000000555888888989 860689
Nuttapong Chentanez, Andrew G Barto, and Satinder P Singh. Intrinsically motivated reinforcement learning. Advances in neural information processing systems, pp. 1281-1288, 2005.
Miguel Suau de Castro, Elena Congeduti, Rolf AN Starre, Aleksander Czechowski, and Frans A Oliehoek. Influence-based abstraction in deep reinforcement learning. In Adaptive, learning agents workshop (Vol. 2019.
Prafulla Dhariwal, Christopher Hesse, Oleg Klimov, Alex Nichol, Matthias Plappert, Alec Radford,
John Schulman, Szymon Sidor, Yuhuai Wu, and Peter Zhokhov. Openai baselines. https:
h/gitt/ub.ccom//peeeee http:/ooooopppaaaaaaaaaee ines, 2017.
Maria Dimakopoulou and Benjamin Van Roy. Coordinated exploration in concurrent reinforcement
learning. In International Conference Machine Learning, pp. 1270-1278 2018.
Maria Dimakopoulou, Ian Osband, and Benjamin Van Roy. Scalable coordinated exploration in concurrent reinforcement learning. In Advances in Neural Information Processing Systems, pp- 4219-4227, 2018.
Vladimir Feinberg, Alvin Wan, Ion Stoica, Michael I Jordan, Joseph E Gonzalez, and Sergey Levine. Model-based value estimation for efficient model-free reinforcement learning. arXiv preprint arXiv:1803.00101, 2018
Carlos Florensa, Yan Duan, and Pieter Abbeel. Stochastic neural networks for hierarchical rein- forcement learning, arXiv preprint N.KV::1704000122 2017.
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 N Foerster, Gregory Farquhar, Triantafyllos Afouras, Nantas Nardelli, and Shimon Whiteson. Counterfactual multi-agent policy gradients. In Thirty-Second AAAI Conference on Artificial Intelligence, 2018.
11

---

Published as a conference paper at ICLR 2020
Charles W Fox and Stephen J Roberts. A tutorial on variational bayesian inference. Artificial intelligence review, 38(2):85 95,885995,,0 2012.
Abhishek Gupta, Russell Mendonca, YuXuan Liu, Pieter Abbeel, and Sergey Levine. Meta- reinforcement learning of structured exploration strategies. In Advances in Neural Information Processing Systems, pp. 5302-5311, 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.
Edward Hughes, Joel Z Leibo, Matthew Phillips, Karl Tuyls, Edgar Duefiez-Guzman, Anto- nio García Castañeda, lain Dunning, Tina Zhu, Kevin McKee, Raphael Koster, al. Inequity aversion improves cooperation in intertemporal social dilemmas. In Advances in Neural Informa- fion Processing Systems, pp. 1330-3340, 2018.
Yeonwoo Jeong Sergey Levine Hyun Oh Song Hyoungseok Kim, Jaekyeom Kim. Emi: Explo- ration with mutual information. In Proceedings of the 36th International Conference on Machine Learning. JMLR. org, 2019.
Shariq Iqbal and Fei Sha. Actor-attention-crittee for multi-agent reinforcement learning. In Interna- tional Conference on Machine Learning pp. 2961-2970, 2019a.
Shariq Iqbal and Fei Sha. Coordinated exploration via intrinsic rewards for multi-agent reinforce- ment learning. arXiv preprint arXiv: 1905. 12127, 1202, 2019b.
Thomas Jaksch, Ronald Ortner, and Peter Auer. Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research, 11 1466))):153311600 2010.
Natasha Jaques, Angeliki Lazaridou, Edward Hughes, Caglar Gulcehre, Pedro A Ortega, DJ Strouse, Joel Z Leibo, and Nando de Freitas. Intrinsic social motivation via causal influence multi-agent rl. arXiv preprint arXiv:/810.0880 1810.08677, 2018.
Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael Jordan. Is q-learning provably effi- cient? In Advances Neural Information Processing Systems, pp. 4863-4873, 2018
Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. Computer Science, 2014.
Ryan Lowe, Yi Wu, Aviv Tamar, Jean Harb, OpenAl Pieter Abbeel, and Igor Mordatch. Multi-agent actor-critic for mixed cooperative-comppettiee environments. In Advances in Neural Information Processing Systems, pp. 6379-6390, 2017.
Piotr Mirowski, Razvan Pascanu, Fabio Viola, Hubert Soyer, Andrew Ballard, Andrea Banino, Misha Denil, Ross Goroshin, Laurent Sifre, Koray Kavukcuoglu, et al. Learning to navigate in complex environments. arXiv preprinl arXiv:1611.0367. 2016.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Mare G Belle- mare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning, Nature, 518(7540):529, 2015.
Shakir Mohamed and Danilo Jimenez Rezende. Variational information maximisation for intrinsi- cally motivated reinforcement learning. In Advances in neural information processing systems, pp. 2125-2133, 2015.
Ann Nowé, Peter Vrancx, and Yann-Michaël De Hauwere. Game theory and multi-agent reinforce- ment learning. In Reinforcement Learning, pp. 441-470. Springer, 2012.
Frans Adriaan Oliehoek, Stefan Witwicki, and Leslie Pack Kaelbling, Influence-based abstraction for multiagent systems. In Swehty-Sixth AAAI Conference on Artificial Intelligence, 2012.
OpenAL. Openai five. httppss/bblog.cpeeaa..coo
2018.
Ian Osband and Benjamin Van Roy. On lower bounds for regret in reinforcement learning. arXiv preprint arXiv: /608 060.00278, 2016.
12

---

Published as a conference paper at ICLR 2020
Ian Osband, Daniel Russo, and Benjamin Van Roy. (more) efficient reinforcement learning via posterior sampling. Advances in Neural Information Processing Systems, pp. 3003-3011, 2013.
Georg Ostrovski, Mare G 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-Voile Volume 70, pp. 2721-2730. JMLR. org, 2017.
Pierre-Yver Oudeyer and Frederic Kaplan. What is intrinsic motivation? a typology of computa- tional approaches. Frontiers in neurorobotics, 1:6, 2009.
Pierre Yves Oudeyer, Frdric Kaplan, and Verena V Hafner. Intrinsic motivation systems for au- tonomous mental development. IEEE transactions on evolutionary computation, 11(2):255-286, 2007.
Deepak Pathak, Pulkit Agrawal, Alexei A Efros, and Trevor Darrell. Curiosity-driven exploration by sulf-super prediction. In International Conference on Machine Learning, pp. 2778-2783 2017.
Deepak Pathak, Parsa Mahmoudieh, Guanghao Luo, Pulkit Agrawal, Dian Chen, Yide Shentu, Evan Shelhamer, Jitendra Malik, Alexei A Efros, and Trevor Darrell. Zero-shot visual imitation. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition Workshops, pp. 1050-2053 2018
Alexander Peysakhovich and Adam Lerer. Prosocial learning agents solve generalized stag hunts better than selfish ones. In Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems, pp. 2043-2044. International Foundation for Autonomous Agents and Multiagent Systems, 2018.
Tabish Rashid, Mikayel Samvelyan, Christian Schroeder Witt, Gregory Farquhar, Jakob Foerster, and Shimon Whiteson. Qmix: Monotonic value function factorisation for deep augtt rein- forcement learning. In International Conference on Machine Learning, pp. 4292-4300 2018.
Martin Riedmiller, Roland Hafner, Thomas Lampe, Michael Neunert, Jonas Degrave, Tom Van de Wiele, Volodymyr Mnih, Nicolas Heess, and Jost Tobias Springenberg. Learning by playing- solving sparse reward tasks from scratch. arXiv preprint arXiv:1802. 10567, 2018.
Jonathan Rubin, Ohad Shamir, and Naftali Tishby. Trading value and information in mdps. In Decision Making with Imperfect Decision Makers, pp. 57-74. Springer, 2012.
Christoph Salge, Comellus Glackin, and Daniel Polani. Changing the environment based em- powerment as intrinsic motivation. Entropy, 16(5):2799-2819, 2014.
Tom Schaul, John Quan, Ioannis Antonoglou, and David Silver. Prioritized experience replay, arXiv preprint arXiv:1511.05995 2015.
Jürgen Schmidhuber. A possibility for implementing curiosity and boredom in model-building neu- ral controllers. In Proc. of the international conference on simulation of adaptive behavior: From animals to animats, pp. 222-227, 1991.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv: orXiv:/707.066 1707.06347, 2017.
Kyunghwan Son, Daewoo Kim, Wan Ju Kang, David Earl Hostallero, and Yung Yi. Qtran: Learning to factorize with transformation for cooperative multi-agent reinforcement learning. In Interna- tional Conference on Machine Learning, pp. 5887-5896, 2019.
Susanne Still and Doina Precup. An information--hhoreee approach to curiosity-driven reinforce- ment learning. Theory in Biosciences, 131(3):19--148, 2012.
Malcolm Strens. A bayesian framework for reinforcement learning. In ICML, volume 2000, pp- 943-950, 2000.
DJ Strouse, Max Kleiman- Weiner, Josh Tenenbaum, Matt Botvinick, and David J Schwab. Learning to share and hide intentions using information regularization. In Advances in Neural Information Processing Systems, pp. (0249-10255) 2018.
13

---

Published as a conference paper at ICLR 2020
Peter Sunehag, Guy Lever, Audrunas Gruslys, Wojciech Marian Czarnecki, Vinicius Zambaldi, Max Jaderberg, Mare Lanctot, Nicolas Sonnerat, Joel Leibo, Karl Tuyls, et al. Velossieoonnooition networks for cooperative multi-agent learning based team reward. In Proceedings of the 17th International Conference on Autonomous Agents and MultiA gent Systems, pp. 2085-2087. Inter- national Foundation for Autonomous Agents and Multiagent Systems, 2018.
Richard Sutton, David McAllester, Satinder P Singh, and Yishay Mansour. Policy gradient methods for reinforcement learning with function approximation. In Advances in neural informa- fion processing systems, pp. 1057-1063, 2000.
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.
Ying Wen, Yaodong Yang, Rui Luo, Jun Wang, and Wei Pan. Probabilistic recursive reasoning for multi-agent reinforcement learning. In International Conference on Learning Representations, 2019.
Yi Wu, Yuxin Wu, Georgia Gkioxari, and Yuandong Tian. Building generalizable agents with realistic and rich 3d environment. arXiv preprint arXiv: 020209, 2018.
Yuxin Wu and Yuandong Tian. Training agent for first-person shooter game with actor-critic cur- riculum learning. ICLR, 2016.
Chongjie Zhang and Victor Lesser. Coordinated multi-agent reinforcement learning in networked distributed pomdps. In Twenty-Fifth AAAI Conference on Artificial Intelligence, 2011.
14

---

Published as a conference paper at ICLR 2020
APPENDIX
A INTRINSIC EDTI
Value of interaction (Vol) captures both transition and reward influence among agents, and it facil- itates coordinated exploration by encouraging interactions. Vol contains influence of both intrinsic and extrinsic rewards. Since single-agent literature has studied purely auriosity-driver learning and gets cutting-edge performance (Burda et al. 2019), is interesting to investigate the performance of Vol given only intrinsic rewards.
Intuitively, intrinsic Vol distributes individual curiosity among team members and facilitates explo- ration by encouraging agents to help each other to reach under-explored states. Specifically, the following objective:
Jo. [TT m- Pol Vext, (so) Viint. (so) + B Vol
(19)
i/s
The corresponding augmented reward is:
* = rt + u
u/² + (1
(52 |s2. az)
1/2 V . 2btt
(of
(20)
p0s52*1 1s| 2b2 ai ai))
We use this method (intrinsic EDTI) to train the agents on Pass, Secret-Room, Push-Box, and Island and show the results in Fig.
B MATHEMATICAL DETAILS
B.1 GRADIENT OF MUTUAL INFORMATION
To encourage agents to exert influence on transitions of other agents, we optimize mutual informa- tion between agent's trajectories. In particular, in the following, we show that term 2 in Eq. 6 is always zero.
(=,,,,,,))V log p(s s, pd (s/ 82, 02)
T2
Σ
(21)
8, (.
Σ p" a Vo, log (6/2 182,
(22)
s,a.s/
Vo, (p (26
Σ
(8, a 2
(23)
ndt (5//1882,
8.0.8/
( a 8/))
Von
Σ
1862222. az aisssssssle a2) (ailsi)
(24)
2 $2, (2))
8,a,5
sj.oj
p² a 8/)
Σ
Σ
(ailss)
(25)
( 82, a2
8
siaa
(82, 02 122
Σ
Σ
p( f0, 02 si af) a2) ne (ailsi)
(26)
px (5/2 82, a2)
$2
si.ai
Σ
nd (52, 02)
Σ
p(5/ (2, 02 af
ne, (ails))
(27)
82,02.3/
(82, (2))
Σ
p(3 12 02 Va, To, (a, Σ p( 02 00.0s.i..0 aj)
(28)
$2.02
Σ
nd (82, 02)
Σ
p(s 02
Vo, Te, (ailst)
Σ
p(sh 82, 02 $7 af)
(29)
$2.02
$7.07
%
15

---

Published as a conference paper at ICLR 2020
pass
secret-room
Team Performance
800
Team Performance
800
600
600
400
400
200
200
0
0
0
2500
5000
7500
2000
4000
6000
Updates
Updates
push-box
island
200
Team Performance
100
Team Performance
150
75
100
50
50
EITI
25
EDTI
0
EDTI-intrinsic
0
0
2500
5000 Updates
7500
2500
5000
7500
Updates
Figure 5: Performance of intrinsic EDTI in comparison with EITI and EDTI on Pass, Secret-Room, Push-Bac Box, and Island.
Σ (s2, a2)
Σ
p(si]32 (2) Vo, Σ no, (ails))
(30)
s1
Σ
p" ($2, a2)
Σ
p(s 02 Vo.
(31)
$2.02
si
0
(32)
B.2 DEFINITION Value of Interaction
To capture both transition and reward interactions between agents and thereby achieve intrinsic re- ward distribution, we propose a decision-theorete measure called Value of Interaction. We start from 2-agent cases and the following theorem gives the definition of V Volgi in the form of an ex- pectation over trajectories, which is especially helpful in the derivation of the EDTI policy gradient update shown Eq. 15
Theorem 1. Value of Interaction of agent I on agent 2 is:
Volz (Sy S1, A, A2) = E, (2( - (52, a2) + (1- pa pT ((5)) 02)
V (8
p( a)
(33)
where F3 (82, u2) is the counterfactual immediate reward.
Volgi1 can be defined similarly. To lighten notation in the proof, we define
V (s $1. S2, a1 02) = Σ p(s $1, 82, a1, a2 1 (5), 1/))
(34)
16

---

Published as a conference paper at ICLR 2020
12 (52, (2)
Σ p" (12. 82, ai,
(35)
sj.0i
V/2 (sg) 02) = Σ (s a2)
Σ
p(s 82, q. 02 v2 s2).
(36)
si
We first prove Lemma] 1 which is used in the proof of Theorem 1 Lemma 1.
Σ
p" 82, 82, 02)7
Σ p(2/|1) 82, a1 V2 (52])2,0)) 02)
(37)
$1:82/01:02
Dz (522 a2)
Σ $1,52;01,02
82,
Σ
a2) (21 p(s/
[ $1, 82, 01, 02) V22 (51, 12))
$1.02
Proof.
Σ $1,
s2, 01
(38)
$/2
Σ 88, $1:
Σ
(39)
$/
Σ
p" (st af
$2, 02) Σ S2
(40)
=
Σ 82, Σ
(41)
01,
T( s1s1. aj 02)
Σ
(si
aj 18,82,2,2 U2)
V/2¹ (61, 8/2)
(42)
p6,2 ii 82, a2.0 (2)
T 181 82, 01, (1)
=
Σ 82, 01,001
Σ
(43)
01,22,01,02
Vi2 (5)1)22)
(44)
$1.0i
Σ
Σ
(45)
$1
pº ( 82, a2)
V.7 (51,
(46)
p 81 82, a1, (2)
We now give the proof of Theorem II
Proof.
Voly (S/:
S1, A2)
(47)
Σ
as) 2/)
as, 121 0z x2)
(48)
(.
Σ
02) - 5 a2) +
(49)
81.22.01.42
?
Σ
- ( 02))
(561
(50)
Σ
04 02) - (s2, a2) +
(51)
01.82,01,02
17

---

Published as a conference paper at ICLR 2020
(5 82 a2)
7 Σ T(s $2,
$2, 02,
1/2T (5/((5),, (s), (2))
(Lemma 1) (52)
p $1. $2 a1 a2)
E a2(8,0) - (82 + (1 (1- p0 (5/ 82, (2)
1/2 (s')
(53)
p( 8, a)
B.3 CALCULATING GRADIENT OF Vol
we propose to In order to optimize Vol with respect to the parameters of agent policy, in Sec. 3.2.1 target function and get:
Vo, Vo (52; S1, A1 A2)
Σ
(Vo,p" (F2(s,))) (52,
a.eE(S.A)
P p(s/
T(s'ss,a)
V2 (5 s6)].
(54)
We prove that Eea (Vo,p"(s, (82, a2) is 0 in the following lemma.
Lemma 2.
Σ
82, a1, (2) (s2, a2) = O.
(55)
81,82.01.02
Proof. Similar to the way that policy gradient theorem was proved by Sutton et al. (2000).
Σ (Vo (81, 82, 01, (2,))) Fz (82, 02)
(56)
$1,53,41,00
Vo,
Σ
(51 $2 02 a2)
(57)
81,82,01,02
Σ
do(s)
Vo,
(aj, ab 1b)) T(s]+1 ,52 15 at 82 ab)r (52 ob)
(58)
t=
Σ
do 0
II
n (aa o51s sb) (Vo, log π agls,,
(59)
9
T( .2
11 of
(52 a5)
(60)
Σ
p" (s1 82, 01 02) (Vo a2|s1 Fo (82, a2)
(61)
Σ
p" (51, (s, a1 02) (o. (ag s2)) i5 (s2,
(62))
$1,32,01.02
Σ
pr
(82,00 02)
Σ
DT (s1, 02) (Vo, ( 82) Frz (82,
(63)
$2.43
$1.01
Σ
p"
S2,, a2)
(s2, 02)
Σ
p" (s (s1, 01ls2 02) (e,, log T (1 s2))
(64)
$2.02
$1.01
n (81, (82,
=
Σ
p
82, 15
(82, 02)
(Vo, ((r
(65)
π [aaiss188 82)
$2.02
$1.01
p (s1 S2, 02) (a1 S2)
Σ 52.4g
p" (82
(82, 02)
(Ve, (a1181 82)) (66)
(a) 81)
$1.01
Σ
p
S2, Fz
(s2, az)
822
0g (a) 82)
(Vo ( sz))
(67)
n (ag 82)
$2.00 02
81.01
18

---

Published as a conference paper at ICLR 2020
Σ v" (2)r (52, 02)
Σ p" (81182, 02)
(Vo,
(68)
#2:02
$1
Σ p (52, (52, 02)
12) (52, 02)
Σ p" (51 a2) Σ (Vo. (a11)111100
(69)
02
Σ p" (82, 02) (82, 02) Σ p" (81 (81
Vo Σ
π (211811,82)
(70)
$2.02
41
Σ p" (82, 22 (82, 02) Σ
p" (2) (V,,1)
(71)
= 0
(72)
B.4 IMMEDIATE REWARD INFLUENCE
Similar to MI and Vol, we can define influence of agent 1 on the immediate rewards of agent as:
RI (1
Σ
() F2($2,
(73)
(SAE(S,A)
Use Lemma 2 we can get:
Ve, (11
Σ Volp""),a))
(74)
8,8E(S.A)
Now we have
Ve, Jo, (t)
(A) PRi-Vii ( Vo, log To, (ails
(75)
where (st) is an augmented value function of I71 ΣI 2v pf' and
A = ui + Bug.
(76)
C ESTIMATION OF CONDITIONAL PROBABILITIES
To quantify interdependence among exploration processes of agents, we use mutual information and value of interaction. Calculations of MI and Vol need estimation of p(s ((s2sss $2, 02) and p(s/ a). In practice, we track the empirical frequencies Pemp (s/2 (2, and pemp (&2 8, a) and substitute them for the corresponding terms in Eq. and 16
Estimating Pemp (#21 82, a2) and Pemp (22ls, a) one obstacle to the scalability of our method, we now discuss how to solve this problem. When the state and action space is small, hash table to implement Monte Carlo method (MC) for estimating the distributions accurately. In
the MC sampling, count from the samples the state frequencies p(s/|52, a2)
N(s))52.02) and
((52.02)
p(</|8, s, a) N(sh_51.52.01.22) ([#1,52.01.02 where N.)) is the number of times each state-action pair was visited during the learning process. When the problem space becomes large, MC consumes large memory in practice. As an alternative, we adopt variational inference (Fox & Roberts 2012) learn variational distributions qg. (s'2 $2, 02) and (g, (s/1s, a), parameterized via neural networks with parameters & and &2, by optimizing the evidence lower bound. In Fig. 6 we show the performance of EDTI estimated using variational inference and the changing of associated EDTI rewards on Pass during 9000 PPO updates. Variational inference introduces some noise in EDTI rewards estimation and thus requires slightly more steps to learn the true probability and the strategy. However, estimating using MC sampling consumes 1.6G memory to save the hash table with 100M items each agent while variational inference needs layer fully connected network with 74800 parameters occupying about 0.60M memory. This results highlights the feasibility of estimating EITI and EDTI rewards using variational inference in problem with large state-action space.
19

---

Published as a conference paper at ICLR 2020
800
Team Performanie
Agent
600
400
200
Agent 2
2
EDTI (v))
1
2500
5000 Updates
7500
100 Updates 2100 Updates
3800 Updates
7000 Updates
Figure 6: Left: Performance of EDTI (vi) (EDIT estimated using variational inference) compared with EITI and EDTI estimated using MC sampling. Others: Development of EDTI (vi) rewards during exploration process. Top row: EDTI (vi) rewards of agent I; bottom row: EDTI (vi) rewards of agent 2.
Table 2: The scaling weights for different intrinsic reward terms in various tasks. ST is the weight of term Ti (see Table Pitt and Seu scaling factors combine and u, in F. u-; in influence
scaled by while Vine and Vest in PlusV are respectively scaled by @plusy and splusV
Task
BT
fint
Bex
Br
@plusV in
gplusV
ext
Pasy
10.
10
1.
0.1
1.
0.1
0.01
Secret-Roome Room
10.
10
1.
0.1
Push-Box
1.
100.
100.
0.1
0.1
0.1
0.01
Island
1.
10
10.
0.5
0.1
0.1
0.01
Large-Island
1.
10
1.
0.1
0.1
0.1
0.01
D IMPLEMENTATION DETAILS
D.1 NETWORK ARCHITECTURE, HYPERPARAMETERS, AND INFRASTRUCTURE
We base our framework on OpenAl implementation of PPO2 DDhariwal et al, 2017 and use its default parameters to carry out all the experiments. We train models 2080TI GPU using experience sampled from 32 parallel environments. We use visitation count to calculate the intrinsic reward, for its provable effectiveness (Azar et al.) 2017 Jin et al. 2018). For all our methods and baselines, we use / /N(s (s) the exploration bonus for ((s)-th visit 8. Specific values of and scaling weights can be found in Table 2
NVIDIA RTX
As for variational inference, the inference network is a 3-layer fully-connected' network coupled with a 64-diimensional reparameterization estimator. ReI.U is used as the activation function for the first two layers and the sum of negative log- likelihooo and negative Evidence Lower Bound used as loss. We use Adam optimizer (Kingma & Ba, 2014) with learning rate 1 x 10-3 and batchsize 2048. To speed up the learning of variational distributions estimation, we equip the learning with proportional prioritized experience replay (Schaul et al. 2015).
D.2 TASK STRUCTURE
In this section, we describe the detailed settings of the experimental tasks.
Pass: There are two agents and two switches open the door in 30 30 grid. Only when least one of the switches are occupied will the door open. The agents need navigate from left to right and the team reward, which is 1000, is only provided when all agents reach the target zone. Agents observe the position another agents.
This is an extension of the Pass task with rooms and 4 switches locating in different rooms. The size of the grid is 25 x 25. When the left switch is occupied, all the three doors are open. And the three switches in each room the right only control the door of its room. The agents need
Secret-Room:
20

---

Published as a conference paper at ICLR 2020
agent
agent A
agent
box
agent
agent B
agent
agent B
wolf
wolf
$
agent D
Figure 7: Task Push-Box, Island, and Large-Island
push-bor box
Island
200
Team Performance
Team Performance
100
EDTI
150
EITI
75
random
100
50
50
dec
25
ren_control
infi_MOn MOA
Multi
2500
5000 Updates
7500
2500
5000
7500
COMA
Updates
Figure 8: Comparison of our methods against baselines Push-Box (left), Island (right).
to navigate towards the desired room (in light red of Fig. I middlle to achieve the extrinsic team reward 1000. Agents can observe the position of the other agents.
There are two agents and one box in a 15 x 15 grid. Agents need to push the box to the wall. However, the box is so heavy that only when two agents push it in the same direction the same time can it be moved grid. The only team reward, 1000, is given when the box is placed right against the wall. Agents can observe the coordinates of their teammate and the location of the box.
Push-Box:
Island: A group of two agents are hunting for treasure on an island. However, random walking beast may attack the agents when they are too close. The agents can also attack the beast within their attack range. This hurt doubles when more than one agent attack at the same time. Each agent has a maximum health of 5 and will lose 1/n health per step when there are n agents within the attack range of the beast. Island is modified version of the classic coordination scenario Stag-Hun, with local optimal, because finding each treasure (9 in total) will trigger a team reward of but catching the beast gives higher team reward of 300. Agents other, and the coordinates of the beast. Fig. shows the development of the probability of catching the beast and the averaged number of treasures found in an episode during 9000 PPO updates.
observe the position and health of each
Large-Island: Settings are similar to that of Island but with more agents (4), more treasures (16), and beast with more energy (16) and higher reward (600) for being caught.
The horizon of one episode set to 300 timesteps in all these tasks.
E COMPARISON WITH AGENT EXPLORATION METHODS
this paper, we study the exploration problem in multi-agent settings from a decentralized per- spective. Alternatively, exploration can be carried out in centralized manner treating agents as a joint one and using single-agent exploration algorithms. In this section, we compare our methods with centralized exploration strategies using RND (Burda al. 2018) and EMI (Hyoungseok Kim 2019), which are among the most cutting-edge exploration algorithms driven by curiosity and based mutual information, respectively. We codes published by their authors and carry out modest
21

---

Published as a conference paper at ICLR 2020
Averaged Treasures Found
EDT1
10
0.2
EMT
Catch Probability
8
random
cen
0.1
6
dec
con_contoo
COMA
0.0
2
infl_MOA
2500
5000
7500
2500
5000
7500
Updates
Updates
Averaged Treasures Found
EDTI
0.20
EITI
Catch Probability
Linfluence
0.15
plusV
shared critic
0.10
Q-Q
0.05
0.00
2500
5000
7500
2500
5000
7500
Updates
Updates
Comparison of our methods against baselines and ablations Island in terms of the probability of catching the beast and the averaged treasures collected in an episode.
Figure 9:
grid search over hyperparameters. For RND, we search intrinsic reward coefficient the range of [0.005, 1.0] and extrinsic reward coefficient in range [0.05, 2.0). For EMI, test difference com- binations loss weights. Results averaged over four random seeds with the best found parameters shown below.
pass
secrettrDom
push-bax
Performace
1000
Team Performence
1000
Team Purformancee
750
150
500
EMTI
250
250
50
-250
Updates
Updates
Updates
Figure 10: Comparison our methods against centralized single-agent exploration algorithms on Pass (left), Secret-Room (middle), and Push- Box (right).
Performance comparisons on problems of Pass, Secret-Room, and Push-Box are illustrated in We can observe that our methods significantly outperform centralized exploration strategies using RND or EMI. To better understand this observation, we plot visitation heatmaps over time for RND and EMI, respectively, in Fig. and 12
Fig. 10
Fig. shows visitation heatmaps of RND on the Pass problem. From Fig. (b), we can see that RND seems finding good policies for agents to pass the door in the first 4671 updates. However, agents' policies seem to collapse quickly after that and their visits scatter around rooms again, which explains its learning curve in Fig. 10 From the evolution of its visitation heatmaps, we hypothesize that after visiting the center of the room for many times, agents' curiosity models overfit par- ticular set states and they start to curious about the relatively unfamiliar transition dynamics around the wall. As the result, the RND intrinsic reward drags the agents the walls, shown in Fig. (T(c) and (d), and their performance quickly drops within several updates (i.e., update 4671- 4677 shown by Fig. b-dj). After while, agents then leave from the walls and visit around in the
22

---

Published as a conference paper at ICLR 2020
5-
10
10
10-
10-
Agent
15
15
25-
25
10
20
10
20
10
20
10
10
5-
5-
10-
Agent
15
20
20
20
20
2
25
25
25
25
(a) 2500 Updates
(b) 4671 Updates
(c) 4673 Updates
(d) 4677 Updates
(c) 5500 Updates
Figure 11: Visitation heatmap of RND agents Pass of most recent 1k episodes. The brighter the
yellow color, the higher the visitation frequency. Top: agent 1, bottom: agent
Agent
20
20-
25-
25-
25
25-
20
20
Agent 2
10
10
10-
10-
15
15
15
15
15
20
20
20
10
20
10
20
20
10
20
(a) Updates
(b) Updates
(c) Updates
(d) 500 Updates
(e) Updates
Figure 12: Visitation heatmap most recent 1 episodes of EMI agents on Pass. The brighter the yellow color, the higher the visitation frequency. Top: agent 1, bottom: agent 2.
room again, as shown in Fig. (mm). The whole exploration process repeated. Similar behaviors also observed on the Secret-Roowe problem.
We also analyze the exploration behaviors of EMI agents on Pass, illustrated by visitation heatmaps in Fig. [2 EMI tends to explore the state-action pairs where the transition dynamics relatively complex, such as the edges and corners of the room (Fig. [-))). For problems where these state-action pairs do not lead to goals, EMI is not very effective. As the (centralized) transition dynamics of the Pass problem relatively simple, EMI intrinsic reward quickly diminishes, which results in the behaviors of agents keeping unchanged after 500 updates (Fig d-))).
In summary, centralized single-agent exploration methods encode some heuristics to facilitate ex- ploration, but they typically do not place great emphasis interactions among agents and are thus not very efficient for multi-agent exploration with sparse interactions.
23


Reviews:
[{"review_id": "rJg6aatjYH", "reviewer": "AnonReviewer1", "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": "Update: I thank the authors for their response and I will maintain my score, my main hesitation being the overall clarity and readability of the paper. \n\nSummary:  \nThis paper proposes the use of two intrinsic rewards for exploration in MARL settings. The first one is an information-theoretic influence (EITI) bonus and a decision-theoretic influence (EDTI)  bonus. EITI uses mutual information to capture the influence of one agent on the transition dynamics of others,  while EDTI uses an intrinsic reward called Value of Interaction (VoI) to quantify the influence of one agent’s behavior on expected returns of other agents.\n\nMain Comments:\nOverall, I think this paper would be a good contribution for ICLR 2020 and I lean towards accepting it. The experimental section is thorough, the authors include relevant ablations, baselines and popular algorithms used in MARL settings. The use of the decision-theoretic influence is novel as far as I can tell and it also seems to be quite effective on the tasks used for evaluation. Although the method uses a series of approximations and assumptions, I believe most of them are clearly stated and fairly well-motivated (plus they are not very far from those of other recent work in the deep MARL literature). I also appreciated the fact that the authors explicitly derived the main mathematical results used in the paper.\n\nI only have some minor comments and questions regarding some assumptions and notation.\n\nI  also encourage the authors to proof-read the paper as some parts of it are a bit hard to follow. I would very much like to see a more an edited version of this paper with more precise language.\n\nCan you discuss in more detail the difference between EITI and the intrinsic reward based on social influence used in Jacques et al. (2018)? They seem to be quite similar conceptually and the related work part related to this is rather vague. Please clarify the distinction.  \n\nMinor Questions / Comments:\nThere are a few typos throughout the paper:\n\n1. On page 3 after equation (3), I believe part of the sentence that should describe the I term in the equation is missing. \n\n2. The phrase right after equation (16) which defines the EDTI reward does not seems to not match the  above expression. Can you please explain why the transition would be conditioned on the influence term? While reviewing, I’ve been assuming this was just a mistake in writing but please double check and clarify. \n\n3. On page 4, after equation (8), you refer to  a_1, a_1 and s_2’ which do not appear in the above equation. Can you please use the same notation or motivate your choice for referring to those variables instead?\n\n \n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of 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": {}}, {"review_id": "HJx2JQyg9S", "reviewer": "AnonReviewer2", "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": "This paper proposes methods for incentivizing exploration in multi-agent RL.  There are two approaches that are proposed, both framed as influence maximization (of either the state transitions or the decisions of the other agents).  The scaling to multiple agents is done via decomposing to pairwise interactions. This influence objective is the appended to the standard intrinsic motivation objective for single agent RL.\n\nThe proposed approaches are pretty elegant, and in a sense seem fundamental.  I'm not an expert in this particular area, so I don't know how novel these ideas are.  (See related work comments below.)\n\nThe empirical results seem quite strong, although (being a a non-expert), I can't tell if they're constructed to be good for the proposed approaches.  There isn't much discussion of limitations and/or experiments breaking the proposed approach.\n\nI found the related work discussion a bit incomplete.  Can the authors comment directly on related MARL work, such as Foerster et al., AAAI 2018?  What are the specific points of contrast?", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "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_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "BkxVHrpKYS", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "This paper studies the problem of designing effective exploration strategies in multi-agent domains. The key idea is to define one agent's exploration in terms of its interactions with other agents. This leads to two auxiliary exploration objectives, which measure how one agent's actions affect the dynamics and value of another agent's actions. The paper does an admirable job comparing the proposed method against a number of baselines, where the proposed method performs significantly better. Visualizations and ablation experiments nicely illustrate the contributions of various components of the method.\n\nI am leaning towards accepting the paper. To the best of my knowledge, the broad idea of applying information theory to multi-agent exploration, in addition to the specific instantiation described in the paper, is novel. I expect that this paper will encourage future work to explore more problems in this area. The experiments are quite thorough. My main reservation is a lack of comparisons to single agent exploration methods. As noted in Section 3, we can view multi-agent domains as just a special type of single agent domain. How would curiosity-based exploration, such as [Burda 2018, Pathak 17], or mutual information-based exploration, such as [Gregor 16, Eysenbach 18, Achaim 18], compare to the proposed method?\n\nI have a few reservations about the clarity of presentation, but I think those are easily addressed. My remaining concern is that the results are on somewhat toy tasks, but I think that is par for this area of research.\n\nOverall, I would strongly argue for accepting this paper if comparisons to single-agent exploration methods were added. I would consider decreasing my review if another reviewer found quite similar prior work, or if significant bugs were found in the mathematical derivation (I have not carefully checked all the proofs in the appendix.).\n\nMinor comments\n* \"transition-dependent\" -- what does this mean?\n* \"while tend\" -- missing a subject\n* \"struggle in many real-world scenarios with sparse rewards\" -- please add a citation\n* \"intrinsic value function of agent i, I_{-i|i}^\\pi is \\beta > 0 is a weighting\" -- I think part of this sentence was accidentally deleted.\n* Eq 5: What is the difference between I and MI?\n* \"We call …\" -- What is the a_2^V0I^\\pi_{-i|i} term?\n* Nitpick: Use `` for the start of quotes\n* Appendix B1: How is Eq 22 obtained from Eq 21?\n\n-------------------UPDATE AFTER AUTHOR RESPONSE---------------------\nThe authors have done a great job address my two concerns (similarity to prior work and empirical comparisons with single-agent exploration). I therefore increase my vote to \"accept.\"", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of 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 paper presents a new take on exploration in multi-agent reinforcement learning settings, and presents two approaches, one motivated by information theoretic, the other by decision theoretic influence on other agents. Reviewers consider the proposed approach "pretty elegant, and in a sense seem fundamental", the experimental section "thorough", and expect the work to "encourage future work to explore more problems in this area". Several questions were raised, especially regarding related work, comparison to single agent exploration approaches, and several clarifying questions. These were largely addressed by the authors, resulting in a strong submission with valuable contributions.
Decision: Accept (Spotlight)