Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 5: Marginally below acceptance threshold
review_content: Summary: The paper proposes a fast method for solving reinforcement learning problems with constraints. Oracle computational and memory complexity of the proposed algorithm are provided along with experiments on a grid-world navigation task to illustrate the convergence behavior of the proposed algorithm.

Strength:

- Instead of using a penalty or a regularization scheme to impose safety, risk or budget constraints, the paper proposes to impose the constraints explicitly, or in other words treat them as hard constraints. Dealing with hard constraints is an important open problem especially in nonconvex problems as in reinforcement learning. The paper uses the reductions approach proposed in Agarwal et al, to transform the policy constrained problem to a mixed policy scheme in which finding a feasible solution is equivalent to finding a distribution over policies. Now, with this reduction, the paper leverages the fact that feasible set is guaranteed to be a polytope (given by the convex hull of all feasible policies), and hence the paper solves the equivalent problem of finding a point that minimizes the distance to the convex polytope. 

- The minimum norm point algorithm or Wolfe's method is proposed to solve the distance minimization problem. An advantage of the algorithm is that it can be used in tandem with any off-the-shelf RL algorithm while guaranteeing feasibility unlike the penalty based methods. In addition to the time complexity of the algorithm, they also provide a memory complexity bound which in some sense is inherited from the minimum norm point algorithm. The analysis in the appendix seem to use the techniques from the Chakrabarty et al paper.

Weaknesses:

- There is no discussion or comparison of subproblem complexity with respect to existing methods. I consider this paper to be a theoretical paper, and it is unfortunate that there is no mention to any practical use cases. I believe that this is an important aspect of numerical algorithm that needs to be discussed in papers. For example, it is well known that exact projections do provide strictly feasible solutions and solve a problem that is in theory equivalent. That is, if the feasible set is a polytope, Euclidean projection and minimum norm point are both generic quadratic programming problems, hence it is not clear why the minimum norm point should be preferred in reinforcement learning settings. I believe that sparsity in the intermediate iterates seem like the crucial difference, but the paper discusses this aspect merely in passing. Some specific examples of safety, risk or budget constraints and describing the subproblem complexity for such constraints will make this clear. 

- I'm not sure if the experiments are reproducible with the information provided in the paper. First, the experiments seem separate from the rest of the paper and the reader has to go over other papers to get an idea of the overall setup. For example, it is not clear why 300 steps are sufficient or what risky region is. Secondly, there is no discussion of the hyperparameters used in the experiments and algorithm. For example, how was the value of epsilon determined? the step size or learning rate? I think the paper would hugely benefit from ablation studies in more than one task, preferably something that is used in practice.

After response: Thanks for the clarifications. However, conceptually important questions are not yet clarified yet. For example,  the objective itself can be made into a pure square function (and hence strongly convex) in both classical Wolfe's formulation and the proposed. As the authors are pointing out, the main issue is in designing separation (or projection) oracle for the constraints which corresponds to the base polytope in the context of submodular optimization and was the main motivation for Wolfe's algorithm. Moreover, authors mention that main difficulty in using projections is intractability but it is not clear why the linear optimization performed in the proposed algorithm is efficient.
review_title: The paper proposes a fast method for solving reinforcement learning problems with constraints. Oracle computational and memory complexity of the proposed algorithm are provided along with experiments on a grid-world navigation task to illustrate the convergence behavior of the proposed algorithm.

final_score: rating: 5: Marginally below acceptance threshold
review_content: The authors propose C2RL to solve RL problems under convex constraints. The authors reduce the RL problem under convex constraints to a distance minimization problem and solve the distance minimization problem with a Frank-Wolfe type method (with an RL solver as a sub-routine).
The authors further show that the algorithm converges (in terms of approximation error), and validate some of their theoretical findings with simulations.

# Pros:
I like the fact that the authors have theoretical guarantees for their approximation error.
The reduction to distance minimization problem is also clear.

