Title: LYAPUNOV-BASED SAFE POLICY OPTIMIZATION

Abstract: In many reinforcement learning applications, it is crucial that the agent interacts with the environment only through safe policies, i.e., policies that do not take the agent to certain undesirable situations. These problems are often formulated as a constrained Markov decision process (CMDP) in which the agent's goal is to optimize its main objective while not violating a number of safety constraints. In this paper, we propose safe policy optimization algorithms that are based on the Lyapunov approach to CMDPs, an approach that has well-established theoretical guarantees in control engineering. We first show how to generate a set of state-dependent Lyapunov constraints from the original CMDP safety constraints. We then propose safe policy gradient (PG) algorithms that train a neural network policy using deep deterministic policy gradient (DDPG) or proximal policy optimization (PPO), while guaranteeing near-constraint satisfaction at every policy update by projecting either the policy parameter or the action onto the set of feasible solutions induced by the linearized Lyapunov constraints. Unlike the existing (safe) constrained policy gradient algorithms, ours are more data efficient as they are able to utilize both on-policy and off-policy data. Furthermore, the action-projection version of our algorithms often leads to less conservative policy updates and allows for natural integration into an end-to-end PG training pipeline. We evaluate our algorithms and compare them with constrained policy optimization (CPO) and the Lagrangian method on several high-dimensional continuous state and action simulated robot locomotion tasks, in which the agent must satisfy certain safety constraints while minimizing its expected cumulative cost.

1. INTRODUCTION:

In many real-world reinforcement learning (RL) problems, the agent must satisfy a number of constraints while minimizing its expected cumulative cost. In particular, these constraints might be related to safety, i.e., the policy learned by the agent should not take it to certain undesirable parts of the state and/or action space. In some problems, it is not only important that the policy learned by the agent (that will be deployed) be safe (Amodei et al., 2016) , but also crucial that all the policies generated during training (with which the agent interacts with the environment to collect samples) be safe (Achiam et al., 2017) . For example, a robot should always avoid taking actions that irrevocably harm its hardware. We often formulate the agent's interaction with the environment in constrained sequential decision-making problems as a constrained Markov decision process (CMDP). CMDPs are extensions of MDPs in which, in addition to the original cost function, there exists a constraint cost function, whose expected cumulative value should remain bounded. The additional constraint cost function gives more flexibility to CMDPs in modeling problems with trajectorybased constraints compared to approaches that artificially re-cast the cost of MDPs to enforce the constraints (Regan & Boutilier, 2009) . Under the CMDP framework, we consider a policy to be safe if it satisfies the (expected) cumulative cost constraints.

A common approach to solve CMDPs is to use the Lagrangian method (Altman, 1998; Geibel & Wysotzki, 2005) that augments the original objective function with a penalty on constraint violation and computes the saddle-point of the constrained policy optimization via primal-dual method (Chow et al., 2017) . Although safety is ensured when the policy converges asymptotically, a major drawback of this approach is that it makes no guarantee with regards to the safety of the policies generated during training. To address this issue (safety during training), heuristic algorithms for policy search with safety constraints have been proposed (e.g., Uchibe & Doya 2007) . While some of them work reasonably well in practice, none is theoretically grounded to generate constraint-satisfying policies. Achiam et al. (2017) recently proposed the constrained policy optimization (CPO) method that extends the trust-region policy optimization (TRPO) algorithm (Schulman et al., 2015a) to handle CMDP constraints. Although there is no theoretical guarantee that the policies generated by CPO are all safe, the empirical results reported in the paper are promising in terms scalability, performance, and constraint satisfaction, both during training and after convergence. Moreover, CPO is based on a principled approach to generate constraint-satisfying policies, and not just on heuristics. However, the CPO methodology is closely connected to TRPO. While adopting this methodology to PPO for constrained optimization is straight-forward (this is exactly how we derive our SPPO algorithm in this paper), it is not clear how it can be combined with algorithms that do not belong to the family of proximal PG algorithms (PG algorithms that are regularized with relative entropy), such as DDPG.

Another recent approach to solve CMDPs, while remaining safe during training, is by Chow et al. (2018) . This work is based on the notion of Lyapunov function that has a long history in control theory to analyze the stability of dynamical systems (Khalil, 1996; Neely, 2010) . Using Lyapunov functions in RL was first studied by Perkins & Barto (2002) , where they were used to guarantee closed-loop stability of an agent. In a recent work, Berkenkamp et al. (2017) used Lyapunov functions to guarantee that a model-based RL agent can be brought back to a "region of attraction" during exploration. Using the theoretical underpinnings of the Lyapunov approach, Chow et al. (2018) proposed two dynamic programming (DP) algorithms to solve a CMDP and provided theoretical analyses for the feasibility and performance of the resulted policies. The proposed algorithms correspond to the two celebrated DP algorithms: policy and value iteration. They then extended their algorithms to learning (the scenario in which the MDP model is unknown) and proposed RL algorithms that correspond to approximate policy and value iteration. However, since their algorithms are all value-function-based, applying them to continuous action problems is not straightforward.

In this paper, we extend the Lyapunov-based approach to solving CMDPs of Chow et al. (2018) to continuous action problems that play an important role in control and robotics. Our contributions can be summarized as follows: 1) We formulate the problem of safe RL as a CMDP and propose a Lyapunov-function-based policy optimization framework that can handle continuous action CMDPs.

2) By leveraging the theoretical underpinnings of the Lyapunov-based approach to CMDPs in Chow et al. (2018) , we present two classes of safe policy optimization algorithms that can work with any standard policy gradient algorithm such as deep deterministic policy gradient (DDPG) (Lillicrap et al., 2015) and proximal policy optimization (PPO) (Schulman et al., 2017) . The first class of our algorithms is based on constrained optimization w.r.t. policy parameter (similar to what is done in constrained policy optimization (CPO)). The second class hinges on the concept of a safety layer introduced by Dalal et al. (2018) and transforms the constrained policy optimization problem into an unconstrained one, by integrating the Lyapunov constraints into the policy network via safety-layer augmentation. 3) We evaluate our algorithms and compare them to two baselines, CPO (Achiam et al., 2017) and the Lagrangian method, on several robot locomotion tasks, in which the agent must satisfy certain safety constraints while minimizing its expected cumulative cost. Our results show that our algorithms outperform the baselines in terms of balancing the performance and constraint satisfaction at every policy update.

2. PRELIMINARIES:

