Iteratively Learning Novel Strategies with Diversity Measured in State Distances
Authors: Wei Fu
Weihua Du
Jingwei Li
Sunli Chen
Jingzhao Zhang
Yi Wu
Venue: Submitted to ICLR 2023 (2023)
Keywords: diverse behavior
multi-agent reinforcement learning
deep reinforcement learning

Abstract: In complex reinforcement learning (RL) problems, policies with similar rewards may have substantially different behaviors. Yet, to not only optimize rewards but also discover as many diverse strategies as possible remains a challenging problem. A natural approach to this task is constrained population-based training (PBT), which simultaneously learns a collection of policies subject to diversity constraints. However, due to the unaffordable computation cost of PBT, we adopt an alternative approach, iterative learning (IL), which repeatedly learns a single novel policy that is sufficiently different from previous ones. We first analyze these two frameworks and prove that, for any policy pool derived by PBT, we can always use IL to obtain another policy pool of the same rewards and competitive diversity scores. In addition, we also present a novel state-based diversity measure with two tractable realizations. Such a metric can impose a stronger and much smoother diversity constraint than existing action-based metrics. Combining IL and the state-based diversity measure, we develop a powerful diversity-driven RL algorithm, State-based Intrinsic-reward Policy Optimization (SIPO), with provable convergence properties. We empirically examine our algorithm in complex multi-agent environments including StarCraft Multi-Agent Challenge and Google Research Football. SIPO is able to consistently derive strategically diverse and human-interpretable policies that cannot be discovered by existing baselines.

Under review as a conference paper at ICLR 2023
ITERATIVELY LEARNING NOVEL STRATEGIES WITH DIVERSITY MEASURED IN STATE DISTANCES
Anonymous authors Paper under double-blind review
ABSTRACT
In complex reinforcement learning (RL) problems, policies with similar rewards may have substantially different behaviors. Yet, to not only optimize rewards but also discover as many diverse strategies as possible remains a challenging problem. A natural approach this task is constrained population-baser training (PBT), which simultaneously learns a collection of policies subject to diversity constraints. However, due to the unaffordable computation cost of PBT, we adopt alternative approach, iterative learning (IL), which repeatedly learns single novel policy that sufficiently different from previous ones. We first analyze these two frameworks and prove that, for any policy pool derived by PBT, always use IL to obtain another policy pool of the same rewards and competitive diversity scores. In addition, we also present novel state-based diversity measure with two tractable realizations. Such a metric can impose stronger and much smoother diversity constraint than existing action-based metrics. Combining IL and the state-based diversity measure, we develop a powerful diversity-driven RL algorithm, State-based Intrinsic-reward Policy Optimization (SIPO), with prov- able convergence properties. We empirically examine our algorithm in complex multi-agent environments including StarCraft Multi-Agent Challenge and Google Research Football. In these environments, SIPO is able to consistently derive strategically diverse and human-interpretable policies that cannot be discovered by existing baselines.
INTRODUCTION
A consensus in deep learning (DL) is that most local optima have similar losses to the global opti- mum (Venturi et al., 2018 Roughgarden| 2020; Ma 202I). Hence, via stochastic gradient descent (SGD), most DL works only focus the final performance of the learned model without consider- ing which local optimum SGD discovers. However, such a performance-orienter paradigm can be problematic for reinforcement learning (RL) because it is typical in complex RL problems that poli- cies with the same reward may have substantially different behaviors. For example, a high-reward agent in boat-driving game either carefully drive the boat or keep turning around to exploit an environment bug (Clark& & Amodei 2016); humanoid football AI can adopt any dribbling or shooting behaviors score goal (Liu al.) 2002);; a strong StarCraft AI can take very distinct construction and attacking strategies (Vinyals et al. 2019). Thus, it is a fundamental problem for an RL algorithm to not only optimize rewards but also discover as many diverse strategies as possible.
In order to obtain diverse RL strategies, we can naturally extend single-policy learning to population- based training (PBT). The problem can be formulated as a constrained optimization problem by si- multaneously learning a collection of policies subject to policy diversity constraints (Parker-Holder et al. 20205 Lupu et al. 202T). However, since multiple policies are jointly optimized, PBT can be computationally challenging (Omidsafiiii al. 2020). Thereforr, greedy alternative is iterative learning, which iteratively learns a single novel policy that is sufficiently different from previous ones Masood & Doshi- Velez 2019 Zhou al. 2022) Since only one policy is learned per itera- tion, IL can largely simplify optimization. However, there have not been any theoretical guarantees on the performance the convergence properties of IL methods.
In addition to the computation frameworks, how to quantitatively measure the difference (i.c., diver- sity) between two policies remains open question well. Mutual information (MI) is perhaps

---

Under review as a conference paper at ICLR 2023
the most popular diversity measure (Eysenbach et al. 2019). Although MI reveals great potential to discover diverse locomotion skills, it is proved in Eysenbach et al. (2022) that maximizing MI will not recover the set of optimal policies w.r.. the environment reward. Therefore, MI-based methods often serve as a pre-training phase for downstream tasks (Sharma et al. 2020 Campos et al. 2020). Another category of diversity measure is based the action distributions, such as Wasserstein dis- lance (Sun et al. 2020). cross-entropy (Zhou et al., (2022). and Fensen-Shannoe divergence (Lupu 2021) ). Action-based measures are straightforward evaluate and optimize. However, we will show in Sec. that such metric can completely fail in simple scenarios.
al.
In this paper, we present comprehensive studies address the two issues above. First, we pro- vide an in-depth analysis of the two computation frameworks, namely PBT and IL. for learning diverse strategies. We theoretically prove that, addition to simplified optimization thanks to fewer constraints, II. can discover solutions with the same reward as PBT with at least half of the diver- sity score. Regarding the diversity measure, we consider two concrete scenarios, i.e., grid-world world navigation and Google Research Football (GRF). In the grid-world example, we construct visually different strategies that cannot be distinguished by popular action-based diversity measures, In the GRF example, we show that duplicated actions taken by idle player drastically influence the action-baseed diversity score. Consequently, we argue that an effective diversity measure should focus on state distances instead of action distributions.
Combining II. and a state-based diversity measure, we design a generic and effective algorithm, State-based Intrinsic-reward Policy Optimization (SIPO), for discovering diverse RL strategies in an iterative fashion. In each iteration, SIPO learns a single novel policy with state-based diversity constraints w.r.t. policies learned in previous iterations. We further solve this constrained opti- mization problem via Lagrangian method and two-timescale gradient descent ascent (GDA) (Lin) al., 2020). Theoretical results show that our algorithm guaranteed to converge to neighbour of e-approximate KKT point (Dutta et al. 2013). Regarding the state-based measure, we provide two practical realizations, including straightforward version based on the RBF kernel and a more general learning-based variant using Wasserstein distance.
We validate the effectiveness of our algorithm in two challenging multi-agent environments: Star- Craft Multi-Agent Challenge (Samvelyan et al. 2019) and Google Research Football (Kurach al.) 2020). Specifically, our algorithm can successfully discover 6 distinct numan-interpretable strategies in the GRF 3-vs-1 scenario and 4 strategies in two 1 1-pllaeer GRF scenarios, namely counter-attack and cornr,, without any domain knowledge, which are substantially more than existing baselines.
RELATED WORK
Discovering diverse solutions has been a long-established problem (Miller & Shaw
1996; Deb &
Saha
2010 Lee et al. 2022) with wide range of applications in robotic control
(Cully et al.,
2015 Kumar et al. 2020). dialogues (Li et al. 2016), game AI (Vinyals et al. 2019 Lupu al.
2021
design (Gupta et al. 202T) and emergent behaviors (Liu et al. 2019 Baker et al.
2020: Tang
al. 2021). Early works are primarily based on the setting of multi-objective optimization (Mouret
& Clune| 2015 Pugh et al. 2016 Ma et al. 2020 Nilsson & Cully 2021 Pierrot et al.
2022).
which assumes set of reward functions given advance. In RL, this is also related reward
shaping (Ng et al.) 1999 Babes et al. 2008 Devlin & Kudenko 2011 Tang et al.] 2021). We
consider learning diverse policies without any domain knowledge.
Population-based training (PBT) is the most popular framework for producing diverse solutions by jointly learning separate policies. Representative algorithms include evolutionary computa- tion (Wang et al. 2019 Long et al.) 2020 Parker- et al. (2020b), league training (Vinyals et al. Jaderberg et 2019), computing Hessian matrix (Parker-Holder et al. (020a)) or con- strained optimization with a diversity measure over the policy population (Lupu et al. 2001 /Zho ctt al. 1 Li et al. 2021 Liu et al. 20211). An improvement over PBT is to learn a latent variable policy instead of separate ones to improve sample efficiency. Prior works have incorporate different domain knowledge to design the latent code, such as action clustering (Wang et al., 2021). agent identities (Li et al. 2021) prosocial level (Peysakhovich & Lerer 2018 Baker et al. 2020). The latent variable can be also learned in an unsupervised fashion. DIYAN (Eyenbbach et al. 2019) and its variants (Kumar et al. 2020 Osa et al. 2022) learns latent-conditioned policies by maxi-
2

---

