summaries: The paper proposes Interior Policy Differentiation, a variant of Interior Point Method, for learning diverse policies in RL. The paper uses the empirical Wasserstein distance  to measure the difference between policies, then formulates the novel policy generation problem as a constrained optimization problem. However, the novelty of the paper is limited and the empirical evaluation is not convincing to make it pass the bar of ICLR 2022.  The paper explores a gradient-free constrained optimization framework for generating diverse policies. Its main contributions are: (i) a computationally light metric to measure the diversity of a policy with respect to an existing set of policies, based on the Wasserstein metric W2; (ii) a practical algorithm with instant feedback at every timestep, inspired by constrained optimization to generate diverse policies. Experiments on continuous benchmarks show that the proposed algorithm, IPD, can generate diverse as well as well-performing policies, and outperform competitors relying on multi-objective optimization. The authors describe an approach to regularise policy iteration methods towards regions of novel policies. They propose that constraint optimisation is superior to regularised objective functions. They attempt to to derive the algorithm form theoretical principles and demonstrate its superiority on a couple of artificial RL experiments.  The paper aims at enabling the learning algorithms with the capacity of solving the task with multiple solutions. The paper introduces a new metric to evaluate the difference between policies. It also proposes a practical novel policy-seeking algorithm, derived from the interior point method in the constrained optimization literature. The algorithm is evaluated on multiple mujoco tasks.
abstractText: In problem-solving, we humans tend to come up with different novel solutions to the same problem. However, conventional reinforcement learning algorithms ignore such a feat and only aim at producing a set of monotonous policies that maximize the cumulative reward. The resulting policies usually lack diversity and novelty. In this work, we aim at enabling the learning algorithms with the capacity of solving the task with multiple solutions through a practical novel policy generation workflow that can generate a set of diverse and well-performing policies. Specifically, we begin by introducing a new metric to evaluate the difference between policies. On top of this well-defined novelty metric, we propose to rethink the novelty-seeking problem through the lens of constrained optimization, to address the dilemma between the task performance and the behavioral novelty in existing multi-objective optimization approaches, we then propose a practical novel policy seeking algorithm, Interior Policy Differentiation (IPD), which is derived from the interior point method commonly known in the constrained optimization literature. Experimental comparisons on benchmark environments show IPD can achieve a substantial improvement over previous novelty-seeking methods in terms of both the novelty of generated policies and their performances in the primal task.1.
references.authors: Joshua Achiam David Held Aviv Tamar Pieter Abbeel
references.title: Constrained policy optimization
references.venue: In Proceedings of the 34th International Conference on Machine Learning-Volume
references.authors: Ilge Akkaya Marcin Andrychowicz Maciek Chociej Mateusz Litwin Bob McGrew Arthur Petron Alex Paino Matthias Plappert Glenn Powell Raphael Ribas
references.title: Solving rubik’s cube with a robot hand
references.authors: Eitan Altman
references.title: Constrained Markov decision processes, volume 7
references.venue: CRC Press,
references.authors: Martin Arjovsky Soumith Chintala Léon Bottou
references.title: Wasserstein generative adversarial networks
references.venue: Doina Precup and Yee Whye Teh (eds.), Proceedings of the 34th International Conference on Machine Learning,
references.authors: Adrià Puigdomènech Badia Bilal Piot Steven Kapturowski Pablo Sprechmann Alex Vitvitskyi Zhaohan Daniel Guo Charles Blundell
references.title: Agent57: Outperforming the atari human benchmark
references.venue: In International Conference on Machine Learning,
references.authors: Christopher Berner Greg Brockman Brooke Chan Vicki Cheung Przemysław Debiak Christy Dennison David Farhi Quirin Fischer Shariq Hashme Chris Hesse
references.title: Dota 2 with large scale deep reinforcement learning
references.venue: arXiv preprint arXiv:1912.06680,
references.authors: Yuri Burda Harri Edwards Deepak Pathak Amos Storkey Trevor Darrell Alexei A Efros
references.title: Large-scale study of curiosity-driven learning
references.venue: arXiv preprint arXiv:1808.04355,
references.authors: Yuri Burda Harrison Edwards Amos Storkey Oleg Klimov
references.title: Exploration by random network distillation
references.venue: arXiv preprint arXiv:1810.12894,
references.authors: Yinlam Chow Ofir Nachum Edgar Duenez-Guzman Mohammad Ghavamzadeh
references.title: A lyapunovbased approach to safe reinforcement learning
references.venue: In Advances in neural information processing systems,
references.authors: Kamil Ciosek Quan Vuong Robert Loftin Katja Hofmann
references.title: Better exploration with optimistic actor critic
references.venue: In Advances in Neural Information Processing Systems,
references.authors: A Conn Nick Gould Ph Toint
references.title: A globally convergent lagrangian barrier algorithm for optimization with general inequality constraints and simple bounds
references.venue: Mathematics of Computation of the American Mathematical Society,
references.authors: Edoardo Conti Vashisht Madhavan Felipe Petroski Such Joel Lehman Kenneth Stanley Jeff Clune
references.title: Improving exploration in evolution strategies for deep reinforcement learning via a population of novelty-seeking agents
references.venue: In Advances in Neural Information Processing Systems,
references.authors: George B Dantzig Mukund N Thapa
references.title: Linear programming 2: theory and extensions
references.venue: Springer Science & Business Media,
references.authors: Mahmoud Elbarbari Kyriakos Efthymiadis Bram Vanderborght Ann Nowé
references.title: Ltlf-based reward shaping for reinforcement learning
references.venue: In Adaptive and Learning Agents Workshop
references.authors: Dominik Maria Endres Johannes E Schindelin
references.title: A new metric for probability distributions
references.venue: IEEE Transactions on Information theory,
references.authors: Benjamin Eysenbach Abhishek Gupta Julian Ibarz Sergey Levine
references.title: Diversity is all you need: Learning skills without a reward function
references.venue: arXiv preprint arXiv:1802.06070,
references.authors: Bent Fuglede Flemming Topsoe
references.title: Jensen-shannon divergence and hilbert space embedding
references.venue: In International Symposium onInformation Theory,
references.authors: Scott Fujimoto Herke Van Hoof David Meger
references.title: Addressing function approximation error in actor-critic methods
references.venue: arXiv preprint arXiv:1802.09477,
references.authors: Tuomas Haarnoja Aurick Zhou Pieter Abbeel Sergey Levine
references.title: Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor
references.venue: arXiv preprint arXiv:1801.01290,
references.authors: Yuval Noah Harari
references.title: Sapiens: A brief history of humankind
references.venue: Random House,
references.authors: Peter Henderson Riashat Islam Philip Bachman Joelle Pineau Doina Precup David Meger
references.title: Deep reinforcement learning that matters
references.venue: In Thirty-Second AAAI Conference on Artificial Intelligence,
references.authors: Joseph Henrich
references.title: The secret of our success: How culture is driving human evolution, domesticating our species, and making us smarter
references.authors: José Herskovits
references.title: Feasible direction interior-point technique for nonlinear optimization
references.venue: Journal of optimization theory and applications,
references.authors: Zhang-Wei Hong Tzu-Yun Shann Shih-Yang Su Yi-Hsiang Chang Tsu-Jui Fu Chun-Yi Lee
references.title: Diversity-driven exploration strategy for deep reinforcement learning
references.venue: In Advances in Neural Information Processing Systems,
references.authors: Rein Houthooft Xi Chen Yan Duan John Schulman Filip De Turck Pieter Abbeel
references.title: Variational information maximizing exploration
references.authors: Edward Hughes Joel Z Leibo Matthew Phillips Karl Tuyls Edgar Dueñez-Guzman Antonio Garcı́a Castañeda Iain Dunning Tina Zhu Kevin McKee Raphael Koster
references.title: Inequity aversion improves cooperation in intertemporal social dilemmas
references.venue: In Advances in neural information processing systems,
references.authors: Natasha Jaques Angeliki Lazaridou Edward Hughes Caglar Gulcehre Pedro Ortega Dj Strouse Joel Z Leibo Nando De Freitas
references.title: Social influence as intrinsic motivation for multi-agent deep reinforcement learning
references.venue: In International Conference on Machine Learning,
references.authors: Adam Daniel Laud
references.title: Theory and application of reward shaping in reinforcement learning
references.venue: University of Illinois at Urbana-Champaign,
references.authors: Timothy P Lillicrap Jonathan J Hunt Alexander Pritzel Nicolas Heess Tom Erez Yuval Tassa David Silver Daan Wierstra
references.title: Continuous control with deep reinforcement learning
references.venue: arXiv preprint arXiv:1509.02971,
references.authors: Hao Liu Alexander Trott Richard Socher Caiming Xiong
references.title: Competitive experience replay
references.venue: CoRR, abs/1902.00528,
references.authors: Deepak Pathak Pulkit Agrawal Alexei A Efros Trevor Darrell
references.title: Curiosity-driven exploration by self-supervised prediction
references.venue: In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition Workshops,
references.authors: Alexander Peysakhovich Adam Lerer
references.title: Consequentialist conditional cooperation in social dilemmas with imperfect information
references.venue: arXiv preprint arXiv:1710.06975,
references.authors: Florian A Potra Stephen J Wright
references.title: Interior-point methods
references.venue: Journal of Computational and Applied Mathematics,
references.authors: Justin K Pugh Lisa B Soros Kenneth O Stanley
references.title: Quality diversity: A new frontier for evolutionary computation
references.venue: Frontiers in Robotics and AI,
references.authors: Jette Randløv Preben Alstrøm
references.title: Learning to drive a bicycle using reinforcement learning and shaping
references.venue: In ICML,
references.authors: Alex Ray Joshua Achiam Dario Amodei
references.title: Benchmarking safe exploration in deep reinforcement learning
references.venue: openai,
references.authors: Barbara Rogoff
references.title: Apprenticeship in thinking: Cognitive development in social context
references.venue: Oxford university press,
references.authors: Ludger Rüschendorf
references.title: The wasserstein distance and approximation theorems
references.venue: Probability Theory and Related Fields,
references.authors: Andrzej Ruszczyński
references.title: Feasible direction methods for stochastic programming problems
references.venue: Mathematical Programming,
references.authors: Richard M Ryan Edward L Deci
references.title: Intrinsic and extrinsic motivations: Classic definitions and new directions
references.venue: Contemporary educational psychology,
references.authors: John Schulman Sergey Levine Pieter Abbeel Michael Jordan Philipp Moritz
references.title: Trust region policy optimization
references.venue: In International conference on machine learning,
references.authors: John Schulman Filip Wolski Prafulla Dhariwal Alec Radford Oleg Klimov
references.title: Proximal policy optimization algorithms
references.venue: arXiv preprint arXiv:1707.06347,
references.authors: Pedro Sequeira Francisco S Melo Rui Prada Ana Paiva
references.title: Emerging social awareness: Exploring intrinsic motivation in multiagent learning
references.venue: In 2011 IEEE International Conference on Development and Learning (ICDL),
references.authors: Archit Sharma Shixiang Gu Sergey Levine Vikash Kumar Karol Hausman
references.title: Dynamics-aware unsupervised discovery of skills
references.venue: arXiv preprint arXiv:1907.01657,
references.authors: Felipe Petroski Such Vashisht Madhavan Rosanne Liu Rui Wang Pablo Samuel Castro Yulun Li Ludwig Schubert Marc Bellemare Jeff Clune Joel Lehman
references.title: An atari model zoo for analyzing, visualizing, and comparing deep reinforcement learning agents
references.venue: arXiv preprint arXiv:1812.07069,
references.authors: Hao Sun Ziping Xu Meng Fang Zhenghao Peng Jiadong Guo Bo Dai Bolei Zhou
references.title: Safe exploration by solving early terminated mdp
references.venue: arXiv preprint arXiv:2107.04200,
references.authors: Richard S Sutton Andrew G Barto
references.title: Introduction to reinforcement learning, volume 2
references.venue: MIT press Cambridge,
references.authors: Chen Tessler Guy Tennenholtz Shie Mannor
references.title: Distributional policy optimization: An alternative approach for continuous control
references.venue: arXiv preprint arXiv:1905.09855,
references.authors: Emanuel Todorov Tom Erez Yuval Tassa
references.title: Mujoco: A physics engine for model-based control
references.venue: In IROS, pp. 5026–5033
references.authors: Carel P van Schaik Judith M Burkart
references.title: Social learning and evolution: the cultural intelligence hypothesis
references.venue: Philosophical Transactions of the Royal Society B: Biological Sciences,
references.authors: Cédric Villani
references.title: Optimal transport: old and new, volume 338
references.venue: Springer Science & Business Media,
references.authors: Oriol Vinyals Igor Babuschkin Wojciech M Czarnecki Michaël Mathieu Andrew Dudzik Junyoung Chung David H Choi Richard Powell Timo Ewalds Petko Georgiev
references.title: Grandmaster level in starcraft ii using multi-agent reinforcement learning
references.authors: Stephen J Wright
references.title: On the convergence of the newton/log-barrier method
references.venue: Mathematical Programming,
references.authors: Yunbo Zhang Wenhao Yu Greg Turk
references.title: Learning novel policies for tasks
references.venue: In International Conference on Machine Learning,
sections.heading: 1 INTRODUCTION
sections.text: In the sense of learning through interactions with the environment, the scheme of reinforcement learning (RL) is conceptually similar to the emergence of intelligence (Sutton et al., 1998): an agent explores and exploits information of a given environment, learns to master some certain skills through trials and errors to gain as much reward as possible. When solving a problem, we humans could be creative to come up with multiple different solutions and gain insights from searching for diverse solutions. e.g., a self-containing example is the various approaches in RL research.
  While the state-of-the-art algorithms have achieved superhuman performance in a variety of challenging tasks (Vinyals et al., 2019; Akkaya et al., 2019; Berner et al., 2019; Badia et al., 2020; Elbarbari et al., 2021), the task of encouraging individualized diversity 2 of learned agents, on the other hand, is relatively under-explored. Different from conventional RL agents that are only learned through interactions with the external environment, novel policy generation is a task considering the differentiation among individual policies. The differentiation among policies can be explained as the social influence (Rogoff, 1990; Ryan & Deci, 2000; van Schaik & Burkart, 2011; Henrich, 2017; Harari, 2014) in social science literature. Although many works have been proposed applying social motivation to Multi-Agent Reinforcement Learning (MARL) settings (Jaques et al., 2019; Hughes et al., 2018; Sequeira et al., 2011; Peysakhovich & Lerer, 2017), how to motivate a single RL agent to perform differently against existing agents is still an open question.
  In previous attempts for novel policy generation, there are three main challenges: (1) heuristically defined metric for novelty estimation is computational expensive (Zhang et al., 2019), (2) defining novelty reward for an entire episode yields additional challenge in credit assignment, and (3) solving
  1Code is included in the supplemental material. 2Note that this is different from diversity-driven exploration. While the latter focuses on the inner-diversity
  of a policy, in our work we focus on the inter-diversity between policies
  the problem under the formulation of multi-objective optimization leads to the performance decay in the original task. Fig. 1 compares the policy gradients of three cases, namely the one without novel policy seeking, novelty-seeking with multi-objective optimization, and novelty-seeking with constrained optimization methods, respectively.
  In this work we take into consideration not only the novelty of a set of learned policies but also the performance of those novel policies in the primal task, when addressing the problem of novel-policygeneration. Our contributions can be summarized as follows:
  1. We introduce a lightweight metric to compute the difference between policies with instant feedback at every timestep, to address the first two drawbacks of previous novel policy seeking methods discussed above;
  2. We propose a constrained optimization formulation for novel policy generation and design a practical algorithm of IPD, resembling the interior point method in constrained optimization literature;
  3. The proposed method, IPD, is evaluated on several continuous control benchmarks, showing the strengths of our constrained optimization solution for novelty-seeking can generate a series of diverse and well-performing policies, compared to previous multi-objective novel policy generation methods.
