Novel Policy Seeking with Constrained Optimization
Authors: Hao Sun
Zhenghao Peng
Bo Dai
Jian Guo
Dahua Lin
Bolei Zhou
Venue:  (2021)
Keywords: Novel Policy Seeking
Reinforcement Learning
Constrained Optimization

Abstract: We address the problem of seeking novel policies in reinforcement learning tasks. Instead of following the multi-objective framework commonly used in existing methods, we propose to rethink the problem under a novel perspective of constrained optimization. We at first introduce a new metric to evaluate the difference between policies, and then design two practical novel policy seeking methods following the new perspective, namely the Constrained Task Novel Bisector (CTNB), and the Interior Policy Differentiation (IPD), corresponding to the feasible direction method and the interior point method commonly known in the constrained optimization literature. Experimental comparisons on the MuJuCo control suite show our methods can achieve substantial improvements over previous novelty-seeking methods in terms of both the novelty of policies and their performances in the primal task.

Under review as a conference paper at ICLR 2021
NOVEL POLICY SEEKING WITH CONSTRAINED OPTI- MIZATION
Anonymous authors Paper under double-blind review
ABSTRACT
We address the problem of seeking novel policies in reinforcement learning tasks. Instead of following the multi-objective framework commonly used in existing methods, we propose to rethink the problem under a novel perspective of con- strained optimization. We first introduce a new metric to evaluate the difference between policies, and then design two practical novel policy seeking methods fol- lowing the new perspective, namely the Constrained Task Novel Bisector (CTNB), and the Interior Policy Differentiation (IPD), corresponding to the feasible direction method and the interior point method commonly known in the constrained opti- mization literature. Experimental comparisons the MuJuCo control suite show our methods can achieve substantial improvement over previous novelty-seeking methods in terms of both the novelty of policies and their performances in the primal task
INTRODUCTION
In Reinforcement Learning. an agent interacts with the environment learn policy that can maximize a certain form of cumulative rewards (Sutton & Barto 1998). while the policy gradient method can be applied to optimize parametric policy functions (Sutton al. 2000). However, direct optimization with respect to the reward function is prone to get stuck in sub-optimal solutions and therefore hinders the policy optimization (Liepins & Vose 1991 Lehman Stanley, 2011 |
Plappert
et al. 2018). Consequently, an appropriate exploration strategy is crucial for the success of policy learning (Auer 2002; Bellemare et al. 2016 Houthooft et al. 2016: Tang et al. 2017 Ostrovski
al. 2017 Tessler al.) 2019 Ciosek et al. 2019).
Recently many works have shown that incorporating curiosity in the policy learning leads to better exploration strategies (Pathak et al. 2017 Burda et al. 2018a b; Liu et al. 2019). In these works, visiting previously unseen or infrequent state is assigned with an extra curiosity bonus reward. Dif- ferent from those ouriosity-driven methods which focus discovering
states within the learning procedure of a repeated single policy, the alternative approach of Novel Policy Seeking (Lehman Stanley 2011 1 Zhang et al. 2019 Pugh et al. (016) focuses learning different policies with diverse or the so-called novel behaviors to solve the primal task. In the process of novel policy seeking, policies in new iterations are usually encouraged
be different from previous policies. method at the level
Therefore novel policy seeking can be viewed as an extrinsic curiosity-drive of policies, as well as an exploration strategy for population of agents. Besides encouraging exploration (Eysenbach et al., 20188] Gangwani et al. 2018 Liu et al., (017). novel policy seeking also related to policy ensemble (Osband et al. 2018) 2016; Florensa et al. 2017) and evolution strategies (ES) (Salimans et al. 2017: Conti et al. (018))
In this work, we aim at generating a set of policies that behave differently from all previous given policies while trying to keep their primal task performance. In order to generate novel policies, previous work often defines a heuristic metric for novelty estimation, e.g., differences of state distributions estimated by neural networks used in (Zhang et al.) 2019), and tries solve the problem under the formulation of multi-objective optimization. However, most of these metrics suffer from the difficulty when dealing with episodic novelty reward, i.e., the difficulty of episodic credit assignment (Sutton et al. 1998). thus their effectiveness in learning novel policies is limited.
'Code will be made publicly available.

---

Under review as a conference paper at ICLR 2021
Policy Gradient
Mujti-objective Optimization
Constrained Optimization
Policy m Policy nz
Policy Gradient Novelty Gradient
Palicy Gradient
Novelty Gradient
Figure 1: The comparison of the standard policy gradient method without novelty seeking (left), multi-objective optimization method (middle), and our constrained optimization approach (right) for novel policy seeking. The standard policy gradient method does not try actively to find novel solutions. The multi-objective optimization method may impede the learning procedure when the novelty gradient is being applied all the time (Zhang et al.] 2019), c.g., a random initialized policy will be penalized from getting closer to the previous policy due to the conflict of gradients, which limits the learning efficiency and the final performance. On the contrary, the novelty gradient of our constrained optimization approach will only be considered within a certain region to keep the policy being optimized away from highly similar solutions. Such an approach is more flexible and includes the multi-objective optimization method as its special case.
Moreover, the difficulty of balancing different objectives impedes the agent to find a well-perforning policy for the primal task, as shown by Fig- which compares the policy gradients of three cases, namely the one without novel policy seeking, novelty seeking with multi-objectivv optimization and novelty seeking with constrained optimization methods, respectively.
In this work we take into consideration both the novelty of the learning policies and the performance of the primal task when addressing the problem of novel policy seeking. To this end we propose to seek novel policies under a formulation of constrained optimization. Two algorithms under such a formulation are designed to seek novel policies while keeping their performances of the primal task, avoiding excessive novelty seeking. As a result, the performances of our learned novel policies can be guarantced and even further improved.
Our contributions can be summarized in three-folds. Firstly, we introduce new metric to compute the difference between policies with instant feedback at every timestep; Secondly, we propose a constrained optimization formulation for novel policy seeking and design two practical algorithms resembling two approaches in constrained optimization literature; Thirdly, we evaluate our proposed algorithms the MuJoCo locomotion environments, showing the advantages of these constrained optimization novelty-seeking methods which can generate a series of diverse and well-performing policies over previous multi-objective novelty seeking methods.
2 RELATED WORK
Intrinsic motivation methods In previous work, different approaches are proposed to provide intrinsic motivation or intrinsic reward as a supplementary to the primal task reward for better exploration (Houthooft al. 2016 Pathak al. 2017 Burda al., 2018a by Liu et al., 2019). All those approaches leverage the weighted sum of two rewards, the primal rewards provided by environments, and intrinsic rewards that provided by different heuristics. On the other hand, the work of DIAYN and DADS (Eysenbach et al. 22018] (Sharma et al. 2019)] learn diverse skills without extrinsic reward. Those approaches focus on decomposing diverse skills of single policy, while our work focuses on learning diverse behaviors among a batch of policies for the same task.
Diverse policy seeking methods The work of Such et al. shows that different RL algorithms may converge to different policies for the same task (Such et al.) 2018). On the contrary, we are interested in how to learn different policies through single learning algorithm with the capability of avoiding local optimum. The work of Pugh et al. establishes standard framework for understanding and comparing different approaches to search for quality diversity (QD) (Pugh et al. 2016). Conti et al. proposes solution which avoids local optima as well as achieves higher performance by adding novelty search and QD to evolution strategies (Conti et al. 2018). The Task-Novelty Bisector (TNB) (Zhang al., 2019) aims to solve novelty seeking problem by jointly optimize the extrinsic rewards and novelty rewards defined by an auto-encodes In this work, one of the two proposed methods is closely related to TNB, but is adapted to the constrained optimization formulation.
2