We consider the RL problem in which the agent's interaction with the environment is modeled as a Markov decision process (MDP). A MDP is a tuple (X , A, γ, c, P, x 0 ), where X is the state space; A is the action space; γ ∈ [0, 1) is the discounting factor; c(x, a) ∈ [0, C max ] is the immediate cost function (negative reward); P (•|x, a) is the transition probability distribution; and x 0 ∈ X is the initial state. Our results easily generalize to random initial states and random costs, but for simplicity we will focus on the case of deterministic initial state and immediate cost. In a more general setting where cumulative constraints are taken into account, we define a constrained Markov decision process (CMDP), which extends the MDP model by introducing additional costs and associated constraints. A CMDP is defined by (X , A, γ, c, d, P, x 0 , d 0 ), where the components X , A, γ, c, P, x 0 are the same as in the unconstrained MDP; d(x) ∈ [0, D max ] is the immediate constraint cost; and d 0 ∈ R ≥0 is an upper-bound on the expected cumulative (through time) constraint cost. To formalize the optimization problem associated with CMDPs, let ∆ be the set of Markov stationary policies, i.e., ∆(x) = π(•|x) : X → R ≥0s : a π(a|x) = 1 for any state x ∈ X . For notational convenience, at each state x ∈ X , we define the generic Bellman operator w.r.t. policy π ∈ ∆ and generic cost function

h as T π,h [V ](x) = a π(a|x) h(x, a)+γ x ∈X P (x |x, a)V (x ) .

Given a policy π ∈ ∆ and an initial state x 0 , the expected cumulative cost is defined as C π (x 0 ) := E ∞ t=0 γ t c(x t , a t ) | x 0 , π , and the safety constraint is defined as

D π (x 0 ) ≤ d 0 , where D π (x 0 ) := E ∞ t=0 γ t d(x t ) | x 0 , π is the safety constraint function (expected cumulative constraint cost).

The goal in CMDPs is to solve the constrained optimization problem

π * ∈ min π∈∆ C π (x 0 ) : D π (x 0 ) ≤ d 0 .

(1)

Using the discounting property of a CMDP, Theorem 3.1 in Altman (1999) shows that if the feasibility set is non-empty, then there exists an optimal policy in the class of stationary Markovian policies ∆. To motivate the CMDP formulation, we refer the reader to Chow et al. (2018) , which presents two real-world examples in modeling safety using (i) the reachability constraint, and (ii) the constraint that limits the agent's visits to undesirable states.

3. A LYAPUNOV APPROACH FOR SOLVING CMDPS:

In this section, we revisit the Lyapunov approach to solving CMDPs proposed by Chow et al. (2018) and report the mathematical results that are important in developing our safe policy optimization algorithms. To start, without loss of generality, we assume that we have access to a baseline feasible policy of Equation 1, π B ; i.e. π B satisfies D π B (x 0 ) ≤ d 0 . We define a set of Lyapunov functions w.r.t. initial state x 0 ∈ X and constraint threshold d 0 as 

L π B (x 0 , d 0 ) = {L : X → R ≥0 : T π B ,d [L](x) ≤ L(x), ∀x ∈ X ; L(x 0 ) ≤ d 0 },

(x) = π(•|x) ∈ ∆ : T π,d [L](x) ≤ L(x)

the set of L-induced Markov stationary policies. Since T π,d is a contraction mapping (Bertsekas, 2005) , any L-induced policy π has the property

D π (x) = lim k→∞ T k π,d [L](x) ≤ L(x), ∀x ∈ X .

Together with the property that L(x 0 ) ≤ d 0 , they imply that any L-induced policy is a feasible policy of Equation 1. However, in general, the set F L (x) does not necessarily contain an optimal policy of Equation 1, and thus it is necessary to design a Lyapunov function (w.r.t. a baseline policy π B ) that provides this guarantee. In other words, the main goal is to construct a Lyapunov function

L ∈ L π B (x 0 , d 0 ) such that L(x) ≥ T π * ,d [L](x), L(x 0 ) ≤ d 0 .

(2) Chow et al. (2018) show in their Theorem 1 that 1) without loss of optimality, the Lyapunov function can be expressed as

L (x) := E ∞ t=0 γ t (d(x t ) + (x t )) | π B , x

, where (x) ≥ 0 is some auxiliary constraint cost uniformly upper-bounded by * (x) := 2D max D T V (π * ||π B )(x)/(1 -γ), and 2) if the baseline policy π B satisfies the condition

max x∈X * (x) ≤ D max • min{(1 -γ)(d 0 -D π B (x 0 ))/D max , D max -(1 -γ)D/D max + (1 -γ)D}, where D = max x∈X max π D π (x)

is the maximum constraint cost, then the Lyapunov function candidate L * also satisfies the properties of Equation 2, and thus, its induced feasible policy set F L * contains an optimal policy. Furthermore, suppose that the distance between the baseline and optimal policies can be estimated effectively. Using the set of L * -induced feasible policies and noting that the safe Bellman operator T [V ](x) = min π∈F L * (x) T π,c [V ](x) is monotonic and contractive, one can show that T [V ](x) = V (x), ∀x ∈ X has a unique fixed point V * , such that V * (x 0 ) is a solution of Equation 1, and an optimal policy can be constructed via greedification, i.e., π * (•|x) ∈ arg min π∈F L * (x) T π,c [V * ](x). This shows that under the above assumption, Equation 1 can be solved using standard dynamic programming (DP) algorithms. While this result connects CMDP with Bellman's principle of optimality, verifying whether π B satisfies this assumption is challenging when a good estimate of D T V (π * ||π B ) is not available. To address this issue, Chow et al. (2018) propose to approximate * with an auxiliary constraint cost , which is the largest auxiliary cost satisfying the Lyapunov condition L (x) ≥ T π B ,d [L ](x), ∀x ∈ X and the safety condition L (x 0 ) ≤ d 0 . The intuition here is that the larger , the larger the set of policies F L . Thus, by choosing the largest such auxiliary cost, we hope to have a better chance of including the optimal policy π * in the set of feasible policies. Specifically, is computed by solving the following linear programming (LP) problem:

EQUATION

where 1(x 0 ) represents a one-hot vector in which the non-zero element is located at x = x 0 . When π B is a feasible policy, this problem has a non-empty solution. Furthermore, according to the derivations in Chow et al. (2018) , the maximizer of Equation 3 is an indicator function of the form

(x) = (d 0 -D π B (x 0 )) • 1{x = x}/E[ ∞ t=0 γ t 1{x t = x} | x 0 , π B ] ≥ 0, where x ∈ arg min x∈X E ∞ t=0 γ t 1{x t = x} | x 0 , π B .