Under review as a conference paper at ICLR 2023
mizing the mutual information between states and the latent variable. The discovered behaviors primarily low-level motion skills rather than high-reward strategies (Eysenbach et al. 2022)
Iterative learning (IL) simplifies PBT by only optimizing single policy subject to different diver- sity measures, such as maximum mean discrepancy (Masood & Doshi- 2019), Wasserstein distance actions (Sun et al. 2020), and cross entropy (Zhou et al.] 20022, which are often action- based. We adopt a purely state- based measure. Some other works require an expensive clustering process before each optimization iteration (Zhang al. al.] (2199) or domain-specific features (Zahavy et al. 2021) while we consider measures that can be efficiently optimized in an end-to-end fashion. Besides. Pacchiano al. (2020) learns kernel-based score function to guide policy optimization. The score function is conceptually similar to our Wasserstein flaserrtein-distance-- tistance-based diversity measure but applied to parallel setting with more restricted expressiveness power.
3 PRELIMINARY
Notation: We consider Partially Observable Markov Decision Process (POMDP) Spaan 2012). defined by a tuple M (S.A, O,v, H). is the state space. A and O are the action and observation space. F:S AA" - R is the reward function. O : S O is the observation function. H the horizon. P the transition function. For state 8, 8 E and an action a E A, the transition probability from 8 to s' by executing action a is P(s' 8, a). At timestep h. the agent receives an observation On, = (sk)) from the current state 5y and outputs an action ap E A w.r.. its policy 0 A (A). The RL objective (TT), i.e., expected return, is defined by J(T)
(ap..)))((P..)) Σ h==1 r(s,, as) The discounted factor is omitted here to simplify notations. The above formulation can naturally extended to cooperative multi-agent settings, where æ and correspond to the joint policy and the shared reward. We follow the standard POMDP notations for conciseness and evaluate our algorithm in complex cooperative multi-agent scenarios since multi- agent games are substantially more challenging than single-agent ones.
Finally, in order to discover diverse strategies, we aim to learn a set of M policies { M such that all of these policies are locally optimal under J-) but mutually distinct subject to some diversity measure .) x A - R, which captures the difference between two policies. We present two popular computation procedures for this purpose.
Population- Based Training (PBT): PBT is a straightforward formulation the diversity discovery problem by jointly learning M policies {mrM subject to pairwise diversity constraints, i.e.,
M
max
J(Z,)
s.t. D(T,, TR) > 6 Vj.k E [M] j * k,
(1)
where 8 is a threshold. Despite a precise formulation, PBT poses severe optimization challenges.
Iterative Learning (II.:: II is greedy approximation of PBT by iteratively learning novel policies.
In the i-th (1 & i & M) iteration, IL solves the following constrained optimization problem
arg max
J(T:)
s.t. D(T. mJ) > 8 VIεja!
IL runs unconstrained RL at first and then solves incrementally more constrained problems.
Action-Based Diversity Measure: We briefly introduce the diversity measure in this paragraph. Many prior works define D(.,)) over actions, which can be formally summarized by
DA(T,, T,) = Es-q(s) [Da(m(( (. (1s))]
where g (SS) denotes some specific state distribution, and ( A A ER measures the difference between action distributions. DA can be any probability distance such as Wasserstein distance (Sun et al., 2020). -hasenn- Divergence (Lupu et af.) (02T), cross-entropy (Zhou et al. 2022), simply the T-2 distance given continuous action space (Parker-Holder et al. 2020b).
3

---

Under review as a conference paper at ICLR 2023
4 ANALYSIS OF EXISTING DIVERSITY-DISCOVERY APPROACHES
In this section, we conduct both theoretical and quantitative analysis of existing approaches to mo- tivate our method. We first compare computation frameworks, namely PBT and IL, in Sec. 4.1 and then present concrete failure examples for action-based diversity measures in Sec. 4.2
4.1 COMPUTATION FRAMEWORK: POPULATION- D OR ITERATIVE LEARNING?
Theoretical Comparison: We consider the simplest motivation example in the setting of linear programming intuitively illustrate the computation challenges. We simply assume that я, is scalar, and (TT)) is linear in R; and D(T,, πy) = IT; Tyl. In our definition, PBT involves (2M²) variables in single constrained optimization problem while IL involves ((M) variables in all. It is well-known that the complexity of linear programming is a high degree polynomial (degree 3 higher depending on the algorithm) w.r.f. the number of variables (Bertsimas & Tsitsiklis, 1997]. Therefore, even in the linear case, we can notice that more constraints can pose substantial challenges to the optimization problem. This issue can be more severe in RL due complex solution space and large training variance.
Although IL can be optimized efficiently, remains unclear whether IL, as greedy approximation of PBT, can obtain solutions of comparable rewards. Fig. [ shows the worst case in 1-D setting when the policies found by IL (green) can indeed have much lower rewards than the PBT solution (red) when subject to the same diversity constraint. However, we will show in the next theorem that IL is guarantced to have no worse rewards than PBT by trading off half of the diversity.
Theorem 4.1. Assume D is a distance metric. Denote the optimal value of Eq. 7 as Tí. Let
Ta = S ((Tt) where
#. arg max 31
J(ms)
s.t. ((T,, 8/2 viej<i
(4)
for 1, 1,..., M, then T2 3 Ti.
Proof. See Appendix E.
The above theorem provides quality guaran- tee for the IL solutions. The proof can be intu- itively explained by the 1-D example Fig. [ Assuming the worst case where the first II. so- lution lies in the middle of plateau with size 6 (green 1), then the next solution with thresh- old å must locate outside the plateau with a low reward. However, if the threshold is halved, the IL. solutions are guaranteed to locate in the high-reward area (blue and 2). Thm. 4.. shows that, for any policy pool derived by PBT, we can always use IL to obtain another policy pool, which has the same rewards and compa- rable diversity scores. We remark that the worst case in Fig. may not be common for RL environ- ments in practice.
[(t)
optimal solution
solution found by IL
with threshold 8/2
worst-case solution found by IL with threshold 8
8/2 6/2 6/2 6/2
Figure 1: 1-D worst case of With threshold II. finds solutions with inferior rewards. However, IL can find optimal solutions if the threshold is halved.
We empirically compare PBT and IL in a 2-D navigation environment with one agent and Nr. landmarks (blue circles), as shown in Fig. 2 The reward is +1 if the agent successfully navigates to land- marks and 0 otherwise. Before training, landmark posi- tions are randomly initialized subject to pre-specified distance threshold per episode. We train Nr policies us- ing both PBT and IL discover strategies towards each of these landmarks. Specifically, we simply take D(T,, TT) as the La distance of the final state reached by т. and Ty. i.e., D(T,, TT)) = || 8 12. We solve this problem via Lagrangian multiplier with details in Appendix
Empirical Results:
Table 1:
The number of discovered land- marks by PBT and II across seeds with standard deviation in the bracket.
setting
PBT
IL
No = 4
(1.0)
3.5(0.5)
N2 5
2.2 (0.9)
4.5(0.5)
4

---

Under review as a conference paper at ICLR 2023
Training Progress
Epoch 0
Epoch 10
Epoch
Epoch 30
PBT
IL
Iteration
Iteration 2
Iteration 3
lteration
Figure 2: Illustration of the learning process of PBT and IL 2-D navigation environment with 4 modes. PBT will not uniformly converge to different landmarks as computation can be either too costly or unstable. By contrast, II. repeatedly excludes a particular landmark, such that policy the next iteration can continuously explore until novel landmark is discovered.
Agent
Goal
Table 2: Diversity measures of the grid-world example. Bold numbers indicate larger values. Computation details can found in Appendix Divergence,
Ja
(KL=KLL divergence, JSD,= generalized
EMD-Earth Moving Distance)
based (Da)
state-hused (Ds)
JSD:
JSD,/EMD
La
norm
D ( m2)
small +
log
1/2
VT
2v
5.7
D(11, ma)
large
+00
log
1/8
2v6
11.3
Figure 3: (left) A grid- environment with size NG and different optimal policies. In- tuitively, D( π2) < D( π3) because πı (purple) and IT (blue) both move along the diagonal. However, action-based diversity measures can give ( m2) DA(31, (right), which moti- vates our proposal of state-distance based diversity measure.
Table I shows the number of discovered landmarks by PBT and IL. IL performs consistently better than PBT even in this simple example. We illustrate the learning process of PBT and IL in Fig. 2 IL, due to its computation efficiency, can afford to run longer iterations and tolerate larger exploration noises. Hence. can converge easily to diverse solutions by imposing large diversity constraint. The PBT. however, only converges when the exploration is faint, otherwise it diverges converges too slowly.
4.2 CHOICE OF DIVERSITY MEASURE: ACTION-BASED OR STATE-BASED?
We then analyze the impact of different diversity measures. We first show that action-based measures can often fail even for very simple tasks.
Action-Based Measure: Although action-based measures are easy compute and widely used, we present concrete failure cases here. The first example single-agent grid-world with size Ng. where agent spawns the top left and needs to navigate to the bottom right. We consider three different policies shown in Fig. 3 и (purple) and Ta (blue) move along the diagonal while Ty (red) moves along the boundary. Humans
naturally conclude that is visually different from л and T2. i... ( T2) < D( R3), especially when No is large. However, the actions of σ; and ma along the trajectory are totally disjoint. Consequently, action-based measures will have large value
5

---

Under review as a conference paper at ICLR 2023
on 1(T T2). We compute 1TT (TT)))T)))))))))))))()))(() and D( ms) based on popular iitioo-based diversities measures Table 2 where the obtained values largely violates human intuition.
Next, consider more realistic and complicated multi-agent football scenario in Fig. where an idle player in the backyard takes an arbitrary action, such as "pass", "shoot" or "slide" without involving in the attack at all. Although the idle player stays still with effect on the team strategy at all, action-based measures can produce high diversity scores when the idle player takes different duplicated actions, leading to visually indistinguishable solutions.
State-Based Measure:
Based on the previous examples, we propose focus states rather than action when designing a diversity measure. Formally, denote the state distribution induced by π as pa. We define the state ddistance-basee di- versity measure as
(T( = Bo 1g (d (8,
(5)
d is distance metric over S S. g: R function. E [[Ha, ( is distribution over state pairs. T(U M45y) denotes the collection of all distributions S with marginals Mx. and Mr, on the first and second factors respectively.
R - R is monotonic
S
Driabing Player
Our proposed measure is soiely defined over states and such a metric can impose stronger and much smoother diversity constraint than existing action- based metrics. The state dis- tance in the measure encourages the policies to reach visually different states leading to desired diversity. We compute two simple state-based measures, i.e., the L2 norm and the Earth Moving Distance (EMD), for the grid- world example in Ta- ble which is consistent with human intuition.
Player
Figure 4: agent football. For players who are not involved in the attack, actions like "pass". "shoot". and "slide" result in the consequence. Diversity measures should not focus on these actions.
Duplicate actions in multi-
4.3 PRACTICAL REMARK
Based on the analysis in the above subsections, we conclude that PBT can pose severe optimization challenges, and that action-based diversity measures can often fail because they may not correctly reflect behavioral differences. By contrast, IL and state-based diversity measures are free from the above issues and should be preferred in challenging RL applications. Therefore, we consider how to develop powerful algorithm for discovering diverse policies that can leverage both algorithmic design choices. In the next section, combine these ideas with theoretically sound optimization algorithm, Gradient Descent Ascent (GDA), towards an efficient and practical algorithm for learning diverse policies.
METHOD
5.1
ALGORITHM OVERVIEW
In this section, develop powerful diversity-driven RL algorithm, State-based Intrinsic-reward Policy Optimization (SIPO), by combining IL and state-distance- iterations discover M distinct policies. At the i-th iteration, we solve Problem (2) by converting it into unconstrained optimization using the Lagrange method. The unconstrained optimization can be written
measures. SIPO runs M
min
max A,20, Ejjt J(TT))
X (Ds(Tn)z))
(6)
where X, (1 adopt two-timescale Gradient Descent Ascent (GDA) (Lin et al. 2020) to solve the above minimax optimization, i.c., performing gradient descent over т; and gradient ascent over XÚ with different learning rates. We also clip the dual variables X, which plays important role both in our theorem
are Lagrange multipliers and {m:) 1--1 are previously obtained policies. We 1-1

---

Under review as a conference paper at ICLR 2023
and in empirical convergence. However, (T( m;) cannot be directly optimized through gradient- based methods because it is related to the states visited by Rş. As a popular solution (Zhou et al. 2022). cast Ds(T,, T.. mT)) the summation of intrinsic rewards and optimize it via policy gradient. The pseudocode of SIPO can be found in Appendix G
An important property of SIPO the convergence guarantee. We present informal illustration in Thm. 5.1 and present the formal theorem with proof Appendix E.2
Theorem 5.1. (Informal) Under moderate assumptions, SIPO converges to a neighborhood of e- approximate KKT point.
Remark: Please see the appendix for detailed description of the assumptions and the proof. We assumed that the reward and the distance Ds are smooth in policies. practice, this is true if the policy remains in bounded region and the reward is continuous in state. The key step in the proof to analyze the role of clipping the dual variables X, which stabilizes the algorithm without hurting the optimality condition.
5.2 REALIZATION OF THE WTATE-BASHD MEASURE
Instead of directly defining Ds. we define intrinsic rewards as illustrated in Sec. 5.1 such that (T)m lowing two types of diversity measures.
Ds( vz) Es,,- ~Mi Σ (ine(Nn; Tú, mj)]. With this formulation, we can implement the fol-
RBF Kernel: The most popular realization of Eq. in machine learning is kernel functions. In this paper, we realize Eq. (5) as an RBF kernel on states. Formally, the intrinsic reward is defined by
88 812
RBF (Sn Tey mJ)) ini
H B By
exp
20²
where a is hyperparameter controlling the variance.
Wasserstein Distance: For stronger discrimination power, we realize Eq. (5) as L2 Sa-Wasserstein
distance. According to the dual form (Villani 2009), the intrinsic reward is defined by
WD T in
SNS Te, m3) = H sup f(sn) - E [f('']] lf
(8)
where f R is a I-Lipschitz function. Following Arjovsky et al. (017)), we implement f neural network and clip parameters to [-0.1 0.01] ensure the Lipschitz constraint. riWP utilizes a learnable scoring function f and is more flexible in practice.
We name SIPO with RBF and WD SIPO-RBF and SIPO-WD respectively.
Implementation In the i-th iteration (1 < & MM, we learn an actor and a critic with separate value heads to accurately predict different return terms, including i - intrinsic returns for the diversity constraints and the environment reward. The input of Pim is the global state, which contains the state information of all the agents. To incorporate temporal information, global states to compute intrinsic rewards and normalize the intrinsic rewards to stabilize training. In multi-agent environments, we learn agent-ID-conditione policy (Fu et al. (022)) and share the
stack the recent
parameter across all agents. Our implementation is based on MAPPO (Yu et al. 2021) with more details in Appendix
EXPERIMENTS
We validate the effectiveness of SIPO two complex multi-agent games: StarCarft Multi Agent Challenge (SMAC) (Samvelyan et al. 2019) and Google Research Football (GRF) (Kurach et al. 2020). First, we show that SIPO can efficienlly learn diverse strategies all scenarios and outper- form several baseline methods, including DIPG (Masood & Doshi- Velez 2019), SMERL (Kumar ct al. 2020), DvD (Parker-Holll et al. 2020b), and RSPO (Zhou et al., 2022). Then, we qualita- tively demonstrate the emergent behaviors learned by SIPO, which are both visually distinguishable

---

Under review as a conference paper at ICLR 2023
Table 4: Number of visually distinct strategies in GRF discovered by different methods. Popula- tion size M = 4 in all cases. Details of the evaluation protocol can be found in Appendix
ours
baselines
random
SIPO-RBF
SIPO-WD
DIPG
SMERL.
DvD
RSPO*
PG
3v/
3.00()
3.00(0.00)
2.67(0.47)
1.33(0.47)
3.00(..82)
2.33(0.47)
2.67(0.47)
CA
3.33()
3.00(0.82)
2.33(0.47)
0.75(0.43)
2.67(0.47)
1.67(0.47)
corner
2.33(0.47)
3.00(0.82)
2.33(0.47)
0.75(0.43)
2.33(0.47)
Training DvD in CA and corner requires >24GB GPU memory, which exceeds memory limit. Not converged in corner.
and human--nteene intrreiatterre.. Finally, we perform an ablation study over the building components of SIPO and show that both the diversity measure and GDA are critical to the performance.
All the algorithms including ablation variants run for the same number of environment frames on desktop machine with a single NVIDIA RTX3090 GPU. All the quantitative results repeated over 3 random seeds with standard deviation shown in brackets. Additional results in continuous control can be found in Appendix B
6.1 COMPARISON WITH BASELINE METHODS
In SMAC, we only compare SIPO and RSPO, since RSPO outperforms other baselines (Zhou et al, 2022). We run both algorithms on an easy map. 2m $m_vs____ Iz, and a hard map, 2c vs 10____66666 2__644g, across 4 iterations. Both algorithms can discover 4 distinct winning strategies. To perform further com- parison, we compute the population diversity score based on RBF (see definition Appendix The results in Table 3 show that SIPO can discover an even more diverse population than RSPO, even
Table 3: Population diversity in SMAC.
though RSPO explicitly forces all policies to output different actions. In GRF, we run all algorithms and train population of in three academy narios, specifically (3v/), "academy_counterr""
map
RSPO
SIPO
2m/z
0.035 (0.011)
0,047(0.011)
2c642g
0.292 (0.023) 0.368(0.013)
"eas"" (CA), and "academy_ soory___orerrreo (corner). The GRF environment is more challenging than SMAC due to the large action space and the existence of duplicate actions. Table 4 compares the number of visually distinct policies discovered in the population. We present the population diversity scores in Appendix Our algorithm is the most efficient and robust - even in the challenging 11-vs-11 corner and CA scenario, SIPO can effectively discover different winning strategies in just few iterations across different seeds. By contrast, baselines adopting action-based measures, e.g. DvD and RSPO, suffer from the issue of duplicate actions and tend to discover policies with slight distinctions. In addition, the mutual information objective SMERL is sub-optimal (Eysenbach) et al. (2022) and the MMD- based measure of DIPG may not impose strong adversarial power policies.
6.2 QUALITATIVE ANALYSIS
For SMAC, we present heatmaps of agent positions in Fig. The heatmaps clearly show that SIPO can consistently learn novel winning strategies to conquer the enemy. Fig. 6 presents the learned behavior by SIPO in the GRF 3v/ scenario, where 3 attackers should collaborate shoot under the defense of an opponent player and goalkeeper. We can observe that agents have learned wide spectrum of collaboration strategies across merely iterations. Visualization results in CA and corner scenarios can be found in Appendix [
Surprisingly, the strategies discovered by SIPO are both diverse and human-interprettable We take the 3v/ scenario as an example. In the first iteration, all agents are involved in the attack such that they can distract the defender and obtain a high win rate. Similar strategies are discovered in the 4th and 5th iterations. The 2nd and the 6th iteration demonstrate strategy, where agents quickly elude the defender and score a goal. In the 3rd and the 7th iterations, agents learn smart "one-two" strategies bypass the defender, which is common tactic adopted by
efficient pass-and-shoot
8

---

Under review as a conference paper at ICLR 2023
policy
policy
policy 3
policy
23
position
2m_ unnys__ _s_1s_1
position policy
policy
policy
policy
20
2c_vs_ 23_g
X position
Figure 5: Heatmaps of agent positions in SMAC across 4 iterations with SIPO-RBE
Allacker
Defender
Direction
Player Direction
Win Rate
Reration
Reration
feration
Ieration
iteration
teration 6
eration 7
0.0
0.2
6..4
0.8 Environment Frames (1.0e8)
1.01
1.2
1.4
Figure 6: Evaluation winning rate and discovered strategies by SIPO-WD the 3v/ scenario 7 iterations. Each iteration runs for 20 million environment frames. The learning curve is averaged over random seeds with standard deviation shaded. Strategies of seed are shown.
professional human football players. To the best of our knowledge, SIPO may be the first algorithm that can discover such diverse human like tactics in complex multi-agent RL environments.
6.3 ABLATION STUDY
We perform ablation studies by
Table 5: Number visually distinct strategics GRF discovered by ablations.
fixing the Lagrange multiplier (fix-
L);
fix-I.
CF
filter
PRT
replacing our proposed diversity measure with cross-entropy (CE);
3vl
3.00/0.00)
1.000.000
3.00(0.82)
1.33(0.47)
2.67(0.47)
CA
3.00(0.82)
2.33(0.94)
1.000.000)
replacing GDA with the filtering- based method (filter);
corner
3,00(0.82)
1.67(0.47)
1.0000.00)
Not converged.
Training requires > 24GB memory and exceeds our memory limit.
replacing I. with PBT (PBT).
We apply these changes to SIPO-WD and report the number of visually distinct policies discovered by these methods in Table 5 Comparison between SIPO and CE demonstrates that the action- based cross-entropy measure may suffer from duplicate actions in GRF and produce nearly identical behavior by overly exploiting duplicate actions, especially in the CA and corner scenarios with 11 agents. Besides, the fixed Lagrange coefficient, the sieeing-bbsed method, and PBT are all detrimental to our algorithm. These methods also suffer from significant training instability. Overall, both the pate-distance-based diversity measure and GDA critical to the performance of SIPO.

---

Under review as a conference paper at ICLR 2023
7 CONCLUSION
In this paper, we tackle the problem of discovering diverse high-reward policy in complex RL sce- narios. We present a thorough comparison between two popular computation frameworks for this problem, i.e., population-base PBT, IL is much easy to optimize and can derive solutions with comparable quality to PBT. More- over, we also demonstrate concrete failure cases for popular ration-based diversity measure. Moti- vated by these insights, we combine II. with a diversity measure defined on state distance to develop State-bused Intrinsic-reward Policy Optimization (SIPO), which has provable convergence and can efficiently discover a wide spectrum of interpreatce strategies in challenging multi-agent environments. We emphasize that the contribution of our work is much beyond the final algorithm SIPO. We believe our analysis on frameworks and diversity measure with concrete examples and theoretical justifications can bring useful insights to benefit the community for developing more powerful aiversity-driven RL algorithms.
training (PBT) and iterative learning, and show that, comparing with
REFERENCES
Martin Arjovsky, Soumith Chintala, and Léon Bottou. Wasserstein generative adversarial net- works. In Doina Precup and Yee Whye Teh (eds.), Proceedings of the 34th International Con- ference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pp. 223. PMLR, 06-11 Aug 2017. URL https: https::/ http::s:/pprceediigge ml prrss///ss
ar jovsvyy 7a. html
Monica Babes, Enrique Munoz de Cote, and Michael L. Littman. Social reward shaping in the prisoner's dilemma. In Lin Padgham, David C. Parkes, Jörg P. Müller, and Simon Parsons (eds.). 7th International Joint Conference on Autonomous Agents and Multiagent Systems (AA- MAS 2008), Estoril, Portugal. May 12-16, 2008, Volume 3, pp. 1389-1392. IFAAMAS, 2008. URL https: acm. org/ wttgg/itteeeeee.eeeeee witatiiiiinnn cfm? 1
Bowen Baker, Ingmar Kanitscheider, Todor M. Markov, Yi Wu, Glenn Powell, Bob McGrew, and Igor Mordatch. Emergent tool use from multi-agent autocurricula. In 8th International Con- ference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020. URL htthh::tt////mettt /pw.reviee./ee.eeeeeoeoe.e wwt. htte///oommmmdssxpppeee
Dimitris Bertsimas and John N Tsitsiklis. Introduction to linear optimization, volume 6. Athena Scientific Belmont, MA, 1997.
Yura Burda and Harri Edwards, Oct 2018. URL /ttt::::///penaa.ccom//////// rriinforcement www-ellarnnngigee
predi ct ion bwwsdd-rwwwreeee
Andres Campero, Roberta Raileanu, Heinrich Küttler, Joshua B. Tenenbaum, Tim Rocktäschel, and Edward Grefenstette. Learning with amigo: Adversarially motivated intrinsic goals. In 9th International Conference on Learning Representations, ICLR 2021, Viriual Event, Austria, May 3-7, 2021. OpenReview.net, 2021. Utt.htttsss///opeerree
www.teeooourmmme id
MIMgoX
Victor Campos, Alexander Trott, Caiming Xiong, Richard Socher, Xavier Giró-i-Nieto, and Jordi Torres. Explore. discover and learn: Unsupervised discovery of state-covering skills. In Pro- ceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pp. 1317-1327. PMLR, 2020. URL/http://prrccedl cgoooeeeedini.........c. mlr. press/vvi99 httpa////w11///cmm2oaaaaaaa
Jack Clark and Dario Amodei, Dec 2016.
URL https: pettenai.com/boogg
rolllyy-rewarr-funccec
Antoine Cully, Jeff Clune. Danesh Tarapore, and Jean -an--Batttteeee Mouret. Robots that can adapt like animals. Nature, 521(7553) May 2015. ISSN 0028-0836, 1476-4687. doi: 10. 1038/ 144u. URL htRlhttp:/ / nwwure.........mmmmm......
Kalyanmoy Deb and Amit Saha. Finding multiple solutions for multimodal optimization prob- lems using multi-objective evolutionary approach. In Martin Pelikan and Jürgen Branke (eds.),
10

---

Under review as a conference paper at ICLR 2023
Genetic and Evolutionary Computation Conference, GECCO 2010, Proceedings, Portland, Ore- gon, USA, July 7-11, 2010. pp. 447 454, ACM, 2010. doi: 10.1145/1830488.1886666 URL sttps:///oil wtt.://........1111111.3........
Sam Devlin and Daniel Kudenko. Theoretical considerations potential- based reward shaping for multi-agent systems. In Liz Sonenberg, Peter Stone, Kagan Tumer, and Pinar Yolum (eds.), 10th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 201 1), Taipei, Taiwan, May 2-6, 2011, Volume 1-3. pp. 225-232. IFAAMAS, 2011. URL wttp:ttp://// / acm. org/ www.aiiiiiooo ion. cîm ?id 20 3805900030-
Joydeep Dutta, Kalyanmoy Deb, Rupesh Tulshyan, and Ramnik Arora. Approximate kkt points and proximity measure for termination. Journal of Global Optimization, 56(4): 1461-1664444100 1499, 2013.
Benjamin Eysenbach, Abhishek Gupta, Julian Ibarz, and Sergey Levine. Diversity all you need: Learning skills without reward function. In 7th International Conference on Learning Repre- sentations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019. URL
3 wet.eeewweeeeeeeeeeeeeeeeeeeeeee worum iesorummid--Sae S3x66 JR(Fm
Benjamin Eysenbach, Ruslan Salakhutdinov, and Sergey Levine. The information geometry of unsupervised reinforcement learning. In The Tenth International Conference on Learning Rep- resentations, ICLR 2022, Virtual Event, April 25-29, 2022. OpenReview.net, 2022. URL
https://epenreviee net/ forum iididddwwst 3w020000V
Wei Fu, Chao Yu, Zelai Xu, Jiaqi Yang. and Yi Wu. Revisiting some common practices in coop- erative multi-agent reinforcement learning. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song. Csaba Szepesvari, Gang Niu, and Sivan Sabato (eds.), Proceedings of the 39th International Con- ference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pp- 1863-6877, PMLR, 17-23 Jul 2022. URL https: httpss:/prcceediigg. mlr www....ees//vl..... Fu22d.
Dibya Ghosh, Abhishek Gupta, and Sergey Levine. Learning actionable representations with goal conditioned policies. 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019. URL https:/7
Agrim Gupta, Silvio Savarese, Surya Ganguli, and Li Fei-Fei. Embodied intelligence via learning and evolution. Nature communications, 12(1):1-12, 2021.
Max Jaderberg, Wojciech M. Czarnecki, lain Dunning, Luke Marris, Guy Lever, Antonio Garcia Castañeda, Charles Beattie, Neil C. Rabinowitz, Ari S. Morcos, Avraham Ruderman, Nico- las Sonnerat, Tim Green, Louise Deason, Joel Z. Leibo, David Silver, Demis Hassabis, Koray Kavukcuoglu, and Thore Graepel. Human-level performance in 3D multiplayer games with population-based reinforcement learning. Science, 364(6443):859-8666 May 2019. ISSN 0036- 8075, 1095-9203. doi: (0.1126/science.aal aau6249. URL (tR.httss:// http:/::/wwwwwwwcee.cce..c.. www.e http:///////..cccceeee..oo////// 10.1126/ 10.1125/science. http//cieccc..c aau6249
Saurabh Kumar, Aviral Kumar, Sergey Levine, and Chelsea Finn. One solution is not all you need: Few-shot extrapolation via structured maxent RL. In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin (eds.), Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, December 6-12, 2020, virtual, 2020. URL 0i111diin 2ed.1111119322213333333333 55531000022333333333222222222223
cc/paper/202//hast
Abs html
Karol Kurach, Anton Raichuk, Piotr Stańczyk, Michal Zajac, Olivier Bachem, Lasse Espeholt, Car- los Riquelme, Damien Vincent, Marcin Michalski, Olivier Bousquet, et al. Google research football: A novel reinforcement learning environment. In Proceedings of the AAAI Conference Artificial Intelligence, volume 34, pp. 4501-4510, 2020.
Yoonho Lee, Huaxiu Yao, and Chelsea Finn. Diversify and disambiguate: Learning from underspec- ified data. CoRR, abs/2202.03418. 2022.
03418

---

Under review as a conference paper at ICLR 2023
Chenghao Li, Tonghan Wang, Chengjie Wu, Qianchuan Zhao, Jun Yang, and Chongjie Zhang- Celebrating diversity in shared multi-agent reinforcement learning. In Mare' Aurelio Ran- zato, Alina Beygelzimer. Yann N. Dauphin, Pency Liang, and Jennifer Wortman Vaughan (eds.), Advances in Neural Information Processing Systems 34: Annual Conference on Neu- ral Information Processing Systems 2021, NeurlPS 2021, December 6-14, 2021, virtual, pp- 3991 2021. URL httpp::/pprccceingg..o. http://cciaa....i..ssoo..ee////a (0aaeea5f4465
wwtppppppwww./////ccccc h 9ee (ot.e6a773000a0 Abstraatttttaattttttttt. Abstract.html
Jiwei Li, Will Monroe, Alan Ritter, Dan Jurafsky, Michel Galley, and Jianfeng Gao. Deep re- inforcement learning for dialogue generation. In Jian Su, Xavier Carreras, and Kevin Duh (eds.), Proceedings of the 2016 Conference on Empirical Methods in Natural Language Pro- cessing, EMNLP 2016, Austin, Texas, USA, November 1-4, 2016, pp. 1192-1202. The As- sociation for Computational Linguistics, 2016. doi: 10.18653/v1/d1-- 1127. URL https:
1127
Tianyi Lin, Chi Jin, and Michael I. Jordan. On gradient descent ascent for nonconvex-concave minimax problems. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning PMLR, 2020. URLhttp: hlle:://proceedlnge mlr. wttp:///s.......ee///////.. press/v199/
Research, pp. 1in20a.htm h
Tou-Jen Liu, Unnat Jain, Raymond A. Yeh, and Alexander G. Schwing. Cooperative exploration for multi-agent deep reinforcement learning. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learming Research, pp. 6836. PMLR, 2021a. URL http:::/pproceeeingggs mi wtt..ppreee///ee//ee..
Siqi Liu, Guy Lever, Josh Merel, Saran Tunyasuvunakool, Nicolas Heess, and Thore Graepel. Emer- gent coordination through competition. In 7th International Conference on Learning Repre- sentations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019. URL lhttps://openrett
net forum dd 1355km
Siqi Liu, Guy Lever, Zhe Wang, Josh Merel, S. M. Ali Eslami, Daniel Hennes, Wojciech M. Czar- necki, Yuval Tassa, Shayegan Omidshafiei, Abbas Abdolmaleki, Noah Y. Siegel, Leonard Hasen- clever, Luke Marris, Saran Tunyasuvunakool, H. Francis Song, Markus Wulfmeier, Paul Muller, Tuomas Haarnoja, Brendan D. Tracey, Karl Tuyls, Thore Graepel, and Nicolas Heess. From mo- tor control to team play in simulated humanoid football. Sci. Robotics, 7(69), 2022. doi: 1266 abo0235
doi. . org/ 10. 1126.1116./1 http:/scrooooiiccccc ott.o/////....1////oootttttoo... scirobotics.abo0233. URL https: //doi.
Xiangyu Liu, Hangtian Jia, Ying Wen, Yujing Hu, Yingfeng Chen, Changjie Fan, Zhipeng Hu, and Yaodong Yang. Towards unifying behavioral and response diversity for open-ended learning in zero-sum games. In Marc' Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan (eds.), Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual, pp. 941-952 2021b. URL https: htttt:::s//prcceediggg.ooo wtwp:/eddddiinsn..nuueeeeeeeeeee www.ips..pp... cc/ paper/202 /0tp//22//// httphaaahhhha/ hwtsshh77bba555
-Abtt html
Qian Long, Zihan Zhou, Abhinav Gupta, Fei Fang, Yi Wu, and Xiaolong Wang. Evolutionary popu- lation curriculum for scaling multi-agent reinforcement learning. In International Conference on Learning Representations, 2020.
Andrei Lupu, Hengyuan Hu, and Jakob N. Foerster. Trajectory diversity for zero-shot coordination. In Frank Dignum, Alessio Lomuscio, Ulle Endriss, and Ann Nowé (eds.). AAMAS '21: 20th International Conference Autonomous Agents and Multiagent Systems, Virtual Event, United Kingdom, May 3-7, 2021, pp. 1593-1595. ACM, 2021. doi: 10.5555/3463952.444411 URL https: www 1 aamaa htt.a//ww......coooeeoe///aa/aaa
Pingchuan Ma, Tao Du, and Wojciech Matusik. Efficient continuous pareto exploration in multi- task learning. In Proceedings of the 37th International Conference on Machine Learning. ICML 2020, 13-18 July 2020, Virtual Event. volume 119 of Proceedings Machine Learning Research, pp. 6522-6532 PMLR, 2020. URL http: http:::/ppocceeddneeoo mlr. prwpsreesvveee aaress/v19//ma2a.. html
12

---

Under review as a conference paper at ICLR 2023
Tengyu Ma. Why Do Local Methods Solve Nonconvex Problems?, March 2021. URL http: axxiv.crg/aas//11...3
arXiv:2103.13662 [cs, math, stat].
Marlos C. Machado, Mare G. Bellemare, and Michael Bowling. Count- exploration with the successor representation. In The Thirty-Fourty AAAI Conference on Artificial Intelligence, AAAI 2020, The Thirty-Second Innovative Applications of Artificial Intelligence Conference, IAAI 2020, The Tenth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2020,
New York, NY, USA, February 7-12, 2020, pp. 5125-5133, AAAI Press, 2020. URL https:
77ojs aaal. wtwpg/in//........ee php/ AAAI httpp//AAA/arrieeeeeeee/////////
Muhammad Masood and Finale Doshi-Velez. Diversity-inducing policy gradient: Using max- imum mean discrepancy to find set of diverse policies. In Sarit Kraus (ed.), Proceedings of the Twenty-Fighth International Joint Conference on Artificial Intelligence, IJCAI 2019, Macao, China, August 10-16, 2019, pp. 5923-5929, orcai.org, 2019. doi: 20024963/jccai22218/8822 URL attps://ddt org/ fcwi..96//.a......... 2019/821
B.L. Miller and M.J. Shaw. Genetic algorithms with dynamic niche sharing for multimodal function optimization. In Proceedings of IEEE International Conference on Evolutionary Computation, pp. 786-791, Nagoya, Japan, 1996. IEEE. ISBN 978-0-7803-2902-1 doi: 10.1 10.1109/CCE..199 542701. URL http:: http:/eeeeeepore.e U wew.e..iee.... htt.eee.or//ccomee///5555
Jean- dean-Baptiste Mouret and Jeff Clune. Illuminating search spaces by mapping elites. CoRR, pap
abs/1504.04909, 2015. URL
Andrew Y Ng, Daishi Harada, and Stuart Russell. Policy invariance under reward transformations:
Theory and application to reward shaping. In Ieml, volume 99, pp. 278-287, 1999.
Olle Nilsson and Antoine Cully. Policy gradient assisted MAP-Elites. In Proceedings of the Genetic and Evolutionary Computation Conference, pp. 866-875, Lille France, June 2021. ACM. ISBN 978-1-4503-8350-9, doi: 00.144573449699334593444 10.1145/34496333 3459304
URL https: acm. org/doi/
Shayegan Omidshafici, Karl Tuyls. Wojeiech M Czarnecki, Francisco C Santos, Mark Rowland, Jerome Connor, Daniel Hennes, Paul Muller, Julien Pérolat, Bart De Vylder, et al. Navigating the landscape of multiplayer games. Nature communications, 11(1):1-17, 2020.
Takayuki Osa, Voot Tangkaratt, and Masashi Sugiyama. Discovering diverse solutions in deep reinforcement learning by maximizing state-action-based mutual information. Neural Networks, 152:90-104, 2022. doi: 10.. n00f//..eunet.2222.00o j.reunet 2022. 009
htllhttss///ci.orr
Aldo Pacchiano, Jack Parker-Holder, Yunhao Tang, Krzysztof Choromanski, Anna Choromanska, and Michael Jordan. Learning to score behaviors for guided policy optimization. In International Conference Machine Learning, pp. 7445-7454. PMLR, 2020.
Jack Parker- Holder, Luke Metz, Cinjon Resnick, Hengyuan Hu, Adam Lerer, Alistair
Letcher, Alexander Peysakhovich, Aldo Pacchiano, and Jakob N. Foerster. Ridge
rider: Finding diverse solutions by following eigenvectors of the hessian. In Hugo Larochelle. Mare' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and
Lin (eds.), Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020a. URL httt:pss//proceedingg..oo
occ/paper/202//hast
Jack Parker-Holder, Aldo Pacchiano, Krzysztof Marcin Choromanski, and Stephen J. Roberts. Effective diversity in population based reinforcement learning. Larochelle, Marc' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin (eds.), Advances in Neural Information Processing Systems 33: Annual Conference Neural Information Processing Systems 2020, NeurlPS 2020, December 6-12, 2020, http:/pssccpppppe/2////eaa/ virtual, URL abst:0000t00ttttatttttttththh ort.aa33SS.BBaa10000000oooaoaaor
Hugo
13

---

Under review as a conference paper at ICLR 2023
Alexander Peysakhovich and Adam Lerer. Consequentialist conditional cooperation in social dilem- mas with imperfect information. In 6th International Conference on Learning Representations, ICLR 2018. Vancouver, BC, Canada, April 30 May 3, 2018, Conference Track Proceedings. OpenReview.net, 2018. URL. https::///// http::://ppeeevveeeeee
d=RkabR Qpb
Thomas Pierrot, Valentin Macé, Félix Chalumeau, Arthur Flajolet, Geoffrey Cideron, Karim Be- guir, Antoine Cully, Olivier Sigaud, and Nicolas Perrin-Gilbert. Diversity Policy Gradient for Sample Efficient Quality-Diversityy Optimization. In Proceedings of the Genetic and Evolution- ary Computation Conference, pp. 1075-1083, July 2022. doi: 1445/3512229335288455 URL http:://axxii org/ abs / 2006 08505 arXiv:2006.0855 [cs].
Justin K. Pugh, Lisa B. Soros, and Kenneth O. Stanley. Quality Diversity: A New Frontier for Evolutionary Computation. Frontiers in Robotics and AI, 3, July 2016. ISSN 2296-9144. doi: 10. 1..3389ffrobt.2211.000444 URL 3389/frobt 2016.
front Froonieersiinn. htt.aaa.........aa..ooatcccaaaaa
Tim Roughgarden (ed.). Beyond the Worst-Case Analysis of Algorithms. Cambridge University Press, 2020. ISBN 9781 108633333
doi: 10.1017/978100837753. URL https://doi.
org/10.
Mikayel Samvelyan, Tabish Rashid, Christian Schröder de Witt, Gregory Farquhar, Nantas Nardelli, Tim G. J. Rudner, Chia-Man Hung. Philip H. S. Torr, Jakob N. Foerster, and Shimon White- son. The starcraft multi-agent challenge. In Edith Elkind, Manuela Veloso, Noa Agmon, and Matthew E. Taylor (eds.), Proceedings of the 18th International Conference Autonomous Agents and MultiAgent Systems, AAMAS '19, Montreal, QC, Canada, May 13-17, 2019, pp- 2186-2188, International Foundation for Autonomous Agents and Multiagent Systems, 2019. URL http: acm. org/ citatitiiioo ion. cfmp:m.mmmmmmmmmmmm 3332052
Archit Sharma, Shixiang Gu, Sergey Levine, Vikash Kumar, and Karol Hausman. Dynamics-aware unsupervised discovery of skills. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020. URL https:
7/ //openevview www. westt/ooormm.dd-uugiiiaa....
Matthijs TJ Spaan. Partially observable markov decision processes. Reinforcement Learning, pp. 387-414. Springer, 2012.
Hao Sun, Zhenghao Peng, Bo Dai, Jian Guo, Dahua Lin, and Bolei Zhou. Novel policy seeking with constrained optimization. arXiv preprint arXiv:2005.1066 2020.
Zhenggang Tang, Chao Yu, Boyuan Chen, Huazhe Xu, Xiaolong Wang, Fei Fang, Simon Shaolei Du, Yu Wang, and Yi Wu. Discovering diverse multi-agent strategic behavior via reward ran- domization. In 9th International Conference on Learning Representatiinss ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OpenReview.net, 2021. URL httphhtttt//eeeeeeeeeeee Forum? w
net//
Luca Venturi, Afonso S. Bandeira, and Joan Bruna. Neural networks with finite intrinsic dimension have no spurious valleys. CoRR, abs/1802.06384. 2018. URL
18C2. 06384
Cédric Villani. Optimal transport: old and new, volume 338. Springer, 2009.
Oriol Vinyals, Igor Babuschkin, Wojeiech M. Czarnecki, Michaël Mathieu, Andrew Dudzik, Juny- oung Chung, David H. Choi, Richard Powell, Timo Ewalds, Petko Georgiev. Junhyuk Oh, Dan Horgan, Manuel Kroiss, Ivo Danihelka, Aja Huang, Laurent Sifrre, Trevor Cai, John Agapiou, Max Jaderberg, Alexander S. Vezhnevets, Rémi Leblond, Tobias Pohlen, Valentin Dalibard, David Budden, Yury Sulsky, James Molloy, Tom L. Paine, Caglar Gulcehre, Ziyu Wang. Tobias Pfaff, Yuhuai Wu, Roman Ring, Dani Yogatama, Dario Wünsch, Katrina McKinney, Oliver Smith, Tom Schaul, Timothy Lillicrap, Koray Kavukcuoglu, Demis Hassabis, Chris Apps, and David Silver. Grandmaster level in StarCraft II using multi-agent reinforcement learning. Nature, 575(7782): 350-354, November 2019. ISSN 0028-0836 0836. 1476-4687, doi: 10. 10w.10///41186-01111 019-----99--2-----2 URL
http: www. na wat.eu...... cww a rt es 4 150
14

---

Under review as a conference paper at ICLR 2023
Rui Wang, Joel Lehman, Jeff Clune, and Kenneth O Stanley. Poet: open-ended coevolution of environments and their optimized solutions. In Proceedings of the Genetic and Evolutionary Computation Conference, pp. 142-151, 2019.
Tonghan Wang, Tarun Gupta, Anuj Mahajan, Bei Peng, Shimon Whiteson, and Chongjie Zhang. RODE: learning roles to decompose multi-agent tasks. In 9th International Conference on Learn- ing Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OpenReview.net, 2021.
URL httphtttp////peeeeeiee. net wttp://wwwee///uumeeeeeee iinrrummid-Tinee TdVTTVVV6VKT
Yifan Wu, George Tucker, and Ofir Nachum. The laplacian in RL: learning representations with efficient approximations. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019. URL https:
opoenzeview. wwt um..ommmmmmmm..mmmmmmmmmmm.mmmm. Honddd-HHNNoASS
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.01955, 2021.
Tom Zahavy, Brendan O' D'Donog Andre Barreto, Volodymyr Mnih, Sebastian Flennerhag, and Satinder Singh. Discovering diverse nearly optimal policies with successor features. arXiv preprint 1..::2006.000000 2021.
Yunbo Zhang, Wenhao Yu, and Greg Turk. Learning novel policies for tasks. In International Conference Machine Learning, pp. 7483-7492. PMLR, 2019.
Rui Zhao, Jinming Song, Hu Haifeng, Yang Gao, Yi Wu, Zhongqian Sun, and Yang Wei. Max- imum entropy population based training for zero-shot human-ai coordination. arXiv preprint arXiv:2112.11701, 2021.
Zihan Zhou, Wei Fu, Bingliang Zhang, and Yi Wu. Continuously discovering novel strategies via reward-switching policy optimization. In The Tenth International Conference on Learning Representations, ICLR 2022, Virtual Event, April 25-29, 2022. OpenReview.net, 2022. URL https://openrewe net/ www.oomiddochHRRRE....
15

---

Under review as a conference paper at ICLR 2023
A
PROJECT WEBSITE
Check http://as....ooooo...//////////r for GIF demonstrations.
B
ADDITIONAL RESULTS
B.1 MORE QUALITATIVE RESULTS
Allacker
Delender
Ball Direction
Player Direction
Figure 7: Visualization of learned behaviors in GRF CA across a single training trial.
Walking
1.0
Iteration 1
ileration 2
ittration
iteration
Win Rate
MwW
0.5
Awmm
0.0
Environment framés (1.0c10)
Mincing
Attacker
Datender
Walting
Ball Direction
Direction
Gl. hand balancing walking
Figure 8: Visualization of learned behaviors in GRF corner (left) and MuloCo Humanoid-vž (right)
across a single training trial.
show visualization results in GRF CA and corner Fig. 7 (left) and Fig. (left). We also
evaluate SIPO-WD in the most challenging continuous control environment, Humanoid-v3, across 3 iterations and visualize the learned behavior in Fig. (right). SIPO- WD is able to produce diverse behaviors with different gaits. We additionally remark that the population diversity score is very close to 1 (such as 0.999) even when we repeatedly run PPO (Zhou et al. 2022). Hence, we do not report the population diversity score here.
B.2 STATE-BASED BASED POPULATION DIVERSITY
We define the pairwise difference between policies as
||s]]
Kg = K(TT, RTy) |F (P
exp
(9)
28
16

---

Under review as a conference paper at ICLR 2023
Table 6: Population diversity in GRF. Mean values averaged over random seeds are shown with standard deviation in the brackets. Population size M = 4.
ours
baselines
SIPO-RBF
SIPO-WE WD
DIPG
SMERL'
DvD²
RSPO*
3v/
0.023(0.002)
0.025(0.004) 0.027(0.002)
0.014(0.002)
0.024(0.008)
0.019(0.002) 0.899(0.058)
CA
0.972(0.022)
0.945(0.050)
0.919(0.004)
Corner
0.213(0.088)
0.278(0.086)
0.154(0.021)
When conditioned on some specific latent variable, SMERL policy cannot even collect single winning trajectory in CA and Corner. Therefore, we omit the result here.
Training DvD in CA and corner requires >24GB GPU memory, which exceeds our memory limit. Not converged in corner.
Table 7: Population diversity and the number of distinct strategies in GRF 3v/
scenario with population size M 10. Mean values averaged over 3 random seeds are shown with standard deviation in the brackets.
ours
baselines
SIPO-RBF
SIPO-WD
DIPG
RSPO
population diversity
0.291(0.053)
0.399(0.040)
0.251(0.018)
0.272(0.036)
# strategics
4.33(0.47)
5.67(0.47)
3.67(0.47)
2.33(0.47)
where scaling factor. Then, similar to Parker-Holder al. (202bb), we compute the deter-
minant of the matrix K as the population diversity. ā = 1 for Table 0.4 for Table 6 and
0.15 for Table
Similar to Table 3 present the state-based population diversity score of GRF scenarios in Table GRF scenarios are more challenging than SMAC and the trained policies may not always score goal in each episode. (See evaluation winning rates in Table [ To reduce the variance, we collect 32 winning trajectories and compute population diversity scores on them.
B.3 RESULTS WITH A LARGER POPULATION SIZE
To demonstrate the effectiveness of SIPO, we additionally conduct an experiment in the GRF 3v/ scenario with population size M 10. Baselines include DIPG and RSPO. We present the results Table Results show that SIPO clearly outperforms these baselines by consistently discovering one more additional strategies.
Empirically, we find that there are 4 "primitive" strategies the 3v1 scenario, which are pass-and- shoot (iteration 2 in Fig. (). houble-puss-and--hhe mirror strategies. Across 10 iterations, baseline methods do not discover any strategies beyond these primitives, while SIPO is able learn addition smart behaviors like "one-two" strategies (iteration
(iteration 1 in Fig. ( and the corresponding
7 in Fig.
B.4 EVALUATION WIN RATE
The evaluation win rates the demonstrated visualization results (Fig. shown in Table
Fig.
Fig. and Fig.
B.5 COMPUTATION OF ACTION-BASED MEASURES IN THE WRID-WORLD EXAMPLE
We consider the policies illustrated in Fig. These policies all optimal since these actions only include "right" and "down" and actions on non non-visited states can be arbitrary. We only mark actions states visited by any of these 3 policies and actions other states be considered the same.
17

---

Under review as a conference paper at ICLR 2023
Table Evaluation win rate (%) of the demonstrated visualization results. Averaged across 3 seeds with standard deviation shown in brackets.
SMAC
GRF
2m/z
2c642g
3v/
CA
corner
711
100.0(0.0)
98.1(2.1)
92.3(6.2)
48.2(10.4)
78.2(16.2)
99.6(0.9)
100.0(0.0)
82.1(8.4)
43.8(42.2)
57.0(3.77
73
100.0(0.0)
96.9(3.3)
90.7(1.1)
54.7(30.6)
55.7(20.8)
99.6(0.6)
98.6(2.4)
63.6(45.0)
17.2(30.0)
30.7(29.0)
755
85.4(9.1)
93.2(1.9)
77
64.6(32.5)
B.5.1 ACTION-DISTRIUUTION-.. BASED MEASURES
Action-distributionnbee diversity measures can be defined
DA(T., = Esn((s) [ s)] s))
(10)
R is a measure over action distributions and (SS) is a state proposal distribution. Here, we consider q to be the joint state distribution visited by nN and πT
where D(,,-)
x
KL Divergence
KL divergence is defined by
S{ (i log Ti(a| 8) Ty(a s)
DEL (m(( 8), x- s))
da.
When (a 8) = 0 at any state 8, KL divergence is +00. Since the trajectories of these policies have disjoint states, DK (T1, T2) = DKL (51, TT) = +00. Similar results can be obtained for cross- entropy.
JSD JSD,, was defined in Lupu et al. (022)) and we consider two special cases when 7 = 0 and
As illustrated by Lupu al. (2021), JSD, measures the expected number of times two policies will "disagree" by selecting different actions. On trajectories induced by and π2, there are 4 + 4 states
that disagrees with (TI and are symmetric) and D (TI, T2) 8/16 1/2. Similarly, m and Rh only disagree the initial state, therefore have DOSDo (II, T3) 2/16 1/8.
4
T
T2
T3
Figure 9: Policies in the grid-world example when No 5.
18

---

Under review as a conference paper at ICLR 2023
Average Intrinic Beward
Sigea 2012
supeo
sigeo and sign 2erd
Table 9: The values of and in different environments.
8.23
0538
football
3v1
corner
CA
2m vs lz
2c vs 64zg
0434
5WD WD
0.004
0.01
0.012
0.02
0.2
0.5
0.5
0.05
jRBF
0.03
0.01
0.015
0.002
0.001
Q
RBF
0.001
0.001
0.001
0.001
0,001
Figure 10: Average intrinsic re-
0.02
0.02
0.02
0.02
0.02
ward during training #1-
JSD, is defined by
JSD (T,
Σ
P(T. m
Σ
T
1
log
T((Ti) TT(TT)
T
2T.(TT)
T
(T(T;) + xy TT(
2
P(T P(T
log
2T,(
Since each of the policies considered only induces a single trajectory and TT(Ty) 0 * j), we can easily compute
D' (TI, T2) = D (TI, T3) = log
Wasserstein distance or Earth Moving Distance (EMD) if two policies disagree on a state and 0 otherwise. Therefore, it equals to 1
Wasserstein Distance
B.5.2 ACTION NORM
We embed the action "right" as vector [1, 0] since it increases the x-coordinate by and the action "down" vector [0, -1] since it decreases the y-coordinate by 1. This embedding can be naturally extended to continuous action space with velocity action. Following [aaker- Holder al. (020b), states. We can see that there are states where иi and #2 perform differently and state (the initial state) where mi and कh perform differently. Therefore, we can get (TT,, T2) /7 and D(T1, Tz) 1.
we compute the action norm over uniform distribution
B.5.3
BBSSED MEASURES
State Le Norm Similar to action L2 norm, we concatenate the coordinates instead of actions as the embedding and compute the L2 norm between embedding.
Wasserstein Distance Wasserstein distance is tractable in the grid-world example. We consider 7 states (except the initial and final states) in each trajectory and compute the pair-wise distance as matrix C14- Then solve the following linear programming
min Σ10c 1
7 a, 7" T 114
The > 0, 1 i,j < 14
where means element-wise multiplication, 1 is d-dim all-one vector, 014x1 [1] oT and 10 1T is the marginal state distribution of each policy.
614X1
B.6 How TO ADJUST CONSTRAINT-RELANE HYPERPARAMETER
Three hyperparameters are essential in the implementation of the intrinsic reward Pin: the threshold the intrinsic reward scale factor a, and the variance factor in RBF
int These parameters differ
19

---

Under review as a conference paper at ICLR 2023
under different domains and must be adjusted individually. We find proper parameters by running two iterations without constraints and get two similar policies To and T1. We record Tint during training Ti and the trend is shown in Fig. T0. Not surprisingly, Tim gradually decreases as training proceeds.
Threshold We set á c1 ( 1T). We try several different a find that C₁ = 1.2 or 1.4 are universal proper solutions for all the experimental environments.
and
Intrinsic Scale Factor We need to balance the intrinsic reward Tint and the original reward J so that neither of the two rewards can dominate the training process. Empirically, the maximums of the rewards should be in the same order of magnitude. i.e., max, (
027mazo, where 02 = Q(1. When C2 is too large, the new-trained policy тÿ will oscillate near the boundary of (T) for some pre-trained policy p.. Conversely, when C2 is too small, the intrinsic reward Pint cannot yield diverse strategies. In experiments, we set C2 0.8 ~ 1.0.
Variance Factor We sweep the variance factor across {le 3, 5e 3, lc 2. 2, le 3) by training T1 and observe the trend of intrinsic rewards. We find the steepest trend and select the corresponding a. Empirically, we find that our algorithm performs robustly well when o² 0.02.
The 5 and a of GRF and SMAC are listed in Table 9
B.7 EVALUATION PROTOCOL OF TABLE AND TABLE 5
In 3v/ and CA, players perform passes and shoot in the front yard. We consider two strategies to be different if the resulting trajectories of ball movement are different, e.g. the ball is passed to different players or different players perform shoot. In Corner, besides ball movement, we further categorize pass-and-shoot strategies according to the position of shooting in the penalty box (e.g.. lower/middle/upper spot). All the authors perform independent evaluation based on this criterion and strong agreements are achieved. Please check our project website for GIF demonstrations.
C ENVIRONMENT DETAILS
C.I DETAILS OF THE 2D NAVIGATION ENVIRONMENT
The navigation environment has an agent circle with size a and 4 landmark circles with size b. We pre-specify threshold and constrain that the distance of final states reaching different landmarks must be larger than c. Correspondingly, landmark circles are randomly initialized by constraining the pairwise distance between centers to be larger than threshold c+ c+2((++b) such that the final-state constraint is valid. An episode ends the agent touches any landmarks, i.e., the distance between the center of the agent and the center of the landmark d a 6, 1000 timesteps have elapsed. The observation space includes the positions of the agent and all landmarks, which is a 10-dimensional vector. The action space is 2-dimensional vector, which is the agent velocity. The time interval is set to be At = 0.1, i.e., the next position is computed by Fz+1 = It + At v. The reward 0 if the agent touches the landmark and 0 otherwise.
C.2 DETAILS OF SMAC, GRF, AND MuJoCo
SMAC We adopt the SMAc environment in the MAPPO codebase with the same configuration as Yu et al. (202T). The input of intrinsic rewards diversity measure is the state of all allies, including positions, health, etc.
GRF
We adopt the "simple 15v2" representation as observation with both "scoring" and "check- point" reward. The reward is shared across all agents. The input of intrinsic rewards or diversity measure is the position and velocity of all attackers and the ball.
MuJoCo
We use the Humanoid-v4 environment in OpenAl gym version 0.21.0 with the default configuration. To remove irrelevant or unchangeable features, we use the first 45-dimension of
20

---

Under review as a conference paper at ICLR 2023
Table 10: Hyperparameters in the 2D navigation environment.
discount
GAB
PPO epuchs
clip parameter
entrupy bonus
Anas
actir
critic Ir
Lagrange Ir
batch size
0.997
0,95
10
0.2
10
30-4
Io-3
0.5
4000
Table 11: Common hyperparameters for SIPO, baselines, and ablations.
discount
GAE A
actor
critic Ir
clip parameter
entropy homus
GRF hatch size
SMAC batch size
5e-4
1o-3
observation the input of intrinsic rewards and the semantic meaning be found in https://
D IMPLEMENTATION DETAILS
D.I 2D NAVIGATION
We apply PPO optimize the policy and hyperparameters summarized in Table I0 The applied algorithm is the same as SIPO (see Appendix G except that the intrinsic reward is only computed the last timestep.
D.2 SIPO
We include all practical tricks mentioned in Yu et al. (2021) because we find them all critical to algorithm performance. We use separate actor and critic networks, both with hidden size 64 and GRU layer with hidden size 64. The common hyperparameters for SIPO, baselines, and ablations are listed Table Other environment-speciffe parameters, such as PPO epochs and mini-batch size, are all the same as Yu et al. (2021). Besides, Table and Table 12 lists some extra hyperparameters for SIPO.
Specific hyperparameters for baselines can be found in Appendix D.3
D.3 BASELINES
We ce-implement baselines with PPO based on the MAPPO Yu et al. 2021 project. All algo- rithms run for the same number of environment frames.
SMERL We implement SMERL (Kumar et al. 2020) with PPO, where the actor and the critic take as the input the concatenation of observation and one-hot latent variable. The discriminator is 2-layer feed-forward network with 64 hidden units. The learning rate of the discriminator is the same as the learning rate of the critic network. The input of the discriminator is the same as the input we use for SIPO-WD. The critic has 2 value heads for an accurate estimation of intrinsic return. Since SMERL trains single latent-conditioned policy, we train SMERL for Mx more environment steps, such that total environment frames are the same. The scaling factor of intrinsic rewards is 0.1 and the threshold for diversification is [0.81, 0.45, 0.72] (0.9 x [0.9, 0.5, 0.8J) for "3v1", "counterattack", and "comner" respectively.
TrajDi
We also try TrajDi (Lupu et al. 2021) in the GRF domain. We sweep the action discount factor among (0.1,0.5, 0.9) and the coefficient of TrajDi loss among (0.1, 0.01, 0.01, 0.001). However,
Table 12: SIPO hyperparameters across all environments.
Amax
Discriminator Ir
Lagrangian Ir
lc-4
0.1
21

---

Under review as a conference paper at ICLR 2023
TrajDi fails to converge in the "3v1" scenario and exceeds the GPU memory in the "counterattack" and "corner" scenarios. Therefore, we exclude the performance of TrajDi in the main body.
DvD We concatenate the one-hot actions along a trajectory as the behavioral embedding. The square of the variance factor, i.e., o² in the RBF kernel, is set to be the length of behavioral embed- ding. We also use the same Bayesian bandits as proposed in (Parker-Holder et al. (020b). Training DvD in "counterattack" and "comner" exceeds the GPU memory and we exclude the results in the main body.
DIPG For DIPG (Masood & Doshi Desei-Velez, 2019), we follow the opensouree implementatior We set the same variance factor in the RBF kernel as SIPO-RBF and apply the same state the input of RBF kernel. We sweep the coefficient of MMD loss among {0.1, 0.5, 0.9} and find 0.1 the most appropriate (larger value will cause training instability). We the same method to trajectories as SIPO and the input of the RBF kernel the same as the input we use for SIPO-RBF. To improve training efficiency, the training is still much slower (~1 1--hhiterratinn for 3v/) than SIPO-RBF (~ 12 h/iteration for 3v/).
archived
only hack-propagate the MMD loss at the first PPO epoch, but
RSPO For RSPO (Zouu et al. 2022). we follow the opensource implementation and use the same hyperparameters the SMAC 2c 642g map in the original paper for GRF experiments.
D.4 ABLATION STUDY DETAILS
For the three ablation studies: fix-I., CE, and filter, we list the specific hyperparameters here:
fix-L: we set the Lagrange multiplier to be 0.2;
CE:
the threshold is 3.800 and the intrinsic reward scale factor is 1/ 1/1000 of that in the WD setting:
filter: all the hyperparameters in the setting the same as those in the WD setting.
E
PROOFS
E.1 PROOF OF THEOREM
Theorem 4.1
Assume is distance metric. Denote the optimal value of Problem Ti. Let
T2 AM J (Att where
7 = arg max J(T.) Ti
(3)
s.t. D(T mj) > 8/2, V1 Mijj<t
for i = 1,..., M. then T2 3 Ti.
Proof. Suppose the optimal solution of Problem is mı T2. -.. aM satisfying J(m) 3 J(R2) 3
2 ((TM) and the optimal solution of Problem is T. T2 Fa satisfying ( e ((
> J
Assume the contrary that Thm. is not true, which means MM J(TT) Ti T2 S J(
Then choose the smallest number N & M that satisfies
(TT)
((
By Tj > T3 we know that N exists. In addition, because Problem solves unconstrained RL in the
first iteration, know that म, arg max, (]Tr and then J(TT)) & ((r). Therefore, N > 2.
22

---

Under review as a conference paper at ICLR 2023
Suppose J(TN) & J(tx). Then have
N-1
N-1
Σ
J(m)) > Σ J(ū,).
Contradicting the fact that N is the smallest number satisfies that equation.
Hence, we know that (TT) > ( Then
J(T1) > J( > J(TN) > J(tN).
Consider the optimization problem of #::
IN arg max J(T)) D(T, 8/2,
V
This optimization does not find [T....., nN but find WN. which means that for each nÜ 1 < i & N, there exists 1 Js < N such that D(T, お5)) 8/2. Otherwise, we will get the solution of the above problem as π, instead of N..
By the Pigeonhole Principle, we know that there exist two indexes i e [N] and in [N] (i # i2) such that ji Jia j. Then we have
4g) where the inequality follows by the triangle inequality of the distance function. It contradict with the fact that D(T TT22) in Problem !
= 8, D(Ti, Tea) & at) + DiT., 4T) 6/2 8/2
Therefore, prove the theorem ΣM1 J(T,) Ti T2 ΣM J(a.).
E.2 PROOF THEOREM
In this section, we consider the i-th iteration of SIPO illustrated in Eq. @ For the sake of simplicity, we use a & À & b vector À to denote each component satisfies a & X; b, where b IR. We use to denote the policy we are optimizing, and Tÿ (1 & < i) to denote previously obtained policy. We denote the Lagrange function as L(T, X) -J(x) Σト X (D(T, mT) 8).
To prove Theorem
5.1
consider the following optimization problems:
(T,, X²) = arg min max L(T,) A) A
(11)
and
(#, X arg min L(T, A),
(12)
0EASA
where A 1 and > 0 is sufficiently small.
<p Assumption E.1. E J(-) &
Assumption E.2. AA > 0, L(-A) is I-smooth and (-Lipschitz Lemma E.3. J(m)) J J(::).
Proof. As the domain of X in Eq. 12 is smaller than Eq. 11 we have L(m,, A) > I(# 2).
By the fundamental property of Lagrange duality, know that L achieves its optimal value when = 0 and the optimal value is (m...
By the optimality of (f., X*), we know that
Xz(D(ā -
(13)
23

---

Under review as a conference paper at ICLR 2023
Then have
-J(T() L(TS, A²) > L( X1) -J( Σ -)) -- -J(...
Lemma E.4. Under Assumption E.1
D(Ti, Tz)
> 8 c0. 11 < j <i.
Proof. We prove by contradiction.
Suppose there exists $ jo < i, D 50 < cy-
Then we choose Ả such that
A ] jo
2
j # jo.
By the Assumption E.1 Eq. 13). and A
we have
60
0 (m:) (m,, L L( Å) - A(D(
T50) -1-1A((iT, 6) 0.
That is contradiction. So we have proved that D mT) 60:
E0: Mijjái.
Lemma E.5. (Lin et al. (2020), Theorem 4.8) Under Assumption E.2
solving Eq. 72) via two-
timescale GDA with learning rate The ( ( and пл
177
requires
(PC2A2C PA2C2
E1
iterations to converge to an e-stationary point nद. where C1 and O2 are the constants that depend on the distance between the initial point and the optimal point.
Theorem Under moderate assumptions, SIPO converges to neighbourhood of e-approximate KKT point.
Proof. At the i-th E & M) iteration, SIPO solves the following constrained optimization
min m
- (T,)
s.t.
D( Ty) > 8, V1 $ <i.
Consider the Lagrange function L(T, A) = = X (D(T, TT)) 8). Denote the optimal
solution of Eq. 11 and Eq. 12 as (T, A) and ( x) respectively.
By Lemma E.3 and Lemma E.4 we have
J(m;) J (
D(#, Tj) > co.
V1 vル
and therefore only need consider the following nonconvex-coneave optimization min max L(T,A).
(14)
06A5A
know that the Two-Timescale GDA algorithm converges stationary point T Denote ((x) = maXo=A=A L(T,N) and || || as the Euclidean distance. Using the property of e-stationary point T/ in (Lin al. 2020) (Lemma 3.8), we know that there exists n. such that ming [4ll & and | ..| < 21.
Following Lemma E.5
From the definition of L(T;, A), we know that म an e-approximate KKT point of ((TT) (Dutta al. 2013)).
From the above deduction, the Two- Timescaee GDA algorithm convergences to an neighbourhood of c-approximate KKT point of the above problem. The theorem then follows by applying the smoothness assumption.
24

---

Under review as a conference paper at ICLR 2023
F DISCUSSION
F.1 THE FAILURE CASE OF STATE-BASED DIVERSITY MEASURES
failure case of state-based diversity measures may be when the state space includes many irrel- evant features. These features cannot reflect behavioral differences. If we run SIPO in such an environment, the learned strategies may be only diverse w.r. these features and have little visual distinction. Like the famous noisy TV problem (Burda & Edwards 2018), the issue of irrelevant features intrinsically challenging for general RL applications, which cannot be resolved by using action-based diversity measures either.
Thanks to the advantages we discussed in the paper, we generally find that state-based metrics can be preferred in challenging RL tasks. Mcanwhile, since the state dimension can be much higher possible that RL optimization over states may be accordingly more difficult than
than actions, actions. In practice, diversity and run diversity learning over the filtered features. In SMAC and GRF, we utilize the agent features (excluding enemies) the input of diversity constraint without further modifications, as discussed in Appendix D We remark that even after filtering, the agent features remain high- dimensional while our algorithm still works well. Note that using a feature selector common practice in many existing domains, such as novelty search (Cully et al. 2015), exploration (Liu al. 2021a), and curriculum learning (Campero et al. 2021). There are also works studying how to extract useful low-dimensional features from observations (Wu et al. 2019 Ghosh et al. 2019
design feature selector for those most relevant features for visual
which are orthogonal to our focus.
F.2 THE DISTANCE METRIC IN STATE-BASED DIVERSITY MEASURES
In Sec. we adopt the two most popular implementations in the machine learning literature, i.e., RBF kernel and Wasserstein distance, while it is totally fine to adopt alternative implementations. For example, we can learn state representations (e.g. auto-encoder, Laplacian, or successor feature) and utilize pair-wise distance or norms as diversity measure. Similar topics have been extensively discussed in the exploration literature (Wu et al. 2019 Machado et 2020 We leave them as our future directions.
G PSEUDOCODE OF SIPO
The pseudocode of SIPO is shown in Algorithm
25

---

Under review as a conference paper at ICLR 2023
Algorithm SIPO (red for SIPO-RBF and blue for SIPO-WD)
Input: Number of Iterations M, Number of Training Steps within Each Iteration T.
Hyperparameter: Learning Rate Th. Diversity Threshold 8, Intrinsic Scale Factor a, Lagrange Multiplier Upperbound Amaa, Lagrange Learning rate f]x, Wasserstein Critic Learning Rate 1jw,
RBF Kernel Variance d.
1: Archived trajectories X < Ø
t- to store states visited by previous policies
2: for iteration i == .., M do
3: Initialize policy Re;
t> initialization
4: Initialize Wasserstein critic fø.
5: for archive index j l,..., do
6: Lagrange multiplier X - 0
7: end for
8: for Training step & = 1, I, do
T'
9:
Collect trajectory {88,, ag. r (8h,, ) h-1
for archive index j I...., do R end for
12:
13:
for timestep /t = 1,.... do
t> compute intrinsic reward
14:
Fint,
15:
for archive trajectory X X do
16:
min - Hixs Ev'x, exp
I 190-
20
17:
Piu. + 1
H [e, (sh) - Ixil
LI Soy
18:
Finth Fint, >3 r
19:
R R h + rinn
20:
end for
Th r(sk, an) + a Tint.
22:
end for
for archive index j 1, 1....,ū- do
24:
Xy clip Xg + 171 Ry +0) O, Amax
gradient ascent A
25:
Φ Φj + ww H 2 Va, (fr, 1xol Ewex, So,(
26:
+, - clip(d,, - 0.01, 0.01)
27:
end for
28:
Update Te with ((sn, an, rn)) by PPO algorithm end for
policy gradient A
29:
30:
Collect many trajectories Xi
collect trajectories approximate d for the of following iterations
31: X X bxi
32:
end for
26


Reviews:
[{"review_id": "v4-1CZ-PFtU", "reviewer": "Reviewer_aXw1", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "Combining iterative learning (IL) and the state-based diversity measure, this paper proposed a new framework called a powerful diversity-driven RL algorithm, State-based Intrinsic-reward Policy Optimization (SIPO), with provable convergence properties. IL repeatedly learns a single novel policy that is sufficiently different from previous ones. The paper proved that, for any policy pool derived by PBT, they can always use IL to obtain another policy pool of the same rewards and competitive diversity scores. In addition, they also present a novel state-based diversity measure with two tractable realizations, which can impose a stronger and much smoother diversity constraint than existing action-based metrics. It has been verified experimentally that SIPO is able to consistently derive strategically diverse and human-interpretable policies that cannot be discovered by existing baselines.", "summary_of_the_review": "This paper addresses the problem of discovering diverse high-reward policies in complex RL scenarios. An in-depth comparison of PBT and IL is carried out, and it is found that IL is easier to optimize and can obtain comparable solutions to PBT. Furthermore, the authors illustrate the necessity of combining IL with a diversity measure defined on the state distance through specific failure cases of action-based diversity measures, and finally propose a state-based intrinsic reward policy optimization algorithm (SIPO) and prove that The proposed framework and the analysis of the diversity measure will bring a lot of inspiration to future work on policy diversity and PBT.", "strength_and_weaknesses": "a)\tStrength:\nThis paper addresses a very important problem in reinforcement learning: policies with similar rewards may have fundamentally different behaviors. Therefore, the authors propose SIPO to discover as many different policies as possible. This paper objectively expounds on the disadvantages of the PBT method and proposes a very novel method that mathematically gives a state-based diversity measure and proves the convergence. Through experimental results, they find that SIPO is able to consistently derive strategically diverse and human-interpretable policies that cannot be discovered by existing baselines. The graphs are very clear. Figure 2 compares the training process of SIPO and PBT from a geometric perspective, which proves the advantages of SIPO and gives a lot of inspiration. The RL environments are also complex, which can fully prove the ability of the SIPO, and provides a well-made demo.\n\nb)\tWeaknesses: \nWhen measuring Action-Based diversity, the author claims that A can be any distance metric. For different distance metrics, theoretical analysis is no problem, but will it affect the final experimental results? Maybe the author can consider adding these Experiments and Demonstrations. There are also many improvements to the PBT method in the future, perhaps the author can consider making further comparisons to reflect the advantages of SIPO.\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": "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": "JJKrJJSFMHq", "reviewer": "Reviewer_GEJD", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "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 explores methods for discovering diverse policies for RL problems, specifically focusing on MARL. This is well-motivated, as these types of methods have become increasingly prominent in recent years and played a part of large scale successes such as AlphaStar. The paper then disappointingly focuses on a new algorithm \"SIP\" which is rather similar to many other similar algorithms in the space. My suggestion would be to focus on the analysis of design choices and produce a useful paper for the community, rather than trying to win on some benchmarks which makes the results hard to trust and subsequently transfer. ", "summary_of_the_review": "Nothing in this paper is new and that is totally fine. But, what I dislike is the approach of claiming to invent a new algorithm that \"wins\" on a specific benchmark chosen by the authors and making the paper all about this algorithm. Instead, if the authors reframe this paper as an analysis of joint vs. sequential population training algorithms, and a comparison of state vs. action representations, with theory and experiments showing this trade-off then it would be a useful contribution and I'd likely vote to accept. The paper I just described would be interesting to many, more broadly useful, and might also get cited a fair amount.", "strength_and_weaknesses": "### Strengths\n\n- This paper covers many very interesting areas, for example comparing state vs. action representations and parallel vs. sequential population learning. If these were executed in a more rigorous way it would make a great contribution.\n- The results in Figure 6 are interesting. \n- The experiments are in relevant and reasonably high dimensional tasks.\n- Related work seems to be correctly cited.\n\n### Weaknesses\n\n- The biggest weakness here is that the paper is framed as a new algorithm to rule them all when it really doesn't need to be. The actual algorithm isn't particularly novel, it is very similar to approaches like DOMiNO (Zahavy et al), which train policies using state occupancy metrics. Instead, if the authors focused on analyzing 1. Parallel vs. Sequential population training and 2. State vs. action representations then this would be a good paper I would accept. \n- I think it is wrong to say prior work \"typically\" use action based representations for diversity. This is really just DvD and TrajeDi. Many previous works, including the original Novelty search, DIAYN etc have used diversity in the state space/trajectories. It is not super novel to switch back to states.\n- The failure mode of action based metrics presented in Figure 3 is not necessarily true. In DvD, the actions are compared for *the same states*, while here it is for different states. The only state where the policies take different actions here is s0, otherwise it is possible that both policies act the same way everywhere else. So concretely, I disagree with the L2 norm being 2\\sqrt{2} for D(\\pi_1, \\pi_2) in the case where the states are sampled from a joint distribution of the state visitation from both policies. \n- How does bolding work in the tables, e.g. Table 4 & 5? It seems like in both cases there are multiple cells with the same value but the one with your method is bolded and the others aren't. Seems totally unnecessary to try and look like you \"win\". \n\nMinor issues (did not impact score):\n- Section 3 title, \"Preliminary\" -> \"Preliminaries\"\n- Sec 4.1 \"motivation example\" -> \"motivating example\"\n- Sec 4.1 \"worst case in 1-D setting\" -> \"in a 1-D setting\"", "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": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "0hn_zubBvPe", "reviewer": "Reviewer_nUUy", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "An important problem in RL is to compute a diverse set of strategies that optimize the (total) reward. One strategy is to simultaneously optimize over all strategies, as with population-based training (PBT), but this can be computationally challenging. An alternative is to use a greedy algorithm, as with iterative learning (IL), which iteratively learns a new policy that is sufficiently diverse from all policies computed so far. The paper sheds light on the performance guarantees and the convergence properties of IL methods. Furthermore, it argues that, at least in the scenarios considered in the paper, a diversity measure based on state distances is more meaningful than action-based diversity. The authors combine IL and state-based diversity measures, and propose a new framework, State-based Intrinsic-reward Policy Optimization (SIPO), for discovering diverse RL strategies in an iterative fashion. For optimization, they use two-timescale gradient descent ascent (GDA), which comes with convergence guarantees. SIPO is empirically evaluated on two challenging multi-agent environments, namely, Star-Craft Multi-Agent Challenge and Google Research Football, where it is able to discover diverse and human-interpretable strategies.\n", "summary_of_the_review": "Overall, I tend to be positive about the work because it provides various a number of interesting insights together with a rigorous analysis of an IL algorithm (SIPO with GDA). The results seem to confirm that SIPO can compute diverse policies in the multi-agent games of the evaluation. That said, the paper makes various strong claims, which may not be fully substantiated in the text. It would make sense to revisit some of these statements to increase precision. Furthermore, even though SIPO can get slightly better numbers than RSPO in the evaluation, I have the feeling that the empirical analysis does not provide very strong evidence for the superior performance of SIPO compared to RSPO.", "strength_and_weaknesses": "Strengths\n- The work provides several interesting insights: (i) the fact that IL can in fact achieve rewards similar to PBT by just trading-off half the diversity; (ii) the fact that IL can converge easily to diverse solutions by imposing a large diversity constraint, as opposed to PBT which suffers from slow convergence (or even divergence); (iii) the fact that in certain scenarios action-based diversity may produce similar policies, which motivates the authors to introduce a state-based diversity measure.\n- The connection of SIP with intrinsic rewards is interesting. Intrinsic rewards and curiosity are often used to signal whether the agent has encountered a known or surprising state, so they fit well with the state-based diversity. \n- SIPO comes with theoretical guarantees (when coupled with GDA).\n- The two multi-agent games considered in the experimental evaluation are quite complex, and SIPO is able to achieve good results.\n\nWeaknesses\n- I understand that in the scenarios considered in this work, a state-based diversity measure is more appropriate. However, is this always the case? For example, one case where a state-based diversity measure would not make sense is when there are many irrelevant states. In that case, even if a new policy is quite diverse in terms of the irrelevant states, it may not be much more interesting than the existing policy. Do the authors make the claim that state-based diversity should always be preferred to action-based diversity? That would be a strong statement, and I am not sure enough evidence is provided in the test for such a claim.\n- The authors claim that the strategies discovered by SIPO are not only diverse but human-interpretable as well. I do not dispute that this is the case in the studied scenarios. But I do not see how the proposed framework can generally guarantee interpretability. Is it sufficient to just enforce state-based diversity for this purpose? I do agree that SIPO would be expected to result in diverse policies, but I personally fail to see how human-interpretability can arise out of SIPO.\n- In Table 4, the authors mention the number of visually distinct strategies discovered by different methods. Maybe I missed that in the text, but how did the authors come up with the exact number? This seems a very subjective metric, since different observers may report a different number. I was wondering whether some other methodology was followed instead.\n- When it comes to comparing SIPO with other competitors (including RSPO), I am not sure that the current empirical evaluation does a very convincing job. Tables 3 and 4 indeed show improved numbers for SIPO, but RSPO also performs quite well (e.g., in Table 4). The empirical analysis shows to some extent that SIPO produces diverse policies, but I am not so sure that it shows very strongly that SIPO is consistently better than RSPO.", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject