Accelerating Safe Reinforcement Learning with Constraint-mismatched Policies
Authors: Tsung-Yen Yang
Justinian Rosca
Karthik R Narasimhan
Peter Ramadge
Venue:  (2021)
Keywords: Reinforcement learning with constraints
Safe reinforcement learning

Abstract: We consider the problem of reinforcement learning when provided with (1) a baseline control policy and (2) a set of constraints that the controlled system must satisfy. The baseline policy can arise from a teacher agent, demonstration data or even a heuristic while the constraints might encode safety, fairness or other application-specific requirements. Importantly, the baseline policy may be sub-optimal for the task at hand, and is not guaranteed to satisfy the specified constraints. The key challenge therefore lies in effectively leveraging the baseline policy for faster learning, while still ensuring that the constraints are minimally violated. To reconcile these potentially competing aspects, we propose an iterative policy optimization algorithm that alternates between maximizing expected return on the task, minimizing distance to the baseline policy, and projecting the policy onto the constraint-satisfying set. We analyze the convergence of our algorithm theoretically and provide a finite-sample guarantee. In our empirical experiments on five different control tasks, our algorithm consistently outperforms several state-of-the-art methods, achieving 10 times fewer constraint violations and 40% higher reward on average.

Under review as a conference paper at ICLR 2021
ACCELERATING SAFE REINFORCEMENT LEARNING WITH CONSTRAINT-MISMATCHDD POLICIES
Anonymous authors Paper under double-blind review
ABSTRACT
We consider the problem of reinforcement learning when provided with (1) baseline control policy and (2) a set of constraints that the controlled system must satisfy. The baseline policy can arise from teacher agent, demonstration data or even a heuristic while the constraints might encode safety, fairness or other application-speefie requirements. Importantly, the bascline policy may be sub-optimal for the task at hand, and is not guaranteed to satisfy the specified constraints. The key challenge therefore lies in effectively leveraging the baseline policy for faster learning, while still ensuring that the constraints are minimally violated. To reconcile these potentially competing aspects, we propose an iterative policy optimization algorithm that alternates between maximizing expected return on the task, minimizing distance the baseline policy, and projecting the policy onto the constraint-satisfying set. We analyze the convergence of our algorithm theoretically and provide finite-time guarantee. In our empirical experiments on five different control tasks, our algorithm consistently outperforms several state-of- the-art methods, achieving 10 times fewer constraint violations and 40% higher reward on average
INTRODUCTION
Deep reinforcement learning (RL) has achieved superior performance in several domains such as games (Mnih et al. 2013 Silver et al. 2016) and robotic control (Levine et al. [016 Rajeswaran al. 2017). However, in these complex applications, learning policies from scratch often requires tremendous amounts of time and computation power. To alleviate this issue, one would like to leverage a baseline policy available from a teacher or a previous task. However, the baseline policy may be sub-optimal for the new application and is not guaranteed to produce actions that satisfy given constraints on safety, fairness, or other costs. For instance, when you drive an unfamiliar vehicle, you do so cautiously to ensure safety, while at the same time you adapt your driving technique to the vehicle characteristics to improve your 'driving reward'. In effect, you (as the agent) gradually adapt a baseline policy (i.e., prior driving skill) to avoid violating the constraints (e.g., safety) while improving your driving reward (e.g., travel time, fuel efficiency).
This problem is challenging because directly leveraging the baseline policy, in DAGGER (Ross) let al. 2011] or GAIL (Ho & Ermon 2016), may result in policies that violate the constraints since the baseline is not guaranteed satisfy them. To ensure constraint satisfaction, prior work either adds a hyper-parameter weighted copy of the imitation learning (IL) objective (i.e., imitating the baseline policy) the RL objective (Rajeswaran et al.) 2017 Gao al., [018 Hester al.) 2018). or pre-trains policy with the baseline policy and then fine-tunes it through RI. (Mülling et al. 2013
Chernova Thomaz 2014). Both these approaches incur the cost of weight tuning to satisfy the cost constraint and do not ensure constraint satisfaction during training.
In this work, to learn from the baseline policy while satisfying constraints, we propose an iterative algorithm that performs policy updates in three stages. The first step updates the policy to maximize expected reward using trust region policy optimization (e.g., TRPO (Schulman et al. 2013)). This can, however, result in intermediate policy that is too far from the bascline policy and one that may not satisfy the constraints. The second step performs a projection in policy space to control
Code available
com htw.gg/le..cmm//e//////acellllll

---

Under review as a conference paper at ICLR 2021
Trust region k+z
Cost
hb Re
Cost constraint
Region around
constraint
Reward optinal
Cost constraint
Rg
set
Reward optimal
h5
set
set
(a)
(b)
(c)
Figure 1: (a) Update procedures for SPACE. Step (green) improves the reward in the trust region. Step (blue) projects the policy onto a region around the baseline policy wg- Step 3 (red) projects the policy onto the constraint set. (b) Illustrating when we is outside the constraint set. (c) Illustrating when TB is inside the constraint set. The highest reward is achieved at the yellow star.
the distance between the current policy and the baseline policy. This distance is updated each episode depending on the reward improvement and constraint satisfaction, allowing the learning algorithm to explore without being overly restricted by the (potentially constraint- constraint-violating) -voolatin)) baseline policy (Rajeswaran et al. 2017). This also enables the baseline policy to influence the learning without the computational burden of learning cost function for the baseline policy (Kwon et al.) 2020). The third step ensures constraint satisfaction at every iteration by performing projection onto the set of policies that satisfy the given constraints. This ensures recovery from infeasible (i.e., constraint-violating
states (e.g., due to approximation errors), and eliminates the need for tuning weights for auxiliary cost objective functions (Tessler et al. 2018). We call our algorithm Safe Policy Adaptation with Constrained Exploration (SPACE).
This paper's contributions are two-fold. We first analyze our proposed SPACE algorithm and provide a finite-time guarantee for its convergence. We also provide an analysis of controlling the distance between the learned policy at iteration and the baseline policy to ensure both feasibility of the optimization problem and safe exploration by the learning agent. Second, we empirically compare SPACE with sfateoof-the-are algorithms on five different control tasks, including two Mujoco environments with safety constraints from Achiam et al. (2017), two challenging traffic management tasks with fairness constraints from Vinitsky et al. (2018), and one human demonstration driving task with safety constraints from Brockman et al. (2016). In all tasks, SPACE outperforms the state-of- oace-of-lie the art safe RL algorithm, projection-base based constrained policy optimization (PCPO) in Yang et al. (2020), averaging 40% more reward with 10 times fewer cost constraint violations. This shows that SPACE leverages the baseline policy to achieve hetter learning efficiency while satisfying the cost constraint.
2 RELATED WORK
Policy optimization with constraints. Learning cunstraint-satisfyie policies has been explored in
the context of safe RL (Garcia & Fernandez, 2015), (Hasanbeig al. 2020 Junges et al. 2016 type of approach (Achiam et al.
Jansen et al. 2020). Prior work either uses a condiiional-gradieen
2017),
adds a weighted copy of the cost objective in the reward function (Tessler et al. 2018 Chow
ct al.
2019:
Fujimoto et al.) 2019) Stooke et al.] 2020), adds a safety layer to the policy Dalal
al.
2018 Avni et al. 2019), concerns about the chanced constraints (Fu & Prashanth L.
2018
Zheng & Ratlifi 2020). Perhaps the closest work to ours is Projection-basee Constrained
Policy Optimization (PCPO) (Yang et al., 2020), which also uses projections in policy space to
ensure constraint satisfaction. However, PCPO does not have the capability to safely exploit prior information (through baseline policy). The lack of using prior policies in PCPO makes it sample- inefficient. In addition, our SPACE algorithm's 's update dynamically sets distances between policies while PCPO does not. This update important effectively and safely learn from the baseline policy. Furthermore, we provide a safety guarantee to ensure the feasibility of the optimization problem while PCPO does not. Merely adding an II. objective in the reward objective of PCPO cannot learn efficiently, as shown in experiments. This analysis allows to advance towards the practical use of RL in real applications, which PCPO and other algorithms have never done before.
Policy optimization with the initial safe set. Wachi & Sui 2020): Sui et al. (2015): Turchetta et al. 2016) assume that the initial safe set is given, and the agent explores the environment and verifies the safety function from this initial safe set. There is baseline policy here. In contrast, our assumption to give a baseline policy to the agent. Both assumptions are reasonable as they provide an initial understanding of the environment.
2

---

Under review as a conference paper at ICLR 2021
Algorithm
Properties
Approach
DAGGER (Ross al. 2011
Optimize IL objective
DAPG (Rajeswaran al. 2017)
Optimize RL and IL. objectives jointly
NAC
Gao et al. 2018)
Pre-train with IL and find-tune with RL
IC-GAIL [Wu et al.
2019
Generative adversarial IL
CPO
(Achiam et al. 2017)
④ A
Safe RL solved by a line search
RCPO
Tessler et al.
2018
@ A
Safe RL solved by a Lagrangian approach Safe RL solved by a projection
PCPO
Yang et al.
2020)
@ A
PID-RL
Stooke et al.
2020
G A
Safe RL solved by PID control
SPACE (ours)
& A O M
Safe RL aided by baseline policies with analysis
maximize reward, A constraint-com satisfaction, ? on-policc imitation, B off oofl-polic imitation, w/ expert/optimal demonstrations, @ w/ suboptimal demonstration
Table Comparison to prior work.
Leveraging baseline policies for RI. Prior work has used baseline policies to provide initial infor- mation to RL algorithms to reduce avoid undesirable situations. This is done by either: initializing
the policy with the baseline policy (Driessens & Džeroski, 2004; |mart & Kaclbling 2000; Koppejan
& Whiteson 2011 Abbeel al. 2010 Gao al. 2018 Le et Veceei Vecerik
2017 Jaques
et al. 2019); or providing a teacher's ' advice to the agent (Garcia & Fernández 2012 Quintia Vidal
al. 2013 Abel et al.] 2017| Zhang al.] 2019). However, such works often assume that the
baseline policy is constraint-satisfiin (Sun et al. 2018 (Balakrishna et al.) 2019). In contrast, our
SPACE algorithm safely leverages the baseline policy without requiring it to satisfy the specified constraints.
Pathak et al. 2015): Bartocci et al. [201 also modify the existing known models (policies) based on new conditions in the context of the formal methods. In contrast, we solve this problem using projections in the policy space.
Learning from logged demonstration data. To effectively learn from demonstration data given by the baseline policy, Wu et al. (2019); Brown et al. (2019); Kwon et al. (2020) assess the demon- stration data by either: predicting their cost in the new task using generative adversarial networks (GANs) (Goodfellow et al.) 2014); or directly learning the cost function of the demonstration data. However, these approaches require a large number of training samples from the new task. In addition, the learned cost function is not guaranteed to recover the true one. This may result in driving the agent undesirable situations. In contrast, SPACE controls the distance between the learned and baseline policies to ensure reward improvement and constraint satisfaction.
Table catalogs related work on safe RL and IL. We can differentiate these methods on several key axes: (1) whether they optimize reward and/or ensure cost satisfaction, (2) whether they use on-policy methods (i.e., query the baseline policy) or off-policy methods (i.e., learn from batch of demonstration data). (3) whether the baseline policy or demonstration data is optimal for the agent's s
own objective, and (4) the technical approach of the work.
3 PROBLEM FORMULATION
We frame our problem constrained Markov Decision Process (CMDP) (Altman 1999), defined as tuple < S, AA T, R. C' > Here S is the set of states, AA is the set of actions, and T specifies the conditional probability T(s'), [s, a) that the next state is s' given the current state s and action a. In addition, R S A + R is reward function, and C S x A + R is constraint cost function. The reward function encodes the benefit of using action a in state s, while the cost function encodes the corresponding constraint violation penalty.
A policy is a map from states to probability distributions on A. It specifies that in state s the selected action is drawn from the distribution (s). The state then transits from to s' according to the state transition distribution T(s' a). In doing so, a reward R(s, a) is received and a constraint cost C(s, a) is incurred, outlined above.
3

---

Under review as a conference paper at ICLR 2021
Let (0, denote a discount factor, and T denote the trajectory (su, ag. 81, induced by policy т. Normally, we seek policy æ that maximizes a cumulative discounted reward
J (T( = Erwa
(((ss)
(1)
while keeping the cumulative discounted cost below he
JC(T) = Er- o' S hcc
Here we consider an additional objective. are provided with a baseline policy яn and at each state measure the divergence between (s) and (s)... For example, this could be the KL-divergence D(s) DKL (T()) [ [))).. We then seek a policy that maximizes Eq. [ satisfies Eq. ( and ensures the discounted divergence between the learned and baseline policies is below hD:
JD(T) Eysn IE: Y D(s & hp-
We do not assume that the baseline policy satisfies the cost constraint. Hence allow hD to be adjusted during the learning of π to allow for reward improvement and constraint satisfaction.
Let ( denote the state distribution at time under policy æ. The discounted state distribution induced by ı is defined to be d= = (1 7) Σiz 7 (s/TT) Now bring in the reward advantage function (Kakade & Langford 2002) defined by
(ss a) = (2 a) (s),,,
where (s) = Erww E 7 R(s,, 4,){s0 - s] the expected reward from state under policy and (5, a) = Bysx 1Et 72 RSs, as]so
ag a] is the expected reward from state and initial action a, and thereafter following policy æ. These definitions allow us to express the reward performance of one policy x' in terms of another
JR(T') (R(T) = - swat' _aw [A,
Similarly, we can define (5 a). (s, a) and (s) for the divergence cost, and AT a). (7(s, a) and V (s) for the constraint cost.
4 SAFE POLICY ADAPTATION WITH CONSTRAINED EXPLORATION (SPACE)
We now describe the proposed iterative three step algorithm illustrated in Fig. In what follows, n² denotes the learned policy after iteration k, and M denotes a distance measure between policies. For example, M might be the 2-norm of the difference of policy parameters states of the KL-divergence of the action policy distributions.
average over the
Step 1.
We perform one step of trust region policy optimization (Schulman et al. 2015). This maximizes the reward advantage function A (s, a) over KL-divergence neighborhood of *
b+ arg max soud
[4 a)) s.t. erught (DIL(T(s) (s)] s 6.
(4)
Step We project ++ onto a region around TB controlled by hy to minimize M:
x k+ arg min M(T,, +++ s.t. JD( + 1 evat" aux (A) < hb.
(5)
a
Step 3. We project + onto the set of policies satisfying the cost constraint minimize M: π k+1 arg min M(T + s.t. Jo(T*) - s LAT (s) < lc.
(6)
Control h in Step We select h&, be small and gradually increase h each iteration to expand the region around лg. Specifically, we make 1 11. if:
J > * this increase is to ensure a nonempty intersection between the region around ия and the cost constraint set (feasibility). See Fig. [b).
(b) ( < (n this increase gives the next policy more freedom to improve the reward and the cost constraint performance (exploration). See Fig. [[).
4

---

Under review as a conference paper at ICLR 2021
It remains to determine how to set the new value of DD the cost constraint, and 245 denote the set of policies in the region around Th controlled by h. Then we have the following Lemma.
k++ Let U4 denote the set of policies satisfying
Lemma 4.1 (Updating hp) Ifat step k+1 k+1 O((c((+))nc))) then U1 nut+1 + (feasibility) and U al1 * (exploration).
Proof. See the supplementary material.
Lemma 4.1 ensures that the boundaries of the region around æ determined by hD and the set of policies satisfying the cost constraint intersect. Note that h will become large enough to guarantee feasibility during training. This allows the learning algorithm to explore policies within the cost constraint set while still learning from the baseline policy.
A THEORETICAL ANALYSIS OF SPACE
We will implement a policy as a neural network with fixed architecture parameterized by 0 E g" We then learn policy from the achievable set {T(-10): ing O. Let H and n² = x(-10%) denote the parameter value and the corresponding policy step k. In this setting, it impractical (6). Hence we approximate the reward function and constraints with first order Taylor expan- sions, and KL-divergence with a second order Taylor expansion. We will need the follow- ing derivatives: (1) g Vali smath. amr [ a), (2) a Vel smart ams (s)], (3)
1²3 by iteratively learn-
solve for the policy updates in Eq. (4). ( and
(s)],
ch VoE and"", a~a [4 (s, a)), and (4) Fh V a~d= [DKI( (s)]] Each of these derivatives are taken w.r.t. the neural network parameter and evaluated at @ We also define 28 b = (=* hb and d = Jc( hc. Let - g" PE g and L for the 2-norm projection and L pk for the KL-divergence projection.
We first approximate Eq. Eq. and Eq. 6 using the following approximations:
Step Approximating Eq. yields
arg max gt 0h) s.t. 5 F 0h) 56.
Step 2 and Step 3. Approximating Eq. 55) and 66. similarly yields
g++ $ arg min (0-
g L gh+b) s.t. a T -0- 00) b <
0++ arg min
TT 0 0++ 3) L(O gh+ă) s.t. (0- 0*h d
< 0,
where == for the 2-momm projection and L = t for the KL-divergence projection. We solve these problems using using convex programming (see the supplementary material for the derivation), then for each policy update, we have
u a FR gt +
Fk-1
bb )
g++1 = 6h
+ th F 9" mmxx(0,
--aaa
kT L-lak
(10)
uh F
g" db
max(0,
cc
C L-lck
Algorithm shows the corresponding pseudocode.
Convergence analysis. We consider the following simplified problem to provide a finite-time guarantee of SPACE:
min
f(0),
(11)
eEC,rCa
where f R" + is a twice continuously differentiable function at every point in open set
X' C RR and Ci C X and C2 X' are compact convex sets with CG n C2 * 0. The function f is the
5

---

Under review as a conference paper at ICLR 2021
negative reward function of our CMDP, and the two constraint sets represent the cost constraint set and the region around T..
For vector let ||>|| denote the Euclidean norm. For matrix M let |M denote the induced matrix 2-norm, and o; (M) denote the i-th largest singular value of M.
Assumption 1. We assume:
(1.1) The gradient f is L-Lipschitz continuous over open set X.
(1.2) For some constant G, V/V f0) - G.
(1.3) For some constant H, diam (C1) И and (Ca) H. H.
Assumptions (1.1) and (1.2) ensure that the gradient can not change too rapidly and the norm of the gradient can be too large. Assumption (1.3) implies that for every iteration, the diameter of the region around Th is bounded above by H.
We will need concept of an e-first order stationary point (Mokhtari al. 2018). For > we say that 0 C₁ n C2 an e-first order stationary point (e-FOSP) of Problem under KL-divergence projection
VS(0")) 0*) -, 40 E C1 n22
(12)
Similarly, under the 2-norm projection, l" E EC C2 an c-FOSP of
11 if
(F 0*) c, 40 C1 nC2,
(13)
where F = V and=" (=(()) Notice that SPACE converges to distinct stationary points under the two possible projections (see the supplementary material). With these assumptions, we have the following Theorem.
Theorem 5.1 (Finite-Time Guarantee of SPACE). Under the KL-divergence projection, there exists sequence (n1² such that SPACE converges to an e-FOSP in at most O(e-2) iterations. Moreover, step lo +
s(0kt)) S 1(00) 2(G+ Heg Mey (F*) )2
(14)
Similarly, under the 2-norm projection, there exists a sequence fot*) such that SPACE converges an c-FOSP in at most ()) iterations. Moreover, at step l: +
s(O)+1) S((0))
Lea 2[G
(15)
3
Proof. The proof and the sequence {1/² are given in the supplementary material.
We now make several observations for Theorem 5.1
Algorithm 1 SPACE
Initialize policy TO = ( (00) and trajectory buffer B for l = 0, 2, do
(1) The smaller H is, the greater the decrease in the objective. This ob- servation supports the idea of start- ing with a small value for ln and increasing only when needed.
Run x² π (-)00) and store trajectories in B
Compute g. a, c, F, and d using B
Obtain - using the update in Eq. 10
if () Jc or JR JR( then
(2) Under the Kl--divergence projec- tion, the effect of σı (F*t) ) is negligi- ble. This is because in this case 1/
k++1 Update h/p using Lemma 4.1
Empty B
determined by the KL-divergence between two consecutive updated policies (see the supplementary material). This implies that of is proportional to σı (F*). Hence 01 (F*) does not play major role in decreasing the objective value.
(3) Under the 2-norm projection, the smaller a (F* (i.e., larger o, a..(F'F (F*)) is, the greater the decrease in the objective. This is because a large a (F*) means a large curvature of f in all directions. This implies that the 2-norm distance between the pre-projection and post-projection points small, leading to a small deviation from the reward improvement direction after doing projections (see the supplementary material for visualization).

---

human This is Under review as a conference paper at ICLR 2021
t0 10100
(a) Gather (b) Circle (c) Grid (d) Bottleneck
(c) Car-racing (f) Demo.
Figure 2: (a) Gather task: the agent is rewarded for gathering green apples, but is constrained to collect a limited
number of red apples (Achiam et al. 2017). (b) Circle task: the agent is rewarded for moving in specified wide circle, but constrained to stay within a safe region smaller than the radius of the circle (Achiam et al. 2017). (c) Grid task; the agent controls the traffic lights a grid road network and rewarded for high throughput. but is constrained to let lights stay red for at most 7 consecutive seconds (Vinitsky et al. 2018). (d) Bottleneck task: the agent controls set of autonomous vehicles (shown in red) in traffic merge situation and is rewarded for achieving high throughput, but constrained to ensure that buman-driven vehicles (shown in white) have low speed for no more than 10 seconds (Vinitsky et al. 2018). (e) Car-racing task: the agent controls an autonomous vehicle on race track and is rewarded for driving through as many tiles as possible, but is constrained to use the brakes at most 5 times to encourage a smooth ride (Brockman ct al. 2016). (f) A human player plays car-racing with demonstration data logged.
EXPERIMENTS
Tasks. We compare the proposed algorithm with existing approaches on five control tasks: three tasks with safety constraints ((a), (b) and (e) in Fig. 2). and two tasks with fairness constraints ((c) and (d) in Fig. 2}. These tasks are briefly described in the caption of Fig. [ We chose the traffic management tasks since a good control policy can benefit millions of drivers. In addition, we chose the car-racing task since a good algorithm should safely learn from baseline human policies. For all the algorithms, we use neural networks to represent Gaussian policies. We use the KL-divergence projection in the Mujoco and car-racing tasks, and the 2-norm projection in the traffic management task since it achieves better performance. We use grid-search to select for the paper-parameters. See Appendix for more experimental details.
Baseline algorithms. We compare SPACE with five baseline methods. (1) Fixed-point Constrained Policy Optimization (f-CPO. In f-CPO, the weight À is fixed followed by CPO update (Achiam al. 2017). The f-CPO policy update solves:
gh+11 arg max(g* + Xa DT - 0*) s.t. (0 0b (0- gh) < 6, T 20"(0- (0- ob) + d < 0.
0 F-CPO adds the divergence objective in the reward function. The lack of weight-adjusttmet makes susceptible to suboptimal TB-
(2) Fixed-point PCPO (f- PCP). In f-PCPO, the weight À is fixed followed by PCPO update YYagg
et al. 2020). The f-PCPO policy update solves:
g = arg max
(g* + yT (0- ok) s.t. [ B F* (0- 0h) S 6,
@++1 arg min
(0 g t
10-0") 0h) + d < 0. g s.t. ct (0
f-PCPO also adds the divergence objective in the reward function, but followed by a PCPO update (3) Dynamic-point Constrained Policy Optimization (d-CPO). The d-CPO update solves f-CPO
problem with a stateful X++1 = (2+)² where 0 < B < 1. This is inspired by Rajeswaran al. method to adjust A
(2017). in which they have the same weight-schedull
(4) Dynamic-point PCPO (d-PCPO). The d-PCPO update solves f-PCPO problem with a stateful
x++1_ (x+)², where 0 < 3 1. d-PCPO also uses the same method to learn from TB as in d-CPO. For all the experiments and the algorithms, the weight is fixed and it is set to I.
Baseline policies Tg. To test whether SPACE can safely and efficiently leverage the baseline policy, we used three variants of the baseline policies: (1) suboptimal TB with (c z 0, (2) suboptimal z reward with (c > hc, and (3) near with Jc( z he (i.e., the baseline policy has the same cost constraint as the agent). Note that these πв have different degrees of constraint satisfaction. This is to examine (1) whether SPACE can achieve better learning efficiency given the constraint-satisfyin Ty (i.e, cost and mB meear), and (2) whether SPACE can safely learn from constraint- constraint-voolating TB (i.e. TB reward)) In addition, in the car-racing task we pre- pre-train& ma using an pol-cy algorithm (DDPG (Lillicrap et al., (016)). which directly learns from human demonstration data (Fig. f)) This suboptimal human baseline policy is denoted by n
7

---

Under review as a conference paper at ICLR 2021
Bottleneck
Car-racing
Grid
320
665
80
260
reward
15
Disc. reward
64
R2
240
85
200
180
50
300
150
200 250
300
100
150 20o 250 abe 350 400
52-
75 100 125 130 50
200
policyy updates
policy updates
of policy updates
Undise. divergence cost Undise. constraint cost
Undlsc. constraint cost
Undltc. divergence cost Undlsc, constraint
700-
600
-30
500
co-
800
-10
300
200
20
100
50
200 of policy updates
150
300
150 200 250 300 of policy updates
400
75 130 125 175 200
of policy updates
1000
175
0n
500
800
Undisc. divergence
150
125
60-
600
100
500-
400
20
300
200
50
100 150
200
250
300
100
50
100 150 200 250 300
350
400
25
50 75 100 125 150 175 200 of policy updates
policy updates
policy updates
SPACE (Ours)
f- CPO
PCPO -
d-CPO O d' PCPD +
PCPO (Yang al.)
he
(a(m))
Figure 3: The discounted reward, and the undiscounted constraint cost, the undiscounted divergence cost over policy updates for the tested algorithms and tasks. The solid line is the mean and shaded area is the standard deviation over 5 runs. The baseline policies in the grid and bottleneck tasks are π peaa and the baseline policy in the car-racing task is WB gummann The black dashed line is the cost constraint threshold hc. Overall, we observe that SPACE is the only algorithm that satisfies the constraints while achieving superior reward performance in human has substantially low reward, SPACE still can learn to improve the reward. (We only show the results in these tasks as representative cases since these tasks are more challenging. Please read Appendix for more results. Best viewed in color.)
all cases. Although BB
to simulate that B comes from heuristic or human demonstration data, which are far from optimal. The detailed implementation updating hD can found in Appendix E.I
Overall performance. The learning curves of the discounted reward (JR(T)). the undiscounted constraint cost (JC(T)), and the undiscounted divergence cost (JD(z)) over policy updates are shown for all tested algorithms and tasks in Fig. We use x near in bottleneck and grid tasks, and T in car-racing task. Note that T humman is highly suboptimal to the agent (i.e., (numman) ) is small). The value of the reward is only around 5 as shown in the plot. It does not solve the task at hand. Overall, observe that (1) SPACE achieves least 2 times faster cost constraint satisfaction in all cases even learning from Jumma, (2) SPACE achieves at least 10% more reward in the bottleneck and car-racing tasks compared to the best baseline, and (3) SPACE is the only algorithm that satisfies the cost constraints in all cases. In contrast, PCPO agent cannot robustly satisfy the cost constraints. This because using the baseline policy can provide additional information about the safety constraints. For example, when using cost B that is only optimized for the safety constraints specified by the environment, we can observe the agent trained with SPACE satisfies the constraints more. This shows that using the baseline policy could also help to improve the cost performance.
For example, in the car-racing task we observe that Jp (TT) in SPACE decreases at the initial iteration, but increases in the end. This implies that the learned policy is guided by the baseline policy w in the beginning, but use less supervision in the end. In addition, in the grid task we observe that the final reward of SPACE is lower than the baseline algorithm. This is because that SPACE converges to a policy in the cost constraint set, whereas the baseline algorithms do not find constraint-satiss -atiiiiiittiffiiingg policies. These observations show that SPACE robustly ensure constraint satisfaction while achieving fast learning aided by the potentially suboptimal baseline policy.
human
f-CPO and f-PCPO. f-CPO and f-PCPO fail to improve the reward and have more cost violations. Most likely this is due to persistent supervision from the baseline policy which need not satisfy the cost constraints have high reward. For example, in the car-racing task observe that the value
8

---

Under review as a conference paper at ICLR 2021
of the divergence cost decreases throughout the training. This implies that the learned policy overly evolves to the sub-optimal baseline policy and hence degrades the reward performance.
d-CPO and d-PCPO. d-CPO and d-PCPO improve the reward slowly and have more violations. They do not use projection to quickly learn from лв. For example, in the car-racing task Jp in d-CPO and d-PCPO high compared to SPACE throughout the training. This suggests that simply adding an IL objective in the reward objective is susceptible to a suboptimal g.. Hence these approaches require good selection of the initial value of X and B.
Suboptimal
cost and TB TBwaard The learning curves of JC(T) and the JR((T) over pol- "B
suboptimal base- line policies; TB and TB rewardd and fo is set to 0.5. They do not solve the task at hand.
icy updates are shown for the point gather task in Fig. 4 We
We observe that SPACE robustly sat- isfies the cost constraints in all cases roward
Undisc. constraint cost
1.6
16
14
even when learning from "B In addition, we observe that learn- ing guided by T reward achieves faster
1.2
20
0.8
reward learning efficiency at the initial iteration. This is because JR (T( (Tgward)) > (R( seen in the reward plot. Furthermore, we ob- serve that learning guided by "B achieves faster reward learning effi- ciency the later iteration. This is because that by starting in the in- terior of the cost constraint set (i.e., (C ~ 0 S hc), the agent can safely exploit the baseline policy. The results show that SPACE enables fast convergence to a constraint -attsffins policy, even if T does not meet the constraints itself or does not optimize the reward.
04
0.0
600
policy updates
policy updates
SPACE with in
SPACE with ne he
+
Jelns"
* Jeingman) 3 Jategm * Janggaon
Figure 4: Learning from suboptimal
straint cost and the discounted reward The undiscounted con-
policy updates for the point gather task. solid line the mean and the shaded area the standard deviation over runs. The black dashed line is the cost constraint threshold he. We observe that SPACE satisfics the cost constraints even when learning from the suboptimal π (Best viewed in color.)
7 CONCLUSION
We address the problem of learning constraint-satisfyigg policies given baseline policy from either a teacher agent or demonstration data. The proposed algorithm effectively learns from the potentially suboptimal baseline policy without violating the constraints. SPACE achieves superior reward and cost performance compared with state-of tftte-of-the-art approaches (i.e.. PCPO). We further analyze the convergence of SPACE and provide an effective approach controlling the distance between the learned and baseline policies. Future work will consider learning system dynamics to account for the uncertainty of the environment and hence enable safe learning real applications.
REFERENCES
Pieter Abbeel, Adam Coates, and Andrew Y. Ng. Autonomous helicopter aerobatics through apprenticeship learning. The International Journal of Robotics Research, 29(13):1688-163, 2010.
David Abel, John Salvatier, Andreas Stuhlmüller, and Owain Evans. Agent-agnostic human-in-the- loop reinforcement learning. arXiv preprint arXiv:1701.04079, 2017.
Joshua Achiam, David Held, Aviv Tamar, and Pieter Abbeel. Constrained policy optimization. In Proceedings of the International Conference on Machine Learning, pp. 22-31, 2017.
Eitan Altman. Constrained Markov decision processes, volume 7. CRC Press, 1999.
Guy Avni, Roderick Bloem, Krishnendu Chatterjee, Thomas A. Henzinger, Bettina Könighofer, and Stefan Pranger. Run-time optimization for learned controllers through quantitative games. In International Conference Computer Aided Verification, pp. 630-649. Springer, 2019.

---

Under review as a conference paper at ICLR 2021
Ashwin Balakrishna, Brijen Thananjeyan, Jonathan Lee. Arsh Zahed, Felix Li, Joseph E. Gonzalez, and Ken Goldberg. On- On-policy robot imitation learning from a converging supervisor. In Proceedings of the Conference Robot Learning, 2019.
Ezio Bartocci, Radu Grosu, Panagiotis Katsaros, CR Ramakrishnan, and Scott A. Smolka. Model repair for probabilisticc systems. In International Conference on Tools and Algorithms for the Construction and Analysis of Systems. pp. 326-340. Springer, 2011.
Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojeiech Zaremba. Openai gym. arXiv preprint arXiv: 015400 2016.
Daniel S. Brown, Wonjoon Goo, Prabhat Nagarajan, and Scott Niekum. Extrapolating beyond suboptimal demonstrations via inverse reinforcement learning from observations. In Proceedings of the International Conference on Machine Learning, pp. 783-792, 2019.
Gong Chen and Mare Teboulle. Convergence analysis of a proximal- like minimization algorithm using bregman functions. SIAM Journal on Optimization, 3(3):538-555 543, 1993.
Sonia Chernova and Andrea L. Thomaz. Robot learning from human teachers. Synthesis Lectures Artificial Intelligence and Machine Learning, 8(3):1-121, 2014
Yinlam Chow, Ofir Nachum, Aleksandra Faust, Mohammad Ghavanzadeh, and Edgar Duenez- Guzman. Lyapunov- based safe policy optimization for continuous control. arXiv preprint arXiv:1901.10031, 2019.
Gal Dalal, Krishnamurthy Dvijotham, Matej Vecerik, Todd Hester, Cosmin Paduraru, and Yuval Tassa. Safe exploration in continuous action spaces. arXiv preprint arXiv:1801.087 2018.
Kurt Driessens and Sašo Džeroski. Integrating guidance into relational reinforcement learning. Machine Learning, 57(3):271-300 2004.
Yan Duan, Xi Chen, Rein Houthooft, John Schulman, and Pieter Abbeel. Benchmarking deep reinforcement learning for continuous control. In Proceedings of the International Conference on Machine Learning, pp. 1329-13388 2016.
Michael Fu and A. Prashanth L. senkisensitive reinforcement learning: A constrained optimization viewpoint. arXiv preprint arXiv:/810.09//2/ 2018.
Scott Fujimoto, Edoardo Conti, Mohammad Ghavamzadeh, and Joelle Pineau. Benchmarking batch deep reinforcement learning algorithms. arXiv preprint arXiv:1910.01708, 2019.
Yang Gao. Ji Lin, Fisher Yu, Sergey Levine, and Trevor Darrell. Reinforcement learning from imperfect demonstrations. In Proceedings of the International Conference on Muchine Learning, 2018.
Javier Garcia and Fernando Fernández. Safe exploration of state and action spaces in reinforcement learning. Journal of Artificial Intelligence Research, 45:515-564, 2012.
Javier Garcia and Fernando Fernandez. A comprehensive survey on safe reinforcement learning. Journal of Machine Learning Research, 16(1):1437-148)) 2015.
Ian Goodfellow, Jean Pouget-Abadic, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. In Advances in Neural Information Processing Systems, pp. 2672-2680, 2014.
Mohammadhosein Hasanbeig, Alessandro Abate, and Daniel Kroening, Cautious reinforcement learning with logical constraints. arXiv preprint arXiv:2002. 12156, 2020.
Todd Hester, Matej Vecerik, Olivier Pietquin, Mare Lanctot, Tom Schaul, Bilal Piot, Dan Horgan, John Quan, Andrew Sendonaris, Ian Oshand, et al. Deep q-learning from demonstrations. In Proceedings of the AAAI Conference on Artificial Intelligence, 2018
Jonathan Ho and Stefano Ermon. Generative adversarial imitation learning. In Advances in Neural 2016.
Information Processing Systemx, pp.
10

---

Under review as a conference paper at ICLR 2021
Nils Jansen, Bettina Könighofer, Sebastian Junges, Alex Serban, and Roderick Bloem. Safe Re- inforcement Learning Using Probabilistic Shields (Invited Paper). Igor Konnov and Laura Kovács (eds.), 31st International Conference Concurrency Theory (CONCUR 2020), vol- ume 171 of Leibniz International Proceedings in Informatics (IJPles), pp. 3:1-3:16, Dagstuhl, Germany, 2020. Schloss Seteruuhl-LLiiniiieeettuuuu für Informatik. ISBN 978-3-95977-160- 3. doi: wwtp://.I.....CCC..... voolltexte/2020/2282
URL
Natasha Jaques, Asma Ghandeharioun, Judy Hanwen Shen, Craig Ferguson, Agata Lapedriza, Noah Jones, Shixiang Gu, and Rosalind Picard. Way off-policy batch deep reinforcement learning of implicit human preferences in dialog. arXiv preprint
2019.
Sebastian Junges, Nils Jansen, Christian Dehnert, Ufuk Topcu, and Joost-Pieter Katoen. Safety- constrained reinforcement learning for mdps. In International Conference on Tools and Algorithms for the Construction and Analysis of Systems, pp. 130-146. Springer, 2016.
Sham Kakade and John Langford. Approximately optimal approximate reinforcement learning. In Proceedings of the International Conference Machine Learning, pp. 267-274, 2002.
Rogier Koppejan and Shimon Whiteson. Neuroevolutionarr reinforcement learning for generalized control of simulated helicopters. Evolutionary intelligence, ((4):219-241) 2011.
Minae Kwon, Erdem Biyik, Aditi Talati, Karan Bhasin, Dylan P. Losey, and Dorsa Sadigh. When humans aren't optimal: Robots that collaborate with risk-aware humans. In Proceedings of ACM/EEEE International Conference on Human-Robot Interaction, 2020.
Hoang M. Le, Cameron Voloshin, and Yisong Yue. Batch policy learning under constraints. In Proceedings of the International Conference Machine Learning, pp. 3703-3712, 2019.
Sergey Levine, Chelsea Finn, Trevor Darrell, and Pieter Abbeel. End-to-end training of deep visuomotor policies. The Journal of Machine Learning Research, 17(1):1334-333, 2016.
Timothy P. Lillicrap, Jonathan J. Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra. Continuous control with deep reinforcement learning. In Proceedings of the International Conference on Learning Representations, 2016.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wierstra, and Martin Riedmiller. Playing atari with deep reinforcement learning. arXiv preprint arXiv:13/2.5602, 2013.
Aryan Mokhtari, Asuman Ozdaglar, and Ali Jadbabaie. Escaping saddle points in constrained optimization. In Advances in Neural Information Processing Systems, pp. 3629-3639, 2018.
Katharina Mülling, Jens Kober, Oliver Kroemer, and Jan Peters. Learning to select and generalize striking movements in robot table tennis. The International Journal of Robotics Research, 32(3): 263-279, 2013.
Shashank Pathak, Erika Ábrahám, Nils Jansen, Armando Tacchella, and Joost-Picter Katoen. A greedy approach for the efficient repair of stochastic models. In NASA Formal Methods Symposium, pp. 295-309, Springer, 2015.
Pablo Quintía Vidal, Roberto Iglesias Rodríguez, Miguel Ángel Rodríguez González, and Carlos Vázquez Regueiro. Learning on real robots from experience and simple user feedback. 2013.
Aravind Rajeswaran, Vikash Kumar, Abhishek Gupta, Giulia Vezzani, John Schulman, Emanuel Todorov, and Sergey Levine. Learning complex dexterous manipulation with deep reinforcement learning and demonstrations. Proceedings of Robotics: Science and Systems, 2017.
Stéphane Ross, Geoffrey Gordon, and Drew Bagnell. A reduction of imitation learning and structured prediction to no-regret online learning. In Proceedings of the International Conference on Artificial Intelligence and Statistics, pp. 627-635. 2011.
11

---

Under review as a conference paper at ICLR 2021
John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz. Trust region policy optimization. In Proceedings of the International Conference on Machine Learning, pP- 1897, 2015.
John Schulman, Philipp Moritz, Sergey Levine, Michael Jordan, and Pieter Abbeel. High-dimensional continuous control using generalized advantage estimation. In Proceedings of the International Conference on Learning Representations, 2016.
David Silver, Aja Huang, Chris J. Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Marc Lanctot, et al. Mastering the game go with deep neural networks and tree search. Nature, 529(7587):484, 2016.
William D. Smart and Leslie Pack Kaelbling. Practical reinforcement learning in continuous spaces. In Proceedings of the International Conference Machine Learning, pp. 903-910. Citeseer, 2000.
Adam Stooke, Joshua Achiam, and Pieter Abbeel. Responsive safety in reinforcement learning by pid lagrangian methods. arXiv preprint wrXiv:2007039960 2020.
Yanan Sui, Alkis Gotovos, Joel Burdick, and Andreas Krause. Safe exploration for optimization with gaussian processes. In International Conference on Machine Learning, pp. 997-1005. PMI., 2015.
Wen Sun, Geoffrey J. Gordon, Byron Boots, and Andrew J. Bagnell. Dual policy iteration. In Advances in Neural Information Processing Systems, pp. 7059-7069, 2018.
Chen Tessler, Daniel J. Mankowitz, and Shie Mannor. Reward constrained policy optimization. In Proceedings of the International Conference on Learning Representations. 2018.
Matteo Turchetta, Felix Berkenkamp, and Andreas Krause. Safe exploration finite markov decision processes with gaussian processes. In Advances in Neural Information Processing Systems, pp. 4312-4320, 2016.
Mel Vecerik, Todd Hester, Jonathan Scholz, Fumin Wang, Olivier Pietquin, Bilal Piot, Nicolas Heess, Thomas Rothörl, Thomas Lampe, and Martin Riedmiller. Leveraging demonstrations for deep reinforcement learning on robotics problems with sparse rewards. arXiv preprint arXiv: 107.v81707.08817, 2017.
Eugene Vinitsky, Aboudy Kreidieh, Lue Le Flem, Nishant Kheterpal, Kathy Jang, Cathy Wu, Fangyu Wu, Richard Liaw, Eric Liang, and Alexandre M. Bayen. Benchmarks for reinforcement learning in mixed-autonomy traffic. Proceedings of Conference on Robot Learning, pp. 399-409, 2018.
Akifumi Wachi and Yanan Sui. Safe reinforcement learning in constrained markov decision processes. arXiv preprint arXiv:2008.0663 2020.
Yueh-Hua Wu, Nontawat Charoenphakdee, Han Bao, Voot Tangkaratt, and Masashi Sugiyama. Imitation learning from imperfect demonstration. In Proceedings of the International Conference on Machine Learning, pp. 6818-6827, 2019.
Tsung-Yes Yen Yang, Justinian Rosca, Karthik Narasimhan, and Peter Ramadge. Projection-based constrained policy optimization. In Proceedings of the International Conference on Learning Representations, 2020.
Ruohan Zhang, Faraz Torabi, Lin Guan, Dana H. Ballard, and Peter Stone. Leveraging human guid- ance for deep reinforcement learning tasks. In Proceedings of the International Joint Conference on Artificial Intelligence, pp. 6339-6346, 2019.
Liyuan Zheng and Lillian J. Ratliff. Constrained upper confidence reinforcement learning. arXiv preprint arXiv:2001.090 093777 2020.
12

---

Under review as a conference paper at ICLR 2021
Supplementary Material for Accelerating Safe Reinforcement Learning with Constrain--mismacheel Policies
Outline. Supplementary material is outlined as follows. Section A discusses the impact of
the proposed algorithm. Section B details the proof of updating hp in Lemma 4.1 Section describes the proof of analytical solution SPACE in Eq. {T0). Section D gives the proof of finite-time guarantee of SPACE in Theorem 5. and discuss the difference between the
KL-divergence and 2-norm projections. Section E assembles the additional experiment results
to provide a detailed examination of the proposed algorithm compared to the baselines. These include:
evaluation of the discounted reward versus the cumulative undiscounted constraint cost to demonstrate that SPACE achieves better reward performance with fewer cost constraint violations,
evaluation of performance of SPACE guided by baseline policies with different Jc(TB) B) to demonstrate that SPACE safely learns from the baseline policies which need not satisfy the cost constraint,
ablation studies of using fixed hn in SPACE to demonstrate the importance of using the dynamic hp to improve the reward and cost performance,
comparison of SPACE and other annealing approaches to demonstrate that SPACE exploits the baseline policy effectively,
comparison of SPACE under the KL-divergence and the 2-norm projections to demonstrate that they converge different stationary points,
evaluation of using different initial values of h. to demonstrate that the selection of the initial value does not affect the performance of SPACE drastically.
Section Elasso details the environment parameters, the architectures of policies, computational cost, infrastructure for computation and the instructions for executing the code. Section provides procedure for getting a baseline human policy. Finally, we fill the Machine Learning Reproducibility Checklist in Section G
A IMPACT OF SPACE
Many autonomous systems such as self-driving cars and autonomous robots are complex. In order to deal with this complexity, researchers are increasingly using reinforcement learning in conjunction with imitation learning for designing control policies. The more we can learn from a previous policy (e.g., human demonstration, previous applications), the fewer resources (e.g., time, energy, engineering effort, cost) we need to learn a new policy. The proposed algorithm could be applied in many fields where learning a policy can take advantage of prior applications while providing assurances for the consideration of fairness, safety, or other costs. For example, a dialogue system where an agent intended converse with human, the agent should safely learn from human preferences while avoiding producing biased or offensive responses. In addition, in the self-driving car domain where an agent learns a driving policy, the agent should safely learn from human drivers while avoiding a crash. Moreover, in the personalized robotic assistant setting where an agent learns from human demonstration, the agent should carefully imitate humans without damaging itself or causing harm to nearby humans. These examples highlight the potential impact of the proposed algorithm for accelerating safe reinforcement learning by adapting prior knowledge. This can open the door to advances in lifelong learning and adaptation of agents to different contexts.
One deficiency of the proposed algorithm is that the agent still experiments with cost constraint violation when learning control policies. This is because that any learning-based system needs to experiment with various actions to find a mnnstraint-satisfiing policy. Even though the agent does not violate the safety constraints during the learning phase, any change perturbation of the environment that was not envisioned at the time of programming or training may lead to catastrophic failure during run-time. These systems cannot guarantee that sensor inputs will not induce undesirable
13

---

Under review as a conference paper at ICLR 2021
Region around gg
Region around Tgg
Wooudary
Rhoudury:
h m TD
Cost
* Reward optimal
T" hb
constraint
hb+1
Cost
Reward optimal
RD
constraint
set
Roo
set
(a)
(b)
Figure 5: (a) Illustrating when Th outside the cost constraint set. (b) Illustrating when Ta is inside
the cost constraint set. Aboundary is the policy with Jo (ooonddor)) hc. We aim to bound k++ (i.e., the KL-divergence between Fboundary and TB) by using hip-
consequences, nor can the systems adapt and support safety in situations which new objectives are created. This creates huge concerns in safety-critical applications such as self-driving vehicles and personalized chatbot system.
This raises several questions: What human-agent communication is needed to bring humans in the loop to increase safety guarantees for the autonomous system? How can trust and safety constraints be incorporated into the planning and control processes? How can one effectively identify unsafe plans the baseline policy? We believe this paper will encourage future work to develop rigorous design and analysis tools for continual safety assurance in conjunction with using baseline policies from previous applications.
B PROOF OF UPDATING hn IN LEMMA 4.1
Proof. Based on Theorem in Achiam et al. 2017 for any two policies a and n' we have
2
JC(T') - JT(T) 2
Bowd ama
(s
D
2
Band"
[V
(RL(T'(s))I((S))
2 Jo('' + Jc(())
Exnar (Z(() awd
-
E
Byndd
DKL(T((S)II(())
2 Jc(x)) + Jo(m)
7)2
/ 2
7)2 Bxner
V
E Bundd
(TT((T((s)
> -o((m) + Jc(T)
(- (T))²
(
(16)
2v
The fourth inequality follows from Jensen's inequality. We then define (p((s)) -
Σ, (a()))s) log (a(i)ss)) By Three-point Lemma (Chen Teboulle 1993). for any three policies T. n. and have
E Enn [Ia(T E E
+ Emar (
Eawan (V)(((s))- - (T()
(17)
Let Thoundary denote policy satisfying Jc ( (Toonndary) = ho (i.e., Aboundary is in the boundary of the set of the policies which satisfy the cost constraint (C( hc). Let nt' Aboundary: + π
14

---

Under review as a conference paper at ICLR 2021
and Th in Eq. 16 and Eq. 17
(this is illustrated in Fig. 5) Then have
DEL (houndary (8))(((((()))) - E and
(s)((T(s
DEL FRkL(Touual (Thoundoyy (s)]l=(()))
R sharth (VD(TT((s) ()((T(())))
((T) (Thoundary +²())
(1 7) Jol (boundary) J)(
2x2
E snadoh (Vp(Ta(S)) (x))) ( (boundary(s) 7t (8))
7) (-h ho + +o(TT))
27 12
swatt (Vp((T((s) V)((+<()))) (oonddryys)) 75 (s))
= = he Jo( (T())))
(18)
where (T(ooonndor)) hc.
For the first case in Fig. 5 a), we would like to have 4n nu, + (feasibility). For the second case in Fig. 5(bb,, we would like to have Ug n au * (exploration). These implics that the policy in ++ + 0 and ug nölk + 0.
step k: + 1 is Aooundary which satisfies U1 n nu
Now k+1 snd""
and h = snart (T (s)))
Then Eq. 18 implies
hot 2 o (((=))) + hb.
theoretically ensures hp is large enough to guarantee feasibility and exploration of the agent. Note that we do not provide guarantees for finding an optimal policy. This requires additional assumptions on the objective function (e.g., convexity).
Lemma 4.1
In addition, the goal of this paper is understand and analyze how effectively exploit baseline policy in constrained RL. Without such an analysis, we are not confident in deploying SPACE in real applications. Furthermore, the question of safely using baseline policies has practical potential. is less studied by prior work (Achiam et al. 2017: Chow et al., 2019 Tessler et al.) 2018 Yang et al. 2020
C PROOF OF ANALYTICAL SOLUTION TO SPACE IN EQ. (10)
We first approximate the three stages in SPACE using the following approximations.
Step Approximating Eq. yields
0 = arg max g (0) 0%) s.t.
10 -0--0"TF'' 0²)) 8.
(19)
2
Step 2 and Step 3. Approximating Eq. 5 and 66) similarly yields
0++ # = arg min 00 0 b+ L(O 0²+$) s.t. a aTT(0- (0- 0²) + th 50,
(20)
r+ arg min 0 0 2
L(0
g++3)
k² (0 0* t 0,
(21)
where L I for the 2-norm projection and L Fk for the KL-divergence projecttioo.oo..
15

---

Under review as a conference paper at ICLR 2021
Proof. For the first problem in Eq. semi-definite. Hence is a convex program with quadratic inequality constraints. If the primal problem has feasible point, then Slater's condition is satisfied and strong duality holds. Let 0 and A denote the solutions to the primal and dual problems, respectively. In addition, the primal objective function is continuously differentiable. Hence the Karush-Kuhn Kuhn-Tucker (KKT)) conditions are necessary and sufficient for the optimality of 0 and X*. We now form the Lagrangian:
19 since F is the Fisher Information matrix, it is positive
(( -9 0²) A ( F (0 0%) -6)
And we have the following KKT conditions:
9 F X F
VoL(O' ; =0
(22)
0 8h) F* (0" 0*)
8 ==0
VxC(O" (7 =
(23)
(0" / F (0- 0%)
8 S 0
primal constraints
(24)
X 20 0
dual constraints
(25)
0%) 1h
F0 (0 0%)
complementary slackness
(26)
By Eq. 22). we have l + 1 x
F - g" And by plugging Eq.
(2)
into Eq.
we have
gk pt gh Hence have solution
x
28
gk+$
0t +
gh" Fk
gh
F
g
(27)
which also satisfies Eq.
24
Eq. 25 and Eq. 26
For the second problem in Eq. Lagrangian:
20 we follow the same procedure for the first problem to form the
1 ( 0++ y gh+ + >(a (0-0h) b*).
(( And have the following KKT conditions:
LO L + x =0
Vel(o"
(28)
a 0' 0²) bb
VXC(O", =
(29)
a T 00' 0 + +
primal constraints
(30)
X 2
dual constraints
(31)
(a T (0' 8²) + + =0
complementary slackness
(32)
By Eq. 28 we have 0" t + X k And by plugging Fq. (88) into Eq. 29 and Eq. (31 we
have X" max(( (0, a (0 0 +**
Hence have solution
la
o++ 0" O max(O, a T (0 0%) + 8
)
(33)
a L I-la
which also satisfies Eq.
30 and Eq.
For the third problem in Eq. 21 instead doing the projection on X ++ which is the intermediate
policy obtained in the second step, we project the policy * onto the cost constraint. This allows us compute the projection without too much computational cost. We follow the same procedure for the first and second problems to form the Lagrangian:
L(O, A)
- 0 0² L(O g + 1(c (00 00- +d
1
2
16

---

Under review as a conference paper at ICLR 2021
And we have the following KKT conditions:
LO Lo x
VeC(O" ,1')
(34)
x 0 ) de
VxC(O" x-) =0
(35)
x (0" 0%) d
primal constraints
(36)
X 2 0
dual constraints
(37)
X (c "k T
(0) - 0 d
complementary slackness
(38)
By Eq. 334 we have 0 0 + X - And by plugging Eq. (34 into Eq. (35) and Eq. 37 we
ct 10 0 Ha"
have X max (0,
Hence have solution
L l
T (Q 0% de
g++1 0" O²+ max
)L c
(39)
ch L
c
Hence by combining Eq.
27 Eq.
33
and Eq. 39
we have
gh F g a 7
26
F Fk-1 9 +
28
@ th +
F 9*
max(0,
)L )b'aa* a
1 gh
Fk
gh
L L-
gh Fh gr C² Fk
9" + +
max(0,
L-
L
D PROOF OF FINITE- HINTE-TIME GUARANTEE OF SPACE IN THEOREM 5.1
We now describe the reason for choosing two variants of e-FOSP under two possible projections. Let the denote the step size for the reward, 7h denote the step size for the divergence cost, and nē: denote the step size for the constraint cost. Without loss of generality, under the KL-divergence projection, step SPACE does
g = 8² + F g
T a F ck
Similarly, under the 2-norm projection, at step SPACE does
g++1 0* 1/ g
nha" T/C
With this definition, we have the following Lemma.
Lemma D.1 (Stationary Points for SPACE). Under the KL-divergence projection, SPACE con- verges to stationary point 0* satisfying
Tag "bba" + tnee".
Under the 2-norm projection, SPACE converges to stationary point O* satisfying
Ting" F a" + n)(e))
Proof. Under the KL-divergence projection, by using the definition stationary point we have
0" 0" + F F* g" F a" F vi F. 9" "i F a" + 1ia Fa-le" c²
"n nia" + c².
Under the 2-norm projection, by using the definition of a stationary point we have
0- = 0" + 1 F g" "iaa" - c
n F 9g a + c
"gn = F* "vib + nec)).
17

---

Under review as a conference paper at ICLR 2021
Hence Lemma D.I motivates the need for defining two variants of FOSP.
Before proving Theorem 5.1 we need the following Lemma. Define ()(() arg min |0 - 0 =
#'EC
arg argmin min (0 0²)² L 0'); and L F under the KI--divergence projection, and L I uuder #'EC
the 2-norm projection.
Lemma D.2 (Contraction of Projection Yang et al. 2020 ) For any 0 ( if and only (
0-)² 0-) L(O' )*) s 0, v0' eC.
Proof. (=) Let or -P) for given I E C, O' E C. be such that 0' * 0", and a E (0, 1). Then
we have
100 1 < 0 (0 a0 0²)) i
= 0" 1- + a a 0
2a L 0*)
= (0- - 00-00 L( 0*) S 0' 0" 1
(40)
Since the right hand side of Eq. 40 be made arbitrarily small for given a, have
0 0-)² L(O'' 0*) s 0,v0' EC
v0'
(+) Let 0 E C be such that (0 L() 0*) S 0, A
C. We show that 0 must be the
optimal solution. Let 0 E and 0' * 0". Then we have
||0 0'
1
1
0 0* 0 1 1
110 0" 1
= 0 1 + 1 r- 11. 2 - -0'
L(O' - 0*) - 100 0
0
0 1
> 0
Hence, 0* the optimal solution to the optimization problem, and 0 (0).
We now prove Theorem 5.1 Without loss of generality, on each learning episode SPACE updates the reward followed by the alternation of two projections onto the constraint sets (region around TB and the cost constraint set):
g =0 h² x F ((0 0 (o gh+1= -P-1=,, (0 if 0² EC,, g = gh - 17" F FF
- = =Pe, (@)+)), gh+l = (e ) if 8² EC,,
where 1²th is the step size at step k.
Proof. SPACE under the KL-divergence projection converges to an c-FOSP. Based on Lemma
D.2 under the KL-divergence projection, and setting 0 0² 1/a F V((0)), 0 0 $ and
0 0², we have
@ - (et 1/* F ((()))
g 0
V 0t) < rp
(0 -0
1
0²) yT F² 0 0%)
(41)
Based on the L-Lippshitzz continuity of gradients and Eq. 41
we have
1(0 8) < ((0)) + (/(Ot) (0+ o²) + -
2 1 0²
f((0)) (0 - - F g gh) + L
g - -
2
= -
2 11 g+ 12 - v f( + T (Bh+1
I 2
110
g 1
(42)
18

---

Under review as a conference paper at ICLR 2021
where the equality follows by setting ö (i.e., the size of the trust region) such that
(0 3 / F (0k+ 3 0%)
L1 1 V 3 - ) 1/2 | 0
Again, based on Lemma D.2 for C2 we have
(0 n VS(0") g F (0- 3)+ 00 )
1- FK 0 gkt _ - 3) Fh 0
( 0 z @ gh+ F
( gh+
Vf(0")002 v
/ 1 0 p 3 F (0 -0²+3)
1
1/
f(0h)" 0r) 2 f (0 (Bt+ gh) +
1
(@t g B 3 F (0 g
o/t
2 --I/f(0>)|l 11 - 081|
|| 0 g
npp
Do (o 2 - +
||0h+ - 1%1
(43)
nyt
where in the last two inequalities we use the property of the norm. Before reaching c-FOSP, Eq. implies that
D01(F")
E 2 min V
Tf (0- 8h) > -G
110h 0k| -
DEC₂
1/t
g²+ 0²|
(44)
G
Dr: FK
n
Based on Eq.
42 and Eq.
44
we have
L
f(0k+h) - f(0t)
g =
0-1l2= Vf(0kt 100-110000 -
11ght1
-
2
2
Le
S <((00)
3/ - gkt3)
1 - -
2( + Do (F )
2
(45)
Based on the L-Lipschitz continuity of gradients, for the projection to the constraint set C1 we have 1. ( 3)+ + ; 11ght1 g++ 1p2
f(0ht1) f(0++8) vf(a+t3 (
(46)
Combining Eq.
45 with Eq. 46
we have
L
f(e > f(th)
(47)
2(G + Do (Ft)
Hence it takes O(E-²) iterations to reach e-FOSP.
SPACE under the 2-norm projection converges to an e-SSPP. Based on Lemma D.2 under the
2-norm projection, and setting 0 = 0² T/² Fk vf(0), 0" = o++ 3 and O' 0² we have
(0* B r²² F - ((k) g 8) 0 +(F* v (
((@*))))++++ - @h) f x
c g T - g*))
(48)
19

---

Under review as a conference paper at ICLR 2021
Based on the L-Lipschitz comtiniu of gradients and Eq. (48 have
$ VS(0")) 0*) + L 10++ 0+
s f(00)) (F* " (0++ 0²) + +Q+
+++ +
L 10k 1
-0112
1 (okt @ 0%) + Q 2
1
1 0%
-(00))
110+ 0²112 V 8 7(0 gl+
| - - 1
2
2
(49)
where Q == -
(0k+ - which represents the difference
between the gradient and the nature gradient, and the equality follows by setting 8 (i.e., the size of the trust region) such that
10++ 3 0+
L
0
Q + ff () gh+ 1 0 0
Again, based on Lemma
D.2 for 0 E C2 we have
1 F (V(OO) gh+ 3) 0++ 8) 00
(-(FF~~(((0)) V((())) g++ S -00 - ( (4+
V[(0")T 0 > 10h g 0k+i)
V/(0")"F 0
g
10t g++ 3)+ 335((0) (0 00+
VI 9 0%) Vf( p 1g 0%) + t @ - - - 0kt
1
2 --I1S5(0) 1110+3 0%
g
@|||| 0 0++$
0
2 -Go ) 1010 0¹1
(50)
where in the last two inequalities we use the property of the norm. Before reaching an e-FOSP, Eq. 50) implies that
2 min (S(OO)''pp pp (0 (0-0")
D (Fo
/p 110 0*11
OEC₂
10b+3
0%1
2 (Go (Fk 11
(51)
+ 7p
Based on Eq. 49) and Eq, (5). we have
f( s f(eh)
L
1 - -btt))
I
_
11 0g
2
2 gx+3)=
LE"
3 - 1 11ght1
L 3
s(0h) 2(Gor (Fr ) 1212
(52)
Based on the L-Lipschitz continuity of gradients, for the projection to the constraint set C₁ we have
5(0h+2) s(0++3) (0 3)) ((*++1 gk+3) + 1 110ht2 g++ 1|2
(53)
Combining Eq.
52 with Eq.
53
we have
Lea
f(gh+1)= < s((0))
(54)
2(Go) ) ))
Hence it takes O iterations to reach an e-FOSP.
20

---

Under review as a conference paper at ICLR 2021
Constraint set
Ok
θ k+ 2
(a) SPACE under the KL-diveegeece projection
Constraint set
Ok
0 k 3
(b) SPACE under the 2-norm projection
Figure 6: Update procedures for SPACE under the KL and 2-norm projections with two possible Fisher information matrices. A lower objective value is achieved at the darker green area. Red and orange ellipses are F with two different spectra of singular values. Red and orange dots are resulting updated points under these two spectra of F*s. (a) A red ellipse has smaller on (F*) and an orange ellipse has larger d1 (F*). Both ellipses have the same o, (F*). The two resulting 0 are similar. (b) A red ellipse has larger o, (F*) and an orange ellipse has smaller o, (F*). Both ellipses have the same (F*). @ with larger o (F*) (red dot) has greater decrease of the objective value.
Comments on Assumption 1.3. In the paper, we assume that both the diameters of the cost constraint set (Ci) and the region around иy (C2) are bounded above by H. This implies that given small value for hD, the convergence speed is determined by how large the constraint set is. This allows us do an analysis for the algorithm. In practice, we agree that this assumption too strong and leave it as a future work for improvement.
We now provide visualization in Fig. under two possible projections. For each projection, we consider two possible Fisher information matrices. Please read the caption for more detail. In Fig. G(a) we observe that since the reward improvement and projection steps use the KL-divergence, the resulting two update points with different a (F*) are similar. In addition, under the 2-morm projection, the larger a (F)) is, the greater the decrease in the objective. This is because that large o, (F*) implies large curvature of f in all directions. Intuitively, this makes the learning algorithm confident about where to update the policy decrease the objective value greatly. Geometrically, a large o, (F%) makes the 2-norm distance between the pre-pu pre-proeection and projecrooottion points small, leading to small deviation from the reward improvement direction. This is illustrated in Fig. 6 (b. We observe that since F* determines the curvature of f and the 2-norm projection is used, the updated point with larger o, (F) (red dot) achieves more improvement of the objective value. These observations imply that the spectrum of the Fisher information matrix does play major role in SPACE under the KL-divergence projection, whereas affects the decrease of objective value in SPACE under the 2-norm projection. Hence we choose either KL-divergence or 2- 2-norm projections depending on the tasks achieve better performance.
Interpretation on Theorem 5.1
E ADDITIONAL EXPERIMENT RESULTS
E. IMPLEMENTATION DETAILS
Mujoco Task Achiam et al. 2017). functions are
In the point circle and ant circle tasks, the reward and cost
T 1
222 31
R(s) =
+
||| [x11000)
d
21

---

Under review as a conference paper at ICLR 2021
Safe area
d
Unsafe
area
Xlim
Figure 7: The environment of the circle task (adapted from Achiam et al. (017)). The agent receives the maximum reward while staying in the safe area by following the red dashed line path.
and
C(s) = 1[ > Tlim]:
where 21 and I2 are the coordinates in the plane, v is the velocity of the agent, and d, Tlim are environmental parameters that specify the safe area. The agent is rewarded for moving fast in wide circle with radius of d, but is constrained to stay within a safe region smaller than the radius of the cirele in cooordiinatee Flim d. For the point agent, we use d = and Zlim 2.5; for the agent, we use d = 5 and Fiim = 1. The environment is illustrated in Fig.
In the point gather task, the agent receives reward of +10 for gathering green apples, and cost of 1 for gathering red apples. Two green apples and eight red apples are placed in the environment at the beginning. In the ant gather task, the agent receives a reward of +10 for gathering green apples, and a cost of 1 for gathering red apples. The agent also gets reward of - 10 for falling down to encourage smooth moving. Eight green apples and eight red apples are placed the environment at the beginning.
For the point and ant agents, the state space consists of the positions, orientations, velocities, and external forces applied to the torso and joint angles. The action space is the force applied to joints.
Traffic Management Task (Vinitsky et al. 2018). In the grid task, the state space, action space, reward function, and cost function are illustrated as follows.
(1) States:
Speed, distance the intersection, and edge number of each vehicle. The edges of the grid are uniquely numbered so the travel direction can be inferred. For the traffic lights, we return and corresponding green red for each light, number between [0, fewitch] indicating how long until a switch can occur, and and indicating the light is currently yellow. Finally, we return the average density and velocity of each edge.
(2) Actions: list of numbers a = -[-1, 1] where n is the number of traffic lights. If a, >> 0 for traffic light it switches, otherwise no action is taken.
(3) Reward: The objective of the agent is to achieve high speeds. The reward function is
R(s) max Ptarget
Vtarget vll.0)
Utarget
where Utarget is an arbitrary large velocity used to encourage high speeds and E RR is the velocities of l: vehicles in the network.
(4) Cost: The objective of the agent is to let lights stay red for at most 7 consecutive seconds. The cost function is
C(s)
Σ 1 rte > 7],
1=1
where lireed is the consecutive time that the light i is in red.
22

---

Under review as a conference paper at ICLR 2021
In the bottleneck task, the state space, action space, reward function, and cost function are illustrated as follows.
(I) States: The states include: the mean positions and velocities of human drivers for each lane for each edge segment, the mean positions and velocities the autonomous vehicles on each segment, and the outflow of the system in vehicles per/hour over the last 5 seconds.
For a given edge-segment and a given lane, the action shifts the maximum speed of all the autonomous vehicles in the segment from their current value. By shifting the max-speed to higher or lower values, the system indirectly controls the velocity of the autonomous vehicles.
(2) Actions:
(3) Reward: The objective of the agent is to maximize the outflow of the whole traffic. The reward function is
i=t R(s:) = Σ
Texit (i)
A Allne 500
where Rexit (t) is the number of vehicles that exit the system at time-step i, and Piae is the number of lanes.
(4) Cost: The objective of the agent is to let the velocities of human drivers have lowspeed for no more than 10 seconds. The cost function
Alamaan
C(s)
Σ 1[t 10],
where 7human is the number of human drivers, and 1,,oow is the consecutive time that the velocity of human driver / is less than 5 m/s. For more information, please refer to Vinitsky al. (2018).
Car-racing Task. In the car-racing task, the state space, action space, reward function, and the cost function are illustrated as follows.
(1) States: It is high-dimensional space where the state is 96 96 tensor of raw pixels. Each pixel is in the range of [0, 255].
(2) Actions: The agent has 12 actions in total: E A
{(asteer a a brake) Jaster 1-1,0, 0, 1}, a0aa E {0, 1), a brake E {0, 0.2] where atoer is the steering angle, ages is the amount of gas applied, and a the amount of brake applied.
(3) Reward: In each episode, we randomly generate the track. The episode is terminated if the agent reaches the maximal step traverse over 95% of the track. The track is discretized into 281 tiles. The agent receives a reward of 1000 for each tile visited. To encourage driving efficiency, the agent receives penalty of per-time step.
28I
(4) Cost: The cost is to constrain the accumulated number of brakes to encourage smooth ride.
Architectures and Parameters. For the gather and circle tasks we test two distinct agents: a point-mass (S C R9 A C R22) and an ant robot (S 1232 C 188). The agent in the grid task is S C 1556 A C R2 and the agent in the bottleneck task is S C R 141 A C 220 Finally, the agent in the car-racing task is S C x66x96x3 A C R
For the simulations in the gather and circle tasks, we use a neural network with two hidden layers of size (64, 32) represent Gaussian policies. And we use the KL-divergence projection. For the simulations in the grid and bottleneck tasks, we use neural network with two hidden layers of size (16, 16) and (50, 25) to represent Gaussian policies, respectively. And we use the 2-norm projection. For the simulation in the car-racing task, we use convolutional neural network with two convolutional operators size 24 and 12 followed by a dense layer size (32, 16) to represent Gaussian policy. And we use the KL-divergence projection. The choice of the projections depends on the task itself, we report the best performance among two projections. We use tanh as an activation function for all the neural network policies. In the experiments, since the step size is small, we reuse the Fisher information matrix of the reward improvement step in the KL-divergence projection step to reduce the computational cost.
23

---

Under review as a conference paper at ICLR 2021
Parameter
PC
PG
AC
AG
Gr
BN
CR
Reward factor
0.995
0.995
0.995
0.995
0.999
0.999
0.990
Constraint cost dis. factor TC
1.0
1.0
1.0
1.0
1.0
1.0
1.0
Divergence cost dis. factor Yo
1.0
1.0
1.0
1.0
1.0
1.0
1.0
step size 6 GAA GAA AGAE
10-4
10-4
10
10
10
10
10
0.95
0.95
0.95
0.95
0.97
0.97
0.95
1.0
1.0
0.5
0.5
0.5
1.0
1.0
0.95
0,95
0.95
0,95
0.90
0.90
0.95
Batch size
50,000
50,000
100,000
100,000
10,000
25,000
10,000
Rollout length
50
15
500
500
400
500
1000
Constraint threshold he
5
0.5
0.2
0
5
Divergence cost threshold b Number of policy updates
1,000
1,200
2,500
1,500
200
300
600
Table 2: Parameters used in all tasks. (PC: point circle, PG: point gather, AC: ant circle, AG: ant
gather, Gr: grid, BN: bottleneck, and CR: car-racing tasks)
SPACE (Ours)
F-PCPO
E-CPO
d-PCPO
d-CPO
M/C
Time
M/C
Time
M/C
Time
M/C
Time
M/C
Time
M/C
Time
B
22.14
25.2
31.9
25.5
32.6
35.1
51.2
48.4
49.4
55.5
55.9
AG
B 386.9
110.5
C
268.6
C
235.1
138.2
187.5
AC
B
148.9
94.0
C
222.6
C
214.6
177.4
151.2
Gr
A
105.3
91.4
A
88.2
A
58.7
116.8
A
115.3
BN
A
257.7
181.1
162.9
161.6
259.3
275.6
C
993.5
971.6
1078.3
940.1
1000.4
981.0
Table 3: Real-time in seconds for one policy update for all tested algorithms and tasks. (PC: point circle, PG: point gather, AC: ant circle, AG: ant gather, Gr: grid, BN: bottleneck, and CR: car-racing tasks)
We use GAE-À approach (Schulman al., (016) to estimate ( AT(ss a), and (s). For the simulations in the gather, circle, and car-racing tasks, we use neural network baselines with the same architecture and activation functions as the policy networks. For the simulations in the grid and bottleneck tasks, we use linear baselines. The hyperparameters of all algorithms and all tasks are in Table 2
We conduct the experiments three separate machines: machine A has an Intel Core i7-4770HQ CPU, machine has an Intel Core i7-6850K CPU, and machine has an Intel Xeon X5675 CPU. We report real-time (i.e., wall-clock time) in seconds for one policy update for all tested algorithms and tasks in Table We observe that SPACE has the same computational time as the other baselines.
For the most intensive task, i.e., the car-racing task, the memory usage is 6.28GB. The experiments are implemented rllab (Duan et al. 2016), a tool for developing RI. algorithms. We provide the link the code: httpp:://// /tta::///siess goog cww/coocc..coooooo eww spacealcceeee
Comments on the rationale behind when to increase hn- The update method of hp is empir- ically designed to ensure that the value of the cost does not increase (i.e., (c(a*) S (J and the reward keeps improving (i.e., ( 2 JR(m*=1)) after learning from T.. Lemma 4.1 theoretically ensures hp is large enough guarantee feasibility and exploration of the agent.
Implementation of Updating h Lemma 4.1 shows that k++1 should be increased at least by ((Jo(=*) - h))²)) + ht if Je(x²) > [ or Jn(=*) < J=z(=*=1) at step We now provide the practical implementation. For each policy update check the above conditions. If one of the conditions satisfies, we increase h by setting the constant to 10, i.e., 10- -
hy. In practice, we find that the performance of SPACE not affected by the selection of the constant. Note that we could still compute the exact value h k+1 as shown in the proof Lemma 4.1 However, this incurs the computational cost.
24

---

Under review as a conference paper at ICLR 2021
375
350
66
Disc. reward
325
Disc. reward
Disc. reward
300
62
275
250
30
58
225
20-
200
10
175
2000 4000 B0oU 8000 1000012000 Cumu, undisc. cons, cost
10a
500 1000 1500 2000 2500 3000 Cumu. undisc. cons. cost
Cumu. undisc. cons. cost
(a) Bottleneck
(b) Car-racing
(c) Grid
SPACE (Ours)
- f- CPO
PCPCPO d CPO d PCPO
PCPO (Yang al.)
The discounted reward vs. the cumulative undiscounted constraint cost over policy updates for the tested algorithms and tasks. The solid line is the mean over runs. SPACE achieves the same reward performance with fewer cost constraint violations in all cases. (Best viewed in color.)
Figure 8:
Comments on learning from multiple baseline policies TB. In our setting, we use one Tg. This allows us do theoretical analysis. One possible idea for learning from multiple Tg is to compute the distance to each πB. Then, select the one with the minimum distance to do the update. This ensures that the update for the reward in the first step is less affected by n. And the analysis we did can be extended. We leave it as future work for developing this.
Comments on refining the PCPO agent's policy (Yang et al,, 2020) directly. Fine-tuning the pre-trained policy directly might result in lower reward and cost violations. This is because that the pre-trained policy has a low entropy and it does not explore. We empirically observe that the agent pre-trained with the baseline policy yields less reward in the new task (i.e., different cost constraint thresholds lc)) as illustrated in Section E.2 In contrast, the SPACE agent simultancously learns from the baseline policy while ensuring the policy entropy high enough to explore the environment.
Comments on the feasibility of getting safe baseline policies. In many real-world applications such as drones, we can obtain baseline policies modeled from the first principle physics, or pre- train baseline policies in the constrained and safe environment, use rule-based baseline policies. Importantly, we not assume the baseline has be a "safe policy" can be heuristic that ignores safety constraints. This is one of the main motivations for our algorithm: to utilize priors from the baseline which may be unsafe, but guarantee the safety of the newly learned algorithm according to the provided constraints.
Instructions for Reprodueibility. We now provide the instructions for reproducing the results. First install the libraries for python3 such as numpy, scipy. To run the Mujoco experiments, get the licence from https: www. robot www.s///weeeeeeeeeeeeeeeeeeeee. m To run the traffic management experiments, install FL.WW simulator from httpt::t////.. To run the car-racing experiments, install OpenAl Gym from https:ttpp... / thu. com openai/ gym Our implementation is based on the environment from Achiam et al. (2017), please down- load the code from ht /tt/tttttuue thub com/ jachiam/..mmmm cpo, The code is based on rllab (Duan) et al. 2016), install the relevant packages such as theano software /atarr//teere (ww.arrr//hhano// Then, download SPACE code from and place the codes on the designated folder instructed by Readme.tx txt on the main folder. Finally, go the example folder and execute the code using python command.
htt.ssiitsssso.elleeeeeeeeo gwc.le.........ooo....o......... com/
wiew/apaceneee
E.2 EXPERIMENT RESULTS
Baseline policies. We pre-train the baseline policies using a safe RL algorithm. Here we also consider three types of baseline policies: (1) suboptimal n with (m R 0, (2) suboptimal a
reward with Jc(n reward) > hc, and (3) m hear with (m as he Note that these TB have different degrees of constraint satisfaction.
The Discounted Reward ys. the Cumulative Undiscounted Constraint Cost (see Fig. 8
To
show that SPACE achieves higher reward under the same cost constraint violations (i.e., learning
25

---

Under review as a conference paper at ICLR 2021
cunstraint-satisfiinn policy without violating the cost constraint lot), we examine the discounted reward versus the cumulative undiscounted constraint cost. The learning curves of the discounted reward versus the cumulative undiscounted constraint cost shown for all tested algorithms and tasks in Fig. g We observe that in these tasks under the same value of the reward, SPACE outperforms the baselines significantly with fewer cost constraint violations. For example, in the car-racing task SPACE achieves 3 times fewer cost constraint violations at the reward value of 40 compared to the best baseline PCPO. This implies that SPACE effectively leverages the baseline policy while ensuring the constraint satisfaction. In contrast, without the supervision of the baseline policy, PCPO requires much more constraint violations to achieve the same reward performance as SPACE. In addition, although the fixed-point and the dynamic-poie approaches use the supervision of the baseline policy, the lack of the projection step makes them less efficient in learning a constraint-satistying policy.
To examine whether SPACE can safely learn from the baseline policy which need not satisfy the cost constraint, we consider two baseline policies: Coet and r rewward" The learning curves of the undiscounted constraint cost, the discounted reward, and the undiscounted divergence cost with two possible baselines over policy updates are shown for We observe that in the point gather and point cirele tasks,
Comparison of Baseline Policies (see Fig. 9
all tested algorithms and tasks in Fig. 9 the initial values of the cost are larger than ly (i.e., (c() > hc). Using T allows the learning algorithm to quickly satisfy the cost without doing the extensive projection onto the cost constraint set. For example, in the point circle task we observe that learning guided by Tg mpss quickly satisfies the cost constraint. In addition, we observe that in the ant gather and ant circle tasks, the initial values reward of the cost are smaller than la (i.e.. (c(T)) < l.). Intuitively, we would expect that using Th allows the agent to quickly improve the reward since the agent already satisfies the cost constraint in the beginning. In the ant gather task we observe that SPACE guided by TB rewward does improve the reward more quickly at around 200 iteration. However, we observe that the agent guided by the both baseline policies achieve the same final reward performance in the ant gather and ant circle tasks. The reason is that using dynamic hD allows the agent to stay away from the baseline policy. This makes the baseline policy less influential in the end. As result, the reward improvement mostly comes from the reward improvement step of SPACE if the agent starts in the interior of the cost constraint set (i.e., Jc(TT) S he).
Fixed lDD (see Fig. 10). To understand the effect of using dynamic h when learning from sub-optimal baseline policy, we compare the performance of SPACE with and without adjusting hp- The learning curves of the undiscounted constraint cost, the discounted reward, and the undiscounted divergence cost over policy updates are shown for all tested algorithms and tasks in Fig. T0, We observe that SPACE with fixed hn converges to less reward. For example, in the ant circle task SPACE with the dynamic DD achieves 2.3 times more reward. The value of the divergence cost in the ant circle task shows that staying away from the baseline policy achieves more reward. This implies that the baseline policy in the ant circle task is highly sub-optimal to the agent. In addition, we observe that in some tasks the dynamic hp does not have much effect on the reward performance. For example, in the point gather task SPACE achieves the same reward performance. The values of the divergence cost in the point gather task decrease throughout the training. These observations imply that the update scheme of hn is critical for some tasks.
Comparison of SPACE vs. d-CPO, d-PCPO and the Pre-training Approach (see Fig. Il.. To show that SPACE is effective in using the supervision of the baseline policy, we compare the performance of SPACE to the dynamic-point and the pre-training approaches. In the pre-training approach, the agent first performs the trust region update with the objective function being the divergence cost. Once the agent has the same reward performance as the bascline policy (i.e., Jn(n*) R Jn(nB) for some k), the agent performs the trust region update with the objective function being the reward function. The learning curves of the undiscounted constraint cost, the discounted reward, and the undiscounted divergence cost over policy updates are shown for all tested algorithms and tasks in Fig. I1 We observe that SPACE achieves better reward performance compared to the pre- pre-training approach in all tasks. For example, in the point circle, ant gather and ant circle tasks the pre- pre-training approach seldom improves the reward but all satisfies the cost constraint. This implies that the baseline policies in these tasks are highly sub-optimal in terms of reward performance. In contrast, SPACE prevents the agent from converging to a poor policy.
26

---

Under review as a conference paper at ICLR 2021
Undisc constraint cost
16
Undisc divergence cost
14
Disc. reward
12
10
0.8
0.6
0.0
800
1000
800
400
of policy updates
of policy updates
# of policy updates
(a) Point gather
Undise. constraint cost
Undise. divergence cost
40
80-
Disc. reward
30
30-
15
20
10
20-
10
0
200
800
1000
600
800
600
1000
policy updates
policy updates
policy updates
(b) Point circle
Undise. constraint cost
X-.. Yoos w0
Undisc. divergence cost
120
Disc. reward
100
450
200
40
300
0.0
20
200
400 600 800 100012001400
200 400 600 a00 100012001400 0
200
400 600 800 20001
policy updates
of policy updates
pollcy updates
(c) Ant gather
Undisc. constraint cost
10
Undisc divergence cost
20 88 Ek-
Disc. reward
100
a00
20"
109
10-1-0
200
10-2
10
10
500
1000
1500
2000
7500
500
1000
1500
2000
7500
500
1000
1500
2000 7500
# of policy updates
of policy updates
# of policy updates
(d) Ant circle
SPACE mg
SPACE with rgwword
Jeingaann
*
Joingrannty
Figure 9: The undiscounted constraint cost, the discounted reward, and the undiscounted divergence cost over policy updates for the tested algorithms and tasks. The solid line is the mean and the shaded area is the standard deviation over 5 runs. SPACE ensures cost constraint satisfaction guided by the baseline policy which need not satisfy the constraint. (Best viewed in color.)
In addition, we observe that in the point gather task the pre-training approach achieves the same reward performance as the baseline policy, whereas SPACE has a better reward performance compared to the baseline policy. The pre-training approach does not keep improving the reward after learning from the baseline policy. This is because that after pre-training with the baseline policy, the entropy of the learned policy small. This prevents the agent from trying new actions which may lead to better reward performance. This implies that pre- teeiriiinng approach may hinder the exploration of the learning agent on the new environment. Furthermore, in the car-racing task we observe that using pre-training approach achieves the reward performance SPACE but improves reward slowly,
27

---

Under review as a conference paper at ICLR 2021
Undisc constraint cost
16-
Undisc. divergence cost
0.9
14
Disc. reward
12
0.8
0.5
800
1000
800
# of policy updates
of policy updates
# of policy updates
(a) Point gather
Undise. constraint cost
30
Undisc. divergence cost
25
25
90
Disc. reward
20
20-
30
15
20:
5
10-
700
400
600
800
1000
0
700
400
600
800
1000
200
400
600
800
1000
# of policy updates
of policy updates
# of policy updates
(b) Point circle
Undisc. constraint cost
Undisc. divergence cost
60
500
0.25
Disc. reward
400
0.15
0.20
80
300
200
20
100
0.05
100
700 400 600 200 100m 700 400
700 400 600 son 100017801400 0
700 400 600 800 1200000004000 of policy updates
of policy updates
policy updates
(c) Ant gather
Undisc. constraint cost
Undisc. divergence cost
350
Disc. reward
300
250
20
200
10
1500
policy updates
of policy updates (d) Ant circle
policy updates
Undisc. constraint cost
Undisc. divergence cost
1.000
700
600
Disc. reward
500
600
400
300
200
20-
200
100
0-
100
300
400
200
400
400
# of policy updates
# of policy updates
# of policy updates
(c) Car-racing
SPACE
SPACE with fixed ho hc Ja((ta
Figure 10: The undiscounted constraint cost, the discounted reward. and the undiscounted divergence cost over policy updates for the tested algorithms and tasks. The solid line is the mean and the shaded area the standard deviation over runs. SPACE with the dynamic hp achieves higher reward. (Best viewed in color.)
and the pre-training approach has cost constraint violations than SPACE. This implies that jointly using reinforcement learning and the supervision of the baseline policy achieve better reward and cost performance.
28

---

Under review as a conference paper at ICLR 2021
For d-CPO and d-PCPO, in the point and ant tasks we observe that both approaches have comparable or silently better reward and cost performance compared to SPACE. However, in the car-racing task we observe that d-CPO cannot improve the reward due to slow update procedure for satisfying the cost constraint, whereas d-PCPO has a better reward performance. These observations imply that the projection steps in SPACE allow the learning agent to effectively and robustly learn from the baseline policy.
Comparison of SPACE under the KI-divergence and the 2-norm Projections (see Fig, 12. Theorem 5.T shows that under the KL-divergence and 2-norm projections, SPACE converges to different stationary points. To demonstrate the difference between these two projections, Fig. 12 shows the learning curves of the undiscounted constraint cost, the discounted reward, and the undiscounted divergence cost over policy updates for all tested algorithms and tasks. In the Mujoco tasks, we observe that SPACE under the KL-divergence projection achieves higher reward. For instance, in the point gather task the final reward is 25% higher under the same cost constraint satisfaction. In contrast, in the traffic management tasks, we observe that SPACE under the 2-norm projection achieves better cost constraint satisfaction. For instance, in the grid task SPACE under the 2-norm projection achieves a lower reward but more cost constraint satisfaction. In addition, in the bottleneck task SPACE under the 2-norm projection achieves more reward and cost constraint satisfaction. These observations imply that SPACE converges to different stationary points under two possible projections depending on tasks.
To understand the effect of the initial value of h.: we test SPACE with three different initial values: hい = L, 1 5, and h3 25 in the ant circle and car-racing tasks. The learning curves of the undiscounted constraint cost, the discounted reward, and the undiscounted divergence cost over policy updates are shown for all tested algorithms and tasks in Fig. B In both tasks, we observe that the initial value of hD does not affect the reward and the cost performance significantly (i.e., the mean of learning curves lies in roughly the same standard deviation over the initialization). In addition, the value of the divergence cost over three h% are similar throughout the training. These observations imply that the update scheme of h in SPACE is robust to the choice of the initial value of hg-
Initial 119 (see Fig. 13
However, in the car-racing task we observe that the learning curves of using a smaller h& tend to have higher variances. For example, the standard deviation of h2 = 1 in the reward plot is times larger than the one with /4, = 25. This implies that SPACE may have reward performance degradation when using smaller initial value of h. One possible reason is that when the distance between the learned and baseline policies is large, using small value of hD results in an inaccurate projection (i.e., due to approximation errors). This causes the policy follow a zigzag path. We leave the improvement of this in future work.
F HUMAN POLICIES
We now describe the procedure for collecting human demonstration data in the car-racing task. A player uses the right key, left key, up key and down key to control the direction, acceleration, and brake of the car. The human demonstration data contain the display of the game (i.e., the observed state), the actions, and the reward. We collect 20 minutes of demonstration data. A human player is instructed stay in the lane but does not know the cost constraint. This allows us to test whether SPACE can safely learn from the baseline policy which need not satisfy the cost constraints. We then use an off-policy algorithm (DDPG) trained on the demonstration data to get the baseline human policy. Since the learned baseline human policy does not interact with the environment, its reward performance cannot be better than the human performance. Fig. 14 shows the procedure.
Implementation Details of DDPG. We use DDPG as our off- pollcy algorithm. We use a convolu- tional neural network with two convolutional operators of size 24 and 12 followed by dense layer of size (32, 16) to represent a Gaussian policy. A Q function shares the same architecture of the policy. The learning rates of the policy and Q function set to 10-4 and 10-3, respectively.
29

---

Under review as a conference paper at ICLR 2021
G THE MACHINE LEARNING REPRODUCIBILITY CHECKLIST (VERSION 1.2, MAR. 27 2019)
For all models and algorithms presented, indicate if you include
A clear description of the mathematical setting, algorithm, and/or model:
Yes, please see the problem formulation in Section the update procedure for SPACE in Section [ and the architecture of the policy in Section
An analysis of the complexity (time, space, sample size) of any algorithm:
Yes, please the implementation details in Section
E.1
A link to downloadable source code, with specification of all dependencies, including external libraries:
Yes, please see the implementation details in Section
For any theoretical claim, check if you include:
A statement of the result:
Yes, please see Section 4 and Section
A clear explanation of any assumptions:
Yes, please see Section and Section
A complete proof of the claim:
Yes, please see Section Section C and Section D
For all figures and tables that present empirical results, indicate if you include:
A complete description of the data collection process, including sample size:
Yes, please Section E.1 for the implementation details.
A link to a downloadable version of the dataset or simulation environment:
Yes, please see Section E. for the simulation environment.
An explanation of any data that were excluded, description of any pre-processing step:
It's not applicable. This is because that data comes from simulated environments.
An explanation of how samples were allocated for training validation / testing:
It's not applicable. The complete trajectories (i.e., data) is used for training. There is validation set. Testing is performed in the form of online learning approaches.
The range of dyper-parameters considered, method to select the best hyper-parameter used to generate results:
configuration, and specification of all
Yes, we randomly sclect five random seeds, and please see Section E.1 for the imple- mentation details.
The exact number of evaluation runs:
Yes, please see Section E for the implementation details.
A description of how experiments were run:
Yes, please see Section for the implementation details.
A clear definition of the specific measure or statistics used to report results:
Yes, please see Section
Clearly defined error bars:
Yes, please see Section
HHer
is link the
list:
https://ww.cc. www.:/c............mm ca/ jpinaaui
VeprocuciiiliiyCheee
30

---

Under review as a conference paper at ICLR 2021
A description of results with central tendency (e.g., mean) variation (e.g., stddev):
Yes, please see Section 6
A description of the computing infrastructure used:
Yes, please see Section E.1 for the implementation details.
31

---

Under review as a conference paper at ICLR 2021
Undisc. constraint cost
Undisc. divergence cost
14-
0.8
Disc. reward
10-
0.6
0.4
200
600
800 1000
1200
200
400 600
800
1000
1200
200
400
600
800
1000
1200
of policy updates
of policy updates
# of policy updates
(a) Point gather
Undisc. constraint cost
Undisc. divergence cost
25
30
Disc. reward
25
20
20
30
1.5
20
10
10-
200
400
600
800
1000
200
400
600
800
1000
200
400
600
800
1000
of policy updates
of pollcy updates
# policy updates
(b) Point circle
Undisc. constraint cost
80
Undisc. divergence cost
300
0.3
Disc. reward
60
400
50
0.2
300
30
50
200
20
a00 600 8do 100012001400
200 600 800 100012001400
100
200
300
400
500
600
policy updates
policy updates
policy updates
(c) gather
Undisc. constraint cost
25
Undisc. divergence cost
a00
20
Disc. reward
1.5
300
10
200
of policy updates
# of policy updates (d) Ant circle
of policy updates
Undisc. constraint cost
Undisc. divergence cost
700
900
500-
Disc. reward
500
80
700
400
30
600
300
200
20
500
100
0
100
200
300
400
500
1010
200
300
400
500
100
200
300
400
500
# of policy updates
# of policy updates
# of palicy updates
(e) Car- Car-racing
SPACE (Ours)
d CPO
PCPO
Pretraining
Ja(na)
Figure 11: The undiscounted constraint cost, the discounted reward, and the undiscounted divergence cost over policy updates for the tested algorithms and tasks. The solid line is the mean and the shaded area the standard deviation over runs. SPACE outperforms d-CPO, d-PCPO and the pre-training approach in terms of the efficiency of the reward improvement and cost constraint satisfaction. (Best viewed in color.)
32

---

Under review as a conference paper at ICLR 2021
Undisc. constraint cast
Undise. divergence cost
20.0
reward
17.5
15.0
12.5
0.5
2.5
0.4
0.0
800
1000
1200
1000
1200
400
1000
1200
policy updates
policy updates
policy updates
(a) Point gather
Undisc. constraint cost
Undise. divergence cost
25
25-
Disc. reward
20
20
30
20
10
0
200
400
600
800
1000
200
400
600
800
1000
200
400
600
800
1000
of policy updates
of pollcy updates
# policy updates
(b) Point circle
Undisc. constraint cost
70
Undlsc. divergence cost
Disc. reward
120
20
100
15
62
80
10
60
56
40
20
25
50
75 100 125 150 175 200
25
50
75
100 125 150 175
200
25
50
75
100 125
175 200
# of policy updates
# of policy updates
# of policy updates
(c) Grid
Undisc. constraint cost
100
320
Undisc. divergence cost
300
100
Disc reward
260
80
260
240
40
220
40
200
180
20
160
# of policy updates
# of policy updates
of policy updates
(d) Bottleneck
SPACE, 2 norm proj.
SPACE, KL - proj.
he (m(mp)
The undiscounted constraint cost, the discounted reward, and the undiscounted divergence cost over policy updates for the tested algorithms and tasks. The solid line is the mean and the shaded area is the standard deviation over 5 runs. SPACE converges to differently stationary points under two possible projections. (Best viewed in color.)
Figure 12:
33

---

Under review as a conference paper at ICLR 2021
Undisc. constraint cost
20.0
Undisc. divergence cost
15.0
Disc. reward
12.5
7.5
5.0
2.5
0.0
-2.5
500
1000
1500
2000
2500
500
1000
1500
2000
2500
500
1000
1500
2000
2500
policy updates
policy updates
of policy updates
(a) Ant circle
Undisc. constraint cost
100
Undisc. divergence cost
700
900
600
Disc. reward
800
500
700
60
400
600
300
20
100
300
0
100
200
300
400 500 600
0
100
200
300
400
500
600
100
200
300
400 500 800
of policy updates
of policy updates
of policy updates
(b) Car-racing
SPACE, =
SPACE, =5
SPACE, ng =8=22
jaima)
Figure 13: The undiscounted constraint cost, the discounted reward, and the undiscounted divergence cost over policy updates for the tested algorithms and tasks. The solid line the mean and the shaded area is the standard deviation over 5 runs. We observe that the initial value of hy does not affect the reward and the cost performance significantly. (Best viewed in color.)
Off-policy algorithms (DDPG)
SPACE
nt human
.a,r)
Figure 14: Procedure for getting baseline human policy. We ask a human to play the car-racing game. He/She does know the cost constraint. The trajectories (i.e., display of the game, the action, and the reward) are then stored. A human policy is obtained by using an off-policy algorithm (DDPG) trained on the trajectories.
34


Reviews:
[{"review_id": "uaAb9mN7dDQ", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper considers the constrained Markov Decision Process (CMDP) problem where the goal is to maximize cumulative reward while satisfying the safety constraint on cumulative cost. Solving CMDP is challenging, and this paper proposes a shortcut by utilizing a given baseline policy. The idea of the proposed SPACE algorithm is to have three steps for each iteration of policy optimization. The first step is a trust region optimization step to optimize reward, the second step projects the policy to a region close to the given baseline policy, and the third step projects the policy to the constraint set. \n\nCompared with other CMDP methods, the step of projecting close to the baseline policy allows the policy to quickly improve if the baseline policy is decent. Compared with some behavior cloning methods, the steps of reward optimization and constraint satisfaction allows the policy to achieve good final performance. I feel the ideas of the proposed SPACE algorithm is good, but I have some concerns for the current version.\n\n- The constraints (5) and (6) in Step 2 and Step 3 need to be further discussed. From the description of Step 2, the constraint (5) should be $J_D(\\pi) \\leq h^k_D$ for the region around $\\pi_B$. One can replace $J_D(\\pi)$ by $J_D(\\pi^k) + \\frac{1}{\\gamma} \\mathbb{E}_{s\\sim d^\\pi, a \\sim \\pi}[A^{\\pi^k}_D(s, a)]$ by using the performance difference formula, but the state distribution is different from the distribution in (5). It seems like (5) could be some approximation, but how it relates to the desired region and how the guarantee may be affected should be discussed. Similar for (6).\n\n- In Lemma 4.1, only a big-O value for the update of $h^{k+1}_D$ is provided and no description on what the big-O hides. Since this value is required in SPACE, it's not clear how to implement the algorithm without the specific value. According to the proof of Lemma 4.1 in the appendix, this value seems to depend on some expectation whose computation may not be trivial.\n\n- The practical version of SPACE described in Algorithm 1 does not solve the optimization problems (4)-(6). Since it uses (7) to update, the actual three steps of SPACE are the approximations (16)-(18) in the appendix. I think the actual steps should be stated in the main text with discussion on the effect of the approximations.\n\n- For experiments, it is very confusing by introducing f-(P)CPO and d-(P)CPO without any explanation on the weight and the weighted objective. It is also unclear what is the value of $h_C$ and not possible to evaluate constraint violations of each methods.\n\n- The comparisons with f-(P)CPO and d-(P)CPO is interesting, but the comparison with these baselines provides little idea for the main messages of the proposed method. SPACE is supposed to learn quicker compared to other CMDP methods by using the baseline policy, but all the compared methods actually use the baseline policy in some non-efficient way. Instead, the comparison with original CPO and PCPO will be much more meaningful as they might show the accelerated learning of SPACE, but all methods might have similar final reward/cost performance given enough training samples. Another possible comparison would be with other behavior cloning methods given a good baseline policy.\n\n\nAfter reading the authors' response, I would like to thank the authors to clarify some of the my questions. But my main concerns still remain so I plan to keep my marginally below score. The value of the key bound in Lemma 4.1 is unknown and it's not clear about the effect of the described empirical trick. For the experiments, the proposed SPACE algorithm indeed outperforms all considered baselines. But performing better than all baselines in the final performance seem to indicate that the choice of baselines and experiment design do not present a fair comparison. One would expect the final performance of a reasonable baseline algorithm to be similar to SPACE because the idea of the proposed method is to \"accelerating learning\" not achieving better final performance. The poor final performance of the baselines seems to be due to the inappropriate adaption of existing methods.\n\n\n\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "TSpPoHQ_F8G", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary of review:\nA clear problem statement & technical approach for an important problem, supported by positive empirical results, and some theoretical analysis.\n\nDescription:\nThe paper proposes a 3-part approach to constrained RL:   (1) perform policy optimization, (2) minize distance to the baseline policy, (3) project the policy into the policy space that satisfies the constraints.  The analysis shows better empirical performance, and a finite-sample guarantee.\n\nStrengths:\n-\tThe paper’s overall approach is easy to understand, and decomposes in a few conceptually simple steps.\n-\tI appreciated that the experiments considered tasks with both safety constraints and fairness constraints.  The latter are seldom considered in RL papers, yet very important in practice, so it’s nice to see this considered here.\n-\tThe paper includes a good range of baseline comparisons.\n\nWeaknesses:\n-\tThe theoretical analysis uses several simplifying assumptions (e.g. approximation of the reward fn and constraints, and those in Assumption 1.)  What is the impact of these? Are they typically met in benchmarks?  What is the usefulness of Theorem 5.1?  I wasn’t sure what to make of this result, what it was significant or useful.  Can Eqn 12 give one intuition of when to use more / less data?  \n-\tKey experimental details are missing.  How many seeds did you use for the experiments?  Why show standard deviation rather than standard error?  How were the hyper-parameters selected?\n\nQuestions:\n-\tTable 1: There are many more works on constrained MDPs. What was your inclusion/exclusion criteria for this table?\n-\tWhy is the Disc. reward for SPACE and f-PCPO going down in Grid (Fig.3, top right plot)?  This should be explained.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "Lq9atmRSkj", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary\n\nThe authors propose SPACE, an RL algorithm for learning a policy that maximizes reward while satisfying given constraints in a setting where a baseline policy is provided. They design a three-step update rule for learning such a policy and provide a finite-sample analysis of the resulting method in a simplified setting. They report numerical results in several domains that show how the proposed approach outperforms competitive baselines.\n\nPros\n\n- The paper is very well-written and easy to follow.\n- The experimental evaluation is performed in complex domains. The results are significant and well-described. Full details are provided in the appendix to enable reproducibility.\n\nCons\n\n- The paper might lack some novelty. The approach seems quite incremental with respect to Yang et al. 2020 (though I am not very familiar with that work to precisely judge this). In particular, handling the additional constraint due to the baseline policy seems not that different from how the \"cost constraint\" is handled, and indeed the two approaches have a very similar update rule. The experimental domains seem also the same (except for the car racing one which was not present in Yang et al. 2020).\n- The setting considered for the finite-sample analysis might be overly-simplified. In particular, the analysis seems not really \"finite-sample\" but rather \"finite-time\", in the sense that it is carried out for a finite number of learning steps in a standard optimization setting where all functions (e.g., the gradients) can be exactly evaluated and are not estimated from finite samples.\n\nDetailed comments\n\n1. While it is intuitive why we need to project the policy onto the set of policies satisfying the constraint in Eq. 2, it was not very clear to me why we need to perform a projection to stay close to the baseline policy (especially since the actual \"closeness\" h_D is changed by the algorithm). It seems that, after all, what we care about is to stay close to this policy during the initial phases of learning (if possible) and slowly stop caring about this as learning proceeds. So could we simply regularize the standard RL objective with the distance wrt the baseline policy and make the regularization parameter fade over time? Would that perform worse than projecting?\n\n2. Lemma 4.1 provides a formal justification for increasing h_D over time. How is the actual increase performed in practice? Is there any fixed \"increase value\" or is the theoretical value from the lemma used? \n\n3. Could you provide some intuition on why the finite-sample bound for SPACE with KL divergence scales with the maximum eigenvalue of F^k while the one for l2-norm scales with the minimum eigenvalue of the same matrix?\n\n4. It seems that the work of Yang et al. 2020 also reports a similar convergence guarantee as the one derived here. Could the authors clarify what are the technical difficulties in extending such a result to this setting? It seems to me that after the simplifications the two considered settings are quite similar.\n\n5. In the experiments, the authors mention that \"PCPO agent cannot robustly satisfy the cost constraints\". Why does this happen? Doesn't PCPO handle the constraints in the same way as SPACE?\n\n6. Why is there no baseline for comparison in Figure 4?\n\nSome minor comments:\n\n- In the caption of Table 1, I would say \"w/ expert/optimal demonstrations\" to be more precise and \"constraint-cost satisfaction\" (cost alone might be interpreted as the negative reward)\n- Third line of page 8: \"gird\" -> \"grid\"\n\nOverall comment\n\nOverall I believe that the paper is interesting and it reports good results. However, at the present time, I am not sure about the novelty wrt Yang et al. 2020, so I am quite borderline. I will be happy to increase my score after the authors have clarified my doubts.\n\nReferences\n\nTsung-Yen Yang, Justinian Rosca, Karthik Narasimhan, and Peter J. Ramadge. Projection-based\nconstrained policy optimization. In Proceedings of the International Conference on Learning\nRepresentations, 2020.", "extra_scores": {}, "extra_text": {}}, {"review_id": "30Mic_-TkMn", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "update after rebuttal: the authors answered all my questions to my satisfaction.\n\n* Summary and Contribution\n\nThis work presents a novel approach to safe reinforcement learning. In particular, in line with several other works, the others propose to start from a baseline policy, which is then improved. Three key steps are identified: (1) updating the baseline to maximize expected reward, (2) measuring and controlling the ``distance'' between the new policy and the baseline, and (3) projecting the policy to satisfy given safety constraints. The authors provide both the an theoretical analysis and a number of experiments. \n\n\nReasons for Score\nI believe this is a nice paper with good contribution and valid evaluation, but some parts can be improved.\n\nStrengths\n\n- A novel method for safe RL\n- The baseline policy is not required to already satisfy the safety constraints\n- A thorough theoretical analysis\n- Convincing, though small-scale, experiments\n\nWeaknesses\n\n- Some related work should be discussed. The statement that all other approaches using a baseline do require a safe baseline is not entirely true and needs further detailed discussion. \n- Better motivation why this is Safe RL -> How to 'safely' obtain a baseline?\n- The approach seems like a (nice) collection of already established building blocks. \n\n\nQuestions for Authors\n\n- I would like a better discussion on why it is realistic to have a baseline policy. In a (physical) safety-critical scenario, any baseline may be either so bad that the approach is not effective anymore, or it may be obtained using actual unsafe interaction with the environment.\n\n- A key step of the approach seems to be 'Trust region policy optimization' work, which is well known. How would you argue that your work is really novel, and not just reusing that approach? \n\n- The paper states that other approaches using a baseline require it to be safe. I do not think that is true, see the detailed comment.\n\n- Please compare your work to the literature on model repair, see the detailed comments.\n\n\nDetailed comments\n\n- safe baselines, please discuss: \n\n[1] makes two assumptions: a set of safe states is given, and there is regularity for the safety function. My understanding is that these assumptions allow the agent to explore within the safe region until it learns enough to explore new areas. Also, [2] and [3] seem to make the same assumptions. [3] states that \"Our approach [...] does not require a backup policy but only a set of initially safe states from which the agent starts to explore.\"\n\n\n\n[1] Akifumi Wachi, Yanan Sui 2020\n   Safe Reinforcement Learning in Constrained Markov Decision Processes.\n   In International Conference on Machine Learning (ICML) 2020\n\n[2] Sui, Y., Gotovos, A., Burdick, J. W., and Krause, A.\n  Safe exploration for optimization with Gaussian processes. \n  In International Conference on Machine Learning (ICML), 2015\n\n[3] Turchetta, M., Berkenkamp, F., and Krause, A. \n  Safe exploration in finite Markov decision processes with Gaussian processes. \n  In Neural Information Processing Systems (NeurIPS), 2016.\n\n\n- model repair, please discuss\n\nIn the essence, and admittedly, the work [4,5]listed below is from the formal methods community, so it may just not be known for ICLR. Yet, what happens: A model (for instance, a policy), is 'repaired' to satisfy (temporal logic) safety constraints, with minimal distance to the original policy. At least a discussion is in order.  \n\n[4] Shashank Pathak, Erika Ábrahám, Nils Jansen, Armando Tacchella, Joost-Pieter Katoen:\nA Greedy Approach for the Efficient Repair of Stochastic Models. NFM 2015: 295-309\n\n[5] Ezio Bartocci, Radu Grosu, Panagiotis Katsaros, C. R. Ramakrishnan, Scott A. Smolka:\nModel Repair for Probabilistic Systems. TACAS 2011: 326-340\n\n\n- general related work:\n\nThere is some other related work both on Safe RL that could be discussed.\n\n\nPrashanth L, A., and Michael Fu. \"Risk-sensitive reinforcement learning: A constrained optimization viewpoint.\" arXiv preprint arXiv:1810.09126 (2018)\n\nZheng, Liyuan, and Lillian J. Ratliff. \"Constrained upper confidence reinforcement learning.\" arXiv preprint arXiv:2001.09377 (2020).\n\nSebastian Junges, Nils Jansen, Christian Dehnert, Ufuk Topcu, Joost-Pieter Katoen:\nSafety-Constrained Reinforcement Learning for MDPs. TACAS 2016: 130-146\n\nNils Jansen, Bettina Könighofer, Sebastian Junges, Alex Serban, Roderick Bloem:\nSafe Reinforcement Learning Using Probabilistic Shields. CONCUR 2020: 3:1-3:16\n\nGuy Avni, Roderick Bloem, Krishnendu Chatterjee, Thomas A. Henzinger, Bettina Könighofer, Stefan Pranger: Run-Time Optimization for Learned Controllers Through Quantitative Games. CAV (1) 2019: 630-649\n\nMohammadhosein Hasanbeig, Alessandro Abate, Daniel Kroening:\nCautious Reinforcement Learning with Logical Constraints. AAMAS 2020: 483-491\n\n\n\n\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper is about a reinforcement learning algorithm that operates in a Constrained MDP and is provided with a baseline policy.
Although the reviewers acknowledge that the paper has some merits (well-written, clearly organized, significant empirical evaluation, reproducible experimental results), some concerns have been raised about the novelty of the proposed solution and of its theoretical analysis. The reviewers feel that the authors' responses have not properly addressed all their doubts.
The paper is borderline and I think that it is not ready for publication in the current form.
I encourage the authors to update their paper following the reviewers' suggestions and try to submit it in one of the forthcoming machine learning conferences. 
Decision: Reject