Iteratively Learn Diverse Strategies with State Distance Information
Authors: Wei Fu
Weihua Du
Jingwei Li
Sunli Chen
Jingzhao Zhang
Yi Wu
Venue: NeurIPS 2023 poster (2023)
Keywords: diverse behavior
multi-agent reinforcement learning
deep reinforcement learning
TL;DR: Based on the analysis of existing approaches, we develop an iterative RL algorithm for discovering diverse high-reward strategies with provable convergence properties.

Abstract: In complex reinforcement learning (RL) problems, policies with similar rewards may have substantially different behaviors. It remains a fundamental challenge to optimize rewards while also discovering as many *diverse* strategies as possible, which can be crucial in many practical applications. Our study examines two design choices for tackling this challenge, i.e., *diversity measure* and *computation framework*. First, we find that with existing diversity measures, visually indistinguishable policies can still yield high diversity scores. To accurately capture the behavioral difference, we propose to incorporate the state-space distance information into the diversity measure. In addition, we examine two common computation frameworks for this problem, i.e., population-based training (PBT) and iterative learning (ITR). We show that although PBT is the precise problem formulation, ITR can achieve comparable diversity scores with higher computation efficiency, leading to improved solution quality in practice. Based on our analysis, we further combine ITR with two tractable realizations of the state-distance-based diversity measures and develop a novel diversity-driven RL algorithm, *State-based Intrinsic-reward Policy Optimization* (SIPO), with provable convergence properties. We empirically examine SIPO across three domains from robot locomotion to multi-agent games. In all of our testing environments, SIPO consistently produces strategically diverse and human-interpretable policies that cannot be discovered by existing baselines.

Iteratively Learn Diverse Strategies with State Distance Information
Wei Fulh, Weihua Du" Jingwei Li Sunli Chen', Jingzhao Zhang Yi Wu III, Tsinghua University, 2 Shanghai Qi Zhi Institute fuuth170gmail. com, "jxmuy@@gmail.. @gmail com
Abstract
In complex reinforcement learning (RL) problems, policies with similar rewards may have substantially different behaviors. It remains fundamental challenge to optimize rewards while also discovering as many diverse strategies as possible, which can be crucial in many practical applications. Our study examines two design choices for tackling this challenge, i.e., diversity measure and computation frame- work. First, we find that with existing diversity measures, visually indistinguishable policies can still yield high diversity scores. accurately capture the behavioral difference, we propose to incorporate the state-space distance information into the diversity measure. In addition, we examine two common computation frame- works for this problem, i..., population-base based training (PBT) and iterative learning (ITR). We show that although PBT is the precise problem formulation, ITR can achieve comparable diversity scores with higher computation efficiency, leading improved solution quality in practice. Based on our analysis, we further combine ITR with two tractable realizations of the state state-distance distance- based diversity measures and develop a novel diversity-driver RL algorithm, State-based Intrinsic-reward Policy Optimization (SIPO), with provable convergence properties. We empirically examine SIPO across three domains from robot locomotion to multi-agent games. In all of our testing environments, SIPO consistently produces strategically diverse and numan-interpreelie policies that cannot be discovered by existing baselines.
Introduction
A consensus in deep learning (DL) is that different local optima have similar mappings in the functional space, leading to similar losses to the global optimum 62 56 40). Hence, via stochastic gradient descent (SGD), most DL works only focus the final performance without considering which local optimum SGD discovers. However, in complex reinforcement learning (RL) problems, the policies associated with different local optima exhibit significantly different behaviors [TO 35 64
Thus, it is fundamental problem for an RI. algorithm to not only optimize rewards but also discover many diverse strategies possible. A pool of diversified policies towards wide range of applications, including the discovery of emergent behaviors [44 3 61],
be further leveraged
generating diverse dialogues [30], designing robust robots [12 25 [9], and enhancing human-Al collaboration (38
Obtaining diverse RL strategies requires quantitative method for measuring the difference (i.e., diversity) between two policies. However, how to define such a measure remains an open challenge. Previous studies have proposed various diversity measures, such comparing the difference between the action distributions generated by policies [60] 38 [74,, computing probabilistic distances between the state occupancy of different policies
431
measuring the mutual information between states and
Equal Contribution
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

policy identities [16]. However, it remains unclear which measure could produce the best empirical performance. Besides, the potential pitfalls of these measures are rarely discussed.
In addition to diversity measures, there are two common computation frameworks for discovering diverse policies, including population-basee training (PBT) and iterative learning (TTR). PBT directly solves a constrained optimization problem by learning a collection of policies simultancously, subject Although PBT perhaps the most popular framework in the existing literature, it can be computationally challenging [4]] since the number of constraints grows quadratically with the number of policies. The alternative framework ITR, which iteratively learns a single policy that is sufficiently different from previous policies 43] 74). ITR is a greedy relaxation of the PBT framework and it largely simplifies the optimization problem in each iteration. However, the performance of the ITR framework has not been theoretically analyzed yet, and it is often believed that ITR can be less efficient due to its sequential nature.
to policy diversity constraints [52] 38 ?
We provide a comprehensive study of the two aforementioned design choices. First, we examine the limitations of existing diversity measures in a few representative scenarios, where two policies outputting very different action distributions can still lead to similar state transitions. In these scenarios, eale-occuppaccy-based measures are not sufficient to truly reflect the underlying behavior differences of the policies either. By contrast, we observe that diversity measures based on state distances can accurately capture the visual behavior differences of different policies. Therefore, we suggest that an effective diversity measure should explicitly incorporate state distance information for the best practical use. Furthermore, for the choice of computation framework, we conduct an in-depth analysis of PBT and ITR. We provide theoretical evidence that ITTR which has a simplified optimization process with fewer constraints, can discover solutions with the same reward as PBT while achieving af least half of the diversity score. This finding implies that although ITR is greedy relaxation of PBT, their optimal solutions can indeed have comparable qualities. Furthermore, note that policy optimization is much simplified in ITR, which suggests that ITR can result in much better empirical performances and should be preferred in practice.
Following our insights. we combine ITR and state-distane--ee based diversity measure to develop a generic and effective algorithm, State-based Intrinsic- intrinsic-reward Policy Optimization (SIPO), for discovering diverse RL strategies. In each iteration, we further solve this constrained optimization problem via the Lagrange method and two-timescale gradient descent ascent (GDA) [1. We theoretically prove that our algorithm is guaranteed to converge to a neighbor of c-stationary point. Regarding the diversity measure, we provide two practical realizations, including a straightforward version based on the RBF kernel and a more general learning-based variant using Wasserstein distance.
We evaluate SIPO in three domains ranging from single-agent continuous control to multi-agent games: Humanoid locomotion 42. StarCraft Multi-Agent Challenge [57]. and Google Research Football (GRF) [26). Our findings demonstrate that SIPO surpasses baselines in terms of population diversity score across all three domains. Remarkably, our algorithm can successfully discover distinct numan-interpretabbe strategies in the GRF 3-vs-1 scenario and 4 strategies in two 1 11-player GRF scenarios, namely counter-attack, and corner, without any domain-speciff priors, which are beyond the capabilities of existing algorithms.
2 Related Work
Diversity in RL. It has been shown that policies trained under the same reward function can exhibit significantly different behaviors 110 35). Merely discovering a single high-perforning solution may
not suffice in various applications 12 64 25). As such, the discovery of diverse range of policies
is fundamental research problem, garnering attention over many years
44 13
28 Early works
are primarily based on multi-objective optimization 45
55 39
54], which assumes a set of
reward functions is given in advance. In RL, this is also related to reward shaping 46 consider learning diverse policies without any domain knowledge.
2 15
61.
We
Population-based training (PBT) is the most popular framework for diverse solutions by jointly
learning separate policies. Representative works include evolutionary computation [63 37 52). league training (64|
23
computing Hessian matrix [51 or constrained optimization with population
diversity measure
38
73
29
36 An improvement is to learn a latent variable policy instead of
separate ones. Prior works have incorporated different domain knowledge to design the latent code,

---

3] The latent variable can be also learned in an unsupervised fashion, such as DIYAN [66] and its variants 225 49
such as action clustering [66], agent identities [29 21 or prosocial level [53 [33
Zahavy et al. [71 learns diverse policies with hard constraints on rewards to ensure the derived policies are (nearly) optimal, potentially hindering policies with disparate reward scales. On the other hand, our method prioritizes diversity and fully accepts sub-optimal strategies.
Iterative learning (TTR) simplifies PBT by only optimizing a single policy in each iteration and forcing it to behave differently w.r.t. previously learned ones [43] 60, 74]. While some ITR works
require an expensive clustering process before each iteration 72 or domain-specific features [70], we consider Nomain-agnosioe ITR in an end-to-end fashion. Besides, Pacchiano et al. [50] learns kerne-- based score function to iteratively guide policy optimization. The score function conceptually similar to SIPO-WD but is applied to a parallel setting with more restricted expressiveness power.
Diversity Measure. Most previous works considered diversity measures action distribution and state occupancy. For example, measures such as Jensen-Shannon divergence [38] and cross- entropy [74] are defined over policy distributions encourage different policies take different actions on the same state, implicitly promoting the generation of diverse trajectories. Other measures such as maximum mean discrepancy [K] maximize the probability distance between the state distributions induced by two policies. However, these approaches can fail to capture meaningful behavior differences between two policies in certain scenarios, as we will discuss in Section There also exist specialized measures, such as cross-play rewards [9], which are designed for cooperative multi-agent games. It is worth noting that diversity measures are closely related to exploration
criteria 4 20 27 and skill discovery [8] 32 24], where a diversity surrogate objective is often introduced to encourage broad state coverage. However, this paper aims to explicitly discover mutually distinct policies. Our diversity measure depends on a function that computes the distance between states visited by two policies.
Preliminary
Notation: We consider POMDP
159 defined by M = (S, S is the state space. A and ( are the action and observation space. S
IR is the reward function. O: + O is the observation function. H is the horizon. P is the transition function. At timestep h, the agent receives an observation On (sh) and outputs an action aA A w.r.t. its policy J(x)) is defined by J(T)) (ee,,.o))~(P.. E an))
0 A The RL objective
The above formulation can be naturally extended to cooperative multi-agent settings, where π and R correspond to the joint policy and the shared reward. We follow the standard POMDP notations for conciseness. Our method will be evaluated in both single-agent tasks and complex cooperative multi-agent scenarios. Among them, multi-agent environments encompass notably more diverse range of potential winning strategies, and hence offer an apt platform for assessing the effectiveness of our method. Moreover, in this paper, we assume access object-centric information and features rather than pure visual observations to simplify our discussion. We remark that although we restrict the scope of this paper to states, our method can be further extended to digeesinnnii inputs (e.g. images, see App. B.4.1) or tabular MDPs via representation learning [68] [4].
Finally, discover diverse strategies, we aim learn set of M policies these policies are locally optimal under J(-) but mutually distinct subject to some diversity measure D(..)) A A + R, which captures the difference between two policies.
{T; ) such that all of
Existing Diversity Measures: We say a diversity measure D is defined over action distribution if it can be written as
D(T, RT) = Essg(s)
[D (T () ( (1))]
where g is an occupancy measure over states, D : A x A - IR measures the difference between action distributions. D can be any probability distance as defined in prior works 660
38
74 52
Denote the state occupancy of 4n. We say diversity measure is defined over state occupancy if can be written as
D(Ti Tz) = Ds ()m)))
3

---