# Cons:
+ I find it hard to understand Section 4.3 and Section 4.4 even after quite a few passes.
This is the main reason for my score and my confidence level. For Section 4.3, while I understand how Algorithm 1 works, I have no intuitive idea why Algorithm 1 converges. There is a lack of connection to the original Wolfe's algorithm (such as what corresponds to the objection function and to the linear minimization oracle? Why the linear property of the RL-oracle is important? etc). For Section 4.4, the authors just pile-up their results without further remark on the implications.

+ I don't understand the role of the sparse policy here. Does finding a sparse policy makes the problem easier or harder? Why do we want to find a sparse policy?

+ It seems that the optimal $\mu$ is not unique, if there are multiple $\mu$ such that $c(\mu) \in \Omega$. If this is so, the analysis of the Frank-Wolfe type method could be tricky.

+ While I understand the challenges of RL problem under convex constraints, could the author list specifically what are the applications that can be formulated into RL under cvx constraints? Do we have an easy projection operator for these convex constraints? How to choose the policy set in the real world application?

Minor comments:

+ Above equation (7): “is equivalent to minimizing the distance between the polytope and the convex set”. It is misleading to talk about the distance between the two sets. Maybe "find a point in the polytope that is closest to the convex set $\Omega$"?

+ Some comments on the meaning of equation (4) should be helpful for the readers to understand the main flow

review_title: Section 4 is hard to parse

final_score: rating: 7: Good paper, accept
review_content: This paper presents a reduction approach to tackle the optimization problem of constrained RL. They propose a Frank-Wolfe type algorithm for the task, which avoids many shortcomings of previous methods, such as the memory complexity. They prove that their algorithm can find an $\epsilon$-approximate solution with $O(1/\epsilon)$ invocation. They also show the power of their algorithm with experiments in a grid-world navigation task, though the tasks looks relatively simple.

pros:
- The application of Frank-Wolfe algorithm to constrained RL problem is novel. The method is basically different from the that of Miryoosefi et al. (2019).The improvement is mainly due to the algorithm design.

- The theoretical improvement is solid. The paper tackles the memory requirement  issue in the previous literature, and only requires constant memory complexity. Further, the number of RL oracle invocation is also reduced from $O(1/\epsilon^2)$ to $O(1/\epsilon)$.

- The paper is well-written. Though I only sketched the proof in the appendix, the algorithm and the analysis in the main part is reasonable and sound.

comments:
- The algorithm requires a policy set $\mathcal{U}$ and finds a mixed policy $\mu \in \Delta(\mathcal{U})$ to satisfy the constraints. How to get a policy set with a feasible solution? Is $\mathcal{U}$ predefined? For an MDP with $S$ states and $A$ actions, the possible deterministic policy can be $A^S$. Trivially setting $\mathcal{U}$ as a set with all possible policies may lead to exponential computational and memory complexity.

- Constrained RL problem can be formulated from the standard dual LP form of RL problem, in which the policy $\pi$ can be fully represented as the density over state-action $d(s,a)$ (See e.g. [1]). Is it possible to solve constrained RL problem under this formulation? What is the advantage of using mixed policies over fixed policy set $\mathcal{U}$ compared with this formulation?

typos:
- line 3 of Algorithm 2: $(1-\eta_t w_{t-1})$ -> $(1-\eta_t) w_{t-1}$

[1] Constrained episodic reinforcement learning in concave-convex and knapsack settings
review_title: A good paper with solid theoretical improvement

final_score: rating: 6: Marginally above acceptance threshold
review_content: 1. Summarize what the paper claims to do/contribute. Be positive and generous.

In this paper, the authors consider a class of constrained MDP problem. In the considered problem, instead of getting a scalar reward, in each step, the MDP returns a vector “reward” which is termed as a measurement vector. Then the problem requires finding a (mixed) policy such that the expected measurement vector belongs to a convex set. This problem was first considered in (Miryoosefi et al. , 2019) and the authors of this paper propose a new algorithm and claim an improvement over the sparsity in the mixed policy. The main idea of the new algorithm is to solve the problem as convex minimization of the squared distance to the target set. A standard Frankwolfe-type algorithm is proposed to solve the problem, convergence and complexity analysis are also provided. 

