Continuously Discovering Novel Strategies via Reward-Switching Policy Optimization
Authors: Zihan Zhou
Wei Fu
Bingliang Zhang
Yi Wu
Venue: ICLR 2022 Poster (2022)
Keywords: diverse behavior
deep reinforcement learning
multi-agent reinforcement learning

Abstract: We present Reward-Switching Policy Optimization (RSPO), a paradigm to discover diverse strategies in complex RL environments by iteratively finding novel policies that are both locally optimal and sufficiently different from existing ones. To encourage the learning policy to consistently converge towards a previously undiscovered local optimum, RSPO switches between extrinsic and intrinsic rewards via a trajectory-based novelty measurement during the optimization process. When a sampled trajectory is sufficiently distinct, RSPO performs standard policy optimization with extrinsic rewards. For trajectories with high likelihood under existing policies, RSPO utilizes an intrinsic diversity reward to promote exploration. Experiments show that RSPO is able to discover a wide spectrum of strategies in a variety of domains, ranging from single-agent navigation tasks and MuJoCo control to multi-agent stag-hunt games and the StarCraft II Multi-Agent Challenge.

Published as a conference paper at ICLR 2022
CONTINUOUSLY DISCOVERING NOVEL STRATEGIES VIA REWARD-SWITCHING POLICY OPTIMIZATION
Zihan Zhou 15 Wei Fu" 24, Bingliang Zhang", Yi 2u
1 CS Department, University of Toronto, 2 III,, Tsinghua University," 3 Shanghai Qi Zhi Institute Footoredo@gmallo com, fuwth1 7 gmail il com, 4 ixwuy1@gmails com
ABSTRACT
We present Reward- -wittchiii Policy Optimization (RSPO), a paradigm to dis- cover diverse strategies in complex RL environments by iteratively finding novel policies that both locally optimal and sufficiently different from existing ones. To encourage the learning policy to consistently converge towards previously undiscovered local optimum, RSPO switches between extrinsic and intrinsic wards via trajectory- novelty measurement during the optimization process. When a sampled trajectory is sufficiently distinct, RSPO performs standard policy optimization with extrinsic rewards. For trajectories with high likelihood under existing policies, RSPO utilizes an intrinsic diversity reward to promote exploration. Experiments show that RSPO is able to discover wide spectrum of strategies in a variety of domains, ranging from single-agent navigation tasks and MuJoCo control to multi-agent stag-hunt games and the StarCraft II Multi-Agent Challenge.
INTRODUCTION
The foundation of deep learning successes is the use of stochastic gradient descent methods to obtain a local minimum for a highly non-convex learning objective. It has been a popular consensus with theoretical justifications that most local optima are very close to the global optimum (Mal 2020). Consequently, algorithms for most classical deep learning applications only focus on the final performance of the learned local solution rather than which local minimum is discovered.
However, this assumption can problematic in reinforcement learning (RL), where different local optima in the policy space can correspond to substantially different strategies. Therefore, discovering a diverse set of policies can be critical for many RL applications, such as producing natural dialogues
in chatbot (Li et al. 2016). improving the chance of finding targeted molecule (Percira et al.) 1021
generating novel designs Wang et al. 2019) or training a specialist robot for fast adaptation CCully
et al. 2015). Moreover, in the multi-agent setting, collection of diverse local optima could further
result in interesting emergent behaviors (Liu et al. 2019]] [hhng et al.) 2020 Baker et al.] 2020)) and
discovery of multiple Nash equilibria (Tang al. [222]) ), which further help build strong policies that
can adapt to unseen participating agents in a zero-shot manner in competitive (Jaderberg el al. 2019
Vinyals et 2019) and cooperative games (Lupu et 202T)
In order to obtain diverse strategies in RL, most existing works train a large population of policies in parallel (Pugh et al. 2016); Cully et al. 2015 Parker-Holder al. (0220b). These methods often adopt a soft learning objective by introducing additional diversity intrinsic rewards or auxiliary losses. However, when the underlying reward landscape in the RL problem is particularly non-uniform, policies obtained by population-based methods often lead to visually identical strategies (Omidshafiei al. 2020 Tang et al. 202Tp. Therefore, population-basee methods may require a substantially large population size in order to fully explore the policy space, which can be computationally infeasible.
Moreover, the use of soft objective also results in non arivtrivil and subtle aaperr-praamtte tuning to balance diversity and the actual performance in the environment, which largely prevents these existing methods from discovering both diverse and high-quality policies in practice (Parker-Holder et al.) 2020b] Lupu al. 2021 Masood & Velez, 2019). Another type of methods directly explores diverse strategies in the reward space by performing multi-objective optimization over
'Equal Contribution.
1 Work done residence researcher Shanghai Qi Zhi Institute.

---

Published as a conference paper at ICLR 2022
human-designed behavior characterizations (Pugh et al., 2016; Cully et al. 2015) random search over linear combinations of the predefined objectives (Tang et al. 2021 2 et al. 2020;] Ma et al.) 2020). Although these multi-objective methods are particularly successful, set of well-defined and informative behavior objectives may not be accessible in most scenarios.
We propose simple, generic and effective iterative learning algorithm, Reward-Switching Policy Optimization (RSPO), for continuously discovering novel strategies under a single reward function without the need of any environment--pecific inductive bias. RSPO discovers novel strategies by solving a sitering-bbsed objective, which restricts the RL policy to converge to a solution that is sufficiently different from a set of locally optimal reference policies. After a novel strategy obtained, it becomes another reference policy for future RL optimization. Therefore, by repeatedly running RSPO, we can quickly derive diverse strategies in just a few iterations. In order to strictly enforce the novelty constraints in policy optimization, we adopt rejection sampling instead of optimizing a soft objective, which is adopted by many existing methods by converting the constraints as Lagrangian penalties or intrinsic rewards. Specifically, RSPO only optimizes extrinsic rewards over trajectories that have sufficiently low likelihood w.r.t. the reference policies. Meanwhile, to further utilize those rejected trajectories that are not distinct enough, RSPO ignores the environment rewards on these trajectories and only optimizes diversity rewards to promote effective exploration. Intuitively, this process adaptively switches the training objective between extrinsic rewards and diversity rewards w.r.t. the novelty of each sampled trajectory, so we call it the Reward Switching technique.
We empirically validate RSPO collection of highly multi-modal RL problems, ranging from multi-target navigation (Mordatch & Abbeel 2018) and MuJoCo control (Todorov et al. 2012) in the single-agent domain, to stag-hunt games (Tang al. (021) and the StarCraft II Multi-Agent Challenge (SMAC) (Rashid et al., (019) in the multi-agent domain. Experiments demonstrate that RSPO can reliably and efficiently discover surprisingly diverse strategies in all these challenging scenarios and substantially outperform existing baselines. The contributions can be summarized as follows:
1. We propose novel algorithm, Reward- Policy Optimization, for continuously discovering diverse policies. The iterative learning scheme and reward-switching technique both significantly benefit the efficiency of discovering strategically different policies.
2. We propose to use cross-entropy-basee diversity metric for policy optimization and two additional diversity-driven intrinsic rewards for promoting diversity-driven exploration.
3. Our algorithm is both general and effective across variety of single-agent and multi-agent domains. Specifically, our algorithm is the first to learn the optimal policy in the stag- hunt games without any domain knowledge, and successfully discovers 6 visually distinet winning strategies via merely 6 iterations on a hard map in SMAC.
2 RELATED WORK
Searching for diverse solutions in a highly multi-modal optimization problem has a long history and various block- box methods have been proposed (Miller & Shaw 1996 Deb & Saha 2010 Kroese ct al. 2006). In reinforcement learning, one of the most popular paradigms is population based training with multi-objeccive optimization. Representative works include the family of qualitative diversity (QD) (Pugh et al. 2016) algorithms, such as MAP-Elites (Cully et al.) 2015). which are based on genetic methods and assume set of human-defined behavior characterizations, and policy- gradient methods (Ma et al. 2020 Tang et al., 22221), which typically assume a distribution of reward function is accessible. There are also some recent works that combine QD algorithms and policy gradient algorithms (Cideron et al., 2020: Nilsson & Cully 202T). The DvD algorithm (Parker- al. 2020b) improves QD by optimizing population diversity (PD), a KL-divergence- based diversity metric, without the need of hand-designed behavior characterizations. Similarly, Lupu et al. (2021) proposes to maximize trajectory diversity, i.e., the approximated lensen-Shannon divergence with action-discounting kernel, to train diversified population.
There are also works aiming to learn policies iteratively. PSRO (Lanctot et al. 2017) focuses on learning Nash equilibrium strategies in zero-sum games by maintaining strategy oracle and repeatedly adding best responses to it. Various improvements have been made upon PSRO by using different metrics promote diverse oracle strategies (Liu et al.] 2021 Nieves et al. 2021). Hong jet al.] (2018) utilizes the KL-divergence between the current policy and past policy version as an exploration bonus, while maximizing the diversity w.r. a fixed set of reference policies,
2

---