sections.heading: 2 RELATED WORK
sections.text: 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 et al., 2016; Pathak et al., 2017; Burda et al., 2018a;b; Liu et al., 2019). All those approaches use the weighted sum of two rewards, the primal rewards provided by environments and the intrinsic rewards provided by different heuristics. On the other hand, the work of DIAYN and DADS (Eysenbach et al., 2018; Sharma et al., 2019) learn diverse skills without extrinsic reward. Those approaches focus on decomposing diverse skills of a single policy, while our work focuses on learning diverse behaviors among a batch of policies for the same task.
  Diverse policy generation 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 learning different policies through a single algorithm with the capability of avoiding local optimum. The work of Pugh et al. establishes a standard framework for understanding and comparing different approaches to search for quality diversity (QD) (Pugh et al., 2016). Conti et al. proposes a 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 et al.,
  2019) aims to solve novel policy generation problem by jointly optimize the extrinsic rewards and novelty rewards defined by an auto-encoder. In this work, we first adopt TNB in the constrained optimization framework, resulting in Contrained TNB, to demonstrate the dilemma between the task performance and novelty pursuance.
  Constrained Markov Decision Process. The Constrained Markov Decision Process (CMDP) (Altman, 1999) considers the situation where an agent interacts with the environment under certain constraints. Formally, the CMDP can be defined as a tuple (S,A, γ, r, c, C, P, s0), where S andA are the state and action space; γ ∈ [0, 1) is a discount factor; r : S×A×S → R and c : S×A×S → R denote the reward function and cost function; C ∈ R+ is the upper bound of permitted expected cumulative cost; P (·|s, a) : S ×A → S denotes the transition dynamics, and s0 is the initial state. Denote the Markovian policy class as Π, where Π = {π : S × A → [0, 1], ∑ a π(a|π) = 1} The learning objective of a policy for CMDP is to find a π∗ ∈ Π, such that
  π∗ = max π∈Π Eτ∼π,s′∼P [ ∞∑ t=0 γtr(s, a, s′)], s.t. Eτ∼π,s′∼P [ ∞∑ t=0 γtc(s, a, s′)] ≤ C, (1)
  where τ indicates a trajectory (s0, a0, s1, ...) and τ ∼ π represents the distribution over trajectories following policy π: at ∼ π(·|st), st+1 ∼ P (·|st, at); t = 0, 1, 2, .... Previous literature provide several approaches to solve CMDP (Achiam et al., 2017; Chow et al., 2018; Ray et al., 2019; Sun et al., 2021).
  In Sec.2.1, we define a metric space that measures the difference between policies, which is the fundamental element for the proposed methods. In Sec.2.2, we develop a practical estimation method for this metric. Sec.2.3 describes the formulation of constrained optimization on novel policy generation. The implementations of two practical algorithms are further introduced in Sec.2.4.
  We denote the policies as {πθi ; θi ∈ Θ, i = 1, 2, ...}, wherein θi represents parameters of the i-th policy, Θ denotes the whole parameter space. In this work, we focus on improving the behavioral diversity of policies from PPO (Schulman et al., 2017), thus we use Θ to represent ΘPPO in this paper. It is worth noting that the proposed methods can be easily extended to other RL algorithms (Schulman et al., 2015; Lillicrap et al., 2015; Fujimoto et al., 2018; Haarnoja et al., 2018). To simplify the notation, we omit π and denote a policy πθi as θi unless stated otherwise.