2. Clearly state your decision (accept or reject) with one or two key reasons for this choice.
This paper is marginally above the acceptance threshold. 

3. Provide supporting arguments for the reasons for the decision. 

(i). (Weakness) A significant flaw is the WRONG claim of improvement over the previous result (Miryoosefi et al. , 2019). In this paper, the authors yield dist(c(\mu),\Omega) \leq 1/T. While (Miryoosefi et al. , 2019) proves dist(c(\mu),\Omega) \leq 1/sqrt{T}. Thus the authors claim an improved O(1/\epsilon) complexity over the O(1/\epsilon^2) complexity of the compared paper. However, this is a wrong argument. If the authors pay attention to the definition of (Miryoosefi et al. , 2019), they should find that the “dist” denotes the standard notation of Euclidean distance. However, the “dist” function in this paper is the SQUARED Euclidean distance. They are defined differently. Therefore, if we view the two results under the same optimality measure, these two complexity results are the same. No improvement is made in this paper in terms of complexity. 

(ii). (strength) Though in (i), we find there is no improvement in terms of complexity and hence the sparsity of the mixed strategy. The reason why I still think it is marginally above the threshold is that, compared to the existing approach in (Miryoosefi et al. , 2019), the Frank-Wolfe type algorithm is way more natural and robust. 

(iii). (strength) Due to the desirable structure of the Frank-Wolfe method, the authors are able to constantly eliminate the affinely dependent historical policies/measurement vectors. Thus limiting the storage memory to only m+1, where m is the dimension of the measurement vector.

4. Provide additional feedback with the aim to improve the paper. Make it clear that these points are here to help, and not necessarily part of your decision assessment.

(i). The author should change their claim of the improvement over (Miryoosefi et al. , 2019), such improvement is not achieved in this paper. 

(ii). In terms of notation, the definition of the “dist” function should be changed. Traditionally, “dist” only denotes the distance instead of the squared distance. The authors should use “dist^2(c,x)” or simply change to some other notation, otherwise, it will cause confusion. (This notation confusion is also possibly the reason why the authors wrongly claim the improvement over (Miryoosefi et al. , 2019))

(iii). It might worth more discussion about what Algorithm 1 is doing. For example, for line 3, briefly comment that $x-\omega$ is the gradient of the objective function will make the understanding of the algorithm significantly simpler. Similarly, the authors can make more explanation about the line 6-13 of Algorithm 1, which might cause confusion without explanation.

5. Ask questions you would like answered by the authors that help you clarify your understanding of the paper and provides the additional evidence you need to make be confident in your assessment. 

Consider finding a policy \pi whose measurement vector c(\pi)\in\Omega. For simplicity suppose there are only 2 policies. In this paper, the proposed solution is to find p s.t. 
p*c(\pi) + (1-p)*c(\pi’)\in\Omega. However, this corresponds to the situation where before doing anything, first toss a coin to decide whether \pi or \pi’ is used. Then use that policy for all future plays. However, this situation is weird in the sense that none of the \pi or \pi’ is feasible, and the variance can be very large. My question is, is it possible to find the convex combination s.t. c(p*\pi + (1-p)*\pi’)\in\Omega? (It is obvious that c(p*\pi + (1-p)*\pi’) \neq p*c(\pi) + (1-p)*c(\pi’)). I think such a policy will be stabler. 



review_title: Marginally above the acceptance threshold

Meta-review: The paper builds on the prior work by Miryoosefi et al. (2019) that finds a feasible mixed policy under convex constraints through distance minimization over a simplex set. Instead of the primal-dual approach used in Miryoosefi et al. (2019), this paper proposes to apply Frank-Wolfe type algorithm (particularly, the minimum norm point algorithm) to promote sparsity of the mixed policy, while achieving the same complexity. 

Despite the improvement on sparsity, the AC and some reviewers share two main concerns: (1) incremental novelty of the algorithm/theory, which basically follows from existing optimization work, (2) lack of (theoretical and numerical) justification of the significance of sparsity (especially given that the main computation costs come from projection and RL oracle). 

Unfortunately, the paper lands just below borderline and cannot be accepted this time. 

Decision: Reject