Published as a conference paper at ICLR 2022
which is more stable and will not incur cyclic training process. IiversityInnducing Policy Gradient (DIPG) (Masood & Doshi Velez 2019) utilizes maximum mean discrepancy (MMD) between policies soft learning objective to iteratively find novel policies. By contrast, our method utilizes a filtering-based objective via reward switching to strictly enforce all the diversity constraints, [Sun] al. (2020) adopts a conceptually similar objective by early terminating episodes that do not incur sufficient novelty. However, Sun et al. (2020) does not leverage any exploration technique for those rejected samples and may easily suffer from low sample efficiency in challenging RL tasks we consider in this paper. There is another concurrent work with an orthogonal focus, which directly optimizes diversity with reward constraints (Zahavy et al., 202T). We remark that enforcing a reward constraint can be problematic in multi-agent scenarios where different Nash Equilibrium can have substantially different pay-offs.. In addition, the ridge rider algorithm (Parker-Holder et al. 2020a) proposes to follow the eigenvectors of the Hessian matrix to discover diverse local optima with theoretical guarantees, but Hessian estimates can be extremely inaccurate in complex RL problems.
Another stream of work uses unsupervised RL to discover diverse skills without the use of environment rewards, such as DIYAN (Eysenbach et al. 2019) and DDLUS (Hartikainen et al, 2020). However, ignoring the reward signal can substantially limit the capability of discovering strategic behaviors. SMERL (Kumar et al. 2020) augments DIYAN with extrinsic rewards to induce diverse solutions for robust generalization. These methods primarily foeus learning low-level locomotion while tackle a much harder problem of discovering strategically and visually different policies.
Finally, our algorithm is also conceptually related to exploration methods (Zheng et al. 2018 Burda iet al. 2019 (Simmons-Edlie et al., 2201),, since it can even bypass inescapable local optima in challenging RL environments. Empirical comparisons can be found in Section emphasize that our paper tackles a much more challenging problem than standard RL exploration: we aim to discover as many distinct local optima as possible. That is, even if the global optimal solution is discovered, we still want to continuously seek for sufficiently distinct local- local-optimum strategies. We remark that such an objective particularly important for multi-agent games where finding all the Nash equilibria can be necessary for analyzing rational multi-agent behaviors (Tang et al., (021).
However, we
3 METHOD
3.1 PRELIMINARY
We consider environments that can be modeled Markov decision process (MDP) (Puterman 1994) M = (S. A, R. P.7) where S and A are the state and action space respectively, R(s, a) is the reward function, P(s'|s, s, a) is the transition dynamics and " is the discount factor. We consider a stochastic policy no paramterized by 0. Reinforcement learning optimizes the policy w.r.t. the expected return J(T) E (r 7'rz] over the sampled trajectories from n, where a trajectory denotes a sequence of state-action-rewaa can be naturally applied to multi-agent scenarios with homogencous agents with shared state and action space, where learning shared policy for all the agents will be sufficient.
triplets, i.c., = {(,,, a,, a;,rt) r.)]. Note that this formulation
Rather than learning a single solution for J(B), we aim to discover a diverse set of M policies, i.e, [T |1 < k S M). such that all of these polices are locally optimized under J(f) and mutually distinct w.r.t. some distance measure (T Taz) i.e.,
max J(O²) VI < < M, subject to D(TTE (())) 2 6, VI S @k
S M.
(1)
Here D(-,-) measures how different two policies are and is the novelty threshold. For conciseness, in the following content, we omit 0 and use n to denote the policy with parameter g²
3.2 ITERATIVE CONSTRAINED POLICY OPTIMIZATION
Directly solving Eq. ( suggests a population-base training paradigm, which requires a non-trivial optimization technique for the pairwise constraints and typically needs a large population size M. Herein, we adopt an iterative process to discover novel policies: in the k-th iteration, we optimize a single policy ne with the constraint that & is sufficiently distinct from previously discovered policies Ti...., Mh- Here, the term "iteration" is used to denote the process of learning a new policy. Formally, we solve the following iterative constrained optimization problem for iteration S k S M:
0g = arg max (0), subject to D(TO, mT) 2 6, VI s < k.
(2)
3

---

Published as a conference paper at ICLR 2022
Eq. reduces the iopulation-based objective standard constrained optimization problem for a single policy, which is much easier to solve. Such an iterative procedure does not require a large population size .M as is typically necessary in population-bas -bseed methods. And, in practice, only few iterations could result in a sufficiently diverse collection of policies. We remark that, in theory, directly solving the constraint problem in Eq. (2) may lead solution that is not local optimum w.r.t. the unconstrained objective (0). It is because a solution in Eq. (2) can be located on the boundary of the constraint space (i.e., (TT Ti) = 8), which is undesirable according our original goal. However, this issue can be often alleviated by properly setting the novelty threshold 8.
The natural choice for measuring the policy difference is KL divergence, as done in the trust-region constraint (Schulman et al.] 2015: 2017). However, in our setting where the difference between policies should maximized, using KI. as the diversity measure would inherently encourage learning policy with small entropy, which is typically undesirable in RL problems (see A detailed derivation). Therefore, we adopt the accumulative cross-entropy as our diversity measure, i.e.,
DiT., mz) = mT) = ETwT,
log TT (at 8x)
(3)
3.3 TRAJECTORY FILTERING FOR ENFORCING DIVERSITY CONSTRAINTS
popular approach solve the constrained optimization problem in Eq. (2) is to Lagrangian multipliers to convert the constraints to penalties in the learning objective. Formally, let B 3 be a set of hyperparameters, the soft objective for Eq. 22 is defined by
k-
Juon = ((Te) + Σ ())(
(4)
Such soft objective substantially simplifies optimization and is widely adopted in RL applications. However, in our setting, since cross-entropy is a particularly dense function, including the diversity bonus as part of the objective may largely change the reward landscape of the original RL problem, which could make the final solution diverge from a locally optimal solution w.r.t (Ø). Therefore, is often necessary to anneal the Lagrangian multipliers 8j. which is particularly challenging in our setting with a large number of reference policies. Moreover, since (TT, π;) estimated over the trajectory samples, it introduces substantially high variance to the learning objective, which becomes even more severe as more policies are discovered.
Consequently, we propose Trajectory Filtering objective to alleviate the issues of the soft objective. Let's use NLL(T: π) to denote the negative likeliieldhood of a trajectory 7 w.r.t. a policy т, i.e., NLL(T: m) - ((e log π [o,) st). We apply rejection sampling over the sampled trajectories 7 To such that we train on those trajectories satisfying all the constraints, i.e., NLL(T; myy) 2 8 for each reference policy Tÿ. Formally, for each sampled trajectory we define filtering function Φ(T). which indicates whether we want to reject the sample т, and use I[-] to denote the indicator function, and then the trajectory filtering objective (O) can be expressed
K-1
Jnteer (0) = ET ((T) Σ Tr
where d(T) = II (INL((TTTT)) 2 8). 3=1
(5)
We call the objective in Eq. a filtering objective. We show in App. G that solving Eq. (5) is equivalent to solving Eq. (2) with an even stronger diversity constraint. In addition, we also remark
that trajectory filtering shares a conceptually similar motivation with the clipping term in Proximal
Policy Optimization (Schulman et al. 2017).
3.4 INTRINSIC REWARDS FOR DIVERSITY EXPLORATION
The main issue in Eq. is that trajectory filtering may reject a significant number of trajectories, especially in the early stage of policy learning since the policy is typically initialized to the a random policy. Hence, it is often the case that most of the data in batch are abandoned, which leads to severe wasting of samples and may even break learning due to the lack of feasible trajectories.
Can make use of those rejected trajectories? We propose to additionally apply a movelty-driven objective on those rejected samples. Formally, we use (T( to denote whether т violates the constraint of nj. i.e., (T) [[NLL( nT) 2 8). Then have the following switching objective:
4

---

Published as a conference paper at ICLR 2022
switch = By
((T) Σ 7/r (1- (LL (T,
(6)
The above objective simultaneously maximizes the extrinsic return on accepted trajectories and the cross-entropy on rejected trajectories. It can be proved that solving Eq. (6) is also equivalent to solving Eq. 2 with a stronger diversity constraint (see App. G
Furthermore, Eq. (6) can be also interpreted as introducing additional cross-entropy intrinsic rewards on rejected trajectories (i.e., (T( 0). More specifically, given NLL(T: x) -Eer,aa)er log (a)]ss)), an intrinsic reward (st, Oe; Qy;Ty))) = - log (y(a st) applied each state-action pair (#t, (z) from every rejected trajectory т. Conceptually, this suggests an even more general paradigm for diversity exploration: we can optimize extrinsic rewards accepted trajectories while utilizing novelty-driver intrinsic rewards on rejected trajectories for more effective exploration, i.e, by encouraging the learning policy me to be distinet from a reference policy zjj.
Hence, we propose two different types of intrinsic rewards to promote diversity exploration: one is likelihood-based which directly follows Eq. (6) and focuses more on behavior novelty, and the other is reward- cattuuddrredittoo-baasesee which focuses more on achieving novel states and reward signals.
Behavior-driven exploration.
The behavior-driven intrinsic reward rinit is defined by int (a, 8; TTy) log iy |))
i..nnt encourages the learning policy to output different actions from those reference policies and "B therefore to be more likely to be accepted. Note that r can be directly interpreted as the Lagrangian penalty utilized in the soft objective (6).
Reward-driven exploration. A possible limitation of behavior-driven exploration is that it may overly focus on visually indistinguishable action changes rather than high-level strategies. Note that in RL problems with diverse reward signals. it is usually preferred to discover policies that can achieve different types of rewards (Simmons- Edler et al. 22020) Wang ct al. 2020). Inspired by the curiosity-drive exploration method (Pathak et al.] (017), we adopt model -ased approach for predicting novel reward signals. In particular, after obtaining each reference policy πj. we learn reward prediction function [ss az 4)2) trained by minimizing the expected MSE loss L(wy)
Ey-wyyt et (st, 445 tbyy rel3] over the trajectories generated by my. The reward prediction function f(s, a: eiy) is expected to predict the extrinsic environment reward more accurately on state-action pairs that are more frequently visited by T and less accurately on rarely visited pairs. To encourage reward-driven intrinsic reward TR (a, s; MT). Formally, given the transition triplet (st, a, rr), 'R (a, s; TTy) is defined by
policy exploration, we adopt the reward prediction error
(8) We remark that reward-driven exploration can be also interpreted as approximately maximizing the f-divergence of joint state occupancy measure between policies (Liu et al.) (022)). By combining these two intrinsic rewards together, we approximately maximize the divergence of both actions and states between policies to effectively promote diversity. By default, use behavior-dre driven intrinsic reward for computational simplicity and optionally augment with reward-driven intrinsic reward in more challenging scenarios (see examples in Section 4.2)
int (St, az ) = [s dri why) rrl?.
3.5 REWARD-SWITCHIN POLICY OPTIMIZATION
We define the RSPO function RSPO by
RSPO r = ((()r; + (1-10 = (a,,8) my))
where À is scaling hyper-parameter. Note that extrinsic rewards and intrinsic rewards are mutually exclusive, i.e., a trajectory r may be either included in Jiitering or be rejected to produce exploration bonuses. Conceptually, our method is adaptively "switching" between extrinsic and intrinsic rewards during policy gradients, which is so-called remark that the intrinsic reward will constantly push the learning policy towards the feasible policy space and the optimization objective will eventually converge to J(() when no trajectory is rejected.
Soward-Switching Policy Optimization (RSPO). We also
In addition the aforementioned RSPO algorithm, we also introduce two implementation enhance- ments for better empirical performances, especially in some performaace--sessitve scenarios.
5

---

Published as a conference paper at ICLR 2022
Automatic threshold selection. We provide an empirical way of adjusting 6. In some environments, is sensitive to each reference policy. Instead of tuning 8 for each reference policy, we choose its corresponding threshold by ò, task-specific hyperparameter. We remark that a is constant parameter across training iterations and is much easier to choose than manually tuning 6, which requires subtle variation throughout multiple training iterations. We use automatic threshold selection by default. Detailed values of a and the methodology of tuning a can be found in App. D.I and App. B.3 respectively.
D( ;Ty), where nnd is a fully random policy and is
Smoothed-switching for intrinsic rewards. Intrinsic rewards have multiple switching indicators, ie., Ø1..... OK-1- Moreover, for different trajectories, different subsets of indicators will be turned on and off, which may result in varying scale of intrinsic rewards and hurt training stability. Therefore, cases, we propose a smoothed switching mechanism which could further in some constraint-sensee
improve practical performance. Specifically, we maintain a running average 6, over all the sampled trajectories for each indicator (T) and use these smoothed indicators compute intrinsic rewards defined in Eq. (9). mmoothed-switching empirically improves training stability when a large number of reference policies exist, such as stag-hunt games (see Section 4.2)
EXPERIMENTS
To illustrate that our method can be applied to general RL applications, we experiment on 4 do- mains that feature multi-modality of solutions, including a single-agent navigation problem in the warddcle-world (Mordatch & Abbeel 2018). 2-agent Markov stag-hunt games (Tang et al.. [02II) continuous control in MuJoCo (Todoroy et al. (012). and the StarCraft II Multi-Agent Challenge (SMAC) (Vinyals al. 2017 Rashid al. 2019). J. In particle world and stag-hunt games, all the local optima can be precisely calculated, so we can quantitatively evaluate the effectiveness of different algorithms by measuring how many distinct strategy modes are discovered. In MuJoCo control and SMAC, we qualitatively demonstrate that our method can discover a large collection of visually distinguishable strategies. Notably, we primarily present results from purely RL-based methods which do not require prior knowledge over possible local optima for a fair comparison. We also remark that when a precise feature descriptor of local optima is feasible, it is also possible to apply evolutionary methods (Nilsson& & Cully, 2021) to a subset of the scenarios we considered. For readers of further interest, a thorough study with discussions can be found in App. B.4
Our implementation is based on PPO (Schulman et al. (017)) on a desktop machine with one CPU and one NVIDIA RTX3090 GPU. All the algorithms are run for the same number of total environment steps and the same number of iterations (or population size). More details can be found in appendix.
4.1 SINGLE-AGENT PARTICLE- WORLDD ENVIRONMENT
We consider a sparse-reward navigation scenario called 4-Goals (Fig. [ The agent starts from the center and will receive a reward when reaching a landmark. We set up difficulty levels. In the easy mode, the landmark locations are fixed. In the medium mode, the landmarks randomly placed. In the hard mode, landmarks are not only placed randomly but also have different sizes and rewards. Specifically, the sizes and rewards of each landmark are 2x, 1x, 0.5x, 0.25x and 1x, 1.1x, 1.2x, 1.3x of the normal one respectively. We remark that in the hard mode, the landmark size decreases at an exponential rate while the reward gain is only marginal, making it exponentially harder to discover policies towards those smaller landmarks. We compare RSPO with several baselines, including PPO with restarts (PG), Diversity-Inducin population-based training with cross-entropy objective (PBT-CE), DvD (Parker-Holder et al.
(a) Easy
(b) Medium
(c) Hard
Figure I: The agent (orange) and land- marks (blue) in 4-Goals.
Policy Gradient (DIPG) (Masood & Doshi- Velez
2019
2020b
SMERL (Kumar al.) 2020). and Random Network Distillation (RND) (Burda et al./ 2019) designed to explore the policy with the highest reward, so we only evaluate RND in the hard mode.
RND
The number of distinct local optima discovered by different methods is presented in Fig. 2a RSPO consistently discovers all the 4 modes within 4 iterations even without the use of any intrinsic rewards over rejected trajectories (i.e., r!t 0). DIPG finds 4 strategies in 4 out of the 5 runs in the easy mode but performs no better than PG in the two harder modes. Fig. sblshows the highest expected return achieved over the policy population in the hard mode. RSPO is the only algorithm that
6

---

Published as a conference paper at ICLR 2022
Gistirct strategies found
Bode
mode red
mode hard
1.4
1.3
PG
3-
DIPG
RSPO
SMURL
2.
PBT-CE
PBT-0v0
0.3
0.1
Iterations
A Lttrations
Iterations
(a) Mean number of distinct strategies found on 4-Goals.
(b) Rewards hard mode.
Figure 2: Experiment results on 4-Goals for M = 7 iterations averaged over 5 random seeds. Error bars are 95% confidence intervals.
edge strategies
edge stranegies
corner strategies
200
153
eating apples
chasing monster
Figure 4: Different strategies found in run of 20 iterations diversity setting RSPO in Monster-Humt, We plot the heatmap of the two agents' meeting point to indicate the type of the found strategies.
successfully learns the optimal policy towards the smallest ball. We also report the performance of RSPO optimizing the soft objective Eq. {4) with the default behavior-driven intrinsic reward int (no-switch), which was able to discover the policy towards the second largest landmark. Comparing no-switch with r!" 0, we could conclude that the fittring-basee objective can be critical for RSPO to discover sufficiently different modes. We also remark that the nu-switch variant only differs from DIPG by the used diversity metric. This suggests that environments with high state variance (e.g. landmarks with random sizes and positions), state-based diversity metric may be less effective.
4.2 2-AGENT MARKOV STAG-HUNT GAMES
We further show the effectiveness of RSPO on two grid-world stag-hunt games developed in 'Tang al. (2021), Monster-Hunn and Escalation, both of which have very distinct Nash Equilibria (NEs) for self-play RL methods to converge to. Moreover, the optimal NE with the highest rewards for both agents in these games are risky cooperation, i.e., big penalty will be given an agent the other agent stops cooperation. This makes most self-play RI algorithms converge to the safe non-cooperative NE strategies with lower rewards. It has been shown that none of the ttte-oof-the-rr exploration methods can discover the global optimal solution without knowing the underlying reward structure (Tang et al. (021). We remark that since there are enormous NEs in these environments shown in Fig, and 7b] population-based methods (PBT) require significantly large population size for meaningful performances, which is computationally too expensive to run. Therefore, do not include the results of PBT baselines. We also apply the smoothed switching heuristic for RSPO in this domain. Environment details can be found in App.
Ageni
Applo-
Agen22
Monder
Figure 3: Monster-Humt
The Monster-Hunt game. The Monster-Hunt game (Fig. 3) contains a monster and two apples. When single agent meets the monster, it gets a penalty the same time, they "cctcc"" the monster and both get bonus of 5. When player meets apple, it gets a bonus of 2. The optimal strategy, i.c., both agents move towards the monster, a risky cooperative NE since agent will receive penalty if the other agent deceives. The non-cooperative NE for eating apples is safe NE and easy to discover but has lower rewards.
22 When both agents meet the monster
We adopt both behavior driven and soward-driven intrinsic rewards in RSPO to tackle Monster- Humt. Fig. Iillustrates all the discovered strategies by RSPO over 20 iterations, which covers a wide range of human- human-interpretable strategies, including the non-cooperative apple-eating strategy well the
7

---

Published as a conference paper at ICLR 2022
Table 1: Types of strategies discovered by each methods in Comster-Humt over 20 iterations.
180%
accoptance ratio
Apple
Corner
Edge
Chase
68%
ASP0
RSPO
20%
No switch
Ablation
No r
0.8
0.4
B only
V
Figure 5: Sample acceptance ratio when learning a policy distinct from Apple NE. The intrinsic reward critical.
RPG
Baseline
MAVEN
PG/DIPG/RND
distinct stratopies
Agen1
DIP6
DIPG
grid
40
RMD
Next
RSPO
RSPO
Ii grid
RSPO: smooth
Agm22
0-
franes (1e6)
Figure 6: Escalation:
(a) Reward iteration
(b) Number distinct strategics found.
two agents need to keep stepping the light si- multancously.
Figure 7: Results on Excalation averaged over 3 random seeds. Shaded area and error bars are 95% confident intervals.
optimal strategy, where both two agents stay together and chase the monster actively. By visualizing the heatmap of where both agents meet, we observe a surprisingly diverse sub-optimal cooperation NEs, where both agents move corner or an edge simultaneously. keep staying there, and wait for the monster coming. We remark that due to the existence of such great number of passive waiting strategies, which all have similar accumulative environment rewards and states, it becomes critical to include the reward-driven intrinsic reward to quickly bypass them and discover the optimal solution.
We perform ablation studies on RSPO by turning off reward switching (No Switch) or intrinsic reward (No pd")) or only using the behavior-driven intrinsic reward (rit only), and evaluate the performances of many baseline methods, including vanilla PG with restarts (PG), DIPG, RND, popular multi- agent exploration method MAVEN (Mahajan al. 2019) and wwwrrdrrandoizee policy gradient (RPG) (Tang et al. 2021). We summarize the categories of discovered strategies by all these base in Table Apple denotes the con-coopeeative apple-eating NE; Chase denotes the optimal NE where both agents actively chase the monster; Corner and Edge denote the sub-optimal cooperative NE where both agents passively wait for the monster corner an edge respectively. Regarding the baselines, PG, DIPG, and RND never discover any strategy beyond the non-cooperative Apple NE. For RPG, even using the domain knowledge change the reward structure of the game, never discovers the Edge NE. Regarding the RSPO variants, both reward switching and intrinsic rewards are necessary. Fig. shows that when the intrinsic reward turned off, the proportion of accepted trajectories per batch stays low throughout training. This implies that the learning policy failed to escape the infeasible subspace. Besides, as shown Table I using behavior-driven exploration alone fails to discover the optimal NE, which suggests the necessity of reward-driven exploration to maximize the divergence of both states and actions in problems with massive equivalent local optima.
The Escalation game. Escalation (Fig. 6 requires the two players to interact with a static light. When both players step on the light simultaneously, they both receive a bonus of 1. Then the light moves to random adjacent grid. The game continues only if both players choose to follow the light. If only one player steps on the light, it receives a penalty of -0.97, where I, the number of previous cooperation steps. For each integer L, there is corresponding NE where both players follow the light for steps then simultaneously stop cooperation. We run RSPO with both diversity-drive intrinsic rewards and compare it with PG, DIPG, RND and RPG. Except for RPG, none of the baseline methods discover any cooperative NEs while RSPO directly learns the optimal cooperative NE (i.e., always cooperate) in the second iteration shown in Fig. 7a We also measure the total number of discovered NEs by different methods over 10 iterations in Fig. 7b Due to the existence of many spiky local optima, the smoothed-switchiene technique can be crucial here stabilize the
8

---

Published as a conference paper at ICLR 2022
Table 2: Population Diversity scores in MuJoCo.
Table 3: Number of visu- ally distinct policies over
4 iterations in SMAC.
H.-Cheetah
Hopper
Walker2d
Humanoid
PG
0.033 (0.013)
0.418 (0.125)
0.188 (0.079)
0.965 (0.006)
206428
2m1
DIPG
0.051 (0.009)
0.468 (0.054)
0.179 (0.056)
0.996 (0.000)
PG
2
2
PBT-CE
0.160 (0.078)
0.620 (0.294)
0.512 (0.032)
0.999 (0.000)
DIPG
2
2
DvD
0.275 (0. 164)
0.656 (0.523)
0.542 (0.103)
1.000 (0.000)
PBT-CE
2
3
SMERL
0,003 (0.002)
0.674 (0.389)
0.669 (0.152)
N/A
TrajDiv
3
RSPO
0.359 (0.058)
0.989 (0.009)
0.955 (0.039)
0.999 (0.000)
RSPO
4
4
training process. We remark that even without the smoothed-switchig technique, RSPO achieves comparable performance with RPG - note that RPG requires a known reward function while RSPO does not assume any environment-speccfii domain knowledge.
4.3 CONTINUOUS CONTROL IN MuJoCo
We evaluate RSPO in the continuous control domain, including Half-Cheetah, Hopper, Walker2d and Humanoid, and compare it with baseline methods including PG, DIPG, DvD (Padker-Holder itt al. (0205)) SMERL (Kumar et al., 2020) and population- based training with our cross- objective (PBT-CE). All the methods are run over 5 iterations (a population size of 5, or have a latent dimension of 5) across 3 seeds. We adopt Population Diversity, a determinant-based diversity criterion proposed in Parker-Holder et al. (2020b), to evaluate the diversity of derived policies by different methods. Results are summarized in Table 2 where RSPO achieves comparable performance in Hopper and Humanoid and substantially outperforms all the baselines in Half- CalffChhetahh and Walker2d. We remark that even with the same intrinsic reward, vopulation-based training (PBT-CE) cannot discover sufficiently novel policies compared with iterative learning (RSPO). In Humanoid, SMERL achieves substantially lower return than other baseline methods and we don't 't report the population diversity score (more details can be found in App. (B.6). We also visualize some interesting emergent behaviors RSPO discovered for Half-Cheetah and Hopper in App. B. where different strategy modes discovered by RSPO are visually distinguishable while basclines methods often converge to very similar behaviors despite of the non-zero diversity score.
4.4 STACRAFT MULTI-AGENT CHALLENGE
We further apply RSPO to the StarCraft II Multi- Challenge (SMAC) (Rashid al., 2019). which is substantially more difficult due to partial observability, long horizon, and complex state/action space. We conduct experiments both of which have heterogeneous unit types leading to a multi-modal solution space. Baseline methods include PG. DIPG, PBT-CE and trajectory diversity (TrajDiv) (Lupu et al. 202T]. SMERL algorithm and DvD algorithm are not included because they were originally designed for continuous control domain and not suitable for SMAC (see App. B.6land App. [B.2.2p. Instead, we include the
2 maps, an easy map 2m_vs_lz and hard map 2c_vs________________________2 1c__v________ vs_64zg,
TrajDiv algorithm (Lupu et al., 2021) as an additional baseline, which was designed for cooperative multi-agent games. We compare the number of visually distinct policies by training a population of 4 (or for 4 iterations), as shown in Table While PBT-based algorithms tend to discover policies with slight distinctions, RSPO can effectively discover different winning strategies demonstrating intelligent behaviors in just few iterations consistently across repetitions. We remark that there may not exist an appropriate quantitative diversity metric for such a sophisticated MARL game in the existing literature (see App. B.2.2). Visualizations and discussions can be found in App. B.
5 CONCLUSION
We propose Reward-Switching Policy Optimization (RSPO), a simple, generic, and effective iter- ative learning algorithm that can continuously discover novel strategies. RSPO tackles novelty- constrained optimization problem via adaptive switching between extrinsic and intrinsic rewards used for policy learning. Empirically, RSPO can successfully tackle wide range of challenging RL domains under both single-agent and multi-agent settings. We leave further theoretical justifications and sample efficiency improvements future work.

---

Published as a conference paper at ICLR 2022
REFERENCES
Bowen Baker, Ingmar Kanitscheider, Todor Markov, Yi Wu, Glenn Powell, Bob McGrew, and Igor Mordatch. Emergent tool use from multi-agent autocurricula. International Conference on Learning Representations, 2020.
Nolan Bard, Jakob Foerster, Sarath Chandar, Neil Burch, Mare Lanctot, H Francis Song, Emilio Parisotto, Vincent Dumoulin, Subhodeep Moitra, Edward Hughes, et al. The hanabi challenge: A new frontier for ai research. Artificial Intelligence, 280: 180:10 2020.
Yuri Burda, Harrison Edwards, A. Storkey, and Oleg Klimov. Exploration by random network distillation. ICLR, 2019.
Junyoung Chung, Caglar Gulcehre, KyungHyun Cho, and Yoshua Bengio. Empirical evaluation of gated recurrent neural networks on sequence modeling. arXiv preprint arXiv:1412.3555 2014.
Geoffrey Cideron, Thomas Pierrot, Nicolas Perrin, Karim Beguir, and Olivier Sigaud. Qd-rl: Efficient
mixing of quality and diversity in reinforcement learning. arXiv preprint wwXiv:2006.08505 2020.
Antoine Cully, Jeff Clune, Danesh Tarapore, and Jean- Cann-Bapistte Mouret. Robots that can adapt like animals. Nature, 521(7553):503-507 2015.
K. Deb and Amit Saha. Finding multiple solutions for multimodal optimization problems using a multi-objective evolutionary approach. In GECCO '10, 2010.
Benjamin Eysenbach, A. Gupta, J. Ibarz, and Sergey Levine. Diversity is all you need: Learning skills without reward function. ICLR, 2019.
Scott Fujimoto, Herke Hoof, and David Meger. Addressing function approximation error in actor- critic methods. In International Conference on Machine Learning, pp. 1587-1596. PMLR, 2018.
Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor. In International conference machine learning, pp. 1861-1870. PMLR, 2018.
Kristian Hartikainen, Xinyang Geng, T. Haarnoja, and Sergey Levine. Dynamical distance learning for sepi-super and unsupervised skill discovery. ICLR, 2020.
Zhang-Wez Wei Hong, Tzu-Yur Yun Shann, Shih- Yang Su, Y. Chang, and Chun-Yo Yi Lee. Diversity-driven exploration strategy for deep reinforcement learning. 2018.
Max Jaderberg, Wojciech M Czarnecki, lain Dunning, Luke Marris, Guy Lever, Antonio Garcia Castaneda, Charles Beattie, Neil C Rabinowitz, Ari S Morcos, Avraham Ruderman, al. Human- level performance in 3d multiplayer games with population-based reinforcement learning. Science, 364(6443):859-85, 2019.
Dirk P. Kroese, S. Porotsky, and R. Rubinstein. The cross-entropy method for continuous multi- extremal optimization. Methodology and Computing in Applied Probability, 8:383-407, 2006.
Saurabh Kumar, Aviral Kumar, Sergey Levine, and Chelsea Finn. One solution is not all you need: Few-shot extrapolation via structured maxent rl. Advances in Neural Information Processing Systems, 33, 2020.
Mare Lanctot, V. Zambaldi, A. Gruslys, A. Lazaridou, K. Tuyls, J. Pérolat, D. Silver, and T. Graepel. unified gaee-the approach to multiagent reinforcement learning. In NIPS, 2017.
Jiwei Li, Will Monroe, Alan Ritter, Dan Jurafsky, Michel Galley, and Jianfeng Gao. Deep rein- forcement learning for dialogue generation. In Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing, pp. 1192- 2016.
Siqi Liu, G. Lever, J. Merel, Tunyasuvunakool, N. Heess, and T. Graepel. Emergent coordination through competition. 2019.
10

---

Published as a conference paper at ICLR 2022
Xiangyu Liu, Hangtian Jia, Ying Wen, Yaodong Yang. Yujing Hu, Yingfeng Chen, Changjie Fan, and Zhipeng Hu. Unifying behavioral and response diversity for open-endee ended learning in zero-sum games. arXiv preprint 106.:220..04998, 2021.
Andrei Lupu, Brandon Cui, Hengyuan Hu, and Jakob Foerster. Trajectory diversity for zero-shot coordination. In International Conference on Machine Learning, pp. 7204-7213, PMLR, 2021.
Pingchuan Ma, Tao Du, and Wojeiech Matusik. Efficient continuous pareto exploration multi-task learning. In International Conference Machine Learning, pp. 6522 6531. PMLR, 2020.
Tengyu Ma. Why do local methods solve nonconvex problems? Beyond the Worst- Analysis of Algorithms, pp. 465, 2020.
Anuj Mahajan, Tabish Rashid, Mikayel Samvelyan, and S. Whiteson. Maven: Multi-agent variational exploration. In NewrIPS, 2019.
M. A. Masood and Finale Doshi- discrepancy to find a set of diverse policies. 2019.
diversity-inducin policy gradient: Using maximum mean
B. Miller and Michael Shaw. Genetic algorithms with dynamic niche sharing for multimodal func- tion optimization. Proceedings of IEEE International Conference on Evolutionary Computation, pp. 786-791, 1996.
Igor Mordatch and P. Abbeel. Emergence of grounded compositional language in multi-agent populations. In AAAI, 2018.
Nicolas Perez Nieves, Yaodong Yang, Oliver Slumbers, David Mguni, and Jun Wang. Modelling behavioural diversity for learning in open-ended games. ICML, 2021.
Olle Nilsson and Antoine Cully, Policy gradient assisted map-elites. In Proceedings of the Genetic and Evolutionary Computation Conference, pp. 866-875 2021.
Shayegan Omidshafiei, Karl Tuyls, Wojeiech M Czarnecki, Francisco C Santos, Mark Rowland, Jerome Connor, Daniel Hennes, Paul Muller, Julien Pérolat, Bart De Vylder, et al. Navigating the landscape of multiplayer games. Nature communications, 1 11(1):1-17, 20200.00......
Jack Parker-Holdde Holder, Luke Metz, Cinjon Resnick, H. Hu, A. Lerer, Alistair Letcher, Alexander Peysakhovich, Aldo Pacchiano, and Jakob Foerster. Ridge rider: Finding diverse solutions by following eigenvectors of the hessian. NeurIPS, 2020a.
Jack Parker-Holder, Aldo Pacchiano, Krzysztof Choromanski, and Stephen Roberts. Effective diversity in population- based reinforcement learning. NeurIPS, 2020b.
Deepak Pathak, Pulkit Agrawal, Alexei A Efros, and Trevor Darrell. Curiosity-driven exploration by self-supervised prediction. In International Conference Machine Learning, pp. 2778-2787.
PMLR, 2017.
Tiago Pereira, Maryam Abbasi, Bernardete Ribeiro, and Joel P. Arrais. Diversity oriented deep reinforcement learning for targeted molecule generation. Journal of Cheminformatiic, 13(1):21, Mar 2021. ISSN 2946. doi: 10.1 10.1188/113321--01-000494
URL/xtts::/ddi..oom
10. 11 86/ 8 3321 021 004 98-2
Justin K. Pugh, L. B. Soros, and K. Stanley. Quality diversity: A new frontier for evolutionary computation. Frontiers Robotics AI, 3:40, 2016.
M. Puterman. Markov decision processes: Discrete stochastic dynamic programming. In Wiley Series in Probability and Statistics, 1994.
Tabish Rashid, Philip HS Torr, Gregory Farquhar, Chia-Man Hung, Tim GJ Rudner, Nantas Nardelli, Shimon Whiteson, Christian Schroeder de Witt, Jakob Foerster, and Mikayel Samvelyan. The Star- craft multi-agent challenge. volume 4, pp. 2186-2188. International Foundation for Autonomous Agents and Multiagent Systems, 2019.
John Schulman, Sergey Levine, Abbeel, Michael Jordan, and P. Moritz. Trust region policy optimization. ICML, 2015.
11

---

Published as a conference paper at ICLR 2022
John Schulman, F. Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. ArXiv, abs/1707.063477 2017.
Riley Simmons-Edler, Ben Eisner, Daniel Yang, Anthony Bisulco, Eric Mitchell, Sebastian Seung, and Daniel Lee. Qxplore: Q-learning exploration by maximizing temporal difference error. 2019.
Riley Simmons-Edler, Ben Eisner, Daniel Yang, Anthony Bisulco, Eric Mitchell, Sebastian Seung. and Daniel Lee. Reward prediction error as exploration objective in deep rl. In Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI-20, pp. 2816-2825, 2823, 2020.
Hao Sun, Zhenghao Peng, Bo Dai, Jian Guo, Dahua Lin, and Bolei Zhou. Novel policy seeking with constrained optimization. arXiv preprint arXiv:2005. 2020.
Zhenggang Tang, C. Yu, Boyuan Chen, Huazhe Xu, Xiaolong Wang. Fei Fang. S. Du, Yu Wang, and Yi Wu. Discovering diverse multi-agent strategic behavior via reward randomization. ICLR, 2021.
E. Todorov, T. Erez, and Y. Tassa. Mujoco: A physics engine for model-based control. 2012 IEEE/RSJ International Conference Intelligent Robots and Systems, pp. 5026-5033, 2012.
Oriol Vinyals, Timo Ewalds, Sergey Bartunov, Petko Georgiev, Alexander Sasha Vezhnevets, Michelle Yeo, Alireza Makhzani, Heinrich Küttler, John Agapiou, Julian Schrittwieser, et al. Starcraft ii: A new challenge for reinforcement learning. arXiv preprint w7Xiv:1708.04782, 2017
Oriol Vinyals, Igor Babuschkin, Wojeiech M Czamecki, Michaël Mathieu, Andrew Dudzik, Junyoung Chung, David H Choi, Richard Powell, Timo Ewalds, Petko Georgiev, et al. Grandmaster level in StarCraft II using multi -agett reinforcement learning. Nature, 575(7782)3350-3555 2019.
Rui Wang, Joel Lehman, Jeff Clune, and Kenneth O Stanley. Poet: open-ended coevolution of environments and their optimized solutions. In Proceedings of the Genetic and Evolutionary Computation Conference, pp. 142-151, 2019.
Tonghan , Jianhao Wang*. Yi Wu, and Chongjie Zhang. Influence- based multi-agent explo- ration. In International Conference Learning Representations, 2020.
Chao Yu. Akash Velu, Eugene Vinitsky, Yu Wang, Alexandre Bayen, and Yi Wu. The surprising effectiveness of mappo in cooperative, multi-agent games. arXiv preprint arXiv:2103.01953 2021.
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.00665 00069, 2021.
Stephan Zheng, Alexander Trott, Sunil Srinivasa, Nikhil Naik, Melvin Gruesbeck, David C Parkes, and Richard Socher. The Al economist: Improving equality and productivity with AI-driven tax policies. arXiv preprint arXiv:2004. 13332, 2020.
Zeyu Zheng, Junhyuk Oh, and Satinder Singh. On learning intrinsic rewards for policy gradient methods. Advances in Neural Information Processing Systems, 31:4644 4654, 2018.
12

---

Published as a conference paper at ICLR 2022
A
GIF DEMONSTRATIIONS ON MUJoCo AND SMAC
See
B ADDITIONAL. RESULTS
B.1 VISUALIZATION DISCOVERED STRATEGIES
B.1.1 MUJoCo
(a) Normal running
(a) Normal hopping
(b) Charged hopping
(b) Handstand running
(c) Upside-down running
(c) Small-step hopping
(d) Kneeling
Figure 8: Half- Cheethhh behaviors.
Figure 9: Hopper behaviors.
(a) Normal running
(a) feet mincing
(b) Jumping
(b) Striding
(c) Striding running
(c) Hand-helped balancing
Figure 10: Walker behaviors.
Figure 11: Homanoid behaviors.
B.1.2 SMAC
We present screenshots of emergent strategies in the SMAC environment in Fig. 14 and Fig. 15 for _s_ /2_ respectively. We expect different emergent strategies to be both visually distinguishable and human-intte iittmam--itterretable. The strategies induced by baseline methods and RSPO are summarized in Table Table
25_64zg and 2m_vs_ vs 2c_vs_
2c
On the hard map 2c_ 20_vs_64222 642g. agents need to control the 2 colossi to fight against 64 zergs. The colossi have wider attack range and can step over the cliff. Fig. 14alshows aggressive strategy
13

---

Published as a conference paper at ICLR 2022
where the two colossi keep staying together on the left side of the cliff to fire at all the coming enemies. Fig. [1b]shows a particularly intelligent strategy where the colossi make use of the terrain to play hit-and-run. When the game starts, the colossi stand the cliff to snipe distant enemies to make them keep wandering around under the cliff. Hence, as the game proceeds, we can observe that the enemies are clearly partitioned while the colossi always maintain smart fire position on the cliff. Fig. [4c]shows a mirror strategy similar to Fig. to aggressively clean up incoming enemies from the right side. Fig. [4d shows a conservative strategy that the colossi stand still in the corner to keep minimal contact with the enemies, and thus minimize damages received from enemies. Fig. [4c] shows another smart strategy: one colossi blocks all incoming enemies on the mountain pass as a fire attractor, while the other one hides behind the fire attractor and snipes enemies distantly. We can see from the last two frames that the distant sniper does not lose any health points in late stages. In Fig. [41 one colossi (#1 I) actively take advantage of the terrain to walk along the cliff, such that enemies on the plateau must run around to attack it. In the mean time, the colossi helps its teammate by sniping distant enemies. Finally, they separately clean up all the remaining enemies for the win.
On the easy map 2m 2m_vs_l_ agents need to control 2 marines to defeat a Zealot. The marines can shoot the Zealot in distant position but the Zealot can only perform dlse-rangge attacks. In Fig. 15a the marines swing horizontally to keep an appropriate fire distance from the Zealot. In Fig. 15b the marines perform a parallel hit-and-run from top to bottom as the Zealot approaches. In Fig. 15c the right-side marine stands still, and the left-side marine swings vertically to distract the Zealot. In the two marines alternatively perform hit-and-run from bottom to top to distract the Zealot.
Fig. 15d
Table 4: Strategies induced by baseline methods and RSPO in SMAC map 2c_vs_642g
Algorithm
Strategies
PG DIPG PBT-CE TrajDiv
left wave cleanup, right wave cleanup cliff walk, corner
left wave cleanup, right wave cleanup fire attractor and distant sniper, cliff walk, right wave cleanup
left wave cleanup, cliff sniping and smart blocking, right wave cleanup corner, fire attractor and distant sniper, cliff walk
RSPO
Table 5: Strategies induced by bascline methods and RSPO in SMAC map 2m vs 1z.
Algorithm
Strategies
PG
parallel hit-and-run, alterative distraction parallel hit-and-run, one-sided swinging
DIPG
PBT-CE
one-sided swinging, paralle-hittand-- swinging parallel hit-and-run
TrajDiv
RSPO
one-sided swinging, parallel-hit hit-and-rum run, swinging, alterative distraction
B.2
QUANTITATIVE EVALUATION
B.2.1 MuJoCo
The final performance of MuJoCo environments is presented in Table 6 As mentioned in Ap- pendix C,3, in our implementation we fix the episode length to 512 so that the diverse intrinsic rewards can be easily computed, which may harm sample efficiency and the evaluation score. More- over, we use a hidden size of 64 which is usually smaller than previous works (which is 256 in the SAC paper (Haarnoja et al. 2018)). Hence, these results may not be directly compared with other numbers in the existing literature. However, the policy in Iter #1 is obtained by vanilla PPO and can therefore be used to assess the relative performances of other runs. Note that even if the presented scores are not the state-of-the of-the-art, visualization results show that our algorithm successfully learns the basic locomotion and diverse gaits in these environments. The results indeed demonstrate diverse local optima that are properly discovered by RSPO, including many interesting emergent behaviors
14

---

Published as a conference paper at ICLR 2022
Table 6: Final evaluation performance of RSPO averaged over 32 episodes in MuJoCo continuous control domain. Averaged over 3 random seeds with standard deviation in the brackets.
Environment
Iter #1
Iter #2
Iter #3
Iter #4
Iter #5
Shef-Chhetth
2343 (882)
1790 (950)
1710 (1394)
859 (498)
1194 (640)
Hopper
1741 (56)
1690 (29)
1428 (322)
1349 (275)
841 (296)
Walker2d
1668 (284)
1627 (228)
1258 (538)
1275 (342)
1040 (318)
Homanoid
3146 (26)
3148 (140)
3118 (84)
3072 (76)
2707 (860)
Table 7: Final evaluation winning rate of RSPO averaged over 32 episodes in SMAC.
Map
Iter #1
Iter #2
Iter #3
Iter #4
Iter #5
Iter#6
2c_vs_642g
100%
84.4% 100%
96.9%
100%
87.5% N/A
100%
2m_vs_la
100%
100%
100%
N/A
that may have never been reported in the literature (check the website in Appendix A for details), which accords with our initial motivation.
B.2.2 SMAC
Final evaluation winning rate of SMAC is presented in Table 7 The final performance of RSPO on the easy map 2m_vy_ matches the state-of-the-art YYu et al. 2021). The median evaluation winning rate and standard deviation on the hard map 2c_vs_ v__62gg is 98.4% (6.4%). which is slightly lower than the state-of-the- 100%((). We note that the policies discovered by our algorithm are both diverse and high-quality winning strategies (local optima) showing intelligent emergent behaviors.
We note that population diversity, which we use for quantitative evaluation for MuJoCo, may not be an appropriate metric for such sophisticated MARL game with large state space and a long horizon. Diversity via Determinant or Population Diversity "Parker-Holder et al. 2020b) is originally designed for the continuous control domain. It mainly focuses on the continuous control domain and directly adopts the action as action embedding, while it remains unclear how to embed a discrete action space. For SMAC, adopt the logarithm probability of categorical distribution the action embedding and evaluate RSPO and selected baselines using Population Diversity on the hard map 2c 2c_vs_ co_v__64z 64zg. We further train DvD with a population size of 4 as an additional baseline. The results are shown in Table 8 The population diversity scores of baseline methods and RSPO both reach the maximum value of T.000. However, if we visualize all the learned policies, actually many policies induced by PBT-CE or DvD cannot be visually distinguished by humans. Moreover, policies induced by PG are visually identical but still achieve a population diversity score 0.981. This indicates that high population diversity scores might not necessarily imply diverse strategy pool in complex environments like SMAC. We hypothesize that this is due to complex game dynamics in SMAC. For example, unit performing miero-strategies of attack-then then-move and move-then-attade the same for humans but will have very different action probabilities each timestep. Such subtle changes in policy outputs can significantly increase the population diversity scores. Since high scores may not directly reflect more diverse policies, it may not be reasonable to explicitly optimize population diversity as an auxiliary loss in SMAC. Therefore, we omit the results of DvD in SMAC in the main body of our paper.
visually
Table 8: Population Diversity on the hard map 2c_v8_64zg in SMAC.
Algorithm
# Distinct Strategies
Population Diversity
PG
1
0.981
PBT-CE
2
1,000
DvD
3
1.000
RSPO
4
1.000
15

---

Published as a conference paper at ICLR 2022
Data Efficiency
Winning rale
0.6
8-
alpham0.5
alpha=1
lembdaR-0.2
alpha=1.5
lambdaR==000
alpha=2
lambdaR-0.0
Training Update Steps
Training Update Steps
Figure 12: Humanoid.
Data efficiency with different a in
Figure 13: Learning curve with different Xint on the 2m_ vs 1a map in SMAC.
Population Diversity
Agrat
Population Diversity
0.5
0.604
0.5
0.640
1.0
0.676
1.0
0.621
1.5
0.687
5.0
0.697
2.0
0.748
10.0
0.697
Table 9: Population Diversity scores of the first policies with different hyperparameters in Humanoid. We have scaled the denominator of the RBF kernel in the Population Diversity matrix by a factor 10, such that the difference can be demonstrated more clearly.
To the best of our knowledge, a commonly accepted policy diversity metric for complex MARL games remains an open question in the existing literature. In our practice, rendering and visualizing the evaluation trajectories remains the best approach distinguish different learned strategies. We emphasize that qualitatively, we are so far the first paper that ever reports such a visually diverse collection of winning strategies hard map in SMAC. Please check website for policy visualizations (see Appendix A).
B.3 SENSITIVITY ANALYSIS
We have performed a sensitivity analysis over int and Xir since they are the critical to the performance RSPO. The default values used in our experiments can be found in Table 12
is the most important hyperparameter in RSPO because it determines what trajectories in a batch to be accepted. We focus on the data efficiency, i.e., the proportion of accepted trajectories in batch. In the sensitivity analysis, we run the second iteration of RSPO in Humanoid with a = 0.5, 1.0, 1.5, 2 respectively and compute the population diversity score of the 2 resulting policies. The result shown in Fig. 12 and the left part of Table The result accords with our heuristic to adjust o: with small a (a 0.5), RSPO may accept all the trajectories at the beginning and lead to similar policy after convergence, which is better than the PG baseline; with large (a = 1.5 and RSPO may reject too many trajectories at the early stage of training and spend quite lot time on exploration, which sacrifices training time for the gain in the diversity score. In practice, starting with a = and adjusting it such that the acceptance rate can drop at the start of training and then quickly and smoothly converge decreased if too much data is rejected at the beginning of training and increased if data efficiency always stays high in the early stage of training.
2).
suggest
as shown in Fig. 12
1) and Fig. [5] a should be
Xint and Xint determines the scale of intrinsic rewards. In our sensitivity analysis. Airt is analyzed in the Humanoid environment and Aint is analyzed on the 2m_vs_lz map in SMAC. Similarly, we run the second iteration of RSPO with Xint = 0.5, 1, 10 in Humanoid and with X 0.05, 0.2 2m_vs_la /z. The results shown in Fig. T3 and the right part of Table With
16

---

Published as a conference paper at ICLR 2022
Table 10:
The number of distinct strategies discovered by PGA-MAP-Elites and RSPO and the highest achieved rewards in 4-Galls Hard. Numbers are averaged over 3 seeds.
Easy
Medium
Hard
Escalation
Reward in 4-Goals Hard
PGA-MAP-Elin
4
1.6
1.2
10
0.98
RSPO
4
4
7.7
1.30
value and advantage normalization in PPO, the scale of intrinsic rewards may not significantly affect performance. Specifically, the diversity scores in Humanoid do not vary too much, and the induced policies on 2m_ 2m_vs_/z /s_/z are all visually distinct from the reference one. However, the scale is much larger than extrinsic rewards, it may cause learning instability, shown in Fig. T3] On the opposite side, if the intrinsic rewards are turned off, RSPO may slow down convergence (Fig. (3), fail to discover non-trivial local optima due to lack of exploration (Table. T get stuck during exploration
due to low data efficiency (Fig. 5). We suggest starting with >g= and X O, and adjusting them such that the intrinsic rewards lead to fast and smooth convergence.
B.4 ADDITIONAL STUDY WITH AN EVOLUTIONARY METHOD
Note that the main paper focuses on the discussion of RL-based solutions which require minimal domain knowledge of the solution structure. Evolutionary methods, as another popular line of research, have also shown promising results in variety of domains and are also able to discover interesting diverse behaviors (Cully et 2015 Hong et al.. 2018). However, evolutionary methods typically assume an effective human-designed set of characteristic features for effective learning.
Here, for complete empirical study, we also conduct additional experiments w.r.t. a very recent evolutionary-basse based algorithm, PGA-MAP-Elites (Nilsson & Cully) (2021) which integrates MAP. Elites (Cully et al. 2015) into a policy gradient algorithm TD3 (Fujimoto et al. 2018). The PGA- MAP-Elites algorithm requires a human-defined behavioral descriptor (BD) to map a neural policy into a dow-dimensional (discretized) space for behavior clustering. We run PGA-MAP- 4-goals and the Escalation environment, where the behavioral descriptors (BDs) can be precisely defined to the best our efforts. We remark that for the remaining cases, including the Monster- Hunt environment, MuJoCo control domain, and SMAC scenarios, behaviors of interests always involve strong temporal characteristics, which makes the design of a good BD particularly non-trivial and remain a challenging open question for the existing literature.
on the
In particular, we define a 4-dimensional descriptor for the 4-Goals environment, i.e., a one-hot vector indicating the ID of the nearest landmark. For the Escalation environment, we 1-dimensional descriptor for the Escalation environment, which is a 0-1 0-1-normalized value of the cooperation steps within the episode. We set the number of behavior cells (niches) equal to the iteration number in RSPO, specifically for 4-Goals and 10 for Escalation.
Results are shown in Table 10, where SGA-MAP-Elicee performs much worse on the 4-Goals scenario while outperforms RSPO on the Escalation environment due to the informative BD. Based on the results, we would like discuss some characteristics of evolutionary algorithms and RSPO below:
1.
We empirically observe that many policies produced by PGA-MAP-Elite. are immediately archived without becoming converged, particularly in 4-Goals (Hard) and Escalation. When measuring population diversity, these unconverged policies would contribute a lot even though many of them may have unsatisfying behaviors/returns, By contrast, the objective of RSPO aims to find diverse local optima. This also suggests further research direction to bridge such convergence-diversit gap.
2. The quality of BD can strongly influence the performance of evolutionary methods. Note that the BD in Escalation provides a particularly clear signal whether policy reaches a local optimum or not (i.e., each BD niche precisely corresponds to a policy mode) while RSPO directly works the deceptive extrinsic reward structure without knowing the structure NEs. This suggests the importance of BD design, which, however, remains an open challenge in general.
17

---

Published as a conference paper at ICLR 2022
3. An improper BD may lead largely constrained behavior space. The success of PGA- MAP-Elites largely depends on the fact that the BD is known to be able to effectively cover all the local optima of interest. However, for complex environments like SMAC, we do not even know in advance what kind of behaviors will emerge after training. Therefore, open-ended BD would be desired, which becomes even more challenging problem note that there even has not been any effective diversity measurement on SMAC yet. Therefore, a purely RL-based solution would be preferred.
4. Without informative BD, evolutionary methods typically require large population size introduced, which can cause practical issues. For example, maintaining a large unstructured archive can be computationally expensive. It can be also challenging visually evaluate learned behaviors given a large population.
To sum up. when an effective and informative BD is available, evolutionary methods can be a strong candidate to consider, although it may not fit every scenario of interest, while RSPO can be generally applicable solution with minimal domain knowledge. It could he also beneficial to investigate how to incorporate informative domain prior into RSPO framework, which we leave our future work.
B.5 THE POINT-VO ENVIRONMENT
Parker-Holder et al. 2020b) develops continuous control environment which requires the agent to bypass a wall to reach the goal. A big penalty will be given to the agent if it directly runs towards the goal and hits the wall. This environment indeed has a local optimum which can be overcome by diversity-driven exploration. While the authors of the DvD paper argued that ES and NSR will get stuck in the wall, the naive PPO algorithm can directly learns bypass the wall and escape the local optimum. Hence in our experiment section, we consider much more challenging environments where much larger number of local optima exist, such stag-hunt games and SMAC.
B.6 SMERL
In SMERL (Kumar et al. 2020), if the agent can achieve sufficiently high return in the trajectory, the trajectory will be augmented with intrinsic rewards of DIAYN (Eysenbach et al. 2019) for skill differentiation and policy diversification. In Humanoid, it may be challenging for SMERL to achieve such a high return, which turns off the intrinsic reward for promoting diversity. Hence, we do not report the population diversity score in the main body of our paper.
In stag-hunt games, SMERL keeps producing low returns. Note that since the SMERL algorithm only starts promoting diversity after sufficiently high reward is achieved, all the produced policies by SMERL are visually identical non-cooperative strategies. What's more, DIAYN (Eysenbach et al.) 2019), which has the same intrinsic reward SMERL, has been evaluated in Tang al. (2021) and proved to perform worse than RPG (Tang et al. 2021). while the performance of RPG is further surpassed by RSPO. Hence, we omit the results of SMERL in the stag-hunt games.
We also evaluate SMERL in SMAC with a latent dimension of 5, which only induces strategy on each map across all possible latent variables. We hypothesize the reason is that in such a complex MARL environment with large state space and long horizon, the skill latent variable may be particularly challenging to be determined from game states. Moreover, the latent dimension usually dominated by the state dimension, which makes latent variables less effective.
C ENVIRONMENT DETAILS
C.I 4-GOALS
The implementation of 4-Goals is based on Mulli-Agent Particle Environment: MMrddtch & Abbeel 2018). The size of the agent is 0.02 and the size of the goals 0.04 (in easy and medium mode). The agent spawns at 0). In the easy mode, the four goals spawn at {0, 0.5), (0.5, 0), (0, (0.5) 0.5, 0)) respectively; In the medium and hard mode, the four goals spawn uniformly randomly with x E [- and E [-1, 1]. At each step, the agent receives an
18

---

Published as a conference paper at ICLR 2022
observation vector of the relative positions of the four goals to itself. The game ends when the agent touches any of the goals or when the timestep limit of 16 reached.
C.2 GRIDWORLD STAG-HUNT GAMES
Both Monster-Houe Hunt and Escalation are based on a x grid. In both games, the action space contains discrete actions, including moving up, moving down, moving up, moving down and stay. The policy output is softmax distribution over these actions. Each movement action moves the agent to one neighboring grid while the stay action makes the agent stay still. Each episode lasts for 50 timesteps. We used vector representations with continuous values for observations, i.e., two real numbers to represent the 2-dimensional positions for each entity. The detailed state representations presented in the following sub-sections respectively. (Note: the dimension of each feature is shown in the parentheses)
C.2.1 MONSTER-HUNT
Monster-Hune is based on a 5 x 5 grid. There are three types of entities: 2 agents, monster and apples. All of the entities spawn uniformly randomly on the grid without overlapping. At each step, both agents one step towards its closest agent (ties break randomly). If one agent ends up in the same grid with the monster, it receives penalty of -2; If both agents end up in the same grid with the monster, they both receive bonus of 5; If any agent ends up in the same grid with an apple, it receives a bonus of 1 (ties break randomly if both agents enter the apple grid at the same time). Whenever any agent ends up in the same grid with non-agent entity, the entity respawns randomly on the grid. The observation vector of an agent consists of the absolute position of itself and the relative positions of the other entities. Specifically, total dimension is 10, consisting of self absolute position (2), other agent's 's relative position (2), monster's relative position (2), apple I's relative position (2), apple 2's relative position (2).
choose to move up, down, left, right stay; The monster always moves for
C.2.2 ESCALATION
Same as Monster-Hunt, Escalation is also based a 5 x grid. There are two types of entities: agents and light. All of the entities spawn uniformly randomly on the grid without overlapping. When the two agents and the light ends up in the same grid for the first time, they enter cooperation stage and the cooperation length L is set to 0. At each step of cooperation stage, they first both receive a bonus 1, then L increases by 1. the light entity moves agents move again. The cooperation stage continues only if both agents move the the same grid as the light. If only one agent moves to the light, receives penalty of -0.9T. The game ends if the cooperation stage ends. The observation vector of an agent consists of the current cooperation length L, the absolute position of itself and the relative positions of the other entities. Specifically, total dimension is 7, consisting of current cooperation length (1), self absolute position (2), other agent's relative position (2), light's relative position (2).
random adjacent grid and the
C.3 MUJoCo
We use the MuJoCo environments from Gym (version 0.17.3) with moving forward reward. The only modification is that we set the episode length be 512 that the diverse intrinsic rewards can be easily computed.
C.4 STARCRAFT MULTI-AGENT CHALLENGE
SMAC concentrates decentralized micromanagement scenarios, where each unit of the game is controlled by an individual RL agent. Detailed description of state/action space and reward function can be found in Rashid et al. 20199)
19

---

Published as a conference paper at ICLR 2022
Table 1I: PPO hyperparameters for different experiments.
Hyperparameters
4-Goals
Stag- Games
MuJoCo
SMAC
Network structure
MLP
MLP
MLP
MLP+RNN
Hidden size
64
64
64
64
Initial learning rate
3e-4
le-3
3e-4
5e-4
monster-Huunt 12800
Batch size
8192
16384
1600
Escalation: 6400
Monster- Hunt: 12800
Minibatch size
8192
512
1600
Escalation: 6400
Adam stepsize (f)
le-5
1e-5
le-5
le-5
Discount rate (n)
0.99
0.99
0.99
0.99
GAE parameter (A)
0.95
0.95
0.95
0.95
Value loss coefficient
0.5
1.0
0.5
0.5
Entropy coefficient
0.05
0.01
0.01
0.01
Gradient clipping
0.5
0.5
0.5
10.0
PPO clipping parameter
0.2
0.2
0.2
0.2
2m vs Iz:
PPO epochs
4
4
10
2c vs 64zg: 5
Gated Recurrent Unit (GRU) (Chung et al. 1600 chunks with length 10.
2014
D IMPLEMENTATION DETAILS
For all experiments, baselines are re-initialized and re-run multiple times with the same number of iterations as RSPO except for population-base methods. Population- based baselines are run for single trial with population of policies trained in parallel. We also make sure the population size the same as the iteration number of RSPO. All the baselines are built upon PPO with the same hyperparameters and run for the same number of total environment steps.
D.1 RSPO
We use PPO with separate policy and value networks as the algorithm backbone of RSPO in all experiments. Both policy and value networks are multi-layer perceptrons (MLP) with a single hidden layer. Specifically for SMAC, we add an additional GRU (Chung et al. 2014) layer with the same hidden size and adopt the paradigm of centralized-traiie -rriieei---iiiig---- training-with--dee with-deeentralized execcutin (CTDE), under which agents share a policy conditioned on local observations and a value function conditioned on global states. The PPO hyperparameters we use for each experiment shown in Table TT Even though the trajectory filtering technique induces an unbiased policy gradient estimator, it introduces unnegligible variance in the early stage of training. Therefore, we typically use large batch size for PPO training to alleviate the defect of trajectory filtering. What's more, by using large batch size, the advantage normalization and value normalization tricks could empirically improve learning accepted and learning smoothly converges to locally optimal solution as shown in Fig [5] We also note that the hidden size is 64 across the domains, which may hurt final performance especially in the MuJoCo environments.
stability. In the late stage of training, more trajectories
There are three additional hyperparameters for RSPO: the automatic threshold coefficient a mentioned in Section 3.5 weight of the behavior-driven intrinsic reward Xnt and weight of the reward-driven
intrinsic reward Xint. These hyperparameters shown in Table 12
Smoothed-switching that it helps stabilize training when there are large number of reference policies. Therefore, apply mmoothed-switching in experiments with 10+ iterations, specifically in Fig. 4 and Fig. 7b We
We mention the smoothed-switching technique in Section 3.5 and remark
use the average of switching indicators in batch as the smoothed indicator.
20

---

Published as a conference paper at ICLR 2022
Table 12: RSPO hyperparameters for different experiments.
Hyperparameters
4-Goals
Stag- Hunt Games
MuJoCo
SMAC
2m_vs_ 12:
B
N/A
0.2
2c_vs vas_4ag:: 5
2m_vs 1z: 0.05
innt
N/A
1
_c_vs vs_ 2=__4g::
H. H.Cheetah: 1.1
2m_ 2m_vs_lz: 0.5
0.5
0.6
Hopper & Walker2d: 0.9
2c vy 642g: 0.3
Homanoid: 1.0
D.2 BASELINE METHODS
All baseline methods are integrated with PPO and utilize the same hyperparameters presented in Table 11 For population- hased methods, all workers have independent data collection processes and buffers. RSPO and all baseline methods except for PG are initialized with the same weights. specially mentioned, the algorithn-specific hyperparameters inherited from other papers which proposed the algorithm or utilized the algorithm as a baseline.
PG
Policy gradient with restarts (PG) utilize different random seeds for different policies. Samples collected and consumed independently during training.
PBT-CE Population praudt training with our cross entropy objective (PBT-CE) utilizes the intrinsic reward in Eq. as a soft objective without trajectory filtering and reward switching. By comparing PBT-CE with RSPO, we can validate the significance of the iterative learning and reward-switching scheme. We performed a grid search over le0, 5e-1, le-2, 5e-2, 5e-3, 2e-3, and 1e-3 on the Lagrange multiplier in each domain, and only 1e-3 converges.
DIPG DIPG (Masood & Doshi- Velez 2019) utilizes the Maximum Mean Discrepancy (MMD) of the state distribution between the learning policy and reference policies as a diversity driven objective. By contrast, our algorithm mainly focuses the divergence of action distribution and optionally augment with approximate divergence of state distribution. We performed grid search over 2e0, 1e0, 5e-1, le-1, and le-2 on the coefficient of MMD loss in each domain. The MMD loss coefficient is fixed to 0.1 in SMAC and 1.0 in other environments. We refer to the public implementation""
MAVEN We use the open-soure implementation"
PGA-MAP-Elites We use the open-source implementatior""
DvD Diversity via Determinant (DvD) (Parker- et al., 2020b) algorithm aims to maximize the determinant of the RBF kernel matrix of action embedding. The original paper mainly focuses on the continuous control domain and directly adopts the action as action embedding, while remains unclear how to embed discrete action space. Regarding implementation, we refer to the public codebase We also utilize the Bayesian Bandits module to automatically adjust the coefficient of the auxiliary loss from {0, 0.5), same as original paper.
SMERL SMERL (Kumar al. 2020). if the agent can achieve sufficiently high return in the trajectory, the trajectory will be augmented with intrinsic rewards of DIAYN (Eysenbach et al. 2019) for skill differentiation. SMERL mainly designed for tackling perturbation control domain. We use the score obtained in the first iteration of RSPO the expert return for SMERL. We train SMERL with a latent dimension of with intrinsic reward coefficient a = 10.0
the continuous
httas///aithhbb.cmm//llelll// http::/m00011111111ooomaaaaaaaa0
ites
21

---

Published as a conference paper at ICLR 2022
and trajectory threshold raio 0.1, same the original paper. For fair comparison, train SMERL for latent-dimx more environment frames.
TrajDiv Trajectory Diversity (TrajDiv) (Lupu et al. 2021) is designed for tackling zero-shot coordination problem in cooperative multi-agent games, specifically Hanabi (Bard et al. 2020). Trajdiv utilizes the approximate Jensen-Shand -haennhnnnoon divergence with action discounting kernel as an auxiliary loss in population- based training. We performed grid search le-2, le-1, 1e0 on the coefficient on the TrajDiv loss and over le-1, 5e-1, 9e-1 on the action-kernel discounting factor. We the coefficient of trajectory diversity loss be 0.1 and action discount factor be 0.9.
Ridge Rider The Ridge Rider method (Parker-Holder et al. 2020a) attempts to search for local optima via Hessian information. However, due to the high variance of policy gradients, the Hessian information can be accurately estimated in complex RL problems. The Ridge Rider method basically diverges across the 4 domains we considered. Hence, we exclude the results of it.
E POPULATION DIVERSITY
Population Diversity (PD) is originally proposed in Parker-Holder et al. (2020b) as metric to measure the group diversity of population of deterministic policies ( pMr. The original PD is defined as:
DivD ==
(10)
where d a Behavior Embedding of defined a concatenation of the actions taken N randomly sampled states and K Rd x IR + IR is a kernel function. In the case of Parker- Holder et al. (2020b),
K is the Squared Exponential (or RBF) kernel, defined as KSE(I, 2) = eep length scale.
|
where /
21
In Parker-Holder et al. (2020b), only deterministic policies were considered. In our work, we design an modified version of PD that suits set of stochastic policies II {I.,.... TT defined as follows:
DIv(II) det (ict(Kis((T;; x, )=)
(11)
(-Jspg JSD(a v) and JSD is the Jensen-Shannon divergence. We provide 2p²
where Kisp y) == cxp
the following theorem that connects our definition of PD with the original PD in continuous action space.
Theorem E.1. Let II (pi....,ps) be a deterministic policies in continuous action space. Let II = ( aMs be the randomized policies of II defined as म. (als) -((u(s), where a is an arbitrary deviation. With a suitable choice of p. Div((l) = lim (II) if the states in & is sampled with the randomized policies.
Proof. We first observe that for any i.J E (1....,M]
lim [((#z) - 0(15)11
lim
Σ (1)()))) (=(2))11
N
No0
N
A=1
Eup [s) (
(12)
In the of stochastic policies, have
22

---

Published as a conference paper at ICLR 2022
Ti( (i(a(s)
(Ti(TT -B
log
Ji (als)
E B,
20 (Ila 2=())]1 - ||a (3())]13)
(Since (a]s) ~ (N(((s),
[(l]x((s) 23(s)]1 + )²²
0²1
(Since a ~ +T(())
20²
1
Bonn,
[1]u((s) [s(()]
(13)
20
Then,
JSD(T, 2
(xI( + D ( m4)
2 Bawn: [llu(()) - 15 (6))1 40 Banr, [1]a(()) (s)())]
20 BowauUn [llma(s) [s)(1)
(14)
Therefore, if choose p L
Div(Il) det((KsD TT; xz)
JSD JSS((Te (mT))TTT))
M
det
exp
2p²
2,j=1
(TISD(TT((TT))))
det
exp
2/2
1,j=1
[Φ((;)
0111))11
=det
exp
lim N-+00
2/2NV
tif=1
[(ā(1s) - +(H9))11
lim det
exp
N
212
(.j=1)
lim
DIVD
(15)
F MOTIVATION OF USING CROSS-ENTROPE DIVERSITY MEASURE
Maximizing KL-divergence between policies could be problematic in RL problems. The accumulative KL-divergence of trajectory is defined as
Ty (a, log
OKL(T,,T) TT) = Eron,
(a (st)
Eraw,
Σ log ग. (arls))
E
Σ log क. (arl
cross entropy
entropy of
The above derivation suggests that optimizing KL-divergence would inherently encourages learning policy with small entropy. This usually undesirable. Therefore, we choose to use cross-entropy instead of -l-diivegence.
23

---

Published as a conference paper at ICLR 2022
G DERIVATION OF TRAJECTORY FILTERING AND DEWARD-SWITCHING
In this section, we want to validate our claim that solving the trajectory filtering objective Eq. ( and the reward switching objective in Eq. (6) is equivalent to solving Eq. (2) with even stronger diversity measure Diter ( (T))TT) defined by
Diteer TT. mz) = inf
Σ log ny (a1lbx)
Note that (itter(T;; mz) measures lowest possible trajectory-wise negative likelihood rather than the average value (i.e., cross-entropy) in Eq. (3)
For simplicity, in the following discussions, we omit the discounted factor y for conciseness. Be- fore presenting the theoretical justifications, we focus a simplified setting with the following assumptions.
Assumption 1. (Non-negative Reward and Fixed Horizon) The MDP has finite states and actions with fixed horizon length and non-negative rewards, i.e., Te 2 0 at each timestep t.
remark that this a general condition since for any fixed-horizon MDP with bounded rewards, we can shape the reward function without changing the optimal policies by adding a big constant to each possible reward.
Assumption 2. (Multiple Distinct Global Optima) There exist M distinct global optimal policies Ti. TT. T. namely, गद E arg max; Eyor [E, rel for S is M, and Djtter (T) πz) 2 8 for 1 $ is M.
This assumption ensures that the problem is solvable. Assumption 3. (Non-trivial Optimum) For each global optimal policy n², we have Ener Tt 0 for each possible trajectory under the policy n².
Since rewards are non-negative, Assumption 3 suggests that the optimal policy will not generate any trivial trajectories. We also remark that similar to Assumption [ this assumption can be generally satisfied by properly shaping the underlying reward function without changing the optimal policies.
With all the assumptions presented, we first derive the filtering objective in Eq. 5 via Theorem G.I and then the switching objective in Eq. 66 via Theorem G.2
Theorem G.1. (Filtering Objective) Consider the constrained optinization problem
Tk+1 arg max EET
Σ rr
subject
inf The
- log me (aelst) 2 8, visisk M.
x
(16)
Given assumption
and solving the following unconstrained optimization problem
# arg max E (x(T) Σn
(17)
is equivalent to solving Eq. 16 where Px(T) = II (i(T) and (i(T) is defined by
1, if -, n. (atls))) 2 8, (st, az) ~ otherwise
(x(T)
(18)
Proof. When 1: 1, the optimization problems in Eq. (6 and Eq. 17 are trivially equivalent. We assume the optimization in the first iteration leads to global optimum. For any k > 1, given previously discovered optimal policies {Tq]1 < < k). we will show that Eq. (17) must have an equivalent solution to Eq. (16), which is
global optimum. By induction, the proposition holds.
Consider a fixed k we use S to denote the subspace of feasible policies satisfying all the distance constraints, i.c., S { V1 < i S k Dutter (π, πT) 2 5}. Note that by Assumption [ We would like to prove Theorem. G. by showing that the optimal value of Eq. (17) over π E S is greater than the value & S. Consequently, the solution of Eq. (17) should satisfy the constraints in Eq.. (6))
24

---

Published as a conference paper at ICLR 2022
For S,
max B P~~ (a(t) TES
max Eyww
Σ
r3
max 5
(19)
TEB
For S, we define
T T=STNT TMT -
Elog log Te (arlst) 2 8, vi
(20)
as the constraint-satistyingg set of I under policy æ. The right-hand side of Eq.
can be written as 17
max RHS-
max BTAN
(T( Σ Tt
rgS
x$S
max (T E ET) rgS
(T( Σ r TET
PT $ T)E
#x(T) Σ
7 T
T
max (T E ET) x$S
1. Σ rb TET
+Pa(T $ T)
0. Σ
r2
T 7
max (T E T)) x$8
Σ T1 TET
(21)
Here E [: T T) denotes the expectation conditioned on the event (T E T} and Pa(T T*
=
Eysr [xx (T)
Next, we want to prove that
max RHS of Eq. TÉS
max E TBS
Σ r2
(22)
On one side, the optimal value the right- side in Eq. 17 is not global optimum. Eq.
22
holds because rt >> 0 by Assumption 1 On the other side, consider the solution of the right-
hand side in Eq. (17) is a globally optimal policy xt" & S. According to the definition of T,
PT- (T E T) 0. By Assumption for VT T², En re O. Further, for x² S. (r TE
T E T 0. Thus,
EndTer) P $ T
max RHS of Eq. =$S
17
< max PT E T)E RgS
Σ re T
max ags
EYNT
Σ rt = max Bror
Σre
= max E
Σ r'
RES
(23)
Therefore, we can conclude that the maximum value of the objective function in Eq. 17) should be obtained when S. because for S, (T( for all < i < the constrained objective and the unconstrained objective have the same form. Finally, by induction, the solution of Eq. (17) must be a solution of Eq. (16).
Theorem G.2. (Switching Objective) Consider the constrained optimization problem in Eq. 16) [ for any > O, there exists some X > such that solving the following
Given Assumption. | unconstrained optimization problem
(T(T)) Σ rt Σ (1 2x(7)) (-Σ log n. (aalss))
]
1 arg max E
(24)
equivalent to solving Eq.
16),
where (x(T) II (i(T) and @s(T) is defined by
1,
if - E, log (a,(ss):) 2 8, (st, az) ~ otherwise
(.(T)
(25)
0,
25

---

Published as a conference paper at ICLR 2022
Proof. Following the same induction process and definition of S, the critical part is again show that the optimal value of Eq. (24) w.r.t. a particular iteration & over т E S is greater than the value over & S. Consequently, the solution of Eq. (24) should satisfy the constraints in Eq. (16) and the overall proposition holds by induction.
For 8, the unconstrained optimization problem in Eq. (24 changes
M&+1 arg max EETO
Σ
(26)
FES
For $ S, we define
T TMT
Σ
log क; (ar(st) 2 8, v1 visisk
(27)
as the constraint-sattisfying set of given policy First observe that when $ T,
(-> log log (aee)s)))
Σ (1 (i(())
Σ log (aelss) 0)
(-Σ log ग. (asls))
1
k
= k8.
(28)
Then write the right-hand side of Eq. 24
max RHS = max Eynn [g(T)]
TSS
THS
max P=(7 ( Pr(T &
TéS
max (x T) agS
(x(TT) Σ
Te + Y Σ
(1 - (T())
(-- log गi (aclst)
T TET
1=1
+ F (T & TY
(R(T) Σ r + Σ (1-)((7)) (-
(-)
Σ log (as((s)))
T&T
max PT(T TT)ETNT TgS
1 Σ r2 TET
+ +F & T)
0. Σ r' T
k Σ (1 - di(T)) (1-1(())
+ AP,(T $ T)E
Σ log (arlse)
T T T
max P- (T(T T)E TÉS
1 Σ rr T
+ (T $ T)
0 0.> r
T $ T
+ Ake
max EToO THS
Σ T:
-P $ T
Σ rs T $ T
+ Ako.
(29)
Here ErAT [-|7 T' denotes the expectation conditioned on the event (T TT and Px(T T) Epax (0x
Next, would like show that
Σn
max ETAN x$5
Σ - PT $ T)E
Σ
TT < max Eran
(30)
26

---

Published as a conference paper at ICLR 2022
Note that it is trivial that max Bron 1rrr
PT Pr
T)E rele
<
max, Eyon 1E, re] by Assumption (i.e., Tt 2 0). We just need to verify that the equality condition is infeasible. We prove by contradiction. In the case of equality, the left-hand side yields a global optimum xt' & S. However, by Assumption 3 (i.e., VT ~ n²,, E,, Pt > 0), we have E, 1 relT & 7 > 0. Since (T- & T) > 0, a contradiction yields. Thus, Eq. (30) holds.
Accordingly, let
A max E
Σ
max rgS
B
Σ r2
(T & T)E
Er
Σ r T T T
(31)
and we can choose
With such X, we can continue the derivation in Eq.
(9 by
Rd
max RHS
< max BT
Σ
(x & T)EENT
Σ
T
T
+ Ak8
"
(32)
max Eysn
Σ
max EES
Σ
Therefore, we can conclude that the maximum value of the objective function in Eq. (24g can be only obtained from S. Finally, by induction, the solution of Eq. (24) must be a solution of Eq. (16).
Corollary G.3. Providing Assumption can find M distinct global optima in M iterations.
2 and
3
the filtering objective and the switching objective
Intuition Remark:
We want to emphasize that the constraint by Diiter in Eq. [16 does not mean the infimum over every possible trajectories, but the infimum over subspace of trajectories generated by the learning policy TR+1- From the perspective of functional analysis, TT++1 produce 0 probability w.r.t. some state-action pairs, which restricts the space of possible trajectories sampled from Tk+1-
Note that even though in practice, neural network policy may never produce an action probability of zero due to approximation error, we would like to remark that the constraint- violated trajectories will have very low probability to be sampled, that is, we typically have P Σ, log ग (s) 2 8) ~ 1 when the policy converges. In this case, the diversity constraints will be rarely violated given a limited number of trajectory samples. This is empirically justified as shown in Fig. and Fig. 12 where the trajectory acceptance rate consistently stays at 1 in the later stage of training.
Practical Remark 1:
Practical Remark 2: Although the theorems only justify our algorithm when the optimal solutions are found, we empirically notice that our algorithm can even effectively discover a surprisingly diverse set of local optimal policies shown in the experiment section. We believe there will be still huge room for further theoretical analysis, which we leave as future work.
H ADDITIONAL DISCUSSIONS
H.1 COMPARISON WITH CLASSICAL EXPLORATION METHIODS
RSPO is beyond an exploration method. In the classical exploration literature, the goal is to discover single policy that can approach the global optimal solution to produce the highest reward. By contrast, the goal of RSPO is not to just find a policy with high reward. Instead, RSPO aims to find as many distinct local optima as possible.
our experiments, a standard PPO trial iteration 1 of RSPO can directly solve the task with the highest rewards. However, there still large number of distinct local optima with novel emergent behaviors other than this high-reward one. This is a particularly challenging constrained optimization problem more local optima are discovered.
H.2 SUBOPTIMALITY OF DISCOVERED POLICIES
is possible that a policy produced by RSPO reaches a suboptimal solution if ccarly-optimal solutions have been all discovered, such as in the MuloCo domain. Meanwhile, RSPO could also possibly find
27

---

Published as a conference paper at ICLR 2022
optimal solution if the previously discovered solutions are all suboptimal, such in the stag-hum games. Overall, as a general solution, RSPO can definitely be applied as an exploration method by escaping sub-optimal strategies.
H.3 MAY RSPO FAIL TO PRODUCE DIVERSE SOLUTIONS?
As more strategy modes are discovered, RSPO is solving an increasingly challenging constrained optimization problem, so is indeed possible that an iteration "fails", e.g., some constraints may be violated or the policies may simply converge to previous modes leading. We empirically observe that these "failure" iterations typically lead visually indistinguishable behaviors, which would not affect our final evaluation metric.
I LICENSES
We use MuJoCo under personal license.
28

---

Published as a conference paper at ICLR 2022
(a) Aggressive left-wave cleanup
(b) Cliff--niping and smart blocking
right-wave (c) Aggressive right wave cleanup
(d) Corner
(c) Fire attractor and distant sniper
(I) Cliff walk
Figure 14: Diverse strategies discovered by RSPO on the _c_vs_ vs_64zg map in SMAC.
29

---

Published as a conference paper at ICLR 2022
Swinging
(b) Parallel hit-and-run
(c) One- sided vertical swinging
(d) Alternative distraction
Figure 15: Diverse strategies discovered by RSPO on the 2m_ws_/ map in SMAC. The movement direction is indicated by yellow arrows.
30


Reviews:
[{"review_id": "j6xYIWTzAt", "reviewer": "Reviewer_YXUG", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall the paper is of high quality. It is well structured and describes concisely and clearly the work done. The experimental evaluation is appropriate and demonstrates the benefits of the proposed method in a large variety of domains. \n\nWhile the novelty of this paper is clear from the domain of deep reinforcement learning, the paper does not consider recent approaches that combine QD algorithms and policy gradient algorithms, such as QD-RL[1] or PGA-MAP-Elites[2]. These approaches can generate collections of hundreds of NN policies and would appear as suitable baselines for this paper. One might say that these approaches require a well-defined behaviour descriptor (like MAP-Elites approaches). Yet, it is possible to use distance-based archives (like the unstructured archive in [3]) which only require the definition of a distance function and a threshold value, like in eq.(1). \n\nAn aspect of the algorithm that remains unclear to me after looking at the experimental results is if every iteration necessarily leads to a policy added to the collection. Figures 1.a, and 7.b show that it is possible to have fewer strategies than the number of iterations. Is it because the authors listed the possible strategies and they counted how many of these were discovered by the algorithms, or is it that in certain cases, the algorithms would fail to produce a policy that satisfies the hard constraint and thus fail?\n\nMinor comments: \n- MAP-Elites belongs to the family of QD algorithms, and there is a typo in its name in the paper. \n- \"Justin K. Pugh, L. B. Soros, and K. Stanley. Quality diversity: A new frontier for evolutionary computation.\" appears twice in the reference list.\n\n[1] Cideron, G., Pierrot, T., Perrin, N., Beguir, K., & Sigaud, O. (2020). QD-RL: Efficient Mixing of Quality and Diversity in Reinforcement Learning. arXiv preprint arXiv:2006.08505.\n[2] Nilsson, O., & Cully, A. (2021, June). Policy gradient assisted MAP-Elites. In Proceedings of the Genetic and Evolutionary Computation Conference (pp. 866-875).\n[3] Cully, A., & Demiris, Y. (2017). Quality and diversity optimization: A unifying modular framework. IEEE Transactions on Evolutionary Computation, 22(2), 245-259.", "summary_of_the_paper": "In the paper \"Continuously Discovering Novel Strategies via Reward-Switching Policy Optimization\", the authors introduce a new reinforcement learning algorithm to iteratively form a collection of high-performing and diverse policies. The main idea is that at each iteration of the algorithm, a new policy is optimised so that it maximises the extrinsic reward and satisfy the condition of being different enough from the policy already in the collection. In order to solve this constrained reinforcement learning problem, the authors propose a new loss that effectively rejects the strategies that are similar to already discovered ones and provide an intrinsic reward for pushing these strategies as far as possible before considering the extrinsic reward. They evaluate the benefits of the proposed algorithm on a large set of experiments, including continuous control tasks, and complex multi-agent domains. ", "summary_of_the_review": "Overall the paper is of high quality. It is well structured and describes concisely and clearly the work done. The experimental evaluation is appropriate and demonstrates the benefits of the proposed method in a large variety of domains. I believe the paper could be improved by also considering recent work from the QD literature which could be applied in similar domains while scaling to larger collections.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "UVAG_Zd-b56", "reviewer": "Reviewer_LnVU", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The problem is well-formulated and experiments are validating the claims authors made in the paper. The overall idea of the proposed method makes sense to me. \n\nI have the following concerns and questions regarding this paper. I can adjust my score accordingly after the authors reply to these questions:\n\n(1) My first concern is regarding $\\delta$. I appreciate the author’s effort to provide an empirical way of adjusting it, but I didn’t find it intuitive. Such an important parameter requires a better Ablation study. The results of Table 1 shows the occurrence of different strategies by stopping the reward switching. But does it say much? Or could it be just randomly happening? I suggest showing a percentage of each strategy that is discovered, or any better way of investigating this parameter.\n\n(2) My second concern is regarding using the reward prediction error as your reward-driven intrinsic reward. To my understanding, this value may never be accurate, specially at the start of learning $f(.,.,\\psi)$. Also does it somehow relate to this paper? https://proceedings.neurips.cc/paper/2018/file/51de85ddd068f0bc787691d356176df9-Paper.pdf\n\n(3) The ordering of the Figures in the experiments could be much better. I believe authors can fix this issue as it affects the readability of paper. E.g. Figure 4 in the main text has been referred to only in the Appendix. Page 8 contains 3 figures, start from 7, then 6, and then 5. The location of Table 1 doesn’t match with the corresponding text. Figure 7 (a) does not clearly show other approaches (PG,DIPG,RND) due to the overlay. Maybe authors can have a small zoom-in box in there?\n", "summary_of_the_paper": "This paper presents a Reward-Switching Policy Optimization (RSPO) that discovers diverse policies that are locally optimal and sufficiently different from the existing ones. This is done by adaptive switching among extrinsic and intrinsic rewards that are used for policy learning. RSPO makes use of both the trajectory filtering objective and the exploration objective.", "summary_of_the_review": "Overall, the paper seems to contribute to the field, but small changes are required before publication.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "29xB7_48CDB", "reviewer": "Reviewer_tRht", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "### Strong points\n- Proposed method finds the diverse strategies in the experiments\n\n### Weak points\n- It is not clear what is really optimized by the proposed algorithm\n- design of the experiment is unclear and not convincing in some parts\n- proposed algorithm seem to have many hyperparameters to be tuned\n\nI describe the detailed comment to each point below.\n\n### Meaning of the objective function\n I do not see a clear connection between the constrained optimization in Eq. (2) and (5). Although it is stated that the rejection-sampling-based approach enables to directly optimize Eq. (2) by strictly enforcing all the hard constraints, I don't understand why optimization problems in Eq. (2) and (5) are equivalent. It is necessary to show the equivalence mathematically. \n\nIn my understanding, the policy update is simply PPO, and the only difference from PPO is the use of the specific form of the reward function. In my opinion, the reward with the indicator function may encourage the policy not to overlap with other policies, but the policy update does NOT have any hard constraint.\nIn addition, the reward function in Eq. (9) also has the intrinsic reward which does not have the indicator function. The intrinsic reward seems to encourage the diverse behavior, but this term does not have any hard constraint. It is not clear what is really constrained in the  policy update using the proposed algorithm. \n\nIn addition, I'm not sure what is meant by \"we also remark that trajectory filtering is closely related to the derivation of the\npolicy ratio clipping term in Proximal Policy Optimization (Schulman et al., 2017).\" I encourage authors to mathematically  show the relation using equations.\n\nIf the authors cannot mathematically support the claims I pointed out above, these claims should be removed or modified.\nIn the current form, these claims are not properly supported, and the contribution is limited to just a reward engineering without theoretical justification.\n\n### Experiment design\nIn the experiment section, the term \"iteration\" appears several times, but the definition of the iteration is not clear to me.\nIn my understanding, policies are trained sequentially in the proposed method, and I guess that a policy is optimized in each iteration. Then, I'm not sure how many environment steps are used in each iteration. If it requires significantly many steps, it is not fair to compare the results of keep running baseline methods. Rather, the baseline methods should be evaluated by repeating initializing and training the policy multiple times. For example, what happens if we run DIPG multiple times?  Another possible easy baseline is running SAC multiple times. (I guess that SAC is more sample efficient than simple policy gradient, and we can run SAC more times than PG with the same number of environment steps.)\n\n### Hyperparameters\nJudging from the appendix, hyperparameters such as $\\lambda^{int}_B$, $\\lambda^{int}_R$, $\\alpha$, entropy-coefficient, PPO epochs, batch size are carefully tuned in the experiment. For fair comparison, hyperparameters of baseline methods should also be carefully tuned. In addition, the effect of some importance hyperparameter such as $\\lambda^{int}_B$, $\\lambda^{int}_R$, $\\alpha$ should be analyzed.\n\nMinor comments\n\n- The proposed method is evaluated based on diversity metric, but the results of the average return based on the extrinsic reward should also be reported. As the goal of the proposed algorithm is to obtain the diverse policies that solves given tasks, the average return based on the extrinsic reward is also an important metric.\n\n- I'm not sure whether the results in Tables 2 and 3 are the mean values over multiple trials or a single trial. If the results in Tables 2 and 3 are the mean values over multiple trials, the standard deviations should also be reported. Similar modifications should be made for Tables 6, 7, and 8 in Appendix as well.\n\n ", "summary_of_the_paper": "This paper presents an algorithm for discovering diverse strategies in reinforcement learning. In the proposed method, policies are sequentially trained with the constraint that encourages to find different behaviors. During the training process, the extrinsic and intrinsic rewards are switched based on a metric for quantifying the novelty of trajectories. The proposed method is evaluated on 4 domains, including OpenAI Gym Mujoco tasks and StarCraftII Multi-Agent Challenge. The experimental results show that the proposed method discovers diverse strategies in these domains.", "summary_of_the_review": "Although the paper reports some interesting results, some of statements regarding the proposed algorithm do not seem well-supported.\nIn addition, the experimental section requires some improvement to justify the claims. \n\n======== Comments after the author response ===========\n\nI appreciate the authors' effort to address my concerns. During the conversation, the authors modified the several parts, which are crucial to support the problem formulation.  However, even after the in-depth discussion, I am not fully convinced that the claims are correctly proved. \nTherefore, I keep the initial score.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "0D_t1UFTMtu", "reviewer": "Reviewer_kTab", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Pro:\n1. Simple approach that can generate policies with distinctive behaviors. Furthermore, a wide range of environments and many baseline methods are used to verify the effectiveness of the proposed approach.\n2. The method is clearly described. The idea of trajectory filtering based on the sum of cross entropy and how to make use of rejected trajectories with the intrinsic reward to promote diversity is new to me.\n\nIssue:\n1. Some result indicates that the additional intrinsic reward can lead to suboptimal behaviors in terms of the extrinsic result. e.g., in the mujco environments, the 1st policy always demonstrates the best performance, and the subsequent policies can either perform worse or better than previous ones . It will be nice to provide a discussion about this. ", "summary_of_the_paper": "This paper presents a method to train diverse policies. New policies are trained to maximize the original reward while also optimized to be distinctive compared to previous policies. This is achieved by switching between optimizing for original reward and diversity reward. Multiple environments are used to demonstrate the proposed method is able to generate policies with distinctive behaviors.", "summary_of_the_review": "This paper presents a simple and effective approach to generating policies with diverse behaviors. I believe this will be an important contribution to the field.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: In this paper, a new method is proposed to discover diverse policies solving a given task. The key ideas are to (1) learn one policy at a time, with each new policy trying to be different enough from the previous ones, and (2) switch between two rewards on a per-trajectory basis: the "normal" reward on trajectories that are unlikely enough under previoiusly discovered policies, and a "diversity-inducing" reward on trajectories that are too likely (so as to push the policy being learned away from the previous ones). The main benefit of this switching mechanism is to ensure that the new policy will be optimal, because the reward signal isn't "diluted" by the diversity-inducing signal as long as the policy stays far away from the previous ones.

After the discussion period, most reviewers clearly recommended acceptance of the paper. One reviewer remained on the "reject" side though, especially due to an unconvincing theoretical analysis of the method, in spite of several back and forth with authors. I also had my own concerns regarding that part after reading the paper, and further discussions with authors eventualy led to a significant rewrite of the corresponding theorems and proofs. I believe the final version (shared in comments by authors after the dealine for paper revisions) to at least be technically correct, though the relevance of the theory w.r.t. practical usage of the method is still not entirely convincing (e.g., assumptions regarding the number of distinct global optima, and the need for positive rewards).

That being said, in spite of these concerns regarding the practical significance of the theoretical analysis, I believe the paper has a strong enough empirical validation, and the method is (1) simple, (2) intuitively reasonable, (3) original due to the trajectory-switching mechanism, which makes me recommend acceptance.
Decision: Accept (Poster)