Constrained Markov Decision Processes via Backward Value Functions
Authors: Harsh Satija
Philip Amortila
Joelle Pineau
Venue:  (2020)
Keywords: Reinforcement Learning
Constrained Markov Decision Processes
Deep Reinforcement Learning

Abstract: Although Reinforcement Learning (RL) algorithms have found tremendous success in simulated domains, they often cannot directly be applied to physical systems, especially in cases where there are hard constraints to satisfy (e.g. on safety or resources). In standard RL, the agent is incentivized to explore any behavior as long as it maximizes rewards, but in the real world undesired behavior can damage either the system or the agent in a way that breaks the learning process itself. In this work, we model the problem of learning with constraints as a Constrained Markov Decision Process, and provide a new on-policy formulation for solving it. A key contribution of our approach is to translate cumulative cost constraints into state-based constraints. Through this, we define a safe policy improvement method which maximizes returns while ensuring that the constraints are satisfied at every step. We provide theoretical guarantees under which the agent converges while ensuring safety over the course of training. We also highlight computational advantages of this approach. The effectiveness of our approach is demonstrated on safe navigation tasks and in safety-constrained versions of MuJoCo environments, with deep neural networks.

Under review as a conference paper at ICLR 2020
CONSTRAINED MARKOV DECISION PROCESSES VIA BACKWARD VALUE FUNCTIONS
Anonymous authors Paper under double-blind review
ABSTRACT
Although Reinforcement Learning (RL) algorithms have found tremendous success in simulated domains, they often cannot directly be applied to physical systems, especially in cases where there are hard constraints to satisfy (c.g. on safety or resources). In standard RI., the agent is incentivized to explore any behavior as long as it maximizes rewards, but in the real world undesired behavior can damage either the system or the agent in a way that breaks the learning process itself. In this work, we model the problem of learning with constraints as Constrained Markov Decision Process, and provide a new on on-policy formulation for solving it. A key contribution of our approach is to translate cumulative cost constraints into state-based constraints. Through this, we define a safe policy improvement method which maximizes returns while ensuring that the constraints at every step. We provide theoretical guarantees under which the agent converges while ensuring safety over the course of training. We also highlight computational ad vantages of this approach. The effectiveness of our approach is demonstrated on safe navigation tasks and in safety- cansty-constrained versions of MuJoCo environments, with deep neural networks.
satisfied
INTRODUCTION
Reinforcement Learning (RL) provides a sound decision-theoreti framework to optimize the behavior of learning agents in an interactive setting (Sutton & Barto, 2018). Recently. the field of RL has found success in many high-dimensional domains, like video games, Go, robot locomotion and navigation. However, most of the success of RI algorithms has been limited to simulators, where the learning algorithm has the ability to reset the simulator. In the physical world, an agent will need to avoid harmful behavior (e.g. damaging the environment or the agent's hardware) while learning to explore behaviors that maximize the reward.
few popular approaches for avoiding undesired behaviors for high-dimensional systems include soward-shaping (Moldovan & Abbeel, 2012), reachability preseervnn algorithms (Mitchell, 2003; Eysenbach et al., 2017), state-level surrogate constraint satisfaction algorithms (Dalal et al., 2018), risk-sensitive algorithms (Tamar al., 2013; Chow al., 2015) and apprenticeship learning (Abbeel & Ng, 2004). There also exists model-based Bayesian approaches that are focused on imposing the constraints via the dynamies (such as classifying parts of state space as unsafe) and then using model predictive control to incorporate the constraints in the policy optimization and planning (Turchetta al., 2016; Berkenkamp et al., 2017; Wachi al., 2018; Koller al., 2018). A natural way to model safety is via constraint satisfaction. A standard formulation for adding constraints to RL problems is the Constrained Markov Decision Process (CMDP) framework (Altman, 1999), wherein the environment is extended to also provide feedback on constraint costs. The agent must then attempt to maximize its expected return while also satisfying cumulative constraints.
A few algorithms have been proposed to solve CMDPs for high-dimensional domains with continuous action spaces- however they come with their own caveats. Reward Constrained Policy Optimization (Tessler et al., 2018) and Primal Dual Policy Optimization (Chow et al., 2015) do not guarantee constraint satisfaction during the learning procedure, only on the final policy. Constrained Policy Optimization (Achiam al., 2017) provides monotonie policy improvement but is computationally expensive due to requiring a backtracking line-search procedure and conjugate gradient algorithm for approximating the Fisher Information Matrix. Lyapunov-based Safe Policy Optimization (Chow

---

Under review as a conference paper at ICLR 2020
al., 2019) requires solving Linear Program (LP) at every step of policy evaluation, although they show that there exists heuristics which can be substituted for the LP at the expense of theoretical guarantees.
In this work, we propose an alternate formulation for solving CMDPs that transforms trajectory-level constraints into localized state-dependent constraints, through which safe policy improvement step can be defined. In our approach, we define a notion of Backward Value Functions, which act as an estimator of the expected cost collected by the agent so far and can be learned via standard RL bootstrap techniques. We provide conditions under which this new formulation is able to solve CMDPs without violating the constraints during the learning process. Our formulation allows us to define state-level constraints without explicitly solving a LP or the Dual problem at every iteration. Our method implemented as reduction to any model-free on-policy bootstrap based RI. algorithm, both for deterministic and stochastic policies, and discrete and continuous action spaces. We provide the empirical evidence of our approach with Deep RL. methods on various safety benchmarks, including 2D navigation grid worlds (Leike et al., 2017; Chow et al., 2018), and MuJoCo tasks (Achiam et al., 2017; Chow et al., 2019).
CONSTRAINED MARKOV DECISION PROCESSES
We write (Y) for the set of probability distributions on space Y. A Markov Decision Process (MDP) (Puterman, 2014) is a tuple (X, P, r, Tb), where X' is a set of states, AA is set of actions, r: X' x A + [0, RMAX] is a reward function, P X x (X) is a transition probability function, and Ho is a fixed starting state. For simplicity we assume deterministic reward function and starting state, but our results generalize.
A Constrained Markov Decision Process (CMDP) (Altman, 1999) is a MDP with additional con- straints that restrict the set of permissible policies for the MDP. Formally, a CMDP is a tuple (X, A, P, r, ro, d, do). where d X + [0. DMAx]] is the cost function' and do E I220 is the maxi- mum allowed cumulative cost. The set of feasible policies that satisfy the CMDP is the subset of
stationary policies IT == { X- - (AA) EE d(xx) To, π| S do)- We consider a finite time horizon T after which the episode terminates. The expected sum of rewards following policy
from an initial state is given by the value function V=(x)) = E r(z,, a;) T, 2:.. Analogously,
the expected sum of costs is given by the cost value function (z) E to= d(xx)) क., x] The
RL problem in the CMDP is find the feasible policy which maximizes expected returns from the initial state Ho. i.e.
π arg max V (200
An important point to note about CMDPs is that, in the original formulation, the cost function depends on immediate states but the constraint is cumulative and thus depends on the entire trajectory.
In the case of MDPs, where a model of the environment not known is not easily obtained, it is still possible for the agent to find the optimal policy using Temporal Difference (TD) methods (Sutton, 1988). Broadly, these methods update the estimates of the value functions via bootstraps of previous estimates on sampled transitions (we refer the reader to Sutton & Barto (2018) for more information). In the on- oo-policy setting. we alternate between estimating the state-action value function Q" for a given π and updating the policy to be greedy with respect to the value function.
3 SAFE POLICY ITERATION VIA BACKWARD VALUE FUNCTIONS
Our approach proposes to convert the trajectory-Ievel constraints of the CMDP into single-step state-wise constraints in such a way that satisfying the state-wise formulation will entail satisfying the original trajectory-level problem. The advantages of this approach are twofold: i) working with single-step state-wise constraints allows us to obtain analytical solutions to the optimization problem, and ii) the state-wise constraints can be defined via fottue-funttion-lie quantities and can thus be estimated with well-studied value-based methods. The state-wise constraints are defined via Backward Value Functions, in Section 3.2, and in Section 3.3 we provide a safe policy iteration procedure which satisfies said constraints (and thus the original problem).
Here the cost only depends on states and state-action pairs.
2

---

Under review as a conference paper at ICLR 2020
3.1 BACKWARD MARKOV CHAIN
Unlike in traditional RL, in the CMDP setting the agent needs to take into account the constraints which it has accumulated so far in order to plan accordingly for the future. Intuitively, the accumulated cost so far can be estimated via the cost value function VD running "backward in time". Before giving the details of our approach and formally introducing the Backward Value Functions, we review the main ideas, which are built upon the work of Morimura et al. (2010), who also considered time-reversed Markov chains but from the standpoint of estimating the gradient of the log stationary distribution; we extend these ideas to TD methods.
Assumption 3.1 (Stationarityy. The MDP is ergodic for any policy т. i... the Markov chain charac- terized by the transition probability D (11+1 Ea,eA P(1++1120 (a()))(())))) is irreducible and aperiodic.
Let M(T) denote the Markov chain characterized by transition probability pa p* (x++1( The above assumption implies that there exists unique stationary distribution 17" associated with n, such that it satisfies: 17" (x++1) = Em,x Pd (#141|24)n" (zz). We abuse the notation and denote pD
pT (Ie+1. 0x/24)) P(z++1 [rx (
According to Bayes' rule, the probability g( 11-12))) of previous state-action pair (It-1; Qt-1) leading to the current state xe is given by:
( a111) E. Eamied -
ar
From Assumption 3.1, have that Pr 01( Ex-ex Ea.-Ee a(I2-1, ax-1 (I)) as backward (or time-reversed) probability P (c--1,a-11172 and we have:
1)" ( 1x4-1),, and
a-11) = 1f (11). We denote the posterior
5" (0 P( 01 1)m² (x1-1) (at-2
(x1)
(T 101t,a11111-111 (xc-1)
(x+)
The forward Markov chain, characterized by the transition matrix P (I++1 (xx), runs forward in time,
i... it gives the probability of the next state in which the agent will end up. Analogously, backward
Markov chain is denoted by the transition matrix P (x2-1læz)) = Ea. IEa P (II- at-1 (z2), and describes the state and action the agent took to reach the current state.
Definition 3.1 (Backward Markov Chain). A backward Markov chain associated with M(T)) is denoted by (TT) and is characterized by the transition probability ""' (11))
3.2 BACKWARD VALUE FUNCTION
We define the Backward Value Function (BVF) to be value function running on the backward Markov chain (T). A BVF is the expected sum of returns or costs collected by the agent so far. We are mainly interested in maintaining estimates of the cumulative cost incurred at state in order to express the total constraint state-wise.
We note that, since every Markov chain M(T) is ergodic by Assumption 3.1, 1, the corresponding backward Markov chain B(x) also ergodic (Morimura et al., 2010, Prop. B.1). In particular, every policy reach the initial state via some path in the transition graph of the backward Markov chain. Thus, the backwards Markov chain are also finite-horizon for some TB. with To corresponding to the terminal state. We define a finite-horizon Backward Value Function for cost
Tw
(ox) B(T)
Σ
d(
Proposition 3.1 (Sampling). Samples from the forward Markov chain M(T) can be used directly to estimate the statistics of the backward Markov chain ((x)) ) (or the Backward Value Function). We
3

---

Under review as a conference paper at ICLR 2020
have:
K x)
K = (()))))
d( 22) (Ix-
(3)
B (T)
= (E)()))
(1re)
where (=) and E (x)
expectations the forward and backward chains respectively. The Equation (3) holds true even in the limit K -
The proof is given in Appendix B.1. Using the above proposition, we get an interchangeability property that removes the need to sample from the backward chain. We can use the traditional RL. setting and draw samples from the forward chain and still estimate the BVFs. Equation (2) can be written recursively as:
V D (z+) = E (x)
d(xx)) + (x)-))
In operator form, the above equation can also be written as:
T (TV) = E 2 (d(xz) + V ((a
(4)
Proposition 3.2 (Fixed point). For a policy т, the associated Backward Value Function vector, 1 V" for every vector V.an and V is the unique solution of the equation
satisfies lim
(
TV=
The proof given in Appendix B.2. The above proposition allows us to soundly extend the RI. methods based on Bellman operators for the estimation of BVFs.
3.3 SAFE POLICY IMPROVEMENT VIA BVF-BASED CONSTRAINTS
With the Backward Value Function framework, the trajectory-level optimization problem associated with a CMDP can be rewritten in mate-wise form. Recall that a feasible policy must satisfy the constraint:
[M(T)
Σ d(xx) xo
do.
Alternatively, for each timestep t E [0, T] of a trajectory:
E
Σ d(xRk
Fo,
+ E
d(xx) Ip. - E d(xx)) ao
S da.
Via the identities E d((r)))
To. m S Burwee (pr [V (xx)) and ElE d(xx) Zo. S Ezgwoe, (Pr)) [V (xx))(deriveed in Appendix C)2, we remark that the quantity the LHS is less than the expectation over k-step trajectories of (xx) + Vz((,) d(x,). In other words, for each I [),
T Σ
E EM
d(xx))
2
< (Per (D())) + Vz((x) - d(zz)) s do.
These are the state-wise constraints that should hold at each step in a given trajectory we refer them the value-based constraints. Satisfying the value-based constraints will automatically satisfy the given CMDP constraints.
28,, Dirac distribution æo, and 8z, (P*)t
a is the distribution of states at time
4

---

Under review as a conference paper at ICLR 2020
This formulation allows to introduce a policy improvement step, which maintains safe feasible policy at every iteration by using the previous estimates of the forward and backward value functions" The policy improvement step is defined by linear program, which performs greedy update with respect to the current state-action value function subject to the value-based constraints:
Th+11 (-12) = arg max (T([22)) Q (x.-)). -)),
(SPI)
TEll
s.t.
(F(-)Z)) QD (x, (x,
V (x) d(x) & do, VI E X.
Our first result is that the policies obtained by the policy improvement step will satisfy the safety constraints. We write -V for the total variation metric between distributions.
Theorem 3.1 (Consistent Feasibility). Assume that successive policies are updated sufficiently slowly, i.e. TV(T++1 (- (+1x)), mT (+())) dg-V (#o) 4 Then the policy iteration step given by (SPI) is 2DMAxT
consistently feasible, i.e. if Tı is feasible at 20 then so is T
It is also possible consider larger neighbourhoods for updates of successive policies, but at the cost of serrywere--easibilie For want of space, we present that result in Appendix D.
Next show that the policy iteration step given by (SPI) leads to monotonic improvement.
Theorem 3.2 (Policy Improvement). Let n. and Th++1 be successive policies generated by the policy iteration step of (SPI). Then V* (x) 2 V*a (x) Ve E X. In particular, the sequence of value functions / Tm In20 given by (SPI) monotonically converges.
Proofs for Theorems 3.1 and 3.2 are given in Appendix D. Finding the sub-optimality gap (if any) remains an interesting question left for future work.
PRACTICAL IMPLEMENTATION CONSIDERATIONS
4.1 DISCRETE ACTION SPACE
In discrete action spaces, the problem in (SPI) can be solved exactly a Linear Programming problem. It is possible to approximate its analytical solution by casting it into the corresponding catropy-regularia counterpart (Neu et al., 2017; Chow al., 2018). The details of the closed form solution can be found in Appendix E.
Furthermore, if we restrict the set of policies be deterministic, then it is possible to have an in-graph solution as well. The procedure then closely resembles the Action Elimination Procedure (Puterman, 2014, Chapter 6), where non-optimal actions are identified as being those which violate the constraints.
4.2 EXTENSION TO CONTINUOUS CONTROL
For MDPs with only state-dependent costs, Dalal et al. (2018) proposed the use of safety layers, constraint projection approach, that enables action correction at each step. At any given state, an unconstrained action is selected and is passed to the safety layer, which projects the action to the nearest action (in Euclidean norm) satisfying the necessary constraints. We extend this approach to stochastic policies to handle the corrections for the actions generated by stochastic policies. When the policy parameterized with Gaussian distribution, then the safety-layer projecting both the mean and deviaation vector to the constraint-satisfyimn hyper-plane" plane In most cases, the dtandard vector is kept fixed independent of the state (Kostrikov, 2018; Dhariwal et al., 2017), which allows us to formulate the problem as solving the following L2-projection of the mean of the Gaussian in Euclidean space. For yo (-; 0), at any given state X,
still be used by
IIn general, not possible to obtain expectation Er,-d,, (P+ [-] directly it may be intractable to compute may not have access to the true transition distributions of the model. Thus, we sample batch of transitions from the current policy and use them for the updates.
"This can be enforced, for example, by constraining iterates to a neighborhood D(r, m&) S 6. Mooe information about this claim he found in Appendix F.
5

---

Under review as a conference paper at ICLR 2020
the safety layer solves the following projection problem:
arg min
2 11(e um (x))1
(b( + VD()) d(2) s do-
s.t.
As shown in Dalal et al. (2018); Chow et al. (2019), if the constraints have linear nature then an analytical solution exists. In order to get a linearized version of the constraints (and simplify the projection), we can approximate the constraint with its first-order Taylor series at = p0x
[
- ((u [[---x(x)]1" (=(())
arg min
(5)
2
s.t. (x)) - d(x) + @T (x)) + (n-
(l) I dg.
First urder Tay for expansion
The above objective function is positive-definite and quadratic, and the constraints are linear. Though this problem can be solved by an in-graph QP solver, there exists analytical solution (see Ap- pendix G):
Proposition 4.1. At given state x E X, the solution to the Eq. (5), μr is:
/¹ Mr (x X (xx)) (x), 9nD (z) = VQb (=)
where,
(x) -(do + d(x) V
(u. gu.D(z))
5 RELATED WORK
Lagrangian-base methods: Initially introduced in Altman (1999), more scalable versions of the Lagrangian based methods have been proposed over the years (Moldovan & Abbeel, 2012; Tessler et al., 2018; Chow et al., 2015). The general form of the Lagrangian methods is to convert the problem to an unconstrained problem via Langrange multipliers. If the policy pa- rameters are denoted by 0, then Lagrangian formulation becomes: minx max maxx(L(0.))) A) minx20 max; [V (zp) - A(V (xo) - do))] , where L is the Lagrangian and À is the Lagrange multiplier (penalty coefficient). The main problems of the Lagrangian methods that the Lagrangian multiplier is either a syper-paramest (without much intuition), or is solved on a lower time-scale. That makes the unconstrained RL problem three time-scale problem, which makes very difficult to optimize in practice. Another problem is that during the optimization, this procedure can violate the constraints. Ideally, we want a method that can respect the constraint throughout the training and not just at the final optimal policy.
Lyapunov- based methods: In control theory, the stability of the system under fixed policy is computed using Lyapunov functions (Khalil, 1996). A Lyapunov function is a type of scalar potential function that keeps track of the energy that system continually dissipates. Recently, Chow al. 2018; 2019) provide a method of constructing the Lyapunov functions to guarantee global safety of a behavior policy using a set of local linear constraints. Their method requires the knowledge of (V, π²) to guarantee the theoretical claims. They substitute the ideally required Lyapunov function with an approximate solution that requires solving a LP problem at every iteration. For the practical scalable versions, they use heuristic, constant Lyapunov function for all states that only depends on the initial state and the horizon. While our methods also constructs state-wiss wise constraints, there two notable differences: a) our assumption only rely on the current policy candidate and the baseline policy, instead of the baseline and the optimal policy, b) our method does not require solving an LP at every update step construct the constraint and as such the only approximation error that is introduced comes from the function approximation.
*Classic Actor Critic is two time-scale (Konda & Tsitsiklis, 2000), and adding learning schedule over the I Lagrangian makes three time scale.

---

Under review as a conference paper at ICLR 2020
Conservative Policy Improvement: Constrained Policy Optimization (CPO) (Achiam al., 2017) extends the trust-region policy optimization (Schulman et al., 2015) algorithm to satisfy constraints during training as well as after convergence. CPO is computationally expensive it uses an approximation to the Fisher Information Matrix which requires many steps of conjugate gradient descent (Ney steps) followed by backtracking line-search procedure (Mts steps) for each iteration, so it is more expensive by (neg + nis)) per update. Furthermore, accurately estimating the curvature requires large number of samples each batch (Wu al., 2017).
6 EXPERIMENTS
We empirically validate our approach on RL benchmarks to measure the performance of the agent with respect the accumulated return and cost during training in the presence of neural-networks based function approximators. We compare our approach with the respective Unconstrained versions, and the Lyapunov-based approach (Chow et al., 2018; 2019) in each setting. Even though our formulation is based on the undiscounted case, we use discounting with ? = 0.99 for estimating the value functions in order to be consistent with the baselines."
6.1 STOCHASTIC GRID WORLD
Motivated by the safety in navigation tasks, we first consider a stochastic 2D grid world (Leike et al., 2017; Chow et al., 2018). The agent (green cell in Fig. la) starts in the bottom-right corner, the safe region, and the objective is to move to the goal on the other side of the grid (blue cell). The agent can only move in the adjoining cells in the cardinal directions. It gets a reward of +1000 on reaching the goal, and penalty of -1 at every timestep. Thus, the task is to reach the goal in the shortest amount of time. There are number of pits in the terrain (red cells) that represent the safety constraint and the agent gets cost of 10 on passing through any pit cell. Occasionally, with probability p = 0.05, a random action will be executed instead of the one selected by the agent. Thus, the task is to reach to the goal in the shortest amount of time, while passing through the red grids most do/ /10 times. The size of the grid is 12 x 12 cells, and the pits are randomly generated for each grid with probability p = 0.3. The agent starts at (12, 12) and the goal is selected uniformly on (ax, 0), where a ~ (0, 12). The threshold do = 20 implies the agent can pass at most two pits. The maximum horizon is 200 steps, after which the episode terminates.
We use the action elimination procedure described in See 4.1 in combination with n-step SARSA (Rummery& & Niranjan, 1994; Peng & Williams, 1994) using neural networks and multiple syn- chronous agents as in Mnih et al. (2016). We use e-greedy exploration. The results are shown in Fig. 1 (more experimental details can be found in Appendix H). We observe that the agent is able to respect the safety constraints more adequately than the Lyapunov- based method, albeit at the expense of some decrease in return, which is the expected trade-off for satisfying the constraints.
6.2 MuJoCo BENCHMARKS
Based on the safety experiments in Achiam et al. (2017): Chow et al. (2019), we design three simulated robot locomotion continuous control tasks using the MuJoCo simulator (Todorov et al., 2012) and OpenAI Gym (Brockman et al., 2016): (1) Point-Gather: A point-mass agent (S C R2. A R2) is rewarded for collecting the green apples and constrained to avoid the red bombs; (2)
bi-pedal agent (S C R A C RR)) rewarded for running at high speed, but at the same time constrained by speed limit; (3) Point-Circle The point-mass agent (S C IR A C R2) is rewarded for running along the circumference of a circle in counter-clockwise direction, but is constrained to stay within safe region smaller than the radius of the circle.
We integrate our method on top of the A2C algorithms (Mnih et al., 2016) and PPO (Schulman et al., 2017), using the procedure described in Section 4.2. More details about the tasks and network architecture can be found in the Appendix Algorithmic details can be found in Appendix J. The results with A2C are shown in Fig. 2 and the results with PPO are shown in Fig. 3. We observe that
'I practice the starting states in the episode are unlikely to be distributed according to the stationary distribution 1y'. We still use the initial trajectories to update the estimates nonetheless in our experiments, but we use n-step updates.
7

---

Under review as a conference paper at ICLR 2020
Safe method is able to respect the safety constraint throughout most of the learning, and with much greater degree of compliance than the Lyapunov-basse method, especially when combined with A2C. The
where the Safe method fails to respect the constraint is in Point-Circle with PPO (Fig. 3(c)). Upon further examination, we note that the training in this scenario has one two outcomes: some runs end with the learner in infeasible set of states from which it cannot recover; other runs end in good policy that respects the constraint. We discuss solutions to overcome this in the final section.
Gric-world,
Grid-wordd wttd-wor..Coonrraan. Constrant
100
bated
(a) 2D GridWorld
(h) Returns
(c) Constraints
Figure I: Example of gridworld environment. (b,c) Performance over the training for Unconstrained (red), Lyapunov-baset (green), and our method (blue) all trained with n-step SARSA on GridWorld task over 20 random seeds. The x-axis is the number of episodes in thousands. The dotted black line in (c) denotes the constraint threshold, dp. The bold line represents mean, and the shaded region denotes 80% confidence-nntervass.
7 DISCUSSION
We present a method for solving constrained MDPs that respects trajectory-level constraints by converting them into state dependent value-based constraints, and show how the method can be used to handle safety limitations in both discrete and continuous spaces. The main advantage of our approach is that the optimization problem is more easily solved with value-based constraints, while providing similar guarantees and requiring less approximations. The empirical results presented show that our approach is able solve the tasks with good performance while maintaining safety throughout training. It is important to note that there is a fundamental trade-off between exploration and safety. It impossible be 100% safe without some knowledge; in cases where that knowledge not provided priori, it must be acquired through exploration. We see this in some of our results (Gridworld, Point-Circle) where our safe policy goes above the constraint in the very early phases of training (all our experiments started from random policy). We note that the other methods also suffer from this shortcoming. An open question how to provide initial conditions or priori knowledge, avoid this burn-in phase. Another complementary strategy explore for cases where agent is stuck in an unsafe or infeasible policy space, where a recovery method (trained by purely minimizing the constraints) could be useful to help the agent recover (Achiam al., 2017: Chow al., 2019).
8

---

Under review as a conference paper at ICLR 2020
Returns
Salt
Cal
Constraints
Holm wotter. Corsrrairt
Tain Jiin
Salt
(a) Soint-Gather
(b) Safe-Cheeter
(c) Point- Circle
Figure A2C Performance over training for Unconstrained (red), Lyapunov-based (green), our method (blue) all trained with A2C on MuJoCo tasks over 10 random seeds. The x-axis is the number of episodes in thousands. The dotted black line denotes da. The bold line represents the mean, and the shaded region denotes the 80% confidence-intervee
Returns
125
fall
Sala puans
Constraints
inint oother. CoRctroirt
(a) Point-Gather
(b) Safc-Chcetah
(c) Point-Circle
Figure 3: Performance over training for Unconstrained (red), Lyapunov- based (green), our method (blue) all trained with PPO on MuJoCo tasks over 10 random seeds. The x-axis is the number of episodes in thousands, and y-axis denotes the undiscounted accumulated returns. The dotted black line denotes dg. The bold line represents the mean, and the shaded region denotes the 80% suffidence-interaak

---

Under review as a conference paper at ICLR 2020
REFERENCES
Pieter Abbeel and Andrew Y Ng. Apprenticeship learning via inverse reinforcement learning. In
Proceedings of the twenty-first international conference on Machine learning, pp. 1. ACM, 2004.
Joshua Achiam, David Held, Aviv Tamar, and Pieter Abbeel. Constrained policy optimization. arXiv preprint arXiv: 10528, 2017.
Eitan Altman. Constrained Markov decision processes, volume 7. CRC Press, 1999.
Felix Berkenkamp, Matteo Turchetta, Angela Schoellig, and Andreas Krause. Safe model-based reinforcement learning with stability guarantees. In Advances in Neural Information Processing Systems, pp. 908 919, 2017.
Dimitri P Bertsekas, Dimitri P Bertsekas, Dimitri P Bertsekas, and Dimitri P Bertsekas. Dynamic programming and optimal control, volume 1. Athena scientific Belmont, MA, 1995.
Greg Brockman, Vicki Cheung. Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojeiech Zaremba. Openai gym. arXiv preprint arXiv:1606. 01540, 2016.
Yinlam Chow, Mohammad Ghavamzadeh, Lucas Janson, and Marco Pavone. Risk-constrained reinforcement learning with percentile risk criteria. arXiv preprint arXiv: 1512.0162, 2015.
Yinlam Chow, Ofir Nachum, Edgar Duenez-Guzman, and Mohammad Ghavamzadeh. A Iyapunov- based approach to safe reinforcement learning. arXiv preprint /80.: 2018.
Yinlam Chow, Ofir Nachum, Aleksandra Faust, Mohammad Ghavamzadeh, and Edgar Duenez- Guzman. Lyapunov-based safe policy optimization for continuous control. arXiv preprint arXiv:1901.1033/ 2019.
Gal Dalal, Krishnamurthy Dvijotham, Matej Vecerik, Todd Hester, Cosmin Paduraru, and Yuval Tassa. Safe exploration in continuous action spaces. arXiv preprint 1801.088 2018.
Prafulla Dhariwal, Christopher Hesse, Oleg Klimov, Alex Nichol, Matthias Plappert, Alec Radford, John Schulman, Szymon Sidor, Yuhuai Wu, and Peter Zhokhov. Openai baselines. https:
//github. www httm///peaaaaaaeeeeeeee 2017.
Yan Duan, Xi Chen, Rein Houthooft, John Schulman, and Pieter Abbeel. Benchmarking deep reinforcement learning for continuous control. In International Conference on Machine Learning, pp. 1329-1338, 2016.
Benjamin Eysenbach, Shixiang Gu, Julian Ibarz, and Sergey Levine. Leave no trace: Learning to reset for safe and autonomous reinforcement learning. arXiv preprint 1rXiv:1711.06782, 2017.
Hassan K Khalil. Nonlinear systems. 1996.
Torsten Koller, Felix Berkenkamp, Matteo Turchetta, and Andreas Krause. Learning-basee model pre- dictive control for safe exploration and reinforcement learning. arXiv preprint arX1v:1803.08287, 2018.
Vijay Konda and John Tsitsiklis. Actor-critic algorithms. Advances in neural information processing systems, pp. 1008-1014, 2000.
Ilya Kostrikov. Pytorch implementation of reinforcement learning algorithms. https:://ttthhiiieee
com/ wttss/ikkoo///oooreeeeoo a2c ppo acktr gail, 2018.
Jan Leike, Miljan Martic, Victoria Krakovna, Pedro A Ortega, Tom Everitt, Andrew Lefrancq, Laurent Orseau, and Shane Legg. Ai safety gridworlds. arXiv preprint arXiv: 171.08871 2017.
Ian Michael Mitchell. Application of level set methods to control and reachability problems in continuous and hybrid systems. 2003.
Volodymyr Mnih, Adria Puigdomenech Badia, Mehdi Mirza, Alex Graves, Timothy Lillicrap, Tim Harley, David Silver, and Koray Kavukcuoglu. Asynchronous methods for deep reinforcement learning. In International conference machine learning, pp. 1928-1937, 2016.
10

---

Under review as a conference paper at ICLR 2020
Teodor Mihai Moldovan and Pieter Abbeel. Safe exploration in markov decision processes. arXiv preprint A2t5.4220.48880 2012.
Tetsuro Morimura, Eiji Uchibe, Junichiro Yoshimoto, Jan Peters, and Kenji Doya. Derivatives of logarithmii stationary distributions for policy gradient reinforcement learning. Neural Computation, doi: 10.1 (..116//neco.2000 200ec, 19-01122--2222 URL https: //to://ooiii org/
22(2):34--37,, 2010.
1162/neco. 2009. -8-08-20000 922.
PMID: 19842990.
Gergely Neu, Anders Jonsson, and Vicenç Gómez. unified view of entropy-regularized markov decision processes. arXiv preprint arXiv:1705.07799 2017.
Jing Peng and Ronald J Williams. Incremental multi-step q-learning. In Machine Learning Proceed- ings 1994, pp. 226-232. Elsevier, 1994.
Joelle Pineau. The machine learning reproducibility checklist. htt. pdf, 2018.
Martin L Puterman. Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons, 2014.
Gavin A Rummery and Mahesan Niranjan. On-line Q-learning using connectionist systems, vol- ume 37. University of Cambridge, Department of Engineering Cambridge, England, 1994.
John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz. Trust region policy optimization. In International Conference on Machine Learning, pp. 1889-1897, 2015.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv: 1707.66777. 2017.
Richard S Sutton. Learning to predict by the methods of temporal differences. Machine learning, (1):9-44 44, 1988.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Aviv Tamar, Dotan Di Castro, and Shie Mannor. Policy evaluation with variance related risk criteria in markov decision processes. arXiv preprint 1 2013.
Chen Tessler, Daniel J Mankowitz, and Shie Mannor. Reward constrained policy optimization. arXiv preprint arXiv: 2018.
Emanuel Todorov, Tom Erez, and Yuval Tassa. Mujoco: A physics engine for model-basee control. In 2012 JEEE/RS International Conference on Intelligent Robots and Systems, pp. 5026-5033. IEEE, 2012.
Matteo Turchetta, Felix Berkenkamp, and Andreas Krause. Safe exploration in finite markov decision processes with gaussian processes. In Advances in Neural Information Processing Systems, pp. 4312-4320, 2016.
Akifumi Wachi, Yanan Sui, Yisong Yue, and Masahiro Ono. Safe exploration and optimization of constrained mdps using gaussian processes. In AAAI Conference Artificial Intelligence (AAAI), 2018.
Yuhuai Wu, Elman Mansimov, Roger B Grosse, Shun Liao, and Jimmy Ba. Scalable trust-region method for deep reinforcement learning using tronecker-factorff approximation. In Advances in neural information processing systems, pp. 2279-5288, 2017.
11

---

Under review as a conference paper at ICLR 2020
A REPRODUCIBILITY CHECKLIST
We follow the reproducibility checklist (Pineau, 2018) and point to relevant sections explaining them here. For all algorithms presented, check if you include:
A clear description of the algorithm. The algorithms explained in Sec. J. Any addi- tional details for Discrete methods are provided in Sec. 4.1, and for continuous Sec. 4.2.
An analysis of the complexity (time, space, sample size) of the algorithm. The analytical solution in Eq. (5) consists of a few vector arithmetic and relu operator and such has the same complexity as the baselines. For the discrete case, with deterministic policies the solution again can be implemented basic vector arithmetic operations, and has very little additional overhead. For discrete actions with stochastic policies, one needs to sovle the LP problem in (SPI). In that case the complexity is same as the baseline safe-methods (Lyapunov), and is higher than the unconstrained versions. In terms of computation time (for Deep-RL RL experiments) the newly proposed algorithms are almost identical to the baselines due to its parallelizable nature. We do not make any claims about the sample complexity.
part of the computation graph, consisting of
A link to downloadable source code, including all dependencies. The code will be
made available after the acceptance of the paper.
For any theoretical claim, check if you include:
A statement of the result. See the main paper for all the claims we make. Additional details are provided in the Appendix.
A clear explanation of any assumptions. See the main paper for all the assumptions.
A complete proof of the claim. See the main paper. The cross references to the proofs in the Appendix have been included in the main paper.
For all figures and tables that present empirical results, check if you include:
A complete description of the data collection process, including sample size. For the base agent we standard benchmarks provided in OpenAl Gym (Brockman et al., 2016), and rllab (Duan al., 2016). We use the code from Achiam al. (2017) for building the Point-Circle and Point-Gather environments.
A link to downloadable version of the dataset or simulation environment. See: cattuub.co//openi/gyyn.n for OpenAI Gym benchmarks, gittub.com/jachaam/qpo for rllab based Circle and Gather environments.
An explanation of how samples were allocated for training / validation / testing. We do not use a split as we run multiple runs over random seeds to examine the optimization performance.
An explanation of any data that were excluded. NA
The range of syper-parametery considered, method to select the best hyper-parameter configuration, and specification of all hyper-parameters used generate results. The default hyper- parameterssss for the MuJoCo baselines taken from Kostrikov (2018). The ranges and parameters for Grid experiments are described in Sec. H, and for MuJoCo are described in Sec. I.
The exact number of evaluation runs. The number of evaluation runs is mentioned in the caption corresponding to each result.
A deseription of how experiments were run. See Experiments Sec. 6 in the main paper and in the Appendix Sec. H and Sec. I.
A clear definition of the specific measure statistics used to report results. Un- discounted return and cost using the current policy over the horizon are plotted after every 1000 episodes are plotted. We use a linear-filter with 0.7 weight for smoothing. We use the smooting algorithm provided by TensorBoard (https:/ /ggthub.. hom//tnsorffow/ tensorboard),
12

---

Under review as a conference paper at ICLR 2020
Clearly defined error bars. Standard enror used in all cases.
A description of results with central tendency (e.g, mean) and variation (e.g. siddev). The bold lines in the figure represent the mean, and the shaded region denotes the 80% confidence interval.
A description of the computing infrastructure used. We distribute all runs across 10 CPU nodes (Intel(R) Xeon(R) CPU E5-2650 v4) and GPU (GP 100) per run for experiments.
B BACKWARD VALUE FUNCTIONS
We have the following result from Proposition 1 from Morimura al. (2010). We give the proof too for the sake of completeness.
Proposition B.1. Let the forward Markov chain M(=) be irreducible and ergodic, i.e., has a stationary distribution. Then the associated backward Markov chain (xx) is also ergodic and has the same unique stationary distribution as (
(vr X)
where 17 17*(()) (x)) and 177(x)
(x)) the stationary distributions of M(=) and BTT).
Proof. Multiply both sides of Eq. (1) by 17" (zx)) and sum over all actions d:1 A obtain detailed
balance like equations (with respect to time):
D" (= (#x) = D ( (1
(V E X, 2e X)
Sum over all possible xe we have:
Σ p" (c1-1 (1z) (1 (Iz-1).
The above equation indicates that ((T) has same stationary distribution as M(T).. the matrix form the above equation can be written n/p 17. that implies that 7) is stationary distribution with 7 transition matrix.
B. RELATION BETWEEN FORWARD AND BACKWARD MARKOV CHAINS AND BACKWARD VALUE FUNCTIONS
Proof. We use the technique of Proposition 2 of Morimura et al. (2010) to prove this. Using the Markov property and then substituting Eq. (1) for each term have:
p" (x1-1, a:-1.-1000 1....... Et a K [x+) = 5" (x--1, ae- ac-1 1/x1) 5" (xI-K, k. at ((1
P (I1, a: 11-1) ... p (x1- at- k 11 (PP-K) )n (xI-K)
17 (x,1
Pd (zt, 0--1/=1-1)--- ... PT (It- (ot-K+i, a, - (F-KK))
This proves the proposition for finite K. Using the Prop. B.1, K + oo case is proven too:
K
K Σ
lim E
Σ d(
= lim EMGr) 10000
d(z) (F)- (FL-K)
K-0
(x))
= ΣΣ (o)(())
3EA'
13

---

Under review as a conference paper at ICLR 2020
B.2 TD FOR BVF
Proof. We use the same technique from Stochastic Shortest Path dynamic programming (Bertsekas al., 1995, Vol 2, Proposition 1.1) prove the above proposition. The general outline of the proof is given below, for more details we refer the reader to the textbook.
We have,
= -
(Eq. (4) in matrix notation)
Using induction argument, we have for all V. E Rd and 2 1, we have:
T") Re V P
d
m=0
Taking the limit, and using the result, limg-
P
V
0, regarding proper policies from
Bertsekas et al. (1995, Vol 2, Equation 1.2), we have:
lim
lim
P
d= d=V"
m==
Also we have by definition:
8+1
=
T
V.
and by taking the limit + 20, we have:
V = d v'V
which is equivalent to.
To show uniqueness, note that V = =VVV then V. = =(7m) "V for all and letting k - oo we get
-=
C VALUE-BASED CONSTRAINT LEMMA
Lemma C.1. d(ax) wo, π| S Pe (xx)) and Di d(xx)
2o x
s
Baa-da (Pr)) (1x)
Proof. Follows since adding more steps to the trajectory (from steps to T) can only 8 (prye [k s
increase the expected total cost. ΣT= d(xx)
Fo. π
8an (Pry (E d Eugyees (p
VT (oz)). The backward case analogous.
D PROPERTIES OF THE POLICY ITERATION (SPI)
Theorem D.1. Let = (V(T++1(11)) (+a)) (1/2) E. | (a|z) TT (a)xz)) denote the total variation between policies TH (-|z) and + (z). the policies are updated sufficiently slowly and me is feasible, then is m More specifically:
14

---

Under review as a conference paper at ICLR 2020
do 6o-V2* Vo then T is feasible at zp- 27 Dsexx
(I) If Ty. is feasible at 20 and (xx) I
(II) If Wh feasible everywhere (i.e.
(*)
S do Va) and
(Φ))
do (x)
Va: then T441 feasible everywhere. 27 max," (do (+)))(2²))
We note that the second case allows the policies to updated in a larger neighborhood but requires TA to be feasible everywhere. By contrast the first item updates policies in smaller neighbourhood but only requires feasibility at the starting state.
Proof. Similar to the analysis in Chow et al. (2018). aim to show that V S do. For simplicity consider & = 0, and by induction the other cases will follow. We write Po pro P1 = pm) (aa x)) = TT (a x) To (a(22)) and PA = [EucA ((a")) a)] fxr,)) Note
that Po) (I Pi Pa). and therefore (I P1 + PA)(1 Po) [ Thus, we find
(1- - (1 - (1-
+ PA(I PP)
Multiplying both sides by the cost vector d one has
(x) (x) = E Σ d(xx) + =((x)) M1,
for each x, where e(x) EeEd A(a/x) Ex'Ex P(a" [r, a) a) (x'). Splitting the expectation, we have
VT V5 (x) - Σ c(xr) mi
For case (I) we note that V < DMXX T and so (20 DMXX S 6(x)) Vo,. Using a (Iz) S
do. (do - VV M/D gives V (xp) I V (xo) - 22022-2MXX (do V (2D Le. Wo feasible Zg- For case (II) note that V (x) < max (dn (v')
(v') d(x')) O since To is feasible
at every T. As before, we have 20 (z)) < E(x,) Va, and so V (x) < ( (
Vi (2)) do Vz, ie. æi feasible everywhere.
Theorem D.2. Let Th and T be successive policies generated be the policy iteration algorithm of (SPI). Then /Tn+1 > V
Proof. Note that kn+1 and nn are both feasible solutions of the LP (SPI), Since TT+1 maximizes V over all feasible solutions, the result follows.
E ANALYTICAL SOLUTION OF THE UPDATE - DISCRETE CASE
We follow the same procedure (Chow et al., 2018, Section E.1) to convert the problem to its Shannon entropy regularized version:
{(1=))(Q(2,)) + (o))(((=)); REA
max
((1x)) + V)(x)) d(x) < do:
s.t.
(6)
where + > 0 is regularization constant. Consider the Lagrangian problem for optimization:
max max I (T,, A) (.1x)) + (QD(x,)) + log (+(x)) + A(do + d(x) - V(x))
A20
From literature (Neu et al., 2017), the inner X-solution policy has the form:
(-1o) x exp Q(z..) (2x(x..)
15

---

Under review as a conference paper at ICLR 2020
We now need to solve for the optimal lagrange multiplier X at æ. Q(x,,) .) + (QD(2,,)) + X(do d(x) Vx(r),,
max - log-sum-exp A20
where rog-sum-expl = Ea exp(ya) is convex function in and objective is a concave function of A. Using KKT conditions, the V gives the solution:
(do + d(x) - Vx(x)) Eo Qu( a) exp( (- -(ee0))Ap((am)))
0
Ea exp( (- ((xa)))))aaaa) (Qm(za)
Using parameterization of 2 exp(-A), the above condition can be written as polynomial equation z:
(do + d(x) VD (<)) Qo(x,a)) (exp(-2(in)) ((x,a))
@a(s.a)
The roots to this polynomial will give 0 < (2) s 1, using which one can find X*(x) = -oo[(>(<>)), The roots can be found using the Newton's method. The final optimal policy of the entropy-reeularizee process is then:
मं exp (((x,))xQQlll
F EXTENSION OF SAFETY LAYER TO STOCHASTIC POLICIES WITH GAUSSIAN PARAMTERIZATION
Consider stochastic gaussian policies parameterized by mean p(2; 0) and Srandard-deviation (a; o). and the actions sampled have the form {ur;; 0) + (2; Ø)c, where c ~ (N,,, T) is the noise. Here, < p(x;; f)), (x; Φ) > are both deterministic w.r.t. the parameters 8, á and x, and as such both of them together can be treated in the same way deterministic policy (π(x) =< p(x), (xx >). The actual action sampled and executed the environment is still stochastic, but we have moved the stochasticity fron the policy to the environment. This allows to define and work with action-vas -vauue functions Qx(r, Hr (z), F (x)). ). this case, the corresponding projected actions have the form ul + a'c. The main objective of the safety layer (without the constraints) can be further simplified as:
arg min E. ((..) M².0 o'
(1 + o'c) (Mx (zx)
2
1
arg min EC-N1o.) o
(1 (1l'-ux(()) (x(x)) + (10' (x()))1)
2
arg min BEnNoOn u'.""
(=))(())) + 11(0' - ox (x))ee| +2< - >
=0,due to linearity of expectation,
1
EE-NCON [IlO'' -lo (x))ee11))) (Ilu' (n(2))) (1l''=n(<)))
arg min- or
2
arg min
1|'' (n)))1 + 11(o' -xx(x)) -
EanNionn [[
=1,sccond moment of
aa.a" 2 (Ilee (11p'-ux (2)11 11(o' -
arg min
As both (=; 0) and o (1: modelled by independent set of parameters (different neural networks, usually) we can solve each of the safety layer problem independently, w.r.t only those parameters.
16

---

Under review as a conference paper at ICLR 2020
G ANALYTICAL SOLUTION IN SAFETY LAYER
The proof is similar to the proof of the Proposition I of Dalal et al. (2018). We have the following optimization problem:
[
arg min
2 (p un (x))
s.t. (x)))- d(x)
+ (n (p- (=(=)) (o do
As the objective function and constraints are convex, and the feasible solution, ft,,, X², should satisfy the KKT conditions. We define <<x) (do d(x:) (x) (x(2) and gu.((x) VQ (2t, u) (x)=(x)- Thus, we can write the Lagrangian as:
1 -1 s((w (x()))= gup(()) c(x))
I(u, X)
From the KKT conditions, get:
V L = μ (x) + )0)
(1 Un (x))² g,, c(x)
From Eq. (7), we have:
n¹ -2)) (x)
(9)
Substituting Eq. (9) in Eq. (8), we get:
(z) (x)) (,) E(xx) =
x -E(x)
(u.
When the constraints are satisfied (e(x) operator, that O for negative values.
0), the À should be inactive, and hence we have ()+
H DETAILS OF GRID-WORLD. EXPERIMENTS
H.1 ARCHITECTURE AND TRAINING DETAILS
We one-hot encoding of the agent's 's location in the grid the observation, i.e. æ is binary vector of dimension IR 12x12 The agent is trained for 200k episodes, and the current policy's 's performance is evaluated after every 1 episodes.
The same three layer neural network with the architecture is used for state encoding for all the different the estimators. The feed-forward neural network has hidden layers of size 64, 64, 64, and relu activations. For the state-action value based estimators, the last layer is linear layer with 4 outputs, for each action. For value function based estimators the last layer linear layer with single output.
We use Adam Optimizer for training the estimators. A learning rate of 1e-3 was selected for all the reward based estimators and learning rate of 5e-4 selected for all the cost based estimators. The same range of learning rate parameters for considered for all estimators i.c. [1e-5, Se-5, Ic-4, 5e-4, le-3, 5e-3, le-2, 5e-2, le-1).
We use n-step trajectory length in A2C with n = 4, i.e., trajectories of length n were collected and the estimators were updated to used via the td-errors based on that. We use the number of parallel agents 20 in all the experiments. The range of parameters considered was n E (1, 4, 20). The same value of was used for all the baselines.
17

---

the Under review as a conference paper at ICLR 2020
Step:
Step: 0
Step:
(a) Point-Circle
(h) Safe-Cheetah
(c) Point-Gather
Figure 4: MuJoCo Safety Environments
DETAILS OF THE MuJoCo EXPERIMENTS
1.1 ENVIRONMENTS DESCRIPTION
The environment (Fig.4c) taken from Achiam et al. (2017), where the point mass agent gets reward of +10.0 for collecting green apple, and cost of I for collecting a red bomb. Two apples and eight bombs are spawned randomly at the start of each episode. The constraints defined over the nmber of bombs collected episode. Episode horizon is 15 and threshold dg = 4.
Point-Gather:
This environment (Fig.4b) is taken from Chow et al. (2019). A bi-pedal agent (HalfCheetah-vO))
Safe-Cheetahi
augmented with speed safety constraints. The agent gets the reward based on the speed with which it runs, and the constrain is define the speed be less than 1, i.e. it gets constraint cost based on 1 |[]e] > 1]. where is the velocity at the state. The maximum length of the episode is 200 and the constraint threshold is d0 50.
This environment (Fig.4a) taken from Achiam et al. (2017). The point- mass agent is rewarded for running along the cireumference of circle of radius 15 in counter-clockwise direction, with the reward and cost function:
Point-Circle:
R(s)
1 [. 2l1l2 15
C(s) [|x] > 2.5].
where v. coordinates in the plane and is the velocity. The length of the episode is 65 and the constraint threshold do = 10.0.
I.2 NETWORK ARCHITECTURE AND TRAINING DETAILS
The architecture and the training procedure is based on the open-source implementations (Kostrikov, 2018). All the value based estimators use a network architecture of 2 hidden layers of size 200, 50 hidden units with tanh non-linearity, followed by linear layer with single output. For the actor, model mean using a network architecture of hidden layers of size 100, 50 hidden units with tanh non-linearity, followed by linear layer with dimensions of the action-space and tanh non- -ineaiiiarr For the (x, μ1) we also 2 layer neural network with 200, (50 + action-dimension) hidden units and tanh non-linearity. We concatenate the mean the second layer, and add a linear layer with single output in the end.
Entropy regularization with 3 0.001 was used for all the experiments and the baselines. The trajectory length for different environments. For PPO GAE with À 0.95 was used for every algorithm. 20 parallel actors were used for every algorithm for each experiment. We searched the trajectory length hyper-parameter in the range 5,20,100 for every environment. We used the trajectory length of 1000 over which the samples are collected for PPO, for all environments. For the A2C experiments, for SafeCheetah trajectory length of is used and for the rest 20 is used.
18

---

Under review as a conference paper at ICLR 2020
We Adam Optimizer for training all the estimators. The learning rate of the critic is always 0.5 the learning rate of the actor. For the cost estimators, the same learning rate was used for forward and backward estimators. The same range of learning rate parameters for considered for all estimators i.e. (1e-5, 5e-5, le-4, 5e-4, le-3, Se-3, le-2, 5e-2, le-1).
1.3 OTHER DETAILS
As we mentioned Sec. 7, due to exploration the agent can potentially end up being in an infeasible policy space. To prevent that from happening recovery policy (or safe-guard policy) (Achiam et al., 2017; Chow et al., 2019) is used to recover back to the feasible policy space. We run the experiments with and without the use of recovery policies (in the same procedure as the baselines), and chose the run that performs the best. We noticed that, empirically, for our approach recovery policies are only required for Point-Circle environments, as the agent has much more probability of being stuck constraint space.
In order to take error due to function approximation into account, Achiam et al. (2017) use cost- shaping to smooth out the sparse constraint, and Chow et al. (2019) use relaxed threshold, i.e. do (1 - 8). instead of do, where å E (0. 1). We run experiments with = {0.0, for each algorithms, and use the best among them. We found that empirically, only for Safe-Cheetah å = 0.2 works better compared to = 0.0.
J ALGORITHM DETAILS
J.1 N-STEP SYNCHRONOUS SARSA
The algorithm for n-step Synchronous SARSA is similar to the n-step Asynchronous Q-learning of Mnih al. (2016), except that uses SARSA instead of Q-learning, is synchronous, and instead of greedy maximization step of e-greedy we use (SPI). When working with discrete actions and deterministic policies, this can be solved as part the computation- grapph itself. The algorithm is presented in Alg. 1.
J.2 A2C
In Actor Critic (Konda & Tsitsiklis, 2000) algorithms, the parameterized policy (actor) is denoted by T (r; 0), and updated to minimizing the following loss:
(()) R log (atl (rx + ( V2,)))
The algorithm for A2C with Safety Layer given by Eq. (5) is similar to the Synchronous version of Actor-Critic (Mnih et al., 2016), except that it has estimates for the costs and safety-layer. Note that due to the projection property of the safety layer, it possible to sample directly from the projected mean. Also, the projection is a result of vector products and max, it is differentiable and and computed in-graph (via relu). The algorithm presented in Alg.
J.3 PPO
The PPO algorithm build on top of the Actor-Critic algorithm and is very similar to Algorithm 2. The main difference is how the PPO loss for the actor is defined
CLIP (0) Elmin(pe (ipppp 1, +c)))),
<,(0/ where the likelihood ration is (0) nene (4e )
with votd being the policy parameters before the
update, < 1 is hyper-parameters that controls the clipping and A, is the generalized advantage estimator:
T-1
A, GAB(AN)
k=0
19

---

Under review as a conference paper at ICLR 2020
Algorithm 1 Synchronous n-step SARSA
Input: 9 parameters for (z,, 0), fD parameters for Qa(z, BDD parameters for V (x; ΦD); To initial feasible policy. for episode e E 1,.,, .M do
Add the initial state to the trajectory buffer {5r) t s-1
while < T do:
Estart <- f
while < + n or == T do
Select d, using (SPI), execute de, observe #++1 and reward and cost de.
Add experiences to buffer, i.e., T t- (a,, Tr, de, Tz+1).
5- ++++1
end while
Calculate the next action for 2441 using the current policy estimates, dz+1 Bootstrap the targets:
if Tfl=- T otherwise
R -
Q (11+11
RD + 0
i = T otherwise if 0 otherwise
0
RD
1100)
b. Calculate the targets for the transitions buffer
for E (t - 1..-,,,,,,,., tstart] do
R +- F; 1 + RD s d, RRD
Accumulate the gradients wrt 0 0p:
d0 d0 + 0R Q(2,,a;;)))
a,;
00
d0p d0p 0(Rp QD( as 0p))
00p
end for for i (tstart..... do RD t- d; + RRD Accumulate the gradients wrt óp:
0RD Volan 2
dép dép
DΦD
end for
Do synchronous batch update with the accumulated gradients to update 6, 0p, ΩD using d0, d0 døp end while
Empty the trajectory buffer, end for
20

---

Under review as a conference paper at ICLR 2020
Algorithm 2 Synchronous A2C with Safety Layer
Input: parameters for π ((;; 0), @ the parameters for V(x; Φ). OD parameters for Qp(x, μu; 0D).
ΦD parameters for V (1; (b)); for episode e ,..,. M do
Add the initial state to the trajectory buffer T + {0o} t
while t < T do:
Estrrt t-t
while t < + or = do
Select a, using sampling from the projected mean μ via safety layer Eq,(5), execute des observe 1 and reward and cost de.
Add experiences to buffer, i.c,, T < (at, Pt, Ti, de, T141).
t t- ++
end while
Calculate the next mean for 2++1 using the current policy estimates, 14+1 Bootstrap the targets:
0 R
if = T otherwise
V (I441,
50 + (p((sct))M41i:0))
if = T otherwise
RD
RD
0
it==00 0 otherwise
> Calculate the targets for the transitions in buffer
i (1 ,,, start do
R +- P; R
RD d, RRD
Accumulate the gradients w.r.t. 0, cb, 0p:
d0 + d0 + V log (a;
0e () V(ze Ø))
dø + do + 0R V(I:))2
0
d0p + d0p + 0RR Qp H4: 0p))
D0p
end for
for iE (tstart..... . do
RD +- d2 + + RD Accumulate the gradients wrt Φp:
dép døp 0RD - ">(=;o)))
OΦD
end for
Do synchronous batch update with the accumulated gradients update 0, Φh 0D, &D using d0, dó, d@p, dép. end while
Empty the trajectory buffer, end for
21

---

Under review as a conference paper at ICLR 2020
where T is the maxmimum number of timestamps in an episode trajectory, and 8, denotes the TD error at j. The value function is updated using the "A-returns from the GAE:
[(Ø) ((V" ②) (V* (x; Oold) + A.))
Similar to the the forward value estimates the backward value estimates are defined in the similar sense. One way to think of it is to assume the trajectories are reversed and we are doing the regular GAE estimation for the value functions.
The GAE updates for the regular value function can be seen in the A-operator form as:
Txx = (1 - >Pp" + yP=0" (²) + v².
In similar spirit it can be shown that the X-operator for SARSA has the form:
4x = (T
-T" -
where (T"9" q"" denotes the TD ertor. Thus, the GAE estimates can be applied for the Q-functions in the similar form, i.e.
T-1 B GGAEAAN) E (
I(Op) = ()( 0D) (Q (z, 0p..) + B.))
22


Reviews:
[{"review_id": "r1x5sCBaYB", "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": "This paper presents a new approach for solving Constrained MDPs. Because the cost constraint is cumulative, the best action depends on the cumulative cost so far. They address this issue by learning a backward value function of the estimated cumulative cost so far. Their theoretical results show that the same properties for forward value functions hold here for backwards ones. They are then able to use the forward and backward cost estimates to constraint the actions selection, by adding a safety layer to the algorithm. The results show that the method does a better job of meeting safety constraints than the Lyapunov based method.\n\nThe backward value function idea is a nice novel way of addressing the cumulative cost constraint problem. \n\nThe paper is clearly written and the results are nice.\n\nThe biggest issue with this paper is that too much material has been pushed to the appendix. I think at the least some of the details of the actual implementation with PPO or A2C should be moved into the main text. \n\nFor the empirical results, it would be great to see something about the computation or wall clock time required. Does this method run more quickly than the Lyapunov based 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 at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "SkgIf8LfFS", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "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 approaches the CMDP problem, in which one wishes to learn a max return policy subject to trajectory-based constraints.  The paper proposes a technique based on the introduced concept of \"backward value functions\".  These functions satisfy a sort of Bellman equation.  The paper proposes a safe policy improvement step based on these value functions, with theoretical guarantees on the safety of the resulting policy.  The method is evaluated on gridworlds and mujoco tasks, showing good performance.\n\nThe paper provides nice results some intriguing ideas, although after reading I am left with several questions as to the details of the method and its place relative to previous works.\n\n-- How is the backwards value function learned exactly?  Since it relies on a backwards Bellman operator, it seems to necessitate on-policy samples.  Is the function learned in an off-policy fashion somehow?\n-- The problem solved by SPI (constraint for each state) seems much more conservative than the constraint at the bottom of page 4 (single constraint based on average over all states). In it current form, the algorithm appears to be overly conservative, to the point that it may converge to a policy very far from optimal.\n-- I am confused by the assumption on policies updating \"sufficiently slowly\".  Why is this needed?  Also, how does this relate to CPO (Achiam, et al.)?  It would appear that the methodology of CPO is more desirable, since it only requires the \"sufficiently slow\" assumption without the additional backward-value constraints. ", "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 assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "B1gmihsAYH", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "In this work, the authors studied solving the CMDP problem, in particular to model the constraint propagation using the idea of the backward value functions. Using the time-reversed probability property, they first established Bellman optimality conditions for the backward value function, which accounts for the tail expected return, conditioned on the final state. \nUtilizing  the notion of backward value function, they further use that to model the constraint in the CMDPs, and proposed several safe policy iteration algorithms for both cases with discrete actions and with continuous actions. Experiments show that this method has better constraint guarantees than the state-of-the-art algorithms, such as the Lyapunov approach.\n\nThe idea of using backward value functions to model constraints in CMDP is interesting and so far I have not seen it in other places. The algorithms developed with this approach also appear to work reasonably well (especially in constraint guarantees) on benchmark domains such as gridworld and mujoco control tasks. The authors also provide several properties such as consistent feasibility and policy improvement, similar to the Lyapunov method,  and derive several versions of safe policy optimization algorithms. However, I found the intuition of using backward value function rather unclear. Unlike the Lyapunov function, which attempts to estimate a near-optimal \"remaining constraint budget\" w.r.t. CMDP constraint, what is the motivation behind using the backward value. Does the backward probability have any connections to occupation measures? Without similar motivations it is unclear how close the performance of the policy computed from this backward value approach with that of an optimal CMDP policy. Also unlike the Lyapunov approach in Chow'18, the consistent feasibility  property in this work appears to be more restricted as it is only limited to a slow policy update. Finally the experimental results look promising, but it would be great to also compare with other state-of-the-art results such as Lagrangian method, and conservative policy improvement (such as CPO).\n \n", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "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": {}}]

Author rebuttal:

Meta-review: The paper considers the setting of constrained MDPs and proposes using backward value functions to keep track of the constraints.

All reviewers agreed that the idea of backward value functions is interesting, but there were a few technical concerns raised, and the reviewers remained unconvinced after the rebuttal. In particular, there were doubts whether the method actually makes sense for the considered problem (the backward VF averaging constraints over all trajectories, instead of only considering the current one), and a concern about insufficient baseline comparisons.

I recommend rejection at this time, but encourage the authors to take the feedback into account, make the paper more crisp, and resubmit to a future venue.
Decision: Reject