Never Revisit: Continuous Exploration in Multi-Agent Reinforcement Learning
Authors: Chenghao Li
Tonghan Wang
Xiaoran Wu
Jun Yang
Qianchuan Zhao
Chongjie Zhang
Venue: Submitted to ICLR 2023 (2023)

Abstract: Recently, intrinsic motivations are wildly used for exploration in multi-agent reinforcement learning. We discover that coming with intrinsic rewards is the issue of revisitation -- the relative values of intrinsic rewards fluctuate, causing a sub-space visited before becomes attractive after a period of exploration to other areas. Consequently, agents risk exploring some sub-spaces repeatedly. In this paper, we formally define the concept of revisitation, based on which we propose an observation-distribution matching approach to detect the appearance of revisitation. To avoid it, we add branches to agents' local Q-networks and the mixing network to separate sub-spaces which have already been revisited. Furthermore, to prevent adding branches excessively, we design intrinsic rewards to reduce the probability of and penalize the occurrence of revisitation. By virtue of these advances, our method achieves superior performance on three challenging Google Research Football (GRF) scenarios with sparse rewards. 

Under review as a conference paper at ICLR 2023
NEVER REVISIT: CONTINUOUS EXPLORATION IN MULTI-AGENT REINFORCEMENT LEARNING
Anonymous authors Paper under double-blind review
ABSTRACT
Recently, intrinsic motivations are wildly used for exploration multi-agent rein- forcement learning. However, we discover that coming with intrinsic rewards is the issue revisitation the relative values of intrinsic rewards, estimated based neural networks. fluctuate during learning, causing failures of rediscovering promising areas after detachment exploration. Consequently, agents risk explor- ing some sub-spaces repeatedly and being stacked nearing the fixed initial point. In this paper, we formally define the concept of revisitation, based on which we propose observation-distribe of revisitation. According to each detected revisitaion, we dynamically augment branches for agents' local Q-networks and the mixing network to achieve sufficient representational capacity. Furthermore, we use historical joint observations to adjust intrinsic rewards reduce the probability of and penalize the occurrence of revisitation. By virtue of these advances, our method achieves superior perfor- mance on three challenging Google Research Football (GRF) scenarios and three StarCraft II micromanagement (SMAC) maps with sparse rewards.
matching approach detect the appearance
(ours)
35
The issue of revisitation. During learning, we will store the joint observation distribution induced by the joint policy π every 100k time steps, named historical point time. Meanwhile. for every 100k time step, we will calculate the JS distance between the current distribution and all historical points, named checkpoint time. Experiments are carried out on 6 x 12 maze task introduced in Sec. 4 Left: Basic exploration scheme (QMIX (Rashid et al., 2018) with c-greedy exploration) achieves a coverage rate of the joint observation space less than 20% Middle: Adding CDS (Li et al. 2021) intrinsic incentives improves the coverage rate to 80%. However, the fluctuating IS distances indicate that agents are periodically revisiting some sub-spaces. Consequently, most samples are wasted revisitation. Right: Revisitation is avoided based IS distances are large and stable before converging to an optimal strategy, indicating continuous exploration achieved by approach.
Figure 1:
method, and the
INTRODUCTION
Multi-agent cooperation is ubiquitous in real-world problems, such as sensor networks (Zhang & Lesser 2013) and traffic light control (Zhang et al., 2019). To introduce intelligence into multi- agent systems and achieve sophisticated cooperative behavior, multi-agent reinforcement learning (MARL) has been gaining increasing interest in recent years. Advanced MARL methods have largely pushed forward the performance of machine learning algorithms tasks such StarCraft II micromanagement (Rashid et al. 2018): Wang et al. 2021b), Hanabi (Bard et al.) 2020 Foerster et al. 2019) and robotic control (Kurin al. 2020).

---