sections.heading: 2.1 MEASURING THE DIFFERENCE BETWEEN POLICIES
sections.text: We use the Wasserstein metric Wp (Rüschendorf, 1985; Villani, 2008; Arjovsky et al., 2017) to measure the distance between policies. Concretely, we consider the Gaussian-parameterized policies, where the Wp over two policies can be written in the closed form W 22 (N (m1,Σ1),N (m2,Σ2)) = ||m1 −m2||2 + tr[Σ1 + Σ2 − 2(Σ1/21 Σ2Σ 1/2 1 )
  1/2] as p = 2, where m1,Σ1,m2,Σ2 are mean and covariance metrics of the two normal distributions. In the following of this paper, we use DW to denote the W2 and it is worth noting that for the deterministic policy class, the trace term disappears and the only term involving the means remains, i.e., DW = |m1 − m2| for Dirac delta policies located at points m1 and m2. This diversity metric satisfies the three properties of a metric, namely identity, symmetry as well as triangle inequality.
  Proposition 1 (Metric Space (Θ, DqW )). The expectation of DW (·, ·) of two policies over any state distribution q(s):
  D q
  W (θi, θj) := Es∼q(s)[DW (θi(a|s), θj(a|s))], (2)
  is a metric on Θ, thus (Θ, D q
  W ) is a metric space.
  The proof of Proposition 1 is straightforward. It is worth mentioning that although the KL-divergence is commonly applied in measuring differences between policies (Schulman et al., 2015; 2017; Hong et al., 2018). It can not be used directly as a metric for novelty quantification as the symmetric property do not hold. In this sense, the Jensen Shannon divergence DJS and Total Variance Distance DTV (Endres & Schindelin, 2003; Fuglede & Topsoe, 2004; Schulman et al., 2015) can be also used as alternative choices, 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 (Θ, D q
  W ), the novelty of a policy can be computed as follows,
  Definition 1 (Novelty of Policy). Given a reference policy set Θref such that Θref = {θrefi , i = 1, 2, ...},Θref ⊂ Θ, the novelty U(θ|Θref) of policy θ is the minimal difference between θ and all policies in the reference policy set, i.e.,
  U(θ|Θref) := min θj∈Θref
  D q
  W (θ, θj), (3)
  Consequently, to encourage the discovery of novel policies discovery, typical novel policy generation methods tend to directly maximize the novelty of a new policy, i.e., maxθ U(θ|Θref ), where Θref includes all existing policies.
  2.2 ESTIMATION OF D q
  W (θi, θj) AND THE SELECTION OF q(s)
  In practice, the calculation of D q
  W (θi, θj) is based on Monte Carlo estimation where we need to sample s from q(s). Although in Eq.(2) q(s) can be selected simply as a uniform distribution over the state space, there remains two obstacles: first, in a 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 s is sampled from a uniform distribution q, we can only get sparse episodic reward instead of dense online reward which is more useful in learning. Therefore, we make an approximation here based on importance sampling.
  Formally, we denote the domain of q(s) as Sq ⊂ S and assume q(s) to be a uniform distribution over Sq , without loss of generality in later analysis. Notice Sq is closely related to the algorithm being used in generating trajectories (Henderson et al., 2018). As we only care about the reachable regions of a certain algorithm (in this work, PPO), the domain Sq can be decomposed by Sq = limN→∞ ⋃N i=1 Sθi , where Sθi denotes all the possible states a policy θi can visit given a starting state distribution. In order to get online-reward, we estimate Eq.(2) with
  D q W (θi, θj) = Es∼q(s)[DW (θi(a|s), θj(a|s))] = Es∼ρθi (s)[ q(s)
  ρθi(s) DW (θi(a|s), θj(a|s))], (4)
  where we use ρθ(s) to denote the stationary state visitation frequency under policy θ, i.e., ρθ(s) = P (s0 = s|θ) + P (s1 = s|θ) + ... + P (sT = s|θ) in finite horizon problems. We propose to use the averaged stationary visitation frequency as q(s), e.g., for PPO, q(s) = ρ(s) = Eθ∼ΘPPO [ρθ(s)]. Clearly, choosing q(s) = ρ(s) will be much better than choosing a uniform distribution as the importance weight will be closer to 1. Such an importance sampling process requires a necessary condition that ρθi(s) and q(s) have the same domain, which can be guaranteed by applying a sufficient exploration noise on θ.
  Another difficulty lies in the estimation of ρ(s), which is always intractable given a limited number of trajectories. However, during training, θi is a policy to be optimized and θj ∈ Θref is a fixed reference policy. The error introduced by approximating the importance weight as 1 will get larger when θi becomes more distinct from normal policies, at 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 ρθ(s) 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, and indicates that with a sufficiently large number of trajectories, we are able to access the exact value of novelty. Given the definition of novelty and a practically unbiased sampling method, the next step is to develop an efficient learning algorithm.