They also show that by further restricting (x) to be a constant function, the maximizer is given by (x) = (1-γ)•(d 0 -D π B (x 0 )), ∀x ∈ X . Using the construction of the Lyapunov function L , Chow et al. (2018) propose the safe policy iteration (SPI) algorithm (see Algorithm 1 in Appendix A) in which the Lyapunov function is updated via bootstrapping, i.e., at each iteration L is recomputed using Equation 3 w.r.t. the current baseline policy. This algorithm has the following properties: 1) Consistent Feasibility, i.e., if the current policy π k is feasible, then π k+1 is also feasible; 2) Monotonic Policy Improvement, i.e., C π k+1 (x) ≤ C π k (x) for any x ∈ X ; and 3) Asymptotic Convergence. Despite all these nice properties, SPI is still a valuefunction-based algorithm, and thus it is not straightforward to use it in continuous action problems. The main reason is that the greedification step becomes an optimization problem over the continuous set of actions that is not necessarily easy to solve. In Section 4, we show how we use SPI and its nice properties to develop safe policy optimization algorithms that can handle continuous action problems. Our algorithms can be thought as combinations of DDPG or PPO (or any other on-policy or off-policy policy optimization algorithm) with a SPI-inspired critic that evaluates the policy and computes its corresponding Lyapunov function. The computed Lyapunov function is then used to guarantee safe policy update, i.e., the new policy is selected from a restricted set of safe policies defined by the Lyapunov function of the current policy.

4. SAFE POLICY GRADIENT ALGORITHMS WITH LYAPUNOV FUNCTIONS:

Policy gradient (PG) algorithms optimize a policy end-to-end by computing sample estimates of the gradient of the cumulative cost induced by the policy and then updating the policy in the gradient direction. In general, stochastic policies that give a probability distribution over actions are parameterized by a κ-dimensional vector θ, so the space of policies can be written as

π θ (•|x), x ∈ X , θ ∈ R κ .

Since in this setting a policy π is uniquely defined by its parameter vector θ, policy-dependent functions can be written as a function of θ or π, and they are used interchangeably in this paper.

Recently there are two PG algorithms which have emerged as generally well-performing, namely DDPG and PPO. These algorithms are widely used in many continuous control tasks. DDPG (Lillicrap et al., 2015) is an off-policy Q-learning style algorithm. A deterministic policy π θ (x) and a Q-value approximator Q(x, a; φ) are trained jointly. The Q-value approximator is trained to minimize Bellman errors with respect to π; i.e., it is trained to fit the true Q-value function satisfying

Q(x, a) = c(x, a) + γ x ∈X P (x |x, a)Q(x , π θ (x ))

. The policy π is then trained to optimize Q(x, π θ (x); φ) via chain-rule. The PPO algorithm we use is a penalty form of TRPO (Schulman et al., 2017) with an adaptive rule to tune the D KL penalty weight β k . Specifically, PPO trains a Gaussian policy π θ (x) according to the standard policy gradient objective augmented with a penalty on KL-divergence from a previous version of the policy; i.e., the penalty is of the form,

D KL (θ, θ ) = E[D KL (π θ (•|x t )||π θ (•|x t ))|x 0 , θ ],

where θ is a previous version of the policy.

In CMDPs, the presence of a constraint D π θ (x 0 ) ≤ d 0 may be naively incorporated into the standard forms of DDPG and PPO via the Lagrangian method. That is, one may transform the constrained optimization problem to a penalty form, in which the constraint costs d(x) are added to the task costs c(x, a). The resulting penalized form of the objective is min θ max λ≥0 E ∞ t=0 c(x t , a t ) + λd(x t )|x 0 , θ -λd 0 . In this form, both θ and λ must be optimized jointly to find a saddle-point of the objective. The optimization of θ may be performed by either DDPG or PPO on the augmented cost c(x, a) + λd(x). The optimization of λ may be performed by stochastic gradient descent on x t taken from trajectories sampled according to θ.

Although the Lagrangian approach is easy to implement (see Appendix B for details), in practice it does not lead to safety in training. While the objective encourages finding a solution which is safe, any intermediate step in the optimization may lead to an unsafe policy. In contrast, the Lyapunov approaches we propose are guaranteed to return a safe policy, not only at convergence, but also during training. In the subsections below, we elaborate how to transform DDPG and PPO to their Lyapunov safe counterparts below:

θ * = arg min θ C π θ (x 0 ) subject to a∈A (π θ (a|x) -π B (a|x))Q L (x, a)da ≤ (x), ∀x ∈ X . (4) where Q L (x, a) = d(x) + (x) + γ x P (x |x, a)L (x )

is the state-action Lyapunov function.

We will describe two approaches to incorporating Lyapunov constraints in PG: θ-projection and a-projection. In Section 4.1, we formulate the Lyapunov-based PG using constrained policy optimization (which we call θ-projection), and in Section 4.2 we show how the Lyapunov constraints can be embedded into the policy network via a safety layer (which we call a-projection). In Section A.1, we also discuss two practical techniques to further enforce safety during policy training.

4.1. CONSTRAINED OPTIMIZATION APPROACH TO LYAPUNOV-BASED PG:

For demonstration purposes, we hereby show how one can perform constrained policy optimization with PPO and Lyapunov constraints. With almost identical machinery, this procedure can also be applied to DDPG. Consider the following constrained optimization at iteration k with semi-infinite dimensional Lyapunov constraints for policy update:

θ ∈ arg min θ∈Θ (θ -θ k ), ∇ θ Ex∼µ θ k ,a∼π θ Q θ k (x, a) + β k (θ -θ k ), ∇ 2 θ DKL(θ||θ k ) | θ=θ k •(θ -θ k ) | θ=θ k s.t. (θ -θ k ), ∇ θ Ea∼π θ QL θ k (x, a) | θ=θ k ≤ (x), ∀x ∈ X ,

where µ θ k is the γ-visiting distribution w.r.t. π θ k , and β k is the adaptive penalty weight of the D KL (θ||θ k ) regularizer. Clearly if one updates the policy parameter by solving the above optimization, and if the approximation errors from neural network parameterizations of Q θ k and Q L θ k and first-order Taylor series expansion are small, then safety may ensure safety during training. However, the presence of infinite-dimensional Lyapunov constraints makes solving the above optimization (in real-time) numerically intractable. To tackle the issue of infinite dimensionality, (without loss of optimality) we re-write the Lyapunov constraint in the following form:

max x∈X (θ -θ k ), ∇ θ E a∼π θ Q L θ k (x, a) | θ=θ k -(x) ≤ 0.

This might still lead to numerical instability in gradient descent algorithms, because the max-operator in the constraint is nondifferentiable. Similar to the surrogate constraint used in TRPO (to transform the max D KL constraint into an average D KL constraint), a more numerically stable way is to approximate the Lyapunov constraint using the following average constraint surrogate:

EQUATION

)

where N is the number of on-policy trajectories of π θ k . In practice, if one adopts

= (1 -γ)(d 0 -D π θ k (x 0 )) from Section 4.1, then the linear term in Equation 5 can be sim- plified as ∇ θ E a∼π θ Q L θ k (x i , a) = ∇ θ a∈A π θ (a|x)∇ θ log π θ (a|x)Q D,θ k (x i , a)da. On the other hand, by setting M = O(1/(1 -γ)), the constraint threshold becomes 1 M M i=1 (x i ) ≈ d 0 -D π θ k (x 0 ).

Collectively, the average constraint surrogate in Equation 5 becomes (θ -

θ k ), 1 M M i=1 ∇ θ E a∼π θ Q D,θ k (x i , a) | θ=θ k ≤ d 0 -D π θ k (x 0 )

, which is equivalent to the constraint used in the CPO algorithm (see Section 6.1 in Achiam et al. (2017) ). This draws the connection between CPO and Lyapunov-based PG with θ-projection.

The Lyapunov-based algorithms with θ-projection in constrained policy update is summarized by Algorithm 4 in Appendix A. In the experiment section, we denote the DDPG version and the PPO version of this algorithm by SDDPG and SPPO respectively.

4.2. EMBEDDING LYAPUNOV CONSTRAINTS INTO A SAFETY LAYER:

Notice that the main contribution of the Lyapunov approach is to break down a trajectory-based constraint into a sequence of single-step, state dependent constraints. When the state space is infinite/continuous, it is counter-intuitive to directly enforce these Lyapunov constraints (instead of the original trajectory-based constraint) in the optimization w.r.t. policy parameter θ, because the feasibility set is characterized by infinite dimensional constraints. Rather, leveraging the ideas of a safety layer from Dalal et al. (2018) that was applied to single-step constraints, we propose a novel approach to embed the set of Lyapunov constraints into the policy network. In this way, one reformulates the CMDP problem into an unconstrained one, whose policy parameter θ (of the augmented network) can then be optimized by any standard unconstrained PG algorithms. At every given state, the unconstrained action is first computed and is then passed through the safety layer, where a feasible action mapping is constructed by projecting the unconstrained actions onto the feasibility set w.r.t. the corresponding Lyapunov constraint. Therefore, safety during training w.r.t. the original CMDP problem is guaranteed by the Lyapunov theorem.

We hereby demonstrate how one can find a feasible action mapping using the safety layer with DDPG, whose role is to solve the following projection problem at given state x ∈ X :

a * (x) ∈ arg min a 1 2 a -π θ,unc (x) 2 : (a -π B (x)) ∇ a Q L (x, a) | a=π B (x) ≤ (x) . (6)

In the above optimization problem, π θ,unc is the unconstrained policy whose policy parameter is updated by standard DDPG, π B is the current data-generation policy that is safe, and the left side of the constraint is the first-order Taylor series approximation of a∈A Q L (x, π θ (x)) -Q L (x, π B (x))da over actions, w.r.t. the action π B (x) induced by the baseline policy. As in Section 4.1, since the auxiliary cost is state-dependent, one can readily find ∇ a Q L (x, a) | a=π B (x) by computing the gradient of the constraint action value function ∇ a Q D (x, a) | a=π B (x) . Generally, the safety layer perturbs the unconstrained action as little as possible in the Euclidean norm in order to satisfy the Lyapunov constraints. Notice that the objective function is positive-definite and quadratic and the constraint approximation is linear. Therefore, we can find the global solution to this convex problem effectively via an in-graph iterative QP-solver, such as the one from Amos & Kolter (2017) . Furthermore, since the optimization in Equation 6only has a single Lyapunov constraint, one can express a * (x) using the following analytical solution.

Proposition 1. At any given state x ∈ X , the solution to the optimization problem in Equation 6has the following form:

a * (x) = π θ,unc (x) + λ * (x)∇ a Q L (x, a) | a=π B (x)

, where

λ * (x) = ∇aQ L (x, a) | a=π B (x) (π θ,unc (x) -π B (x)) -(x) / ∇aQ L (x, a) | a=π B (x) ∇aQ L (x, a) | a=π B (x) + .

The closed-form solution is essentially a linear projection of the unconstrained action π θ,unc (x) to the safe hyperplane characterized with slope

∇ a Q L (x, a) | a=π B (x) and intercept (x) = (1 -γ)(d 0 - D π B (x 0 )

). Implementing a * (x) is very simple; it only consists of several arithmetic operations such as matrix products and ReLU. Extending this closed-form solution to handle multiple constraints is possible, under the assumption of having at most one constraint active at a time.

In general, the safety layer approach can also be applied to policy gradient algorithms, such as PPO, that learn a non-deterministic policy. For example in the PPO case when the policy is parameterized with a Gaussian distribution, then one simply need to project both the mean and the standarddeviation vector, in order to obtain a feasible action probability. The Lyapunov-based algorithms with a-projection in safety layer is summarized by Algorithm 5 in Appendix A. In the experiment section, we denote the DDPG version and the PPO version of this algorithm by SDDPG-modular and SPPO-modular respectively.

5. EXPERIMENTS:

We empirically validate the Lyapunov-based PG algorithms on several robot locomotion continuous control tasks. In these experiments we aim to address the following questions about our proposed algorithm: (i) How is the performance (in terms of cost and safety during training) of Lyapunovbased PG compared to other baseline methods such as CPO and the naive Lagrangian approach? (ii)

In the presence of approximation errors in value functions and policies, how robust is Lyapunovbased PG algorithm with respect to constraint violations?

To understand the performance of these algorithms in terms of both cost and safety guarantees, we designed several interpretable experiments in simulated robot locomotion continuous control tasks, whose notions of safety are motivated by physical constraints. We consider three domains using the MuJoCo simulator (Todorov et al., 2012) with a variety of different agents: (i)HalfCheetah-Safe:

The HalfCheetah agent is rewarded for running, but its speed is limited for stability and safety; (ii) Point-Circle: The Point agent is rewarded for running in a wide circle, but is constrained to stay within a safe region defined by |x| ≤ x lim (Achiam et al., 2017) ; (iii) Point-Gather & Ant-Gather:

The agent, which is either a Point or an Ant, is rewarded for collecting target objects in a terrain map, while being constrained to avoid bombs (Achiam et al., 2017) .