Table 1: Diversity measures of the grid-world example. Computation details can be found App.
Agent
B
X
action-based
state-distanss-based
human
K1.
ISD1
JSDg/EMD
Lo norn
Lg norm
EMD
[T m2)
small
+00
log
1/2
V7
2v2
5.7
D mg)
large
4.00
log 2
1/8
2v6
11.3
Figure I: (left) A grid-world world environment with 5 different optimal policies. Intuitively, D( T2) < D(m, Ta) and D(Ta, ma) < D no). However, action based measures can give DA(RI, T2) 2 Da(TI, 0s) and state-occupancy based measures can give ([Ts, m44 (R nT).
which can be realized as an integral probability metric We remark that gx is usually intractable. In addition to diversity measures, we present two popular computation frameworks for this purpose.
Dopulation-Baset Training (PBT): PBT is straightforward formulation by jointly learning M policies [
M subject to pairwise diversity constraints, i.e.,
max
((mt) s.t. D(T,, ma) 2 6, VJ [M), * (144
(3)
where d is threshold. In our paper. we consistently refer to the aforementioned computation framework as "PBT", rather than adjusting hyperparameters [22]. Despite a precise formulation, PBT poses severe optimization challenges due to mutual constraints.
Iterative Learning (TTR): ITR is a greedy approximation of PBT by iteratively learning novel policies. In the i-th (1 < á < M) iteration, ITR solves
π arg max (TT) s.t. ((T., TJ) V1 S <.
(4)
T is recursively defined by the above equation. Compared with PBT, ITR trades off wall-clock time for less required computation resources (e.g., GPU memory) and performs open-ended training (i.e.,
the population size M does not need to be fixed at the beginning of training).
4 Analysis of Existing
Approaches
In this section, we conduct both quantitative and theoretical analyses of existing approaches to motivate our method. We first discuss diversity measures in Sec. 4.1 and then compare computation frameworks, namely PBT and ITR, in Sec. 4.2
4.1 A Common Missing Piece in Diversity Measure: State Distance
The perception of diversity among humans primarily relies on the level of dissimilarity within the state space, which measured by a distance function. However, the diversity measures outlined in Eq. (I) and Eq. (2) completely fail to account for such crucial information. In this section, we provide detailed analysis to instantiate this observation with concrete examples and propose a novel diversity measure defined over state distances.
First, we present synthetic example demonstrate the limitations of current diversity measures. Our example consists of a grid-world environment with a single agent and grid size No- The agent starts the top left of the grid-world and must navigate the bottom right corner, as shown in Fig. [ While NG can be large in general, we illustrate with NG = 5 for simplicity. We draw five distinct policies, denoted as म. through nT. which differ in their approach to navigating the grid-world. Consider 11, π2, and first. Although humans may intuitively perceive that policies and T2, which move along the diagonal, are more similar to each other than to T3. which moves along the boundary, diversity measures based on actions can fail to reflect this intuition, as shown in Table [] Then, let's switch to policies π3, T4, and Ty. We find that state-occupancy-beee based diversity measures are unable to differentiate between and mı in contrast to πT. This is because the states visited by Ty are entirely disjoint from those visited by both क4 and TT. However, humans would judge my to be more distinct from T3 than Ty because both π3 and Ta tend visit the upper boundary.

---

Training Progress
Epoch
Epoch 10
Epoch 20
Epoch 30
PBT
ITR
Dribbling Playar
Player
Iteration 1
Iteration 2
lteration
Iteration 4
Figure counter-example for
action-based diversity measure:
Figure Illustration of the learning process of PBT and ITR in a 2-D navigation environment with 4 modes. PBT will not uniformly converge different landmarks as computation can be either too costly unstable. By contrast, ITR repeatedly excludes a particular landmark, such that policy in the next iteration can continuously explore until novel landmark is discovered.
in a football game, we can achieve high diversity score by simply asking single idle player out- put random actions, which does not affect the high-level gameplay strategy at all.
Next, we consider a more realistic and complicated multi-agent football scenario, i.e., the Google Research Football (26) environment, in Fig. 2 where an idle player the backyard takes arbitrary action without involving in the attack at all. Although the idle player stays still with no effect on the team strategy, action-based measures notable issue. If action-based measures are leveraged to optimize diversity, the resultant policies can produce visually similar behavior. While can be possible to exclude idle actions by modifying task rewards, it requires domain-specific hacks and engineering efforts. The issue of idle actions exists even such popular MARL benchmarks. Similar issues have also been observed in previous works (38]
produce high diversity scores. This example underscores
To summarize, existing measures suffer from a significant limitation they only compare the behavior trajectories implicitly through the lens of action or state distribution without explicitly measuring state distance. Specifically, action-based measures fail capture the behavioral differences that may arise when similar states are reached via different actions. Similarly, state occupancy measures do not quantify the degree of dissimilarity between states. To address this limitation, we propose a new diversity measure that explicitly takes into account the distance function in state space:
D π5) = (s,)'>>>> (d (s,ss')) s')],,
(5)
d is distance metric over S x S. g R+ IR is monotonic cost function. I'(m,, Qxy) is distribution over state pairs. [(g,, Ix,) denotes the collection of all distributions on S x S with marginals dx, and In, on the first and second factors respectively. The cost function g notation providing a generalized and unified definition. It also contributes to training stability by scaling the raw distance. We highlight that Eq. 5 computes the cost on individual states before taking expectation, and therefore prevents information loss of taking the average over the entire trajectory (e.g. the DvD score (52)). We also note that states are consequences of performed actions. Hence, state-distance-based measure also implicitly reflects the (meaningful) differences in actions between two policies. We compute two simple measures based on state distance, i.e., the L2 norm and the Earth Moving Distance (EMD), for the grid-world example and present results in Table These measures are consistent with human intuition.
4.2 Computation Framework: Population- Based or Iterative Learning?
We first consider the simplest motivating example to intuitively illustrate the optimization challenges. Let's assume that m; is a scalar, JT;;) is linear in ny and D(T,, πT) - πTy- | In our definition, where M denotes the number diverse policies, PBT involves O constraints a single linear programming problem while ITR involves ((M) constraints in each of M iterations. Given that the complexity of linear programming a high-degree polynomial (higher than 2) of the number of constraints, solving PBT is harder (and probably slower) than solving ITR in total of M iterations,
5

---

despite PBT being parallelized. This challenge can be more severe in RL due to complex solution space and large training variance.
[(m)
Although ITT can be optimized efficiently, re- mains unclear whether ITR, as a greedy approx- imation of PBT, can obtain solutions of compa- rable rewards. Fig. 4 shows the worst case in the 1-D setting when the ITR solutions (green) can indeed have lower rewards than the PBT solu- tion (red) subject to the same diversity constraint. However, we will show in the next theorem that ITR is guaranteed to have no worse rewards than PBT by trading off half of the diversity.
X optimal solution
solution found by ITR with threshold 6/2
worst-case solution found by ITR with threshold 5
8/2
6/2
6/2
6/2
Figure 4: 1-D worst case of ITR. With threshold 6, ITR finds solutions with inferior rewards. However, ITR can find optimal solutions if the threshold is halved.
Theorem 4.1. Assume D is a distance metric. T3 - E J(++) where
Denote the optimal value of Eq. 3 as Tr. Let
ä. = arg max [mm] s.t. D(T,, H3) 2 6/2,01 n
(6)
for i = I,...,, M, then To 2 Ti.
Please see App. E. for the proof. The above theorem provides quality guarantee for ITR. The proof can be intuitively explained by the I-D example in Fig. 4 where green points represent the worst case with threshold and blue points represent the solutions with threshold 6/2. Thm. 4.1 shows that, for any policy pool derived by PBT, we can always use ITR to obtain another policy pool, which has the same rewards and comparable diversity scores.
We empirically compare PBT and ITR a 2-D navigation environment with 1 agent and Nr. landmarks in Fig. 3 The reward is if the agent successfully navigates to a landmark and 0 otherwise. We train N₂ policies using both PBT and ITR to discover strategies toward each of these landmarks. More details can be found in App. D Table Table shows the number of discovered landmarks by PBT and ITR. ITR performs consis- tently better than PBT even in this simple example. We intuitively illustrate the learning process PBT and ITR in Fig. 3 ITR, due to its computation efficiency, can afford to run longer iterations and tolerate larger exploration noises. Hence, converge easily to diverse solutions by imposing a large diversity constraint. PBT, however, only converges when the exploration is faint, otherwise it diverges converges too slowly.
Empirical Results:
Table 2: landmarks across seeds with stan- dard deviation in the bracket.
The number of discovered
setting
PRT
ITR
Nr. 4
(1.0)
3.5 (0.5)
Nr. 5
2.2 (0.9)
4.5 (0.5)
4.3 Practical Remark
Based on the above analyses, we suggest ITR and diversity measures based on state distances be preferred in RL applications. We also acknowledge that, by the no-free-lunch theorem, they cannot be universal solutions and that trade-offs may still exist (see discussions in Sec(7 and App/F) Nonetheless, in the following sections, will show that the effective implementation of these choices can lead to superior performances in various challenging benchmarks. We hope that our approach will serve starting point and provide valuable insights into the development of increasingly powerful algorithms for potentially more challenging scenarios.
5 Method
In this section, we develop a diversity-driven RL algorithm, State-based Intrinsic-reward Policy Optimization (SIPO). by combining ITR and Mate-distance-based measures. SIPO runs M iterations to discover M distinct policies. At the i-th iteration, solve equation by converting into unconstrained optimization using the Lagrange method. The unconstrained optimization can be written as:
min
max
-m..)
Σ Xg (Ds(T.,
(7)
M; Xy20, 183K

---

A3 S < i) are Lagrange multipliers. { { are previously obtained policies. We adopt two-timescale Gradient Descent Ascent (GDA) B1 solve the above minimax optimization, i... performing gradient descent over मi and gradient ascent over \ with different learning rates. In our algorithm, we additionally enforce the dual variables X, to be bounded (i.e., in an interval [0, A] for large number A), which plays an important role both in the theoretical analysis and in empirical convergence. However, (T, x cannot be directly optimized w.r.t T. through gradient-based methods because it depends
the states traversed by x, rather than its output (e.g. actions). Therefore, we cast (s( x as the cumulative sum of intrinsic rewards, specifically the intrinsic return. This allows to leverage policy gradient techniques for optimization. The pseudocode of SIPO can be found in App.
An important property of SIPO is the convergence guarantee. We present an informal illustration in Thm. 5.1 and present the formal theorem with proof App. F.2
Theorem 5.1. (Informal) Under continuity assumptions, SIPO converges to an e-stationary point.
Remark:
We assumed that the return J and the distance Ds smooth in policies. In practice, this is true if (1) policy and state space are bounded and (2) reward function and system dynamics are o
continuous in the policy. (Continuous functions are bounded over compact spaces.) The key step is to analyze the role of the bounded dual variables X, which achieves an x -approxximation of constraint without hurting the optimality condition.
Instead of directly defining Dg, we define intrinsic rewards as illustrated in Sec. 5 (T(Ti, m3)
such that
H E Time(805 Ti, mT, m
RBF Kernel: The most popular realization of Eq. (5) in machine learning is through kernel functions. Herein, we realize Eq. (5) as an RBF kernel on states, Formally, the intrinsic reward is defined by
[- -exp
||sh. - ='1l²)
RBF (an: We, RJ)
H Eurmnng
(8)
2a²
where a is hyperparameter controlling the variance.
For stronger discrimination power, we can also realize Eq. (5) as L2- Wasserstein distance. According to the dual form 63). define
Wasserstein Distance:
WD Fini
(shi Tay nj) H
sup [(sn) - Estway [S('']]
(9)
11
where f : S R is I-Lipschitz function. This realization holds distinct advantage due to its interpretation within optimal transport theory 63 I. Unlike distances that rely solely on specific summary statistics such as means, Wasserstein distance can effectively quantify shifts in state distributions and remains robust in the presence of outliers [63]. We implement f as a neural network and clip parameters to [-0.01, 0.01] ensure the Lipschitz constraint. Note that im.. incorporates representation learning by utilizing a learnable scoring function I and is more flexible in practice. We also show in App. B.4 that ini robust to different inputs, including states with random noises and RGB images.
SIPO-RBF and SIPO-WD respectively. We name SIPO with RBF and int int
Implementation:
To incorporate temporal information, we stack the recent global states to compute intrinsic rewards and normalize the intrinsic rewards to stabilize training. In multi-agent environments, we learn an Our implementation is based on MAPPO [69] with more details in App. D
policy (17) and share the parameter across all agents.
6 Experiments
We evaluate SIPO across three domains that exhibit multi-modality of solutions. The first domain is the humanoid locomotion task in Isaac Gym 42 where diversity can be quantitatively assessed by well-defined behavior descriptors. We remark that the issues we addressed in Sec. Sec. may not be present in this task where the action space is small and actions are highly correlated with states. Further, we examine the effectiveness of SIPO two much more challenging multi-agent domains, StarCarft Multi-Agent Challenge (SMAC) (7 and Google Research Football (GRF) (26). where well-defined behavior descriptors are not available and existing diversity measures may produce misleading diversity scores. We provide introductions to these environments in App. C
7

---

First, we show that SIPO can efficiently learn diverse strategies and outperform several baseline methods, including DIPG 44 SMERL [25], DvD [52]. and RSPO 774.. Then, we qualitatively demonstrate the emergent behaviors learned by SIPO, which are both risually distinguishable and humann-nterprrttbble. Finally, we perform an ablation study over the building components of SIPO and show that both the diversity measure, ITR, and GDA are critical to the performance.
All algorithms run for the same number of environment frames on desktop machine with an RTX3090 GPU. Numbers are average values over 5 seeds in Humanoid and SMAC and 3 seeds in GRF with standard deviation shown in brackets. More algorithm details can be found in App. D Additional visualization results can be found on our project website (see App. Ap.
6.1 Comparison with Baseline Methods
Humanoid Locomotion. Following Zhou et al. 7Z we train a population of size 4. We assess diversity by the pairwise distance of joint torques, a widely used behavior descriptor works [67] Torque states are not
Table
Pairwise distance of joint torques (i.e. diversity scores) in the hu- manoid locomotion task.
in recent
included as the input of diversity measures and we only use them for evaluation to ensure fair comparison. Results are
SIPO-RBE
SIPO WDD
RSPO
0.53(0.17)
0.71(0.23)
0.53(0.05)
shown in Table [3] We can see that both variants of SIPO can outperform all baseline methods except that SIPO-RBF achieves comparable performance with RSPO, even if RSPO explicitly encourages the output of different actions/forces.
DIPG
DvD
SMERL
0.12(0.04)
0.4000.22)
0.01(0.00)
SMAC Following Zhou et al. [74). we run SIPO and all baselines on an easy map, 2m vs Iz, and a hard map, 2c_vs_ vs_64gg, both across 4 iterations. We merge all trajec-
Table 4: State entropy estimated by
nearest-neighhor in SMAC. (k = 12)
tories produced by the policy collection and incorporate a k-nearest-neighhor state entropy estimation
2m_
2e_rx_6f 66
(88] to assess
SIPO RBF
0.038(0.002)
0.072(0.003)
diversity. Intuitively, a more diverse population should have a larger state entropy value. We set A = 12 following Liu and Abbeel [32] and show results in Table On these maps, two agents are both involved in the attack. There- fore, RSPO, which incorporates an action-based cross-
SIPO-WD
0.036(0.001)
0.056(0.003)
RSPO
0.032(0.003)
0.070(0.001)
DIPU
0.032(0.002)
0.056(0.004)
SMERL
0.028(0.002)
0.042(0.002)
DWD
0.030(0.002)
0.057(0.003)
entropy measure, can perform well across all baselines. However, SIPO explicitly compares the distance between resulting trajectories and can even outperform RSPO, leading to the most diverse population.
GRF We consider three academy scenarios, specifically 3v1, counterattack (CA), and corner. The GRF environment is more challenging than SMAC due to the large action space, more agents, and the existence of duplicate actions. We determine a population size M by balancing resources and wall-clock time across different baselines. Yablee]commpaes the number of distinct policies (in terms of ball- ball-passing routes, see B.3) discovered in the population. Due to the strong adversarial power of our diversity measures and the application of GDA, SIPO is the most efficient and robust- even in the challenging 1 11-vs-11 corner and CA scenario, SIPO can effectively discover different winning strategies in just a few iterations across different seeds. By contrast, baselines suffer from learning instability in these challenging environments and tend to discover policies with slight distinctions. We also calculate the estimated state entropy as we did in SMAC. However, find that this metric cannot distinguish fine-grained ball-passing behaviors in GRF (check our discussions in App.
Remark: In GRF experiments, when M is small, even repeated training with different random seeds (PG) a strong baseline (see T). Hence, the numbers are actually restricted in small interval (with a lower bound equal to PG results and an upper bound equal to M = 4). which makes the improvements by SIPO seemingly less significant. However, achieving clear improvements in these challenging applications remains particularly non-trivial. With a population size M = 10, SIPO clearly outperforms basclines by consistently discovering one or more additional strategies.
6.2 Qualitative Analysis
For SMAC, we present heatmaps of agent positions in Fig. 5 The heatmaps clearly show that SIPO can consistently learn novel winning strategies to conquer the enemy. Fig. 6 presents the learned
8

---

policy
policy
policy
policy
94
7
2m, vs_
20
15
26
25
8
26
15 28
x position policy 4
policy 1
policy
policy 3
27
densiyy
17
2c_ [o_vs_6rt 6,2gg
position
Figure 5: Heatmaps of agent positions in SMAC across 4 iterations with SIPO-RBF.
Attacker
Defender
Ball Direction
Player Direction
Win Rate
0.0
boration
toraton 2
Moration 3
Ioraton
noration
Aoratio
0.2
0.6
1.
1.4
Environment Frames (1.0e8)
Figure 6: Learning curves and discovered strategies by SIPO-WD in the 3vl scenario over 7 iterations. Strategies of seed are shown.
behavior by SIPO in the GRF 3v/ scenario seed can observe that agents have learned a wide spectrum of collaboration strategies across merely 7 iterations. The strategies discovered by SIPO are both diverse and human- inttannnnttrrrtaalee. such that they distract the defender and obtain a high win rate. The 2nd and the 6th iterations demonstrate an efficient pass-and-shoot strategy, where agents quickly elude the defender and score a goal. In the 3rd and the 7th iterations, agents learn smart "one-two" strategies to bypass the defender, a prevalent tactic employed by human football players. We note that NONE of the baselines have ever discovered this strategy across all runs, while SIPO is consistently able to derive such strategies for all random seeds. Visualization results in CA and corner scenarios can be found in App. B
the first iteration, all agents are involved in the attack
6.3 Ablation Study
We apply these changes to SIPO-WD:
Li Fixing the multiplicr A; instead of applying GDA.
Table 5: Number of distinct strategies in GRF discovered by different methods in terms of the ball-passing route. Details of the evaluation protocol be found in App. B.
Population Size M
ours
haselines
random
SIPO-RBE
DIPG
DvD
3v/ CA
3.0 (0.8)
3.0 (0.0)
(0.5)
1.3 (0.5)
(0.8)
2.0 (0.00.0)
2.7 (0.5)
(..5)
(.0.
(0.5)
(0.5)
2.0 (0.0)
1.7 (0.5)
corner
(0.5)
3.0 (0.8)
1.7 (0.5)
1.00).0)
1.6 (0.5)
2.0 (0.8)
(0.5)
(0.5)
Training DvD CA corner with M 10 requires >24GB GPU memory, which exceods memory limit.

---

CE: The intrinsic reward is replaced with cross-entropy, ie., (sh. an) log mr (ax, sn.). where Jj denotes previously discovered policy. Additionally, GDA is still applied.
filter: Optimizing the extrinsic rewards on trajectories that have intrinsic returns exceeding and optimizing intrinsic rewards defined by Eq. 2 for other trajectories
(74
PBT: Simultancously training M policies with M(M - 1)/2 constraints (i.e. directly solving Eq. with intrinsic rewards defined by Eq. 9 and GDA.
We report the number of visually distinct policies discovered by these
Table 6: # distinct strategies of ablations in GRF.
methods Table 6 Comparison be-
tween 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 exploit- ing duplicate actions, especially in the CA and corner scenarios with 11 agents. Besides, the fixed Lagrange coefficient, the filtering- method, and PBT are all detri- mental our algorithm. These methods also suffer from significant training instability. Overall, the state-distance-bart diversity measure, ITR, and GDA are all critical to the performance of SIPO.
fix-L
CE
filter
PBT
3v1
3.0 (0.0)
(0.0)
2.7 (0.5)
(0.5)
2.7 (0.5)
(0.8)
(0.00.
3.0 (0.8)
1.7 (.7)
1.00).
Not converged.
Training roquires 2-4GB memory and excceds our memory limit.
Conclusion
We tackle the problem of discovering diverse high-reward policies in RL. First, we demonstrate concrete failure cases of existing diversity measures and propose novel measure that explicitly compares the distance in state space. Next, we present thorough comparison between PBT and ITR and show that ITR much easier to optimize and can derive solutions with comparable quality to PBT. Motivated by these insights, we combine ITR with state- ciiee-dsstanee-aaa diversity measure to develop SIPO, which has provable convergence and can efficiently discover a wide spectrum of human-interpretable strategies in wide range of environments.
Limitations: First, we assume direct access to an object-centric state representation. When such representation is not available (e.g., image-based based observations), representation learning becomes necessary and algorithm performance can be affected by the quality of the learned representations. Second, because ITR requires sequential training, the wall clock time of SIPO can be longer than the PBT alternatives when fixing the total number of training samples. The acceleration of ITR remains an open challenge.
Future Directions: Besides addressing the above limitations, we suggest three additional future directions based on our paper. First, a consensus on the best algorithmic formulation of distinct solutions in RL remains elusive. It is imperative understand diversity in more theoretical manner. Second, while this paper focuses on single-agent and cooperative multi-agent domains, extending SIPO multi-agent competitive games holds great potential. Finally, although SIPO/ITR enables open-ended training. it is worth studying how to determine the optimal population size to better balance resources and the diversity of the resulting population.
Acknowledgement
This project is partially supported by 2030 Innovation Megaprojects of China (Programme on New Generation Artificial Intelligence) Grant No. 2021AAAA0100000,
References
[1] Martin Arjovsky, Soumith Chintala, and Léon Bottou. Wasserstein generative adversarial networks. Doina Precup and Yee Whye Teh, editors, Proceedings the 34th International Conference Machine Learning, volume 70 of Proceedings of Machine Leurning Research, pages 214-223, PMLR, 06-11 Aug 2017. URL, /tttps://proceeddnggs mlr, press//700 http://eedddaa........ree//////e
ar jojossky17a html
10

---

[2] Monica Babes, Enrique Munoz de Cote, and Michael L. Littman. Social reward shaping in the prisoner's 's dilemma. In Lin Padgham, David C. Parkes, Jörg P. Müller, and Simon Parsons, editors, 7th International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS 2008), Estoril, Portugal, May 12-16, 16, 2008, Volume 3, pages 1389-1392. IFAAMAS, 2008. URL WtRLhttps:///l acm. org/ ci ci tation. cfm21d=1402880
[3] 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 Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia. April 26-30, 2020. OpenReview.net, 2020. URL https::/oppnrreviee hett/foruunidd-Sxxxx.XBB..
[4] Mare Bellemare, Sriram Srinivasan, Georg Ostrovski, Tom Schaul, David Saxton, and Remi Munos. Unifying count-based exploration and intrinsic motivation. Advances in neural information processing systems, 29, 2016.
[5] Yura Burda and Harri Edwards, Oct 2018 URL
reinforcement- -eare-lngannnnniieeea wwth--idddtiiiioonn based rewards/
[6] Yuri Burda, Harrison Edwards, Amos Storkey, and Oleg Klimov. Exploration by random network distillation. arXiv preprint arXiv: 00.81002880. /2894, 2018.
[7] 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, Virtual Event, Austria, May 3-7, 2021. OpenReview.net, 2021. URL https::/ http:////pppppaooooooooooooooaoa MIMgoX
[8] Víctor 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 International Conference on Machine Learning, pages 1317-1327. PMLR, 2020.
[9] Rujikom Charakorn, Poramate Manoonpong, and Nat Dilokthanakul. Generating diverse cooperative agents by learning incompatible policies. In ICML 2022 Workshop for Agent- Based Modelling, 2022.
[10] Jack Clark and Dario Amodei, Dec 2016.
URL httpp:://ppenai.com
[11] Brandon Cui, Andrei Lupu, Samuel Sokota, Hengyuan Hu, David J Wu, and Jakob Nicolaus Foerster. Adversarial diversity hanabi. In The Eleventh International Conference on Learning Representations, 2023.
[12] Antoine Cully, Jeff Clune, Danesh Tarapore, and Jean- Baptiste Mouret. Robots that can adapt like animals. Nature, 521(7553):503-50)) May 2015. ISSN 0028-0836, 1476-4687. doi: 10. 1038/naturee14////// URL http://t:: nature. wtt.//rtticleee/aaarree.....
[13] 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, edi- tors, Genetic and Evolutionarr Computation Conference, GECCO 2010, Proceedings, Portland, Oregon, USA, July 7-11, 2010, pages 447-454. ACM, 2010. doi: 10.1 145/11830483.1835568. URL. htt.ttttt///.o...... org/ 10. 114.1.111111118811 1//////334433.3 1830068
[14] Fei Deng, Ingook Jang, and Sungjin Ahn. Dreamerpro: Reconstruction-Fie model-based reinforcement learning with prototypical representations. In Kamalika Chaudhuri. Stefanie Jegelka, Le Song, Csaba Szepesvári, Gang Niu, and Sivan Sabato, editors, International Conference on Machine Learning. ICML 2022, 17-23 July 2022, Baltimore, Maryland, USA. volume 162 of Proceedings of Machine Learning Research, pages 4956-4975. PMLR, 2022. mlr. www.srppees/eeeee v112/ deng22a. html
hRLhttts:: httttts::/ppocceediiii
[15] Sam Devlin and Daniel Kudenko. Theoretical considerations of potential-based reward shaping for multi-agent systems. In Liz Sonenberg, Peter Stone, Kagan Tumer, and Pinar Yolum, editors, 10th International Conference Autonomous Agents and Multiagent Systems (AAMAS 20/ I), Taipei, Taiwan, May 2-6, 2011, Volume 1-3, pages 232232. IFAAMAS, 2011. URI http' //portal. acm. org/ citatiin..tin.o 20000:000000000000F00C 100 BFT.TT/BEETEEEEEEE365333333

---

[16] Benjamin Eysenbach. Abhishek Gupta, Julian Ibarz, and Sergey Levine. Diversity is all you need: Learning skills without a reward function. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019.
URL. Stt.htttps:/openrvviee -et.:e/EEooummmm-SSS3333333.
[17] Wei Fu, Chao Yu, Zelai Xu, Jiaqi Yang. and Yi Wu. Revisiting some common prac- tices in cooperative multi-agent reinforcement learning. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato, editors, Proceedings of the 39th International Conference on Machine Learming, volume 162 of Proceedings of Machine Learning Research, pages 6863-6877 PMLR, 17-23 Jul 2022. URL https 7/ //proceedings. www.mm.....reeeeeeeeeeeeeeemleee wwwpppeesssvveeee wttpss//vv22fff2222 html
[18] Dibya Ghosh, Abhishek Gupta, and Sergey Levine. Learning actionable representations with goal conditioned policies. In 7th International Conference on Learning Reprexentations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019. URL https
[19] Agrim Gupta, Silvio Savarese, Surya Ganguli, and Li Fei-Fei. Embodied intelligence via learning and evolution. Nature communications, 12(1):1-12, 2021.
[20] Elad Hazan, Sham Kakade, Karan Singh, and Abby Van Soest. Provably efficient maximum entropy exploration. In International Conference on Machine Learning, pages 2681-2699 PMLR, 2019.
[21] Siyi Hu, Chuanlong Xie, Xiaodan Liang, and Xiaojun Chang. Policy diagnosis via measuring role diversity in cooperative multi-agen aagett RL. In Kamalika Chaudhuri. Stefanie Jegelka, Le Song, Csaba Szepesvári. Gang Niu, and Sivan Sabato, editors, International Conference on Machine Learning, ICML 2022, 17-23 July 2022, Baltimore, Maryland, USA, volume 162 of Proceedings Machine Learning Research, pages 9041-9071. PMLR, 2022. httpttttt::///ceeeeeeeee mlr. S.r.press/vve mansss/v662/hu2200 html
[22] Max Jaderberg, Valentin Dalibard, Simon Osindero, Wojciech M. Czarnecki, Jeff Donahue, Ali Razavi, Oriol Vinyals, Tim Green, lain Dunning, Karen Simonyan, Chrisantha Fernando, and Koray Kavukcuoglu. Population Based Training of Neural Networks, November 2017. URL arXiv: 111177111196666 [cs].
http://arxiv. abs/ wwtps//11...00 09846
[23] Max Jaderberg, Wojeiech M. Czamecki, lain Dunning. Luke Marris, Guy Lever, Antonio Garcia Castañeda, Charles Beattie, Neil C. Rabinowitz, Ari S. Morcos, Avraham Ruderman, Nicolas 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, 3641(443): 0036-8075, 1095-9203. doi: 10. 126/science.aau62449 URL. https:: /tt::://wwww.. http://www...ccc.ee. www.nce.eccc......c.... org/ doi/10. 1126/ science. aau6249
May 2019. ISSN
[24] Zheyuan Jiang, Jingyue Gao, and Jianyu Chen. Unsupervised skill discovery via recurrent skill training. Advances in Neural Information Processing Systems, 35:39034 -99046,, 2022.
[25] 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, Mare' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin, editors, Advances in Neural Information Processing Systems 33: Annual Con- ference on Neurul Information Processing Systems 2020, NeurIPS 2020, December 6- 12, 2020, virtual, 2020. URL https: httttpp:///proceeddnngg www..pp.cc.pppprr/////eee 22020/2222hhh/ Aww.::2a00ee-bbtttt........
[26] Karol Kurach, Anton Raichuk, Piotr Stanczyk, Michal Zajac, Olivier Bachem, Lasse Espeholt, Carlos Riquelme, Damien Vincent, Marcin Michalski, Olivier Bousquet, and Sylvain Gelly. Google research football: A novel reinforcement learning environment. In The Thurth-Fourth AAAI Conference on Artificial Intelligence, AAAI 2020, The Thirty-Second Innovative Ap- plications 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, AAAI Press, 2020.
2020, pages
URL https: h/t::://js.... aaai org/ index.nexx.i. php/
AAAI/ MAAIarriile/vvie wwt.e///vewwe/eeee /878
12

---

[27] Lisa Lee, Benjamin Eysenbach, Emilio Parisotto, Eric P. Xing, Sergey Levine, and Ruslan Salakhutdinov. Efficient exploration via state marginal matching. CoRR, abs/1906.05274, 2019.
http://t://aaxiiv.o org/ awtpaa/s..../////
[28] Yoonho Lee, Huaxiu Yao, and Chelsea Finn. Diversify and disambiguate: Learning from underspecified data. CoRR, abs/2202.03418, 2022. URL httphtt////aiiii.rrg.... wrwpw////2rrga//2222222222 03418
[29] Chenghao Li, Tonghan Wang, Chengjie Wu, Qianchuan Zhao, Jun Yang. and Chongjie Zhang. Celebrating diversity in shared multi-agent reinforeement learning. In Marc' Aurelio Ran- zato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan, editors, Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurlPS 2021, December 6-14, 2021, virtual. pages 3991 2021. URL ptttps::/ppoceedinng neurips cttpps.cc//aape cc/paper///cccccpcccccccccpc.ant 202//hash/ 00aae388f46643755579999655666. wwwp:/0000ooosstaaatooo Abstract.
[30] Jiwei Li, Will Monroe, Alan Ritter, Dan Jurafsky, Michel Galley, and Jianfeng Gao. Deep reinforcement learning for dialogue generation. In Jian Su, Xavier Carreras, and Kevin Duh, editors, Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing, EMNLP 2016, Austin, Texas, USA, November 1-4, 2016, pages 1192-1202. The Association for Computational Linguistics, 2016. doi: 10. (0.18653/11//1-- 1127. URL hhtpps
7/doi. 10. 1ww111/////1.---1/1 1127
[31] Tianyi Lin, Chi Jin, and Michael I. Jordan. On gradient descent ascent for nonconvex-concav 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 Research, pages 6083-6093 PMLR, 2020. UtL.pttp://rocceeinns mlr press/v119/ 1in20a. html
[32] Hao Liu and Pieter Abbeel. Behavior from the void: Unsupervised active pre-training. Advances in Neural Information Processing Systems, 34:18459-18844 2021.
[33] lou-Jen Liu, Unnat Jain, Raymond A. Yeh, and Alexander G. Schwing. Cooperative explo- ration for multi-agent deep reinforcement learning. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning. ICML 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pages 6826-6836. PMLR, 2021. URL http:::/ttooeeeeeeect
mlr. http://ccceaann.a...eeeeee/////s
.ttll
[34] Siqi Liu, Guy Lever, Josh Merel, Saran Tunyasuvunakool, Nicolas Heess, and Thore Graepel. Emergent coordination through competition. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA. USA, May 6-9, 2019. OpenReview.net, 2019. URI. httpppp://ppppeeeieeee....
[35] Siqi Liu, Guy Lever, Zhe Wang, Josh Merel, S. M. Ali Eslami, Daniel Hennes, Wojciech M. Czarnecki, Yuval Tassa, Shayegan Omidshafiei, Abbas Abdolmaleki, Noah Y. Siegel, Leonard Hasenclever, Luke Marris, Saran Tunyasuvunakool, H. Francis Song, Markus Wulfmeier, Paul Muller, Tuomas Haarnoja, Brendan D. Tracey, Karl Tuyls, Thore Graepel, and Nicolas Heess. From motor control to team play in simulated humanoid football. Sci. Robotics, 7(69), 2022. doi: 10. (0.11///ciirbooics.aboollo
URL https: //doi org/10. 1126/scirobotics abt.bbttiiisaa.00333
[36] 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 Mare' Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan, editors, Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NewrIPS 2021, December 14, 2021, virtual, pages 941-952, 2021. htR.shttss::// httpttpss:///roceeddggg/ cc/paper///eeeeeeecceeceeeeee 2021 http//222hhhhhh// httpa//aee///////aaaaaaaaaaaaaaa htt.:/5000..---bbaart....t..
Saraaggs.nuriii neur ips
[37] Qian Long, Zihan Zhou, Abhinav Gupta, Fei Fang, Yi Wu, and Xiaolong Wang. Evolution- ary population curriculum for scaling multi-agent reinforcement learning. In International Conference Learning Representations, 2020.
13

---

[38] Andrei Lupu, Hengyuan Hu, and Jakob N. Foerster. Trajectory diversity for zero-shot co- ordination. In Frank Dignum, Alessio Lomuscio, Ulle Endriss, and Ann Nowé, editors. AAMAS '21: 20th International Conference Autonomous Agents and Multiagent Sys- tems, Virtual Event, United Kingdom, May 3-7, 2021, pages 1593-1595. ACM, 2021. doi: 015555/343395.334441777 URLhttps:///// ifaamas org/ org/ Pww.eeeeineee/////ee /roceeddag///mmma22221 a00ps//21/ pdfs/p1593. pdf
[39] Pingchuan Ma, Tao Du and Wojeiech 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 of Machine Learning Research, pages 6522-6533 6531. PMLR, 2020.
.ml.....mm...................... mlr mar.ppree press/v119/
ma20a. html
[40]
Tengyu Ma. Why Do Local Methods Solve Nonconvex Problems?, March 2021. URLhttp / //arxivv wlaaxii.ogg/abaee.......eoa.a..e https//orrgabb//113.333 2103. 13462 arXiv:2103. [cs, math, stat].
[41] Marlos C. Machado, Marc G. Bellemare, and Michael Bowling.
Count-based exploration with the successor representation. In The Thirty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2020, The Shcroy 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, pages 5125-5133, AAAI Press, 2020. URL https:://jss..... aaai org/ wingg.iix.../ php/ AAAI/ TAATTaarticle/vie//5555
[42] Viktor Makoviychuk, Lukasz Wawrzyniak, Yunrong Guo, Michelle Lu, Kier Storey, Miles Macklin, David Hoeller, Nikita Rudin, Arthur Allshire, Ankur Handa, and Gavriel State. Isaac gym: High performance gpu-based physics simulation for robot learning, 2021.
[43] Muhammad A. Masood and Finale Delei-Velez. Diversity-inducing policy gradient: Using maximum mean discrepancy to find a set of diverse policies. In Sarit Kraus, editor, Proceedings of the Ewenty-Eighth International Joint Conference on Artificial Intelligence, IJCAI 2019, Macao, China, August 10-16, 2019, pages 5923-5929. ijcai.org. 2019. doi: 10.24963/ijcai. 2019/821. URL wttttt::///ooi org/ 24903/2963//2 jeai. 2019/8211 821
[44] B.L. Miller and M.J. Shaw. Genetic algorithms with dynamic niche sharing for multimodal function optimization. In Proceedings of IEEE International Conference Evolutionary Computation, pages 786-791, Nagoya, Japan. 1996. IEEE. ISBN 978 777-0078033-2902-1 doi: 10.1109//CEE.11965577777 URL http:tttt/eeeepp.oooo/ ieee, wrg.eee.rgeeeeeeeeeeeeee wtt//oooo///oooooooo www.ddooonennnnnnoooeeeee
[45] Jean-Baptiste Mouret and Jeff Clune. Illuminating search spaces by mapping clites. CoRR, abs/1504.04909, 2015. URL URL http:/tttt///..ott/ttt org/ abs/ 11/// 04909
[46] Andrew Y Ng, Daishi Harada, and Stuart Russell. Policy invariance under reward transfor- mations: Theory and application to reward shaping. In Ieml, volume 99, pages 278-287, 1999.
[47] Olle Nilsson and Antoine Cully. Policy gradient assisted MAP-Elites. In Proceedings of the Genetic and Evolutionary Computation Conference, pages 866 875, Lille France, June 2021. ACM. ISBN 978- 1 1145/3449639 344963949999999 3459304
doi: 10. 10.114553344933933553004 URL https://tt acm
org/ 1145
[48] Shayegan Omidshafiei, Karl Tuyls, Wojciech 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.
[49] Takayuki Osa, Voot Tangkaratt, and Masashi Sugiyama. Discovering diverse solutions in deep reinforcement learning by maximizing state-action-basse mutual information. Neural Nenworks, 152:90- 104, 2022. doi:
04.00. https:/s:://dtt .rg. /0rg/11..0 1016/]
neunet. 2022. 009
[50] Aldo Pacchiano, Jack Parker-Holder, Yunhao Tang, Krzysztof Choromanski, Anna Choro- manska, and Michael Jordan. Learning to score behaviors for guided policy optimization. In International Conference Machine Learning, pages 7445-7454. PMLR, 2020.
14

---

[51] 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, Marc' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin, editors, Advances in Neural Informa- fion Processing Systems 33: Anmual Conference on Neural Information Processing Systems 2020, neurips
NeurlPS 2020, December 12, 2020, virtual, 2020. / www.:ubtbebbttttt..t... html
[52] Jack Parker-Holder, Aldo Pacchiano, Krzysztof Marcin Choromanski, and Stephen J. Roberts. Effective diversity in population based reinforcement learning. In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin, editors. Advances in Neural Information Processing Systems 33: Annual Con- ference Neural Information Processing Systems 2020, NeurIPS 2020, December 6-
12, 2020, virtual, 2020. URL pttpp::/prroceedings. hww.ooceeddnngnneeiiiiseeeeeeeee neurips. htlppaaprr/2////aaae #10G588270a6f9394188884 www.:/4077000000fff0moo wwwfo/00ooobssttaatttttt.. Abstract..tttt......aa
[53] Alexander Peysakhovich and Adam Lerer. Consequentialisst conditional cooperation in social dilemmas with imperfect information. In 6th International Conference on Learning Representa- tions, ICLR 2018, Vancouver, BC, Canada, April 30 May 3, 2018, Conference Track Proceed- ings. OpenReview.net, 2018. URL http:tttss://eereeiiii www.eeewwweeeeeeeeeeeeeeeeeeeeee http:/orrunniidiBaii.ieee
[54] Thomas Pierrot, Valentin Macé, Félix Chalumeau, Arthur Flajolet, Geoffrey Cideron, Karim Beguir, Antoine Cully, Olivier Sigaud, and Nicolas Perrin-Gilbert. Diversity Policy Gradient for Sample Efficient -iivertti Optimization. In Proceedings of the Genetic and Evolutionary Computation Conference, pages 1075-1083, July 2022. doi: 10.1145/3512290. 3528845. URL http://arxiv wwt.aaawwv...gggb...ar a00/aaa../002022 2006 08505 arXiv:2006.08500 [cs].
[55] 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.3389/frob..206..00o 000400 URL
org/ www.rrrg//rrrrrr.r.eoe 3389/
Frobt.2015 00040/ abw.aaabbbtraac.c.oomm
[56] Tim Roughgarden, editor. Beyond the Worst-Case Analysis of Algorithms. Cambridge University Press, 2020. ISBN 9781 108637435. doi: 10.1017797781108677733 URL ftttps:///// org/ 10. 10.1017/9981108637453
[57] Mikayel Samvelyan, Tabish Rashid, Christian Schröder de Witt, Gregory Farquhar, Nantas Nardelli, Tim G. Rudner, Chia-Man Hung, Philip H. S. Torr, Jakob N. Foerster, and Shi- mon Whiteson. The starcraft multi-agent challenge. In Edith Elkind, Manuela Veloso, Noa Agmon, and Matthew E. Taylor, editors, Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems, AAMAS '19, Montreal, QC, Canada, May 13-17, 2019, pages 2186-2188 International Foundation for Autonomous Agents and Multiagent Systems, 2019. URL http://t:/// aww. pntrg/citatiio.com wtt.::o:oon.mmmmdmd33333303
[58] Harshinder Singh, Neeraj Misra, Vladimir Hnizdo, Adam Fedorowicz, and Eugene Demchuk. Nearest neighbor estimates of entropy. American jouraal of mathematical and management sciences, 23(3-4):301-311 2003.
[59] Matthijs TJ Spaan. Partially observable markov decision processes. In Reinforcement Learning, pages 387-414. Springer, 2012.
[60] Hao Sun, Zhenghao Peng, Bo Dai, Jian Guo, Dahua Lin, and Bolei Zhou. Novel policy seeking with constrained optimization. arXiv preprint S0t.:::0005.0066 2020.
[61] 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 randomization. In 9th International Conference Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OpenReview.net, 2021. URL httpppttp///ppeeeeiiie net/forum? i 10RC6669TT
[62] Luca Venturi, Afonso S. Bandeira, and Joan Bruna. Neural networks with finite intrinsic dimension have no spurious valleys. CoRR, abss/1822,0684, 2018. htRp:/ttt://arrtt org/ abs/1802. 2es/1802.06384
15

---

[63]
Cédric Villani. Optimal transport: old and new, volume 338. Springer, 2009.
[64]
Oriol Vinyals, Igor Babuschkin, Wojciech M. Czarnecki, Michaël Mathieu, Andrew Dudzik, Junyoung Chung, David H. Choi, Richard Powell, Timo Ewalds, Petko Georgiev, Junhyuk Oh, Dan Horgan, Manuel Kroiss, Ivo Danihelka, Aja Huang, Laurent Sifre, Trevor Cai, John P. Agapiou, Max Jaderberg. Alexander S. Vezhnevets, Rémi Leblond, Tobias Pohlen, Valentin Dal- ibard, 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)3350-33333 s41586-019- 172222 URL httpttt::/ /www nature com www.///atcclee/eeeeaeeeee...
November 2019. ISSN 0028-0836 1476-4687. doi: 10. 1031088/ 019- -17-1-111666-0111-72-
[65] 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, pages 142-151, 2019.
[66] Tonghan Wang, Tarun Gupta, Anuj Mahajan, Bei Peng, Shimon Whiteson, and Chongjie Zhang. RODE: learning roles decompose multi-agent tasks. In 9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OpenReview.net, 2021. URL httthhtt:///// hattps::/openreviieee net/ tetf/forum?(<--TUWgork..
[67] Shuang Wu, Jian Yao, Haobo Fu, Ye Tian, Chao Qian, Yaodong Yang, QIANG FU, and Yang Wei. Quality- diversity via population based reinforcement learning. In The Eleventh International Conference on Learning Representations, 2023.
[68] 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 //openreview
[69] 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:2 2021.
[70] Tom Zahavy, Brendan O' O'Donoghue, Andre Barreto, Volodymyr Mnih, Sebastian Flennerhag, and Satinder Singh. Discovering diverse nearly optimal policies with successor features. arXiv preprint arXiv:2106. 200.022000.00669, 2021.
[71] Tom Zahavy, Yannick Schroecker, Feryal M. P. Behbahani, Kate Baumli, Sebastian Flennerhag, Shaobo Hou, and Satinder Singh. Discovering policies with domino: Diversity optimization maintaining near optimality. CoRR, abs/2205. 2022. doi: 10.48550/axiv22205.1333 133522
URL https://doii
10. http//10..55////11/////// 2205 13521
[72] Yunbo Zhang, Wenhao Yu, and Greg Turk. Learning novel policies for tasks. In International Conference on Machine Learning, pages 7483-7492. PMLR, 2019.
[73] Rui Zhao, Jinming Song, Hu Haifeng, Yang Gao, Yi Wu, Zhongqian Sun, and Yang Wei. Maximum entropy population based training for zero-shot human-ai coordination. arXiv preprint arXiv:21 2021.
[74] 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
16

---

A
Project Website
Check
for GIF demonstrations.
Additional Results
B.1 More Qualitative Results
Attacker
Defender
Ball Direction
Direction
Figure 7: Visualization of learned behaviors GRF CA across single training trial.
1.0
iteration,
iteration
iteration 3
iteration 4
Win Rate
0.0
n
Environment
Framés (1.0e10)
Attacker
Defender
Waiting
Ball Direction
Player Direction
Figure 8: Visualization of learned behaviors in GRF corner.
We show additional visualization results in Fig. Fig and Fig can be found on our project website.
Corresponding GIF visualizations
B.2 Task Performance Evaluation
The evaluation win rates of the demonstrated visualization results in SMAC and GRF are shown in Table g Evaluated episode returns in Humamoid are shown in Table
We also present the diversity score and average rewards achieved by baselines in Table 10 These numerical values are averaged across the entire population for a clear comparison. The tabulated data highlights the varying trade-offs between task performance and diversity exhibited by different

---

Table k-nearest neighbor state entropy estimation in GRF. Population size M 4.
DaTS
haselines
SIPO-RBF
SIPO-WD
DIPG
SMERL
DvD
RSPO
PG (random seeding)
0.009)0.000)
0.012(0.000)
0.010(0.001)
(0.002)
0.010(0.000)
(0.01() 0.034(0.001)
0.009(0.001)
CA
0.037(0.000)
(.036(0
0.036(0.002)
0.039(0.001)
Comee
0.028(0.001)
0.031(0.001)
0.030(0.002)
0.028(0.902)
'The learned policy in iterations cannot even collect single winning trajectory, compute their diversity score.
unable
Training DvD CA and corner requires >24GB GPU memory, which exceeds our memory limit.
algorithms. It noteworthy that SIPO, in particular, displays an adeptness at training a notably more diverse population while upholding reasonably moderate level of task performance.
Table 8: Evaluation win rate (%) of the demonstrated visualization results in SMAC and GRE
SMAC
GRF
2mlz
2c642g
3vl
CA
comer
T1
100.0(0.0)
98.1(2.1)
92.3(6.2)
48.2(10.4)
78.2(16.2)
772
99.6(0.9)
100.0(0.0)
82.1(8.4)
43.8(42.2)
57.0(37.7)
73
100.0(0.0)
96.9(3.3)
90.7(1.1)
54.7(30.6)
55.7(20.8) 17.2(30.0)
Wa
99.6(0.6)
98.6(2.4)
63.6(45.0)
30.7(29.0)
75
85.4(9.1)
76
93.2(1.9)
77
64.6(32.5)
B.3
Evaluation Metric and Protocol for Diversity
B.3.1
Humanoid
The Humanoid locomotion task is well-studied in the Quality-Diversin (QD) community, enabling the application of well-defined behavior descriptors (BD) to assess diversity scores. While domain- agnostic metrics like DvD scores also be applied, consider domain-specine BDs to be more appropriate and accurate for evaluation in this setting.
B.3.2 SMAC
Complex multi-agent tasks like SMAC lack well-defined BDs. Hence, domain-agnostic diversity measures such the state-entropy measure should be applied. Moreover, different SMAC winning strategies tend to visit different areas the map. which can be usually captured by the state-entropy measure.
Iteration 1
lleration
Iteration
Iteration
Figure 9: Visualization of learned behaviors in Humanoid.
18

---

Table Episode returns in Humanoid.
SIPO-RBF
SIPO-WD
SIPO-WD (visual)
4863.9(970.3)
3909.4(533.4)
4761.3(107.8)
3746.5(488.0)
3784.2(481.2)
4349.3(169.0)
R3
3092.0(805.0)
3770.4(674.4)
4724.3(946.5)
2332.8(519.8)
3589.6(387.4)
3819.7(588.77
Table 10: Reward/diversity of all baselines. The reward metric in SMAC and GRF are evaluation win rate (%). The evaluation metrics of diversity used in humanoid, SMAC, GRF are the joint torque distance, state entropy (1e-3), and the number of different ball-passing routes, respectively. It is noteworthy that SIPO, in particular, displays adeptness at training notably more diverse population while upholding reasonably moderate level of task performance.
Task/Scenario
SIPO-RBF
SIPO-WD
DIPG
RSPO
SMERL.
DvD
PPO
humanoid
3508 0.53
3.63/0.71
5191 /0.12
0.55/0.53
4253 0.001
4498
5299 /-
SMAC 2m12
100/
100/36
100/ 32
100/
100/28
100 30
100/
SMAC 2064zy
72
GRP 3vl (first 4)
93.
82/33.0
93/2.7
9.
91/1.3
83/3.00
9.7
GRF CA
7.3333
41/3.0
46/2.3
7./200
4.
5.7
GRF Corerr
72/2.7
$6/3.00
7.7
2./1.6
6.0
71/2.0
B.3.3 GRF
In our initial study of the GRF task, diversity was evaluated using the d-nearest-neighhor state entropy estimation as in SMAC (see Table However, we observed significant difference between the computed scores and visualized behaviors. Further investigation revealed that state entropy can sometimes report fake diversity GRF For example, the ball-moving route highly fine-grained between nearby players in the counter-attack (CA) scenario, and additional passes may not change the state entropy significantly. Instead, agents' positions play a crucial role in this scenario, where different shooting positions can introduce substantial state variance and lead to higher entropy score. As an example, readers can refer to the replays of SIPO-RBBF (4 iterations of seed 2) and PG (seed 1002, 2002, and 3002), where SIPO-RBF discovers four distinet passing strategies, while PG keeps passing the ball to the same player. Nevertheless, the state entropy of PG (0.0397) higher than that of SIPO-RBF (0.0378).
Hence, we counted the number of distinct policies according to their ball-passing routes, such as passing the ball to different players or shooting with different players, to evaluate diversity in GRF. To quantify these differences, we extracted the positions of the ball and the players in the field and calculated the nearest ally player ID to the ball across winning episode. We then removed timesteps where the nearest distance was above a pre-defined threshold of 0.03. Typically, these timesteps correspond to instances when the ball is being transferred among players, making the nearest player ID irrelevant. Next, we removed consecutive duplicate player IDs from the resulting sequence to obtain a concise and informative embedding of the ball passing route. By comparing the lengths of their respective embeddings and verifying that the player IDs in each embedding are identical, we determined whether the two policies exhibit similar behavior.
acknowledge that existing diversity measures may not be applicable GRF, and hence we opted for this novel approach to evaluate diversity. Additionally, experimented with using raw observations, which include ball ownership information provided by the game engine, but found it to be highly inaccurate based on visualization.
B.4
Additional Ablation Studies
B.4.1 Input the Diversity Measure
Vectorized States in Google Research Football We perform additional ablation study over the input of our diversity measure GRF 3v/ scenario with SIPO-WD. We consider the following kinds of state input besides the default state input adopted in Sec. 6
19

---

full observation (named full, 115 dims);
default state input with random noises of the same dimension (named random, 36 dims).
The numbers of visually distinct strategies are listed in Table [1] The performance full and random is similarly good. The result implies that the learnable discriminator can automatically filter out irrelevant states to some extent, and that STPO-WD performs relatively robust w.r.t. different state input of the diversity measure.
Table 11: State input ablation. The table shows the number of distinct strategies in GRF 3v1.
SIPO-WD
full
random
3v1 3.0 (0.0) 3.0 (0.8) 3.0 (0.0)
RGB Images in Locomotion Tasks We run SIPO-WD in the visual Humanoid task based on Isaac Gym [4]]. The training protocol is similar to the state-only version (i.e., the input of policy and intrinsic rewards are both locomotion states of the Humanoid) except that we stack recent 4 RGB camera observations (84 x 84) as the input of intrinsic rewards in Eq. 9 We adopt the training code developed in Isaac Gym and the default PPO configuration. The backbone of the discriminator is composed of convolutional layers with kernel size 3, stride 2, padding I, and [16, 32, 32, 32] channels. Then the feature is passed activation function is leaky ReLU with slope 0.2. We also compute the pairwise distance of joint shown in
MLP with hidden layer and 256 hidden units. The
torques in the state-only version and show the result in Table 12 Visualizations Fig. I0 SIPO-WT WD can also learn meaningful diverse behaviors with RGB images as the state input thanks to the learnable Wasserstein discriminator. This implies that our algorithm can be naturally extended to high-dimensional states and incorporated with advances in representation learning, which may be potential future direction.
B.4.2 Combining State- and Action-based Diversity Measures
Based on SIPO-RBE, we introduce additional action information by directly concatenating the global state, used for diversity calculation, with the one-hot encoded actions of all agents within the GRF domain. Table 13 presents the outcomes, indicating the number of policies obtained. For scenarios with limited number of agents, the action-urd action-augmenne augmented variant demonstrates comparable performance. However, when the agent count increases (as evident in the ll-aeent cases of CA and corner), the incorporation of actions can introduce misleading diversity, detracting from the authenticity of the outcomes.
B.5 How to Adjust Constraint- -enstreint-Relatedd Hyperparameters
Three hyperparameters are essential in the implementation of the intrinsic reward Fin the threshold 5. the intrinsic reward scale factor a, and the variance factor a in rRR These parameters differ under different domains and must be adjusted individually. We find proper parameters by running two
(a) normal running
(b) left-leg jumping
(c) right-leg jumping
(d) hand-balanced mincing
Figure 10: Results of SIPO-WD in the visual Humanoid task.
20

---

Table 12: Pairwise distance of joint torques (i.e., diversity score) in Humanoid with visual input. Results in visual experiments are averaged over seeds.
SIPO-WD HIPO-WDONE (visual) SIPO-WD WD
RSPO (best baseline)
0.62 (0.26)
0.71 (0.23)
0.53 (0.05)
3v1
CA
Corner
SIPO-RBF SIPO-RBF w. Action
(0.8)
3.3 (0.5)
2.7 (0.5)
3.0 (0.0)
2.3 (0.5)
1.0 (0.0)
Table 13: Ablation study of combining state- and -action-based diversity measures. The number of
different strategies across population of 4 is shown with standard deviation in the brackets.
iterations without constraints and get two similar policies To and πΙ We record Tim during training Ti and the trend is shown in Fig. 11 Not surprisingly, Timi gradually decreases as training proceeds.
Threshold We set ā = Ds(mo, m1). We try several different E 1.2, 1.4, 1.6, 1.8, 2.0} and find that C1 = 1.2 or 1.4 are universal proper solutions for all the experimental environments.
Intrinsic Scale Factor We need to balance the intrinsic reward Tine and the original reward so that neither of the two rewards can dominate the training process. Empirically, the maximums of the two rewards should be in the same order of magnitude. i.e., max, (JT) (T) = X C2Amazō, where C2 = -(1). When C2 too large, the new-trained policy тy will oscillate near the boundary of D(T,, TT) for some pre-trained policy P.. Conversely, when C2 is too small, the intrinsic reward Tint cannot yield diverse strategies. In experiments, we set 02 1.0.
Variance Factor We sweep the variance factor across {le - 3, 5e - 3, le - 2, - 2, le - 33 by training 1 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 x² = 0.02.
The 8 and of GRF and SMAC are listed in Table 14
B.6 Computation of Action-Basse Measures in the World Example
We consider the policies illustrated in Fig. [2 These policies are all optimal since these actions only include "right" and "down" and actions on non-visited states can be arbitrary. We only mark actions on states visited by any these 3 policies and actions on other states can be considered the same.
B.6.1 Action-Distributiinn-Ba Measures
Action-listribution--eeed diversity measures can be defined
DA(Ti, Ty) = Bawg(s)
(
(mx(- ()]lT(( {))]
(10)
where D(..)) : > IR is measure over action distributions and q ASS) is a state distribution. Here, consider to be the joint state distribution visited by ı, and Tz-
Average
Table 14: The values of 5 and a in different environments.
football
smac
0036
3v1
corner
CA
2m vz_lz
2c 642g
FWD WD 1
0.004
0.01
0.012
0.02
0.2
0528
1
0.5
0.5
0.05
GRAF 0.03
0.01
0.015
0.002
0.001
a
RBF 0.001
0.001
0.001
0.001
0.001
Figure 11: Average intrinsic re- ward during training
0.02
0.02
0.02
0.02
0.02
21

---

KL Divergence KL divergence is defined by
Ti(a 8) Tyy (a 8)
DKL (Tx(- (os(-15))) 5), sT (-(-- s)) = (a 8) log
da.
When (a 8) 0 at any state 8, KL divergence is +oc. Since the trajectories of these policies have disjoint states, D (TI, D (T1, T3) too. Similar results can be obtained for cross-entropy.
JSD,, JSD,, was defined in 33 and we consider two special cases when = 0 and = 1.
As illustrated by 38 JSDo measures the expected number of times policies will "disagree" by selecting different actions. On trajectories induced by ти and TT, there are 4 + 4 states that л disagrees with T22 (T1 and are symmetric) and D (T1, π2) = 8/16 16 = 1/2. Similarly, л1 and ns only disagree at the initial state, therefore we have D (TI, TT) 2/16 1/8.
JSD₁ is defined by
(T,) + Iy (T()T)
JSD (T4,, Ty) =
2 P(T.
Σ 72
n.)
log
T
2T. (T:)
T
(Ty) + (T(TT)
Σ
P(T m.)
log
T
2T,
[=1
Since each of the policies considered only induces single trajectory and m. (T(T)) = (i + j), we can easily compute
ISD1 (11 T2) = D (TI, Ta) = log
Wasserstein distance Earth Moving Distance (EMD) is if two policies disagree state and 0 otherwise. Therefore, it equals 1
Wasserstein Distance
B.6.2 Action Norm
We embed the action "right" as vector [1, 0] since it increases the x-coordinate by and the action "down" as vector [0, -1] since decreases the y-coordinate by This embedding can be naturally extended to a continuous action space with velocity actions. Following [52). we compute the action norm over a uniform distribution on states. We can see that there are states where क and na perform differently and 1 state (the initial state) where and perform differently. Therefore, we can get D(T1, T2) = /7 and D( Rz) 1.
B.6.3 State-Distance-
Measures
State L2 Norm Similar to action L2 norm, we concatenate the coordinates instead of actions as the embedding and compute the T.2 norm between embedding.
4
T
T2
π3
Figure 12: Policies in the grid- worldwoldd example when Ng 5.
22

---

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 C. Then we solve the following linear programming
min Σ10c
s.t. 71 = 0, 7 7 =
76 2 0
where @) means element-wise multiplication, 1 is a all-one vector, [1",0") and b = [0", 177T the marginal state distribution of each policy.
C Environment Details
C.1 Details of the 2D Navigation Environment
The navigation environment has an agent circle with size a and 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 + 2(a + such that the final-state constraint is valid. An episode ends if the agent touches any landmarks, i.c., the distance between the center of the agent and the center of the landmark d < a b, or 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 1 It + At v. The reward is 1 if the agent touches the landmark and 0 otherwise.
C.2 Details of Environments
We provide training configurations and environment introductions below and refer readers to our project website in App. A for visualizations of these environments.
Humanoid We use the Humanoid environment in IsaaeGym 42 with default observation and
action spaces. The input of intrinsic rewards or diversity measure is the observation without all torque states.
SMAC We adopt the SMAC environment in the MAPPO codebase with the same configuration Yu al. [69] The input of intrinsic rewards diversity measure is the state of all allies, including positions, health, etc.
On the "easy" map 2m_vv_ /z, two marines must be controlled to defeat Zealot. The marines can attack from a distance, while the Zealot's s attacks are limited to close range. A successful strategy involves alternating the marines' attacks to distract the Zealot. On the "hard" map 2c_ vs 642g, two colossi must be controlled by the agents to fight against 64 zergs. The colossi have a wider attack range and can move corners, or dividing and conquering enemies. The level of difficulty is determined by the learning performance of existing MARL algorithms. Harder maps require more exploration and training steps.
cliffs. Strategies on this map may include hit-and-run tacties, waiting in
We adopt the "simplel 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. All policies are trained to control the left team to score against built-in bots.
GRF
academy_3. 33_v__________________________ __with_keeper In this scenario, team of three players (left) tries score goal against a single defender and goalkeeper. The left team starts with the ball and has to dribble past the defender and the goalkeeper score a goal.
23

---

Table 15: Hyperparameters the 2D navigation environment.
discount
GAF
PPO epochs
clip parameter
entropy honus
Amaa
actor
critic Ir
Lagrange
batch size
0.997
0,95
10
0.2
10
3o-4
le-3
0.5
4000
Table 16: Common hyperparameters for SIPO, baselines, and ablations.
discount
GAE A
critic
clip parameter
entropy bonus
GRF batch size
SMAC batch
0.99
0.95
5e-4
le-3
0.2
0.01
9600
3200
academy ucademyyccunterattieee _ownteraatack_eeeee _aayy In this scenario, the left team starts with the ball the front yard and tries to score goal against several defenders. All eleven players the left players be controlled. srudemyy_ornee In this scenario, the left team tries to score a goal from a corner kick. The right team defends the goal and tries to prevent the left team from scoring. All eleven players in the left players can be controlled.
D
Implementation Details
D.1 2D Navigation
We apply PPO with Lagrange multipliers to optimize the policy and hyperparameters are summarized Table 15 ((a,, Tyy is simply taken the I.2 distance the final state reached by m, and wj, i.e.,
(TT,, my) || HH 1|2. The applied algorithm the same SIPO (see Appendix G except that the intrinsic reward is only computed at the last timestep.
D.2 SIPO
In the i-th iteration (1 i M), 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. We include all practical tricks mentioned in (69 because we find them all critical to algorithm performance. We use separate actor and critic networks, both with hidden size and GRU layer with hidden size 64. The common hyperparameters for SIPO, baselines, and ablations are listed in Table Other environment-specinn parameters, such as PPO epochs and mini-br batch size, are all the same as 669. Besides, Table 14 and Table TableI7lise lists some extra hyperparameters for SIPO.
D.3 Baselines
We re-implement all baselines with PPO based on the MАPPO 69 project. All algorithmss run for the same number of environment frames. Specific hyperparameters for baselines can be found in Appendix D.3
SMERL SMERL trains a latent-conditioned policy that robustly adapt new scenarios. promotes diversity by maximizing the mutual information between states and the latent variable. We implement SMERL with PPO, where the actor and the critic take the input the concatenation of observation and one-hot latent variable. The discriminator is a 2-layer feed-forward network with 64 hidden units. The learning rate of the diseriminator 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
Table 17: SIPO hyperparametens across all environments.
Amax
Discriminator Ir
Lagrangian Ir
10
4.0e-4
0.1

---

single iitent-conditionas policy, we train SMERL for M x more environment steps, such that total environment frames are the same. The scaling factor of intrinsic rewards 0.1 and the threshold for diversification is [0.81, 0.45, 0.72] (0.9 x [0.9, 0.5, 0.8) for "3v1", "counterattack", and "comner" respectively.
DvD DvD simultaneously trains a population of policies to maximize the determinant of a kernel matrix based on action difference. 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 embedding. We also use the same Bayesian bandits as proposed the original paper. Training DvD in "counterattack" and "corner" exceeds the GPU memory and we exclude the results in the main body.
DIPG DIPG iteratively maximizes the maximum mean discrepancy (MMD) distance between the state distribution of the current policy and previously discovered policies. For DIPG, we follow the open-source implementatior We set the same variance factor in the RBF kernel as SIPO-RBF and apply the same state as the input of the 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 use the same method to save archived trajectories as SIPO and the input of the RBF kernel is the same as for SIPO-RBF. To improve training efficiency, only back-propagate the MMD) loss at the first PPO epoch.
the input
RSPO RSPO iteratively discovers diverse policies by optimizing extrinsic rewards novel tra- jectories while optimizing diversity on other trajectories. The diversity measure is defined as the action-cross entropy along the trajectory. For RSPO, follow the opensource implementation" and use the same hyperparameters on the SMAC 2c_vs__d_____________________2 v__62zg map in the original paper for GRF experiments.
TrajDi TrajDi was originally designed for cooperative multi-agent domains to facilitate zero- shot coordination. It defines a generalized Jensen-Shanon divergence objective between policy action distributions. Then this objective and rewards are simultaneously optimized via population- based training. We tried TrajDi in SMAC and GRF. 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.001]. However, 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.
Domino We have meticulously re-implemented Domino within our codebase according to the appendix of Zahavy et al. [7]] We execute the algorithm in the Humanoid locomotion task, employing the robot state (excluding torques) for successor feature computation. Despite our carnest efforts to optimize Domino's 's performance. our findings reveal its comparable performance to SMERL, illustrated by minimal diversity score of 0.01. Therefore, we exclude the performance of Domino in the main body.
APT APT maximized the nearest neighbor state-entropy estimation for skill discovery. While we also adopted this metric for diversity evaluation, there is fundamental distinction in formulation. APT optimizes state entropy within single policy, whereas our method, SIPO, targets the joint entropy of population of policies. is okay for each single policy within the population to have low state entropy. To employ APT's objective of discovering diverse policies, training a population of agents concurrently is required. The algorithm should optimize the estimated entropy over states visited by all policies. Yet, this approach mandates large-scale k-NN computation (k=12) over substantial batches, leading to significant computational inefficiency. Despite our dedicated efforts, we didn't finish a single training trial APT within 48 hours (in contrast to other PBT baselines, e.g. DvD, which completes training in less than 8 hours).
D.4 Ablation Study Details
For the three ablation studies: fix-L, CE, and filter, we list the specific hyperparameters here:
httpp://ggthab...cwwaaaa//pppppp
25

---

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/ 1010 that in the WD
setting:
filter:
all the hyperparameters in the setting are the same as those in the WD setting.
Proofs
E.1 Proof of theorem 4.1
Theorem 4.1
Assume D is a distance metric. Denote the optimal value of Problem 3 as Ti. Let
T2 = -- J(t)) where
#: arg max J(Ti)
S.t. az)
V1 Visj<s
for I...., M, then T2 2 Tí.
Proof. Suppose the optimal solution of Problem 3 is Tı, T2, ... TM satisfying J(T1) 2 [(T22
(TT)) and the optimal solution of Problem i Tl 52 ... TM satisfying J( 2 J (T2)
2 M
Assume the contrary that Thm. 4.1 Then we choose the smallest number N I M that satisfies
is not true, which means Σ ((T)) = Ti > T2 = Σ J(t.).
Σ J(TT)
((T.).
By T2 we know that exists. In addition, because Problem 6 solves unconstrained the first iteration, we know that #1 = arg max, (T) and then J(ri) I J(Fi). Therefore, N 2 2.
Suppose J(TN)= S J(#N). Then we have
N Σ J(T) > Σ ((.))
N-1
Contradicting the fact that N is the smallest number satisfies that equation.
Hence, we know that J(TN) > J(NN). Then
((m) 2 J( 2 J(TN) > J(HN).
Consider the optimization problem of nx:
n arg max ((T)
s.t. D( n3)) 2 5/2, Višj<N
This optimization does not find { n but find #N. which means that for each ,,, <iis N, there exists S ji < N such that D(T,, ). 8/2. Otherwise, will get the solution of the above problem as π; instead of WN-.
By the Pigeonhole Principle, know that there exist two indexes i E [N] and is [N] (4 # iz) such that j,, f:2 j. Then we have
D( m22) D(T,; Rg)) + (TT1,) #3) < 6 = 5,
where the inequality follows by the triangle inequality of the distance function.
It contradict with the fact that D(T;, Ti,)) 2 in Problem 3
Therefore, prove the theorem ΣM (( Ti Th EM
26

---

E.2 Proof of Theorem 5.1
In this section, we consider the i-th iteration of SIPO illustrated in Eq. (4) For the sake simplicity, we use a I X S b for vector À to denote each component of À satisfies S X S b, where a, b E I. We use и to denote the policy we are optimizing, and тy (1 S j to denote a previously obtained policy. We denote the Lagrange function as L(T,, X) -J(()) - 2 >3 (D(T, my) 6).
To prove Theorem 5.1 we consider the following two optimization problems:
(T X²) = arg min max ( A)
(11)
X20
and
(fi, X-) = arg min max [[ A),
(12)
x OSASA
where A 1. and 6o 0 is sufficiently small. 60
We make the following assumptions to prove this theorem: Assumption E.1. S J(-) I
Assumption E.2. AA 2 0, A) is /-smooth and (-Lipschitz
We may notice that solving the optimization problem (11) is hard because its domain is unbounded. Therefore, we make some approximations and consider the bounded optimization problem (12). First, we prove the following lemma about the value function J:
Lemma E.3. (T;) S (
Proof. As the domain of À in Eq. 12 is smaller than Eq. 11 we have L(T; A) 2 L( A).
By the fundamental property of Lagrange duality, know that L achieves its optimal value when À = 0 and the optimal value is (T;).
By the optimality of (ã,, )²), we know that
Σ -)) 0.
(13)
Then we have
-J(T)) = L( X²) 2 I(#, Xt) -J(()
Σ
m)) -J(,).
j=1
Then we prove the distance between optimal policy म; in problem (12) and optimal policy m, in problem (11) is very small: Lemma E.4. Under Assumption E.1 D(#, Rj) 2 5 co. V1 S <i
Proof. We prove this by contradiction.
Suppose there exists 1 jo D D(#re Jo0) 8 6g-
Then choose Á such that
jo:
Å = 0 1 1 < <i
By the Assumption E.1 Eq. 113 and A
1 we have
60
0 (mm) = L(T,, X²) > L( X > L(T Å) -1 A(D(F, TJ.) -8) 0.
That is contradiction. So we have proved that
D( RT) 2 8 - E0. V1 visj<L <i.
27

---

From the deduction above, we get the following approximation lemma:
Lemma E.5. Denote the optimal solution of Eq. 17 and Eq. as (T )) and (āz. X) respectively.
Then we have the following approximation about the optimal value and distance:
( S J (a:)
D( TT) 2 E0.
LA višj<i
Proof. This lemma follows directly by Lemma E.3 and Lemma
E.4
Therefore, it is reasonable to consider the constrained optimization problem (12) instead of primal problem (11) because we have proved that the optimal value doesn't get smaller and the distance of policy is eo-approximation of the primal problem. Finally we use the conclusion in the paper [31 to analysis the convergence of problem (12):
Lemma E.6. (13T), Theorem 4.8) Under Assumption E.2 solving Eq.
72 via two-timescale GDA
with learning rate T = O (2 and 1/λ
(11/l) requires
e6
e4
iterations to converge to c-stationary point Ti, where C1 and C2 are the constants that depend on the distance between the initial point and the optimal point.
Theorem 5.1
Under assumptions and E.2 and learning rate with learning rate Th
(c
and (11/l), SIPO converges to an e-stationary point with convergence rate
PA
Proof. We consider the following constraint nonconvex-concant optimization: min max L(T,, A). USASA
(14)
Following Lemma E.6 we know that the Two-Timescale GDA algorithm converges to an e-stationary point m..
From the above deduction, the Timescaee GDA algorithm requires O [ AACC
e
el
iterations with learning rate T/x = O 0(<2/18(²A²) and π = (l/ll) to converge to an e-stationary point with convergence rate.
F
Discussion
F.1
The Failure Case State-Distance-Based Diversity Measures
A failure case of Matee-iittnceebbssed diversity measures may be when the state space includes many irrelevant features. These features cannot reflect behavioral differences. If we run SIPO in such an environment, the learned strategies may be only diverse w.r.t these features and have little visual distinction. Like the famous noisy TV problem [5), the issue of irrelevant features is intrinsically challenging for general RL applications, which cannot be resolved by using action-based or state-occupancy-baatt diversity measures either.
Thanks to the advantages we discussed in the paper, we generally find that state-distance-hase measures can be preferred in challenging RL problems. Mcanwhile, since the state dimension can be much higher than actions, it is possible that RL optimization over states may be accordingly more difficult than actions. practice, we can design feature selector for those most relevant features for visual diversity and run diversity learning over the filtered features. In SMAC and GRF, we utilize the agent features (excluding enemies) as 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 a common practice in many existing domains, such as novelty search [12]. exploration K3 and curriculum learning 7 There are also works studying how to extract useful low-dimensional features from observations 68 18), which are orthogonal to our focus.
28

---

F.2 The Distance Metric
In Sec. we adopt the two most popular implementations 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 diversity measure. Similar topics have been extensively discussed the exploration literature 68
We leave them our future directions.
G Pseudocode of SIPO
The pscudocode of SIPO is shown in Algorithm !
Algorithm SIPO (red for SIPO-RBF and blue for SIPO-WD)
Input: Number Iterations M, Number Training Steps within Each Iteration
Hlperparameter: Learning Rate 7/. Diversity Threshold 6, Intrinsic Scale Factor a. Lagrange Multiplier Upperbound Amax. Lagrange Learning rate 7/x, Wasserstein Critic Learning Rate v/w,
RBF Kernel Variance a.
1: Archived trajectories X <-
// to store states visited by previous policies
2: for iteration i l...., M do
3: Initialize policy тe,
// initialization
4: Initialize Wasserstein critic fo.
5: for archive index j 1................... 1 do
6: Lagrange multiplier X
7: end for
8: for Training step = ..... do
9: Collect trajectory ((8h, Oh r(sn, a# )) )
h=1
10: for archive index j 1..... 1 do
11:
R
12:
end for
13:
for timestep h 1, ..... H do
14:
Fint, +- 0
compute intrinsic reward
15:
for archive trajectory Xj E X do
16:
Pu Hiiil Evex, exp
1 20
Pl Sos (9h) lxsl EvEx, (0)
18:
Finch 5- -innh + Aj. .rr.
Rd Rd. inth + min
end for
21:
Th +- r(5h, an) + Tint
22:
end for
23:
for archive index j = I,..., i i- do
24:
A + clip ()j + 17> Rim + +5) 0, Amux
II gradient ascent on A
25:
6 + Φ, + nW H
1 E/n
Vo, (fo, (sn) Fxjl
1 Exex, for (6')
26:
Φ + clip( の, - 0.01, 0.01)
27:
end for
28:
Update To, with {(,,, an, rk) by PPO algorithm end for
|| policy gradient on 0,
29:
30:
Collect many trajectories X;
collect trajectories to approximate d // for the use of following iterations
31:
X +- XU
end for
29


Reviews:
[{"review_id": "xp2oTzgeSa", "reviewer": "Reviewer_tun3", "summary": "This work proposes a solution to the problem of finding diverse policies for complex (multi-agent) reinforcement learning (RL) environments. The paper is presented as a joint study on diversity metrics and learning frameworks. For the former, the authors show the limitations of common diversity metrics like action-distribution diversity and state-occupancy based metrics and argue for metrics that incorporate state-distances for training mutually-distinct policies instead. For the latter, population-based (PBT) and iterative training (ITR) approaches are considered, where PBT is presented as a more formally suitable framework, that in reality is limited by its pairwise diversity constraints. ITR as a reasonable relaxation of PBT, on the other hand, is found to be effective in combination with the author’s proposed (’meaningful’) state-distance diversity. The combination if ITR and the proposed metric is incorporated into the State-Based Intrinsic-Reward Policy Optimization (SIPO) algorithm and evaluated on the single-agent human locomotion domain, as well as the multi-agent SMAC and GRF environments. SIPO is shown to outperform related baselines and is presented to be more capable of producing visually distinct / humanly intuitive policies compared to its counterparts.", "questions": "- In 4.2 it is mentioned that PBT only converges when the exploration is faint. Is this claim shown somewhere or is this based on empirical evidence?\n- Could you provide some motivation on why you are casting $D_s(\\pi_i, \\pi_j^*)$ as intrinsic reward, and why RBF Kernel and the Wasserstein Distance were chosen for the diversity? Why does L_2 WSD provide ‘stronger discriminative power’(l263)?\n- Increasingly more MARL approaches start to require a DEC-POMDP for independent / localized actions without a fully observable state. How would you judge the SIPO’s transferability to such a formalization?", "limitations": "There are two larger limitations mentioned, for once the assumption of continuity for convergence and the access to an object-centric state-representation. Both are openly disclosed and discussed in the paper. ‘The acceleration of ITR remains an open challenge’ is also a valid outlook, that should be addressed in the future.", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- The paper is well researched in related work. While the evaluated frameworks PBT and ITR or the concept of state-distance in itself are not novel (but well cited and explained), the combination of ITR with the proposed state-dissimilarity diversity -- realized either as RBF-Kernel or with Wasserstein-Distance — are novel as far as I can tell.\n- Both the study on the limitations and the evaluation are presented in-depth and read quite intuitive. I am not too familiar with formal proofs of convergence criteria but the technical aspects in the paper itself do appear to be sound. The evaluation is reasonably complex, covering both complex single-agent and two multi-agent domains against reasonable baseline models. \n- The paper is very nicely written and well organized. The logical structure of motivation, related work, background, analytic study of the frameworks in combination with the metric and the presentation of the SIPO algorithm and its evaluation is easy to follow and intuitively explained. Small examples to illustrate the argumentation help lighten an otherwise densely formulated reasoning. I also find the visualizations to be nicely done.\n- The author’s SIPO approach seems to produce some very diverse strategies, which also appear intuitively interpretable. While diversity in itself is very important for exploration and an important Problem to solve for RL in general, I find the convergence towards interpretable strategies to be very intriguing. The paper is not only nicely understandable and informative on the matter of diversity related approaches, the evaluation is rather strong and the supplementary material has enough content for another paper by itself. I have no real complaints about this work, very nicely done.", "weaknesses": "- Besides providing a reasonably complex evaluation, there could have been more than 5 seeds used for the evaluation.\n- I would also like to see at least some classic total-reward metrics / comparisons for these domains, as the metrics chosen here to highlight the performances of the SIPO algorithm (pairwise distances, est. state entropy, agent position distributions, nr. distinct strategies) seem a bit cherry-picked to argue in favor of diversity only. While there are some relevant plots in the Appendix (and some of the toy-examples reason with rewards), I would encourage to showcase at last one such classic performance comparison against the baselines in the main-paper itself.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "+ I would also like to see at least some classic total-reward metrics / comparisons\n\nAppendix B.5 elaborates on the detailed returns accomplished by SIPO. We present the diversity score and average rewards achieved by all algorithms below. These numerical values are averaged across the entire population for a clear comparison:\n\n| humanoid\t|SIPO-RBF \t| SIPO-WD \t| DIPG \t| RSPO | SMERL \t| DvD | PPO |\n|  ----  | ----  |----  |----  |----  |----  |----  |----  |\n| reward \t|\t3508 \t| \t3763 \t| 5191\t | 1455   |4253 | 4498 | 5299 |\n| diversity \t| \t0.53\t| \t0.71 \t| 0.12 \t  | 0.53   | 0.01 | 0.40 | -   \t|\n| SMAC 2m1z  |\t\t|\t\t|\t|\t|\t|       |\t        |\n| win rate %   | \t100 \t| \t100 \t| 100\t| 100 \t| 100 |100 | 100 |\n| diversity (1e-3) | \t38 \t| \t36 \t| 32\t| 32\t| 28  | 30   | -     |\n| SMAC 2c64zg |\t\t|\t\t|\t|\t|\t|    |\t|\n| win rate % \t| \t99 \t| \t93 \t| 99\t| 85 \t| 100 |100 | 100 |\n| diversity (1e-3) | \t72\t| \t56 \t| 70\t| 56\t| 42    | 57 | -     |\n| GRF 3v1 (first 4) |\t\t|\t\t|\t|\t|\t|    |\t|\n| win rate % \t| \t93\t| \t 82\t| 93\t|  94\t|   91     |   83   |    92   |\n| diversity \t|  \t3.0\t|  \t3.0\t| 2.7\t| 2.0    |   1.3      |   3.0   | 2.7     |\n| GRF CA \t|\t\t|\t\t|\t|\t|\t|       |\t\t|\n| win rate % \t| \t70\t| \t41\t| 46\t|  76\t|    45    |   -    |   50    |\n| diversity \t|  \t3.3\t|  \t3.0\t| 2.3\t| 2.0\t|   1.3      |   -   | 1.7     |\n| GRF Corner \t|\t\t|\t\t|\t|\t|\t|    |\t|\n| win rate % \t| \t72\t| \t56\t| 75\t|  23\t|    67    |    -   |   71    |\n| diversity \t|  \t2.7\t|  \t3.0\t| 1.7\t| 1.6\t|   1.0      |   -   | 2.0     |\n\nThe tabulated data above highlights the varying trade-offs between task performance and diversity exhibited by different algorithms. It is noteworthy that SIPO, in particular, displays an adeptness at training a notably more diverse population while upholding a reasonably moderate level of task performance. \n\n+ In 4.2 it is mentioned that PBT only converges when the exploration is faint. Is this claim shown somewhere or is this based on empirical evidence?\n\nThis conclusion can be drawn from empirical evidence presented in Table 2. While PBT may occasionally succeed in learning diverse policies, this outcome is contingent upon initializations that prompt the agent to explore all landmarks. Nevertheless, such instances of success are outweighed by cases of failure, leading to notable variance in PBT outcomes.\n\n+ why you are casting the diversity measure as intrinsic reward\n\nThe objective in Equation (7) is not differentiable w.r.t. \\pi. This is because it depends on the states traversed by \\pi, rather than \\pi’s output. Consequently, conventional gradient-based methods are unsuitable for its optimization. Nevertheless, we are able to represent it as the cumulative sum of intrinsic rewards, specifically the intrinsic return. This allows us to leverage policy gradient techniques for optimization.\n\n+ why RBF Kernel and the Wasserstein Distance were chosen for the diversity? Why does L_2 WSD provide ‘stronger discriminative power’(l263)?\n\nWe first choose the RBF kernel because it is the simplest and the most widely adopted kernel function in the ML community. Regarding the choice of the Wasserstein distance, also referred to as the earth-moving distance, it holds a distinct advantage due to its interpretation within optimal transport theory[1,2]. Unlike distances that rely solely on specific summary statistics such as means, the Wasserstein distance can effectively quantify shifts in state distributions and remains robust in the presence of outliers[2].\n\n[1] Arjovsky, M., Chintala, S., & Bottou, L. (2017, July). Wasserstein generative adversarial networks. In International conference on machine learning (pp. 214-223). PMLR.\n\n[2] Villani, C. (2009). Optimal transport: old and new (Vol. 338, p. 23). Berlin: springer.\n\n+ Increasingly more MARL approaches start to require a DEC-POMDP for independent / localized actions without a fully observable state. How would you judge the SIPO’s transferability to such a formalization?\n\nExperimental outcomes in SMAC and GRF confirm the favorable performance of SIPO in Dec-POMDPs. Like most popular MARL algorithms, we assume accessible global states only during training, i.e., centralized training with decentralized execution (CTDE).\n\nIn the fully decentralized training setting, discovering diverse policies requires the fundamental improvement of existing MARL algorithms. While this is not the main focus of our paper, we are making efforts to address this problem in future works.\n"}, {"review_id": "cXn673JxaM", "reviewer": "Reviewer_hytR", "summary": "The paper discusses the challenge of optimizing rewards while discovering diverse strategies in complex reinforcement learning problems. This paper examines two design choices for tackling this challenge: diversity measure and computation framework. By incorporating state-space distance information into the diversity measure, the behavioral differences between policies are accurately captured. Besides, two common computation frameworks: population-based training (PBT) and iterative learning (ITR) are compared, and it shows that ITR can achieve comparable diversity scores with higher computation efficiency. Based on above analysis, a novel diversity-driven RL algorithm named State-based Intrinsic-reward Policy Optimization (SIPO) is proposed. The authors evaluate SIPO across three environments and demonstrate that it consistently produces diverse policies that cannot be discovered by existing baselines.", "questions": "Q1: Would you improve the literature reviews from the aspect of adding some well-known or SOTA related works (e.g. [1] [2] [3] [4] [5])?\n\nQ2: Why can state-distance based measurement overcome the shortcomings of action-based measurements? It is suggested to make more discussion theoretically.\n\nQ3: Can SIPO be extended to algorithms in two-player zero-sum game scenario, like self-play, PSRO?\n\nQ4: What will be like if combining state-based diversity measurement and action-based diversity measurement? It is suggested to add an study in experiment part.\n\nQ5: Since the number of population size is fixed in PBT or ITR, the determination of it is still an open question as we known. Would you add a theoretical or empirical analysis on it?\n\nQ6: Comparison criteria of diversity seems unfair to baselines in Humanoid Locomotion and SMAC, since all baselines’ optimization objective are action-based. An intuitive evaluation criteria is the quantifiable behavioral difference between agents. Could you make more analysis on it?\n\nQ7: As can be seen, the heatmaps in Fig7 seems to show that the positions explored by the four agents are not significantly different. Would you add additional explanations on it?\n\nQ8: Minor: abbreviation in Fig4 (i.e., “IL”) is not been explained.\n\n[1] Liu, Z., Yu, C., Yang, Y., Wu, Z., & Li, Y. (2022). A Unified Diversity Measure for Multiagent Reinforcement Learning. Advances in Neural Information Processing Systems, 35, 10339-10352.\n\n[2] Balduzzi, D., Garnelo, M., Bachrach, Y., Czarnecki, W., Perolat, J., Jaderberg, M., & Graepel, T. (2019, May). Open-ended learning in symmetric zero-sum games. In International Conference on Machine Learning (pp. 434-443). PMLR.\n\n[3] Hu, S., Xie, C., Liang, X., & Chang, X. (2022, June). Policy diagnosis via measuring role diversity in cooperative multi-agent rl. In International Conference on Machine Learning (pp. 9041-9071). PMLR.\n\n[4] Masood, M. A., & Doshi-Velez, F. (2019). Diversity-inducing policy gradient: Using maximum mean discrepancy to find a set of diverse policies. arXiv preprint arXiv:1906.00088.\n\n[5] Li, C., Wang, T., Wu, C., Zhao, Q., Yang, J., & Zhang, C. (2021). Celebrating diversity in shared multi-agent reinforcement learning. Advances in Neural Information Processing Systems, 34, 3991-4002.\n", "limitations": "The authors have concluded the limitation of the methodology from the aspect of state representation and acceleration problem. ", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "This paper introduces a state-based population diversity measurement and transfers it into a shaping reward in practice for computational conveniency. By comparison with PBT and ITR, it is concluded that ITR is able to achieve higher performance. Additionally, experiment environments including single-agent reinforcement learning and multi-agent reinforcement learning all shows the effectiveness of the proposed method. In a way, this paper is well-written and presents some contributions to the field of reinforcement learning. The authors provide clear explanations of their methodology and experiment results, making the paper easy to track. ", "weaknesses": "In this paper, the proposed state-based diversity measurement is one of key innovations. By combining with ITR framework, it achieves satisfactory performance. However, there still exist some weaknesses remained to be polished up.\n\n(1) The comprehensiveness of literature reviews remains to be improved. \n\n(2) The motivating example in Sec4.1 shows the limitation of previous action-based diversity measurement. However, the reason why state-distance based measurement can overcome the problem is not explained adequately.\n\n(3) The experiment part seems to be insufficient. Some SOTA diversity enhancement methods in RL and MARL are not analyzed or summarized. Besides, the assessment criteria of diversity seems unfair. \n\n(4) It claims that the heatmaps of agent positions in SMAC show obvious strategic differences. However, all four policies seem to explore similar areas in the map.\n\n(5) While the main body of the paper is well-written, there is space for improvement. I defer some of my issues in the appendix to \"Questions\".\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "+ Some SOTA diversity enhancement methods in RL and MARL are not analyzed or summarized.\n\nWe sincerely thank the reviewer for providing additional relevant literature, but we believe that our paper does well in contrasting against previous methods for developing diverse policies in RL.\n\n[1] and [2] study diversity in competitive multi-agent games for minimizing exploitability. This objective does not apply to our settings, i.e., single-agent MDPs and cooperative multi-agent games. \n\n[3] and [5] explore cooperative multi-agent games, gauging diversity **among agents within each game**. Their final objectives are optimizing rewards. In contrast, our approach focuses on diversity across **a collection of distinct joint policies**. The final reward is the secondary objective in our setting. [5] has been discussed in line 89 of our paper. We commit to incorporating [3] in our forthcoming revision.\n\nWe acknowledge the significance of [4] (i.e., DIPG) in relation to our paper. This work is extensively discussed in our related work section and comprehensively juxtaposed in our experimental analyses (cited as [39] in our paper).\n\n+ Why can state-distance based measurement overcome the shortcomings? Theoretical discussion?\n\nAction-based measures may fail when visually similar states are reached through very different action sequences. We provide particular **counterexamples** of action-based measures in Sec 4.1, suggesting fundamental flaws of existing methods.\n\nState-distance based measures circumvent this issue by explicitly comparing states, which directly addresses the counter example. Based on this finding, we further empirically validate our proposed methods on many challenging domains with empirical results in Sec 6. How to best quantify diversity remains an open question. A widely accepted theoretical framework has not yet converged in the community. For this reason, we choose to analyze the algorithmic issues using specific examples and an analysis on algorithm convergence. \n\n\n+ Can SIPO be extended to algorithms in self-play, PSRO?\n\nSIPO's design inherently enables the generation of diverse policies for conquering static opponents, as illustrated by SMAC and GRF experiments. We acknowledge that the integration of SIPO (low-level policy solver for best responses) with PSRO (high-level policy mixture) holds great potential. We regard this as a promising avenue for future exploration.\n\n+ What will be like if combining state-based diversity measurement and action-based diversity measurement?\n\nThe reviewer’s suggestion is greatly appreciated. In response, we have carried out additional experiments within the GRF domain to explore this approach. We introduce action information by directly concatenating the global state, used for diversity calculation, with the one-hot encoded actions of all agents. The following table presents the outcomes, indicating the number of policies obtained:\n\n|\t|\t\t3v1 | CA | corner |\n| --- | --- | ---| ---|\n| SIPO-RBF | 3.0 (0.8) | 3.3 (0.5) | 2.7 (0.5) |\n| SIPO-RBF + action | 3.0 (0.0) | 2.3 (0.5) | 1.0 (0.0) |\n\nFor scenarios with a limited number of agents, the action-augmented variant demonstrates comparable performance. However, when the agent count increases (as evident in the 11-agent cases of CA and corner), the incorporation of actions can introduce misleading diversity, detracting from the authenticity of the outcomes. We will append these results in our final version.\n\n+ the determination of the population size\n\nA larger population usually leads to a better performance on the desired application[1]. SIPO/ITR enables open-ended training for diversity discovery. With unlimited time and computation, training can proceed until no additional distinct strategies can be discovered. In our paper, we run with the maximal population size given available resources.\n\n[1] Tang, Z. et al. (2021). Discovering diverse multi-agent strategic behavior via reward randomization. ICLR.\n\n+ Comparison criteria of diversity seems unfair to baselines in Humanoid Locomotion and SMAC\n\nThe adopted criterion (i.e., torque distance, k-NN state entropy) is a commonly used evaluation metric[2,4]. Prior works (i.e., our baselines) develop diversity measures for their own purposes, such as encouraging exploration and deriving robust policies, which may fail to learn meaningful diverse policies. Our measures are designed to directly tackle this diversity problem based on the analysis of counter-examples and empirical evidence. Adopting a state-based criterion does not mean that SIPO will benefit from it and lead to an unfair evaluation since no methods explicitly optimize this evaluation criterion. \n\nPrior works[3] have also attempted to use an action-based metric, i.e., DvD score. However, [3] reported that this criteria can easily achieve the maximum value of 1.0 and does not show distinction among different algorithms.\n\n[2] Shuang Wu, Jian Yao, Haobo Fu, Ye Tian, Chao Qian, Yaodong Yang, QIANG FU, and Yang Wei. Quality-similar diversity via population based reinforcement learning. In The Eleventh International Conference on Learning Representations, 2023. \n\n[3] Zhou, Z., Fu, W., Zhang, B., & Wu, Y. (2022). Continuously discovering novel strategies via reward-switching policy optimization. arXiv preprint arXiv:2204.02246.\n\n[4] Singh et al., Nearest neighbor estimates of entropy, 2001\n\n+ As can be seen, the heatmaps in Fig7 seems to show that the positions explored by the four agents are not significantly different. Would you add additional explanations on it?\n\nTo facilitate a comprehensive comparison, we have included policies generated by DIPG for the reviewer's consideration in the attached pdf. Compared with DIPG, we contend that the heatmap in our paper exhibits greater behavioral diversity. Moreover, we strongly encourage the reviewer to peruse the GIF demonstrations on our [project website](https://sites.google.com/view/diversity-sipo) for an enhanced qualitative assessment."}, {"review_id": "sWePlL2jV1", "reviewer": "Reviewer_3iHV", "summary": "This paper addresses the problem of learning diverse policies for a given RL task. First, it studies pros and cons of various formulations in two different dimensions: (i) How to measure diversity, for which it considers measures based on action or state distribution and state distances, (ii) how to compute the diverse policies, either with a joint method or an iterative one. Then, it combines the findings into a method, called SIPO, which implements iterative learning through gradient descent ascent with state distance incentives. Finally, it empirically evaluates SIPO on a variety of domains, including locomotion tasks, Star-Craft, and Google Research Football.", "questions": "I have one crucial concern about this paper, which is otherwise sound and interesting. The superiority of diversity measures based on state distances is only informally motivated, through examples rather than theoretical justification. Instead, the diversity measures based on action distribution or state occupancy have been both linked to important theoretical properties, such as reward robustness for the former (e.g., Husain et al., Regularized policies are reward robust, 2021) or bounded sub-optimality for the latter (e.g., Kakade and Langford, Approximately optimal approximate reinforcement learning, 2022). Diversity based on state distances currently lacks similar theoretical ground, which also leaves an existential question on the motivation of the paper? Why we want to learn diverse strategies in the first place? Is it to be robust to reward perturbations? Is to learn reusable skills? Is it something else?\n\nThe concern reported above somewhat propagates to the experimental evaluation. If the ultimate purpose of the training is not clear, how can we evaluate one method against another? Indeed, the experiments are based on arbitrary diversity scores. SIPO may be better than baselines on those, but it is hard to reach some conclusion beyond qualitative justifications. Perhaps a good option would be to evaluate SIPO also on more consequential benchmarks, such as testing the reward robustness of the trained set of policies, or showing that the latter is a good starting point for fine-tuning to a different task.\n\nFor this main reason, I am currently providing a borderline evaluation, while I am open to change my score if the authors can provide more formal justification for their objective function in the rebuttal.\n\nI provide below additional comments on the paper.\n\n**Objective function**\n\nOne key aspect that Section 4.1 seems to overlook is that all of the provided motivations (especially in lines 158-169) make sense only when the environment's states lie on a metric space. In several domains, such as tabular MDPs with symbolic state representations or vision-based tasks, defining a proper metric over the states might be even more challenging than learning diverse policies alone. I think this limitation should be explicitly reported everywhere in the paper, including the introduction and abstract.\n\nThe motivation reported in lines 170-173 appears to be somewhat weak too, at least in domains where external rewards are present, and the concept of idle actions may be incorporated in the rewards.\n\nCan the authors clarify the role of the cost function $g$ into the diversity score reported in Eq. 5?\n\n**Experiments**\n\nWhy are the authors reporting experiments in multi-agent domains, even if they present a method for learning diverse policies in a single-agent setting? This choice looks somewhat odd, and it shall be motivated.\n\nI am worried about the statistical significance of the reported performance results, since most of them are obtained as average over 5 or 3 seeds. While I can understand that running experiments in such complex domains is costly, the standard to claim experimental robustness has increased lately. Moreover, the results report average and standard deviation. On the one hand, confidence intervals would be more meaningful than standard deviation, on the other hand only it is not enough to have best average performance to say that one method outperforms another when the intervals are overlapping.\n\n**Related Works**\n\nThis work looks in a way orthogonal to Zahavy et al. (2022), in which the authors present a method to learn diverse near-optimal policies by maximizing diversity with an hard reward constraint. While their concept of diversity is different, it would be interesting to discuss pros and cons of the two alternative solutions in depth, and perhaps compare SIPO with Domino in the experimental campaign.\n\nAnother work that is somewhat relevant to the topic is (Mutti et al., Reward-free policy space compression for reinforcement learning). Their aim is to learn a diverse set of policies from which any reward function can be approximately optimized, and they also present a gradient descent ascent procedure for this purpose. The fact that their work does not account for rewards is an important difference, but the authors can perhaps consider discussing this work in the paper as well. \n\nOne key benefit that I see in the SIPO solution w.r.t. prior works, is that SIPO shall enjoy favorable computational complexity, whereas both Zahavy et al. and Mutti et al. need to solve a non-convex non-concave optimization problem.\n\n**Minor**\n\n- The preliminaries are framing the problem as POMDP. I do not understand why partial observability is introduced, and then never used in the paper at all.\n- Figure 4, IL is instead ITR?\n- Theorem 4 says that ITR can achieve the same rewards as PBT, but only with an inferior diversity. This trade-off between computation and diversity could be better highlighted.\n- One of the evaluation metric is the entropy estimator via k-NN, for which (Liu & Abbeel, 2021) is mentioned. Note that those entropy estimators have been presented before (e.g., Singh et al., Nearest neighbor estimates of entropy, 2001). Moreover, if the goal is to maximize the state entropy, why not using APT instead of SIPO?", "limitations": "The limitations are reported in the final sentences of the paper. Perhaps, some limiting aspects could be discussed in additional length.", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "- Relevance of the problem. Several recent works have addressed the problem of learning diverse policies in RL, in both supervised and unsupervised settings;\n- Methodology. Interesting and reasonably efficient methodology that is based on a new state-metric perspective on the problem of learning diverse policies;\n- Experimental results. Promising empirical results on challenging domains.", "weaknesses": "- Motivation. The introduced objective lacks a strong theoretical ground that is mostly present in previous works with alternative diversity objectives;\n- Related works. The comparison between SIPO and some relevant related works, especially Zahavy et al., 2022, is not really upfront;\n- Experiments robustness and significance. The experiments consider arbitrary performance metric and average results over 5 or 3 seeds, which is hardly enough to get statistical significance.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "+ motivation\n\nOur primary aim is to achieve diversity itself. Agents with similar reward functions can manifest significantly diverse behaviors (e.g., high-reward unexpected behavior[1]). This property is different from standard DL where different local optima (almost) suggest the same results (i.e., proxy to the global optimum[2]).\n\nThis prompts the importance of studying *the learned behavior* and finding *all unique solutions for the same task* in RL beyond only the rewards. We believe it is a **fundamental research problem in RL**, which, however, very few researchers have been fully aware of. A diverse collection of policies can further enhance human-AI collaboration or help design robust robots, depending on the applicaion (line27-line30).\n\nDespite our best efforts to engage in theoretical analysis, we note that a consensus of the best algorithmic formulation of \"distinct solutions\" in RL remains elusive.\n\n[1] https://openai.com/blog/ 409 faulty-reward-functions/.\n\n[2] Ma, T. (2020). Why Do Local Methods Solve Nonconvex Problems?.\n\n+ clarification of the evaluation metric\n\nWe endeavored to select the best available task-specific metric to authentically reflect behavioral diversity. For humanoid, we adopt a metric embraced by the Quality-Diversity community. However, for SMAC and GRF, existing metrics can fail (e.g. Table 8 in [1] and our Appendix B.2.3). Therefore, it is necessary to engineer task-specific metrics relying on both visualization-based insights and metrics in previous works.\n\nWe enthusiastically encourage the reviewer to review all replay files utilized for tallying policy counts on our project website: https://mega.nz/folder/xP0D2CRa#YRL-PVjjsyZhGZ2QUZqH2g. \n\n[1] https://arxiv.org/abs/2204.02246\n\n+ tabular MDPs/vision-based tasks\n\nWe explicitly assume the access to object-centric information and features in our paper. We emphasize that this assumption typically holds in MARL benchmarks and can be further addressed by incorporating feature learning algorithms, e.g. [1] and [2]. We discussed this in Appendix F.2 and are committed to reinforcing this. \n\nWe note that SIPO-WD has already addressed this assumption through the incorporation of a learnable Wasserstein discriminator. The discriminator can effectively process images or one-hot state embeddings as inputs, as detailed in Appendix B.3.\n\n[1] https://arxiv.org/abs/1810.04586\n\n[2] https://arxiv.org/abs/2102.11271\n\n+ The motivation in lines 170-173 appears weak\n\nAs an example, in the soccer attack, the goalkeeper could misleadingly amplify the action-based diversity score by outputting random actions (e.g. sliding in the backyard). This example underscores a notable issue. If action-based measures are leveraged for optimizing diversity, the resultant policies can produce visually similar behavior.\n\nWhile it can be possible to exclude idle actions by modifying task rewards, it requires a large number of hacks and engineering efforts. The issue of idle actions exists even in popular MARL benchmarks like GRF. We propose a systematic approach to bypass idle actions by directly considering state distances.\n\n+ the role of the cost function g?\n\nThe cost function g is a notation providing a generalized and unified definition. It also contributes to training stability by scaling the raw distance. g in Eq.5 can be realized by either RBF kernel or Wasserstein distance. \n\n+ multi-agent experiments and POMDP\n\nWe wish to validate that SIPO is general enough to be applied to many difficult and complicated scenarios, such as testbeds like GRF and SMAC (SMAC has partial observability). These environments encompass a notably more diverse range of potential winning strategies, and existing methods can fail. Therefore, they offer an apt platform for assessing SIPO's capacity.\n\n(Dec-)POMDP is a standard formulation in many MARL works. We follow this common definition since it provides the fewest algorithmic assumptions.\n\n+ Comparison with Domino\n\nWhile we have discussed in Sec 2, we are delighted to present an in-depth discussion below.\n\n**Formulation** Domino pursues hard constraints on rewards while optimizing diversity, potentially hindering policies with disparate reward scales. Therefore, Domino tends to discover similar policies but all with the same reward. SIPO, on the other hand, allows much diverse locally optimal policies.\n\n**Diversity Measure** Domino employs the distance between successor features, while SIPO directly utilizes the distance between raw states. Domino is complementary to our worker because SIPO can also incorporate successor features as the state representation.\n\nWe have meticulously re-implemented Domino within our codebase according to Domino’s appendix. We execute the algorithm in the Humanoid locomotion task, employing the robot state (excluding torques) for successor feature computation. Despite our earnest efforts to optimize Domino's performance, our findings reveal its comparable performance to SMERL, illustrated by a minimal diversity score of 0.01.\n\n+ APT metric and its usage in experiments\n\nWe acknowledge the missing reference and will duly append it to our paper.\n\nRegarding the utilization of APT, we appreciate the suggestion. However, there is a fundamental distinction in formulation. APT optimizes state entropy within a *single policy*, whereas our method, SIPO, targets the joint entropy of *a population of policies*. It is okay for each single policy within the population to have low state entropy.\n\nTo employ APT's objective, training a population of agents concurrently is required. The algorithm should optimize the estimated entropy over states visited by all policies. Yet, this approach mandates large-scale k-NN computation (k=12) over substantial batches, leading to significant computational inefficiency. Despite our dedicated efforts, we didn’t finish a single training trial of APT within 48 hours (in contrast to other PBT baselines, e.g. DvD, which completes training in less than 8 hours).\n"}, {"review_id": "CI0sgvpJ1r", "reviewer": "Reviewer_hxqg", "summary": "Reinforcement Learning (RL) algorithms commonly learn a distinct policy that is responsible for a distinct behavior. Learning different, diverse behaviors generally is a difficult task in RL. This paper proposes a new algorithm State-based Intrinsic-reward Policy Optimization (SIPO) that can learn diverse, human interpretable behaviors.\nThe paper first discusses some of the current diversity measures, and based on the insight, it proposes the new ITR-based method, even though PBT is the choice when it comes to learning diverse behaviors. The method is efficient and can learn diverse behaviors. The effectiveness is demonstrated in simulated environments.", "questions": "- The motivation behind Figure 2 is unclear to me even when reading the text. I think this figure definitely needs more description and explanation. There are also no numbers indicating what the measured distances are. \n\n- Different works have approximated the state entropy for discovering new skills. E.g. the APT [1]. It would be interesting to see how the used diversity measures compare against it. Can the authors assess, how different the solutions would be when using the approximated state entropy compared to the proposed metrics? \n\n- The humanoid locomotion task in Section 6.1 is used to compare the diversity of learned policies. How do the methods compare w.r.t. performance?  \n\n[1]: https://openreview.net/forum?id=fIn4wLS2XzU", "limitations": "The paper explicitly addresses limitations but doesn't state anything about potential negative societal impact.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "- well written. Motivation and contributions made clear\n- the paper covers a good amount of related work, even though there are a few missing, in my opinion (see Weaknesses).\n- Nice evaluations w.r.t. diversity", "weaknesses": "- The big field of unsupervised reinforcement learning also covers a lot of similarity/dissimilarity measures for formulating an intrinsic reward. Even though some of the works are mentioned (e.g. DIAYN), there are several other works that should be mentioned as they are using different objectives and hence differently measure the similarity/dissimilarity:\n\t- https://arxiv.org/pdf/1906.05274.pdf\n\t- http://proceedings.mlr.press/v139/yarats21a/yarats21a.pdf\n\nDuring a Google search, I discovered another work that also seems to have an interesting objective to learn different solutions:\n\t- https://proceedings.mlr.press/v164/celik22a/celik22a.pdf\n\n- weak motivation for the necessity of the state distance (see Questions)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "+  there are several other works that should be mentioned as they are using different objectives and hence differently measure the similarity/dissimilarity\n\nWe appreciate the reviewer's insightful suggestion and ensure that we will incorporate these relevant works into our paper. The reviewer’s additional reference[1] operates in a parallel setting where a mixture of policies is learned within task-aware contextual MDPs, with each policy addressing a subspace of tasks. In contrast, our focus is on the discovery of distinct individual policies to tackle the same task.\n\n[1] Celik, O., Zhou, D., Li, G., Becker, P., & Neumann, G. (2022, January). Specializing versatile skill libraries using local mixture of experts. In Conference on Robot Learning (pp. 1423-1433). PMLR.\n\n+ The motivation behind Figure 2 is unclear to me even when reading the text. I think this figure definitely needs more description and explanation. There are also no numbers indicating what the measured distances are.\n\nAs an example, in the soccer attack, the goalkeeper could misleadingly amplify the action-based diversity score by outputting random actions (e.g. sliding in the backyard). This example underscores a notable issue. If action-based measures are leveraged for optimizing diversity, the resultant policies can produce visually similar behavior.\n\n+ It would be interesting to see how the used diversity measures compare against APT.\n\nWe appreciate the suggestion. However, there is a fundamental distinction in formulation. APT optimizes state entropy within a *single policy*, whereas our method, SIPO, targets the joint entropy of *a population of policies*. It is okay for each single policy within the population to have low state entropy.\n\nTo employ APT's objective, training a population of agents concurrently is required. The algorithm should optimize the estimated entropy over states visited by all policies. Yet, this approach mandates large-scale k-NN computation (k=12) over substantial batches, leading to significant computational inefficiency. Despite our dedicated efforts, we didn’t finish a single training trial of APT within 48 hours (in contrast to other PBT baselines, e.g. DvD, which completes training in less than 8 hours). We primarily employ the k-NN state entropy metric to quantify diversity in the SMAC domain, as we show in the paper.\n\n+ The humanoid locomotion task in Section 6.1 is used to compare the diversity of learned policies. How do the methods compare w.r.t. performance?\n\nWe present the diversity score and corresponding average rewards achieved by all algorithms below. These numerical values are averaged across the complete population for a clear comparison:\n\n| \t\t|SIPO-RBF | SIPO-RBF | DIPG | RSPO | SMERL | DvD | PPO |\n| --- | --- | --- | --- | --- | --- | --- | --- | \n| humanoid reward |3508 \t| 3763 \t\t| 5191 | 1455 |4253 | 4498 | 5299 |\n| humanoid diversity | 0.53 | 0.71 \t\t| 0.12 | \t0.53 | 0.01 | 0.40 | -\t|\n\nThe tabulated data above highlights the varying trade-offs between task performance and diversity exhibited by different algorithms. It is noteworthy that SIPO, in particular, displays an adeptness at training a notably more diverse population while upholding a reasonably moderate level of task performance. \n"}]

Author rebuttal:
We express our sincere gratitude to the reviewer for their meticulous examination and thoughtful feedback on our manuscript. We response to each reviewer's question in the corresponding channels. Please feel free to drop a message if you have additional concerns.

We acknowledge a typo in the figures of our paper. "IL" should be "ITR". We promise to fix this in our next revision.

The attached pdf contains the heatmap of DIPG in SMAC, in response to reviewer hytR.

Meta-review: The paper had mixed reviews, with most reviewers weakly accepting it following discussion with the authors, one reviewer accepting it and one reviewer rejecting it. I have read the paper, the rebuttal and discussed it with the reviewers and I feel that there is still some unclarity w.r.t to Equation 5 (which is the main contribution of the paper) that must be further discussed. In the rebuttal, the authors explain how Equation 5 can be used to encapsulate previous diversity objectives, including Successor Features based diversity. It allows the authors to introduce a loss function between states inside the expectation over the state occupancy, while applying it after the expectation will result in diversity based on SFs. Introducing a non linear function before taking an expectation might bring various advantages. In particular, it is often the case that when averaging the features over the occupancy, to achieve successor features, some information is lost due to averaging. This is a great novelty by the authors, that leads to interesting results. I would like to see that part in the paper clearly discussed w.r.t to related work. I also agree with the reviewers that there is currently a gap in understanding this new objective theoretically. However, given the empirical contributions of the paper, I think that the evidence is clear that this is an interesting idea and that other people might want to study it. I would like to see some discussion on future work on this front, what is missing and why. The authors gave some explanations on that in the rebuttal and they should be included in the paper. I encourage the authors to implement the feedback from the reviews, as well as the new results posted during the rebuttal when making their final version. I will follow closely to see how these changes were implemented. I recommend accepting the paper.
Decision: Accept (poster)