Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 5: Marginally below acceptance threshold
review_content: 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.



Pros:
1.  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.

2. This paper claims to have some global convergence results for CMDP. This is significant.

3. 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.

Cons:

1. 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?

2. 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?

3. The numerical examples need some improvements. It will be more convincing if the authors can demonstrate their methods on 
other standard benchmarks for constrained policy optimization (e.g. Gather, Circle, Half-Cheetah Safe, etc).



review_title: Review for "A Primal Approach to Constrained Policy Optimization: Global Optimality and Finite-Time Analysis"

final_score: rating: 6: Marginally above acceptance threshold
review_content: 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. 

On 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:

- Convergence results of Theorem 2

While 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?

The reviewer suspects that the result in Theorem is not tight, which can be possibly improved. 

- Implementation of proposed algorithm with function approximator

Algorithm 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?

On 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.  

* 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). 

* 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.

* 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)|$?

===== Post Rebuttal =====
The 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. 
review_title: simple & working algorithm, but possibly incomplete theory

final_score: rating: 5: Marginally below acceptance threshold
review_content: 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.

My 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?

Although 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?

In 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?  

review_title: Comments

final_score: rating: 7: Good paper, accept
review_content: 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.

I 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.
review_title: good theory paper

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