Visualizations of these tasks as well as more detailed descriptions (immediate cost and constraint cost functions, constraint thresholds) are given in Appendix C. In these experiments there are three different agents: (1) a point-mass (X ⊆ R 9 , A ⊆ R 2 ); an ant quadruped robot (X ⊆ R 32 , A ⊆ R 8 );

(3) a half-cheetah (X ⊆ R 18 , A ⊆ R 6 ). For all experiments, we use two neural networks with two hidden layers of size (100, 50) and ReLU activations to model the mean and log-variance of the Gaussian actor policy, and two neural networks with two hidden layers of size (200, 50) and tanh activations to model the critic and constraint critic. To build a low variance sample gradient estimate, we use GAE-λ (Schulman et al., 2015b) to estimate the advantage and constraint advantage functions, with a hyper-parameter λ ∈ (0, 1) optimized by grid-search.

5.1. COMPARISON WITH UNCONSTRAINED PG, LAGRANGIAN APPROACH, AND CPO:

For comparison purposes, we implement the naive Lagrangian approach. Details of this algorithm are available in Appendix B. For fair comparisons, we also optimize the Lagrangian using a natural policy gradient when needed. To understand the optimal unconstrained performance on these environments, we also include the learning performance of two state-of-the-art unconstrained reinforcement learning algorithms, namely DDPG (Lillicrap et al., 2015) and PPO (Schulman et al., 2017) . In the PPO case, we aim to compare the performance of CPO (which is equivalent to Lyapunov-based PG with θ-projection) with Lyapunov-based PG (with a-projection) . Notice that the original implementation of CPO in Achiam et al. ( 2017) is based on TRPO (Schulman et al., 2015a) . Instead of the original CPO algorithm, we use its PPO alternative (which coincides with the SPPO algorithm derived in Section 4.1) as the safe RL baseline for comparison. SPPO preserves the essence of CPO by adding a 1st order constraint to the proximal policy optimization. The main difference between CPO and SPPO is that the latter does not perform backtracking line-search. The decision to compare with SPPO instead of CPO is 1) to avoid the additional computational complexity of line-search in TRPO, while maintaining the performance of PG using the popular PPO algorithm, 2) to have a back-propagatable version of CPO, and 3) to have a fair comparison with other back-propagatable safe RL algorithms, such as the DDPG and safety layer counterparts. Figure 2 : Results of various PPO algorithms on safe robot locomotion tasks, with x-axis in thousands of episodes. We include runs from PPO (red), PPO-Lagrangian (magenta), SPPO (blue), SPPO-modular (green) on HalfCheetah-Safe and Point-Gather. Similar to Figure 1 , the Lyapunovbased approaches can perform safe learning in the control tasks when function approximations on policies and value functions are necessary.

Learning curves for unconstrained DDPG, Lagrangian DDPG, SDDPG and SDDPG-modular are shown in Figure 1 , and the learning curves for unconstrained PPO, Lagrangian PPO, SPPO and SPPO-modular are shown in Figure 6 . Due to space restrictions, more results are included in Appendix C. From the comparison plots, one can clearly see that the unconstrained DDPG and PPO agents are constraint-violating in these environments. Although the Lagrangian approaches in DDPG and PPO converge to feasible policies with reasonably good performance, in accord with our earlier claims these algorithms cannot guarantee constraint satisfaction during training. Furthermore it is worth-noting that the Lagrangian approach can be sensitive to the initialization of the Lagrange multiplier λ 0 . If λ 0 is too large, it would make policy updates overly conservative, while if λ 0 is too small then constraint violation will be more pronounced. By default, we initialize λ 0 = 10, which assumes no knowledge about the environment.

Generally in both DDPG and PPO experiments, the Lyapunov-based PG algorithms lead to more stable learning and constraint satisfaction than the Lagrangian approach. The Lyapunov approaches quickly stabilize the constraint cost to be below the threshold, while the constraint costs from the Lagrangian approach tend to jiggle around the threshold. In many cases the a-projection Lyapunovbased PG (SDDPG-modular, SPPO-modular) converges faster than the θ-projection counterpart (SDDPG, SPPO). This corroborates with the hypothesis that the a-projection approach is less conservative during policy updates than the θ-projection approach (which is what CPO is based on).

Finally, in most experiments (HalfCheetah, PointGather, and AntGather) the DDPG class of algorithms tends to have faster learning than the PPO counterpart. This is potentially due to the improved data-efficiency when using off-policy samples in PG updates. Although this benefit is not directly related to the addition of Lyapunov constraints, this also supports our claim that some Lyapunovbased safe PG algorithms (SDDPG, SDDPG-modular) can learn more effectively than CPO (which is analogous to SPPO).

5.2. CONSTRAINT VIOLATION DURING TRAINING:

Due to function approximation errors in policies and value functions, in practice most safe learning algorithms including the Lyapunov-based PG methods may still take a bad step and lead to constraint violation. While methods like safeguard policy update and constraint tightening from Section A.1 might help to remedy this issue, it is still unclear how robust each algorithm is regarding constraint satisfaction during training. To study the degree of constraint violation in different PG algorithms, we show their constraint violation plots in Figure 3 for DDPG-based and PPO-based algorithms. To make the comparison fair, we apply both safeguard policy update and the constraint tightening to all safe PG algorithms. From the constraint violation plots, it is clear that the Lagrangian methods (both DDPG and PPO) violate safety constraints more often than the Lyapunov-based counterparts. In many cases the Lyapunov-based PG algorithms with a-projection have lower constraint violation than its θ-projection counterparts. We speculate this is due to the fact that the safety layer generates smoother gradient updates during end-to-end training. , where ccv represents the area under constraint learning curve that is above the constraint threshold) of various PG algorithms on safe robot locomotion tasks, with x-axis in thousands of episodes. We include runs from DDPG (red), DDPG-Lagrangian (magenta), SDDPG (blue), SDDPG-modular (green), PPO (red), PPO-Lagrangian (magenta), SPPO (blue), SPPO-modular (green) on HalfCheetah-Safe and Point-Gather.

Compared with Lagrangian approach, we discover that the Lyapunov-based approaches generally have more stable and safe learning, which lead to lower constraint violations.

6. CONCLUSIONS:

In this paper, we formulated the problem of safe RL as a CMDP and used the notion of Lyapunov function to develop policy optimization algorithms that learn policies that are both safe and have low expected cumulative cost. Our algorithms extend the Lyapunov-based approach to solving CMDPs of Chow et al. (2018) to continuous action problems. Our algorithms combine DDPG or PPO (or any other on-policy or off-policy policy optimization algorithm) with a critic that is inspired by the safe policy iteration (SPI) algorithm of Chow et al. (2018) and both evaluates the policy and computes its corresponding Lyapunov function. The computed Lyapunov function is then used to guarantee safe policy update. We can categorize our algorithms into two classes in terms of the way they perform safe policy update. The first class is based on constrained optimization w.r.t. policy parameter, similar to what is done in CPO. The second class relies on the safety layer concept (Dalal et al., 2018) that integrates the Lyapunov constraints into the policy network by adding an action projection layer to it. We evaluated our algorithms on four high-dimensional simulated robot locomotion tasks and compared them with CPO (Achiam et al., 2017) and the Lagrangian method in terms of minimizing the expected cumulative return and constraint violation during training. Our results indicate that our Lyapunov-based algorithms 1) achieve safe learning, 2) have better data-efficiency, and 3) can be more naturally integrated within the standard end-to-end differentiable policy gradient training pipeline. In general, our work is a step forward in deploying RL to real-world problems in which safety guarantees are of paramount importance.

Future work includes 1) developing more stable and safe learning algorithms by further exploiting the properties of Lyapunov functions, 2) exploring more efficient ways to include Lyapunov constraints in constrained policy optimization, and 3) applying the Lyapunov-based PG algorithms to real-world continuous control problems, particularly in robotics.

Algorithm 4 Lyapunov-based Policy Gradient with θ-projection (SDDPG and SPPO)

Input: Initial feasible policy π0; for k = 0, 1, 2, . . . do

Step 0: With π b = π θ k , generate N trajectories {ξ j,k } N j=1 of T steps by starting at x0 and following the policy θ k

Step 1: Using the trajectories {ξ j,k } N j=1 , estimate the critic Q θ (x, a) and the constraint critic Q D,θ (x, a); • For DDPG, these functions are trained by minimizing the MSE of Bellman residual, and one can also use off-policy samples from replay buffer (Schaul et al., 2015) ; • For PPO these functions can be estimated by the generalized advantage function technique from Schulman et al. (2015b) Step 2: Based on the closed form solution of a QP problem with an LP constraint in Section 10.2 of Achiam et al. (2017) , calculate λ * k with the following formula:

λ * k =   -β k -∇ θ Q θ (x, ā) | θ=θ k H(θ k ) -1 ∇ θ Q D,θ (x, ā) | θ=θ k ∇ θ Q D,θ (x, ā) | θ=θ k H(θ k ) -1 ∇ θ Q D,θ (x, ā) | θ=θ k   + ,

where

∇ θ Q θ (x, ā) = 1 N x,a∈ξ j,k ,1≤j≤N T -1 t=0 γ t ∇ θ log π θ (a|x)Q θ (x, a), ∇ θ Q D,θ (x, ā) = 1 N x,a∈ξ j,k ,1≤j≤N T -1 t=0 γ t ∇ θ log π θ (a|x)Q θ (x, a),

β k is the adaptive penalty weight of the DKL(π||π θ k ) regularizer, and

H(θ k ) = ∇ 2 θ DKL(π||π θ ) | θ=θ k

is the Hessian of this term:

Step 3: Update the policy parameter by following the objective gradient;

• For DDPG

θ k+1 ← θ k -α k • 1 N • T x∈ξ j,k ,1≤j≤N ∇ θ π θ (x) | θ=θ k •(∇aQ θ k (x, a)+λ * k ∇aQ D,θ k (x, a)) | a=π θ k (x)

• For PPO,

θ k+1 ← θ k - α k N β k H(θ k ) -1 x j,t ,a j,t ∈ξ j,k ,1≤j≤N T -1 t=0 γ t • ∇ θ log π θ (aj,t|xj,t) | θ=θ k • (Q θ k (xj,t,aj,t) + λ * k Q D,θ k (xj,t,aj,t))

Step 4: At any given state x ∈ X , compute the feasible action probability a * (x) via action projection in the safety layer, that takes inputs ∇aQL(x, a) = ∇aQ D,θ k (x, a) and

(x) = (1 -γ)(d0 - Q D,θ k (x0, π k (x0)))

, for any a ∈ A. end for Return Final policy π θ k * , Algorithm 5 Lyapunov-based Policy Gradient with a-projection (SDDPG-modular and SPPOmodular)

Input: Initial feasible policy π0; for k = 0, 1, 2, . . . do

Step 0: With π b = π θ k , generate N trajectories {ξ j,k } N j=1 of T steps by starting at x0 and following the policy θ k

Step 1: Using the trajectories {ξ j,k } N j=1 , estimate the critic Q θ (x, a) and the constraint critic Q D,θ (x, a); • For DDPG, these functions are trained by minimizing the MSE of Bellman residual, and one can also use off-policy samples from replay buffer (Schaul et al., 2015) ; • For PPO these functions can be estimated by the generalized advantage function technique from Schulman et al. (2015b) Step 2: Update the policy parameter by following the objective gradient;

• For DDPG

θ k+1 ← θ k -α k • 1 N • T x∈ξ j,k ,1≤j≤N ∇ θ π θ (x) | θ=θ k •∇aQ θ k (x, a) | a=π θ k (x) ; • For PPO, θ k+1 ← θ k - α k N β k H(θ k ) -1 x j,t ,a j,t ∈ξ j,k ,1≤j≤N T -1 t=0 γ t •∇ θ log π θ (aj,t|xj,t) | θ=θ k •Q θ k (xj,t,aj,t)

where β k is the adaptive penalty weight of the DKL(π||π θ k ) regularizer, and

H(θ k ) = ∇ 2 θ DKL(π||π θ ) | θ=θ k is

the Hessian of this term:

Step 3: At any given state x ∈ X , compute the feasible action probability a * (x) via action projection in the safety layer, that takes inputs ∇aQL(x, a) = ∇aQ D,θ k (x, a) and

(x) = (1 -γ)(d0 - Q D,θ k (x0, π k (x0))), for any a ∈ A. end for Return Final policy π θ k * ,

we propose the following safeguard policy update rule to purely decrease the constraint cost:

θ k+1 = θ k -α sg,k ∇ θ D π θ (x 0 ) θ=θ k ,

where α sg,k is the learning rate for safeguard update. If α sg,k >> α k (learning rate of PG), then with the safeguard update θ will quickly recover from the bad step but it might be overly conservative. This approach is principled because as soon as π θ k is unsafe/infeasible w.r.t. CMDP, the algorithm uses a limiting search direction. One can directly extend this safeguard update to the multiple-constraint scenario by doing gradient descent over the constraint that has the worst violation. Another remedy to reduce the chance of constraint violation is to do constraint tightening on the constraint cost threshold. Specifically, instead of d 0 , one may pose the constraint based on d 0 • (1 -δ), where δ ∈ (0, 1) is the factor of safety for providing additional buffer to constraint violation. Additional techniques in cost-shaping have been proposed in Achiam et al. (2017) to smooth out the sparse constraint costs. While these techniques can further ensure safety, construction of the cost-shaping term requires knowledge from the environment, which makes the safe PG algorithms more complicated.

B LAGRANGIAN APPROACH TO SAFE RL:

There are a number of mild technical and notational assumptions which we will make throughout this section, so we state them here: Assumption 1 (Differentiability). For any state-action pair (x, a), π θ (a|x) is continuously differentiable in θ and ∇ θ π θ (a|x) is a Lipschitz function in θ for every a ∈ A and x ∈ X . Assumption 2 (Strict Feasibility). There exists a transient policy π θ (•|x) such that D π θ (x 0 ) < d 0 in the constrained problem. Assumption 3 (Step Sizes). The step size schedules {α 3,k }, {α 2,k }, and {α 1,k } satisfy

EQUATION

EQUATION

EQUATION

Assumption 1 imposes smoothness on the optimal policy. Assumption 2 guarantees the existence of a local saddle point in the Lagrangian analysis introduced in the next subsection. Assumption 3 refers to step sizes corresponding to policy updates that will be introduced for the algorithms in this paper, and indicates that the update corresponding to {α 3,k } is on the fastest time-scale, the updates corresponding to {α 2,k } is on the intermediate time-scale, and the update corresponding to {α 1,k } is on the slowest time-scale. As this assumption refer to user-defined parameters, they can always be chosen to be satisfied.

To solve the CMDP, we employ the Lagrangian relaxation procedure (Bertsekas, 1999) to convert it to the following unconstrained problem:

EQUATION

)

where λ is the Lagrange multiplier. Notice that L(θ, λ) is a linear function in λ. Then there exists a local saddle point (θ * , λ * ) for the minimax optimization problem max λ≥0 min θ L(θ, λ), such that for some r > 0, ∀θ ∈ R κ ∩ B θ * (r) and ∀λ ∈ [0, λ max ], we have

EQUATION

where B θ * (r) is a hyper-dimensional ball centered at θ * with radius r > 0.

In the following, we present a policy gradient (PG) algorithm and an actor-critic (AC) algorithm. While the PG algorithm updates its parameters after observing several trajectories, the AC algorithms are incremental and update their parameters at each time-step.

We now present a policy gradient algorithm to solve the optimization problem Equation 16. The idea of the algorithm is to descend in θ and ascend in λ using the gradients of L(θ, λ) w.r.t. θ and λ, i.e.,

EQUATION

)

The unit of observation in this algorithm is a system trajectory generated by following policy π θ k . At each iteration, the algorithm generates N trajectories by following the current policy, uses them to estimate the gradients in Equation 18, and then uses these estimates to update the parameters θ, λ.

Let ξ = {x 0 , a 0 , c 0 , x 1 , a 1 , c 1 , . . . , x T -1 , a T -1 , c T -1 , x T } be a trajectory generated by following the policy θ, where x T = x Tar is the target state of the system and T is the (random) stopping time. The cost, constraint cost, and probability of ξ are defined as

C(ξ) = T -1 k=0 γ k C(x k , a k ), D(ξ) = T -1 k=0 γ k D(x k , a k ), and P θ (ξ) = P 0 (x 0 ) T -1 k=0 π θ (a k |x k )P (x k+1 |x k , a k ), respectively. Based on the definition of P θ (ξ), one obtains ∇ θ log P θ (ξ) = T -1 k=0 ∇ θ log π θ (a k |x k ).

Algorithm 2 contains the pseudo-code of our proposed policy gradient algorithm. What appears inside the parentheses on the right-hand-side of the update equations are the estimates of the gradients of L(θ, λ) w.r.t. θ, λ (estimates of the expressions in 18). Gradient estimates of the Lagrangian function are given by

∇ θ L(θ, λ) = ξ P θ (ξ) • ∇ θ log P θ (ξ) C π θ (ξ) + λD π θ (ξ) , ∇ λ L(θ, λ) = -d 0 + ξ P θ (ξ) • D(ξ),

where the likelihood gradient is

∇ θ log P θ (ξ) =∇ θ    T -1 k=0 log P (x k+1 |x k , a k ) + log π θ (a k |x k ) + log 1{x 0 = x 0 }    = T -1 k=0 ∇ θ log π θ (a k |x k ) = T -1 k=0 1 π θ (a k |x k ) ∇ θ π θ (a k |x k ).

In the algorithm, Γ Λ is a projection operator to [0, λ max ], i.e., Γ Λ (λ) = arg min λ∈[0,λmax] λλ 2 2 , which ensures the convergence of the algorithm. Recall from Assumption 3 that the stepsize schedules satisfy the standard conditions for stochastic approximation algorithms, and ensure that the policy parameter θ update is on the fast time-scale ζ 2,i , and the Lagrange multiplier λ update is on the slow time-scale ζ 1,i . This results in a two time-scale stochastic approximation algorithm, which has shown to converge to a (local) saddle point of the objective function L(θ, λ). This convergence proof makes use of standard in many stochastic approximation theory, because in the limit when the step-size is sufficiently small, analyzing the convergence of PG is equivalent to analyzing the stability of an ordinary differential equation (ODE) w.r.t. its equilibrium point.

In policy gradient, the unit of observation is a system trajectory. This may result in high variance for the gradient estimates, especially when the length of the trajectories is long. To address this issue, we propose two actor-critic algorithms that use value function approximation in the gradient estimates and update the parameters incrementally (after each state-action transition). We present two actor-critic algorithms for optimizing Equation 16. These algorithms are still based on the above gradient estimates. Algorithm 3 contains the pseudo-code of these algorithms. The projection operator Γ Λ is necessary to ensure the convergence of the algorithms. Recall from Assumption 3 that the step-size schedules satisfy the standard conditions for stochastic approximation algorithms, and ensure that the critic update is on the fastest time-scale α 3,k , the policy and θ-update α 2,k is on the intermediate timescale, and finally the Lagrange multiplier update is on the slowest time-scale α 1,k . This results in three time-scale stochastic approximation algorithms.

Using the policy gradient theorem from Sutton et al. (2000) , one can show that

EQUATION

where µ θ is the discounted visiting distribution and Q θ is the action-value function of policy θ. We can show that 1

1-γ ∇ log π θ (a k |x k ) • δ k is an unbiased estimate of ∇ θ L(θ, λ), where δ k = Cλ (x k , a k ) + γ V (x k+1 ) -V (x k )

is the temporal-difference (TD) error, and V is the value estimator of V θ .

Traditionally, for convergence guarantees in actor-critic algorithms, the critic uses linear approximation for the value function V θ (x) ≈ φ ψ(x) = V θ,φ (x), where the feature vector ψ(•) belongs to a low-dimensional space R κ2 . The linear approximation V θ,φ belongs to a low-dimensional subspace S V = Ψφ|φ ∈ R κ2 , where Φ is a short-hand notation for the set of features, i.e., Ψ(x) = ψ (x).

Recently with the advances of deep neural networks, it has become increasingly popular to model the critic with a deep neural network architecture, based on the objective function of minimizing the MSE of Bellman residual w.r.t. V θ or Q θ (Mnih et al., 2013) .

C EXPERIMENTAL SETUP:

Our experiments are performed on safety-augmented versions of standard MuJoCo domains (Todorov et al., 2012) .

HalfCheetah-Safe. The agent is a the standard HalfCheetah (a 2-legged simulated robot rewarded for running at high speed) augmented with safety constraints. We choose the safety constraints to be defined on the speed limit. We constrain the speed to be less than 1, i.e., constraint cost is thus

1[|v| > 1]

. Episodes are of length 200. The constraint threshold is 50.

Point Circle. This environment is taken from (Achiam et al., 2017) . The agent is a point mass (controlled via a pivot). The agent is initialized at (0, 0) and rewarded for moving counter-clockwise along a circle of radius 15 according to the reward -dx•y+dy•x 1+| √

x 2 +y 2 -15|

, for position x, y and velocity dx, dy. The safety constraint is defined as the agent staying in a position satisfying |x| ≤ 2.5. The constraint cost is thus 1[|x| > 2.5]. Episodes are of length 65. The constraint threshold is 7.

Point Gather. This environment is taken from (Achiam et al., 2017) . The agent is a point mass (controlled via a pivot) and the environment includes randomly positioned apples (2 apples) and bombs (8 bombs). The agent given a reward of 10 for each apple collected and a penalty of -10 for each bomb. The safety constraint is defined as number of bombs collected during the episode. Episodes are of length 15. The constraint threshold is 2.

Ant Gather. This environment is is the same as Point Circle, only with an ant agent (quadrapedal simulated robot). Each episode is initialized with 8 apples and 8 bombs. The agent given a reward of 10 for each apple collected, a penalty reward of -20 for each bomb collected, and a penalty reward of -20 is incurred if the episode terminates prematurely (because the ant falls). Episodes are of length at most 500. The constraint threshold is 10 for DDPG algorithms and is 5 for PPO algorithms.

Figure 4 shows the visualization of the above domains used in our experiments. Although each algorithm might have a different parameter setting that leads to the optimal performance in training, the results reported here are the best ones for each algorithm, chosen by the same criteria (which is based on value of return plus certain degree of constraint satisfaction). To account for the variability during training, in each learning curve a 95% confidence interval is also computed over 10 separate random runs (under the same parameter setting).

C.1 ADDITIONAL EXPERIMENTAL RESULTS:

In this section, we include more experimental results of various PG algorithms on safe robot locomotion tasks. 

:



Figures and Tables:

Figure1: Results of various DDPG algorithms on safe robot locomotion tasks, with x-axis in thousands of episodes. We include runs from DDPG (red), DDPG-Lagrangian (magenta), SD-DPG (blue), SDDPG-modular (green) on HalfCheetah-Safe and Point-Gather. We discover that the Lyapunov-based approaches can perform safe learning, despite the fact that the environment dynamics model and cost functions are not known, control actions are continuous, and deep function approximations are necessary.HalfCheetah-Safe, ReturnHalfCheetah-Safe, Constraint Point-Gather, Return Point-Gather, Constraint

Figure3: Constraint violations (logarithmic scale, i.e., log(1 + ccv), where ccv represents the area under constraint learning curve that is above the constraint threshold) of various PG algorithms on safe robot locomotion tasks, with x-axis in thousands of episodes. We include runs from DDPG (red), DDPG-Lagrangian (magenta), SDDPG (blue), SDDPG-modular (green), PPO (red), PPO-Lagrangian (magenta), SPPO (blue), SPPO-modular (green) on HalfCheetah-Safe and Point-Gather. Compared with Lagrangian approach, we discover that the Lyapunov-based approaches generally have more stable and safe learning, which lead to lower constraint violations.

Figure 4: The Robot Locomotion Control Tasks

Figure5: Constraint violations (logarithmic scale, i.e., log(1 + ccv)) of various PG algorithms on safe robot locomotion tasks, with x-axis in thousands of episodes. We include runs from DDPG (red), DDPG-Lagrangian (magenta), SDDPG (blue), SDDPG-modular (green), PPO (red), PPO-Lagrangian (magenta), SPPO (blue), SPPO-modular (green) on Ant-Gather and Point-Circle.

and call the constraints in this feasibility set Lyapunov constraints. For any arbitrary Lyapunov function L ∈ L π B (x 0 , d 0 ), we denote by F L

Table content: <table/>

Peer review (iclr2019):
 The paper generalized the approach for safe RL by Chow et al, leveraging Lyapunov functions to solve constraint MDPs and integrating this approach into policy optimization algorithms that can work with continuous action spaces. This work derives two classes of safe RL methods based on Lyapunov function, one based on constrained parameter policy optimization (called theta-projection), the other based on a safety layer. These methods are evaluated against Lagrangian-based counter-parts on 3 simple domains. The proposed Lyapunov-function based approach for policy optimization is certainly appealing and the derived algorithms make sense to me. This paper provides a solid contribution to the safe RL literature though there are two main reasons that dampen the excitement about the presented results: First, the contribution is solid but seems to be of somewhat incremental nature to me, combining existing recent techniques by Chow et al (2018) [Lyapunov-function based RL in CMDP], Achiam et al (2017) [CPO with PPO is identical to SPPO] and Dalal et al (2018) [safety layer]. Second, the experimental results do not seem to show a drastic benefit over the Lagrangian baselines. It is for example unclear to me whether the jiggling of the Lagrange approach around the threshold is a problem is practice. Further, it seems that PPO-Lagrangian can achieve much higher performance in the Point and Gather task while approximately staying under the constraint threshold of 2. Also, as far as I understand, the experiments are based on extensive grid search over hyper-parameters including learning rates and regularization parameters. However, it is not clear why the initialization of the Lagrange multiplier for the Lagrangian baselines was chosen fixed. I would be curious to see the results w.r.t. the best initial multiplier or a comparison without hyper-parameter grid search at all. This is a light review based on a brief read. Minor note: In the figures: where is the magenta line? I assume magenta labels refer to teal lines?