sections.heading: 2.3 CONSTRAINED OPTIMIZATION FORMULATION FOR NOVEL POLICY GENERATION
sections.text: In the conventional RL paradigm, maximizing the expectation of cumulative rewards is commonly used as the objective. i.e., maxθ∈Θ Eτ∼θ[g], where g = ∑ t=0 γ
  trt and τ ∼ θ denotes a trajectory τ sampled from the policy θ.
  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
  et al., 2016; Pathak et al., 2017; Burda et al., 2018a;b; Liu et al., 2019) often directly use the weighted sum of these two terms as the objective:
  max θ∈Θ Eτ∼θ[gtotal] = max θ∈Θ Eτ∼θ[α · gtask + (1− α) · gint], (5)
  where 0 < α < 1 is a weight hyper-parameter, gtask is the reward from the primary task, and gint = ∑ t=0 γ trint,t is the cumulative intrinsic reward of the intrinsic reward rint,t. In our case, the intrinsic reward is the novelty reward rint = minθj∈Θref D ρ
  W (θ, θj). These methods can be summarized as Weighted Sum Reward (WSR) methods. 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 rint as minθj D ρ W (θ, θj), exp [minθj D ρ W (θ, θj)] and − exp [−minθj D ρ
  W (θ, θj)] will lead to significantly different results as they determine the trade-offs in the two terms given α. Besides, dilemma also arises in the selection of α: while a large α may undermine the contribution of intrinsic reward, a small α could ignore the importance of the primal task, leading to the failure of an agent in solving the task.
  The crux of tackling such an issue 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. However, as TNB considers the novelty gradient all the time, it may hinder the learning process. Intuitively, well-performing policies should be more similar to each other than to random initialized policies. As a new random initialized policy is different enough from previous policies, considering the novelty gradient at beginning of training will result in a much slower learning process. We also observe such a problem in experiments that TNB not only fails to find well-performing policies, but also fails in the novelty seeking as all policies are driven away from original performance-pursuing-only policies.
  In order to tackle the above problems and adjust the extent of novelty in new policies, we propose to solve the novelty-seeking problem under the perspective of constrained optimization. The intuition is 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, thus should not impede the learning of the primal task. Fig. 1 illustrates how novelty gradients impede the learning of a policy: at the beginning of learning, a random initialized policy should learn to be more similar to a well-performing policy rather than be different. The seeking of novelty should not be taken into consideration all the time during learning. With such an insight, we update the multi-objective optimization problem in Eq.(5) into a constrained optimization problem as:
  max θ∈Θ
  f(θ) = Eτ∼θ[gtask], s.t. gt(θ) = rint,t − r0 ≥ 0,∀t = 1, 2, ..., T, (6)
  where r0 is a threshold indicating minimal permitted novelty. In practice, we can use the averaged diversity of a batch of agents trained with PPO as r0, motivating our diversity-seeking policies to achieve a higher novelty, therefore, there is only a little need for a hyper-parameter tuning. rint,t denotes a moving average of rint,t as we need not force every single action of a 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 tS timesteps (e.g., tS = 20) for the consideration of similar starting sequences, so that the constraints can be written as gt(θ) ≥ 0,∀t = tS , ..., T .
