A Primal Approach to Constrained Policy Optimization: Global Optimality and Finite-Time Analysis
Authors: Tengyu Xu
Yingbin Liang
Guanghui Lan
Venue:  (2021)
Keywords: safe reinforcement learning
constrained markov decision process
policy optimization

Abstract: Safe reinforcement learning (SRL) problems are typically modeled as constrained Markov Decision Process (CMDP), in which an agent explores the environment to maximize the expected total reward and meanwhile avoids violating certain constraints on a number of expected total costs. In general, such SRL problems have nonconvex objective functions subject to multiple nonconvex constraints, and hence are very challenging to solve, particularly to provide a globally optimal policy. Many popular SRL algorithms adopt a primal-dual structure which utilizes the updating of dual variables for satisfying the constraints. In contrast, we propose a primal approach, called constraint-rectified policy optimization (CRPO), which updates the policy alternatingly between objective improvement and constraint satisfaction. CRPO provides a primal-type algorithmic framework to solve SRL problems, where each policy update can take any variant of policy optimization step. To demonstrate the theoretical performance of CRPO, we adopt natural policy gradient (NPG) for each policy update step and show that CRPO achieves an $\mathcal{O}(1/\sqrt{T})$ convergence rate to the global optimal policy in the constrained policy set and an $\mathcal{O}(1/\sqrt{T})$ error bound on constraint satisfaction. This is the first finite-time analysis of SRL algorithms with global optimality guarantee. Our empirical results demonstrate that CRPO can outperform the existing primal-dual baseline algorithms significantly.

Under review as a conference paper at ICLR 2021
A PRIMAL APPROACH TO CONSTRAINED POLICY OP- TIMIZATION: GLOBAL OPTIMALITY AND FINITE-TIME ANALYSIS
Anonymous authors Paper under double-blind review
ABSTRACT
Safe reinforcement learning (SRL) problems are typically modeled as constrained Markov Decision Process (CMDP), in which an agent explores the environment to maximize the expected total reward and meanwhile avoids violating certain constraints on a number of expected total costs. In general, such SRL problems have nonconvex objective functions subject to multiple nonconvex constraints, and hence are very challenging to solve, particularly to provide a globally optimal policy. Many popular SRL algorithms adopt a primal-dual structure which utilizes the updating of dual variables for satisfying the constraints. In contrast, we propose a primal approach, called constraint-rection rectiffe policy optimization (CRPO), which updates the policy alternatingly between objective improvement and constraint satisfaction. CRPO provides a primal-type algorithmic framework to solve SRL problems, where each policy update can take any variant of policy optimization step. To demonstrate the theoretical performance of CRPO, we adopt natural policy gradient (NPG) for each policy update step and show that CRPO achieves an (L)V/T) convergence rate the global optimal policy in the constrained policy set and an 0(1/ error bound on constraint satisfaction. This is the first finite-time analysis of SRL algorithms with global optimality guarantee. Our empirical results demonstrate that CRPO can outperform the existing primal-dual baseline algorithms significantly.
INTRODUCTION
Reinforcement learning (RL) has achieved great success in solving complex sequential decision- making and control problems such as Go Silver et al. (2017), StarCraft DeepMind (2019) and recommendation system Zheng et al. (2018), etc. In these settings, the agent is allowed to explore the entire state and action space to maximize the expected total reward. However, in safe RL, in addition to maximizing the reward, agent needs to satisfy certain constraints. Examples include self-driving cars Fisac et al. (2018), cellular network Julian et al. (2002), and robot control Levine et al. (2016). One standard model for safe RI. is constrained Markov Decision Process (CMDP) Altman (1999), which further requires the policy to satisfy the constraints on a number of accumulated costs. The global optimal policy in this setting the one that maximizes the reward and the same time satisties the cost constraints. In general, it is very challenging to find the global optimal policy in CMDP, as both the objective and constraints are nonconvex functions.
A commonly used approach to solve CMDP is the primal-dual method Chow et al. (2017); Tessler al. (2018); Ding et al. (2020a); Stooke et al. (2020), in which the constrained problem is converted to an unconstrained one by augmenting the objective with sum of constraints weighted by their corresponding Lagrange multipliers. Usually, Lagrange multipliers are updated in the dual space concurrently Tessler et al. (2018). Although it has been observed that primal-dual methods always converge to the feasible set in the end Ray et al. (2019), such an approach is sensitive to the initializa- tion of Lagrange multipliers and the learning rate, thus can incur extensive cost in hyperparameter tuning Achiam et al. (2017); Chow et al. (2019). Another baseline approach is constrained policy optimization (CPO), in which linearized constrained problem is solved from scratch each iteration to obtain the policy in the next step. However, a successful implementation of CPO requires a feasible initialization, which by itself can be very difficult especially with multiple constraints Ray al.

---

Under review as a conference paper at ICLR 2021
(2019). Other approaches such Lyapunov method Chow al. (2018; Dalal et al. (2018a) and interior point method Liu et al. (2019b) have also been proposed recently. However, these methods do not have clear guidance in hyperparameter tuning, and thus suffer from nontrivial cost to implement in practice Stooke et al. (2020).
2019), safety layer method
Thus, one goal here is to design an easy-to-implement SRL algorithm that enjoys the ease as uncontrained problems and readily approaches feasible points from random initialization.
In contrast to the extensive empirical studies of SRL algorithms, theoretical understanding of the convergence properties of SRL algorithms is very limited. Tessler et al. (2018) provided an asymptotic convergence analysis for primal-dual method and established local convergence guarantee under certain stability assumptions. Paternain et al. (2019) showed that the primal-dual method achieves zero duality gap, which can imply the global optimality under certain assumptions. Recently, Ding et al. (2020a) proposed a primal-dual type proximal policy optimization (PPO) and established the regret bound for linear CMDP. The convergence rate of primal-dur dual method is characterized in a concurrent work Ding et al. (2020b). So far, there exist no primal-type SRL algorithms that have been shown to enjoy global optimality guarantee under general CMDP. Further, the finite-time performance (convergence rate) has not been characterized for any primal-type SRL algorithm.
Thus, the second goal here is establish global optimality guarantee and the finite-time con- vergence rate for the proposed algorithm under general CMDP.
1.1 MAIN CONTRIBUTIONS
We propose novel Constraint- Rectiffed Policy Optimization (CRPO) approach for CMDP, where all updates are taken in the primal domain. CRPO applics unconstrained policy maximization update w.r.t. the reward the one hand, and if any constraint is violated, momentarily rectifies the policy back to the feasible set along the descent direction of the violated constraint also by applying unconstrained policy minimization update w.r.t. the constraint function. Hence, CRPO can be implemented easy as unconstrained policy optimization algorithms. It does not introduce heavy hyperparameter tuning to enforce constraint satisfaction, nor does it require initialization to be feasible. CRPO provides a primal-type framework for solving SRL problems, and its optimization update can adopt various well-developed unconstrained policy optimization methods such as natural policy gradient (NPG) Kakade (2002), trust region policy optimization (TRPO) Schulman et al. (2015), PPO, etc.
To provide the theoretical guarantee for CRPO, we adopt NPG as a representative optimizer and investigate the convergence of CRPO in two settings: tabular and function approximation, where in the function approximation setting the state space can be infinite. For both settings, we show that CRPO converges to global optimum at convergence rate of (1/vT)). Furthermore, the constraint satisfaction error converges to zero at a rate of O(I/VT). To the best of our knowledge, CRPO is the first primal-type SRL algorithm that has provably global optimality guarantee. This work also provides the first tiiie--time analysis for SRL algorithm without restrictive assumptions on CMDP.
Our experiments demonstrate that CRPO outperforms the baseline primal-dual algorithm with higher return reward and smaller constraint satisfaction error.
1.2 RELATED WORK
Safe RL and CMDP: Algorithms based on primal-dual methods have been widely adopted for solving constrained RL problems, such as PDO Chow et al. (2017), RCPO Tessler et al. (2018), OPDOP Ding et al. (2020a) and CPPO Stooke et al. (2020). The effectiveness of primal-dual methods justified in Paternain et al. (2019), in which zero duality gap is guaranteed under certain assumptions. Constrained policy optimization (CPO) Achiam et al. (2017) extends TRPO to handle constraints, and is later modified with a two-step projection method Yang et al. (2019a). Other methods have also been proposed. For example, Chow et al. (2018; 2019) leveraged Lyapunov functions to handle constraints. Yu et al. (2019) proposed a constrained policy gradient algorithm with convergence guarantee by solving sequence of sub-problems. Dalal et al. (201 8a) proposed to add safety layer to the policy network so that constraints can be satisfied at each state. Liu et al. (2019b) developed an interior point method for safe RL, which augments the objective with logarithmic barrier functions. This paper proposes a CRPO algorithm, which can be implemented as easy as unconstrained policy optimization methods and has global optimality guarantee under general CMDP.
2

