Projection-Based Constrained Policy Optimization
Authors: Tsung-Yen Yang
Justinian Rosca
Karthik Narasimhan
Peter J. Ramadge
Venue:  (2020)
Keywords: Reinforcement learning with constraints
Safe reinforcement learning

Abstract: We consider the problem of learning control policies that optimize a reward function while satisfying constraints due to considerations of safety, fairness, or other costs. We propose a new algorithm - Projection-Based Constrained Policy Optimization (PCPO), an iterative method for optimizing policies in a two-step process - the first step performs an unconstrained update while the second step reconciles the constraint violation by projecting the policy back onto the constraint set. We theoretically analyze PCPO and provide a lower bound on reward improvement, as well as an upper bound on constraint violation for each policy update. We further characterize the convergence of PCPO with projection based on two different metrics - L2 norm and Kullback-Leibler divergence. Our empirical results over several control tasks demonstrate that our algorithm achieves superior performance, averaging more than 3.5 times less constraint violation and around 15% higher reward compared to state-of-the-art methods.

Published as a conference paper at ICLR 2020
PROJECTION-BASEE CONSTRAINED POLICY OPTIMIZATION
Tsung- Yen Yang Princeton University cy3@princeton.eds
Justinian Rosca
Siemens Corporation, Corporate Technology
justinian. rosca s emens.
Karthik Narasimhan
Peter Ramadge
Princeton University
Princeton University
karthikn@ppinnotonn.edl
ABSTRACT
We consider the problem of learning control policies that optimize a reward func- tion while satisfying constraints due to considerations of safety, fairness, or other costs. We propose new algorithm. Projection- -ased Constrained Policy Opti- mization (PCPO). This is an iterative method for optimizing policies in two-step process: first step performs a local reward improvement update, while the sec- ond step reconciles any constraint violation by projecting the policy back onto the constraint set. We theoretically analyze PCPO and provide a lower bound on re- ward improvement, and upper bound constraint violation, for each policy update. We further characterize the convergence of PCPO based on two different metrics: I norm and Kullback-Leibler divergence. Our empirical results over several control tasks demonstrate that PCPO achieves superior performance, aver- aging more than 3.5 times less constraint violation and around 15% higher reward compared to state-of-the-art methods
INTRODUCTION
Recent advances in deep reinforcement learning (RL) have demonstrated excellent performance on several domains ranging from games like Go (Silver et al.) 2017) and StarCraft (AlphaStar) 2019) to robotic control (Levine et al. 2016). In these settings, agents allowed explore the entire state space and experiment with all possible actions during training. However, in many real- world applications such self-driving cars and unmanned aerial vehicles, considerations of safety, fairness and other costs prevent the agent from having complete freedom to explore. For instance, an autonomous car, while optimizing its driving policies, must take any actions that could cause harm to pedestrians or property (including itself). In effect, the agent is constrained to take actions that do not violate a specified set of constraints on state-action pairs. In this work, we address the problem of learning control policies that optimize a reward function while satisfying predefined constraints.
The problem of policy learning with constraints is more challenging since directly optimizing for the reward, as in Q-Learning (Mnih et al., 2013) or policy gradient (Sutton al., 2000), will usu- ally violate the constraints. One approach is to incorporate constraints into the learning process by forming a constrained optimization problem. Then perform policy updates using a conditional gradient descent with line search to ensure constraint satisfaction (Achiam al. 2017). However, the base optimization problem can become infeasible if the current policy violates the constraints. Another approach is to add hyperparameter weighted copy of the constraints the objective func- tion (Tessler et al. 2018). However, this incurs the cost extensive hyperparameter tuning.
To address the above issues, we propose projection- boasee constrained policy optimization (PCPO). This is an iterative algorithm that performs policy updates two stages. The first stage maximizes reward using trust region optimization method (e.g. TRPO (Schulman al. 2015al without
For code the project website: httpss://ssteeeee googl e. wtwpwwww.www.ttttttt http://eew...ooooooo//////////// r2000 pppo

---

Published as a conference paper at ICLR 2020
constraints. This might result in new intermediate policy that does not satisfy the constraints. The second stage reconciles the constraint violation (if any) by projecting the policy back onto the constraint set, Le.. choosing the policy in the constraint set that is closest to the selected interme- diate policy. This allows efficient updates to ensure constraint satisfaction without requiring a line search (Achiam et al. (017) adjusting a weight (Tessler al. 2018). Further, due the projec- tion step, PCPO offers efficient recovery from infeasible (i.e. constraint-violatin states (c.g., due approximation errors), which existing methods do not handle well.
We analyze PCPO theoretically and derive performance bounds for the algorithm. Specifically, based on information geometry and policy optimization theory, we construct lower bound on reward improvement, and an upper bound on constraint violations for each policy update. We find that with relatively small step size for each policy update, the worst-case constraint violation and reward degradation are tolerable. We further analyze two distance measures for the projection step onto the constraint set. We find that the convergence of PCPO affected by the smallest and largest singular values of the Fisher information matrix used during training. By observing these singular values, we can choose the appropriate projection best suited to the problem.
Empirically, we compare PCPO with state-of-the-art algorithms on four different control tasks, in- cluding two Mujoco environments with safety constraints introduced by Achiam et al. (0017) and two traffic management tasks with fairness constraints introduced by Viiitsky et al. (2018). In all cases, the proposed algorithm achieves comparable or superior performance to prior approaches, averaging more reward with fewer cumulative constraint violations. For instance, across the above tasks, PCPO achieves 3.5 times fewer constraint violations and around 15% more reward. This demonstrates the ability of PCPO robustly learn constraint-satisfynng policies, and represents step towards reliable deployment of RL in real problems.
2 PRELIMINARIES
We frame our policy learning as a constrained Markov Decision Process (CMDP) (Altman 1999), where policies will direct the agent maximize the reward while minimizing the cost. We define CMDP as the tuple < S, A, T, R, C >; where S is the set of states, A is the set of actions that the agent take, T S A S
[0, 1] is the transition probability of the CMDP, R S x A R is the reward function, and C' : S x A + R is the cost function. Given the agent's 's current state the policy (aas)) S + A selects an action a for the agent take. Based on and the agent transits to the next state (denoted by s') according to the state transition model T(s" (s, a). and receives the reward and pays the cost, denoted by R(s, a) and C(s, a), respectively.
We aim to learn policy π that maximizes cumulative discounted reward, denoted by
(T) = E,
Σ Y' R(s. az)].
t=0
while satisfying constraints, iee. making cumulative discounted cost constraint below a desired threshold h, denoted by
oe JC = [ E''Css ac]] < h.
where 7 is the discount factor, is the trajectory (r (so, ao s1, )), and is shorthand for showing that the distribution over the trajectory depends on т so nt, ~ (aarsst), $141 ~ T(ss_1|9;: az), where p is the initial state distribution.
Kakade & Langford (2002) give an identity to express the performance of policy x in terms of the advantage function over another policy
- J"((''-J'((7)
E 1- and (s) a)),
where d' is the discounted future state distribution, denoted by d (s) = (1 (1-7) E1- = s/m), and (s) the reward advantage function, denoted by AT Q7 (s). Here Qh(s, a) = E.-r - 7 R(s,, a=)[so 8,00 a is the discounted cu- mulative reward obtained by the policy given the initial state and action a, and V (s) =
2

---

Published as a conference paper at ICLR 2020
BY Et=o R(s), as)ss s) is the discounted cumulative reward obtained by the pol- icy given the initial state Similarly, we have the cost advantage function As a) = (c(s. (s), where a)(s,a) = E E ('Cs,, 3, = a), and VT = E Ei=o ('C(s, ss]
3 PROJECTION-BASEI CONSTRAINED POLICY OPTIMIZATION
To robustly learn constraint satisfyyin policies, develop PCPO trust region method that performs policy updates corresponding to reward improvement, followed by projections onto the constraint set. PCPO, inspired by pro- jected gradient descent, is composed of two steps for each update, a reward improvement step and projection step (This is illustrated in Fig.
k Constraint set k+1
Trust region
Figure 1: Update procedures for PCPO. In step one (red arrow), PCPO follows the reward im- provement direction green). In step two (blue arrow), PCPO projects the policy onto the constraint set (light orange).
Reward Improvement Step. First, we opti- mize the reward function by maximizing the reward advantage function A (s, a) subject to Kullback-Leibler (KL) divergence constraint. This constraints the intermediate policy * to be within a 6-neighbourhood of th:
the trust region (light
arg max
E snutt
[A (s, a)]
s.t. E
[DRL ( ||| [+]] < 8.
(2)
This update rule with the trust region, fx E touk DKL (T | [s]] S 8}. is called Trust Region Policy Optimization (TRPO) (Schulman al.
constraints the policy changes diver- gence neighhorhood and guarantees reward improvement.
2015a).
Projection Step. Second, we project the intermediate policy h onto the constraint set by mini- mizing distance measure D between * and
h+1 arg min
D(T, *
s.t. (C( + E erud
[A a)] < h.
(3)
amx
The projection step ensures that the constraint constraint-satisfiing policy *+1 is close to * We consider two distance measures D: 1,2 norm and KL divergence. In contrast, using KL divergence projection in the probability distribution space allows us to provide provable guarantees for PCPO.
3.1 PERFORMANCE BOUND FOR PCPO WITH KL DIVERGENCE PROJECTION
In safety-critical applications such autonomous cars, one cares about how worse the performance of system evolves when applying a learning algorithm. To this end, for PCPO with KL divergence projection, we analyze the worst-case performance degradation for each policy update when the current policy -² satisfies the constraint. The following theorem provides a lower bound on reward improvement, and an upper bound on constraint violation for each policy update.
grhtt = Theorem 3.1 (Worst-case Bound on Updating Constraint-satisffing Policies). Define e
max Ea- (s, a]]], and c-111 - max Eg [A (s, a)]. If the current policy x² satis- fies the constraint, then under KL divergence projection, the lower bound on reward improvement, and upper bound on constraint violation for each policy update are
V2b (1-7)²- and JC (xx+++1)= < h V2ōTez k+1
-
(1 - (1-7)2
where 8 is the step size in the reward improvement step.
3

---

Published as a conference paper at ICLR 2020
Proof. See the supplemental material.
Theorem 3.1 indicates that if 8 is small, the worst-case performance degradation is tolerable.
Due to approximation errors or the random initialization of policies, PCPO may have a constraint- violating update. Theorem 3.1 does not give the guarantee on updating a constraint-violatiee Hence we analyze worst-case performance degradation for each policy update when the current policy n² violates the constraint. The following theorem provides lower bound on reward im- provement, and an upper bound on constraint violation for each policy update.
policy.
Theorem 3.2 (Worst-case Bound on Updating Constraint- max IE 1 T4 (8,a)],, a = max [a [AT (8, a)]], b+ max J (C(TT())))))))))))()) - h), and ØKL 2 Ta where is the gradient of the cost advantage function and H is the Hessian of the KL divergence constraint. the current policy n violates the constraint, then under KL divergence projection, the lower bound on reward improvement and the upper bound on constraint violation for each policy update are
.k++ = Policies). Define Ent
2(8 + b+ bx²
J (1( (T((T²)
(1- 2 26 ( + b+ O R41
and J ( hh
(1 71-
where ō is the step size in the reward improvement step.
Proof. See the supplemental material.
Theorem 3.2 indicates that when the policy has greater constraint violation (b+ increases), its worst- case performance degradation increases. Note that Theorem 3.2 reduces to Theorem [.1 if the current policy * satisfies the constraint (b+ 0). The proofs of Theorem 3.1 and Theorem 3.2 follow from the fact that the projection of the policy is non-expansive, i.e, the distance between the projected policies smaller than that of the unprojected policies. This allows us to measure it and bound the KL divergence between the current policy and the new policy.
PCPO UPDATES
For large neural network policy with many parameters, it is impractical to directly solve for the PCPO update in Problem and Problem due the computational cost. However, with small step size 6, we can approximate the reward function and constraints with first order expansion, and approximate the KI. divergence constraint in the reward improvement step, and the KI. divergence measure in the projection step with a second order expansion. We now make several definitions:
g VØE
[AT" (s, a)] is the gradient of the reward advantage function,
Soud amx
VoE
andt" [A (s, a)] is the gradient of the cost advantage function,
H B [KK. [ is the Hessian of the KI. divergence constraint (H is also called the 50,00,
Fisher information matrix. It is symmetric positive semi-definite), b = (m( h is the constraint violation of the policy t² and is the parameter of the policy.
Reward Improvement Step. We linearize the objective function Th subject to second order approximation the KL divergence constraint in order to obtain the following updates:
g++1 arg max
g" (0 8*)
s.t.
2 00 0h H 0²) 5.
(4)
4

---

Published as a conference paper at ICLR 2020
Algorithm Projection-Basel Constrained Policy Optimization (PCPO)
Initialize policy x² :T(%)
for k = 0, 1, 2, ... do
Run n² (0 and store trajectories in
Compute g.a. a, H, and using 'D
Obtain g using update in Eq. 6
Empty D
Projection Step. If the projection is defined in the parameter space, we can directly use L norm projection. On the other hand, if the projection is defined in the probability space, we can use KL divergence projection. This can be approximated through the second order expansion. Again, we linearize the cost constraint at n². This gives the following update for the projection step:
0 g arg min
2 A 0 + g
s.t. a (0- 0*) + +b
where L = I for L norm projection, and L H for KL divergence projection. One may argue that using linear approximation to the constraint set is not enough to ensure constraint satisfaction since the real constraint set is maybe non-convex. However, if the step size 5 is small, then the linearization of the constraint set is accurate enough to locally approximate it.
We solve Problem (4) and Problem (5) using convex programming (See the supplemental material for the derivation). For each policy update, we have
H 9 max 0, H a TH HHHH--
b
28 g²
gh+1 0 1
L L-'a.
(6)
9
a L''-'a
We assume that H does not have 0 as an eigenvalue and hence it is invertible. PCPO requires to in- vert H, which is impractical for huge neural network policies. Hence use the conjugate gradient method (Schulman et al.) 2015a). Algorithm| [ shows the pscudocode. (See supplemental material for discussion of the tradcoff between the approximation error and computational efficiency of the conjugate gradient method.)
Analysis of PCPO Update Rule. For problem including multiple constraints, we can extend the update in Eq. (6) by using alternating projections. This approach finds solution in the intersection of multiple constraint sets by sequentially projecting onto each of the sets. The update rule in Eq. (6) shows that the difference between PCPO with KI. divergence and T,2 norm projections is the cost update direction, leading to a difference in reward improvement. These two projections converge to different stationary points with different convergence rates related the smallest and largest singular values of the Fisher information matrix shown Theorem 4.1] For our analysis, we make the following assumptions:
minimize the negative reward objective function f R - R (We follow the convention of the literature that authors typically minimize the objective function). The function f is L-smooth and twice continuously differentiable over the closed and convex constraint set C.
Theorem 4.1 (Reward Improvement Under L Norm and KL Divergence Projections). Let n g- in Eq. 16,, where 8 the step size for reward improvement, g is the gradient of f, and H is the Fisher information matrix. Let maxx H) be the largest singular value of H. and be the gradient of cost advantage function in Eq. (6) Then PCPO with KL divergence projection converges stationary point either inside the constraint set in the boundary of the constraint -aa, o 2 0 holds. Moreover, at step k +
set. In the latter case, the Lagrangian constraint the objective value satisfies
f(0++1) 5 $((0)) +1
@+1 4H+4T
PCPO with L2 norm projection converges to a stationary point either inside the constraint set or in the boundary of the constraint set. In the latter case, the Lagrangian constraint H- -0a,0 a
5

---

Published as a conference paper at ICLR 2020
O holds. If mmax (H) S 1, then step l + objective value satisfies
- _ _ |1 -0
1(0 s l(0")
Proof. See the supplemental material.
Theorem 4.1 shows that in the stationary point g a line that points to the opposite direction of a. Further, the improvement of the objective value is affected by the singular value of the Fisher
information matrix. Specifically, the objective of KL divergence projection decreases when Lg I < 2
H. implying that miin (H) > And the objective of L norm projection decreases when rj <
L. implying that condition number of H is upper bounded: ( (H) 2||al1š Observing the L
oman (H)
singular values of the Fisher information matrix allows us to adaptively choose the appropriate
projection and hence achieve objective improvement. In the supplemental material, further use an example to compare the optimization trajectories and stationary points of KI. divergence and T,2 norm projections.
RELATED WORK
Policy Learning with Constraints. Learning constraint-satisfyii policies has been explored in the
context of safe RL (Garcia & Fernandez, 2013). The agent learns policies either by (I) exploration
of the environment (Achiam al.] 2017 Tessler al. 2018 Chow al. 2017) or (2) through
expert demonstrations (Ross et al. | Rajeswaran et al. 2017 Gao et al. 2018). However, using
expert demonstrations requires humans label the constraint-satisfynng behavior for every possible situation. The scalability of these rule-based approaches is an issue since many real autonomous systems such as self-driving cars and industrial robots are inherently complex. To overcome this issue, PCPO uses the first approach in which the agent learns by trial and error. To prevent the agent from having constraint-violating behavior during exploring the environment, PCPO uses the projection onto the constraint set to ensure constraint satisfaction throughout learning.
Constraint satisfaction by Projections. Us- ing projection onto constraint set has been explored for general constrained optimization in other contexts. For example, [Akrour et al. (2019) projects the policy from a parameter space onto the constraint. This ensures the up- dated policy stays close to the previous policy. In contrast,
n Constraint set k+1
Trust region
Figure Update procedures for CPO (Achiam et al., 2017). CPO computes the update by si- multaneously considering the trust region (light green) and the constraint set (light orange). CPO becomes infeasible when these two sets not in- tersect.
examine constraints that de- fined in terms of states and actions. Similarly, Chow et al. (2019) proposes O-projection. This approach projects the policy parameters 0 onto the constraint set. However, no provide prov- able guarantees are provided. Moreover, the problem is formulated by adding the weighted constraint to the reward objective function. Since the weight must be tuned, this incurs the cost of hyperparameter tuning. In contrast, PCPO eliminates the cost the hyperparameter tuning, and provides provable guarantees on learning constraint- satisfying policies.
Comparison to CPO (Achiam et al., 2017). Perhaps the closest work to ours is the approach of Achiam et al. (2017), who proposes the constrained policy optimization (CPO) algorithm to solve the following:
g++ arg max g" (0 (0) s.t. -0 00 H 0*) <6, a= 0*) + + 0.
(7)
CPO simultancously considers the trust region and the constraint, and uses the line search to select step size (This is illustrated Fig. 2p. The update rule CPO becomes infeasible when the current
policy violates the constraint (b 0). CPO recovers by replacing Problem 7 with an update to
purely decrease the constraint value: @++1 = 8¹
25 H H a. This update rule may lead

---

Published as a conference paper at ICLR 2020
10
00000
mm
(a) Gather
(b) Circle
(c) Grid
(d) Bottleneck
Figure 3: The gather, circle, grid and bottleneck tasks. (a) Gather task: the agent is rewarded for gathering green apples but constrained to collect limited number of red fruit (Achiam al, 2017]. (b) Circle task: the agent is rewarded for moving in specified wide circle, but is constrained stay within safe region smaller than the radius of the circle (Achiam et al. 2017]. (c) Grid task: the agent controls the traffic lights in grid road network and is rewarded for high throughput but constrained
lights stay red for most consecutive seconds (Vinitsky al. 2018). (d)
Bottleneck task: the agent controls set of autonomous vehicles (shown in red) in a traffic merge situation and is rewarded for achieving high throughput but constrained to ensure that human-driven vehicles (shown in white) have low speed for no more than 10 seconds (Vinitsky et al. 2018
to slow progress in learning constraint-satiisying policies. In contrast, PCPO first optimizes the reward and uses the projection satisfy the constraint. This ensures feasible solution, allowing the agent to improve the reward while ensuring constraint satisfaction simultaneously.
EXPERIMENTS
Tasks. We compare the proposed algorithm with existing approaches four control tasks in total: two tasks with safety constraints ((a) and (b) in Fig. B). and two tasks with fairness constraints ((c) and (d) in Fig. 3) These tasks briefly described the caption of Fig. The first two tasks Gather and Circle - are Mujoco environments with state space constraints introduced by |Achiam (017). The other two tasks Grid and Bottleneck- are traffic management problems where the agent controls either traffic light fleet of autonomous vehicles. This is especially challenging since the dimensions of state and action spaces are larger, and the dynamics of the environment are inherently complex.
Baselines. We compare PCPO with four baselines outlined below.
(1) Constrained Policy Optimization (CPO) (Achiam et al. 2017).
2017). In PDO, the weight (dual variables) is learned based on the current constraint satisfaction. A PDO policy update solves:
(2) Primal-dual Optimization (PDO) CCow al.
g++1 arg max
g" (0 0h) + x a (0 O*),
0
where A is updated using A ++1 = A + (3 ( - h). Here / is a fixed learning rate.
(3) Fixed-poin Policy Optimization (FPO). A variant of PDO that solves Eq. ( using constant X.
(4) Trust Region Policy Optimization (TRPO) Schulman et al. 2015a). The TRPO policy update is an unconstrained one:
@ l
H H-'g.
Note that TRPO ignores any constraints. We include it to serve as an upper bound baseline on the reward performance.
Since the main focus to compare PCPO with the state-of-the-arr algorithm, CPO, PDO and FPO not shown in the ant circle, ant gather, grid and bottleneck tasks for clarity.
Experimental Details. For the gather and circle tasks we test two distinct agents: a point- mass (S C A R2), and ant robot (S C 2 A C R$). The agent in the grid task is S C 155 A C R4, and the agent bottleneck task is C 1141" A C _ For the simulations in the gather and circle tasks,
neural network with hidden layers of size (64, 32) represent

---

Published as a conference paper at ICLR 2020
PCP (rr (Der))
PCP AI Mugg Doual
Reward
15
TAP Eohuimanciial
Reward
10
Reward
30
6
15
10
200
400
600
800
1000
200
600
800
1000
530
1000
1500
2000
2500
of policy updates
of policy updates
* of policy updates
40
Constraint values
Constraint values
Constraint values
30
ICF3 --rt 10un)
3.0
PC50 xt B pm Jaand
20
(PQ (Sctiam eca))
0.8
10.0
PPC
7.5
10
Ta50 (6duu man mtal
5.0
0.2
2.5
200
400
0.0
600
0.0
1000
1500
2500
policy updates
policy updates
policy updates
(a) Point circle
(b) Point gather
Ant circle
300
260
Reward
Reward
2.00
220
40
20
180
200
400
800
75
100
125
150
175
200
50
250
J00
policy updates
policy updates
of policy updates
0.7
100
Constraint values
0.6
Constralntt values
18
Constraint values
60
0:2
30-
20
0.0
200
400
500
800
1000
25
50
75
100
12s
150
175
200
50
100
150
200
25n
300
# of policy updates
# of policy updates
of policy updates
(d) Ant gather
(e) Grid
(I) Bottleneck
Figure 4: The values of the discounted reward and the undiscounted constraint value (the total number of constraint violation) along policy updates for the tested algorithms and task pairs. The solid line is the mean and the shaded area is the standard deviation, over five runs. The dashed line in the cost constraint plot is the cost constraint threshold h. The curves for baseline oracle, TRPO, indicate the reward and constraint violation values when the constraint is ignored. (Best viewed in color, and the legend is shared across all the figures.)
Gaussian policies. For the simulations in the grid and bottleneck tasks, we use a neural network with two hidden layers of size (16, 16) and (50,25) to represent Gaussian policies, respectively. In the experiments, since the step size small, we reuse the Fisher information matrix the reward improvement step in the KL projection step to reduce the computational cost. The step size 8 is set to 10-4 for all tasks and tested algorithms. For each task, we conduct runs to get the mean and standard deviation for both the reward and the constraint value over the policy updates. The experiments are implemented in rllab (Duan et al., 2016), a tool for developing and evaluating RL algorithms. See the supplemental material for the details of the experiments.
8

---

Published as a conference paper at ICLR 2020
PCPD wi 2'oora) (Ours)
14
(Ours!
12
PDO (Chow sk))
Reward
20
FPO
Reward
10
TRPO (Schulman al.
5
500 1000 1500 2000 2500 3000 3500 4000 Cumulative constraint values
20
40
60 70
Cumulative constraint values
(a) Point cirele
(b) Point gather
Figure 5: The value of the discounted reward versus the cumulative constraint value for the tested algorithms and task pairs. See the supplemental material for learning curves in the other tasks. PCPO achieves less constraint violation under the reward improvement compared to the other algorithms.
Overall Performance. The learning curves of the discounted reward and the undiscounted con- straint value (the total number of constraint violation) over policy updates are shown for all tested algorithms and tasks in Fig. 4 The dashed line in the constraint figure is the cost constraint threshold h. The curves for baseline oracle, TRPO, indicate the reward and constraint value when the straint is ignored. Overall, we find that PCPO is able to improve the reward while having the fastest constraint satisfaction in all tasks. In particular, PCPO is the only algorithm that learns constraint- satisfying policies across all the tasks. Moreover we observe that (1) CPO has more constraint violation than PCPO, (2) PDO is too conservative in optimizing the reward, and (3) FPO requires significant effort to select good value of X.
We also observe that in Grid and Bottleneck task, there is slightly more constraint violation than the easier task such as point circle and point gather. This is due to complexity of the policy behavior and non-convexity of the constraint set, PCPO still outperforms CPO with 85.159 15%15% and 5.42 times less constraint violation in Grid and Bottleneck task, respectively.
However, even with linear approximation of the constraint
These observations suggest that projection step in PCPO drives the agent to learn the constraint- satisfying policy within few policy updates, giving PCPO an advantage in applications. To show that PCPO achieves the same reward with less constraint violation,
examine the reward versus the cu- mulative constraint value for the tested algorithms in point circle and point gather task shown in Fig. We observe that PCPO outperforms CPO significantly with 66 times and 15 times less constraint violation under the same reward improvement in point circle and point gather tasks, respectively. This observation suggests that PCPO enables the agent to cautiously explore the environment under the constraints.
S
Comparison of PCPO with KL Divergence vs. L Norm Projections. We observe that PCPO with L2 norm projection is more constraint-satisfyingg than PCPO with KL divergence projection. In addition, PCPO with L norm projection tends have reward fluctuation (point circle, ant cir- cle, and ant gather tasks), while with KL divergence projection tends to have more stable reward improvement (all the tasks).
The above observations indicate that since the gradient of constraint is not multiplied by the Fisher information matrix, the gradient of the constraint is not aligned with the gradient of the reward. This reduces the reward improvement. However, when the Fisher information matrix is ill-conditioned or not well-estimated, especially in a high dimensional policy space, a bad constraint update direction may hinder constraint satisfaction (ant circle, ant gather, grid and bottleneck tasks). In addition, since the stationary points of KL divergence and L norm projections are different, they converge to policies with different reward (observe that PCPO with L norm projection has higher reward than the one with KL divergence projection around 2250 iterations in ant circle task, and has less reward in point gather task).

---

Published as a conference paper at ICLR 2020
Discussion of PDO and FPO. For the PDO baseline, especially in the point circle task. This phenomena suggests that PDO is not able to adjust the weight X quickly enough meet the constraint threshold, which hinders the efficiency of learning constraint-satisfynng policies. If the learning rate 3 is too big, the agent will be too conservative in improving the reward. For FPO, we also that it learns slightly larger reward improvement compared to PDO. However, in practice FPO requires lot of engineering effort to select good value of X. Since PCPO requires no hyperparameter tuning, has the advantage of robustly learning constraint-satisfying policies over PDO and FPO.
that its constraint values fluctuate
constraint-satisfying policies with
7 CONCLUSION
We address the problem of finding constraint-satisfying policies. The proposed algorithm projection-based constrained policy optimization ( for the reward function while using the projections to ensure constraint satisfaction. This update rule allows PCPO to maintain the fcasibility of the optimization problem each update, addressing the issue of state-of-the-a approaches. The algorithm achieves comparable superior performance proaches in terms of reward improvement and constraint satisfaction in all cases. We further analyze the convergence of PCPO, and find that certain tasks may prefer either KL divergence projection L norm projection. Future work will consider the following: (I) examining the Fisher information matrix to iteratively prescribe the choice of projection for policy update, and hence robustly learn constraint- constraint-satisfying policies with more reward improvement, and (2) using expert demonstration or other domain knowledge reduce the sample complexity.
state-of-the-art ap-
ACKNOWLEDGMENTS
The authors would like thank the anonymous reviewers and the area chair for their comments. Tsung- Yen Yang thanks Siemens Corporation, Corporate Technology for their support.
REFERENCES
Joshua Achiam, David Held, Aviv Tamar, and Pieter Abbeel. Constrained policy optimization. In Proceedings of International Conference on Machine Learning, pp. 22-31, 2017.
Riad Akrour, Joni Pajarinen, Gerhard Neumann, and Jan Peters. Projections for approximate policy iteration algorithms. In Proceedings of International Conference on Machine Learning, pp. 181-
190, 2019.
AlphaStar. craft ii 2019.
Alphastar:
Mastering the real-time strategy
game
star-
URL attips::/deepmirdd.com//bbbbbbb wwwp
al alphastar mastering centterinn-real-taee strategy game starcraft-ii
Eitan Altman. Constrained Markov decision processes, volume 7. CRC Press, 1999.
Yinlam Chow, Mohammad Ghavamzadch, Lucas Janson, and Marco Pavone. fisk-constrained re- inforcement learning with percentile risk criteria. Journal of Machine Learning Research, 18(1): 6070-6120, 2017.
Yinlam Chow, Ofir Nachum, Aleksandra Faust, Mohammad Ghavamzadeh, and Edgar Duenez- Guzman. Lyapunov-based safe policy optimization for continuous control. arXiv preprint arXiv:1901.1003: 2019.
Yan Duan, Xi Chen, Rein Houthooft, John Schulman, and Pieter Abbeel. Benchmarking deep reinforcement learning for continuous control. In Proceedings of International Conference Machine Learning, pp. 1329-1338, 2016.
Yang Gao, Ji Lin, Fisher Yu, Sergey Levine, and Trevor Darrell. Reinforcement learning from imperfect demonstrations. arXiv preprint arXiv: 100.00330 2018.
Javier Garcia and Fernando Fermandez. A comprehensive survey on safe reinforcement learning. Journal of Machine Learning Research, 16(1):1437-1480,
2015. 2015.
10

---

Published as a conference paper at ICLR 2020
Sham Kakade and John Langford. Approximately optimal approximate reinforcement learning. In Proceedings of International Conference on Machine Learning, pp. 267-274, 2002.
Sergey Levine, Chelsea Finn, Trevor Darrell, and Pieter Abbeel. End-to-end training of deep visuo- motor policies. Journal of Machine Learning Research, 17(1):1334-1375 2016.
Volodymyr Mnih, Koray Kavukeuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wier- stra, and Martin Riedmiller. Playing atari with deep reinforcement learning. arXiv preprint arXiv:1312.5602 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. arXiv preprint /70x:::/799.00000000 2017.
Stéphane Ross, Geoffrey Gordon, and Drew Bagnell. A reduction of imitation learning and struc- tured prediction to no-regret online learning. In Proceedings of International Conference on Artificial Intelligence and Statistics, pp. 627-635, 2011.
John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz. Trust region policy optimization. Proceedings of International Conference on Machine Learning, pp. 1889- 1897, 2015a.
John Schulman, Philipp Moritz, Sergey Levine, Michael Jordan, and Pieter Abbeel. High- dimensional continuous control using generalized advantage estimation. arXiv preprint 1rXiv:/506.02444 2015b.
Jonathan Shewchuk. An introduction the conjugate gradient method without the agonizing pain, 1994.
David Silver. Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, et al. Mastering the game of go without human knowledge. Nature, 550(7676)3354, 2017.
Richard S. Sutton, David A. McAllester, Satinder P. Singh, and Yishay Mansour. Policy gradient methods for reinforcement learning with function approximation. In Advances in Neural Infor- mation Processing Systems, pp. 1057-1063, 2000.
Chen Tessler, Daniel J. Mankowitz, and Shie Mannor. Reward constrained policy optimization. arXiv preprint arXiv: 1074, 2018.
Eugene Vinitsky, Aboudy Kreidich, Lue Le Flem, Nishant Kheterpal, Kathy Jang, Fangyu Wu, Richard Liaw, Eric Liang and Alexandre M. Bayen. Benchmarks for reinforcement learning in mixed-autonomy traffic. In Proceedings of Conference Robot Learning, pp. 399.409, 2018.

---

Published as a conference paper at ICLR 2020
S SUPPLEMENTARY MATERIALS
S.1 PROOF OF THEOREM 3.1 PERFORMANCE BOUND ON UPDATING THE CONSTRAINT-SATISFVNE POLICY
To prove the policy performance bound when the current policy is feasible (i.e., constraint- satisfying), we prove the KL divergence between xh and x*+1 for the KL divergence projection. We then prove our main theorem for the worst-case performance degradation.
Lemma S.1. If the current policy nh satisfies the constraint, the constraint set closed and convex, the KL divergence constraint for the first step is LE, anaa" [DK (x [[x*"{] I ö, where is the step size in the reward improvement step, then under KL. divergence projection, we have
E Baagtt [x 2 [s]]] 8.
Proof. By the Bregman divergence projection inequality, T² being in the constraint set, and h++ being the projection of the *++ onto the constraint set, we have
E Bwank
[DK (T7 || ++ [s]] 2 endak
[DKL(T [s]] + E Bendith [DKL(T (| [s]]
8 BB s (x (| & [s}]] 2 E sndrth [DKL(**) ( [ss]]
+
The derivation the fact that KL divergence is always greater than zero We know that KI. divergence is asymptotically symmetric when updating the policy within a local neighbourhood. Thus, have
2 E Smath (T b+g [(T* 2 E Bxnath (T [s]]
Now we use Lemma S.I to prove our main theorem.
Theorem
S.2. Define
h+1
max +n [AT (8, a)]l, and ec
max E E [AT (s,a)]|. If the current policy a² satisfies the constraint, then under the
KI. divergence projection, the lower bound on reward improvement, and upper bound on constraint violation for each policy update are
V2 t+1 (1- and J )
228 kil
-
s h+
(1 7)-
where ô the step size in the reward improvement step.
Proof. By the theorem in Achiam al. (2017) and Lemma S.I have the following reward degradation bound for each policy update:
{1) (T
2
1
E
start
A (s,a)
2
k+1
DKL (I + ||
1
angki1
1
2 A+1
h+1
1
snatth
V5
1 1-7
amghtt
V28
(1 (1-7) 722
Again, we have the following constraint violation bound for each policy update:
J (m()
t x 1nght1
AA (s, a)) < h.
(9)
12

---

Published as a conference paper at ICLR 2020
and
-
2
1
E
Ac (3,0) +
27e6
(10)
1 1-7
++1
Combining Eq.
9 and Eq. 10
we have
2 +11
J (
S
7 V (1+
ama
v 22
S
(1 7)2
S.2 PROOF OF THEOREM 3.2 PERFORMANCE BOUND ON UPDATING THE CONSTRAINT-VIOLLATIG POLICY
To prove the policy performance bound when the current policy is infeasible (i.e., constraint- violating), we prove the KL divergence between nh and n²*1 for the KL divergence projection. We then prove our main theorem for the worst-case performance degradation.
Lemma S.3. If the current policy x violates the construint, the constraint set closed and convex, the KL divergence constraint for the first step is ge [DL((T** + =|(=*) S ö, where the step size in the reward improvement step, then under the KL divergence projection, have
Eanndt [DKL. ( < 5 OKL.
where OKL - 22 カー a is the gradient of the cost advantage function, H is the Hessian of the KL divergence constraint, and b+ (C h).
Proof. We define the sublevel set of cost constraint function for the current infeasible policy n²:
- { J
(mT
E and amp
(AT (s, s )x
This implies that the current policy n² lies in T* and न + projected onto the constraint set: (TT
+ and [A (s, a)] I h}. Next, we define the policy मं as the projection of x k+t
onto LT*
By the Three-poine Lemma, for these three polices th m and mf with ppx)) = E, 24 log (this is illustrated in Fig. 6). we have
8 > E soufth DKL(T)) ( 1+ [[]]]
DTL [|>*)|)>>((s]]
= smotth
E snu
D (TRI(T=++))) ++1 ( 11++++++))))) [s]]
+ E Bradh
((V)((T))) - V )) (I ++1 [+]]]
+ E stugtt (xI( (1
< 5 + E smatt (
E snught
[(Vp(T*)) V (++11 क. [ (11)
The inequality E. B (xft [s]] Lemma S.II
ô comes from that t and ++1 in 1= and
If the constraint violation of the current policy * is small, iee. bt is small, be approximated by the second order expansion. By the
Brnght (x [
13

---

Published as a conference paper at ICLR 2020
Constraint set
Trust region
x+1
T k+ +1
π
Figure 6: Update procedures for PCPO when the current policy x" is infeasible. x/+ is the projec- tion of * onto the sublevel the constraint set. We find the KL divergence between n² and k+1
update rule in Eq. (6). we have
E studt
[KLL (1 1| || ( [s]
(Ak+1 0 ( H(O - -
b+
T H
b+
H
H H
a la
a T aTH-
b" b+2
2a H-ta
b b+² aaKLL
(12)
where OKL =
And since 8 is small, we have Vip(*t) Vy(mm+1) given s. Thus, the third term in Eq. can be eliminated.
Combining Eq. 11 and Eq. (12) we have
sh [RL (T k+ ( [s]] 88+ + b OKL-
Now we use Lemma S.3 to prove our main theorem.
Theorem S.4. Define ett _=*++ max Ea-rki [ATH a)]l co. k+1
max Ea [ (s, a)]l,
b+ max(0, (-())) and OKL 2n-H-1a where a is the gradient of the cost advantage function and H is the Hessian of the KL divergence constraint. If the current policy x² violates the constraint, then under the KL divergence projection, the lower bound on reward improvement and the upper bound on constraint violation for each policy update are
2 b+ b++b+=tk)))) 7E k+1
( (R
71
2(6 22 + bt 2
and j ( hh
)
where 8 is the step size in the reward improvement step.
Proof. Following the same proof in Theorem S.2 we complete the proof.
Note that the bounds obtain for the infeasibe case; to the best of our knowledge, results.
14

---

Published as a conference paper at ICLR 2020
S.3 PROOF OF ANALYTICAL SOLUTION TO PCPO Theorem S.5. Consider the PCPO problem. In the first step, oplimize the reward:
0 arg max g" (0 0%)
/ H( -1)
0%) 2
s.t.
and in the second step, project the policy onto the constraint set:
0 arg min
1
0 0 0 g
2
s.t. a" (0- 8*) +b
ERR,,,, E and H. Raxn L H if using the KL divergence projection, and L = if using the I norm projection. When there is at least one strictly feasible point, the optimal solution satisfies
where 9, a,
28
25 a H g" g
+
a++1 0h
H
max(0,
a-L aL
g"
assuming that H invertible get a unique solution.
Proof. For the first problem, since H is the Fisher Information matrix, which automatically guaran- tees is positive semi-definite. Hence Hence if the primal problem has feasible point, then Slaters condition is satisfied and strong duality holds. Let l" and X denote the solutions to the primal and dual problems, respectively. In addi- tion, the primal objective function is continuously differentiable. Hence the Karush- Kuhnsh Tucker (KKT) conditions are necessary and sufficient for the optimality Lagrangian:
convex program with quadratic inequality constraints.
and X", We now form the
A) (0- (0-000 -
- H 0h) -6) -).
And we have the following KKT conditions:
+ X X" H0 =
VeL(O", =
(13)
2 00 / H 8h)
Vxc(O", x=)=0 =
(14)
(0" 0 H(O 0%) - 850
primal constraints
(15)
2
2
dual constraints
(16)
x ( 1 10 0K)T H( - )
complementary slackness
(17)
By Eq.
13
we have 0- = 0h + + g. And by plugging Eq.
13 into Eq.
14
we have
g" H- g
Hence we have our optimal solution:
26
28
g++ 0" @h
H gg
(18)
g" H
which also satisfies Eq. [5) Eq. 16. and Eq. 177.
Following the same reasoning, we now form the Lagrangian of the second problem:
((O,)) (0 - by
L(O L(O
0²+3) X(a" (0 0²) + b).
15

---

Published as a conference paper at ICLR 2020
0'
0
Figure 7: The projection onto the convex with O' C and 0- Proje (0).
And we have the following KKT conditions:
LO LO + X*a 0
Vol(o", X*)
(19)
a (0" 8¹) +
VxC(O", ,X'
(20)
a a'(0" 0¹) +b 0
primal constraints
(21)
2
dual constraints
(22)
(a (0 0²) + +b
complementary slackness
(23)
By Eq. 19 we have 0- gh+1 + X a. And by plugging Eq. 19 into Eq. 20 and Eq.
22
we have X max(0, a² (0* 1 0² +4b Hence we have our optimal solution:
a (A++ 0
b
g 0 g max(0,
L aa
(24)
a L a
which also satisfies Eq. 21 and Eq.
Hence by Eq.
18 and Eq.
we have
28
H gg max(0, g H i
25
a
g + b
k++ = 0 +
L a.
H
aTL-la
S.4 PROOF OF THEOREM 4.1 STATIONARY POINTS OF PCPO WITH THE KL DIVERGENCE AND L NORM PROJECTIONS
For our analysis, make the following assumptions: we minimize the negative reward objective function f IR" + R (We follow the convention of the literature that authors typically minimize the objective function). The function f is L-smooth and twice continuously differentiable over the closed and convex constraint set C. We have the following lemma to characterize the projection and for the proof of Theorem S.7 (See Fig. for semantic illustration.)
- 0*) < 0,00' E C, where Proje (0) - arg min |ee 0'112. and L = H if using the KL divergence projection, and L = I d'ec
Lemma S.6. For any 0, 0- Proje' (0) if and only if (0 O00
using the 2 norm projection.
Proof. (=) Let 0- = Proje (0) for given 0 & C, 0' E E be such that 0' + 0', and a E (0, 1).
Then we have
|10 1 < 100 (0+ + a0'' 11
= 0 0-
1
+ a 0 20 - 0 - 0*)
+ (0 (0-00--T L 0r) < a
0' 1
(25)
2
Since the right hand side of Eq.
25 can be made arbitrarily small for given a, and hence we have:
0 0 F L(O'
0*) v 0, V0' C.
16

---

Published as a conference paper at ICLR 2020
(=) Let 0 E C be such that (0 L(0' 0*) I 0, 40' E C. We show that 0 must be the
optimal solution. Let 0' E C and + 0" Then we have
||e l 1|0
0- 0 0* + ll. 100 0 11
0 0- + 110' 1- 2( ) -0- -10 1-0--112 --1
=
0
100 0' l1
0 1'
Hence, 0* is the optimal solution to the optimization problem, and 0 = Proje (0).
Based on Lemma 5.6 we have the following theorem.
Theorem S.7. Let 1 = 9"
26
in Eq. (6), where 8 is the step size for reward improvement, g is
the gradient of J, H is the Fisher information matrix. Let (ax)(H) be the largest singular value of H, and a be the gradient of cost udvantage function Eq. (6). Then PCPO with the KL divergence projection converges to stationary points with -a (i.e.. the gradient of f belongs to the negative gradient of the cost advantage function). The objective value changes by
f(A*+1) S f(0)) + |10 0-1| 1
(26)
-a (i.e., the product of the inverse of H and gradient of f belongs to the negative gradient of the cost advantage function). If max H) S 1, then the objective value changes by
PCPO with the L norm projection converges stationary points with H H -a 9
T,
f(ok+1) S f(00) +
111 6+ 1
(27)
2
Proof. The proof of the theorem is based on working in a Hilbert space and the non-expansive property of the projection. We first prove stationary points for PCPO with the KL divergence and L norm projections, and then prove the change of the objective value.
When in stationary points 0;, we have
0' 0
26 g²
H 9 max
n" 4TH-1
28
g
T "H
g + b
L
a
---g
at L-ta
28
a H +
28
H 19 ma
g" H H-H-gg
L L-La
9 g
a L la
# g E L
(28)
For the KL divergence projection (L = H), Eq. 28
boils down to g E -a, and for the L norm
projection (L = I), Eq. (28) is equivalent to H " a.
Now we prove the second part of the theorem. Based on Lemma S.6 for the KL divergence projec- tion, we have
(0* - 1 H(O - 1 9 - 0 5
= = 8²) 5 - ---- 8/1122-
(29)
77
By Eq. 29 and L-smooth continuous function f, we have
f(0h+1) < f(0)) + gT(0" (@++1 1--+--011 -²t) + 1 - -0111
S s(0)) 1 1|0+11 0
L
11gh11
1+13
2
f(0)) + (0 0
1
H
+
L
( 8t)
n
2
-(( 10 - 0² 1
17

---

Published as a conference paper at ICLR 2020
For the L norm projection, we have
- (0* - - - - g - 0 0
g H 1 - - (H) - 1, we have
0- 0²
(30)
By Eq. 330 L-soooth continuous function f, and if T
s(Oh+1) - 5(0*) + +g"(0"+ - 0%) + ク -1 - 1²1
$ f(00)) + ( 17 - 04112-
-
To why need the assumption of o max (H) I 1, we define H = UEUT as the singular value decomposition with u, being the column vector of U. Then we have
g" H 10 0²) Q' u U (0++1 0%)
g" (H) u (0 - 0h)
0 (H) g" (AR+1 0
If we want to have
(0h+1 0h) S g" H (0h+1 0t) S - 1 0 1/1
77 then every singular value o, H)) of H needs be smaller than 1, and hence mmax (H) S 1, which justifies the assumption we use to prove the bound.
To make the objective value for PCPO with the KI. divergence projection improves, the right hand side of Eq. (26) needs to be negative. Hence we have
2 La I H, implying that o (H) > In
And to make the objective value for PCPO with the L norm projection improves, the right hand side of Eq. (27) needs to be negative. Hence we have Z. implying that
25
2
11
9
H
9
28
4
H 9
1
g H 9
12
28
4
L28
99 T
H
9
2
|
H
9112 ||21| 12
< |/||2|
H
||||
max
Omin H
[g|
2
L28
00 (H)
(31)
2 |g|
By the definition of the condition number and Eq.
(3
have
2 2|g
12
miin
L28
4 max
H
2 2|1g1 |
H
0 uiin
H
L
2||g1 13
<
T,28
which justifies what discuss.
18

---

Published as a conference paper at ICLR 2020
S.5
ADDITIONAL COMPUTATIONAL EXPERIMENTS
S.5.1 IMPLEMENTATION DETAILS
For detailed explanation of the task in Achiam et al. (2017), please refer to the appendix of Achiam al. (2017). For detailed explanation of the task Vinitsky et al. (2018), please refer to Vinitsky al. 20188).
We use neural networks that take the input of state, and output the mean and variance to be the Gaussian policy in all experiments. For the simulations in the gather and circle tasks, network with two hidden layers of size (64, 32). For the simulations in the grid and bottleneck tasks, neural network with two hidden layers of size (16, 16) and (50, 25), respectively. We use tanh as the activation function of the neural network.
neural
We use GAE-À approach (Schulman al., 2015b) to estimate (s, and Ag a). For the simulations in the gather and circle tasks, we use neural network baselines with the same architecture and activation functions the policy networks. For the simulations in the grid and bottleneck tasks, we use linear baselines.
The hyperparameters of each task for all algorithms gather, AC: ant circle, AG: ant gather, Gr: grid, and BN: bottleneck tasks);
follows (PC: point circle, PG: point
Parameter
PC
PG
AC
AG
Gr
BN
discount factor step size 5 GAE B AE
0.995
0.995
0.995
0.995
0.999
0.999
10-4
10-4
10-4
10-4
10-4
10
X
0.95
0.95
0.95
0.95
0.97
0.97
1.0
1.0
0.5
0.5
0.5
1.0
Batch size
50,000
50,000
100,000
100,000
10,000
25,000
Rollout length
50
15
500
500
400
500
Cost constraint threshold h
5
0.1
10
0.2
0
Note that we do not use a learned model to predict the probability of entering an undesirable state within fixed time horizon CPO did for cost shaping.
S.5.2 EXPERIMENT RESULTS
To examine the performance of the algorithms with different metries, provide the learning curves of the cumulative constraint value over policy update, and the reward versus the cumulative con- straint value for the tested algorithms and task pairs in Section 6 shown in Fig. The second metric enables us to compare the reward difference under the same number of cumulative constraint violation.
Overall, we find that,
(a) CPO has more cumulative constraint violation than PCPO.
(b) PCPO with L norm projection has less cumulative constraint violation than KL divergence projection except for the point circle and point gather tasks. This observation suggests that the Fisher information matrix not well-estimated in the high dimensional policy space, leading to have more constraint violation.
(c) PCPO has more reward improvement compared to CPO under the same number of cumu- lative constraint violation in point circle, point gather, ant circle, ant gather, and bottleneck task.
S.5.3 CPO WITHOUT LINE SEARCH
Due to approximation errors, CPO performs line search to check whether the updated policy sat- isfies the trust region and cost constraints. To understand the necessity of line search in CPO, we conducted the experiment with and without line search shown in Fig, g The step size 5 is set to 0.01. We find that CPO without line search tends to (1) have large reward variance especially in the point circle task, and (2) learn constraint-satiifyinng policies slightly faster. These observations
19

---

Published as a conference paper at ICLR 2020
Cunulattvve constraint values
Cumul Cumulattive constrains values
Cumulative constraint vallues
PDPO ai Lards 10on)
5000
3000
3000
2000
1000
1000
of policy updates
of policy updates
policy updates
PCPO en cont 30am che (ichamette) vsto ILlle
Reward
20
TRDO Senuimar etal
Reward
200
Cumulative values
Cumulative constraintt
Cumulative constraint
(a) Point circle
(b) Point gather
(c) Ant circle
Curullative constraint values
Cumulative constraint volues
20
Curuulative constraint
37500
0002
155
22500
10
0000
7500
2500
00
200
400
100 policy updates
100
250
300
policy updates
policy updates
80
280
Reward
Reward R.
66
Roward
240
200
30
20
15
20
58
1000 2000 3000 0000 s00e 6000
2000
6000 6000
0000 10000
Cumulative constraint values
Cumulative constraint values
Cumulative constraint values
(d) Ant gather
(c) Grid
(f) Bottleneck
Figure 8: The values of the cumulative constraint value over policy update, and the reward versus the cumulative constraint value for the tested algorithms and task pairs The solid line the mean and the shaded area is the standard deviation, over five runs. The curves for baseline oracle, TRPO, indicate the performance when the constraint ignored. (Best viewed in color, and the legend is shared across all the figures.)
suggest that line search more conservative in optimizing the policies since it usually take smaller steps. However, we conjecture that if using smaller 5, the effect of line search is not significant.
S.5.4 THE TASKS WITH HARDER CONSTRAINTS
To understand the stability of PCPO and CPO when deployed in more constraint-critical tasks, increase the difficulty of the task by setting the constraint threshold to zero and reduce the safe area. The learning curve of discounted reward and constraint value over policy updates are shown in Fig.
10
We observe that even with more difficult constraint, PCPO still has more reward improvement and constraint satisfaction than CPO, whereas CPO needs more feasible recovery steps to satisfy the constraint. In addition, observe that PCPO with T,2 norm projection has high constraint variance
20

---

Published as a conference paper at ICLR 2020
23
-5-
-0- CPO (Actiam all Ire search
CPD (ichiam aE
CP Mntiaam at)
CP Mettiam at at Aleine sEaIO
Reward
Reward
20
2
50
150
25
100 125
200
policy updates
of policy updates
30
(Actiam all
Mthham
Constraint values
23
Constraint values
20-
10-
25
50
75
100
125
150
175
200
50
75
100
175
150 175 200
# of policy updates
of policy updates
(a) Point circle
(b) Point gather
Figure 9: The values the reward and the constraint value for the tested algorithms and task pairs. The solid line is the mean and the shaded area is the standard deviation, over five runs. The dash line in the cost constraint plot the cost constraint threshold h. Line search helps stabilize the training. (Best viewed in color)
PCRC Ligra (Ouns)
PCPO ao2 [Dunl
PCPO RLgel (Danl
FCrO in KiKpi (OuS) CP tichimm al)
CPD (Acram acl
Reward
Reward
2 w
400
600
1000
200
400
600
800
1000
of policy updates
policy updattes
o rcno at Parss Dura
Constraint values
-d- Mehhaa
PCRO Al poo (0urs)
Constraint values
0.8
0.6
0.4
cro (uriam
10
0
0.2
-10
0
200
400
600
800
1000
200
400
600
800
1000
# of policy updates
# of policy updates
(a) Point circle
(b) Point gather
Figure 10: The values of the reward and the constraint value for the tested algorithms and task pairs. The solid line is the mean and the shaded area is the standard deviation, over five runs. The dash line in the cost constraint plot is the cost constraint threshold h. PCPO with KI. divergence projection the only one that can satisfy the constraint with the highest reward. (Best viewed in color)
in point circle task, suggesting that the reward update direction not well aligned with the cost update direction. We also observe that PCPO with 7.2 norm projection converges bad local
21

---

Published as a conference paper at ICLR 2020
20
15
Egro, PCFO (Dum) CPO aaciainn dE
PC50
14-
PCR wirtirrs (Oun))
mar Schulranat stall
12-
ORO (éciia of
1E7O iSehurmen
Reward
Reward
10
-5
250 10001250 150017502000
750 1500 150115007750200
of policy updates
policy updates
Constraint values
-O- FChO ar Ruui
poppe 10and
Constraint values
1.4
EEPO Ri (Oum))
rSnO wre grus Musl
1.2
1.0
0.8
0.6
10
0.4
5
0.2
0.0
250 500 750 1000
250 500 750 100012501500 100115555015100000
# of policy updates
# of policy updates
(a) Point circle
(b) Point gather
Figure 11: The values of the reward and the constraint value for the tested algorithms and task pairs. The solid line is the mean and the shaded area is the standard deviation, over five runs. The dash line in the cost constraint plot is the cost constraint threshold h. The curves for baseline oracle, TRPO, indicate the reward and constraint violation values when the constraint is ignored. We only use 1% of samples compared to the previous simulations for each policy update. PCPO still satisfies the constraints quickly even when the constraint set is not well-estimated. (Best viewed in color)
optimum in terms of reward in point gather task, suggesting that in order to satisfy the constraint, the cost update direction destroys the reward update direction.
S.5.5 SMALLER BATCH SAMPLES
To learn policies under constraints, PCPO and CPO require to have good estimation the con- straint set. However, PCPO may project the policy onto the space that violates the constraint due to the assumption of approximating the constraint set by linear half space constraint. To understand whether the estimation accuracy of the constraint affects the performance, we conducted the periments with batch sample size reducing to 1% of the previous experiments (only 500 samples for each policy update) shown in Fig.
We find that smaller training samples affects the performance of the algorithm, creating more reward and cost fluctuation. However, we observe that even with smaller training samples, PCPO still has more reward improvement and constraint satisfaction than CPO.
S.6 ANALYSIS OF THE APPROXIMATION ERROR AND THE COMPUTATIONAL COST OF THE CONJUGATE GRADIENT METHOD
In the Grid task, we observe that PCPO with KI. divergence projection does worse in reward than TRPO, which expected since TRPO ignores constraints. However, TRPO actually outperforms PCPO with KL divergence projection in terms of constraint, which is unexpected since by trying to consider the constraint, PCPO with KL divergence projection has made constraint satisfaction worse
The reason for this observation is that the Fisher information matrix is ill ill-conditioned, iee. the con- dition number Amax (H)/ Amin (H) (Amax is the largest eigenvalue of the matrix) of the Fisher infor- mation matrix is large, causing conjugate gradient method that computes constraint update direction H-1o with small number of iteration output the inaccurate approximation. Hence the inaccurate
22

---

Published as a conference paper at ICLR 2020
68
1C20
Constraint values
PCPD
KL
40-
64
Reward
30-
62-
20
60
PCPP cL and 60
-6- PCPO CL-gra and lar. 00
10
20
30
40
50
0
10
20
30
40
50
of policy updates
policy updates
1.2
PCPO pro and ker, of -4- PCPo Kiuping and ber.
Approx. error Hf
Condition number
1.0
1.0
0.8
0.8
0.6
0.4
0.4
0.2
0.2
0.0
0.0
10
20
30 40
50
10
20
40 50
of policy updates
# of policy updates
Figure 12: (1) The values of the reward and the constraint, (2) the condition number of the Fisher information matrix, and (3) the approximation error of the constraint update direction over training epochs with the conjugate gradient method's '' iteration of 10 and 20, respectively. The one with larger number iteration has more constraint satisfaction since has more accurate approximation. (Best viewed in color)
approximation of H cause PCPO with KL. divergence projection have more constraint violation than TRPO.
To solve this issue, one can have more epochs of conjugate gradient method. This is because that the convergence of conjugate gradient method is controlled by the condition number (Shewchuk) 1994]: the larger the condition number is, the more epochs the algorithm needs to get accurate approximation. our experiments, we set the number of iteration of conjugate gradient method to be 10 to tradeoff between the computational efficiency and the accuracy across all tested algorithms and task pairs.
To verify our observation, we compare the condition number of the Fisher information matrix, and the approximation error of the constraint update direction over training epochs with different number of iteration of the conjugate gradient method shown in Fig. 12
We observe that the Fisher information matrix is ill-conditioned, and the one with larger number of iteration has less error and more constraint satisfaction. This observation confirms our discussion.
S.7 COMPARISON OF OPTIMIZATION PATHS OF PCPO WITH KL DIVERGENCE AND L NORM PROJECTIONS
Theorem 4.1 states that a stationary point of PCPO with KL divergence projection is different from the of PCPO with _ norm projection. See Fig. 13 for illustration. To compare both stationary points, we consider the following example shown in Fig. 14 We maximize a non-convex function f(x) x " (ilg((y) subject to the constraint <'1 1, where y [5. -1)", and is an all-one vector. An optimal solution to this constrained optimization problem is infinity. Fig. 14 a) shows the update direction that combines the objective and the cost constraint update directions for both projections. It shows that PCPO with KL divergence projection has stationary points with g E -a in the boundary the constraint set (observe that the update direction is zero for PCPO with KL divergence projection at œ [0.75, 11755' [0.25. - -1.25 " and 00225, -0.75'²), whereas PCPO with 2 norm projection does not have stationary points in the boundary of the constraint set. Fur- thermore, Fig. b) shows the optimization paths for both projections with initial starting point. shows that starting at the initial point [0.5, -2.0 PCPO with KL divergence projection with the initial point (0.5, -200"T converges local optimum, whereas I.2 norm projection converges
23

---

Published as a conference paper at ICLR 2020
Normal cone Ne
X1
Normal cone (x2x
X2
Constraint set C
Figure 13: The semantic overview of stationery points of PCPO. The red dashed lines are negative directions of normal cones, and the green dashed lines are objective update directions. The objective update direction in an stationary point is belong to the negative normal cone.
0.5
0.0
-0.5
-1.0
-1.5
-2.0
PCPO L2-prog.
PCPO KL-prog.
-2.5 1.5
1.5
-1.0
-0.5
0.0
0.5
1.0
1.5
X1
(a) Update direction
PCPO w. KL-proj.
PCPO w. L2-proj.
0.5
12.14
0.0
0.0
9.12
0.5
6.11
3.09
$ 110
X 1.0
0.08
-2.94
1.5
1.5
-5.95
-8.97
-2.0
2.0
-11.98
-2.5
2.5
115.00
0
1
X1
X1
(b) Optimization path
The policy update direction that combines the objective and the constraint update di- rections of each point (top), and the optimization path of PCPO with KL divergence and L norm projections with the initial point [0.5. -2.07 (below). The red star the initial point, the red arrows are the optimization paths, and the region that is below to the black line is the constraint set. We see that both projections converge to different solutions.
Figure 14:
infinity. However, the above example does not necessary that PCPO with I,2 norm projection always find a better optimum. For example, the gradient direction of the objective zero in the constraint in the boundary, then both projections may converge the stationary point.
24


Reviews:
[{"review_id": "rJxNx-bBKB", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary : \n\nThis paper introduces a constrained policy optimization algorithm by introducing a two-step optimization process, where policies that do not satisfy the constraint can be projected back into the constraint set. The proposed PCPO algorithm is theoretically analyzed to provide an upper bound on the constraint violation. The proposed constrained policy optimization algorithm is shown to be useful on a range of control tasks, satisfying constraints or avoiding constraint violation significantly better than the compared baselines.\u000b\u000b\n\n\nComments and Questions : \n\n\t- The key idea is to propose an approach to avoid constraint violation in a constrained policy gradient method, where the constraint violation is avoided by first projecting the policy into the constrained set and then choosing a policy from within this set that is guaranteed to satisfy constraints. \n\t- Existing TRPO method already proposes a constrained optimization method (equation 2 as discussed), where the constraint is within the policy changes. This paper further introduces additional constraints (in the form of expected cost or safety measures) where the intermediary policy from TRPO is further projected into a constraint set and the overall policy improvement is based on the constraint satisfied between the intermediary policy and the improved policy. In other words, there are two levels of constraint satisfaction that is required now for the overall PCPO update. \n\t- The authors propose two separate distance measures for the secondary constraint update, based on the L2 and KL divergence.\n\t- I am not sure of the significance of theorem 3.2 in comparison of theorem 3.1? Proof of theorem 3.1 is easy to follow from the appendix, and as noted, follows from Achiam et al., 2017\n\t- Section 4 discusses similar approximations required as in TRPO for approximating the KL divergence constraint. Similar approximations are requires as in TRPO, with an additional second-order approximation for the KL projection step. The reward improvement step follows similar approximations as in TRPO, and the projection step requires Hessian approximations considering the KL divergence approximation. \n\t- This seems to be the main bottleneck of the approach? The fact it requires two approximations, mainly for the projection step seems to add further complexity to the propoed approach? The trade-off therefore is to what extent this approximation is required for safe policy improvement in a constrained PO problem versus computational efficiency?\n\t- Two baselines are mainly used for comparison of results, mainly CPO and PDO, both of which are constrained policy optimization approaches. The experimental results section requires more clarity and ease of presentation, as it is a bit difficult to follow what the results are trying to show exactly. However, the main conclusion is that PCPO significantly satisfies constraints in all the propoed benchmarks compared to the baselines. The authors compare to the sota baselines too for evaluating the significance of their approach. \n\n\nOverall, I think the paper has useful merits - although it seems to be a computational ly challenging approach requiring second order approximations for both the KL terms (reward improvement and project step). It may be useful to see if there is a computationally simpler, PPO form of the variant that can be introduced for this proposed approach. I think it is useful to introduce such policy optimization methods satisfying constraints - and the authors in this work propose a simple approach based on projecting the policies into the constraint set, and solving the overall problem with convex optimization tools.  Experimental results are also evaluated with standard baselines, demonstrating the significance of the approach. \n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "BkgdO3S0FS", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper proposes a technique to handle a certain type of constraints involved in Markov Decision Processes (MDP). The problem is well-motivated, and according to the authors, there is not much relevant work. The authors compare with the competing methods that they think are most appropriate. The numerical experiments seem to show superiority of their method in most of the cases. The proposed method has 4 main variants: (1) define projection in terms of Euclidean distance or (2) KL-divergence, and (a) solve the projection problem exactly (usually intractable) or (b) solve a Taylor-expanded variant (so there are variants 1a,1b,2a,2b).\n\nUnfortunately, I do not feel well-qualified enough in the MDP literature to comment on the novelty, and appropriateness of comparisons. For now, I will take the authors' word, and rely on other reviewers.  The motivation of necessity of including constraints did seem persuasive to me.\n\nOverall, this seems like a nice contribution based on the importance of the problem and the good experimental results, hence I lean toward accepting.  I do have some concerns that I mention below (chiefly that the theory presented is a bit of a red herring), but it may be that the overall novelty/contribution outweight these concerns:\n\n(1) Concern 1: the theorems (Thm 3.1, 3.2) apply to the intractable version, and so are not relevant to the actual tractable version of the algorithm. These are nice motivations, but ultimately we're left with a heuristic method. Perhaps you can borrow ideas from the SQP literature?\n\n(2) Concern 2: Fig 3(e), \"Grid\" data, your algo with KL projection does worse in Reward than TRPO, which is not unexpected since TRPO ignores constraints. But the lower plot shows that TRPO actually outperforms your KL projection-based algorithm even in terms of constraint!  By trying to respect the constraint, your algorithm has made things worse.  Can you explain this phenomenon?\n\n(3) Concern 3: Thm 4.1 and Thm D.2, I don't know what you're proving because I don't know what f is. Please relate it to your problem and to your updates (e.g., Algo 1). If you are talking about just minimizing f(x) with convex quadratic constraints, then I think you are re-inventing the wheel (overall, your proof looks like you are re-inventing the wheel -- doesn't everything follow from the fact that projections operators are non-expansive?  If you scale with H (and assume it is positive definite) then you're still working in a Hilbert space, just with a non-Euclidean norm, and so you can re-use existing standard results on the convergence of projected gradient methods in Hilbert space to stationary points.\n\n\nSmaller issues:\n\n- The appendix was never referenced in the main paper. At the appropriate places in the main text, please mention that the proofs are in the appendix, and mention appendix C when discussing the PCPO update.\n\n- For the PCPO update, the theorem needs to mention that H is positive definite. Using H as the Fisher Information matrix automatically guarantees it is positive semi-definite (please mention that), so the problem is at least convex, and then you assume it is invertible to get a unique solution.\n\n- It wasn't obvious to me when the constraint set is closed and convex. Please discuss.\n\n- When H is ill-conditioned, why not regularize with the identity? You switch between H and the identity, but why not make this more continuous, and look at H + mu I for small values of mu?\n\n- Lemma D.1 is trivial if you use the definition of normal cones and subgradients. You also don't need to exclude theta from the set C, since if it is in the set C, then the quadratic term will be zero, hence less than/equal to zero.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I did not assess the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "B1xGfhvptS", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a new algorithm - Projection based Constrained Policy Optimization, that is able to learn policies with constraints, i.e., for CMDPs. The algorithm consists of two stages: first an unconstrained update for maximizing reward, and the second step for projecting the policy back to the constraint set.  The authors provide analysis in terms of bounds for reward improvement and constraint violation.  The authors characterize the convergence with two projection metrics: KL divergence and L2 norm.  The new algorithm is tested on four control tasks: two mujoco environments with safety constraints, and two traffic management tasks, where it outperforms the CPO and lagrangian based approaches.\n\n\nThis is an interesting work with impressive results.  However, this work still has a few components that need to be addressed and further clarification on novelty.  Given these clarifications in an author's response, I would be willing to increase the score.\n\n\n1) Incremental work\nThe work extends the CPO [1] with a different update rule. Instead of having the update rule of CPO that does reward maximization and constraint satisfaction in the same step, the proposed update does that in two steps.  The theory and the algorithm stem directly from the original CPO work, including appendix A-C. The authors claim that another benefit of PCPO is that it requires no hyper-tuning, but same is true for CPO (in the sense that they both don’t need Lagrange multiplier) . \n\n\n2) The utility of the performance bounds and fixed point\nThe performance bounds depend on the variable $\\delta$, which is never explained. I’m assuming it is the same $\\delta$ that is used in Lemma A.1. In that case, Theorem 4.1 tells about the existence of the fixed point of the algorithm under the assumptions specified Sec 4 (smooth objective function, twice differentiable, Hessian is positive definite).  There is no discussion regarding the comparison of the fixed-point of the algorithm with the optimal value function/policies. Also, all the analysis is with Hessian, whereas in the algorithm the Hessian is approximated via conjugate descent. \n\n\n3) How is line-search eliminated? \nOne of the benefits of the proposed algorithm is that it doesn’t require line search (Sec 1). The underlying algorithm is still based on monotonic policy improvement theory in general, and more specifically on TRPO, so it should still have line-search as part of the optimization procedure.\n\n\n\n\nReferences: \n\n[1] Joshua Achiam, David Held, Aviv Tamar, and Pieter Abbeel. Constrained policy optimization. In Proceedings of International Conference on Machine Learning, pp. 22–31, 2017.\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes a new algorithm for solving constrained MDPs called Projection Based Constrained Policy Optimization. Compared to CPO, it projects the solution back to the feasible region after each step, which results in improvements on some of the tasks considered. 

The problem addressed is relevant, as many tasks could have important constraints e.g. concerning fairness or safety. 

The method is supported through theory and empirical results. It is great to have theoretical bounds on the policy improvement and constraint violation of the algorithm, although they only apply to the intractable version of the algorithm (another approximate algorithm is proposed that is used in practice). The experimental evidence is a bit mixed, with the best of the proposed projections (based on the KL approach) sometimes beating CPO but also sometimes being beaten by it, both on the obtained reward and on constraint satisfaction. 

The method only considers a single constraint. I'm not sure how trivial it would be to add more than one constraint. The reviewers also mention that the paper does not implement TRPO as in the original paper, as in the original paper the step size in the direction of the natural gradient is refined with a line search if the original step size (calculated using the quadratic expansion of the expected KL) does violate the original constraints. (Line search on the constraint as mentioned by the authors would be a different issue). Futhermore, the quadratic expansion of the KL is symmetric around the current policy in parameter space. This means that starting from a feasible solution the trust region should always overlap with the constraint set when feasibility is maintained, going somewhat agains the argument for PCPO as opposed to CPO brought up by the authors in the discussion with R2. I would also show this symmetry in illustrations such as Fig 1 to aid understanding. 



Decision: Accept (Poster)