Under review as a conference paper at ICLR 2023
Despite these achievements, problem persists and prevents MARL from extending successfully to more complex problems. The vetion-observation space grows exponentially with the number of agents, and the efficiency of exploration strategies in such search spaces largely limits the learning
efficiency of MARL algorithms. Basic exploration (Wang et al. 2020b) schemes, like e-greedy, adopted by many previous works (Wang et al. 2021 Yu et al. 22021
1 de Witt et al. (020) appear to struggle even in tasks with a moderate number of agents. For example, in a X 12 maze game with
two agents (Fig. (b)). QMIX (Rashid al. 2018) using independent search can only cover less than 20% of the joint observation space (Fig. Ileft) and struggles to find any rewards.
Various intrinsic motivations are introduced into MARL algorithms enhance their exploration ability by encouraging interaction among agents (Wang et al. (2220b). maximizing measurements of
behavioral randomness (Houthooft et al. 20166; Mahajan et al. 2019 Gupta et al. 202T , and spurring individuality (Tiang & Lu 2021) and diversity (Li et al.) 2021). These methods significantly enlarge the sub-space that can be explored. For example, the coverage rate increases from ~ 20% to 80% using the CDS (Li et al. 2021) iiversity-encouraeeme
incentives (Fig. (middle)) However, in this paper, we find that coming with the augmented exploration is a revisitation problem that severely hurts the expected exploration ability and prevents learning efficiently.
Revisitation refers to the situation where, with an enlarged exploration space, agents forget the areas they have visited before after the detachment (Ecoffet al. 2019) of exploration, causing them to return and re-explore. In this way, agents are stacked nearing the fixed initial point and can not explore continuously. Meanwhile, revisitation in some sub-spaces can repeatedly happen, making this issue more detrimental. For example. in Fig. I (middle), we present the empirical joint observation distribution induced by CDS (Li et al., 2021 policies different training time steps. It can be observed that similar distributions occur periodically during learning, and the algorithm wastes most training samples on unvalued, revisited experiences.
In this paper, we give a formal definition of revisitation in multi- agent settings, according to which we propose a framework for solving this issue. To provide sufficient policy representation capacity, we add branches to agents' local Q-networks and the mixing network when revisitation occurs to achieve a dynamically growing neural network structure. Besides that, we use historical samples to calculate joint observation novelty for adjusting intrinsic rewards. Meanwhile, for each revisitation, we further introduce a KL divergence between its historical point's recorded joint observation distribution and the current to penalize it to happen again.
Based on the above merits for detecting and preventing revisitation, our approach NRT (Never Revisit) achieves nearly 100% coverage rate the maze task (Fig. [ right) with continuous exploration (Fig. Sec. 4.. Furthermore, we benchmark our approach on both Google Research Football (GRF, Kurach et al. (0200) and SMAC (Samvelyan al. (019)) in the sparse reward setting, and find that NRT significantly pushes forward state of the art. Ablation studies show that adding branches is the most important component in revisitation avoidance and performance improvement for challenging tasks. At the same time, the proposed intrinsic reward adjustment modules are critical in achieving continuous exploration.
BACKGROUND
In this paper, we formulate multi-agent coordination tasks as Dec-POMDP HliDDoOliehoek et al. (2016).
which can be defined tuple G = S, A, P. R, O, n,n,,, 7), where I is the set of agents, S is the state space, A is the action space, P is the transition function, It is the reward function, O is the observation space, is the number of agents, and j0, 1) is the discount factor. During sampling, each agent E I observes its unique information o; and selects an action a, E A independently. According the joint action a and environment transition function P(s'|) a), the environment transfers to a new state s' and provides a reward that is shared across all agents.
2.1 CENTRALIZED TRAINING WITH DECENTRALIZED EXECUTION
Our approach follows a recently advanced multi-agent optimization framework of centralized training with decentralized execution (CTDE) Lowe et al. (217)) : Foerster et al. (2018); ; Sunehag et al. (2018); Rashid et al, 2018). In this framework, each agent executes only based on its local oetiion-observatie history. This distributed decision making tackles the exponentially growing joint action space. For
2

---

Under review as a conference paper at ICLR 2023
stable optimization, agents are trained in centralized manner with access to global information to achieve reasonable credit assignment across agents. The sadividul-gllobll-aee
(IGM) principle Son et al. (2019) further guarantees the consistency between the local and global Q-function based on value factorization. With the above advantages, some algorithms [Son et al. (2020); Wang et al. (2021a Ma (202T) have achieved remarkable progress in challenging cooperation tasks.
2.2 CDS
Although the CTDE framework has been proven to accelerate training with value factorization, it still
has to face a giant search space. Diversity exploration is required for sophisticated cooperation. Li ct al. (222)) introduced CDS, which achieves diversity when necessary via shared experiences.
Some of the most salient novelties are: (1) Introduce an intrinsic reward function as shown Eq. [ based on 1d (Ty; id) to encourage specialty of individual trajectories. (2) Provide an independent Q-network for each agent to estimate local Q-value after combining with one shared Q-network. (3) Add an LI regularization on independent Q-values to encourage sharing crucial knowledge while keeping enough policy representation capacity necessary diversity.
r BEd [8yDKL (SoftMax (310 T, id)) p (1)) +31 log 9 (o++1 Te, ae, id) - log (0++1 Fe, a.),
where id is the identity of each agent, 8, 81 and B2 are hyper-parameters introduced in CDS, and variable of one agent's trajectory. this paper, we use reDs as an example expose and solve one crucial potential problem of existing intrinsic motivation methods, revisitation as shown Fig. T (middle).
Tr = (on, 4g, Oi,..., .r)
METHOD
3.1 REVISITATION DETECTION
We first define the concept of revisitation in multi-agent settings. Our definition is based on the empirical joint observation distribution induced by the joint policy (r) Ex + Σ lo,=o] Intuitively, when (o) changes significantly, the agent team starts to explore a new sub-space. Still, if, after significant change, Pr (o) degenerates to distribution that has occurred before, revisitation happens. Formally, we have the following definition:
Definition 1. A ò-revisitation occurs at time step t if there exists time step t" < t so that
1. maxre("".)) Das (P=,.. (0) (o)] > 8:
2. Das (0mp(()))lpm)) (o)] < 6.
Here, Das is the Pensen-Shannon distance between two distributions. The first condition describes ability of many multi-agent exploration algorithms. As the learning progresses, agents are encouraged to explore new sub-spaces, leading to a shift in the empirical joint observation distribution. The second condition depicts the occurrence of revisitation. After exploring the agents may forget previously learned knowledge, possibly due to limited network representative capacity, and start re-explore previously visited sub-spaces.
sub-space for while,
Under discrete observation space, we can estimate (o) with the Monte Carlo (MC) method. However, in continuous observation space, it is intractable use MC. In practice, estimate the joint observation distribution Pr (o) using an a variational auto-encoder parameterized by ç, by minimizing the evidence lower bound:
(E) (log p(o, 2) loga(> o)
where z is latent variable to reconstruct o, and (o( Pe(o 2)p(2)d= EL Po 21) for 2; ~ p(z). where p(2) is prior of the latent variable vector, which modeled by a standard Gaussian distribution ( 0, and L is fixed as 32 in this paper.
During training, for every 100k time step. we store the current joint observation distribution estimator Ps, into buffer, and check for each previous version Ps,r whether they satisfy the conditions
3

---

Under review as a conference paper at ICLR 2023
listed in Definition
1 If the conditions are satisfied, call (t",t', revisitation tuple and
store (Pr." (O), Pm. Pm. with (Prt. (o:), Pmy (oz), Pmr (o:)) for each agent E I, where Pr (Oi)
Em T Et=o o0, mo is estimated along with Pr (o).
3.2
AUGMENTATION OF THE TRAINING FRAMEWORK
Training Time Line
Defiull Mixing Network Hranch
Relu
Historical
Relu
Defoult Switcher
SC
Ws
W;
of "..ff"".dd
MLP
W:
GRU
Checkpoint Time
Switcher
0,(rf. id.)
On(tf.
MLP
Default Local-Q Branch
Detected Revisitation
Branchis
Initialized with the latest default branch
Angmented Mixing Network Branch
Main Body
Augmented Local-Q Bmnnch
LI Norm
Augmented Switcher
Figure 2: Dynamic augmentation of NRT (Never Revisit)'s neural network structure (using one detected revisitation an example).
To achieve sufficient policy representation capacity for handling revisitation while benefiting from parameter sharing, dynamically augment partial neural networks (branches) shown in Fig. 2 In this paper, we follow the CTDE framework as discussed in Sec. 2. with a mixing network as QMIX (Rashid et al. 2018), whose weights are produced by separate hyper networks with an input of state and are followed by an absolute activation function to ensure the IGM principle. Starting from the beginning of training, we provide default mixing network branch part of the mixing network), default local-Q branch (the last layer of local Q-networks), and the main body of our neural networks. The main body is painted blue, while branches are painted green. After one detection of revisitation, we will create related augmented mixing network branch and a related augmented local-Q branch with the same structure as the default ones increase representational capacity. Their parameters are initialized according the latest default branches.
Along with our dynamic augmentation structure is a question about how to switch different branches. Formally, for b th augmented branch, we define the associated joint observation set Q, based on the definition of related revisitation tuple (t" th, to) introduced in Sec. 3.1
2 = {ol| log Pr.g (o) - log Pr. (o)) 8) n {oll log Pmig (o) - log Pm., (o)}1 8).
(3)
However, during decentralized execution, one agent can only obtain its observation. Thus, we further introduce the marginal set 22 for each agent E I as shown in Eq. If agent i's local observation o E Di the related th augmented local-Q branch will be activated for both sampling and training. If none of augmented branches is activated or created, agents will choose the default branch.
2 = {o. log Prg (o.) - log PmÚ (o:)H - n foill log Pm (o.) log Pm., (ot)) < - (4)
4

---

Under review as a conference paper at ICLR 2023
There two questions coming with Eq. 4 (1) how to switch augmented local-Q branches when og belongs to several sets simultancously, and (2) how to switch augmented mixing network branches when agents switch various local-Q branches. As for question (1), we will check according to the created order and activate the earliest branch. As for question (2), each augmented mixing network branch will be activated only when more than half of agents choose the corresponding augmented local-Q branch. Our neural networks will switch to the default branch if none of augmented branches activated created. Because the whole trajectory is spliced from different branches, we expect credit assignments across agents (achieved by the mixing network) to not differ too much for stability, Thus add an LI regularization to mixing network branches encourage them work only when necessary. More details and the pseudo-code of NRT's sampling process are discussed in Sec. B.1
3.3 AUXILIARY SUPPORTING INCENTIVES
short-sighred novelty module
Intrinsic Reward
Ti mny
TEDS
((gid]p)
1oos (o:td)r,a)
[(:: id)
Intrinsic
K-nearest
store periodically
filter
filter
IS
storod da - Ty ((T,))) e
dotected revisitation
(malpx,(o) pr(o))
Intrinsic reward udjustment
Figure 3: NRT (Never Revisit)'s intrinsic reward adjustment modules.
A possible shortcoming of the methods introduced above is that when revisitation occurs frequently, there may be too many branches. Thus, we design adjustment modules for intrinsic motivations to attempt to (1) prevent the appearance of revisitation in advance, and (2) penalize the occurrence of revisitation.
To prevent revisitation in advance, adjust intrinsic rewards with historical joint observations. In this paper, we periodically store joint observation sequences (every ten episodes) in an independent buffer without deletion. During training, for time efficiency, form a compact sub-sampling buffer with 10 trajectories from the whole learning period. As inspired by ByBai et al. (2020), based on joint observation novelty estimated by K-nearest approach, we calculate the weight of intrinsic rewards:
V Nooee K(o,ox)++* where Ni(o) is the ks nearest neighbors of o in the compact buffer,
and small constant (0.001) for numeric stability. The kernel function K(,,-) is defined as K K(x,y) v) F(aa)+t where is the Euclidean distance.
For penalizing revisitation to forbid it to occur again, we additionally add 5 trajectories from each revisitation to the compact sub-sampling buffer discussed above refresh the estimated joint observation novelty. Furthermore, we introduce rP E(tn L(tr,eee ,.,e) DKI. (Prie (o) I| (o)), where Pr is the current joint policy, Overall, the intrinsic reward used in our paper is
rEDs clip(1 + ā. L1, L2) + Spr".
(5)
where ã = a-pe is the running average of a, clip means we clip the running average so that it is in de the range Le), r'os is the intrinsic reward introduced by CDS (Li et al. 2021) as shown in Eq. and Bp is peramer tuning the weight of rP, which is fixed as 0)00) in our experiments.
4 DIDACTIC EXAMPLE
In this section, we present a maze task (shown Fig. 5 (b)) to demonstrate the existence of revisitation, its influence exploration, and how our approach improves learning performance by
5

---

Under review as a conference paper at ICLR 2023
NRT (ours)
CDS
MAVEN
QMIX
QPLEX
MAZE
Episods Reward
100
50
0
0.0
0.5
1.0
1.5
2.0
2.5
3.0
time(1e6)
0.2
NRT
CDS
0.0
Figure 4: Comparison against baselines with visitation heat maps.
avoiding revisitation. In this task, two agents are initialized the blue point and are expected to simultancously reach two red points located in different corners of a 6 x 12 maze within 50 steps. Each agent can observe its own and teammate's coordinates. The action set of both agents includes one-step movement in four directions and an idle action for doing nothing. Only when agents reach two red points simultaneously, the episode will terminate immediately with a team reward of 100. For any other cases, reward is set to 0.
Fig. shows the comparison of our approach against baseline algorithms, including state- of-the-art value function factorization learn- ing methods (QMIX (Rashid et al. 2018) and QPLEX (Wang et al. 2021a)) and multi-agen exploration algorithms (CDS (Li al. 2021) and MAVEN (Mahajan et al. 2019)). Experi-
revisjtation detected
(a)Another perspective of JS distance changing
(b) Environment
mental results demonstrate the advantage of our approach in exploration, as NRT is the only algo- rithm that obtains the episode reward 100. We further provide visitation heat maps of NRT and CDS within three periods agents to explore further, while agents trained by CDS are stacked nearing the fixed initial points and waste most training samples on revisited experiences after the detachment of previous exploration.
Figure 5: Structure of the maze and continuous exploration achieved by approach.
0.5M, 0.5M 1.0M, and 1.0M 1.5M). NRT continuously encourage
In Fig. (a), further show another perspective of the 3D plot of JS distance plot to demonstrate continuous exploration achieved by our approach after detecting revisitation. The circle Fig. (a) highlights time step when revisitation is detected. At this time, our approach (1) adds new branch as described in Sec. 3.2. (2) ensures that the joint observations where the revisitation happens are sampled when calculating the intrinsic reward; and (3) adds punishment of revisitation. In this way, our approach effectively prevents the reappearance revisitation, leading to continuous exploration.
EXPERIMENT
In Sec. we introduce toy maze environment to illustrate approach's 's efficiency of exploration while showing the significant harm of repeat revisitation learned by current advanced multi-agent algorithms. In this section, we will compare approach against baselines on Google Research Football (GRF) Kurach et al. (2020) and SMAC (Samvelyan et al., 2019) in the sparse reward setting, which are currently the most challenging benchmarks for testing cooperation between agents. We show the median and variance of every evaluation's average performance of our approach, baselines, and ablation tested with three random seeds (seed=0,1,2),

---

Under review as a conference paper at ICLR 2023
5.1 GRF
The GRF benchmark provides numerous scenarios varying in agent numbers and difficulty. In this paper, we use three representative scenarios to demonstrate the significance of considering revisitation. Agents' initial locations for each scenario are shown in Appendix [ Following the convention of Kurach et al. 2020) and [i et al. 2021). the state and each agent's s observation are based on the official simple 115 representation vector, while observations are established according relative positions. Each agent has discrete action space of 19 dimensions, including moving and several basic actions, such as passing and shooting. Environmental rewards are only provided the end of one episode, Agents will get 100 if they score, else get -1.
NRT (ours)
CDS
MAVEN
QMIX
QPLEX
Academy
Keeper (Determinsilic))
Academy Counteratiack Easy (Determinstic)
Academy Counterattack Hard (Deleminsiticc)
100
100
100
Test Win %
50
50
50
0.5
1.5
2.0
2.5
T (mil)
(mil)
(mil)
Academy
Keeper (Stochastic)
Academy Counterattack Easy (Stochastio)
Academy Counterattack Hard (Stochestic)
100
80
78-
75
Test Win %
50
40
25
20
0
1.0
1.5
T (mil)
(mil)
T (mil)
Figure Comparison of our approach against baseline algorithms on GRF with deterministic environment seeds or stochastic environment seeds.
Fig. demonstrates the comparison between our approach with baseline algorithms the determin- istic and stochastic settings. Here we first analyze experiment results in the deterministic setting. In Academy_3 3_v._.vvv.._... tra1_wwih Keeeeerr. QPLEX can achieve similar learning efficiency with our ap- proach, while CDS and QMIX can also achieve 100% winning rate. However, in more complex scenarios, Academy_Comm www.oooottttttaaacmommea obvious, showing the advantages of considering revisitation. In Academy vs 1 with Keeper and Academy Counterattade Easy, CDS performs similar with QMIX. With our additional supporting incentives, NRT achieves more efficient exploration.
Hard in particular, the outperformance of our approach is
Like the deterministic counterpart, our approach maintains its outperformance in the stochastic setting, as shown Fig. Because opposing players' behavior might differ across various random environment seeds, the average winning rates during evaluation are nearly impossible to be 100%. In this case, our approach still shows clear superiority in all three scenarios. In challenging scenarios, CDS outperforms QMIX. Following the guidance of our
such as A Academy Counterattack. intrinsic reward adjustment module, the performance further raised in all three scenarios.
Ablation Study To understand the contribution of each component in the proposed NRT framework.
we conduct three ablations: (1) ablate augmented branches, (2) ablate auxiliary dynamic weight of intrinsic motivations, and (3) ablate auxiliary KL punishment after the detection of revisitation. We respectively name them DRT-ab-new-branch. NRT-ab-alpha, and NRT-ab-KL.
further understand the necessity of detecting revisitation, we conduct two ablations based on vanilla CDS: (1) store joint observation distributions every 100k time steps and add the KL divergence between each of them and the current observations and add the KL divergence between it and the current one as intrinsic rewards during training. We respectively name them CDS-KL--Fade and CDS- KI-AII.
intrinsic rewards during training. (2) estimate the distribution of all sampled joint
7