---

Under review as a conference paper at ICLR 2021
Constrained Markov Decision Process The Constrained Markov Decision Process (CMDP) AAl man 1999) considers the situation where an agent interact with the environment under certain con- straints. Formally, the CMDP can be defined as tuple (S, A, 7. c, C, sn), where S and A are the state and action space; E [0. 1) is a discount factor; r S x A X S + R and e: S x A x S - IR denote the reward function and cost function; C IR+ is the upper bound of permitted expected cumulative cost; P(-[s,a) S x A + S denotes the transition dynamics, and is the initial state. Denote the Markovian policy class as 1I, where II { S x A [0, 10,11,2 E. (a/a)) 13 The learning objective of policy for CMDP is to find a T'' E II, such that
π max BT TEll
ar(s,,,8)) S.t.
Brordder yd(s,,, sc, (1)
where t indicates a trajectory (8o. 0o, $1,-.. and 7 ~ represents the distribution over trajectories
following policy и.: at (((]s)), St+1 P( 8t at): = 0, 1, 2, Previous literature provide several approaches to solve CMDP (Achiam et al. 2017 Chow et al. 2018: Ray et al. 2019), and in
this work we include the CPO (Achiam et al. 2017) as baseline according to Ray et al. (2019).
METHODOLOGG
In Sec 3.1 we start with defining metric space that measures the difference between policies, which is the fundamental element for the proposed methods. In 3.2 we develop a practical estimation method for this metric. 3.3 describes the formulation of constrained optimization novel policy seeking. The implementations of two practical algorithms are further introduced in Sec 3.4.
We denote the policies as {TT, : 0g E θ, 1........ wherein 0, represents parameters of the i-th policy, O denotes the whole parameter space. In this work, we focus on improving the behavior diversity of policies from PPO (Schulman et al. (017), thus we use to represent Opro in this paper. It is worth noting that the proposed methods can be easily extended to other RL algorithms (Schulman jet al. 2015 Lillicrap et al. 2015 Fujimoto et al., 2018, Haarnoja et al.) 2018). To simplify the notation, we omit π and denote policy To; as 0; unless stated otherwise.
3.1 MEASURING THE DIFFERENCE BETWEEN POLICIES
In this work, we use the Wasserstein metric Wp (Rüschendorfi 1985 Villani 2008 Arjovsky
et al. 2017) to measure the distance between policies. Concretely, this work consider the policies, where the Wp over two policies can be written in the closed as p where mi, Lt, m2, Dg are mean and covariance metries of the two normal distributions. In the following of this paper, we use Dw to denote the W22 and is worth noting that when the covariance matrix is identical, the trace term disappears and only the term involving the means remains, i.e., Dw = m- m2| for Dirac delta distributions located at points my and m2. This diversity metric satisfies the three properties of metric, namely identity, symmetry as well as triangle inequality.
haussian-parametera
form (. E,,, (m,, 22)) |lm- - m tr[2 + Σا 2( "
Proposition 1 (Metric Space (O, )), The expectation of Dw Dw(s)) of two policies over any state distribution (s)):
Div (0,, 0,) == Ea-g(s) (a)s), ()(sss))
is metric θ thus (0, DW) is metric space.
The proof of Proposition is straightforward. It worth mentioning that Jensen Shannon divergence Das or Total Variance Distance DTv (Endres & Schindelin, 2003) FFuglede & Topsoe 2004; Schul man et al. 2015) can also be applied as alternative metric spaces, we choose Dw in our work for that the Wasserstein metric better preserves the continuity (Arjovsky et al. 2017).
On top of the metric space (0, (W,)), ), we can then compute the novelty of policy as follows.
Definition 1 (Novelty of Policy). Given a reference policy set Ond such that Onj = (Øref 1, 1,2. Ong C O, the novelty U(O Ond) of policy 0 is the minimal difference between 0 and all policies the reference policy set, i.e.,
U(0(Onn)) == min 1% (9,0g)
(3)
3

---

Under review as a conference paper at ICLR 2021
Consequently, to encourage the discovery of novel policies discovery, typical sevelty methods tend to directly maximize the novelty of a new policy, ie., maxş U(f(@ref). where the θre includes all existing policies.
3.2 ESTIMATION OF Di (0;,0) AND THE SELECTION OF g(s)
In practice, the calculation of Di (0., 02) is based on Monte Carlo estimation where we need to sample s from g()). Although in Eq. 2 ((s) can be selected simply as a uniform distribution over the state space, there remains two obstacles: first, in finite state space we can get precise estimation after establishing ergodicity, but problem arises when facing continuous state spaces due to the difficulty of efficiently obtaining enough samples; second, when is sampled from a uniform distribution 9. can only get sparse episodic reward instead of dense online reward which more useful in learning. Therefore, make approximation here based importance sampling.
Formally, we denote the domain of g(s) as Sy C S and assume ((s) to be a uniform distribution over Sg. without loss of generality in later analysis. Notice S, is closely related the algorithm being used in generating trajectories (Henderson et al. 2018). As we only care about the reachable regions of a certain al algorithm (in this work, PPO), the domain Sg can be decomposed by S₂ limy- U So,, where Sg, denotes all the possible states a policy 0, can visit given a starting state distribution.
In order to get online-reward, we estimate (2 with
((s) Po, (8)
Diy (0,, 0,) = E. Eegg() (0: (als))) = Eappo (o)
Dw (O.((()))))
(4)
where we use pa(s) to denote the stationary state visitation frequency under policy 0, i.e. ps(s)
P(5o - s0) + P(s1 s00) + ... + P(TT = s|0) finite horizon problems. We propose to use the averaged stationary visitation frequency as q(5). e.g., for PPO, g(s) p(s) = Re-oppo [s)( Clearly, choosing (ss) = ((s) will be much better than choosing a uniform distribution as the importance weight will be closer to 1. Such importance sampling process requires necessary
condition that Po. (o,($) (s) and (ss) have the same domain, which can be guaranteed by applying sufficient exploration noise on 0.
Another difficulty lies in the estimation of ((s), which always intractable given a limited number of trajectories. However, during training, 0; policy be optimized and 03 Oreff is fixed reference policy. The error introduced by approximating the importance weight as 1 will get larger when 6, becomes more distinct from normal policies, least in terms of the state visitation frequency. We may just regard increasing of the approximation error as the discovery of novel policies.
Proposition 2 (Unbiased Single Trajectory Estimation). The estimation of pa using a single trajectory is unbiased.
The Proposition 2 follows the usual trick in RL that uses a single trajectory to estimate the stationary state visitation frequency. Given the definition of novelty and a practically unbiased sampling method, the next step is to develop an efficient learning algorithm.
3.3 CONSTRAINED OPTIMIZATION FORMULATION FOR NOVEL POLICY SEEKING
In the traditional RL paradigm, maximizing the expectation of cumulative rewards is commonly used as the objective. i.c., maXage Ey~e(g), where g = Et= 7'r and T ~ 0 denotes a trajectory sampled from the policy O.
To improve the diversity of different agents' behaviors, the learning objective must take both the reward from the primal task and the policy novelty into consideration. Previous approaches (Houthooft) al. [016 Pathak al. 2017 Burda et al. 2018a Liu et al. 2019) often directly use the weighted sum of these two terms as the objective:
(5) where 0 < < 1 is a weight poper-parammter, Stask is the reward from the primary task, and Gint Em=o 7'Tin,, is the cumulative intrinsic reward of the intrinsic reward Tiot,-- In our case,
max E, E,-e [9total = max BE0
LaaxEx~ele Er~e(a 9task + (1 (1-a)) a) -utt, #E0
the intrinsic reward is the novelty reward rint ming,e0.., Day (0,00 0,). These methods can be
4

---

Under review as a conference paper at ICLR 2021
summarized as Weighted Sum Reward (WSR) methods (Zhang et al. 2019). Such an objective is sensitive to the selection of as well as the formulation of rint- For example, in our case formulating
the novelty reward rnn as ming, (0, fj), exp mming, D (0,0,0))) 8,)] and exp [- ming, Der(00, (0. 8g) will lead to significantly different results as they determine the trade-offs in the two terms given o- Besides, dilemma also arises in the selection of a: while large a may undermine the contribution of intrinsic reward, small a could ignore the importance of the primal task, leading to the failure of an agent in solving the task.
(0,
To tackle such an issue, the crux is to deal with the conflict between different objectives. The work of Zhang et al. proposes the TNB, where the task reward is regarded as the dominant one while the novelty reward is regarded as subordinate /Zhang et al. (2019). However, as TNB considers the novelty gradient all the time, may hinder the learning process, e.g., Intuitively, well-performing policies should be more similar to each other than to random initialized policies. As new random initialized policy different enough from previous policies, considering the novelty gradient at beginning of training will result in much slower learning process.
In order to tackle the above problems and adjust the extent of novelty in new policies, we propose to solve the nevelng problem under the perspective of constrained optimization. The basic idea as follows: while the task reward is considered as a learning objective, the novelty reward should be considered as a bonus instead of another objective, and should not impede the learning of the primal task. Fig. T iillsttrate how novelty gradients impede the learning of a policy: at the beginning of learning, random initialized policy should in total learn to be more similar to well-performing policy rather than be different. The secking of novelty should not be taken into consideration all the time during learning. With such an insight, we change the multi-objective optimization problem in (5) into a constrained optimization problem as:
max BE
ʃ(0) E.
s.L. (e) = Tint,t - ro 2 0, 1,2,..... T,
(6)
where rn is a threshold indicating minimal permitted novelty, and Tint, denotes a moving average of rint,t- as we need force every single action of new agent to be different from others. Instead, we care more about the long-term differences. Therefore, we use cumulative novelty terms as constraints. Moreover, the constraints can be flexibly applied after the first ty timesteps (e.g., tg = 20) for the consideration of similar starting sequences, so that the constraints can be written as ge (6) 2 0, Vt = fs....,T.
3.4 PRACTICAL NOVEL POLICY SEEKING METHODS
We note here, WSR and TNB proposed in previous work (Zhagg et al. 2019) can correspond to different approaches in constrained optimization problems, yet some important ingredients are missing. We improve TNB according to the Feasible Direction Method in constrained optimization and then propose the Interior Policy Differentiation (IPD) method according to the Interior Point Method in constrained optimization.
WSR: Penalty Method The Penalty Method considers the constraints of Eq. by putting con- straint g() into penalty term, followed by solving the unconstrained problem
max 8E8
((0)
+ min (g))
a
in an iterative manner. The limit of the above unconstrained problem when a - 0 then leads to the solution of the original constrained problem. As an approximation, WSR chooses fixed weight a, and uses the gradient of Vo + _ Veg instead of Vol + L Vo (i 0}, thus the final solution will intensely rely on the selection of a.
TNB: Feasible Direction Method The Feasible Direction Method (FDM) (uuzzzyyssii 1980
Herskovits 1998) solves the constrained optimization problem by finding a direction p where taking gradient upon will lead to increment of the objective function as well as constraints satisfaction, i.c., NofT F 0, if > and Veg" gradients Vof and Veg as
p otherwise. The TNB proposes use revised bisector of
Vol
V
og cos (Vof, Vog)
if cos (Vof, Vog) S 0 if cos (Vef. Vøg) >
F
V
(8)
V
Vo.
V
V
5

---

Under review as a conference paper at ICLR 2021
Clearly, ( satisfies the constraints but it is more strict than it as the Veg term always exists during the optimization of TNB. Based on TNB, we provide a revised approach, named Constrained Task Novel Bisector (CTNB), which resembles better with FDM. Specifically, when g 0, CTNB will not apply Veg on g. It is clear that TNB is a special case of CTNB when the novelty threshold ro is set to infinity. We note that in both TNB and CTNB, the learning stride is fixed to be |NofI+/Vogl and may lead to problem when Vaf - O, where the final optimization result will rely heavily on the selection of g. i.e., the shape of g is crucial for the success of this approach.
IPD: Interior Point Method The Interior Point Method (Potra & Wright, 2000; Dantzig & Thapa 2006) is another approach used to solve the constrained optimization problem. Thus here we solve Eq. 6 using the Interior Policy Differentiation (IPD), which can be regarded as an analogy of the Interior Point Method. In the vanilla Interior Point Method, the constrained optimization problem in (6) is solved by reforming it to an unconstrained form with an additional barrier term -a log (0) in the objective as maxige f(0) a log g(), or more precisely in our problem with the formulation with 6 we have maxege Er-elStask - Ei a log (Fint,: - -ro]], where a > 0 is the barrier factor. Besides the log barrier term, there are other choices like a "(0) can be used and the objective becomes maxage [(0) + o "াo.- As is small, the barrier term will introduce only minuscule influence on the objective. On the other hand, when @ get closer to the barrier, the objective will increase rapidly. The limits when - 0 then lead to the solution of Eq.( The convergence of such methods are provided in previous works Conn et al. (1997) Wright (001))
However, directly applying IPM is computationally expensive and numerically unstable. In this work, we propose a simple yet novel heuristic method that resembles the idea of barrier methods: implicitly apply such barrier terms by providing termination signals in interactions with the environments. Our method can be regarded as revising the primal task MDP into a new one in which the behaviors of agents must satisfy novelty constraints. Specifically, in the RL paradigm, the learning procedure of an agent is determined by the experiences collected during interactions with the environment and the sampling strategy used to filter experiences in the calculation of policy gradients. Since the learning process is based on sampled transitions, a more natural way can thus be used to perform the constrained optimization. We can simply bound the collected transitions in the feasible region by permitting previously trained M policies 0 E Q = 1,2.... M sending termination signals during the training process of new agents. In other words, we implicitly bound the feasible region by terminating any new agent that steps outside it.
Consequently, during the training process, all valid samples we collected are inside the feasible region, which means these samples are less likely to appear in previously trained policies. At the end of the training, we obtain a new policy that has sufficient novelty. In this way, we no longer need to consider the trade-off between intrinsic and extrinsic rewards deliberately. The learning process of IPD is thus more robust and no longer suffers from the objective inconsistency.
4 EXPERIMENTS
According Proposition 2, the novelty reward Fint in Eq.46) under our novelty metric can be unbiasedly approximated by Fime ming,ee..s Dht (0(als.), (s))) We thus utilize this novelty metric directly throughout our experiments. We apply different novel policy seeking methods, namely WSR, TNB, CTNB, and IPD, to the backbone RL algorithm PPO (Schulman et al., 2017). The extension to other popular RL algorithms is straightforward. More implementation details are depicted in Appendix [D] Experiments in the work of Henderson et al. show that one can simply change the random seeds before training to get policies that perform differently Henderson et al. (2018). Therefore, we also use PPO with varying random seeds as baseline method for novel policy seeking. And we use the averaged differences between policies learned by this bascline as the default threshold in CTNB and IPD. Algorithm|] I and Algorithm 2 show the pseudo code of IPD and CTNB based on PPO, where the blue lines show the addition to the primal PPO algorithm.
4.1 THE MuJoCo ENVIRONMENT
We evaluate our proposed method on the OpenAl Gym based on the MuloCo engine (Brockman et al., 2016 Todorov al. 2012). Concretely, we test on three locomotion environments, the Hopper-v3

---

Under review as a conference paper at ICLR 2021
Algorithm IPD
Algorithm 2 Constrained TNB
Input:
Input:
(1) a behavior policy ooldi
(1) to (4) same Algo.1
(2) a set of previous policies
(5) a value network for cost Ve
(0,),j 1.2, ... M;
Initialize Ooldi
(3) a novelty metric (0, (0)H1)))
for iteration = 1, 1,,,...
UO, (0,)lT) ming; Dw (0,0));
for 1= 1, 1,2,,... ..... do
(4) a novelty threshold To and start- ing point to Initialize Oold;
Step the environment by taking action at fold and collect transitions;
end
for iteration 1,, do
Compute advantage of reward Ar,1, Ar.
for f 2. do
Compute advantage of cost Ar, Ar,
Step the environment by tak- ing action a₁ ~ Oold and col- lect transitions;
Optimize surrogate loss related to reward LCLIP in PPO w.r.t. 0, with gradient 9r V LCLIP Optimize surrogate loss related to cost LCLIP in PPO w.r.t 0, with gradient ge -
if (foldd: { [0,] ro <
AND >> t, then
if (0olds { [ To < 0 then
Break this episode;
Calculate p according to Eq. with gr and 9c
end end
else end
Calculate p with gr
Update policy parameters based sampled data;
Update policy parameters
end
end
163
Hopper-v3
1s3
Walker2dw43
163
HalfCheetah-vv
2.5
2.5
2.0
PPO
Rewer
2.0
1.5
1.5
2.0
(Tra
FD)SU))
1.0
CPO
1.00
1.25
1.50
1.75
2.00
0.8
0.8
1.0
1.2
0.8
1.0
1.2
Nomalizzdd Novelty
Figure 2: The performance and novelty comparison of different methods in Hopper-v3, Walker2d-v3 and HalfCheetah-v3 environments. The value of novelty is normalized relative novelty by regarding the averaged novelty of PPO policies as the baseline. The results are from 10 policies of each method, with the points show their mean and lines show their standard deviation.
(11 observations and 3 actions), Walker2d-v3 (11 observations and 6 actions), and HalfCheetah-v3s (17 observations and actions). Although relaxing the healthy termination thresholds Hopper and Walker may permit more visible behavior diversity, all the environment parameters are set default values our experiments to demonstrate the generality of our method.
4.1.1 COMPARISON ON NOVELTY AND PERFORMANCE
We implement WSR, TNB, CTNB, and IPD using the same hyper- parameter settings per environment. And we also apply CPO Achiam et al. (017)) as baseline as solution of CMDP. For each method, we first train 10 policies using PPO with different random seeds. Those PPO policies are used the primal reference policies, and then we train 10 novel policies that try to be different from previous reference policies. Concretely, in each method, the 1st novel policy is trained to be different from the previous 10 PPO policies, and the 2nd should be different from the previous policies, and so on. More implementation details depicted in Appendix D
7

---

Under review as a conference paper at ICLR 2021
Table I:
The Reward and Success Rate of 10 Policies. Our CTNB and IPD beat CPO, TNB and WSR in all three environments, Constrained optimization approaches outperforms multi-objective methods. Results are generated from 5 random seeds.
Reward
Success Rate
Environment
Hopper
Walker2d
HallCheetah
Hopper
Walker2d
HallCheetah
PPO
1292 + 650
2196 + 200
1127 308
0.5
0.5
0.5
WSR
1253 1 591
1992 i 380
1091 + 469
0.6
0.3
0.3
TNB
1699 573
1788 1 214
887 + 178
0.8
0.0
0.1
CPO
1681 + 696
2082 + 660
1194 1: 215
0.8
0.6
0.8
CTNB (Ours)
1721 765
2405 = 177
1251 473
0.8
0.9
0.5
IPD (Ours)
2536 - 557
2282 + 206
1875 + 533
1.0
0.6
0.9
Fig. 2 shows our experimental results in terms of novelty (the x-axis) and the performance (the y-axis). Policies close to the upper right corner are the more novel ones with higher performance. In all environments, the performance of CTNB, IPD and CPO outperforms WSR and TNB, showing the advantage of constrained optimization approaches in novel policy seeking. Specifically, the results of CTNB all better than their multi-objective counterparts, i.e., the results from TNB, showing the superiority of seeking novel policies with constrained optimization. Moreover, the IPD method provides novelty than CTNB and CPO, while the primal task performances are still guaranteed.
Comparisons of the task-related rewards are carried out in Table D where among all the four methods, IPD provides sufficient diversity with minimum loss of performance. Instead of performance decay, we find IPD is able to find better policies in the environment of Hopper and HalfCheetah. Moreover, in the Hopper environment, while the agents trained with PPO tend fall into the same local minimum. (e.g., they all jump far as possible and then terminate this episode. On the contrary, PPO with IPD keeps new agents away from falling into the same local minimum, because once an agent has reached some local minimum, agents learned later will try to avoid this region due to the novelty constraints. Such property shows that IPD can enhance the traditional RI schemes to tackle the local exploration challenge (Tessler et al. [209 Ciosek et al.] (019). A similar feature brings about reward growth in the environment HalfChectah. Detailed analysis and discussions are developed in Appendix
4.1.2 SUCCESS RATE EACH METHOD
In addition averaged reward, we also use the success rate as another metric to compare the performance of different approaches. Roughly speaking, the success rate evaluates the stability of each method in terms of generating a policy that performs as good as the policies PPO generates. In this work, we regard policy successful when its performance achieves at least as good as the median performance policies trained with PPO. To be specific, we use the median of the final performance of PPO as the baseline, and if novel policy, which aims at performing differently solve the same task, surpasses the baseline during its training process, it will be regarded as a successful policy. By definition, the success rate of PPO is 0.5 success rate of all the methods. The results show that all constrained novelty seeking methods (CTNB, IPD, CPO) can surpass the average baseline during training, while the multi-objective optimization approaches normally can not. Thus the performance of constrained novelty seeking methods can always be insured.
baseline for every environment. Table shows the
CONCLUSION
In this work, we rethink the novel policy seeking problem under the perspective of constrained optimization. We first introduce a new metric to measure the distances between policies, and then give definition of policy novelty. Based on the formulation of constrained optimization, we come up with two practical algorithms for novel policy seeking, namely the Constrained Task Novel Bisector (CTNB), and the Interior Policy Differentiation (IPD). Our experimental results demonstrate that the proposed method can effectively learn various well-performing yet diverse policies, outperforming previous methods which are under the multi-objective formulation.
8

---

Under review as a conference paper at ICLR 2021
REFERENCES
Joshua Achiam, David Held, Aviv Tamar, and Picter Abbeel. Constrained policy optimization. In Proceedings of the 34th International Conference Machine Learning- Learning-Volume Volume 70, pp. 22-31.
JMLR. org, 2017.
Eitan Altman. Constrained Markov decision processes, volume 7. CRC Press, 1999.
Martin Arjovsky, Soumith Chintala, and Léon Bottou. Wasserstein generative adversarial networks. In Doina Precup and Yee Whye Teh (eds.), Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pp. 214-223, International Convention Centre. Sydney, Australia, 06-11 Aug 2017. PMLR. URL http press prepees/inns.iiippppes////// https////10/rroosss//.......
Peter Auer. Using confidence bounds for exploitation-exxllration trade-offs. Journal of Machine Learning Research, 3(Nov):397-422, 2002.
Mare Bellemare, Sriram Srinivasan, Georg Ostrovski, Tom Schaul, David Saxton, and Remi Munos.
Unifying count-based exploration and intrinsic motivation. In Advances in Neural Information Processing Systems, pp. 1471-1479, 2016.
Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojeiech Zaremba. Openai gym, 2016.
Yuri Burda, Harri Edwards, Deepak Pathak, Amos Storkey, Trevor Darrell, and Alexei A Efros. Large-scale study of curiosity-driven learning. arXiv preprint arXiv: 04335,, 2018a.
Yuri Burda, Harrison Edwards, Amos Storkey, and Oleg Klimov. Exploration by random network distillation. arXiv preprint arXiv: 18/00.08/0... /2894, 2018b.
Yinlam Chow, Ofir Nachum, Edgar Duenez-Guzman, and Mohammad Ghavamzadeh. A lyapunov- based approach safe reinforcement learning. In Advances in neural information processing systems, pp. 8092-8100 8101, 2018.
Kamil Ciosek, Quan Vuong, Robert Loftin, and Katja Hofmann. Better exploration with optimistic actor critic. In Advances Neural Information Processing Systems, pp. 1785-1796, 2019.
Conn, Nick Gould, and Ph Toint. A globally convergent lagrangian barrier algorithm for optimiza- tion with general incquality constraints and simple bounds. Mathematics of Computation of the American Mathematical Society, 66(217)2261288, 1997.
Edoardo Conti, Vashisht Madhavan, Felipe Petroski Such, Joel Lehman, Kenneth Stanley, and Jeff Clune. Improving exploration in evolution strategies for deep reinforcement learning via population of novelty-secking agents. In Advances in Neural Information Processing Systems, pp. 5027-5038, 2018
George B Dantzig and Mukund N Thapa. Linear programming 2: theory and extensions. Springer Science & Business Media, 2006.
Dominik Maria Endres and Johannes E Schindelin. A new metric for probability distributions. IEEE Transactions on Information theory, 2003.
Benjamin Eysenbach, Abhishek Gupta, Julian Ibarz, and Sergey Levine. Diversity is all you need: Learning skills without a reward function. arXiv preprint 1XXXv:1802.00770 2018.
Carlos Florensa, Yan Duan, and Pieter Abbeel. Stochastic neural networks for hierarchical reinforce- ment learning. arXiv preprint arXiv:1704.000 030122, 2017.
Bent Fuglede and Flemming Topsoe. Jensen-shannon divergence and hilbert space embedding. In International Symposium onInformation Theory, 2004. ISIT 2004. Proceedings., pp. 31. IEEE, 2004.
Scott Fujimoto, Herke Van Hoof, and David Meger. Addressing function approximation error in actor-critic methods. arXiv preprint arXiv: 1802.09477 2018.

---

Under review as a conference paper at ICLR 2021
Tanmay Gangwani, Qiang Liu, and Jian Peng. Learning self-imitating diverse policies. arXiv preprint arXiv: 10309, 2018.
Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off-policy maxi- mum entropy deep reinforcement learning with a stochastic actor. arXiv preprint arXiv: 01290, 2018.
Peter Henderson, Riashat Islam, Philip Bachman, Joelle Pineau, Doina Precup, and David Meger. Deep reinforcement learning that matters. In Thirty-Second AAAI Conference on Artificial Intelli- gence, 2018.
José Herskovits. optimization theory and applications, 99(1):121-146, 1998.
Feasible direction interior- point technique for nonlinear optimization. Journal of
Zhang-Was Wei Hong. Tzu- Yun Shann, Shih-Yang Yang Su, Yi-Hsiang Chang, Tsu-Jui Fu, and Chun- Yi Lec. Diversity-driven exploration strategy for deep reinforcement learning. In Advances in Neural Information Processing Systems, pp. 10489-10500) 2018.
Rein Houthooft, Xi Chen, Yan Duan, John Schulman, Filip De Turck, and Pieter Abbeel. Variational information maximizing exploration. 2016.
Joel Lehman and Kenneth O Stanley. Novelty search and the problem with objectives. In Genelic programming theory and practice IX. pp. 37-56. Springer, 2011.
Gunar E Liepins and Michael Vose. Deceptiveness and genetic algorithm dynamics. Foundations of genetic algorithms, volume 1, pp. 36-50. Elsevier, 1991.
Timothy P Lillicrap, Jonathan J Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra. Continuous control with deep reinforcement learning. arXiv preprint NXXXv::509000977. 2015.
Hao Liu, Alexander Trott, Richard Socher, and Caiming Xiong. Competitive experience replay. CoRR, abs/1992.000528, 2019. URL httt::ttt//aaa.eee
htrgg/bb/1990 /1tp..90.... 00528
Yang Liu, Prajit Ramachandran, Qiang Liu, and Jian Peng. Stein variational policy gradient. arXiv preprint arXiv:1704.00 704.02399, 2017.
Ian Osband, Charles Blundell, Alexander Pritzel, and Benjamin Van Roy. Deep exploration via
bootstrapped dqn. In Advances in neural information processing systems, pp. 4026-4034, 2016.
Ian Osband, John Aslanides, and Albin Cassirer. Randomized prior functions for deep reinforcement learning. In Advances in Neural Information Processing Systems, pp. 8617-8629, 2018.
Georg Ostrovski, Marc G Bellemare, Aäron van den Oord, and Rémi Munos. Count-based exploration with neural density models. In Proceedings of the 34th International Conference on Machine Learning- Volume 70, pp. 2721-2732 JMLR. org, 2017.
Seaaning-Volume
Deepak Pathak, Pulkit Agrawal, Alexei A Efros, and Trevor Darrell. Curiosity-driven exploration by self-supervised prediction. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition Workshops, pp. 16 17, 2017.
Matthias Plappert, Marcin Andrychowicz, Alex Ray, Bob McGrew, Bowen Baker, Glenn Powell, Jonas Schneider, Josh Tobin, Maciek Chociej. Peter Welinder, et al. Multi-goal reinforcement learn- ing: Challenging robotics environments and request for research. arXiv preprint weXiv:/802.09466 2018.
Florian Potra and Stephen Wright. Interior-point methods. Journal of Computational and Applied Mathematics, 124(1-2):281 2000.
Justin K Pugh, Lisa B Soros, and Kenneth O Stanley. Quality diversity: A new frontier for evolutionary computation. Frontiers in Robotics and AI, 3:40, 2016.
Alex Ray, Joshua Achiam, and Dario Amodei. Benchmarking safe exploration in deep reinforcement learning. openai, 2019.
10

---

Under review as a conference paper at ICLR 2021
Ludger Rüschendorf. The wasserstein distance and approximation theorems. Probability Theory and Related Fields, 70(1):117-129, 1985.
Andrzej Ruszczyísski. Feasible direction methods for stochastic programming problems. Mathemati- cal Programming, 19(1):20--22, 1980.
Tim Salimans, Jonathan Ho, Xi Chen, Szymon Sidor, and Ilya Sutskever. Evolution strategies as scalable alternative to reinforcement learning. arXiv preprint trXivv/703.03866 2017.
John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz. Trust region
policy optimization. In International conference on machine learning, pp. 1889-1897, 2015.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv: (aoo:::77004444 2017.
Archit Sharma, Shixiang Gu, Sergey Levine, Vikash Kumar, and Karol Hausman, Dynamics-aware unsupervised discovery of skills. arXiv preprint arXiv: 100,:00977,1657,, 2019.
Felipe Petroski Such, Vashisht Madhavan, Rosanne Liu, Rui Wang. Pablo Samuel Castro, Yulun Li, Ludwig Schubert, Marc Bellemare, Jeff Clune, and Joel Lehman. An atari model zoo for analyzing. visualizing, and comparing deep reinforcement learning agents. arXiv preprint arXiv: 1rXiv:1812.07069, 2018.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. 1998.
Richard S Sutton, Andrew G Barto, et al. Introduction to reinforcement learning, volume 2. MIT press Cambridge, 1998.
Richard S Sutton, David A McAllester, Satinder Singh, and Yishay Mansour. Policy gradient meth- ods for reinforcement learning with function approximation. In Advances in neural information processing systems, pp. 1057-1063, 2000.
Haoran Tang, Rein Houthooft, Davis Foote, Adam Stooke, OpenAl Xi Chen, Yan Duan, John Schulman, Filip DeTurck, and Pieter Abbeel. # exploration: A study of count-based exploration for deep reinforcement learning. In Advances in neural information processing systems, pp. 2017.
Chen Tessler, Guy Tennenholtz, and Shie Mannor. Distributional policy optimization: An alternative approach for continuous control. arXiv preprint arXiv: 19X5v:/905.09850 09..0.0...55.... 2019.
Emanuel Todorov, Tom Erez, and Yuval Tassa. Mujoco: A physics engine for model-based control. In IROS, pp. 5033. IEEE, 2012. ISBN 978- 978-1-4673-1737-5. URL http: //dbll.uni-tzee. de ab/ conf/ iros/
Cédric Villani. Optimal transport: old and new, volume 338. Springer Science & Business Media, 2008.
Stephen J Wright. On the convergence of the newton/log-barreer method. Mathematical PwtptaaaaaiaaaarrrPriaa Programming, 90(1):71-100, 2001.
Yunbo Zhang, Wenhao Yu, and Greg Turk. Learning novel policies for tasks. CoRR, abs/ 1905.0525. 2019. URI htt.htttp//aaxiiiee www..rrggg..o... 905. 90....5....222
11

---

Under review as a conference paper at ICLR 2021
APPENDIX
A METRIC SPACE
Definition 2. A metric space is an ordered pair (M, d) where M is a set and d is metric on M, iee. function d: M M + IR such that for any I. y: M, the following holds:
1. d(r,y) 2 0, dd y) = 0 + z=
d(x.y) d(y,r),
3. d(z,2) S d(r,y) + d(y,z).
B PROOF PROPOSITION 1
The first two properties are obviously guaranteed by Div As for the triangle inequality,
sssp(s))
E
DDw (B,)s
Es-p(s)
(0((s) 0s(s)]
AAI
Egpp(s)
10((s) + (s)]
1=1
(AA
< Eppp(())
10((s) - -0((s) + +10((s) - (+)I)
1=1
IAI
Egmp(a)
10,(5) - -0,(6)1 + E Esmp(s) Σ
10,(s) 0s(6)
Espp(e)
(w.(s 0,(,) E. p()) (Dw (w, (s)
C PROOF OF PROPOSITION 2
po(s) P(so s|0) + P(1 s|0) +... P(ST = s()
L.L.N. lim
Σ 1(50- s|Ti)
EN 1(11 s/Ti)
1(T = s/T.)
N
N
N
2/=0 Ei=1 [(s) S(T))
N
lim N
N
(s) [(s) s/T))
1=0
E E (3) - (s)) =0
D IMPLEMENTATION DETAILS
Calculation of Dw We deterministic part of policies in the calculation of Dw, i.e., the Gaussian noise on the action space in PPO and use Dw (a1, a2) = |0] 02).
Network Structure We use MLP with hidden layers as our actor models in PPO. The first hidden layer is fixed to have 32 units. We choose to 10, 64 and 256 hidden units for the three tasks respectively in all the main experiments, after taking the success rate, performance and computation expense (i.e. the preference
less unit when the other two factors are similar) into consideration.
12

---

Under review as a conference paper at ICLR 2021
Hopper-v3
Walker2divg
HellCheetah-v4
2500
1502-
2520
2000
1032
2030-
1520
1530
2002
1030
1995
Sanelin 3.5
5-6 0.7 5.6
6.9
Zareline
3.4
0106 11
1.3
3.2
3.
144
7.5
Aooelyy
Figure The performance under different novelty thresholds in the Hopper, Walker and HalfCheetah environments. The results are collected from 10 learned policies based on PPO. The box extends from the lower to upper quartile values the data, with a line at the median. The whiskers extend from the box to show the range of the data. Flier points are those past the end of the whiskers.
Training Timesteps We fix the training timesteps in our experiments. The timesteps are fixed to be 1M in Hopper-v3, 1.6M for Walker2d-v3 and 3M for HallCheetah-v3.
E DISCUSSION
E.1 NOVEL POLICY SEEKING WITHOUT PERFORMANCE DECAY
Multi-objective formulation of novel policy seeking has the risk of sacrificing the primal performance as the overall objective needs to consider both novelty and primal task rewards. On the contrary, under the perspective of constrained optimization, there will be more trade-off between novelty and final reward as the only objective the task reward. Given a certain novelty threshold, the algorithms tend to find the optimal solution in terms of task reward under constraints, thus the learning process becomes more controllable and reliable, i.e., one can utilize the novelty threshold to control the degree of novelty.
Intuitively, the proper magnitude of the novelty threshold will lead to more exploration among a population of policies, thus the performance of latter found policies may be better than least as good as those trained without novelty seeking. However, when a larger magnitude of novelty threshold is applied, the performance of found novel policies will decrease because finding a feasible solution will get harder under more strict constraints. Fig. 3 shows our ablation study on adjusting the thresholds, which verifies our intuition.
E.2 CURRICULUM LEARNING IN HALFCHEETAI
Moreover, we observe a kind of auto-curriculum learning behavior in the learning of HalfCheetah, which may also help to understand the performance improvement this environment. The envi- ronment of HalfCheetah is different from the other two in that there is no explicit early termination signal in its default setting (i.e., there no explicit threshold for the states, exceeds which would trigger termination). At the beginning of the learning, a PPO agent always acts randomly and keep twitching without moving, resulting in massive repeated and trivial samples and large control costs. Contrarily, in the learning of IPD, the agent can receive termination signals since repeated behaviors break the novelty constraint, preventing it from wasting too much effort acting randomly. Moreover, such termination signals also encourage the agent to imitate previous policies to get out of random explorations at the starting stage, avoiding heavy control costs while receiving less negative rewards. After that, the agent begins to learn to behave differently to pursue higher positive rewards. From this point of view, the learning process can be interpreted as a kind of implicit curriculum, which saves lots of interactions with the environment, improves the sample efficiency and therefore achieves better performance in the given learning timesteps.
ADDITIONAL EXPERIMENTS
We run additional experiments on the Ant-v3 environment to show the performance of our algorithm on the more complicated continuous control task (with 11 1-dim state space and 8-dim action space).
13

---

Under review as a conference paper at ICLR 2021
1e3
Ant-v3
Ant-v3
2.0
2012
208
Reward
1.5
WSR
Roward
L18
CTuB|O PD(Ouss) Hong et al.
1.0
2214
508
0.5
0.4
0.6
0.8
1.0
1.2
baseline
0.6
Novelty throshold
0.7
0.8
0.9
1.0
Normalized Novelty
Figure 4: (Left): performance comparison in terms of novelty and task performance of PPO, WSR and IPD in the Ant-v3 environment. We also include the work of (Hong et al.] (018)) as a comparison. (Right): performance under different choices on the novelty threshold in the Ant-v3 environment. The results are collected from 10 learned policies based on PPO. The box extends from the lower upper quartile values of the data, with line the median. The whiskers extend from the box show the range of the data. Flier points are those past the end of the whiskers.
Results are shown in Figure Our method of IPD achieves on-par performance with PPO but improves the novelty between policies by 20%.
Notably, both the performance and novelty of CTNB in Ant-v3 is better than its multi-objective optimization counterpart, the TNB, attribute the reason to the limited training timesteps in TNB and CTNB: in limited training timesteps (3M timesteps in Ant-v3), the policies trained with CTNB and TNB can not converge to well-performing policies, and therefore the behavior difference between those policies are limited (even less than PPO). On the contrary. the method of IPD does not fuse the gradient of primal task reward and the novelty reward, thus similar learning efficiency can be achieved and result in well pell-performing policies.
This experiment demonstrates our claim on the superiority of constrained optimization perspectives of novelty-seekin again: too much pursuance of the novelty will hinder the primal task performance as well hinder the generating of both diverse and well-performing policies.
G VISUALIZE DIVERSITY
G.1 THE FOUR REWARD MAZE PROBLEM
We first utilize basic 2-D environment named Four Reward Maze diagnostic environment where we can visualize learned policies directly. In this environment, four positive rewards of different values (e.g., +5, +5, +10, +1 for top, down, left and right respectively) are assigned four middle points with radius 1 on each edge in a 2-D N x N square map. We use N = 16 in our experiments. The observation of policy the current position and the agent will receive negative reward of -0.01 at each timestep except stepping into the reward regions. Each episode starts from a randomly initialized position and the action space limited [-1, 1]. The performance of each agent is evaluated by the averaged performances over 100 trials.
Results are shown in Fig. where the behaviors of the PPO agents are quite similar, suggesting the diversity provided by random seeds is limited. WSR and TNB solve the novelty problem from the multi-objective optimization formulation, they thus suffer from the unbalance between performance and novelty. While WSR and TNB both provide sufficient novelty, performances of agents learned by WSR decay significantly, so did TNE due to an encumbered learning process, analyzed in Sec 3.3 Both CTNB and IPD, solving the task with novelty-scekin from the constrained optimization formulation, provide evident behavior diversity and perform recognizably better than TNB and WSR.
14

---

Under review as a conference paper at ICLR 2021
Roward:447
TNB.
CTNB, Roward: 147.3 32.9
IPD, Roward:
Trel
Tra
Tux
Trxk
Dack
+10
+5
Figure 5: Experimental results on the Four Reward Maze Problem. We generate policies with different novelty seeking methods, and use the PPO with different random seeds baseline. In each figure, the 5 lines indicate trajectories when the game is started from the right hand side. It worth noting that the results of WSR, CTNB and IPD are associated with the parameters of weights or threshold. We set the weight parameter in WSR as 10 to make the two reward terms comparable, and set the thresholds in CTNB and IPD as the averaged novelty between policies trained with PPO. All policies are trained with 6.1 x 10 episodes.
G.2 MUJOCO LOCOMOTION
In this section, we provide some qualitative results of IPD on the Mujoco locomotion tasks, In all of our experiments we use the vanilla Mujoco locomotion benchmarks, with the default settings on defining healthy states. Although otherwise the visualization of learned policies might become more diverse (e.g.. a Hopper agent may learn stand-up after falling down while another agent may learn to move forward on the ground if we set the z-axis healthy threshold as 0).
With the method of IPD, the Hopper policies (Figure 6) learns to jump further and avoids falling down rather instead of just jumping and falling down (Figure 7) In the Walker2d environment, the color of purple indicates the left leg is visible. It can be seen that the IPD policies (Figure ( learn to use both left and right legs in walking, while the PPO policies usually learn jumping. (Figure 9 In HalfCheetah, the IPD policies (Figure 10 perform much better than the PPO policies (Figure 11)
The IPD policies leran to run with head-downward (Figure line 1), head-upward (Figure 10 line 3), and forward (Figure T0 line 5) while the PPO policies are always head-downward.
In Hopper and HalfCheetah, IPD is able improve the primal task performance by avoiding always getting trapped in some certain sub-optimal behaviors.
15

---

Under review as a conference paper at ICLR 2021
1eard 52
Renord T020193
Genor:: 1451.69
1676,22
2227.38
Renor:: 2330115
REAOOE 2081.82
7730.T1
Reaord 2845.03
Figure The visualization of policy behaviors of agents trained by our method in Hopper-v3 environment. Agents learn to jump with different strides.
0enord 226.36
391.26
sesord: 901.16
Rehoro 419.09
930.31
Caodd 75
Renord 785.02
2231.88
Figure 7: The visualization of policy behaviors of agents trained by PPO Hopper-v3 environment. Most agents learn policy that can be described as Jump as far as possible and fall down, leading to relative poor performance.
16

---

Under review as a conference paper at ICLR 2021
Wenord: 1995.03
A
REMOrd: 10
2030.14
6876.47
Rehord: 2047.59
A
2279.93
Figure 8: The visualization of policy behaviors of agents trained by our method in Walker2d-v3 environment. Instead of bouncing at the ground using both legs, our agents learns to use both legs to step forward.
43
NEAORd 1475.18
REAOT:: 2045.40
NeAurd: 2079188
4
2397.83
Benord: 2520.10
Figure 9: The visualization of policy behaviors of agents trained by PPO in Walker2d-v3 environment. Most of the PPO agents only learn to use their right leg to support the body and jump forward.
17

---

Under review as a conference paper at ICLR 2021
Rehord: 1811.0
Renord: 18:0.15
Reword: 186
Reword: 1926./d
Reword: 1975.59
Reaurd: 2053.98
Reword: 2314.11
Figure 10: The visualization of policy behaviors of agents trained by our method in HalfCheetah-v3 environment. Our agents run much faster compared PPO agents and the mean time several patterns of motion have emerged.
Reword:
Reword 1i
Geword: 1219.70
aeard
Reword:
e ord: 1325.59
Rehord: 1327.93
1368.0
Scword 1493.22
Resord: 1601.52
Figure 11: The visualization of policy behaviors of agents trained by PPO in HalfCheetah-v3 environment. Since only draw fixed number of frames in each line, in the limited time steps the PPO agents can not run enough distance to leave the range of our drawing, which shows that our agents run much faster.
18


Reviews:
[{"review_id": "tMLMjipJE9", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper aims at novel policy seeking which incorporates curiosity-driven exploration for better reinforcement learning. This paper first propose to use  a Wasserstein-based metric to calculate the difference between policies, and use it to define  the policy novelty. With these, the authors modeled the novel policy seeking as a constrained markov decision process(CMDP) and solved it using CTNB and IPD.\n\n1. This paper allows to consider the novelity issue dynamically.  However, when training policy according to the proposed CTNB or IPD, there should be some pretrained policies as perconditions, in other words, the proposed method needs some prior knowledge rather than learning policy from scratch. This may be a limitation for its application.\n\n2. About the proposition 2, the single trajectory estimation is unbiased, however, the variance seems to be large, the influence about the estimation variance should be considered.\n\n3.  in fomula (5) and (6), is $r_{int, t}$ equal to $r_{int}$ ? If is,  why use t? and what does moving average mean since there are several kinds of moving averages?  \n\n4. in fomula (4) and (6), Are Ts the same?\n\n5. Fig.2  shows that in Waklker2d and HalfCheetah, the proposed CTNB has less novel than PPO, which doesn't match the purpose of CTNB.\n\n6. It seems not easy to tune the novelty threshold for different task, as it performs different on different tasks. Can the author provide some insight on how to tune this.\n\n7. Five random seeds is not sufficient for experiments. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "jOp2T9iGhp", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\n\nThis paper attempts to solve the problem of seeking novel policies in reinforcement learning from a constrained optimization perspective. This new perspective motives two new algorithms to solve the optimization problem, which are based on feasible direction and the interior point methods. The authors provide empirical results on several Mujoco benchmarks. \n\nDetails:\n\nThe idea of formulating the problem from a constrained optimization perspective is interesting. This new perspective motivates new and better algorithms to solve the optimization problem. \n\nHowever, I feel like the presentation is poor and the writing should be improved.  \n\nWhat’s the exact problem setting? The authors should clearly describe the problem setting before presenting the methods, even one paragraph would be helpful.  \n\nA lot of algorithm details are missing: \n\nQ1. $\\bar{D}^q_W (\\theta_i, \\theta_j)$ is a metric for any state distribution $q$. What’s the motivation of using $q = \\bar{\\rho}$? \n\nQ2. When computing the policy distance, what is $\\rho_{\\theta_i}$ in (4)? Is it the current policy, or a reference policy?\n\nQ3. I assume $\\theta_i$ is the current policy. According to (4), the algorithm uses $\\theta_i$ to get samples, and compute an importance correction ratio $q/\\rho_{\\theta_i}$ to approximate the distance. How is the $q(s)=\\bar{\\rho}(s)$ computed? The authors propose to approximate $\\rho_{\\theta}$ using monte-carlo methods. Does it mean the algorithm need to approximate $\\bar{\\rho}(s)$ using the reference policies for each $s\\sim \\rho_{\\theta_i}$? Is there a computation issue?\n\nQ4. This goes back to Q1. Why just using the on policy samples to estimate the distance? Is there any potential advantage to use $q = \\bar{\\rho}$? \n\nQ5. Learning the stationary distribution is a hard research problem itself. See recent work for example: \n\nZhang, R., Dai, B., Li, L. and Schuurmans, D., 2019, September. GenDICE: Generalized Offline Estimation of Stationary Values. In International Conference on Learning Representations.\n\nI agree the stationary distribution can be approximated using MC methods, but it might need a lot of samples as the variance is very high. This makes me wonder how is the algorithm implemented in practice, and how does the stationary distribution estimation subroutine affect the algorithm’s performance. \n\nOther suggestions:\n\nIf I understand correctly, this paper tries to solve the problem of finding a set of novel polices that solve a given task while exhibiting different behaviors. This seems also related to the exploration problem, as some works try to make the current policy different with previous policies to encourage exploration. See for example:\n\nHazan, E., Kakade, S., Singh, K. and Van Soest, A., 2019, May. Provably efficient maximum entropy exploration. In International Conference on Machine Learning (pp. 2681-2691). \n\nIt might be worth to discuss how the novel policy seeking problem is related to the exploration problem. \n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "NLAfW2ioxlH", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary: This paper proposed a method to leverage the constrained optimization for policy training to learn diverse policies given some references. Based on a diversity metric defined on policy divergences, the paper employs two constrained optimization techniques for this problem with some modifications. Experiments on mujoco environments suggest that the proposed algorithms can beat existing diversity-driven policy optimization methods to learn both better and novel policies. Generally, the paper is well-written and easy to follow. Some concerns/comments:\n\n* The state distributions of proposed CTNB and IPD are different: In the CTNB method, the trajectories will keep rollout until they reach some termination conditions such as time limit or failure behavior. However, in the IPD method, if the cumulative novel reward is below some thresholds, then the trajectories will be truncated. It will be helpful to compare the CTNB with that extra termination condition. \n\n* Using the divergence of policies to quantify the difference between policies seems not a very innovative metric. Some related work could be:\n\nHong, Z. W., Shann, T. Y., Su, S. Y., Chang, Y. H., Fu, T. J., & Lee, C. Y. (2018). Diversity-driven exploration strategy for deep reinforcement learning.\n\nIt will be great if the authors can compare and explain the relationship between the proposed metric and some related ones.\n\n* The experiments can be more convincing if more locomotion environments are included, especially some higher-dimensional environments such as Humanoid and HumanoidStandup. Also, some other environments with a long-term/sparse reward setting can be more illustrative such as some mazes or Atari games. For some of those games, since it is stage-based, the IPD might terminate some rollouts if all reasonable policies are similar at the beginning of the trajectory. For a maze example, all good policies should choose to open the door at the beginning and then behave diversely.  \n\nOther/Minor Comments:\n\n* The choice of r_0 can affect the performance: When sequentially training the policy, should r_0 be adjusted when training each new policy?\n\n* It can be more interesting if some visualization of hopper policy diversity is included.", "extra_scores": {}, "extra_text": {}}, {"review_id": "DHGXlNfDicD", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a novel constrained optimization based method, to optimize the expected return as well as encourage novelty of a new policy in contrast to existing policies. By modeling the problem as a constrained optimization problem, they can avoid excessive novelty seeking effectively, which is common in existing methods which model the problem with multi-objective optimization. \n\nTo be specific, they first propose a novel metric to measure the novelty of a new policy. To estimate such metric on sampled state with dense online reward, they propose an importance-based estimator for the proposed metric. With the estimation of the novelty metric, they propose to formulate the problem as a constrained optimization problem. The novelty is constrained to be larger than certain threshold r_0. In this way, the algorithm will only encourage larger novelty when the novelty is less than r_0, therefore avoiding excessive novelty seeking which may hurt the performance. They improve TNB proposed in (Zhang et al., 2019) with CTNB, where the ∇θg term exists only when the constraint is violated. They also propose another method based on Interior Point Method. Since IPM is computationally expensive and numerically unstable, they made an adaptation to RL setting, by bounding the collected transitions in the feasible region. \n\nOverall, the method is intuitive and reasonable. I have the following questions:\n\n1. The first contribution of this paper, is proposing a novel metric to measure the novelty of current policy in contrast to existing policies. Why propose a novel metric? Is existing metric for measuring the novelty not good? If so, can you verify your claim in experiments? \n\n2. The hyper-parameter r_0.  From Figure 3, we can see the different performance under different novelty thresholds r_0. The algorithm seems to be sensitive to r_0, which is of course reasonable. How did you choose r_0 for different environments? Did you consider a soft r_0 rather than a hard constraint(that is, maybe the constraint has different weight for different r_0)?", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper investigate the interesting problem of policy seeking in reinforcement learning via constrained optimization. Conditioned on reviewers' judgements, this is a good submission but hasn't reached the bar of ICLR.
Decision: Reject