Safe Policy Learning for Continuous Control
Authors: Yinlam Chow
Ofir Nachum
Aleksandra Faust
Edgar Duenez-Guzman
Mohammad Ghavamzadeh
Venue:  (2020)
Keywords: reinforcement learning
policy gradient
safety

Abstract: We study continuous action reinforcement learning problems in which it is crucial that the agent interacts with the environment only through safe policies, i.e.,~policies that keep the agent in desirable situations, both during training and at convergence. We formulate these problems as {\em constrained} Markov decision processes (CMDPs) and present safe policy optimization algorithms that are based on a Lyapunov approach to solve them. Our algorithms can use any standard policy gradient (PG) method, such as deep deterministic policy gradient (DDPG) or proximal policy optimization (PPO), to train a neural network policy, while guaranteeing near-constraint satisfaction for every policy update by projecting either the policy parameter or the selected action onto the set of feasible solutions induced by the state-dependent linearized Lyapunov constraints. Compared to the existing constrained PG algorithms, ours are more data efficient as they are able to utilize both on-policy and off-policy data. Moreover, our action-projection algorithm 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 the state-of-the-art baselines on several simulated (MuJoCo) tasks, as well as a real-world robot obstacle-avoidance problem, demonstrating their effectiveness in terms of balancing performance and constraint satisfaction.

Under review as a conference paper at ICLR 2020
SAFE POLICY LEARNING FOR CONTINUOUS CONTROL
Anonymous authors Paper under double-blind review
ABSTRACT
We study continuous action reinforcement learning problems in which is crucial that the agent interacts with the environment only through safe policies, i.e., policies that keep the agent in desirable situations, both during training and at convergence. We formulate these problems as constrained Markov decision processes (CMDPs) and present safe policy optimization algorithms that are based on a Lyapunov approach to solve them. Our algorithms can use any standard policy gradient (PG) method, such as deep deterministic policy gradient (DDPG) proximal policy optimization (PPO), to train a neural network policy, while guaranteeing near-constraint satisfaction for every policy update by projecting either the policy parameter or the selected action onto the set of feasible solutions induced by the state-dependent linearized Lyapunov constraints. Compared to the existing constrained PG algorithms, ours are more data efficient as they are able to utilize both on-policy and off- policy data. Moreover, our action-projectio leads to less conservative policy updates and allows for natural integration into end-to-end PG training pipeline. We evaluate our algorithms and compare them with the state-of-the real-world robot -vviidnaee problem. demonstrating their effectiveness in terms of balancing performance and constraint satisfaction.
algorithm often
basclines on several simulated (MuJoCo) tasks, as well as
INTRODUCTION
The field of reinforcement learning (RL) has witnessed tremendous success in many high-dimensionnll control problems, including video games (Mnih et al., 2015), board games (Silver et al., 2016). robot locomotion (Lillicrap et al., 2016), manipulation (Levine et al., 2016; Kalashnikov et al., 2018), navigation (Faust et al., 201 8), and obstacle avoidance (Chiang et al., 2019). In RL, the ultimate goal is to optimize the expected sum of rewards/costs. and the agent is free to explore any behavior as long as leads to performance improvement. Although this freedom might be acceptable in many problems, including those involving simulators, and could expedite learning a good policy, it might be harmful in many other problems and could cause damage to the agent (robot) or to the environment (objects or people nearby). In such domains, is absolutely crucial that while the agent optimizes long-term performance, it only executes safe policies both during training and at convergence.
A natural way to incorporate safety is via constraints. A standard model for RL with constraints is constrained Markov decision process (CMDP) (Altman, 1999), where in addition its standard objective, the agent must satisfy constraints on expectations of auxiliary costs. Although optimal policies for finite CMDPs with known models can be obtained by linear programming (Altman, 1999), there are not many results for solving CMDPs when the model is unknown or the state and/or action spaces are large or infinite. A common approach solve CMDPs is to use the Lagrangian method (Altman, 1998; Geibel & Wysotzki, 2005), which augments the original objective function with a penalty on constraint violation and computes the saddle-poin of the constrained policy optimization via primal-dual methods (Chow al., 2017). Although safety is ensured when the policy converges asymptotically, a major drawback of this approach is that makes no guarantee with regards to the safety of the policies generated during training.
A few algorithms have been recently proposed to solve CMDPs at scale while remaining safe during training. One such algorithm is constrained policy optimization (CPO) (Achiam et al., 2017). CPO extends the trust-region policy optimization (TRPO) algorithm (Schulman et al., 2015a) to handle the constraints in a principled way and has shown promising empirical results in terms scalability, perfor- mance, and constraint satisfaction, both during training and convergence. Another class of these algorithms is by Chow et al. (Chow et al., 2018). These algorithms use the notion of Lyapunov func- tions that have a long history in control theory to analyze the stability of dynamical systems (Khalil, 1996). Lyapunov functions have been used in RL to guarantee closed-loop stability (Perkins & Barto, 2002; Faust et al.. 2014). They also have been used to guarantee that a model-based be brought back to a 'region of attraction" " during exploration (Berkenkamp et al., 2017). Chow et al. (Chow et al., 2018 8) use the theoretical properties of the Lyapunov functions and propose safe approximate policy and value iteration algorithms. They prove theories for their algorithms when
RL agent can

---

Under review as a conference paper at ICLR 2020
the CMDP is finite with known dynamics, and empirically evaluate them in more general settings. However, their algorithms are value-function- baaee,,,- and thus are restricted to discrete-action domains.
In this paper, we build on the problem formulation and theoretical findings of the Lyapunov- based approach to solve CMDPs, and extend it to tackle continuous action problems that play an important role in control theory and robotics. We propose Lyapunov- based safe RL algorithms that can handle problems with large or infinite action spaces, and return safe policies both during training and at convergence. To do so, there are two major difficulties that need to be addressed: 1) the policy update becomes optimization problem over the large continuous action space (similar to standard MDPs with large actions), and 2) the policy update a constrained optimization problem in which the (Lyapunov) constraints involve integration over the action space, and thus, it is often impossible to have them in forme-form. Since the number of Lyapunov constraints is equal to the number of states, the situation is even more challenging when the problem has large state space. To address the first difficulty, we switch from malue-function-basee to policy gradient (PG) algorithms. To address the second difficulty, we propose two approaches to solve our constrained policy optimization problem (a problem with infinite constraints, each involving an integral over the continuous action space) that can work with any standard on-policy (e.g., proximal policy optimization (PPO) (Schulman et al., 2017)) and off-policy (e.g., deep deterministic policy gradient (DDPG) (Lillicrap et al., 2016)) PG algorithm. Our first approach, which we call policy parameter projection or 8-projection, is a constrained optimization method that combines PG with a projection of the policy parameters onto the set of feasible solutions induced by the Lyapunov constraints. Our second approach, which we call action projection or a-projection, uses the concept of a safety layer introduced by (Dalal et al., 2018) to handle simple single-step constraints, extends this concept to general trajectory- based constraints, solves the constrained policy optimization problem in closed-form using Lyapunov functions, and integrates this closed-form into the policy network via safety-layer augmentation. Since both approaches guarantee safety at every M approximation), ensuring that all intermediate
training (ignoring errors resulting from Punction policies are safe to be deployed. To prevent constraint violations due to function approximation errors, similar to CPO, we offer a safeguard policy update rule that decreases constraint cost and ensures near-constraint satisfaction.
update, they manage to maintain safety throughout
Our proposed algorithms have two main advantages over CPO. First, since CPO is closely connected to TRPO, it can only be trivially combined with PG algorithms that are regularized with relative entropy, such as PPO. This restricts CPO to on-policy PG algorithms. On the contrary. our algorithms can work with any on-policy (e.g.. PPO) and off-policy (e.g., DDPG) PG algorithm. Having an off-policy implementation is beneficial, since off-po algorithms are potentially more -ata-efficient, as they can use the data from the replay buffer. Second, while CPO is not a back propaggapeea algorithm, due to the backtracking line-search procedure and the conjugate gradient iterations for computing natural gradient TRPO, our algorithms can be trained end-to-end, which is crucial for scalable and efficient implementation (Hafner et al., 2017). In fact, we show in Section 3.1 that CPO (minus the line search) can be viewed special case of the on-policy version (PPO version) of our P-projection algorithm, corresponding to specific approximation of the constraints.
We evaluate our algorithms and compare them with CPO and the Lagrangian method on several continuous control (MuJoCo) tasks and real-world robot navigation problem, in which the robot must satisfy certain constraints, while minimizing its expected cumulative cost. Results show that our algorithms outperform the baselines in terms of balancing the performance and constraint satisfaction (during training), and generalize better to new and more complex environments.
PRELIMINARIES
We consider the RL problem in which the agent's 's interaction with the environment is modeled as a Markov decision process (MDP). A MDP is tuple (X' AA y.e, pro. where X and A are the state and action spaces; 7 E [0. 1) a discounting factor, c(x, a) E [0, Cmax] is the immediate cost function; P(-Jr, a) is the transition probability distribution; and xo E X is the initial state. Although we consider deterministic initial state and cost function, our results can be easily generalized to random initial states and costs. We model the RL problems in which there are constraints on the cumulative cost using CMDPs. The CMDP model extends MDP by introducing additional costs and the associated constraints, and is defined by (X, A. 7, P,zo, d, du), where the first six components are the same as in the unconstrained MDP; d(x)) [0, Dmax] is the istate-depender do E R2o is an upper- on the expected cumulative constraint cost.
immediate constraint cost; and
To formalize the optimization problem associated with CMDPs, let A be the set of Markovian stationary policies, i.e., A = { X x A -> [0. 1], Σ, T(a2)) 1). At each state E X, we define the generic Bellman operator w.r. a policy π e A and a cost function as T T,,((V] [V](2) = CaeAT(ale (M(x, a) + +7 Evex P(a VVV((')) Given policy A, we define the expected
2

---

Under review as a conference paper at ICLR 2020
cumulative cost and the safety constraint function (expected cumulative constraint cost) (zu) E|>r= 7 "f( as) | n, aro] and (=0 == [[> 7 /d( n, zo), respectively. The safety constraint is then defined as (2o)) I do. The goal in CMDPs is to solve the constrained optimization problem
n² E arg min (Co(2)) Dx S do}.
(I)
REA
It has been shown that if the feasibility set is non-empty, then there exists an optimal policy in the class of stationary Markovian policies A (Altman, 1999, Theorem 3.1).
2.1 POLICY GRADIENT ALGORITHMS
Policy gradient (PG) algorithms optimize a policy by computing a sample estimate of the gradient of the expected cumulative cost induced by the policy, and then updating the policy parameter in the gradient direction. In general, stochastic policies that give probability distribution over actions are parameterized by a k-dimensional vector 8, the space of policies as (TT, E @ c JR*). Since in this setting a policy x is uniquely defined by its parameter 8, policy-dependent functions can be written as function of 0 or interchangeably.
be written
DDPG (Lillicrap et al., 2016) and PPO (Schulman et al., 2017) are two PG algorithms that have recently gained popularity in solving continuous control problems. DDPG is an off-policy Qllaarning style algorithm that jointly trains a deterministic policy ()( and a Q-value approximator Q(z, a; Φ)- The Q-value approximator is trained to fit the true Q-value function and the deterministic policy is trained to optimize Q(2, (z)); d) via chain-rule. The PPO algorithm we use in this paper is penalty form of TRPO (Schulman et al., 2015a) with an adaptive rule to tune the Drz penalty weight S.. PPO trains a policy ==(x) by optimizing a loss function that consists of the standard policy gradient objective and a penalty on the KL-divergence between the current ( and previous l' policies, i... (0,, 0²) E[E, 7 DDi. (Tgg ([zx)][==(-)er [o],
2.2
LAGRANGIAN METHOD
Lagrangian method a straightforward way to address the constraint Dxp (xa) S da in CMDPs, La- grangian method adds the constraint costs d(x) to the task costs c(x, a) and transform the constrained optimization problem to penalty form, i.e., minage maxx>0 IF =E c(zs, az) + Ad(z)) ro, mo. Ado. The method then jointly optimizes @ and À to find a saddle-point of the penalized objective. The optimization
may be performed by any PG algorithm on the augmented cost c(z, a) + Ad(x), while A is optimized by stochastic gradient descent. As described in Sec. 1, although the Lagrangian approach is easy to implement (see Appendix A for the details), in practice, it often violates the constraints during training. While at each step during training, the objective encourages finding a safe solution, the current value of A may lead to an unsafe policy. This is why the Lagrangian method may not be suitable for solving problems in which safety is crucial during training.
2.3 LYAPUNOV FUNCTIONS
Since in this paper, we extend the Lyapunov- based approach to CMDPs of (Chow et al., 2018) to PG algorithms, we end this section by introducing some terms and notations from (Chow et al., 2018) that are important in developing our safe PG algorithms. We refer readers to Appendix B for details.
We define a set of Lyapunov functions w.r.t. initial state To E X' and constraint threshold do as Lig (zo, da) {L X + R20 Tag.a [[(z) < L(x), Vo E X, L(zo). < du), where To is feasible policy of (1), i.e., Dag (zo) < do- We refer to the constraints in this feasibility set as the Lyapunov constraints. For an arbitrary Lyapunov function L E Lng (z), we denote by (z) < L(x), Va E X3. the set of L-induced Markoy stationary policies. The
Fr = E A contraction property of Te.ds together with L(xo) S do. imply that any L-induced policy in F, is a feasible policy of (1). However, Fz(x) does not always contain an optimal solution of (1), and thus, it is necessary to design Lyapunov function that provides this guarantee. In other words, the main goal of the Lyapunov approach is to construct Lyapunov function L E Lxg (zu, do), such that FL contains an optimal policy x", i.e., L(x) Z Ts. Ta (z))). Chow et al. (2018) show in their Theorem 1 that without loss of optimality, the Lyapunov function that satisfies the above criterion can be expressed as L (x)= := E Er> 7' (d(#;) + <(x=)) æ in which exx) 2 0 is a specific immediate auxiliary constraint cost that keeps track of the maximum constraint budget available for policy improvement (from Re to x x"). They propose ways to construct such e, as well as an auxiliary constraint cost surrogate é, which is a tight upper-bound on and can be computed more efficiently. They use this construction to propose the safe (approximate) policy and value iteration algorithms, whose objective is to solve the following LP (Chow et al., 2018 Eq. 6) during policy improvement:
[ Qvap (z, a))(a(s), SaEA
T (-|=) = arg min
s.t. Saed Qung (5.a) a) (π((a - =B(a|=)) S ((x), (2)
TEa a
3

---

Under review as a conference paper at ICLR 2020
where Vig = T=g.e[Vag]()) and Qveg (x, c(f,a) 7 P(z' a)V V (x') are the value
and state-action value functions (w.r.t. the cost function c), and Qing (2, = d(z) + ?(z) + y E. P('' a)Lrg, x(x') is the Lyapunov function. In any iterative policy optimization method, such as those studied in this paper, the feasible policy at each iteration can be set to the policy
computed at the previous iteration (which is feasible).
In L. (2), there are as many constraints as the number of states and each constraint involves an integral over the entire action space. When the state space is large, even if the integral in the constraint has a closed-form (e.g., for finite actions), solving (2) becomes numerically intractable. Chow et al. (Chow et al., 2018) assumed that the number of actions finite and focused on valuc-function-basee algorithmms, and addressed the large state issue by policy distillation. Since in this paper. we are interested in problems with large action spaces, solving (2) will be even more challenging. To address this issue, in the next section, first switch from salue-function-based algorithms to PG algorithms, then propose an optimization problem with I Lyapunov constraints, analogous to (2), that suitable for PG, and finally present two methods to solve our proposed optimization problem efficiently.
RL
3 SAFE LYAPUNOV-BAST
POLICY GRADIENT
We now present our approach to solve CMDPs in a way that guarantees safety both at convergence and during training. Similar to (Chow et al., 2018), our Lyapunov-based safe PG algorithms solve a constrained optimization problem analogous to (2). In particular, our algorithms consist of two components, baseline PG algorithm, such as DDPG or PPO. and an effective method to solve the general yyapunov-basee policy optimization problem, the analogous to (2), i.e,
0+ = arg min (z,(, s.t. age
(To(a]>) - (a(a)) QLan (z, a) da S 2(x), Ve E X. AEA
(3)
In the next two sections, we present two approaches solve (3) efficiently. We call these approaches 1) 0- 8-projection, a constrained optimization method that combines PG with projecting the policy parameter O onto the set of feasible solutions induced by the Lyapunov constraints, and 2) a-projection, in which we embed the Lyapunov constraints into the policy network via safety layer.
3.1 THE (-PROJECTION APPROACH
The 0- e-projection approach is based on the cninoorizationmmaiiiiatee technique in conservative PG (Kakade & Langford, 2002) and Taylor series expansion, and can be applied to both on- policy and off-policy algorithms. Following Theorem 4.1 in (Kakade & Langford, 2002), first have the following bound for the cumulative cost: D0, 0B) S CT, - Crog (zo)
T To-pen am (Qe,, (z,a) - Vo (+) S (0, 0p), where g0g..0 .n is the 7-visiting distribution of Tog starting at the initial state æu. and 3 is the weight for the entropy-based regularization. 1 Using this result, we denote by C²,, (oo; Crep (zo) + kL. (0, 0g) -Fx--ere..... a~m [Qva (x,, a) - Vog (z) the surrogate cumulative cost. It has been shown in Eq. 10 of (Schulman et al., 2015a) that replacing the objective function C.p (fo) with its surrogate C. (æo; Teg) ] in solving (3) will still lead to policy improvement. In order to effectively compute the improved policy parameter 0,, one further approxi- mates the function Che,, (zo: g with its Taylor series expansion around 0g. In particular, the term [Qen, (z, a) - Veg (x)] is approximated up its first order, and the term (K 0g)
Ee-pe y zo u0033 is approximated up to its second order. These altogether allow us to replace the objective function in (3) with ((0- 0D), VoEz~ a~xy [Qveg a))) + 2 ((O - 0D), vğDxu 00) la=ag (0- 0z)).
Similarly, regarding the constraints in (3), we can use the Taylor series expansion (around 0g) to approximate the LHS of the Lyapunov constraints as (Te (a(a))) Qu(2, a) da s
((0 0g), Vollawag Sittwws!Qee, (z, a) (==9g)- Using the above approximations, at each iteration, our safe PG algorithm updates the policy by solving the following constrained optimization problem with semi-infinite dimensional Lyapunov constraints:
B ((0 0R), (0DKL(0,0K) le-0g (0 0a)), 0_ E arg min {(0- ((0-0)), Veln- anmn [Qvg (a, (s,)))) + 0E
#2
s.t. {(0- BB). VoFawry (Qla (z) 10=0,> > {(r), Vx E X.
(4)
It can be seen that if the errors resulted from the neural network parameterizations of Qva,, and Q and the Taylor series expansions are small, then an algorithm that updates the policy parameter by solving (4) can ensure safety during training. However, the presence of infinte-dimensiioal Lyapunov constraints makes solving (4) intractable. solution to this is to write the Lyapumov constraints in (4) (without loss of optimality) as maxze ((o - 0p), Vol. IQ (Qe,, (z, a)] (==0a) - ?(x) s O. Since
'Theorem I in (Schulman et al., 2015a) provides recipe for computing such that the minorization- maximization inequality holds, But in practice, B is treated as tunable parameter for entropy regularization.
4

---

Under review as a conference paper at ICLR 2020
the above max-operator is non-differentiable, this may still lead to numerical instability in gradient descent algorithms. Similar to the surrogate constraint in TRPO (to transform the max DKL constraint to an average DxL, constraint, see Eq. 12 in (Schulman et al., 2015a)), a more numerically stable way is to approximate the Lyapunov constraint using the average constraint surrogate
1 (10 0B), M
1 M Σ ((c:),
veLamaylQiog (I., a)] le-0 >
(5)
where M is the number of on-policy sample trajectories of Tég. In order to effectively compute the gradient of the Lyapunov value function, consider the special case when the auxiliary constraint sur- rogate is chosen as ē = (do Drug (xo)) (see Appendix B for justification). Using the fact that Z is 0-independent, the gradient term in (5) can be written as J. m=(alx) Vo log To(a)z) QWag (xi, a)da, where W (x) = =Wen (x) and Qwog (z, d(x) + 7 Σn Pa a)Wag (z') are the con- straint value functions, respectively. Since the integral is equal to Fa (xt, a)}, the average constraint surrogate (5) can be approximated (approximation is because of the choice of 2) by the inequality Drog (2r) + T ((0- 0g). Nz E Vo a- Qwa, (21, a)]lo=00) do. which is equivalent to the constraint used in CPO (see Section 6.1 in (Achiam et al., 2017)). This shows that CPO (minus the line search) belongs to the class of our Lyapunov-basee PG algorithms with 0- d-projection. We refer to the DDPG and PPO versions of our d-projection safe PG algorithms as SDDPG and SPPO. Derivation details and the pseudo-code (Algorithm 4) of these algorithms are given in Appendix C.
3.2 THE a- C-PROEECTION APPROACH
The main characteristic of the Lyapunov approach is to break down trajectory- based constraint into a sequence of single-step state dependenl constraints. However, when the state space is infinite, the feasibility set is characterized by infinite dimensional constraints. and thus, it is counter-intuitive to directly enforce these Lyapunov constraints (as opposed to the original trajectory- based constraint) into the policy update optimization. To address this, we leverage the idea of a safety layer from (Dalal et al., 2018), that was applied to simple single-step constraints, and propose a novel approach to embed the set of Lyapunov constraints into the policy network. This way. we reformulate the CMDP problem (1) as an unconstrained optimization problem and optimize its policy parameter 0 (of the augmented network) using any standard unconstrained PG algorithm. At every given state, the unconstrained action is first computed and then passed through the safety layer, where feasible action mapping is constructed by projecting unconstrained actions onto the feasibility set w.r.t. Lyapunov constraints. This constraint projection approach can guarantee safety during training.
We now describe how the action mapping (to the set of Lyapunov constraints) works?. Recall from the policy improvement problem in (3) that the Lyapunov constraint is imposed at every state x E X. Given a baseline feasible policy TB = TBg, for any arbitrary policy parameter 0 E Ô, we denote by E(Tp, 0) = {0' E θ : QLng (2t, -ar (x)) Q2np (z, (x)) < ((x), Vr E X), the projection of a onto the feasibility set induced by the Lyapunov constraints. One way to construct a feasible policy
T 8) from parameter 0 is to solve the following Ez-projection problem:
()( E arg min aEA
Illaa ma(x))) S.L. Qt. (2. Qi. (I,) E((x).
(6)
We refer to this operation as the Lyαpunov safety layer. Intuitively, this projection perturbs the unconstrained action as little as possible in the Euclidean norm in order satisfy the Lyapunov constraints, Since this projection guarantees safety, if we have access to a closed form of the projection, we may insert it into the policy parameterization and simply solve an unconstrained policy optimization problem, i.e., 0+ arg millage Cr 0) (zo), using any standard PG algorithm.
To simplify the projection (6), we can approximate the LHS of the Lyapumov constraint with its first-order Taylor series (w.rtt action a = (z)))). Thus, at any given state x e X, the safety layer solves the following projection problem:
1-7(2) [a)m0(>))1++++ v(x) ( [[-- s.t. (a-TD(>)) (xng(>) ((x), (7)
TH(mn .) (x) argmin aeAA
2
where n|x) E [0, 1) is the mixing parameter that controls the trade-off between projecting on un- constrained policy (for return maximization) and on baseline policy (for safety), and g1. (r) ==
v.Qu.. (I.a) la= is the action- grrodinnr of the state-action Lyapunov function.
Similar to the analysis of Section 3.1, if the auxiliary cost غ is sate-independent, one can readily find gh. n (z) by computing the gradient of the constraint action-value function V.Qwag (æ, a) (a))
In our experiments, we use stochastic (Gaussian) policies with parameterized mean and fixed variance. We leave extension of the a-projection approach policies in which variance is also parameterized as future work.
5

---

Under review as a conference paper at ICLR 2020
60-
0-
0-
40-
-0-
100
0-
(a) HalfChestal-Safe, Return
(b) Point-Gather, Return
(c) HalfChetaal-Sffe
Con-
(d) Point-Gather. Constraint
straint
Figure 1: DDPG (red). DDPG-Lagrangian (cyan), SDDPG (blue), SDDPG a-projection (green) on HalfCheetah- Safe and Point-Gathen SDDPG and SDDPG a-projection perform stable and safe learning, although the dynamics and cost functions are unknown, control actions are continuous, and deep function approximations are used. Unit of x-axis is in thousands of episodes. Shaded areas represent the 1-SD confidence intervals (over 10 random seeds). The dashed purple line in the two right figures represents the constraint limit.
Note that the objective function in (7) is positive-definite and quadratie, and the constraint approxima- tion is linear. Therefore, the solution of this (convex) projection problem can be effectively computed by an in-graph QP-solver, such as OPT-Net (Amos & Kolter, 2017). Combined with the above projection procedure, this further implies that the CMDP problem can be effectively solved using an end-to-end PG training pipeline (such as DDPG or PPO). When the CMDP has single constraint (and thus a single Lyapunov constraint), the policy ()(x).0)(z) has the following analytical solution.
Proposition 1. At any given state x X, the solution to the optimization problem (7)
has the form ()(=))))()) = (1 - (xx) + (z)))=(z) - >²(x) gLig (2), where X (z)
((11- g (x) (TT( - =x())) - -((x))/)_L (x) _L-n (x))+-
The closed-form solution is essentially a linear projection of the unconstrained action To (2r) onto the Lyapunov-safe hyper-plane with slope gL.,, (z) and intercept ē(x) (1 (do "aag (z.)). It is possible to extend this closed-form solution to handle multiple constraints, if there is at most one constraint active a time (see Proposition in (Dalal et al., 201 ()). We refer to the DDPG and PPO versions of our a- e-projection safe Lyapunov-basee PG algorithms as SDDPG a- a-projection and SPPO a-projection. Derivation and pseudo-code (Algorithm 5) of these algorithms are in Appendix C.
4 EXPERIMENTS ON MuJoCo BENCHMARKS
We empirically evaluate* our Lyapunov-based safe PG algorithms to assess their: (i) performance in terms of cost and safety during training, and (ii) robustness w.r.t. constraint violation. We use three simulated robot locomotion continuous control tasks in the MuJoCo simulator (Todorov et al., 2012). The notion of safety in these tasks is motivated by physical constraints: (i) HalfCheetabhSafts this is a modification of the MuJoCo HalfCheetah problem which we impose constraints on the speed of Cheetah in order to force it to run smoothly. The video shows that the policy learned by our algorithm results in slower but much smoother movement of Cheetah compared to the policies learned by PPO and I Lagrangian*: 4 (ii) Point-Circle: the agent is rewarded for running in a wide circle, but is constrained to stay within safe region defined by |a| S Zimmi (ii) Seint-Gather & Ant-Gather: the agent is rewarded for collecting target objects in a terrain map, while being constrained to avoid bombs. The last two tasks were first introduced in (Achiam et al., 2017) by adding constraints to the original MuJoCo tasks: Point and Ant. Details of these tasks are given in Appendix D.
We compare our algorithms with two saate-of-the-are unconstrained algorithms, DDPG and PPO, and two constrained methods, Lagrangian with optimized Lagrange multiplier (Appendix A) and on-policy CPO. We use the CPO algorithm that is based on PPO (unlike the original CPO that is based on TRPO) and coincides with our SPPO algorithm derived in Section 4.1. SPPO preserves the essence of CPO by adding the first-order constraint and relative entropy regularization to the policy optimization problem. The main difference between CPO and SPPO is that the latter does not perform backtracking line-search in learning rate. We compare with SPPO instead of CPO to 1) avoid the additional computational complexity of line-search in TRPO, while maintaining the performance of PG using PPO, 2) have a proppaaaaee version of CPO, and 3) have a fair comparison with other back paok-propagetable safe PG algorithms, such as our DDPG and a-projection based algorithms.
Comparison with baselines: Figures la, 1b, 2a, 2b, 8a, 8b, 9a, 9b show that our Lyapunov-based PG algorithms are stable in learning and all converge to feasible policies with reasonable performance. Figures 1c, 1d, 2c, 2d, 8c, 8d, 9c, 9b show the algorithms in terms of constraint violation during
'Videos of MuJoCo experiments can be found at https: /ttp///drvvvve//e wwttriie.gooogloo google. com/ filc/d/ 1FWbuEnKN2 DIRKGN21WWEERE WWW.WW 2yyoo (et///ee11///////// WWe also imposed constraint on the torque at the Cheetah's joints in order force it run more smoothly and obtained similar results imposing constraint its speed.

---

Under review as a conference paper at ICLR 2020
50-
40-
40-
100
0-
0g
(a) HalfChettal-Safe, Return
(b) Point-Gather, Return
(c) HallChettab-Safe straint
Con-
(d) Point-Gather, Constraint
Figure 2: PPO (red), PPO-Lagrangian (cyan), SPPO (blue), SPPO a-projection (green) on HallCheetah- and Point-Gather. SPPO a-projection perform stable and safe learning, when the dynamics and cost functions
are unknown, control actions are continuous, and deep function approximation is used.
(a) Noisy Lidar observation corridor
54-
Revart Redencee
Constrine: Total loaage call
Rublen Agai
Saft DDPG
(a) Navigation. Success %
(b) Navigation, Constraint
Nntor
Onlic
Figure 4: DDPG (red), DDPG-Lagrangian (cyan), SDDPG (blue). DDPG a-projection (green) Robot Navigation. Ours (SDDPG, SDDPG a-projection) balance between reward and constraint learning. Unit of x-axis is in thousands of steps. The shaded areas represent the 1-SD confidence intervals (over 50 runs). The dashed purple line represents the constraint limit.
Goal Robel
(b) SDDPG for point point task
Figure 3:
Robot navigation task details.
training. These figures indicate that our algorithms quickly stabilize the constraint cost below the threshold, while the unconstrained DDPG and PPO violate the constraints, and Lagrangian tends to jiggle around the threshold. Moreover, it worth-noting that the Lagrangian method can be sensitive to the initialization of the Lagrange multiplier A If Ag is too large, it would make policy updates overly conservative, and if it is too small, then we will have more constraint violation. Without further knowledge about the environment, we treat Åo as hyper-parameter and optimize it via grid grid-search. See Appendix for more details and for the experimental results of Ant- Ant-Gahher and Point-Circle
a-projection vs. 0-projection: The figures indicate that in many cases DDPG and PPO with a- projection converge faster and have lower constraint violation than their O-projection counterparts (i.e., SDDPG and SPPO). This corroborates with the hypothesis that a-projection is less conservative during policy updates than d-projection (which is what CPO is based on) and generates smoother gradient updates during end-to-end training.
In most experiments (HalfCheetah, PointGather, and AntGather) the DDPG algo- rithms tend to have faster learning than their PPO counterparts, while the PPO algorithms perform better in terms of constraint satisfaction. The faster learning behavior is due to the improved data- efficiency when using off-policy samples in PG, however, the covariate-shift in off-policy data makes tight constraint control more challenging.
DDPG vs. PPO:
SAFE POLICY GRADIENT FOR ROBOT NAVIGATION
We now evaluate safe policy optimization algorithms on a real robot task - a map-less navigation task (Chiang et al., 2019) where a noisy differential drive robot with limited sensors (Fig. 3a) is required to navigate to goal outside of its field of view in unseen environments while avoiding collision. The main goal is to learn a policy that drives the robot to goal as efficiently as possible, while limiting the impact energy of collisions, since the collision can damage the robot and environment.
Here the CMDP is non-discounting and has a fixed horizon. The agent's observations consist of the relative goal position, agent's velocity, and Lidar measurements (Fig. 3a). The actions are the linear and angular velocity at the robot's center of the mass. 6 'hee transition probability captures the noisy robot's dynamics, whose exact formulation is unknown the robot. The robot must navigate
Herre covariate shift is due to the fact that training data is generated by a policy that is different from the current policy that is being optimized.
'The first dimension is the robot's desired linear velocity (speed at which the robot should go straight). The second dimension is the robot's angular velocity speed at which the robot should tur. Both velocity vectors are applied the center of the mass of the robot.
7

---

Under review as a conference paper at ICLR 2020
12-
DORG DNPG
SLO0PG
5S 0003
3000
16-NNNG
SLOORE
06-
04
X00-
pagge fral
PiN
02-
00
05
5:13
30-15
05
5-30
10:35
Gool Distance Range (m)
Goal Distance fiange (mi
(a) Navigation, Success %
(b) Navigation, Constraint
Figure 6: Generalization over success rate (d) and constraint satisfaction (e) different environment. The average success rate and cumulative (trajectory- based) constraint cost are over 100 tasks (randomly sampled start and goal robot positions). A task is con- sidered successful if the robot reaches the goal in the map-less navigation task, regardless of the constraint.
Lagrangian
(b) SDDPG projection
(c) SUDPG projection
Figure 5: Navigation routes of two learned policies in the simulator (a) and (b). On-robot experiment (c).
to arbitrary goal positions collision-free in a previously unseen environment, and without access to the indoor map and any work-space topology. We reward the agent for reaching the goal, which translates to an immediate cost that measures the relative distance to the goal. To measure the total impact energy of obstacle collisions, we impose an immediate constraint cost to account for the speed during collision, with constraint threshold do that characterizes the agent's 's maximum tolerable collision impact energy to any object. Different from the standard approach, where a constraint on collision speed is explicitly imposed to the learning problem at each time step, we emphasize that a CMDP constraint is required here because it allows the robot to lightly brush off the obstacle (such as walls) but prevent it from ramming into any objects. Other use cases of CMDP constraints in robot navigation include collision avoidance (Preiffer et al., 2018) or limiting total battery usage of the task.
We evaluate the learning algorithms on success rate and constraint control averaged over 100 episodes with random initialization. The task is successful if the robot reaches the goal before the constraint threshold (total energy of collision)
Experimental Results:
exhausted. While all methods
converge to policies with reasonable performance, Figure 4a and 4b show that the Lyapunov-base based PG algorithms have higher success rates, due to their robust abilities of controlling the total constraint, as well minimizing the distance goal. Although the unconstrained method often yields a lower distance to goal, it violates the constraint more frequently leading to a lower success rate. Lagrangian approach is less robust to initialization of parameters, and therefore it generally has lower success rate and higher variability than the Lyapunov-based methods. Unfortunately due to function approximation error and stochasticity of the problem, all the algorithms converged pre-maturely with constraints above the threshold, possibly due to the overly conservative constraint threshold (dg = 100). Inspection of trajectories shows that the Lagrangian method tends to zigzag and has more collisions, while the SDDPG chooses safer path reach the goal (Figures 5a and 5b).
Next, we evaluate how well the methods generalize to (i) longer trajectories, and (ii) new environments. The tasks are trained in a 22 by 18 meters environment (Fig. 7) with goals placed within 5 to 10 meters from the robot initial state. In much larger evaluation environment (60 by 47 meters) with goals placed up to 15 meters away from the goal, the success rate of all methods degrades as the goals are further away (Fig. 6a). The safety methods (a-projection - SL--DDG, and f-projection SG-DDPG) outperform unconstrained and Lagrangian (DDPG and LA-DDPG), while retaining the lower constraints even when the task becomes more difficult (Fig. 6b).
Finally, we deployed the SL-DDPG policy onto the real Fetch robot (Wise et al., 2016) in an everyday office environment." Fetch robot weights 150 kilograms, and reaches maximum speed of 7 km/h making the collision force a safety paramount. Figure Sc shows the top down view of the robot log. Robot travelled, through narrow corridors and around people walking through the office, for a total of 500 meters to complete five repetitions of 12 tasks, each averaging about 10 meters to the goal. The robot robustly avoids both static and dynamic (humans) obstacles coming into its path. We observed additional "wobbling" effects, that was not present in simulation. This is likely due to the wheel slippage at the floor that the policy was not trained for. In several occasions when the robot could not find a clear path, the policy instructed the robot to stay put instead of narrowly passing by the obstacle. This is precisely the safety behavior we want to achieve with the Lyapunov- based algorithms.
6 CONCLUSIONS AND FUTURE WORK
We used the notion of Lyapunov functions and developed a class of safe RL algorithms for continuous action problems. Each algorithm in this class is a combination of one of our two proposed projections:
7 Videos of Fetch robot navigation can be found in the following link: https: //driv/v seriveegeee google e. com/ fi 1e/6// FwbuEnkN21 LWFMKV www 2Cydo2#Qvdc 1 401 //vvvviiee htt////wwwssssssaaiiineeee
8

---

Under review as a conference paper at ICLR 2020
8 e-pooeectoon and d-projection, with any on-policy (e.g.. PPO) off- off--oolicy (e.g., DDPG) (e.g..DPG) PG algorithm. We evaluated our algorithmss on four high-dimensional simulated robot locomotion MuJoCo tasks and compared them with several baselines. To demonstrate the effectiveness of our algorithms in solving real-world problems, we also applied them an indoor robot navigation problem, to ensure that the robot's path is optimal and collision-free. Our results indicate that our algorithms achieve safe learning, 2) have better data-efficiency, 3) can be more naturally integrated within the standard end-to-end differentiable PG training pipeline, and 4) are scalable to tackle real-world problems. Our work is step forward in deploying RL to real-wort wolld problems in which safety guarantees are of paramount importance. Future work includes 1) extending a- e-projection to stochastic policies and 2) extensions of the Lyapunov approach to model-based RL. and use it for safe exploration.

---

Under review as a conference paper at ICLR 2020
REFERENCES
Achiam, Held, A. Tamar, and Abbeel. Constrained policy optimization. arXiv preprint 1rXiv:1705.10528, 2017.
E. Altman. Constrained Markov decision processes with total cost criteria: Lagrangian approach and dual linear program. Mathematical methods of operations research, 48(3):387-417, 1998.
E. Altman. Constrained Markov decision processes, volume 7. CRC Press, 1999.
B. Amos and Z. Kolter. Optnet: Differentiable optimization as a layer in neural networks. arXiv preprint xrvi: htt:::773.00444 2017.
F. Berkenkamp, M. Turchetta, A. Schoellig, and A. Krause. Safe model-based reinforcement learning with stability guarantees. In Advances in Neural Information Processing Systems, pp. 908-918, 2017.
D. Bertsekas. Nonlinear programming. Athena scientific Belmont, 1999.
D. Bertsekas. Dynamic programming and optimal control, volume 1-2. Athena scientific Belmont, MA, 2005.
H. Chiang, A. Faust, M., and A. Francis. Learning navigation behaviors end-to-end with autorl. JEEE Robotics and Automation Letters, 4(2):2007-2014, 2019.
Y. Chow, M. Ghavamzadeh, L.. Janson, and M. Pavone. Risk-constrained reinforcement learning with percentile risk criteria. Journal of Machine Learning Research, 18(1):6070-61) 6120, 2017.
Y. Chow, O. Nachum, E. Duenez-Guzman, and M. Ghavamzadeh. A Lyapunov-based approach to safe reinforcement learning. In Proceedings of Advances in Neural Information Processing Systems 32, pp. 12, 2018.
G. Dalal, K. Dvijotham, M. Vecerik, T. Hester, C. Paduraru, and Y. Tassa. Safe exploration in continuous action spaces. arXiv preprint /001://00.0775: 2018.
A. Faust, P. Ruymgaart, M. Salman, R. Fierro, and L. Tapia. Continuous action reinforcement learning for control-affing systems with unknown dynamics. Acta Automatica Sinica Special Issue Extensions of Reinforcement Learning and Adaptive Control, IEEE/CAA Journal of, 1(3): 323-336, July 2014.
A. Faust, O. Ramirez, M. Fiser, K. Oslund, A. Francis, J. Davidson, and L. Tapia. PRM-RI Long- range robotic navigation tasks by combining reinforcement learning and sampling-based planning. In IEEE International Conference on Robot Automation, pp. 51 5113-5120, 2018.
P. Geibel and F. Wysotzki. Risk-sensitive reinforcement learning applied to control under constraints. Journal of Artificial Intelligncce Research, 24:81-108, 2005.
D. Hafner, J. Davidson, and Vanhoucke. TensorFlow Agents: Efficient batched reinforcement learning in tensorflow. arXiv preprint arXiv:1709.02877 2017.
Kakade and J. Langford. Approximately optimal approximate reinforcement learning. In ICML, volume 2, pp. 267-274, 2002.
D. Kalashnikov, A. Irpan, P. Sampedro, J. Ibarz. A. Herzog, E. Jang, D. Quillen, E. Holly, M. Kalakr- ishnan, V. Vanhoucke. and S. Levine. QT-Opt: Scalable deep reinforcement learning for vision- based robotic manipulation. 2018. URL https: arxiv pttp///////...1299999.
H. Khalil. Noninear systems. Prentice-Hall New Jersey, 2(5):5-1, 1996.
S. Levine, C. Finn, T. Darrell, and Abbeel. End-to-end training of deep visuo-motor policies. Journal of Machine Learning Research, 17:1-40, 2016.
Lillicrap, Hunt, A. Pritzel, N. Heess, T. Erez, Y. Tassa, Silver, and D. Wierstra. Continuous control with deep reinforcement learning. In International Conference on Learning Representations, 2016.
V. Mnih, K. Kavukcuoglu, D. Silver, A. Graves, I. Antonoglou, D. Wierstra, and M. Riedmiller. Playing Atari with deep reinforcement learning. arXiv preprint arXiv: 1312.5602, 2013.
10

---

Under review as a conference paper at ICLR 2020
V. Mnih, K. Kavukcuoglu, D. Silver, A. Rusu, J. Veness, M. Bellemare, A. Graves, M. Riedmiller, A. Fidjeland, G. Ostrovski, S. Petersen, C. Beattie, A. Sadik, I. Antonoglou, H. King, D. Kumaran, D. Wierstra, S. Legg, and D. Hassabis. Human-level control through deep reinforcement learning.
Nature, 518(7540):529-555 -335339,,,,, 2015.
T. Perkins and A. Barto. Lyapunov design for safe reinforcement learning, Journal of Machine Learning Research, 3(Dec):803-82) 832. 2002.
M. Pfeiffer, S. Shukla, M. Turchetta, C. Cadena, A. Krause, R. Siegwart, and J. Nieto. Reinforced imitation: Sample efficient deep reinforcement learning for mapless navigation by leveraging prior demonstrations. IEEE Robotics and Automation Letters, 344):4423-4430, 2018.
Schaul, J. Quan, I. Antonoglou, and D. Silver. Prioritized experience replay. arXiv preprint arXiv: 1.055552, 2015.
Schulman, S. Levine, Moritz, M. Jordan, and P. Abbeel. Trust region policy optimization. In Proceedings of the 32nd International Conference on Machine Learning. pp- 1889-1199 2015a.
J. Schulman, P. Moritz, S. Levine, Jordan, and P. Abbeel. High-dimensional continuous control using generalized advantage estimation. arXiv preprint vrXiv:1506.02433. 2015b.
J. Schulman, F. Wolski, P. Dhariwal, A. Radford, and O. Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv: arXiv: 177.006377 2017
D. Silver, A. Huang, C. Maddison, A. Guez, L. Sifre. G. van den Driessche, J. Schrittwiese, Antonoglou, V. Panneershelvam, M. Lanetot, S. Dieleman, D. Grewe, J. Nham, N. Kalchbrenner, Sutskever, T. Lillicrap, M. Leach, K. Kavukcuoglu, T. Graepel, and D. Hassabis. Mastering the game of Go with deep neural networks and tree search. Nature, 529(7587):4844455 489, 2016.
R. Sutton, D. McAllester, S. Singh, and Y. Mansour. Policy gradient methods for reinforcement learn- ing with function approximation, In Proceedings Advances in Neural Information Processing Systems 12, pp. 1057-1063. 2000.
E. Todorov, T. Erez, and Y. Tassa. Mujoco: A physics engine for model-based control. In Intelligent Robots and Systems (IROS), 2012 IEEE/RSJ International Conference on, pp. 5026-5033, IEEE, 2012.
M. Wise, M. Ferguson, D. King, E. Diehr, and D. Dymesich. Fetch & Freight: Standard platforms for service robot applications. In Workshop on Autonomous Mobile Service Robots held at the 2016 International Joint Conference on Artificial Intelligence, 2016

---

Under review as a conference paper at ICLR 2020
A THE LAGRANGIAN APPROACH TO SAFE RL
We first state a number of mild technical and notational assumptions that we make throughout this section.
Assumption (Differentiability).. For any state-action pair (ar, a). xo(aax) is continuously differen- tiable in and Vozo (a (x) is a Lipschitz function function for every x E X and a E A.
Assumption 2 (Strict Feasibility). There exists a transient policy To xo(-aa) such that Dry (xO) < do in the constrained problem.
Assumption 3 (Step Sizes). The step size schedules {a.z,h {az,k), and {ai,tt satisfy
Σ 01,
=
Σ
02,k Σ
03,8 00,
(8)
k
Σ ii
Σ
22,k Σ
03, <
0c,
(9)
k
01 = o((2,R)
02,k = =(
(10)
Assumption imposes smoothness on the optimal policy, Assumption 2 guarantees the existence of a local saddle point in the Lagrangian analysis. Assumption 3 refers to step sizes corresponding to policy updates and indicates that the update corresponding {03,,e) is the fastest time-scale, the updates corresponding to {02.a} is on the intermediate time-scale, and the update corresponding to {or1,e} is on the slowest time-scale. As this assumption refers 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:
max min [(e,)) - Cro (zo) + (Dr, do) ) X20
(11)
where À is the Lagrange multiplier. Notice that L(B, is linear function in X. Then, there exists local saddle point (0*, x²) for the minimax optimization problem maxx2o ming [(0 A), such that for some > 0, v0 E R" n Bg (r), and AA E [0, Amax]. we have
L(O, x²) 2 L( X²) 2 L(0",
(12)
where Bg- (r) is dyper-dimensional ball centered at 6 with radius 0.
In the following, we present policy gradient (PG) algorithm and an actor-critic (AC) algorithm. While the PG algorithm updates its parameters after observing several trajectories, the AC algorithm is incremental and updates its parameters at each time-step.
We now present policy gradient algorithm to solve the optimization problem (11). The idea of the algorithm is to descend and ascend in À using the gradients of L(0, X) w.r.t. f and X, i.e.
VoL(O, = Vo (Cz, ADr, (zo))
L A) D=, (2ro) - dg-
(13)
The unit of observation in this algorithm system trajectory generated by following the current policy Te.- At each iteration, the algorithm generates N trajectories by following the current policy Te., uses them to estimate the gradients in (13), and then uses these estimates to update the parameters 0, X. Let & (Zo, Go Co 21, 01, Ci,.... FT-1, 0r-1, CT- Fr) be trajectory generated by follow- ing the policy 6, where 2T = Fia 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(E) = TT-I ""((z ap), D(E) -T- 7 )d((x), and PP((S) = Po(zo) ) I1K-0 (ax (r P(z++ |I ax), respectively. Based on the definition of Po(E), one obtains Vo log PP)(E) E1= Vo log To (Tx((a))))
Algorithm I contains the pseudo-code of our proposed PG algorithm. What appears inside the parentheses the right-hand-side of the update equations are the estimates of the gradients of L(,, A) w.r.t 0,A A (estimates of the expressions in (13)). Gradient estimates of the Lagrangian function are given by
(oL(O, Σ Po(E) Vo log (C.o (5) (D)(())), VAL(O,A) -do Σ Po(E)-D(E),
12

---

Under review as a conference paper at ICLR 2020
Algorithm 1 Lagrangian Trajectory-basee Policy Gradient Algorithm
Input: parameterized policy <--1-; 0)
Initialization: policy parameter 0 = Oo. and the Lagrangian parameter À = Ao
for i = 0, 1, 2....... do
for j = 2...... do
Generate N trajectories { by starting at zo and following the policy 0,. end for
0 Update:
0.+1 0s 02.. N
Vo log lo (C(Es)) A.D(E..))
A+11= Ta Ax Tx
(
( do + I D(GI.))
X Update:
end for
==1
where the likelihood gradient is
T
Vo Po() =Vo
log P(Zx+1lZE, ax) + log No (ax(<x))) + log 1 = 20}
A
Vo log no (ax|2x)
Voza (an((a))
TO (ax
k=0
In Algorithm 1, D is a projection operator to [0, Amax]. i.e., xx = arg min Aej,, || - X11 which ensures the convergence of the algorithm. Recall from Assumption 3 that the step-size schedules satisfy the standard conditions for stochastic approximation algorithms, and ensure that the anprrnn
policy parameter 9 update is on the fast time-scale {a2,z). and the Lagrange multiplier À update on the slow time-scale (a1.:)- This results in two time-scale stochastic approximation algorithm that has been shown to converge to a (local) saddle point of the objective function L(O, A). This convergence proof makes use of standard results in 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 PG, the unit of observation is 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, propose two actor-critic algorithms that use value function approximation parameters incrementally (after each state-action transition). We present two actor-critic algorithms for optimizing (11). These algorithms are still based on the above gradient estimates. Algorithm 2 contains the pseudo-code of these algorithms. The projection operator I A is necessary ensure the convergence of the algorithms. Recall from Assumption 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 {as..:} the policy update {a2..) is on the intermediate timescale, and finally the Lagrange multiplier update is on the slowest time-scale {a1 This results in three time-scale stochastic approximation algorithms.
the gradient estimates and update the
Using the PG theorem from (Sutton et al., 2000), one can show that
= VoVo(a))
Σ no (2, alzo) V log (a(a)) Qo(
(20)
where μe is the discounted visiting distribution and Qo the action-valle function of policy 9. We can show that - V log To (a)| 66 is unbiased estimate of V VoL A), where
8 cx (x), ax) + 7 Vo Vo()))
is the temporal-differene -ifferreece (TD) error, and Ve is an estimator of the value function Vg.
Traditionally, for convergence guarantees in actor-critic algorithms, the critic uses linear approxima- tion for the value function Vo(x) ~ T (xx)= = (z), where the feature vector vi(-) belongs to low-dimensional space R*2, The linear approximation Vo belongs to low-dimensional subspace
13

---

Under review as a conference paper at ICLR 2020
Algorithm 2 Lagrangian Actor-Critic Algorithm
Input: Parameterized policy x--1::0 0) value function feature vector d(-)
Initialization: policy parameters 0 Bo; Lagrangian parameter λo; value function weight while TRUE do for 0, 1, do Sample as (r(-aaa:e)) CA2 (I*, ax) o(zx, as) + Axd(ox); a=+1 P(-|xe;
// AC Algorithm:
TD Error:
(g(4)) cx2 (Tn, ax) + Vo, (ox+1) (on
(14)
Critic Update: uk+1 = es (=(A)) (vu))
(15)
Update:
0x+1 = O₂ (k)) Vo log To (as) 6x(wx)/1 -7
(16)
Update:
AR+1 I (Ae (x( do N
D(G
(17)
NAC Algorithm:
W6++ (1 (ak log To ta (Vo a log (as (xx (x)))
Critic Update:
wk
+ (a(K)o (ex) Vo (aa
(18)
I Update:
Bct1 02 C2 (k) // -Y
(19)
Other Updates:
Follow from Eqs. 14, 15, and 17.
end for end while
Sy { (oole R where V is short-hand notation for the set of features, i.e., (() & (x). Recently with the advances in deep neural networks, it has become increasingly popular to model the critic with deep neural network, based on the objective function of minimizing the MSE of Bellman residual w.r.t. Vo or Qo (Mnih et al., 2013).
14

---

Under review as a conference paper at ICLR 2020
B THE LYAPUNOV APPROACH TO SOLVE CMDPS
In this section, revisit the Lyapunov approach to solving CMDPs that was 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 baseline feasible policy of (I), TB; i.c. Tg satisfies Dx (2o) I do. We define set of Lyapunov functions w.r.t initial state 26 E X and constraint threshold dg as
LB (To, do)==4 {L: X + Rgo (L) Vx
X; L(zo) S do).
and call the constraints in this feasibility set the Lyapunov constraints. For any arbitrary Lyapunov function I. E Lrg (ro. do), we denote by
FL(z) = (=(+)=) E A :TTra S {L(z)}
the set of L-induced Markov stationary policies. Since x. is a contraction mapping (Bertsekas, 2005), any L-induced policy π has the property (x)x) = lim T (4]] s L(x), Vo E X. Together with the property that (xxo) S do. they imply that any L-induced policy is feasible policy of (1). However, in general, the set FL( does not necessarily contain optimal policy of (1), and thus, necessary design a Lyapunov function (W.I.t. baseline policy TB) that provides this guarantee. In other words, the main goal is to construct a I Lyapunov function I. E L (x0 do) such that
(21) Chow et al. (Chow et al., 2018) show in their Theorem that 1) without loss of optimality, the Lyapunov function can be expressed as
L(x) > T Ta [L]()))
Maa)) do-
Lx(x): = E
(d(a,) + e((x)) T
1=
where e(x) > 0 is some auxiliary constraint cost uniformly upper-bounded by e" (z) == 2Dmax (=)]
and 2) the baseline policy म satisfies the condition
max (x) S Diaxx min { (1 (1- do D'n (zo) ZEX
Dmax (1 -1
Daax
Dmax (1 (1-7)2
where D = max max, (xr)) the maximum constraint cost, then the I Lyapunov function candidate I.-- also satisfies the properties of (21), and thus, its induced feasible policy set FL,, contains optimal policy. Furthermore, suppose that the distance between the baseline and optimal policies can be estimated efficiently. Using the set of L.- -induced feasible policies and noting that the safe Bellman operator [=] = min (x) TT,e. (V(x) is monotonic and contractive, one can show that (x) = V(z), Vr E X. has a unique fixed point V', such that V (ap) solution of (I) and an optimal policy can be constructed via greedification, i.e., n" (-|2x) arg min (a) [V (z)). This shows that under the above assumption, (I) can be solved using standard dynamic programming (DP) algorithms. While this result connects CMDP with Bellman's principle of optimality, verifying whether π satisfies this assumption is challenging when good estimate of Drv (x" (|тн) is not available. To address this issue, Chow et al. (Chow al., 2018) propose to approximate ex with an auxiliary constraint cost e, which is the largest auxiliary cost satisfying the Lyapunov condition Lz(x) 2 (z))(x),, Vo E X, and the safery condition Tæ(xo) S dg- The intuition here is that the larger ?, the larger the set of policies Ft.- Thus, by choosing the largest such auxiliary cost, we hope to have a better chance of including the optimal policy n² in the set of feasible policies. Specifically, ē is computed by solving the following linear program (LP):
Σe(a) <(xx) : d (2o) 2 1(xo)" (1- (1-7(P(d (x,, 2xEE j. (22)
E' arg max R2 Tx
where (22) represents a one-hot vector in which the non-zero element is located at x zo. When TB is a feasible policy, this problem has non-empty solution. Furthermore, according to the derivations in (Chow et al., 2018), the maximizer of (22) has the following form:
(do
Dz (2o) 1(x = =)
{()) E Σi 1=1 7
2 0,
(1a = 2
xo. TB
15

---

Under review as a conference paper at ICLR 2020
Algorithm 3 Safe Policy Iteration (SPI)
Input: Initial feasible policy
for k: = 0, 1. ... do
Ta, evaluate the Lyapunov function Leg, where én is solution of (22) Step I: Evaluate the cost value function Vay (a: Cay (a): Then update the policy by solving the following
Step 0: With
problem: (+ argmin==J (x) Tr, (V,, Kra, (2), Vo E X'
end for
Return Final policy me
where I E arg m E E(r) to be a constant function, the maximizer given by
[Ei 7'1{2z = x} To, TB]. They also show that by further restricting
7(x) (1 7) (do Dzy((D)) Va X.
Using the construction of the Lyapunov function Lz, (Chow et al., 2018) propose the safe policy itera- tion (SPI) algorithm (sce Algorithm 3) in which the Lyapunov function is updated via bootstrapping, i... at each iteration Lę recomputed using (22) w.r.t. the current baseline policy, At each iteration k, this algorithm has the following properties: 1) Consistent Feasibility, i.c., if the current policy Th is feasible, then T is also feasible; 2) Monotonic Policy Improvement, i.e., CrA+1 (x) S. Cr, (x) for any x E X: and 3) Asymptotic Convergence. Despite all these nice properties, SPI is still value-function-base
algorithm, and thus, it is not straightforward to use it in continuous action problems. The main reason is that the greedification step becomes optimization problem over the continuous set of actions that not necessarily easy solve. Section 3, 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 combinations of DDPG or PPO (or any other on-policy or off-policy policy optimization algorithm) with 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.c., the new policy is selected from a restricted set of safe policies defined by the Lyapunov function of the current policy.
16

---

Under review as a conference paper at ICLR 2020
C TECHNICAL DETAILS OF THE SAFE POLICY GRADIENT ALGORITHMS
In this section, we first provide the details of the derivation of the 0 0-projection and a-projection procedures described in Section and then provide the pseudo-codes of our safe PG algorithms.
C.I DERIVATION OF 8 P-POJECCION IN LYAPUNOV-BANE BASED SAFE PG
To derive our 0-projection algorithms, we first consider the original Lyapunov constraint in (3) that is given by
J.e. (Ta(a|z) <n(aax)) Qi. (z, a) da S E(z), Vx E X. aaeA
where the baseline policy is parameterized w.r.t. 0 = 0B, at any arbitrary x E X, the term Ea-ar [Qt.g (2, a)] = SaeA ma(a|z) Qi..g (2, a) da on left-hand-side the above inequality can be written as
Toy. Using the first-order Taylor series expansion
0B), Vo awaso [Qrng (x. l0=0z +0(11000813) Eawsto [QLog (z, a)] = Fawxeg [QLng (s, a). 00)0),
which implies that
QLe (z, a) da ((0 (0-0g)) VoEann (Log (I, le=0a +0110-0=11) 0B). Note that the objective function of the constrained minimization problem in (4) contains a regulariza- tion term: {(00 0B), DiD (0, (0,0B) 10-02 (0-00) (000)) that controls the distance |10 0B| to be
/ (Te(a)=)-TB
JaEA
small. For most practical purposes, here one assume the higher-order term O(110 03 be
much smaller than the first-order term (0 (0-0))). VolEa~<o [Q (ar, a)] 10=0,, Therefore, one can approximate the original Lyapunov constraint in (3) with the following constraint:
(0 BB), (B)) VgEa (QLon (x, a)] (0=0n) S 7(x), Va X.
Furthermore, following the same line of arguments used in TRPO (to transform the max DKL constraint to average DKI. constraint, Eq. 12 in (Schulman al., 2015a)), more numerically stable way is to approximate the Lyapunov constraint using the average constraint surrogate, i.e.,
M
(10 00))
0B).
V VoEarno [QLon (I,, a)] 10=00)
1 M
E(x;).
M
Now consider the special case when auxiliary constraint surrogate is chosen as a constant, i.e.. = (1 7) (do DaH,, (Io)). The justification of such choice comes from analyzing the solution of optimization problem (22). Then, one can write the Lyapunov action-value function Qieg (x, a)
Qtag (z, E Σ dd(()) To z, ag
ē 1 1-7
X, the gradient term Since the second term is independent of 0, for any state x VolEawto [QLog (z) can be simplified
VoEanno [QLo (z, a)]
Te(a(x) Ve log (all)) Qwo, (I, a)da = VoEanno [Qwa, (z, a)],
where Wo,, (x) T. n (xx) and Qw (z. a) d(x) + 7 E. P(='Iz, a) (x') the
constraint value function and constraint state-action value function, respectively. The second equality based on the standard log- likelihood gradient property PG algorithms (Sutton al., 2000).
Collectively, one can then re-write the Lyapunov average constraint surrogate as
M
(00 0z),
VolaNao [Qwag (I:, a]] le=on) ST.
M
where ē is the auxiliary constraint cost defined specifically by the Lyapunov- approach, to guarantee constraint satisfaction. By expanding the auxiliary constraint cost on the right-hane hand-side, the above constraint is equivalent to the constraint used in CPO, i.c..
M
Drog (xo) + 1 - ((0 -0B), M
VoEanta (o,, a) bo=on> S do.
17

---

Under review as a conference paper at ICLR 2020
C.2 DERIVATIONS OF a-PROJECTION IN LYAPUNOV-BASER SAFE PG
For any arbitrary state x E X, consider the following constraint in the safety-layer projection problem given in (6);
Quap (zr, a) Quun n (z, [T)))) S <((x).
Using first-order Taylor series expansion of the Lyapunov state-action value function Q2,g (x, a) w.r.t. action a = BB (z), , the Lyapunov value function QL.g (x, a) can be re-written as
Qkn, (a, a) = Qin (z, (T())) + (C-TT(()) gLan (x) + O(Ia (T(2))]²)
Note that the objective function of the action-projection problem in (7) contains regularization term n(x) laa - n (2) that controls the distance ||a - xx))]] to be small. For most practical purposes, here one can assume the higher-order term O( (x)) to be much smaller than the first-order term (a (x)) 9L.n (z). Therefore, one can approximate the original oetion-based
Lyapunov constraint in (6) with the constraint (B-)((x)) 9L-2 (x) SZ(x) that is the constraint in (7). Similar to the analysis of the 0-projection approach, the auxiliary cost is state-independent, the action-gre grrionggradiet term ILnR (x) is equal to the gradient of the constraint action-value function VaQwe, (xr, a) (=))a(()) where Qwa,, is the state-action constraint value function w.r.t. the baseline policy. The rest of the proof follows the results from Proposition in (Dalal et al., 2018). This completes the derivations of the a-projection approach.
C.3 PSEUDO-CODER OF OUR SAFE PG ALGORITHMS
Algorithms and 5 contain the pseudo-code our safe Lyapunov-based policy gradient (PG) algorithms with 4-projection and a-projection, respectively.
C.4 PRACTICAL IMPLEMENTATION OF OUR SAFE PG ALGORIHTS
Due to function approximation errors, even with the Lyapunov constraints, in practice safe PG algo- rithm may take bad step and produce an infeasible policy update and cannot automatically recover from such a bad step. To address this issue, similar to (Achiam et al., 2017), we propose the following safeguard policy update rule to decrease the constraint cost: 0x+1 02 Ossg.k Vo (0=))==0.- where O'sg.k is the learning rate for the safeguard update. If O'sg.h & >> Og (learning rate of PG), then with the safeguard update, will quickly recover from the bad step. however, it might be overly conservative. This approach is principled because as soon as TT, is unsafc/infcasiblc w.r.t. the CMDP constraints, the algorithm uses a limiting search direction. One directly extend this safeguard update to the multiple-constraie 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 dg, one may pose the constraint based on (1- 5), where E (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 of the environment, which makes the safe PG algorithms more complicated.
18

---

Under review as a conference paper at ICLR 2020
Algorithm 4 Lyyauuov-baseed Safe PG with 0-projection (SDDPG and SPPO)
Input: Initial feasible policy
for 2.. do
Step With my = # generate N trajectories {5y.a }5=1 steps by starting at Jo and following the
policy 0g
Step 1:
Using the trajectories (E,,* ) estimate the critic (2 a.) and the constraint critic QD (xr, a); For DDPG, these functions are trained by minimizing the MSE of Bellman residual, and one also use off- samples from replay butfer (Schaul al., 2015);
For PPO these functions can be estimated by the generalized advantage function technique from Schulman et al. (2015h)
Step 2: Based on the closed form solution of QP problem with an LP constraint in Section 10.2 of Achiam al. (2017), calculate X with the following formula:
- - (VoQa(a,a) ) H(O.) lo=0c (-
(VoQD.O @) lo-0,) H(0x)- (oo.)_ 10-9x
where
VoQo(z, = Σ
Vo Volomo(aaz)Q00tz..)
2,0E ISISN t=0
VaQD,a(E,a) =
Σ
V Volgmmo(l)2)uuaa
S.
is the adaptive penalty weight of the D regularizer, and H(O+) Dx lo-0, the Hessian of this term Step 3: Update the policy parameter by following the objective gradient; For DDPG
02+1 < -x- NT
Σ
VaTa(E) la=ox
(x, l=so (x)
SiSN
For PPO,
Oc+1 +- Or
akk
(IT(0)))
Σ
Σn' Vo log (o(3)))15)))) lo=a.
NBk
(Q,, a5.0) XaQD.o (z,))
Step 4: At any given state x C X, compute the feasible action probability (x) via action projec- tion in the safety layer, that takes inputs (aQu(a,4) = V.QD.o (x. a) and e(x) = =(1 7) QD. (Zp, Te (xo))), ), for any a E A. end for
Return Final policy n.,..
D EXPERIMENTAL SETUP IN MUJoCo TASKS
Our experiments are performed on sagete-augmented versions of standard MuloCo domains (Todorov et al., 2012).
The agent is a the standard HalfCheetah (a 2-legged simulated robot rewarded for running 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.c., constraint cost is thus ||[0| 1]. Episodes are of length 200. The constraint threshold is 50.
HalfCheetah-Safe.
Point Circle. This environment is taken from (Achiam al., 2017). The agent is point mass (controlled via pivot). The agent is initialized (0, 0) and rewarded for moving counter-clockwise along circle of radius according to reward -da-y-dy- for position x;, and velocity
=+iv=-=g' -22=0=--51
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.
19

---

Under review as a conference paper at ICLR 2020
Algorithm 5 Lyapunov-based Safe PG (SDDPG and SPPO) with a-projection
Input: Initial feasible policy
for k 1. do
Step With ma = : generate N trajectories (5y. }8=1 steps by starting at Jo and following the
policy 0g
Step 1:
Using the trajectories {E,,* )= estimate the critic (2 o.) and the constraint critic QD (xx, a); For DDPG, these functions are trained by minimizing the MSE of Bellman residual, and one 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. (2015h)
Step 2: Update the policy parameter by following the objective gradient;
For DDPG
8x41 + 02 at N.T
Σ
VoTO(x) la-0e -Vo (2,, la=mo,
For PPO.
Oct1 <- 0s
Oh (H().))
Σ
Σ
7' vo log (og l0=0z Qu (1554,
NB.
where B& is the adaptive penalty weight of the Dx [ regularizer, and H(xx) (T le=e, is the Hessian of this term Step 3: At any given state E X, compute the feasible action probability (²(x) via action projec- tion in the safety layer, that takes inputs (xQ VaQD.e, (2, and <(x) (1 7) @p.6, (zo, Tes (To))), for any A. end for
Return Final policy Tl2+
Point Gather, This environment is taken from (Achiam et al., 2017). The agent point mass (controlled via pivot) and the environment includes randomly positioned apples (2 apples) and bombs (8 bombs). The agent given reward of 10 for each apple collected and a penalty of 10 for each bomb. The safety constraint is defined as the number of bombs collected during the episode. Episodes are of length 15. The constraint threshold is 4 for DDPG and 2 for PPO.
Ant Gather. This environment 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 receives reward of 10 for each apple collected, a penalty of 20 for each bomb collected, and a penalty of 20 the episode terminates prematurely (hecause the Ant falls). Episodes are of length at most 500. The constraint threshold is 10 and 5 for DDPG and PPO, respectively.
Figure shows the visualization of the above domains used in experiments.
HalfCheetah-Safe
Point-Circle
Ant-Gather
Point-Gather
Figure 7: The Robot Locomotion Control Tasks
In these experiments, there are three different agents: (1) a point-mass (X' C RD. AC R²); an ant quadruped robot (X' C R A C RR*); and (3) half-cheetah (X' C R C R$). For all experiments, we use two neural networks with two hidden layers of size (100, 50) and ReLU activation 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 activation to model the critic and constraint critic. To build low variance sample gradient estimate, we GAE-A (Schulman al., 2015bb to estimate
20

---

Under review as a conference paper at ICLR 2020
25-
6-
200
20-
30
20
(a) AnttGGater, Return
(b) Point-Circle, Return
(c) Ant- Gather, Constraint
(d) Point Carete Constraint
Figure 8: DDPG (red), DDPG-Lagrangian (cyan), SDDPG (blue), SDDPG a-projection (green) Ant-Gather and Point-Circle. Ours SDDPG and SDDPG a-projection algorithms perform stable and safe learning. although the dynamics and cost functions unknown, control actions continuous, and deep function approximation is used. Unit of x-axis is in thousands of episodes. Shaded areas represent the 1-SD confidence intervals (over 10 random seeds). The dashed purple linc in the two right figures represents the constraint limit.
33-
300
30
0
(a) Ant-Gather, Retum
(b) Point-Circle, Retum
(c) Ant-Gather, Constraint
(d) Point-Cireke Constraint
Figure 9: PPO (red), PPO-Lagrangian (cyan), SPPO (blue), SPPO a-projection (green) on Ant-Gather and Point-Circle. SPPO a-projection performs stable and safe learning, when the dynamics and cost functions are unknown, control actions are contimuous, and deep function approximation is used.
the advantage and constraint advantage functions, with hyper- hhper--prannnn parameter À E (0, 1) optimized by grid-search.
On top GAE-X, in all experiments and for each algorithm (SDDPG, SPPO, SDDPG a a-projection, SPPO a-projection, CPO, Lagrangian, and the unconstrained PG counterparts), we systematically explored different parameter settings by doing grid-search over the following factors: (i) learning rates the actor-critic algorithm, (ii) batch size, (iii) regularization parameters the policy relative entropy term, (iv) with-or-withen natural policy gradient updates, (v) with-or-without the emergency safeguard PG updates (see Appendix C.4 for more details). Although each algorithm might have different parameter setting that leads to the optimal performance training, the results reported here are the best ones for each algorithm, chosen by the same criteria (which is based on the value of return plus certain degree of constraint satisfaction). To account for the variability during training, in each learning curve, 1-SD confidence interval is also computed over 10 separate random runs (under the same parameter setting).
D.1 MORE EXPLANATIONS ON MUJOCO RESULTS
In all numerical experiments and for each algorithm (SPPO 0-projection, SDDPG 6-projection, SPPO d-projection, SDDPG a-projection, CPO, Lagrangian, and the unconstrained PG counterparts), we systematically explored various hyper-paranee
settings by doing grid-search over the following factors: (i) learning rates in the actor-critic algorithm, (ii) batch size, (iii) regularization parameters of the policy relative entropy term, (iv) with-or-without natural policy gradient updates, (v) with-or- without the emergency safeguard PG updates (see Appendix C.4 for more details). Although each algorithm might have different parameter setting that leads to the optimal training performance, the results reported in the paper are the best ones for each algorithm, chosen by the same criteria (which is based on value of return + certain degree of constraint satisfaction).
In our experiments, we compare the two classes of safe RI algorithms, one derived from 0 d-projection (constrained policy optimization) and one from the a-projection (safety layer), with the unconstrained and Lagrangian baselines in four problems: PointGather, AntGather, PointCircle, and HalfCheetahh Safe. We perform these experiments with both off-policy (DDPG) and on-policy (PPO) versions of the algorithms.
In PointCircle DDPG, although the Lagrangian algorithm significantly outperforms the safe RL algorithms in terms of return, it violates the constraint more often. The only experiment in which Lagrangian performs similarly to the safe algorithms in terms of both return and constraint violation is PointCircle PPO. In all other experiments that performed in the SalfCheetahSafe, PointGather and
21

---

Under review as a conference paper at ICLR 2020
AntGather domains, either (i) the policy learned by Lagrangian has significantly lower performance than that learned by one of the safe algorithms (see HalfCheetahSafe DDPG, PointGather DDPG, AntGather DDPG), or (ii) the Lagrangian method violates the constraint during training, while the safe algorithms do not (see HalfCheetahSafe PPO, PointGather PPO, AntGather PPO). This clearly illustrates the effectiveness of our Lyapunov-based safe RL algorithms, when compared to Lagrangian method.
22

---

Under review as a conference paper at ICLR 2020
E EXPERIMENTAL SETUP IN THE ROBOT NAVIGATION PROBLEM
Mapless navigation task is continuous control task with a goal of navigating a robot any arbitrary goal position collision-fie free and without memory of the workspace topology. The goal is usually within 5 10 meters from the robot agent, but it is not visible to the agent before the task starts, due to both limited sensor range and the presence of obstacles that block clear line of sight. The agent's observations, * (g, 9. I) E IR6i consists of the relative goal position, the relative goal velocity, and the Lidar measurements. Relative goal position, g, is the relative polar coordinates between the goal position and the current robot pose, and 9 the time derivative of g. which indicates the speed of the robot navigating to the goal. This information is available from the robot's 's localization sensors. Vector L is the noisy Lidar input (Fig. 3a), which measures the nearest obstacle in direction within a 220 field of view split in 64 bins, up to meters in depth. The action is given by a E R?, which is linear and angular velocity vector at the robot's ' center of the mass. The transition probability P: A X' captures the noisy differential drive robot dynamics. Without knowing the full non- linear system dynamics, we here assume knowledge of a simplified blackbox kinematics simulator operating at 5Hz in which Gaussian noise, (0, 0.1), is added to both the observations and actions in order to model the noise in sensing, dynamics, and action actuations in real-world. The objective of the P2P task to navigate the robot to reach within 30 centimeters from any real-time goal. While the dynamics of this system is simpler than that of HalfCheetah. But unlike the MuJoCo tasks where the underlying dynamics are deterministic, in this robot experiment the sensor, localization, and dynamics noise paired with partial world observations and unexpected obstacles make this safe RL much more challenging. More descriptions about the indoor robot navigation problem and its implementation details can be found in Section 3 and 4 of (Chiang et al., 2019). Fetch robot weights 150 kilograms, and reaches maximum speed of km/h making the collision force safety paramount.
Here the CMDP non-discounting and has a finite-horian horizon of T 100. We reward the agent for reaching the goal, which translates the relative distance to goal. To measure the impact energy of obstacle collisions, we impose an immediate constraint cost of d(xx a) = |اوا| 1 [[[4]] S Tmmpaca/ where Timpact is the impact radius w.r.t. the Lidar depth signal, to account for the speed during collision, with a constraint threshold do that characterizes the agent's 's maximum tolerable collision impact energy any objects. (Here the total impact energy is proportional to the robot's speed during any collisions.) Under this CMDP framework (Fig. 3b), the main goal is to train policy x² that drives the robot along the shortest path to the goal and to limit the average impact energy of obstacle collisions. Furthermore, due to limited data any intermediate point-to-point policy is deployed on the robot to collect more samples for further training, therefore guaranteeing safety during training is critical this application.
immediate cost of c(æ, a) || which measures
Training, by 18m
(b) Bailding 60 by
Figure 10: (a) Training and (b) evaluation environments, generated from real office building plans. The evaluation environment is an order of magnitude bigger.
23

---

Under review as a conference paper at ICLR 2020
tf tnt lond
wwared Lead
(b) SDDPG (a-pmj.) Figure 11: Navigation routes of policies similar setup (a) and (b). Log of on-robot experiments (c).
(a) Lagrangian policy
(c) SDDPG (a-proj)) rohot
24


Reviews:
[{"review_id": "S1lJDVGRtB", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper presents a technique for extending existing reinforcement learning algorithms to ensure safety of generated trajectories in terms of not violating given constraints.\n\nI have very little knowledge of this area and as a result was not able to evaluate the paper thoroughly. However, the problem addressed is certainly a very important one and based on my high-level understanding of the concepts involved the approach seems sensible. The experiments are clear and well designed, showing the trade-off between performance and safety.", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}, {"review_id": "HkgUCdPEcB", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This is a very complete submission. There is a novel analysis,\nsimulations, as well as some results on real data. The authors propose\nLyapunov-based safe RL algorithms that can handle\nproblems with large or infinite action spaces, and return safe\npolicies both during training and at\nconvergence. As far as I can tell the approach is novel, makes sense,\nand requires a lot of technical innovations. I was impressed with the\nmethod and the analysis behind the method. The incorporation of the\nLyapunov idea from control theory makes a great deal of sense in this\napplication. However, it is not trivial to get from using this tool to\na working method.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "BJxv60VsYH", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "\nSummary:\n\nAuthors propose ideas to perform safe RL in continuous actions domain with modifications to Policy Gradient (PG)  algorithms via either constraining the policy parameters or constraining the actions selected by PG with a surrogate/augmented state dependent objective. The paper is well motivated and the experiments (although I have some reservations about the setup) demonstrate efficacy of the proposed method.  \n\nReview:\n--> Introduction\nI do not agree with the statement that value function based algorithms are restricted to discrete action domains, especially when you rely on  “ignoring function approximation errors” for some of your claims. \n\nAgain in switching from value function to PG is true for traditional RL/Control theory but this is not valid here. ( your methods rely on Q(s, a) which is action-value function, or the constraint in equation 3 is integral of Q over all actions which would be value-function in traditional definition )\nNote: this is explained very well towards the end in the Appendix B, but this is a review of the paper and not Appendix B or C. \n\n\n--> Section 2\nsection 2.3 I would strongly advise the authors to rewrite this, this section reads like it was copied as is from the reference [Chow et al 2018].  especially the way Lyapunov function is defined. And the language and arguments are almost same. Some sentences cite the reference but conclusions drawn on these are not cited, are you claiming that these conclusions are original from this paper ?\n\nIt is not clear to me how the feasibility of initial pi_0 is ensured ? Did I miss this somewhere ?\n\n\n→ Section 3\n\nSection 3 is pleasant to read and very easy to understand, however, same cannot be said of the\nsection 3.1. I had to spend significant time reading 3.1 and I am still not sure I have understood it very well. \n\nExperiments:\n\nI don’t think halfCheetah-Safe is actually actually an useful experiment, Limiting the joint torques is perfectly understandable, just limiting speed and getting smooth motion could just be an artifact of the simulation environment. Are both constraints applied simultaneously (torque and speed) ? It is unclear from the text. \n\nI am not sure CPO without linesearch is actually a fair comparison. Line search may actually deem of the actions unsafe and therefore I would presume original CPO do be less prone to constraint violation than the proposed modification in your experiments. Again PPO is more heuristic than TRPO which makes it hard to compare like for like. PPO might give higher rewards but constraint violations may increase as well. An important point for Safe-RL I feel.\n\nFigure 6 \nCan you be more specific as what the figure 6 is showing ? Constraint ? is this constraint violation count? or cumulative sum of constraint slack over the whole trajectory ?\n \n\nNot part of assessment :\n\n\nUnclear Statements:\n\nPage 7, DDPG Vs PPO: explain clearly what you mean by  “covariate shift” or remove the statement altogether. \n\nPage 7, section 5 second paragraph, “The actions are the linear …. center of mass” I couldn’t understand this ? What do you mean by actions are velocity ?\n\n\n\nMinor points (Language, Typos):\n\npage 3, last paragraph,  Chow et al. is repeated, I can see why this happens there but suggest editing to avoid this. [This is also in intro paragraph, there it is just a typo and should be rectified]\n\nFigure 6: Captions labels are incorrect.\n\n\n\n\n\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper is about learning policies in RL while ensuring safety (avoid constraint violations) during training and testing. 

For this meta review, I ignore Reviewer #3 because that review is useless. The discussion between the authors and Reviewer #1 was useful.

Overall, the paper introduces an interesting idea, and the wider context (safe learning) is very relevant. However, I also have some concerns.
One of my biggest concerns is that the method proposed here relies heavily on linearizations to deal with nonlinearities. However, the fact that this leads to approximation errors is not being acknowledged much. There are also small things, such as the (average) KL divergence between parameters, which makes no sense to me because the parameters don't have distributions (section 3.1). 

In terms of experiments, I appreciate that the authors tested the proposed method on multiple environments. The results, however, show that safety cannot be guaranteed. For example, in Figure 1(c), SDDPG clearly violates the constraints. The figures are also misleading because they show the summary statistics of the trajectories (mean and standard deviation). If we were to look at individual trajectories, we would find trajectories that violate the constraints. This fact is brushed under the carpet in the evaluation, and the paper even claims that "our algorithms quickly stabilize the constraint cost below the threshold". This may be true on average, but not for all trajectories. A more careful analysis and a more honest discussion would have been useful. In the robotics experiment, I would like to understand why we allow for any collisions. Why can't we set $d_0=0$, thereby disallowing for collisions. The threshold in the paper looks pretty arbitrary.  Again, the paper states that  "Figure 4a and Figure 4b show that the Lyapunov-based PG algorithms have higher success rates". This is a pretty optimistic interpretation of the figure given the size of the error bars. 

There are some points in the conclusion, I also disagree with:
1) "achieve safe learning": Given that some trajectories violate the constraints, "safe" is maybe a bit of an overstatement
2) "better data efficiency": compared to what?
3) "scalable to tackle real-world problems": I disagree with this one as well because for all experiments you will need to run an excessive number of trials, which will not be feasible on a real-world system (assuming we are talking about robots).

Overall, I think the paper has some potential, but it needs some more careful theoretical analysis (e.g., effect of linearization errors) and some better empirical analysis. 

Additionally, given that the paper is at around 9 pages (including the figures in the appendix, which the main paper cites), we are supposed to have higher standards on acceptance than an 8-pages paper.

Therefore, I recommend to reject this paper.
Decision: Reject