---

Under review as a conference paper at ICLR 2023
NRT
NRT-sb-slpha
NRT-a0-KL
NRT-ab-branch
CDS
CDS-KL-Eadh
CDS-KL-AII
Academy Counterattack Easy (Deterministic)
Academy Counterattack Hard (Determnielic)
Academy Counteratisck Hard (Stochaelic)
100
100
80
60
Test Win
50
40
20
0
0.5
1.5
3.0
T (mil)
((ml))
(mill
Figure 7: Ablation studies on three GRF tasks.
We compare NRT with ablations on three representative tasks:
under the deterministic setting and 4cademy_.oomteeaattan wow.nttaatttcccknoo.... under both settings. From Fig. left to Fig. 7 right, the difficulty of the environment increases, accompanied by a sharp This phenomenon reveals the importance of constructing dynamic augmentation of neural networks according to the degree of exploration in complex environments. The performance of NRT-ab-alpha and NRT-ab-KL -LL in three tasks illustrates that the combined effect of our auxiliary supporting incentives makes our approach outperform CDS. CDS-KL-Each performs well in Academy_Countersy Cwwnterattack Hard under the deterministic setting but fails on the other two scenarios, while CDS-KL-AI performs similarly to vanilla QMIX. This phenomenon demonstrates the necessity of dynamically checking the exploration situation and making targeted adjustments when revisitation occurs.
decline in the performance of NRT-ab-new-brande
5.2 SMAC
In this section, we our approach on SMAC, consisting of various maps with different agent numbers and various agent types. Previous work has achieved remarkable performance in many chal- lenging tasks. However, their success heavily relays on dense rewards provided by the environment, which includes changes in the blood volume of our agents and opposing agents. In this paper, we consider SMAC tasks in the sparse reward setting. Agents will only receive rewards the end of one episode. Agents will get 100 if they win, else -1, which maintains the same as that in GRF
(ours)
CDS
QMIX
3m (sparse reward)
1sa (sparse reward)
(sparse reward)
100
100
100
Test Win %
0.2
0.4
0.6
0.8
1.0
2.0
T (mil)
(mil)
T (mil)
Figure 8: Comparison of our approach against baseline algorithms on SMAC the sparse reward setting.
Fig. demonstrates the comparison between our approach with baseline algorithms in three easy SMAC maps with sparse reward. QMIX achieves good performance with dense rewards (Rashid al. 2018 However, vanilla QMIX can not learn any strategies to win all three easy maps based sparse rewards shown in Fig- Using QMIX as the mixing network, CDS can learn valuable strategies 3m with its intrinsic motivations as discussed in Sec. 2.2 However, CDS still learns nothing to win in 2m_vs_1z Our approach, adjusting intrinsic rewards of CDS based on the detection of revisitation, outperforms CDS in all three maps. The comparison between NRT and CDS supports above discussion about one potential drawback of current intrinsic motivation methods, revisitation, which seriously influences exploration efficiency. QPLEX achieves good performance in 3m with its duplex dueling network architecture, but still learns nothing win in other two maps.
8

---

Under review as a conference paper at ICLR 2023
MAVEN achieves remarkable performance in 2m.vs_1e 11.,,, but performs similar with QMIX in other two maps. Compared with QPLEX and MAVEN, NRT can adapt to all three maps, showing its exploration efficiency.
RELATED WORK
Exploration Bonuses.
Exploration is one key factor that determines the efficiency of deep reinforce-
ment learning (Houthooft et al.) 2016] Trott et al. 2019 Raileanu & Rocktäschel [220)] Zintgraf
et al.) |021 Chen et al. 2021). Starting from the classic e-greedy action selector, numerous advanced
algorithms are proposed enhance the efficiency of exploration. Count-based exploration methods
directly use visit counts to guide an agent's 's behavior towards reducing uncertainty (Strehl & Littman
2008; Bellemare et al., 2016; Martin et al. 2017 Ostrovski al.) 2017 Tang et al. [2017] Machaado
et al. 2020p. A representative method is Random Network Distillation (RND), using prediction errors
to estimate count-based rewards (Burda et al. 2018b; Oshand al. 2018: 2019 Ciosek et 2019).
The prediction errors are also used in Pathak et al. (2017): Burda et al. (2018a): Pathak et al. (2019)
Dean et al. (2020) to achieve self-organized intrinsic motivations.
Exploration in the Multi-Agent Setting, Exploration is more crucial in the multi-agent setting, because the search space grows exponentially with the number agents. Besides exploring the environment, we also need to consider diversity across agents to achieve sophisticated coordination. In the multi-agent setting, agents' exploration can be jointly encouraged (Mahajan et al.] [2019] Gupta
et al.
2021 [Zhnng et al. 202T Liu et al. 2021), encouraged in pairs (Wang al. 2000b) Ndousse
et al.
2021). or independently encouraged for being special from the whole group (Jiang & Lu
2021
Liet al. 202T). Exploration can also be encouraged through the factorization of roles (Wang)
et al.
2020a 2021b). In this paper, we choose CDS (Li et al.) (2021) as the intrinsic motivation for
exploration because the current state-of-the-arr algorithm many challenging benchmarks.
Forgetting, Revisitation discussed in our paper also relates to the forgetting of previous policies. which is wildly discussed in lifelong learning with the multi-task setting (Rebuffi al., 2017 Li &
Hoiem 2017 Rolnick et al. 2019)] Von Oswald et al. (019)). Some advanced algorithms have studied this topic by extending the supervised regularization (Kirkpatrick et al., 2017) or replay (Isele & Cosgun 2018 Yan et al., (2022) paradigms, exacerbating the stability-plastichi tension. Others, on the other hand, have proposed multi-stage processes in which the agent first applies existing knowledge to the current task and then incorporates newly acquired knowledge into shared repository (Schwarz) ct al. 2018 Mendez et al. (020).. However, forgetting is rarely discussed in single-task and multi- agent reinforcement learning, which also has the possibility of forgetting during exploration. The key question is how to detect and forbid it automatically without any information about the stages agents in during learning.
In this paper, we attempt to answer this question to enhance exploration efficiency. Ecoffet et al. (2019) (Coffet et al. (202T) intuitively show hypothetical example of revisitation caused by detachment in intrinsic motivations. They solve it by storing all visited states and related policies to access. Before sampling, they will first check which state to return from the whole state space, which is challenging to execute in large continuous search space, especially in multi-agent settings. In this paper, we empirically show policies' repeated revisitation in the multi-agent setting and solve based on much fewer memories. Our approach maintains active detection and prevention of revisitation. We hope this paper can stimulate a rethinking of intrinsic motivations for more effective exploration in single-task multi-agent learning.
CLOSING REMARKS
In this paper, we investigate the intrinsic motivation methods for multi-agent exploration, and find the revisitation issue that prevents these methods from achieving efficient exploration in complex tasks based on sparse rewards. For future work, we plan to study the interplay between the number of augmented branches and the scale of the proposed intrinsic rewards. We hope work encourage more studying on the limitation of current exploration methods based on intrinsic motivations to push forward the boundary of artificial intelligence.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Adrià Puigdomènech Badia, Pablo Sprechmann, Alex Vitvitskyi, Daniel Guo, Bilal Piot, Steven Kapturowski, Olivier Tieleman, Martín Arjovsky, Alexander Pritzel, Andew Bolt, al. Never give up: Learning directed exploration strategies. arXiv preprint wrXiv:2002.0600 2020.
Nolan Bard, Jakob Foerster, Sarath Chandar, Neil Burch, Mare Lanctot, H Francis Song, Emilio Parisotto, Vincent Dumoulin, Subhodeep Moitra, Edward Hughes, et al. The hanabi challenge: A new frontier for ai research. Artificial Intelligence, 280: 103216, 2020.
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, Harri Edwards, Deepak Pathak, Amos Storkey, Trevor Darrell, and Alexei A Efros. Large-scale study of suriosity-driven learning. arXiv preprint arXiv: 04:555 2018a.
Yuri Burda, Harrison Edwards, Amos Storkey, and Oleg Klimov. Exploration by random network distillation. arXiv preprint arXiv: 128944 2018b.
Haipeng Chen, Wei Qiu, Han-Ching Ou, Bo An, and Milind Tambe. Contingency-aware influence maximization: A reinforcement learning approach. In Uncertainly in Artificial Intelligence, pp. 1535-1545. PMLR, 2021.
Kamil Ciosek, Vincent Fortuin, Ryota Tomioka, Katja Hofmann, and Richard Turner. Conserva- tive uncertainty estimation by fitting prior networks. In International Conference Learning Representations, 2019.
Christian Schroeder de Witt, Tarun Gupta, Denys Makoviichuk, Viktor Makoviychuk, Philip HS Torr, Mingfei Sun, and Shimon Whiteson. Is independent learning all you need in the starcraft multi-agent challenge? arXiv preprint arXiv:2011.0953: 2020.
Victoria Dean, Shubham Tulsiani, and Abhinav Gupta. See, hear, explore: Curiosity via audio-visual association. Advances Neural Information Processing Systems, 33:1 4961-1497, 2020.
Adrien Ecoffet, Joost Huizinga, Joel Lehman, Kenneth O Stanley, and Jeff Clune. Go-explore: a new approach for card-exploration problems. arXiv preprint wxXiv:/901.10
2019.
Adrien Ecoffet, Joost Huizinga. Joel Lehman, Kenneth O Stanley, and Jeff Clune. First return, then explore. Nature, 590(7844))580-5586 2021.
Jakob Foerster, Francis Song. Edward Hughes, Neil Burch, lain Dunning, Shimon Whiteson, Matthew Botvinick, and Michael Bowling. Bayesian action decoder for deep multi-agent reinforcement learning. In International Conference Machine Learning, pp. 1942 1951, 2019.
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.
Tarun Gupta, Anuj Mahajan, Bei Peng, Wendelin Böhmer, and Shimon Whiteson. Uneven: Universal value exploration for multi-agent reinforcement learning, In International Conference on Machine Learning, pp. 3930-3941 PMLR, 2021.
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.
David Isele and Akansel Cosgun. Selective experience replay for lifelong learning. Proceedings of the AAAI Conference Artificial Intelligence, volume 32, 2018.
Jiechuan Jiang and Zongging Lu. The emergence of individuality. In International Conference on Machine Learning, pp. 4992-5001, PMLR, 2021.
10

---

Under review as a conference paper at ICLR 2023
James Kirkpatrick, Razvan Pascanu, Neil Rabinowitz, Joel Veness, Guillaume Desjardins, Andrei A Rusu, Kieran Milan, John Quan, Tiago Ramalho, Agnieszka Grabska-Barwinsker et al. Overcoming catastrophic forgetting in neural networks. Proceedings of the national academy of sciences, 114 (13):3521-3526 2017.
Karol Kurach, Anton Raichuk, Piotr Stanczyk, Michat Zajac, Olivier Bachem, Lasse Espeholt, Carlos Riquelme, Damien Vincent, Marcin Michalski, Olivier Bousquet, et al. Google research football: novel reinforcement learning environment. Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 4501-4510, 2020.
Vitaly Kurin, Maximilian Igl. Tim Rocktäschel, Wendelin Boehmer, and Shimon Whiteson. My body is cage: the role of morphology in on Learning Representations, 2020.
incompatible control. In International Conference
Chenghao Li, Tonghan Wang, Chengjie Wu, Qianchuan Zhao, Jun Yang, and Chongjie Zhang. Celebrating diversity in shared multi-agent reinforcement learning, arXiv e-prints, pp. arXiv-2106, 2021.
Zhizhong Li and Derek Hoiem. Learning without forgetting. IEEE transactions pattern analysis and machine intelligence, 40 40(12):2935-2941) 2017.
Iou-Jen Liu, Unnat Jain, Raymond Yeh, and Alexander Schwing. Cooperative exploration for multi-agent deep reinforcement learning. In International Conference on Machine Learning, pp. PMLR, 2021.
Ryan Lowe, Yi Wu, Aviv Tamar, Jean Harb, OpenAl Pieter Abbeel, and Igor Mordatch. Multi-agent actor-critic for mixed cooperative-compeiiine environments. Advances in Neural Information Processing Systems, pp. 0399,,390, 2017.
Xiaoteng Ma, Yiqin Yang, Chenghao Li, Yiwen Lu, Qianchuan Zhao, and Jun Yang. Modeling the interaction between agents in cooperative multi-agent reinforcement learning. In Proceedings of the 20th International Conference on Autonomous Agents and MultiAgent Systems, pp. 853-861, 2021.
Marlos C Machado, Marc G Bellemare, and Michael Bowling. Count-based exploration with the successor representation. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 5125-5133, 2020.
Anuj Mahajan, Tabish Rashid, Mikayel Samvelyan, and Shimon Whiteson. Maven: Multi-agent variational exploration. In Advances in Neural Information Processing Systems, pp. 7611-7622 2019.
Jarryd Martin, Suraj Narayanan Sasikumar, Tom Everitt, and Marcus Hutter. Count-based exploration in feature space for reinforcement learning. arXiv preprint arXiv:1706.08000 2017.
Jorge Mendez, Boyu Wang, and Eric Eaton. Lifelong policy gradient learning of factored policies for faster training without forgetting. Advances Neural Information Processing Systems, 33: 11398-14400 2020.
Kamal Ndousse, Douglas Eck, Sergey Levine, and Natasha Jaques. Emergent social learning via multi-agent reinforcement learning. In International Conference on Machine Learning, pp. 7991-8004. PMLL 2021.
Frans A Oliehoek, Christopher Amato, al. A concise introduction decentralized POMDPs. volume 1. Springer, 2016.
Ian Osband, John Aslanides, and Albin Cassirer. Randomized prior functions for deep reinforcement learning. Advances in Neural Information Processing Systems, 31, 2018.
Ian Osband, Benjamin Van Roy, Daniel J Russo, Zheng Wen. et al. Deep exploration via randomized value functions. J. Mach. Learn. Res,, (0(124)1166. 2019.

---

Under review as a conference paper at ICLR 2023
Georg Ostrovski, Mare G Bellemare, Aäron van den Oord, and Rémi Munos. Count- exploration with neural density models. In Proceedings of the 34th International Conference on Machine Learning- Searning-Volume Volume 70, pp. 2721-2730 JMLR. org, 2017.
Deepak Pathak, Pulkit Agrawal, Alexei A Efros, and Trevor Darrell. Curiosity-driven exploration by self-supervised prediction. In International Conference on Machine Learning, pp. 2778-2787, 2017.
Deepak Pathak, Dhiraj Gandhi, and Abhinav Gupta. Self-supervised exploration via disagreement. In International conference on machine learning, pp. 5062-5071, PMLR, 2019.
Roberta Raileanu and Tim Rocktäschel. Ride; Rewarding impact-driven exploration for procedurally- generated environments. arXiv preprint arXiv: 12292, 2020.
Tabish Rashid, Mikayel Samvelyan, Christian Schroeder Witt, Gregory Farquhar, Jakob Foerster, and Shimon Whiteson. Qmix: Monotonic value function factorisation for deep multi-agent reinforcement learning. In International Conference on Machine Learning, pp. 4292 4301, 2018.
Sylvestre-Alvise Rebuffi, Alexander Kolesnikov, Georg Sperl, and Christoph H Lampeet. icarl: Incremental classifier and representation learning. In Proceedings of the IEEE conference Computer Vision and Pattern Recognition, pp. 2001-2010, 2017.
David Rolnick, Arun Ahuja, Jonathan Schwarz, Timothy Lillicrap, and Gregory Wayne. Experience replay for continual learning. Advances in Neural Information Processing Systems, 32, 2019.
Mikayel Samvelyan, Tabish Rashid, Christian Schroeder de Witt, Gregory Farquhar, Nantas Nardelli, Tim GJ Rudner, Chia-Man Hung, Philip HS Torr, Jakob Foerster, and Shimon Whiteson. The starcraft multi-agent challenge. arXiv preprint arXiv: ftfi:::902.040444 2019,
Jonathan Schwarz, Wojeiech Czarnecki, Jelena Luketina, Agnieszka Grabska Barwinska, Yee Whye Teh, Razvan Pascanu, and Raia Hadsell. Progress & compress: A scalable framework for continual learning. In International Conference Machine Learning, pp. 4528 4537. PMLR, 2018
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 International Conference on Machine Learning, pp. 5887-5896, 2019.
Kyunghwan Son, Sungsoo Ahn, Roben Delos Reyes, Jinwoo Shin, and Yung Yi. Qtran++: Improved value transformation for cooperative multi-agent reinforcement learning, 2020.
Alexander I. Strehl and Michael Littman. An analysis of model-based interval estimation for markov decision processes. Journal of Computer and System Sciences, 7408):1309-1331, 2008.
Peter Sunehag, Guy Lever, Audrunas Gruslys, Wojciech Marian Czarnecki, Vinicius Zambaldi, Max Jaderberg, Mare Lanetot, Nicolas Sonnerat, Joel Z Leibo, Karl Tuyls, et al. Value-decompositionn networks for cooperative multi-agent learning based on team reward. In Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems, pp. 2085-2087. International Foundation for Autonomous Agents and Multiagent Systems, 2018.
Haoran Tang, Rein Houthooft, Davis Foote, Adam Stooke, OpenAl Xi Chen, Yan Duan, John Schulman, 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.
Alexander Trott, Stephan Zheng, Caiming Xiong, and Richard Socher. Keeping your distance: Solving sparse reward tasks using self-balancing shaped rewards. Advances in Neural Information Processing Systems, 32, 2019.
Johannes Von Oswald, Christian Henning, João Sacramento, and Benjamin F Grewe. Continual learning with hypernetworks. arXiv preprint arXiv: /90i: 006600095 2019.
Jianhao Wang, Zhizhou Ren, Terry Liu, Yang Yu, and Chongjie Zhang Qplex: Duplex ducling multi-agent geaarning. International Conference Learning Representations (ICLR), 2021a
12