sections.heading: 2.4 PRACTICAL NOVEL POLICY GENERATION METHODS
sections.text: One thing to note is that WSR and TNB proposed in the prior work (Zhang et al., 2019) correspond to different approaches in constrained optimization problems, yet some important ingredients are missing. We in this section adopt TNB according to the Feasible Direction Method in constrained optimization and then propose our method of Interior Policy Differentiation (IPD), according to the Interior Point Method in constrained optimization literature. A detailed discussion on WSR is provided in Appendix D.
  TNB: Feasible Direction Method The Feasible Direction Method (FDM) (Ruszczyński, 1980; Herskovits, 1998) solves the constrained optimization problem by finding a direction ~p where taking gradient upon will lead to the increment of the objective function as well as constraints satisfaction,
  Algorithm 1 IPD (Ours) 1: Input: (1) a behavior policy θold, (2) a set of previous policies {θj}Mj=1, (3) a novelty metric U(θ, {θj}|ρ) = U(θ, {θj}|τ) = minθj D τ W (θ, θj), (4) a novelty
  threshold r0 and starting point tS . 2: Initialize θold. 3: for iteration = 1, 2, ... do 4: for t = 1, 2, ..., T do 5: Step the environment by tak-
  ing action at ∼ θold and collect transitions.
  6: if U(θold, {θj}|τ) − r0 < 0 AND t > tS then 7: Break this episode. 8: end if 9: end for 10: Update policy parameters based on sampled data. 11: end for
  Algorithm 2 Constrained TNB (For Comparison) 1: Input: (1-4) same as IPD, (5) a value network for cost Vc. 2: Initialize θold. 3: for iteration = 1, 2, ... do 4: for t = 1, 2, ..., T do 5: Step the environment by taking action at ∼ θold and
  collect transitions. 6: end for 7: Compute advantage of reward ˆAr,1, ..., ˆAr,T . 8: Compute advantage of cost ˆAc,1, ..., ˆAc,T . 9: Optimize objective for reward LCLIPr , with gradient gr =
  ∇θLCLIPr . 10: Optimize objective for cost LCLIPc , with gradient gc = −∇θLCLIPc 11: if U(θold, {θj}|τ)− r0 < 0 then 12: Calculate ~p according to Eq.(7) with gr and gc 13: else 14: Calculate ~p with gr 15: end if 16: Update policy parameters 17: end for
  i.e.,∇θfT · ~p > 0, if g > 0 and∇θgT · ~p > 0 otherwise. The TNB proposes to use a revised bisector of gradients ∇θf and ∇θg as ~p,
  ~p = { ∇θf + |∇θf ||∇θg|∇θg, if cos (∇θf,∇θg) > 0 ∇θf + |∇θf ||∇θg|∇θg · cos (∇θf,∇θg), otherwise,
  (7)
  Clearly, Eq.(7) satisfies the constraints but it is more strict than it as the ∇θg 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∇θg on g. It is clear that TNB is a special case of CTNB when the novelty threshold r0 is set to infinity. We note that in both TNB and CTNB, the learning stride is fixed to be |∇θf |+|∇θg|2 and may lead to problem when∇θf → 0, 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. We propose CTNB in our work, as a constrained optimization vairant of TNB, to demonstrate the importance of the constrained optimization perspective in novelty seeking, however, we do not in practice observe such a method achieves satisfactory performance.
  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 Eq.(6) is solved by reforming it to an unconstrained form with an additional barrier term −α log g(θ) in the objective as maxθ∈Θ f(θ)− α log g(θ), or more precisely in our problem with the formulation with Eq.(6) we have maxθ∈Θ Eτ∼θ[gtask − ∑T t=0 α log (rint,t − r0)], where α > 0 is the barrier factor. Besides the log barrier term, there are other choices like α 1g(θ) can be used and the objective becomes maxθ∈Θ f(θ) + α 1g(θ) . 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.(6). The convergence of such methods are provided in previous works (Conn et al., 1997; Wright, 2001).
  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: we 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 θi ∈ Θref, i = 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.
  Remark 1 (Reward-Shaping-Agnostic Novelty Seeking). IPD is a gradient-free method with regard to the novelty reward.
  Remark 1 is an important property that only IPD owns. For other approaches, including both multiobjective approaches and constrained optimization approaches, an elaborated design of the novelty reward function is needed, e.g., it can be any monotonic increasing function of D ρ
  W . While it is well-known that reward shaping (Randløv & Alstrøm, 1998; Laud, 2004) is in general a non-trivial work that requires domain knowledge (Vinyals et al., 2019; Akkaya et al., 2019; Berner et al., 2019; Elbarbari et al., 2021), such an additional novelty-reward term further increases the burden of proper reward design.
  Differently, the seeking of novelty in IPD does not require any (policy) gradient information that flows from the novelty reward, therefore, the selection of reward scaling function is agnostic to the performance of IPD. IPD learns to become novel in a passive manner, i.e., an episode will be terminated whenever the averaged step-wise novelty is lower than a given threshold. Searching in a constant hyper-parameter space is at least tractable while searching in a monotonically increasing functional reward shaping class (Zhang et al., 2019) is not – let alone IPD works well with a default novelty threshold parameter r0 = averaged differences between PPO policies.
sections.heading: 3 EXPERIMENTS
sections.text: According to Proposition 2, the novelty reward rint in Eq.(6) under our novelty metric can be unbiasedly approximated by rint = minθj∈Θref D ρθ W (θ(a|st), θj(aj |st)). We thus utilize this novelty metric directly throughout our experiments. We apply different novel policy generation 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 E.
  Experiments in the work of Henderson et al. (2018) show that one can simply change the random seeds before training to get policies that perform differently. Therefore, we use PPO with varying random seeds as a baseline method for novel policy generation and use the averaged differences between policies learned by this baseline as the default threshold r0 in CTNB and IPD. Algorithm 1 and Algorithm 2 show the pseudo code of IPD and CTNB based on PPO, where the blue lines show the additional code added to the standard PPO. Qualitative results can be found in Appendix G.
sections.heading: 3.1 THE FOUR REWARD MAZE PROBLEM
sections.text: We first utilize a basic 2-D environment named Four Reward Maze as a 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 to four middle points with radius 1 on each edge in a 2-D N ×N square map. We use N = 16 in our experiments. The observation of a policy is the current position and the agent will receive a 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 is limited to [−1, 1]. The performance of each agent is evaluated by the averaged performances over 100 trials.
  Results are shown in Fig. 2, where the behaviors of the PPO agents are quite similar, suggesting the diversity provided by random seeds is limited. WSR and TNB solve the novel policy generation 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 TNB due to an encumbered learning process, as we analyzed in Sec.2.3. Both CTNB and IPD, solving the task with novelty-seeking from the constrained optimization formulation, provide evident behavior diversity and perform recognizably better than TNB and WSR.
sections.heading: 3.2 THE MUJOCO BENCHMARK
sections.text: We evaluate our proposed method on three locomotion tasks (Brockman et al., 2016; Todorov et al., 2012): the Hopper-v3 (11 observations and 3 actions), Walker2d-v3 (11 observations and 6 actions), and HalfCheetah-v3 (17 observations and 6 actions). Although relaxing the healthy termination thresholds in Hopper and Walker may permit more visible behavior diversity, all the environment parameters are set as default values in our experiments to demonstrate the generality of our method.
sections.heading: 3.2.1 COMPARISON ON NOVELTY AND PERFORMANCE
sections.text: We implement WSR, TNB, CTNB, and IPD using the same hyper-parameter settings per environment. And we also apply CPO (Achiam et al., 2017) as a baseline as a solution of CMDP. For each method, we first train 10 policies using PPO with different random seeds. Those PPO policies are used as 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 11 policies, and so on. More implementation details are depicted in Appendix E.
  Fig. 3 shows the 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 generation. Specifically, the results of CTNB are
  all better than their multi-objective counterparts from TNB, showing the superiority of generating novel policies with constrained optimization. In all experiments we use a linear novelty reward function, i.e., rint = minθj D ρ
  W (θ, θj). We attribute the failure of CPO, TNB and CTNB in Walker and HalfCheetah in finding novel policies to that their convergence behavior is fully controlled by the reward scaling function. Whereas in IPD, there is no novelty-gradient controlled by such a scaling function. The IPD method consistently provides more novelty than CTNB and CPO, while the primal task performances are still guaranteed.
  Comparisons of the task-related rewards are carried out in Table 1, 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 to fall into the same local minimum. (e.g., they all jump as 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 RL schemes to tackle the local exploration challenge (Tessler et al., 2019; Ciosek et al., 2019). A similar feature brings about reward growth in the environment of HalfCheetah.
sections.heading: 3.2.2 SUCCESS RATE OF EACH METHOD
sections.text: In addition to 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 a policy successful when its performance achieves at least as good as the median performance of policies trained with PPO. To be specific, we use the median of the final performance of PPO as the baseline, and if a novel policy, which aims at performing differently to 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 as a baseline for every environment. Table 1 shows the success rate of all the methods. The results show that all constrained novel policy generation 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 novel policy generation methods can always be insured.
sections.heading: 4 CONCLUSION
sections.text: 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, on top of which we define the novelty of a policy. Based on our formulation of constrained optimization, we provide practical algorithms for constrained novel policy learning, we evaluate several constrained policy optimization methods: namely the CPO, Constrained TNB, and the Interior Policy Differentiation (IPD) proposed in this work. Our experimental results demonstrate IPD, as a novelty (policy) gradient-free approach, can effectively learn various well-performing yet diverse policies, outperforming previous multi-objective methods, as well as constrained optimization baselines.
  ETHICS STATEMENT
  In this work, we study the problem of diverse policy generation. Although in this work we empirically demonstrate the effectiveness of the proposed algorithm and learning framework on simulated reinforcement learning benchmarks, we believe there are lots of real-world applications of reinforcement learning that can be potentially benefited from our research. To name some examples: first and foremost, behavior diversity itself is precious in that it enables reinforcement learning agents to have their characteristics, being able to generate various well-performing agents will improve the interactive experience in games with both human and AI players. Moreover, as learning novel policies can help to escape from local-optimal solutions, it can potentially benefit downstream tasks such as cooperative exploration. Human society indeed needs individual diversity in cooperatively exploring and exploiting knowledge. Last but not least, diversity helps species in evolution from the perspective of survival of the fittest, therefore agents trained to finish the task with distinct behavior can potentially benefit the robustness of the population under environmental changes.
  REPRODUCIBILITY STATEMENT
  We include our code in the supplementary materials. More implementation details of our experiments are provided in Appendix E.
sections.heading: A METRIC SPACE
sections.text: Definition 2. A metric space is an ordered pair (M,d) where M is a set and d is a metric on M , i.e., a function d : M ×M → R such that for any x, y, z ∈M , the following holds: 1. d(x, y) ≥ 0, d(x, y) = 0⇔ x = y, 2. d(x, y) = d(y, x), 3. d(x, z) ≤ d(x, y) + d(y, z).
sections.heading: B PROOF OF PROPOSITION 1
sections.text: The first two properties are obviously guaranteed by D ρ
  W . As for the triangle inequality, Es∼ρ(s)[DW (θi(s), θk(s)]
  = Es∼ρ(s)[ |A|∑ l=1 |θi(s)− θk(s)|] = Es∼ρ(s)[ |A|∑ l=1 |θi(s)− θj(s) + θj(s)− θk(s)|] ≤ Es∼ρ(s)[ (|A|∑ l=1 |θi(s)− θj(s)|+ |θj(s)− θk(s)|)] = Es∼ρ(s)[ |A|∑ l=1 |θi(s)− θj(s)|] + Es∼ρ(s)[ |A|∑ l=1 |θj(s)− θk(s)|]
  = Es∼ρ(s)[DW (θi(s), θj(s)] + Es∼ρ(s)[DW (θj(s), θk(s)]
sections.heading: C PROOF OF PROPOSITION 2
sections.text: ρθ(s) = P (s0 = s|θ) + P (s1 = s|θ) + ...+ P (sT = s|θ)
  L.L.N. = lim
  N→∞
  ∑N i=1 I(s0 = s|τi)
  N +
  ∑N i=1 I(s1 = s|τi)
  N + ...+
  ∑N i=1 I(sT = s|τi)
  N
  = lim N→∞
  ∑T j=0 ∑N i=1 I(sj = s|τi) N
  ρθ(s) = N∑ i=1 T∑ j=0 I(sj = s|τi) N
  E[ρθ(s)− ρθ(s)] = 0
sections.heading: D MORE DETAILS ON WSR
sections.text: WSR: Penalty Method The Penalty Method considers the constraints of Eq.(6) by putting constraint g(θ) into a penalty term, followed by solving the following unconstrained problem in an iterative manner,
  max θ∈Θ f(θ) + 1− α α min{g(θ), 0}, (8)
  The limit of the above unconstrained problem when α→ 0 then leads to the solution of the original constrained problem. As an approximation, WSR chooses a fixed weight α, and uses the gradient of ∇θf + 1−αα ∇θg instead of ∇θf + 1−α α ∇θ min{g(θ), 0}, thus the final solution will intensely rely on the selection of α.
  E IMPLEMENTATION DETAILS
  Calculation of DW We use deterministic part of policies in the calculation of DW , i.e., we remove the Gaussian noise on the action space in PPO and use DW (a1, a2) = |a1 − a2|.
  Network Structure We use MLP with 2 hidden layers as our actor models in PPO. The first hidden layer is fixed to have 32 units. We choose to use 10, 64 and 256 hidden units for the three tasks respectively in all of the main experiments, after taking the success rate, performance and computation expense (i.e. the preference to use less unit when the other two factors are similar) into consideration.
  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 HalfCheetah-v3.
  Hardware and Training Time We experiment on a server with 8 TITAN X GPUs and 32 Intel(R) E5-2640 CPUs. Experiments take 0.5 (the maze environment with 0.1M interactions) to 10 hours (for the locomotion tasks) to run in generating each policy. As our diversity-seeking method based on a sequential learning framework, new policies must be trained after previous policies are already generated.
sections.heading: F ABLATION STUDY
sections.text: Novel Policy Generation without Performance Decay Multi-objective formulation of novel policy generation 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 no more trade-off between novelty and final reward as the only objective is 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.
  The proper magnitude of the novelty threshold leads to more exploration among a population of policies, thus the performance of latterly found policies may be better than or at 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. 4 shows experimental results on adjusting the thresholds, which supports our intuition.
  G VISUALIZE DIVERSITY
  G.1 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 to 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 5) learns to jump further and avoids falling down rather instead of just jumping and falling down (Figure 6). In the Walker2d environment, the color of purple indicates the left leg is visible. It can be seen that the IPD policies (Figure 7) learn to use both left and right legs in walking, while the PPO policies usually learn jumping. (Figure 8). In HalfCheetah, the IPD policies (Figure 9) perform much better than the PPO policies (Figure 10). The IPD policies leran to run with head-downward (Figure 9 line 1), head-upward (Figure 9 line 3), and forward (Figure 9 line 5) while the PPO policies are always head-downward.
  In Hopper and HalfCheetah, IPD is able to improve the primal task performance by avoiding always getting trapped in some certain sub-optimal behaviors.