---

Under review as a conference paper at ICLR 2021
The finite-time analysis of various policy optimiza- tion algorithms have been well studied. The convergence rate of policy gradient (PG) and actor-critic (AC) algorithms have been established in Shen et al. (2019); Papini et al. (2017: 2018); Xu et al. (2020a; 2019); Xiong et al. (2020); Zhang et al. (2019) and Xu et al. (2020b); Wang et al. (2019); Yang et al. (2019b); Kumar et al. (2019); Qiu et al. (2019), respectively, in which PG or AC algorithm is shown to converge to a local optimal. In some special settings such as tabular and LQR, PG and AC can be shown to convergence to the global optimal Agarwal et al. (2019); Yang et al. (2019b); Fazel et al. (201 8); Malik et al. (201 8); Tu & Recht 22018;; Bhandari & Russo (2019; 2020). Algorithms such as NPG, NAC, TRPO and PPO explore the second order information, and achieve great success in practice. These algorithms have been shown to converge to global optimum in various settings, where the convergence rate has been established in Agarwal et al. (2019); Shani et al. (2019); Liu et al. (2019a); Wang et al. (2019); 9); Cen et al. (2020); Xu et al. (2020c). However, all the above studies only consider unconstrained MDP. A concurrent and independent work Ding et al. (2020b) established the global convergence rate of primal-dual method for CMDP under weak Slater's condition assumption. So far the finite-time performance of primal-type policy optimization in general CMDP settings has not been studied. Our work is the first one that establishes such result.
Finite-Time Analysis of Policy Optimization:
PROBLEM FORMULATION AND PRELIMINARIES
2.1 MARKOV DECISION PROCESS
A discounted Markov decision process (MDP) is a tuple (S, co. P,E, where S and A are state and action spaces; oo : A S ->
the reward function; P S x SxAxS - [0, 1] is the transition kernel, with P(s'|s. s. a) denoting the probability of transitioning to state s' from previous state s given action a; : S + [0, 1] is the initial state distribution; and 7 E (0. 1) is the discount factor. A policy S - P(A) is mapping from the state space to the space of probability distributions over the actions, with r-|(s) denoting the probability of selecting action a in state s. When the associated Markov chain P(s'|s) -EaP( P(s'ls. [s, a) is ergodic, denote He, as the stationary distribution of this MDP, i.e. [S ((s')s))u, (ds) = fxx (s').. Moreover, we define the visitation measure induced by the police π as V/ (s, (1 (1-7) E PP((s 8, at =a).
For given policy æ, we define the state value function as V22 = D at, 1(+1) 1
T.. the state-action value function as 2% a) E B o 7 (oco ae $1+1)|s0 = 8, ag = a, T]. and the advantage function as 1 a) = 04 a) - (s). In reinforcement learning, we aim to find an optimal policy that maximizes the expected total reward function defined Jo(m)
B 2'co p'coos:, at s(+1)] = [<[V = Ee (s, as)
2.2 CONSTRAINED MARKOV DECISION PROCESS
A constrained Markov Decision Process (CMDP) is an MDP with additional constraints that restrict the set of allowable policies. Specifically, when taking action at some state, the agent can incur a number of costs denoted by C1, , Cp. where each cost function q : S x A x S - I maps a tuple (s, a, s') to cost value. Let (T() denotes the expected total cost function with respect to o, as (((T) = [ A'cs ca, at2 884 11). The goal of the agent in CMDP is to solve the following constrained problem
JoT)) subject Ji(T) di, 11 .P.
(1)
where d, is fixed limit for the i-th constraint. We denote the set of feasible policies 2g = {I Vi, (TT) I d.). and define the optimal policy for CMDP as ' = arg min Ju(T). For each cost cs we define its corresponding state value function Vi state-action value function Q and advantage function A analogously to V2. Qa and 4 with c; replacing co. respectively.
2.3 POLICY PARAMETERIZATION AND POLICY GRADIENT
In practice, a convenient way to solve the problem eq. (1) is to parameterize the policy and then optimize the policy over the parameter space. Let (m S - P(A)] W) be a parameterized policy class, where Wi is the parameter space. Then, the problem in eq. (1) becomes
max Jo(Tw), subject (T... d.. =i= 1, ,P.
(2)
The policy gradient of the function J((TTT) has been derived by Sutton et al. (2000) as (...)..))) = E(Q (s, (5,a) (s, a)). where (s, a) == V., log (als) is the score function. Furthermore, the
3

---

Under review as a conference paper at ICLR 2021
Algorithm 1 Constraint-Rectifee Policy Optimization (CRPO)
1: Initialize: initial parameter wo, empty set Noo
2: for t= 0,... , -'-1
do
Policy evaluation under muy to obtain Qi a) = Qt (s,a)
4: Sample (s3. 4z) E B,, compute B, = Eees, Ps. Ps. (z), for 0,... ps (p5, is weight)
J.,, S d: + 1) for i 1, ................................ p, then
6:
Add wi into set No
7:
Take one-step policy update towards maximize do(w:): we+1
8:
else
Choose any d E fl,.... pt such that J,,.8, > di, +1 10: Take one-step policy update towards minimize Ji, (ws):: we - we+1
11:
end if
12:
end for
13:
Output: Wast randomly chosen from No with uniform distribution
natural policy gradient was defined by Kakade (2002) as A,(w) (J where F(w) is the Fisher information matrix defined as F(w) Bv. ( T.
3 CONSTRAINT-RECTIERS POLICY OPTIMIZATION (CRPO) ALGORITHM
In this section, propose the CRPO (see Algorithm 1) approach for solving CMDP problem in eq. (2). The idea of CRPO lies in updating the policy to maximize the unconstrained objective function Jo( (w,) of the reward, alternatingly with rectifying the policy reduce constraint function Ji(TT.)) ) (i 2 1) (along the descent direction of this constraint) if is violated. Each iteration of CRPO consists of the following three steps.
Policy Evaluation: At the beginning of each iteration, we estimate the state-action value function Qh (5,a) 2 Qi.,. (s,a) (i (0. .P}) for both reward and costs under current policy Twy
Constraint Estimation: After obtaining Qz, the constraint function (ww+ - Ee u.. Q can then be approximated via a weighted sum of approximated state-action value function: Jr, EjeB, Pj.x (ss,, az). Note this step does not take additional sampling cost, as the generation of samples (*j, az) B, does not require the agent to interact with the environment.
= (8, a)l
Policy Optimization: We then check whether there exists an it E (1,....,) .P} such that the approxi- mated constraint Jr, BB, violates the condition J.,, 5, < d, + 77, where 1) is the tolerance. If so, we take one-step update of the policy towards minimizing the corresponding constraint function Jr, (Tw)) to enforce the constraint. If multiple constraints are violated, we can choose to minimize any one of them. If all constraints are satisfied, we take one-step update of the policy towards maximizing the objective function Jo( (w.T),. ). To apply CRPO in practice,
any policy optimization update such as NPG, TRPO, PPO Schulman et al. (2017), ACKTR Wu et al. (2017), and SAC Haarnoja et al. (2018), etc, in the policy optimization step (line 7 and line 10).
Differently from previous SRL algorithms, which usually take nontrivial costs to deal with the constraints Chow et al. (2017); Tessler al. (2018); Yang al. (2019a); Chow et al. (2018: 2019); Liu et al. (2019b); Dalal et al. (2018a), our CRPO algorithm essentially performs unconstrained policy optimization alternatingly on different objectives during the training, and thus can be implemented as easy as unconstrained policy optimization algorithms without introducing heave hyperparameter tuning and additional initialization requirement.
CRPO algorithm is inspired by, yet very different from the cooperative stochastic approximation (CSA) method Lan & Zhou (2016) in optimization literature. First, CSA designed for convex optimization subject to convex functional constraint, and is thus not capable of handling the more challenging SRL problems eq. (2), which are nonconvex optimization subject to nonconvex functional constraints. Second, CSA is designed to handle only single constraint, whereas CRPO can handle multiple constraints with guaranteed constraint satisfaction and global optimality. Third, CSA assumes the accessibility of unbiased estimators of both gradient and constraint, while in our problem both the NPG update and constraints are estimated through the random output from the critic, thus requiring developing new analysis framework handle this more challenging setting.
4

---

Under review as a conference paper at ICLR 2021
4 CONVERGENCE ANALYSIS OF CRPO
In this section, we take NPG as a representative optimizer in CRPO, and establish the global convergence rate of CRPO in both the tabular and function approximation settings. Note that TRPO and ACKTR update can be viewed as the NPG approach with adaptive stepsize. Thus, the global convergence property we establish for NPG implies similar convergence guarantee of CRPO that takes TRPO or ACKTR as the optimizer.
4.1 TABULAR SETTING
In the tabular setting, we consider the softmax parameterization. For any w E IRIS x|A|, the corresponding softmax policy Tw is defined as
exp(w(s,a))
(a)a)) = Enred exp(u(ss
E
(3)
Clearly, the policy class defined in eq. (3) is complete, as any stochastic policy the tabular setting can be represented in this class.
To perform the policy evaluation in Algorithm (line 3), we adopt the temporal difference (TD) learning, in which vector 0' E RIS is used to estimate the state-action value function Q s.. for all i == 0, Specifically, each iteration of TD learning takes the form of
Policy Evaluation:
(s,1 (),s))) Ae(cc(s,,, (5,,"' (s'(ssssss) a') (%(s)
(4)
where 8 ~ u a a Tue (-18), s' ~ P[-|s, a), a' ~ (-)(-16). and 3x is the learning rate. In line 3 of Algorithm perform the TD update in eq. (4) for Kin iterations. It has been shown in Dalal et al. (2018b) that the iteration in eq. (4) of TD learning converges to fixed point 02 (TT) || Each component the fixed point is the corresponding state-action value: f (s, a) = Q: (s. The following lemma characterizes the convergence rate of TT learning in the tabular setting.
Lemma (Dalal al. (2019)). Consider the iteration given in eq. (4) with arbitrary initialization
8. Assume that the stationary distribution P.... is not degenerate for all w E R [[S))
Let stepsize
Bx = ( (0 < a < 1). Then, with probability at least - 8, we have
10x (TT =0 ( [log[ [og[[S]] |A| |A| K2)8)
(1 K
Note that a can be arbitrarily close to After performing Kin iterations of TD learning as eq. (4), we let (s a)- k.. (8, a) for all (s, a) E S A and all {0, ... .P) Lemma implies that we can obtain an approximation Qi such that | Q ll. O(1/ Kin) with high probability.
Constraint Estimation: In the tabular setting, we let the sample set B, include all state-action pairs, i.e., B, S x A, and the weight factor be Pj.t {(,))TTr, (aylı;) for all
T Then, the estimation error of the constraints can be upper bounded [J, J, (.()) [E a)] E|Qi.. (s, a)] < (0:) Øi 112. Thus, our approximation of constraints is accurate when the approximated value function ( a) is accurate.
Policy Optimization: In the tabular setting, the natural policy gradient of Jj (mw) is derived by (1 >) (>)-i1't (s, a). Once we obtain an approximation (s a) Q (s, a). we can use it to update the policy in the upcoming policy optimization step:
Agarwal et al. (2019) as Al(w),,
W++1 = wi a (line 10), W++1 = we + aáe, (line 7) or
(5)
where > 0 is stepsize and (s (1-7) a) (line 7) or (1 a) (line 10). Recall that x denotes the optimal policy in the feasible set lc. The following theorem characterizes the convergence rate of CRPO in terms of the objective function and constraint error bound.
Theorem 1. Consider Algorithm 1 in the tabular setting with softmax policy parameterization defined in eq. (3) and any initialization Wo E [ Suppose that the policy evaluation update in eq. (4) takes Kin (TTio (1 1 -7)--fo 2og2/a (T1+2/0 (8)) iterations. Let the tolerance n)
O (( [S] [A][(( - (1)1.//T) and perform the NPG update defined in eq. (5) with a (1
7) 1.5 / [S] T. Then, with probability at least 1 5, we have
VIST
Jo(TT) E[Jo (Wour)) 5
and [[J((Wo]]] - -d; 50
(1 (1-7)LoVT
11-2)166TT
5

---

Under review as a conference paper at ICLR 2021
for all i {1, .P). where the expectation is taken with respect selecting Wour from No-
As shown in Theorem 1, starting from an arbitrary initialization, CRPO algorithm is guaranteed to converge to the globally optimal policy x' in the feasible set Sg at a sublinear rate (LI/VT), and the constraint satisfaction error of the output policy converges to zero also at a sublinear rate
O(1/ (T). Thus, to attain Wout that satisfies J=(x") B[Jo(wou)] I and [EJ. d3 S for all 1 < < p. CRPO needs at most T = ( 2) iterations, with each policy evaluation step consists of approximately Kin ((T) iterations when a is close 1.
4.2 FUNCTION APPROXIMATION SETTING
In the function approximation setting, we parameterize the policy by two-layer neural network together with the softmax policy. We assign a feature vector (1ss a) E IRd with 2 2 for each state- action pair (8, a). Without loss of generality, we assume that [|v, a)ll < 1 for all (s, a) E S x A. two-layer neural network a(), W, b) with input (bs a) and width m takes the form of
((s,a);W,b)
VI Σ b, RRLLUW, a)s, ((s,0)
1
(6)
where ReLU(x) = (xx > 0) Ir, and b= [b,...... .nl E IR' and W = are the parameters. When training the two-layer neural network, we initialize the parameter via [Wa]. ~ Dw and b, ~ Unif[ 1, independently. where D', is distribution that satisfies d1 I [[ S d2 (where d1 and d2 are positive constants), for all [Wa]- in the support of D During training, we only update W and keep b fixed, which is widely adopted in the convergence analysis of neural networks Cai et al. (2019); Du et al. (2018). For notational simplicity, we write f((s, a); W,6) 6) as [(s,, a); W) in the sequel. Using the neural network in eq. (6), we define the softmax policy
W. -WT...... WTIT ml E Rmd
exp(r f((s a); W))
T (a|s) = E. exp(T f((x,, a'); W))
where T is the temperature parameter, and it can be verified that क.p (als) (als).)) We define the feature mapping dw (8, a) = ( (s, a)T
on (s. a) J Rd Rmnd as
br (W, v(s a) > 0) (ss a) V(s, a) E E x A, Wr (1,..., mm.. vm
ow a)
Policy Evaluation: To estimate the state-action value function in Algorithm 1 (line 3), we adopt another neural network f((s, a): 6') as an approximator, where f((s,a); a); 8*) has the same structure as [((s, a); W). with W replaced by 0 E Rund in eq. (7). To perform the policy evaluation step, we adopt the neural TD method proposed in Cai et al. (2019). Specifically, we choose the same initialization as the policy neural work, i.e., 66 Wo, and perform the neural TD iteration
0/41/2 = 0% + ((ci a, 8') + 7f(((' (('(((''');d)) f((s, a) V()
(8)
0 arg min ( 0h+2/2|1
(9)
#g F
where ~ Mrw, a ~ TW (-s),, s' ~ P(-)s, d' ~ (-Is') 3 is the learning rate, and B is a compact space defined as
(0 E R 110 -00-6) 0b1l2 S R). For simplicity, we denote the state-action pair as x = (s, a) and x' = (s'aa) in the sequel. We define the temporal difference error as 6g (z. x', 0%) = f(x 8() (x(,, 0.) cx 2²k,, stochastic semi- oemiiggrdient as g& (0f.) 5e.(ar x/ r( ) VoJ (xx, ).). and full semi remi-gradient as Đr (o) Ey [r, x', O V of (ar, {.)]. We then describe the following regularity conditions on the stationary distribution Howw and state-action
value function Qi which are also adopted in the analysis of neural TD learning in Cai et al. (2019).
There exists constant Co such that for any T + 0, Rd with ||=||| = 1 and TW. it holds that P (|x" Vss a)) <T I Co - T, where (s, a) Paw-
Assumption 1.
Assumption 2. We define the following function class:
FR. {{(((s,));0) f((s,)):00)+ + (0T ((s,a) a) 0) X(O) (N))Tu(s (ls a)dp(1))
where f((s, a); 0g) is the two-layer neural network corresponding the initial parameter 0g Wo. x(0): : Bdd + Rd is weighted function satisfying [|\w)) I R/ R//d,, Vd, and p(-) Rdd R is the density Da.. We assume that Qaw FRooo for all aw and = {0. ... .P).

---

Under review as a conference paper at ICLR 2021
Assumption 3. For the visitation distribution of the global optimal policy v², there exist constants CRN such that for all Tw, the following holds
de (x) [ddlirue (xr)
2
dpwo (1) S CRN-
(10)
Assumption 1 implies that the distribution of 15(8, a) has uniformly upper bounded probability density over the unit sphere. Assumption 2 is a mild regularity condition on Q as FR,so is function class of neural networks with infinite width, which captures a sufficiently general family of functions. We further make the following variance bound assumption of neural TD update.
Assumption 4. For any parameterized policy TW there exist constant C2 > 0 such that exp (I (0t) - (xx))))l /C?) < 1 for all & 2 O.
BRow
Assumption 4 implies that the expectation of variance error [[c((0))) is bounded, which has been verified in (Cai al., 2019, Lemma 4.5). The following lemma provides the convergence rate of neural TD learning. Note that the convergence rate of neural TD in expectation has already been establish in Cai al. (2019); Wang al. (2019). Here we characterize a stronger result on the convergence rate in high probability, which is needed for the analysis of our algorithm.
Lemma (Convergence rate of neural TD in high probability). Considering the neural TD iteration
defined in eq. (8). Let 0K- = K Ek-1 Og be the average of the output from k: = to K Let (i(s,)) a) = f((s, Oxx)) be an estimator of Qz,,,, (s,a). Suppose Assumptions 1-4 hold, assume that the stationary distribution Pxw is not degenerate for all W E B, and let the stepsize 1)/12). Then, with probability at least 6, we have
B = =min(1//e/
[Qi(s.a) - Pz,, wr (s, (b.a) se (0(1))))
log (t) 9
(1 73 log σ
(1-
Lemma implies that after performing the neural TD learning in eq. (8).eq. (9) for ((v iterations, we can obtain an approximation Qi such that ||Q] Qn,,,, ll,, = ((1/mm1mm))) 1//m 1/5) with high probability.
Constraint Estimation: Since the state space is usually very large or even infinite in the function approximation setting, we cannot include all state-action pairs to estimate the constraints as for the tabular setting. Instead, we sample batch of state-action pairs (sj.aj) E B, from the distribution <()),w; (-I-), and let the weight factor be P3 = 1/ [5,] for all j. In this case, the estimation error of the constrains [J{(O)) - [ is small when the policy evaluation Qi is accurate and the batch size [B.] is large. We assume the following concentration property for the sampling process in the constraint estimation step, which has also been taken in Lan & Zhou (2016).
Assumption 5. For any parameterized policy Tw there exists a constant Cj > O such that Eg-ww (xp(((Q(ss a) - -Eg [Q](s, ())3/))))( < 1orr all l: 2 0.
Policy Optimization: In the neural softmax approximation setting, at each iteration t, an approxima- tion the natural policy gradient can be obtained by solving the following linear regression problem Wang et al. (2019); Agarwal et al. (2019):
A (W)) x A. = arg min Eve,,
[[Q a) - ow, (s, a) T))?).
(11)
#EB
Given the approximated natural policy gradient A. the policy update takes the form of
TH+ = Te + a, Te+1 01-1 = T Ws + a.. (line 7) or T++1 We+1 = T: - we a.. (line 10).
(12)
Note that eq. (12) we also update the temperature parameter by T++1 = T. + a simultancously. which ensures wi E B for all t. The following theorem characterizes the convergence rate of Algorithm in terms of both the objective function and constraint error.
Theorem 2. Consider Algorithm I in the function approximation setting with neural sofimax policy parameterization defined in eq. (7). Suppose Assumptions 1-5 hold. Suppose the same setting of policy evaluation step stated in Lemma 2 holds, and consider performing the neural TD in eg. (8) and
eq. (9) with Km O(11 - /m)) at each iteration. Let the tolerance 1 = (m - -t//
7

---

Under review as a conference paper at ICLR 2021
(1-7)-225m" and perform the NPG update defined in eq. (12) with 0(1/VT). Then with probability least 6, we have
( m
(1 ((--2) )):
Jo(x²) - [[ =
(1- + (1 2. 1/8 log$
and for all i 1, P. have ((Ji(TT de 5
(1 (11-2)9Tvm
m
(1 (1- 7)). 1/8 log'
(1-
where the expectation is taken only with respect to the randomness of selecting W from No.
Theorem 2 guarantees that CRPO converges to the global optimal policy π² in the feasible set at sublinear rate (11/VT)) with an optimality gap (m (m-1//8) which vanishes as the network width m increases. The constraint error bound of the output policy converges to zero also at a sublinear rate (L/vVT) with a vanishing optimality gap Om (m/)/ as m increases. The optimality gap arises from both the policy evaluation and policy optimization due to the limited expressive power of neural networks. To attain a Wout that satisfies Jo( - E[Jo(TT...W...
1/5)
S e O 1/6) and de < e (m CRPO needs at most T O(m² iterations, with each iteration contains ((vm) policy evaluation iterations. The convergence analysis in the function approximation setting is more challenging than that in the tabular setting. Since the class of neural softmax policy is not complete, we need to handle additional approximation errors introduced by the neural network parameterization. It is worth noting that CRPO is the first SRL algorithm that has global optimal guarantee the function approximation setting over general CMDP.
5 EXPERIMENT
We conduct experiments based on OpenAl gym Brockman et al. (2016) that are motivated by SRL. We consider two tasks with each having multiple constraints given as follows:
Cartpole:
The agent rewarded for keeping the pole upright, but is penalized with cost if (1)
entering into some specific areas, or (2) having the angle of pole being large.
Acrobot: The agent is rewarded for swing the end-effector at specifie height, but is penalized
with cost if (1) applying torque on the joint when the first link swings in prohibited direction, or (2) when the the second link swings in a prohibited direction with respect the first link.
The detailed experimental setting is described in Appendix A. For both experiments, we use neural softmax policy with two hidden layers of size (128, 128). In previous studies, PDO and CPO have been widely adopted as bascline algorithms. Since not assume the accessibility of a feasible policy as an initialization, baseline algorithm CPO is not applicable here. Thus, we compare CRPO only with PDO in our experiments. For fair comparison, we adopt TRPO as the optimizer for both CRPO and PDO. In PDO, we initialize the Lagrange multiplier zero in both tasks. The learning curves for CRPO and PDO provided in Figure 1. At each step we evaluate the performance based on two metrics: the return reward and constraint value of the output policy. We show the learning curve of unconstrained TRPO (the green line), which although achieves the best reward, but does not satisfy the constraints, i.e., the optimal policy obtained by such an unconstrained method infeasible. In both tasks, CRPO tracks the constraints
are considering multiple constraints and do
Constraint
Return
Constraint Values
200
200
C.
200
200
CVT contrn
160
180
160
160
18P0 cononare
18P0 cowraa
120
120
120
120
CRPO
MDO sewourdd
80
CRPO
MD0 x ae
PDO TRPO
TRPO
0 200 400
600
800
1000
200 100 600 800
1000
200 400 800 of Episodes
800
1000
200 100 600 800 1000
of Episodes
of Episodes
Episodes
(a) Cartpole
(b) Acrobot
Figure I: Average performance for CRPO, PDO, and unconstrained TRPO over 10 seeds. The red dot lines
(a) and (b) represent the limits. In Cartpole, the limits of two constraints are 40 and 10, respectively. In Acrobot, the limits of both constraints are 50.
return almost exactly to the limit, indicating that CRPO sufficiently explores the boundary of the feasible set, which results in optimal return reward. In contrast, although PDO also outputs constraints-satisfiii policy in the end, it tends to over- or under-enforce the constraints, which results in lower return reward and unstable constraint satisfaction performance.
8

---

Under review as a conference paper at ICLR 2021
6 CONCLUSION
In this paper, we propose novel CRPO approach for policy optimization in the CMDP setting, which easy to implement and has provable global optimality guarantee. We show that CRPO achieves an O / /T) convergence rate to the global optimum and an ((1/vT) rate vanishing constraint enror when NPG update is adopted as the optimizer. This is the first finite-time analysis for SRL algorithms under general CMDP. the future, it is interesting to incorporate various momentum schemes CRPO to improve its convergence performance.
REFERENCES
Joshua Achiam, David Held, Aviv Tamar, and Pieter Abbeel. Constrained policy optimization. In International Conference Machine Learning (ICML), pp. 22-31, 2017.
Alekh Agarwal, Sham M Kakade, Jason Lee, and Gaurav Mahajan. Optimality and approximation with policy gradient methods in Markov decision processes. arXiv preprint arXiv: /908. 00261, 2019.
Eitan Altman. Constrained Markov decision processes, volume 7. CRC Press, 1999.
Jalaj Bhandari and Daniel Russo. Global optimality guarantees for policy gradient methods, arXiv preprint arXiv:1906.01770 2019.
Jalaj Bhandari and Daniel Russo. A note the linear convergence of policy gradient methods. arXiv preprint arXiv:2007.1 /20, 2020.
Greg Brockman, Vicki Cheung. Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojciech Zaremba. OpenAl Gym, 2016.
Qi Cai, Zhuoran Yang, Jason D Lee, and Zhaoran Wang. Neural defforal- and q-learning provably converge to global optima. arXiv preprint arXiv:1905. 2019.
Shicong Cen, Chen Cheng, Yuxin Chen, Yuting Wei, and Yuejie Chi. Fast global convergence of natural policy gradient methods with entropy regularization. arXiv preprint arXiv:2007.06558, 2020.
Yinlam Chow, Mohammad Ghavamzadeh, Lucas Janson, and Marco Pavone. Risk-constrained reinforcement learning with percentile risk criteria. The Journal of Machine Learning Research, 18(1))6070-6120, 2017.
Yinlam Chow, Ofir Nachum, Edgar Duenez-Guzman, and Mohammad Ghavamzadeh. A Lyapunov- based approach to safe reinforcement learning. In Advances Neural Information Processing Systems (NIPS), pp. 8092-8101, 2018.
Yinlam Chow, Ofir Nachum, Aleksandra Faust, Edgar Duenez-Guzman and Mohammad Ghavamzadeh. 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:/801.008 00855777777... 20.8a.
Gal Dalal, Balázs Szörényi, Gugan Thoppe, and Shie Mannor. Finite sample analyses for TD (0) with function approximation. Proc. AAA/ Conference on Artificial Intelligence (AAAI), 2018b.
Gal Dalal, Balazs Szorenyi, and Gugan Thoppe. A tale of two-timescale reinforcement learning with the tightest finite-time bound. arXiv preprint 19XXvv9911.0911 2019.
Alphastar DeepMind. Mastering the real-time strategy game starcraft ii 2019.
Dongsheng Ding, Xiaohan Wei. Zhuoran Yang. Zhaoran Wang, and Mihailo R Jovanovié. Provably efficient safe exploration via primal-dual policy optimization. arXiv preprint arXi::2033.00534 2020a.

---

Under review as a conference paper at ICLR 2021
Dongsheng Ding, Kaiqing Zhang, Tamer Basar, and Mihailo Jovanovic. Natural policy gradient primal-dual method for constrained Markov decision processes. In Proc. Advances in Neural Information Processing Systems (NeurlPS), 33, 2020b.
Simon S Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes over- parameterized neural networks. In In Proc. International Conference on Learning Representations (ICLR), 2018.
Maryam Fazel, Rong Ge, Sham M Kakade, and Mehran Mesbahi. Global convergence of policy gradient methods for the linear quadratic regulator. arXiv preprint arXiv:1801.05039 2018.
Jaime F Fisac, Anayo K. Akametalu, Melanie N Zeilinger. Shahab Kaynama, Jeremy Gillula, and Claire Tomlin. A general safety framework for learning-based control in uncertain robotic systems. IEEE Transactions Automatic Control, 64(7):2737-25) 2018.
Saeed Ghadimi and Guanghui Lan. Stochastic zeroth-orrde methods for nonconvex stochastic programming. SIAM Journal on Optimization, 23(4):2341223 2013.
Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor. In In Proc. International Conference on Machine Learning (ICML.), pp. 1861-1870, 2018.
David Julian, Mung Chiang, Daniel O'Neill, and Stephen Boyd. Qos and faimesss constrained convex optimization of resource allocation for wireless cellular and ad hoc networks. In In Proc. Conference of the IEEE Computer and Communications Societies, volume 2, pp. 477-486. IEEE, 2002.
Sham Kakade and John Langford. Approximately optimal approximate reinforcement learning. In
Proc. International Conference on Machine Learning (ICML), volume 2, pp. 267-274, 2002.
Sham M Kakade. A natural policy gradient. In Proc. Advances Neural Information Processing Systems (NIPS), pp. 1531-1538, 2002.
Harshat Kumar, Alec Koppel, and Alejandro Ribeiro. On the sample complexity of actor-critic method for reinforcement learning with function approximation. arXiv preprint 1rX1v:1910.08412. 2019.
Guanghui Lan and Zhiqiang Zhou. Algorithms for stochastic optimization with functional or expectation constraints. arXiv preprint arXiv: /604.0887 2016.
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.
Boyi Liu, Qi Cai, Zhuoran Yang, and Zhaoran Wang. Neural proximal/trust region policy optimization attains globally optimal policy. In Proc. Advances in Neural Information Processing Systems (NeulPS), 2019a.
Yongshuai Liu, Jiaxin Ding, and Xin Liu. Ipo: interior-point policy optimization under constraints. arXiv preprint arXiv:1910.0960 2019b.
Dhruv Malik, Ashwin Pananjady, Kush Bhatia, Koulik Khamaru, Peter L Bartlett, and Martin J Wainwright. Derivative-free methods for policy optimization: guarantees for linear quadratic systems. arXiv preprint arXiv:18/2.08305. 2018.
Matteo Papini, Mattco Pirotta, and Marcello Restelli. Adaptive batch size for safe policy gradients. In Advances in Neural Information Processing Systems (NIPS), pp. 3591-3600, 2017.
Matteo Papini, Damiano Binaghi, Giuseppe Canonaco, Matteo Pirotta, and Marcello Restelli. Stochas- tic variance-reduced policy gradient. International Conference on Machine Learning (ICML., pp. 4026-4035, 2018.
Santiago Paternain. Luiz Chamon, Miguel Calvo-Fullana, and Alejandro Ribeiro. Constrained reinforcement learning has zero duality gap. In In Proc. Advances Neural Information Processing Systems (NeurIPS), pp. 7555-7565, 2019.
10

---

Under review as a conference paper at ICLR 2021
Shuang Qiu, Zhuoran Yang. Jieping Ye, and Zhaoran Wang. On the finite-time convergence of actor-critic algorithm. In Optimization Foundations for Reinforcement Learning Workshop at Advances in Neural Information Processing Systems (NeurlPS), 2019.
Ali Rahimi and Benjamin Recht. Weighted sums of random kitchen sinks: replacing minimization with randomization in learning. In Advances in Neural Information Processing Systems (NIPS), pp- 1313 1320, 2009.
Alex Ray, Joshua Achiam, and Dario Amodei. Benchmarking safe exploration in deep reinforcement learning. arXiv preprint arXiv: 1910.01700 2019.
John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz. Trust region policy optimization. In In Proc. International Conference on Machine Learning (ICML), pp. 1889-1897, 2015.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv: 1707.06777 2017.
Lior Shani, Yonathan Efroni, and Shie Mannor. Adaptive trust region policy optimization: Global convergence and faster rates for regularized mdps. arXiv preprint arXiv: 1909.02769, 2019.
Zebang Shen, Alejandro Ribeiro, Hamed Hassani, Hui Qian, and Chao Mi. Hessian aided policy gradient. International Conference on Machine Learning (ICML). pp. 5729-5738, 2019.
David Silver, Julian Schrittwieser, Karen Simonyan, loannis 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):54--399 2017.
Adam Stooke, Joshua Achiam, and Pieter Abbeel. Responsive safety in reinforcement learning by pid lagrangian methods. In In Proc. International Conference on Machine Learning (ICML), 2020.
Richard S Sutton, David A McAllester, Satinder P Singh, and Yishay Mansour, Policy gradient methods for reinforcement learning with function approximation. In Proc. Advances in Neural Information Processing Systems (NIPS), pp. 1057-1063, 2000.
Chen Tessler, Daniel Mankowitz, and Shic Mannor. Reward constrained policy optimization. In Proc. International Conference on Learning Representations (ICLR), 2018.
Stephen Tu and Benjamin Recht. The gap between model-based and model-free methods the linear quadratic regulator: an asymptotic viewpoint. arXiv preprint arXiv:1812.00355,, 2018.
Lingxiao Wang. Qi Cai, Zhuoran Yang, and Zhaoran Wang. Neural policy gradient methods: Global optimality and rates of convergence. arXiv preprint 1909v09900001 150, 2019.
Yuhuai Wu, Elman Mansimov, Roger B Grosse, Shun Liao, and Jimmy Ba. Scalable trust-region method for deep reinforcement learning using kromecker-factoree factored approximation. In In Proc. Advances in Neural Information Processing Systems (NIPS), pp. 5279-5288, 2017.
Huaqing Xiong, Tengyu Xu, Yingbin Liang, and Wei Zhang. Non-asympiotic convergence of adam-type reinforcement learning algorithms under Markovian sampling. arXiv preprint arXiv:2002.06286, 2020.
Pan Xu, Felicia Gao, and Quanquan Gu. An improved convergence analysis of stochastic variance- reduced policy gradient. Proc. International Conference on Uncertainty in Artificial Intelligence (UAI), 2019.
Pan Xu, Felicia Gao, and Quanquan Gu. Sample efficient policy gradient methods with recursive variance reduction. In Proc. International Conference on Learning Representations (ICLR), 2020a.
Tengyu Xu, Zhe Wang, and Yingbin Liang. Improving sample complexity bounds for actor-critic algorithms. arXiv preprint arXiv:2004. 12956, 2020b.
Tengyu Xu, Zhe Wang, and Yingbin Liang. Non Non-asymptoter convergence analysis of two time-scale (natural) actor-critic algorithms. arXiv preprint arX5v:2005.035577 2020c.

---

Under review as a conference paper at ICLR 2021
Tsung- Yen Yang, Justinian Rosca, Karthik Narasimhan, and Peter J Ramadge. Projection based constrained policy optimization. In Proc. Internationaa Conference on Learning Representations (ICLR), 2019a.
Zhuoran Yang, Yongxin Chen, Mingyi Hong, and Zhaoran Wang. Provably global convergence of actor-critic: A case for linear quadratic regulator with ergodic cost. In Proc. Advances in Neural Information Processing Systems (NeurIPS), pp. 8351-8363, 2019b.
Ming Yu, Zhuoran Yang, Mladen Kolar, and Zhaoran Wang. Convergent policy optimization for safe reinforcement learning. In In Proc. Advances in Neural Information Processing Systems (NeurIPS), pp. 3127-3139, 2019.
Kaiqing Zhang, Alec Koppel, Hao Zhu, and Tamer Başar. Global convergence of policy gradient methods (almost) locally optimal policies. arXiv preprint /96.03390 2019.
Guanjie Zheng, Fuzheng Zhang, Zihan Zheng, Yang Xiang, Nicholas Jing Yuan, Xing Xie, and Zhenhui Li. Drn: A deep reinforcement learning framework for news recommendation. In In Proc. World Wide Web Conference, pp. 167-176, 2018.
12


Reviews:
[{"review_id": "kKVHhbx2cgI", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "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 method for constrained MDP. The proposed method does not require primal-dual formulation and is easy to implement given the availability of state-of-the-art policy optimization solvers.  When the natural policy gradient is used as the  policy optimizer,  a sublinear global convergence rate is proved for both the tabular setting and the function approximation case.\n\n\n\nPros:\n1.  This paper is quite original. Although the paper is inspired by the cooperative stochastic approximation method in optimization literature, significant efforts have been made to adapt things to the CMDP setup.\n\n2. This paper claims to have some global convergence results for CMDP. This is significant.\n\n3. The proposed method is easy to implement. The constrained policy optimization problem is almost transferred to some unconstrained sub-tasks such that existing policy optimization solvers can be directly used.\n\nCons:\n\n1. I don't follow the proof very well. I am not convinced how the proposed method achieved global optimality. Even the high-level proof idea is unclear to me. Here is one example confusing me. Say we t have two functions J_1 and J_0. In addition, we have J_1=J_0. It seems possible that we will have some limit cycle in this case. One does a maximization on J_0 but realizes the constraint on J_1 is violated. Then a minimization on J^1 is done and then the next step of maximizing J^0 may send the policy weight back to the same point.  On the conceptual level, minimizing the constraint function can send the policy weight towards the opposite direction of maximizing J_0, and the iterations may bounce around and be stuck in limit cycle (around local min). Can the authors provide some proof sketch to explain why such cases can be avoided?\n\n2. I am also confused by the assumptions. Does the author assume that there exists a unique solution for the CMDP problem? Can the authors clarify the assumptions in Section 4.2? Are these assumption true for the two examples considered in this paper?\n\n3. The numerical examples need some improvements. It will be more convincing if the authors can demonstrate their methods on \nother standard benchmarks for constrained policy optimization (e.g. Gather, Circle, Half-Cheetah Safe, etc).\n\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "Wg-sT2wlEAG", "reviewer": "AnonReviewer1", "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": "This paper proposes an algorithm called CRPO to solve the constraint reinforcement learning. Different from the literature, where the primal-dual formulations are widely used, this paper introduces a pure primal algorithm. The motivation of this paper is clear, since in practice the primal-dual formulation is hard to train and needs much effort on the hyperparameter tuning. Thus I think the pure primal algorithm is an interesting direction of constrained RL. Another merit of this paper is that it avoids the projection step in literature. It does the gradient step on the constraint when it is not satisfied. The author provides the convergence result both on the tabular setting and function approximation setting (two layer neural network), where it has already been known that the natural gradient can converge to the global optimal (tabular setting ) and the (shallow) neural network behaves like a convex function. I did not check the details of the proof, but the  roadmap of the proof is clear by combining existing results on RL and deep learning. At last, the author affirms their theoretical result by two toy examples on cartpole and acrobot.\n\nMy main concern comes from the novelty on the theoretical result, particularly the proof technique.  The result on the policy evaluation step mainly comes from Dalal et al, while the policy optimization step stems from Agarwal et al. When combined with function approximation setting, it adopts the analysis of the neural networks such as the result in  Du et al. The whole framework is similar to the Lan & Zhou. It seems that the author just combines all these existing results together. Can you emphasize the main theoretical contribution of this paper?\n\nAlthough this work avoids the primal-dual formulation or projection step, my feeling is that it still needs careful hyperparameter tuning. For instance , how do you pick the value of eta in the algorithm? How many policy evaluations are needed before the policy update step?\n\nIn section 4.2. The result is on the two-layer neural network(one hidden layer). However, the algorithm is tested on two hidden layer (with size (128,128)) neural networks. Is it possible to extend the theoretical result to multi-layer (more than one hidden layer) neural network?  \n", "extra_scores": {}, "extra_text": {}}, {"review_id": "CqyKfUdPHlO", "reviewer": "AnonReviewer4", "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": "This paper considers a primal approach to the constrained RL problem where the constraints have a similar form as the total reward. The paper establishes global convergence in the tabular and NTK approximation cases. The problem in the aforementioned two cases is non-convex and therefore the global convergence results are very interesting and can contribute to the RL theory community. I did not check the entire proof but believe it is correct after checking some key points and go through the technical lemmas. The assumption on the one hidden layer neural network is standard, as it is used in a series of recent literature, although it is strong compared with practical algorithms.\n\nI have a question about Lemma 1, which is borrowed from another paper and I don't have enough time to check the specific lemma in that paper and its corresponding contextures and proof. The result says policy evaluation converges to the true Q function under a uniform measure (i.e. 2-norm), while the evaluation sample comes from the policies during iteration, which probably chooses sparse actions and visits sparse states. Do I miss any assumption on the exploration ability of the policies during iteration? Similar questions arise in applying Lemma 2 to Theorem 2. In the papers on unconstrained MDP (Agarwal 19 and Wang 19), they assume bounds on the ratio of visitation measures between policies to handle this technique problem. While I seem to can not find the corresponding parts and would like to ask about the intuition behind that.", "extra_scores": {}, "extra_text": {}}, {"review_id": "82rePtBSzD", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "This paper considers safe RL through solving a constrained MDP in (1). The authors proposed a primal method which alternates between maximizing the reward and minimizing the constraint violation. The convergence rate of the algorithm is also provided under standard settings, e.g., bounded reward, iid samples, etc.. Interestingly, the authors also analyzed the case for using a 2-layer neural network (NN) function approximator for the policy and the actor. \n\nOn the upside, this paper suggested a simple algorithm for a new problem that has not been studied extensively yet and a number of settings have been covered. The authors also supplemented this work with several numerical experiments. The reviewer has a few comments / suggestions regarding the NN function approximator setting as follows:\n\n- Convergence results of Theorem 2\n\nWhile the convergence is well analyzed for the tabular setting in Theorem 1, the reviewer is concerned about the result in Theorem 2 for the case analyzed with function approximator. The latter shows that the optimality gap decays with $T,m$ as $O(m/\\sqrt{T} + \\log(T)/m^{1/8})$ - which indicates that the iteration complexity grows with $m$, i.e., the width of the 2-layer NN. This seems to be non-ideal compared to many recent works on 2-layer NN, e.g., (Cai et al., 2019) as cited in this paper, where the iteration complexity is often independent of $m$. Is there any reason behind such discrepancy in the rate? Or is there any numerical evidence which shows that such dependence on $m$ is unavoidable?\n\nThe reviewer suspects that the result in Theorem is not tight, which can be possibly improved. \n\n- Implementation of proposed algorithm with function approximator\n\nAlgorithm 1 combines a policy evaluation step and the policy gradient step. In particular, the policy evaluation needs to be run with multiple steps to obtain a sufficiently accurate solution. In the case of using NN as function approximator, Lemma 1 for neural TD (Cai et al., 2019) holds with high probability w.r.t. the NN initialization, and the analysis in this paper suggests that the NN needs to be reinitialized every time when the policy is changed. Is it the same way that the algorithm is initialized?\n\nOn the other hand, the reviewer also wonders if such \"restarting\" is necessary given that the policy is updated with only 1 step of policy gradient.  \n\n* Minor point: It was mentioned that the CSA method in Lan and Zhou (2016) handles only convex functional constraints which is different from the current work. However, it is worth pointing out that in the tabular setting, the constraint, objective functions are indeed close to a linear function with respect to the policy, i.e., it is roughly convex. The authors may shed more lights on the similarity between the proposed algorithm and (Lan and Zhou, 2016). \n\n* Minor point: in the statement of Lemma 6 & 7, since the results are specialized for the case of $i=0$. It is better to use $i=0$ in the equation.\n\n* Minor point: in Assumption 1, it is not clear what do the authors mean by $P( |x^T \\psi(s,a)| ) \\leq C_0 \\tau$. What is this event of $|x^T \\psi(s,a)|$?\n\n===== Post Rebuttal =====\nThe reviewer is satisfied by the authors' response. I am fine with raising my score. In the final paper, it would be nice if the authors can include a detailed discussion about the dependence of $m$ in their results. ", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: All reviewers appreciated the main result in the paper, which gives  global optimality guarantee for constrained policy optimization for both tabular setting and NTK setting. However, there were a number of unclear parts of the paper reported by several reviewers (assumptions, hyperparameter tuning, complexity dependence on the number of neurons, experimental setups). On top of it, the AC also echoes with R1’s concern about the novelty of this work as it basically stacks existing results (TD by Dalal et al., Neural TD by Cai et al. (2019), NPG by Agarwal et al, CSA algorithm by Lan & Zhou). 
These concerns made me reticent to recommend acceptance at this point. I strongly encourage the authors to continue their interesting work in considering the reviewer comments and strengthen the numerical experiments. 

Decision: Reject