---

Under review as a conference paper at ICLR 2023
Tonghan Wang, Heng Dong, Victor Lesser, and Chongjie Zhang. Roma: Multi-agent reinforcement learning with emergent roles. In Proceedings of the 37th International Conference on Machine Learning, 2020a.
Tonghan Wang, Jianhao Wang, Wu Yi, and Chongjie Zhang. Influence-based multi-agent exploration. In Proceedings of the International Conference on Learning Representations (ICLR), 2020b.
Tonghan Wang, Tarun Gupta, Anuj Mahajan, Bei Peng. Shimon Whiteson, and Chongjie Zhang. Rode: Learning roles to decompose aagei- tasks. In Proceedings of the International Conference on Learning Representations (ICLR), 2021b.
Qingsen Yan, Dong Gong, Yuhang Liu, Anton van den Hengel, and Javen Qinfeng Shi. Learning bayesian sparse networks with full experience replay for continual learning. Proceedings of the IEEE/CVF Conference Computer Vision and Puttern Recognition, pp. 109-118. 2022.
Chao Yu, Akash Velu, Eugene Vinitsky, Yu Wang, Alexandre Bayen, and Yi Wu. The surprising effectiveness of ppo in cooperative, multi-agent games. arXiv preprint arXiv:2103.0195. 2021.
Chongjie Zhang and Victor Lesser. Coordinating multi-agent reinforcement learning with limited communication. Proceedings of the 2013 international conference on Autonomous agents and multi-agent systems, pp. 1101-1108. International Foundation for Autonomous Agents and Multiagent Systems, 2013.
Zhi Zhang, Jiachen Yang, and Hongyuan Zha. Integrating independent and centralized multi-agent reinforcement learning for traffic signal network optimization. arXiv preprint arXiv: 10651, 2019.
Lulu Zheng, Jiarui Chen, Jianhao Wang, Jiamin He, Yujing Hu, Yingfeng Chen, Changjie Fan, Yang Gao, and Chongjie Zhang. Episodic multi-agent reinforcement learning with curiosity-driven exploration. Advances in Neural Information Processing Systems, 34:3757-3769, 2021.
Luisa M Zintgraf, Leo Feng, Cong Lu, Maximilian Igl, Kristian Hartikainen, Katja Hofmann, and Shimon Whiteson, Exploration in approximate hyper-state space for meta reinforcement learning. In International Conference Machine Learning, pp. 12991-13001. PMLR, 2021.
13

---

Under review as a conference paper at ICLR 2023
A EXPERIMENT SETTING
The visualization of the initial position of each agent shown in Fig. 9 The difficulty of scenarios increases from -artmyy3-vs__iive Keeper to Academy Gradeny-Counterate _oonterattack Hard based no- ticeable difference between the number of agents and the initial distance each agent to the goal and opposing players.
Academy vs with Keeper
Academy Counterattack Easy
Academy Counterattack Hard
Figure 9: Visualization of the initial position of each agent in three GRF scenarios considered in paper, where blue points represent our controlled team, red points represent the opposing team, and yellow point represents the ball.
B ARCHITECTURE AND HYPER-PARAMETER
In this paper, we use simple network structures for the local Q-networks and the mixing networks as baselines. Agents use a partially shared module to represent local Q-functions as CDS (Li et al. 2021). Following the setting of CDS, agents share trajectory encoding network made up of two layers: fully connected layer followed by GRU layer with a 64-dimensional hidden state for individual Q-functions. Following the trajectory encoding network, all agents share one-layer Q network, with each agent having its own Q network with the same structure as the shared Q network. To estimate global action values, we use QMIX-style mixing networks, which include two 32-dimensional hidden layers activated by ReLU. Hypernetworks condition on global states to generate mixing network parameters. These options apply to QMIX Rashid et al. (2018) well.
All experiments are optimized using RMSprop with a learning rate of x 10 7 of 0.99, and no momentum weight decay. We e-greedy with anneals linearly from 1.0 to 0.05 over 50K time steps and keep constant for the rest of the training while selecting actions. We will evaluate the latest policies 32 times every 10k steps calculate the average winning rate. For our approach, all baselines and ablations, we introduce a prioritized replay buffer with the same a of 0.3 and use TD(0.8) while calculating target values.
The intrinsic motivation introduced in CDS includes three papee--prameters:: B, 31, and B2, with another hyper-parameter controls the weight of LI regularization on independent local Q-networks. In this paper, we roughly fine-tune these hyper-parameter while ensuring CDS uses the same hyper- parameters during comparison. For the maze game, we use (B, 31, 83 }} as (0.15, 0.5, 0.5, 0.01). For all GRF scenarios, we use (3, 31, 32 A} as (0.05, 0.5, 1.0, 0.1 which is the same as the original CDS setting in GRF environments.
In our approach, we introduce several special hyper parameerrssstrrs and some basic settings to establish our framework. Definition iis fixed in all experiments. r) in Eq. 3 is fixed in experiments. To reduce the size of the replay buffer loading trajectories calculate every ten times. The weight L1 normalization on independent mixing networks is fixed to 0.1 in all experiments. {L,, L2, 3p } is set (0.5. 2.0, 10 10-3) for the maze game. For all GRF scenarios, Ap Eaataccckasyyyyya.e Easy based on both stochastic and deterministic environment setting. Meanwhile, {L, Lg } is set {1.0, 2.0) for other scenarios. For all SMAC maps, (L1, L2, 3,3 is set to (1.0, 4.0, 10-3).
will save trajectories
set to 0.001. {L, Lg) is set to (0.5. 2.0} for the scenario
We the codes provided by the authors for all baseline algorithms.
14

---

Under review as a conference paper at ICLR 2023
B.1 SUPPLEMENTARY INTERPRETATION OF NRT's DYNAMICALLY AUGMENTED NEURAL NETWORK STRUCTURE
In this paper, at the beginning of learning. when no revisitation is detected. we maintain local Q-networks as CDS (Li al. 2021) with a QMIX-style mixing network to estimate Qtot-
Based on each revisitation, we separate the whole joint observation space into sub-spaces with Eq.3] In this section, for convenience, we use sub-space to represent sub- joint observation space which is dynamically separated along with the detection of revisitaion. To provide sufficient policy representation capacity, we dynamically augment the neural network structure for each sub-space as shown in Fig. 2
The last layers of agents' local Q-networks are independent across sub-spaces, while the previous layers are shared for benefits learning efficiency from parameter sharing. Here we name the augmented last layer of agents' local Q-networks the augmented local- Q branch activated in the sub-space of related revisitation. The original last layer of agents' local Q-networks initialized at the beginning of learning is named default local-Q branch activated when no revisitation is detected or in the sub-space related to no revisitation.
For achieving sufficient representational capacity of the mixing network, augment it along with augmentations of local Q-networks as shown in Fig. 2
The original QMIX (Rashid et al.
2018 calculates Quo with:
Qeo = ((Q), ((Q1,..,QQ)W.. Qn]Wi + b,) + b2,
(6)
where Q, is the local Q-value of agent i E 7, W, a X m matrix, b, and W2 are vectors with m dimensions, b2 is a variable with dimension. W1 and W2 are both with non-negative values. W1. W2, b1, and b2 are all outputs of several hypernetworks with the state input.
However, the shared mixing network might not have enough capacity while the number of local-Q branches increasing. Thus we further expand the mixing network. Our QMIX-style mixing network
Qrot = ([Q),... 2n 2n]Wi WT + (W + WDD) + b2 + bB W WT + b,) + bb) + (IQ1....,Q... QnIWi + b.) + bn)
= =Q + Qt
where WB is vector with dimensions and by is a variable with 1 dimension. Qi is shared among sub-spaces with shared parameters Wi, by. W2, and b2. Q an individual part of each sub-space's mixing network with individual parameters WB and bg. Here name the augmented WB and by related to each revisitation as the augmented mixing network branch. The original WB and bn initialized at the beginning of learning is named default mixing network branch activated when no revisitation is detected or the sub-space related to no revisitation.
In its current form, the mixing network relays Q Q.at arbitrarily- On the contrary, expect credit assignments across agents (achieved by the mixing network) to not differ too much between sub-spaces for stability. Thus we add an Ll regularization mixing network branches to encourage them to work only when necessary.
The original QMIX (Rashid al. 2018) train Qtoe with
[(() = Σ (ufot Quoe (T,
(8)
where yoo = + max, Qroe (T',u,, 0) 0 are the parameters of a target network as in DQN, and b is the batch size of transitions sampled from the replaybuffer.
In this paper, we train Qtoe with
15

---

Under review as a conference paper at ICLR 2023
b
((0) = Σ (vt QIo s;)))
Σ
11 111,
(9)
where (1) yoot = r + pd + ? maxu' Qioe (T's u', s';0 _ is environmental rewards, and yd can be any intrinsic rewards. In this paper, we use intrinsic rewards from CDS (Li et al. 20021). which is named as r'Ds- (2) Q = (stopgrad [Q..... 2n b B + by is an additional regularization loss item. stopgrad is used to stop gradient back-propagation. Thus we can only regularize parameters related to each mixing network branch.
During decentralized execution, one agent can only obtaín local observation. Thus, we introduce the marginal condition Eg. 4based on Eq. guide each agent to select local-Q branches for sampling as shown Algorithm | To maintain consistency between sampling and training, Algorithm is also used to select each agent's local Q-network branches while training. To solve the question about how to switch augmented mixing network branches when agents switch various local-Q branches at one time step, each augmented mixing network branch will be activated only when more than half of agents choose the corresponding augmented local-Q branch. Otherwise, the default mixing network branch is switched.
Algorithm The sampling process of NRT
while Simulating do
2:
if' augmented local-Q branches then
3: All agents activate the default local-Q branch to select actions
4: else
5:
for agent E I do
6:
for augmented branch id b from the earliest created branch to the latest created branch do if o; E S2 based on Eq. then
7:
Agent activates the 6 th augmented local-Q branch select actions and stops searching augmented branches.
8:
end if end for no augmented local-Q -eal-Q branch is activated by agent then
9:
end Agent i activates the default local-Q branch to select actions.
11:
12: end for
13:
end if
14:
end while
15:
Return trajectories for training.
C EXPERIMENTAL DETAILS
C.1 JS DISTANCES CALCULATED DURING TRAINING IN GRF
QMIX
CDS
NRT (RT
18
1.2
mmm
"Becighle aendiies
Figure 10: JS distances calculated during training Academy Counterattack Hard under the deterministic setting
16

---

Under review as a conference paper at ICLR 2023
We further show JS distances calculated during training in Ceademy_Counterattaac. Hard under the deterministic setting as a representative of GRF environments. The definition of the x-y axis is the same that introduced in Sec. 4 Similar to toy maze environment, JS distances between historical points and checkpoints periodically fluctuate under the training of QMIX and CDS, as shown in Fig. left left and middle. Meanwhile, under approach's guidance of preventing revisitation, policies learned in complex environments achieve stable improvement, as shown in Fig. [0 right. Taking advantage from stable improved exploration, our approach achieves outstanding performance in challenging GRF scenarios.
C.2
THE 2D-COLLOR PLOT OF JS DISTANCES DURING TRAINING
QMIX
CDS
NRT (ours)
10 24 10.20
Figure 11: The 2D-color plot of Fig.
We demonstrate the 2D-Color Plot of Fig. as shown in Fig. [T] for readers to follow our work's motivations easier. During learning, will store the joint observation distribution in- duced by the joint policy every 100k time steps, named historical point time (the y-axis in Fig. TTP. Meanwhile, for every 100k time step, we will calculate the JS distance between the current distribution and all historical points, named checkpoint time (the x-axis in Fig. [ Half of each picture Fig. 1iis is printed in the same color. That is because checkpoint time is always larger than historical times while calcu- lating the JS distances. For each historical point, compared with checkpoints after it every 100k time steps. In Fig. II right, most JS dis- tances are large and stable until coverage to the optimal strategy, after approach detects and solves revisitation the early period of learning.
niserncall point time (100 k)
Detected
Revisiation
10
11
checkpoint
Figure 12: The 2D-color plot of JS distances be- tween polices learned by our approach until con- verge.
In Fig. 12 we show and enlarge a part Fig- I1 right to demonstrate our approach's 's learning progress before coverage clearly. Through the whole learning period, revisitation means that the exploration achieved at one learning period is actually driving the joint policy to be similar to some historical policies. For example, in Fig. 12] if choose the joint observation distribution counted at 300k time-step as the historical point, checkpoints at 400k and 500k time-step indicate that intrinsic motivations are driving agents explore the environment. However, if we choose the joint observation distribution counted at 100k time-step as the historical point, checkpoints at 400k and 500k time-step indicate that intrinsic motivations are driving agents to re-explore the sub-space that has been explored at 100k time-step. In this paper, we call this phenomenon revisitation and attempt to solve it with (I) augmented neural networks for sufficient policy representation capacity, (2) adjusted intrinsic motivation weight according to joint observation novelty compared with each revisitation historical point, and (3) further punishment revisitation based on KL divergence. Based these novelties, our approach forbids revisitation occur again and achieves the optimal strategy in the maze exploration task by driving agents to explore away from both 100k time-step and 300k time-step, indicating reliable exploration efficiency.
17

---

Under review as a conference paper at ICLR 2023
As for baselines such QMIX (explores with e-greedy) and CDS (explores with intrinsic motivations), revisitation occurs periodically, which heavily influences exploration efficiency and causes agents to be stacked nearing the fixed initial points shown in Fig.
C.3 WILL THE SIZE OF REPLAY BUFFER INFLUENCE REVISITAION?
Buffer: 250k
Buffer: 500k
30
30
I MMM
25
IS distunce
20
20
15
10
-0
200k
100<
600k
BCOK
1M
1.2M
7.4M
Checkpoint time
Checkpoint time
Figure 13: JS distances calculated during training with the CDS algorithm in our maze environment based historical point at 200k time steps
Coming up with the phenomenon of revisitation based on intrinsic motivations is one natural question: Which role does the replay buffer play in revisitation? Here we still use CDS as an example of intrinsic motivations and test it in our maze environment. Fig. [3] demonstrates that the size of replay huffer has trivial influence on revisitaion. In Fig. 13 left, it seems that revisitation occurs according to the size of the replay buffer. However, after we multplyy the replay buffer's size from 250k time steps to 500k time steps, the interval of periodical revisitation is similar to that with smaller replay buffer as shown in Fig. right. Thus, in this paper, we choose to fix our replay buffer's size as baselines and adjust intrinsic motivations with augmented policy representation capacity.
C.4 EXPERIMENTAL RESULTS PLOTTED WITH MEANS AND STANDARD DEVIATIONS
NRT (aurs)
CDS
MAVEN
QMIX
OPLEX
Academy vs with Keeper (Deteminnittic)
Academy Counterattack Easy (Determinsitic)
Academy Counterattack Hard (Deteminnsttic)
100
100
100
Test Win 56
75
75-
75-
50
50-
50-
25
25
25
0.0
0.2
0.4
0.8
1.0
0.0
0.5
1.5
2.0
1.5 (mil)
2.0
2.5
T (mil)
T (mil)
Acadomy
Keeper (Stochastic)
Academy Counteratlack Easy (Stochastic)
Academy Counteratiack (Stochastic)
80
80-
60
Test Winn %
60
40
40
20
20-
0
1.0
1.5
2.0
2
(mmll
T (mll)
T (ml)
Figure 14: Comparison of our approach against baseline algorithms on GRF with deterministic environment seeds or stochastic environment seeds.
We re-plot our experimental results with means and standard deviations as shown in Fig. and Fig. 1.5 The comparison between our algorithm and baseline consistent with that measured with
18

---

Under review as a conference paper at ICLR 2023
NRT
CDS
MAVEN
QMIX
QPLEX
(sparse reward)
2s (sparse reward)
(sparse reward)
100
100
80
Test Win %
80
50
25
25
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.5
1.0
1.5
2.0
T (mil)
(mill
(miil)
Figure 15: Comparison of our approach against baseline algorithms on SMAC with sparse rewards.
median performance. In general, approach achieves better performance in 4 out of 6 GRF scenarios (slightly better in Academy 3 vs with Keeper based on the stochastic environment) and 2 out of SMAC maps.
19


Reviews:
[{"review_id": "hePXVoZxgC", "reviewer": "Reviewer_XHpU", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 2, "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": "This paper tackles the challenge of exploration in multi agent reinforcement learning. The paper highlights the difficulty that in the multi-agent setting the value of intrinsic rewards can fluctuate and may sometimes increase, making previously visited states appear attractive again. As a solution the authors present Never Revisit an exploration technique for multi agent reinforcement learning. The authors evaluate this method on a maze environment and Google research football on show improved results over existing baselines.", "summary_of_the_review": "Thought the paper seem to display interesting empirical results I would advise the authors to rework section 3 of their manuscript to make it easier to understand. In its current I'm unable to properly judge the paper and for that reason I cannot recommend acceptance.", "strength_and_weaknesses": "Strengths:\n\n_ The paper presents decent results on Google research football that improve over existing multi agent exploration methods.\n\nWeaknesses:\n\nOverall despite several reads I was not able to understand the method proposed by the authors.\nThe paper relies on many concepts and terms are not properly defined.\nThe whole architecture is never properly defined and there is also no pseudo of the algorithm developed in the paper.\nFew examples:\n\nIn Definition 1, \\pi_t is not defined and it is not clear that (t'', t) is an interval\nIn section 3.2, the mixing network, branches and local utility network are not defined.\nThe paper relies on CDS but it is never properly introduced, same goes for the r^short the intrinsic rewards introduced by CDS", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "f5IAEZkZZi", "reviewer": "Reviewer_iFpg", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "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": "The authors propose a novel multi-agent architecture and intrinsic reward scheme for avoiding the issue of revisiting previously seen states in multi-agent reinforcement learning. They demonstrate improved performance in a didactic domain as well as in Google Research Football.", "summary_of_the_review": "This work achieves impressive performance on a challenging domain by addressing a well-motivated problem; however, a significant portion of the methodological decisions (i.e. branching architecture) are lacking convincing motivation and important details. At this time I cannot recommend acceptance; however, I am willing to revise my opinion if the clarity of section 3.2 is significantly improved (in terms of details regarding how branching architectures factor into training and execution as well as motivation for why they are necessary).", "strength_and_weaknesses": "# Strengths \n* The challenge of revisitation is well motivated.\n* The proposed method seems effective for avoiding the revisitation issue.\n* Evaluation is performed on the Google Research Football setting which is still challenging for many cooperative MARL methods.\n\n# Weaknesses\n* It is not clear from the writing whether revisitation is uniquely an issue in multi-agent problems. I could imagine that learning decentralized policies accentuates this issue, but it should be explicitly motivated.\n* The design decisions in the methods section (specifically revolving around the branching architecture) could be motivated better (more details in questions below).\n* The approach seems as though it would scale poorly, as it requires storing new parameters for each \"revisitation tuple\" detected. Furthermore, the computation of intrinsic rewards scales with the number of revisitation tuples.\n* The method's generality would be more convincing if also tested on the standard StarCraft benchmarks in addition to GRF.\n\n# Questions\n* Doesn't computing revisitation tuples require storing all transitions seen over the course of training? And naively it would take $O(T^2)$ time since you have to iterate over $t'$ and $t''$. The details on this are a bit sparse: how do you overcome these challenges? I assume some sort of sub-sampling is involved.\n* It is not clear why branching the Q-function is useful for avoiding revisitation. Why would re-using old policies help avoid revisiting previously seen sub-spaces? Intuitively it would do the opposite. Is the point that you can use these branches to \"absorb\" bad data from thoroughly explored states that come from your replay buffer such that the new branches are only trained on data from novel sub-spaces? If so, perhaps a simpler filtering or re-weighting scheme scheme could be similarly effective and less computationally expensive.\n* How are the branched functions trained? Do you update different ones depending on whether they meet the criteria in Eqn 2? Perhaps more explanation here will address the question in the previous bullet as well.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "BpbY2bFMaE", "reviewer": "Reviewer_hnNg", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 2, "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": "The paper aims to improve exploration in MARL by preventing revisiting of previously explored regions. The authors propose an extension of QMIX with an arbitrary intrinsic reward module (CDS in the experiments). The proposed method NRT makes snapshots of a density estimator to detect when the distribution of joint observations changes. If a revisitation of a previously explored part of the joint observation space is detected, a snapshot of the last layer of the mixing network and the local Q-network is saved as well. Using these saved networks the authors claim they found a method to scale the out-of-the-box intrinsic reward to avoid reexploration of known areas. Empirical results are not entirely clear, but seem to show that the proposed methods improves performance.", "summary_of_the_review": "The paper was in the current form not understandable to the reviewer. The performance of the method appears to be good, but it is not clear how and why this is, and what the downsides of the proposed methods are.", "strength_and_weaknesses": "**STRENGTH**\n\nThe problem of re-exploration is relevant, in particular for MARL, and the idea of making snapshots of the network parameters could in principle be a solution to it. The results also look promising.\n\n**WEAKNESS**\n\nThe proposed method is not clear to this reviewer. Before a reliable review can be made, the reviewer would like to ask the authors to answer the following questions (and try to clarify them in the text as well):\n1. Which role does the replay buffer play in revisitation? As long as a sample is in the replay buffer, it will be regularly updated. Does revisiting occur after a sample leaves the buffer, or for some other reason?\n2. What is stored when you \"store the current joint observation distribution estimator\"? The output? The paramters $\\xi$? And how often do you save them? Is your algorithm constant memory, or do the memory requirements grow linearly with time?\n3. When you \"add a new branch\", which the reviewer interprets as saving (or detaching) the network parameters of the last layer, why do you expect the outputs of both the local Q-network and the mixing network to remain meaningful after the \"shared modules\" have been changed by gradient descent? Wouldn't any substantial change in the shared parameters require a change in the \"saved\" parameters as well? \n4. During exploration (\"execution\"?), which branch is used to select actions? It seems that (eq.2) selects a branch, but what is gained when the actions are drawn from an old policy? Or do you always draw actions from the \"default branch\" and use (eq.2) only to modify the intrinsic reward?\n5. Details on the modified intrinsic reward are hard to decipher. However, it seems that you compute a running average of a scaling factor $1+\\bar\\alpha$, which itself is clipped to be between $L_1$ and $L_2$. The appendix names them as usually $L_1=0.5$ and $L_2=2$, but why these values? How can the reader interpret $\\bar \\alpha$? \n6. Wouldn't it be conceptually simpler to estimate the joint observation density of the *entire past* and scale down intrinsic rewards for observations the agent has already observed?\n7. How should the 3D plots be read? What is \"checkpoint time\" and what is \"historical point time\"? Which graph would indicate a \"non-revisiting\" agent? If it is a front of high JS distances for new checkpoints, wouldn't a 2D-colour-plot be clearer to read?\n8. Plotting the median and the variance is unorthodox and makes the results hard to interpret. Are your results statistically significant (or at least appear that way)? If you re-plot them with means and standard deviations, do the standard deviations of NRT and the best competitor overlap?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "9JO10ONMAny", "reviewer": "Reviewer_2T1q", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "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": "This paper studies multi-agent exploration, which is an important problem for more efficient multi-agent reinforcement learning. The authors first pointed out that the issue of ‘revisition’ hurts the exploration and learning efficiency of  existing intrinsic exploration methods. To address the issue, the author ​​proposed to add branches to agents’ local Q-networks and the mixing network to prevent receiving repeated observations. In addition, auxiliary intrinsic rewards are proposed to further avoid revisitation. The proposed approach is evaluated on three academy tasks of Google research Football (GRF). The results show that the proposed approach outperforms baselines.", "summary_of_the_review": "In summary, the paper identified and addressed the important ‘revisitation’ problem. However, the presentation of technical content is unclear and the experimental results are not very convincing. Major revision is needed.\n", "strength_and_weaknesses": "### Strength:  \n\nThe paper is well-motivated and the problem it aimed to address is important.  Specifically,  the paper identified and formally defined the ‘revisitation’ issue. The reviewer thinks it is an important step for our community to better address the issue. \n\n### Weakness:\n\nWhile the motivation and the introduction is clear, the reviewer has some concerns regarding the rigorousness of the presentation of the technical content and the generality of the experimental results. Please see the detailed comments below:\n\n1. The reviewer found Sec 3.2 difficult to follow. Many terms are either undefined or vaguely defined.   \n\n    - In p.4, the paper reads ‘augment the mixing network in the CTDE framework to achieve diverse credit assignments across agents’. It is unclear what ‘diverse credit assignments’ is referring to. A formal definition would be helpful.   \n\n   - In p.4, the paper reads ‘The red item added to the independent part of each class is an L1 regularization term for filtering out useless diversity.’ Both ‘red item’ and ‘the independent part’ are undefined in the text. In addition, it is unclear to the reviewer what is ’useless diversity’ referring to.   \n\n   - In p.4 the paper mentioned ‘According to each agent’s independent observation, the first class satisfying the marginal condition in Eq. 2 …’ Doesn’t Eq.2 consider joint observation?   \n\n   - It is unclear to the reviewer how Eq (2) helps select a branch that prevents revisitation. Could you elaborate?    \n\n2. While the proposed approach outperformed baselines in some tasks of GRF, the reviewer found reporting results on only three tasks not convincing. Particularly, the three selected tasks involved a very limited number of controlled agents. It is unclear if the proposed approach could be applied to more complex settings. Reporting results in GRF 11 vs 11 full game or in StarCraft II micromanagement challenge (SMAC) would be very helpful. \n\n\n3. The term ‘sub-space’ is used throughout the paper without formal definition. \n\n       \n4. Figure 1 reports the ‘coverage rate’ of baselines and the proposed approach. It is unclear to the reviewer how the ‘coverage rate’ is computed. Without the definition of the metrics, it is hard to interpret the results. \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject