Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: The paper studies the problem of safety in learning, within the framework of tabular episodic Constrained MDPs (unknown transition, rewards and costs). The authors propose a method based on the principle of optimistic pessimism in face of uncertainty that achieves a regret of $\mathcal{O}(\sqrt{K})$ for the rewards ($K$ being the number of episodes) that is comparable to the existing methods. The main advantage of the proposed approach is that it achieves a smaller constraint violation: particularly zero constraint violation when an initial safe policy is given, and bounded constraint violation when no safe policy is known (but it is known that one such policy exists). The known policy case is based on the LP formulation of solving the pessimistic CMDP, and the unknown policy case uses a  primal-dual approach.
main_review: ### Originality:

The proposed methods are inspired by safe exploration in constrained bandits but the extension and application to the constrained RL problem are novel and valuable. The authors do a good job of citing the related literature and differentiating their approach from the others. 

### Quality: 

The submission is technically sound with all the claims being supported sufficiently. All the assumptions and limitations are stated clearly. 

### Clarity:

The paper is clear and easy to follow. Although I believe some aspects of the paper can be improved wrt clarity, particularly:
-  All the analysis depends on how the high probability good event is defined (Appendix A). I think the authors can do a better job in explaining the details in this section. For instance, when the author’s define $\mathcal{E}^{gen}$ the Hoeffding’s, Berstein and Union bound are all applied in a single step and it is not obvious how the $\frac{1}{4(1+|S|)}$ term shows up in the denominator for $\delta’$. I think it will be useful for the readers if the intermediate steps are also provided.
- The results depend heavily on Lemma D.5, the proof for which is referred to another related work. However, the referenced work uses different notation and setting that makes it difficult to draw the connections. I think it will be useful if the proofs for Lemma D.5 (and even D.4) can be presented in the work itself for the sake of completeness.
- Another point that can be highlighted a bit further is how the threshold for the first condition in Eq 9 ($\frac{\tau+c^0}{2}$) is derived. Some discussion on that will add to the clarity of the approach. 



### Significance:

The paper is technically sound and novel with strong results which I believe will be useful for developing further safe/bounded-constraint algorithms in this setting. 

limitations_and_societal_impact: yes
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper presents two novel reinforcement learning algorithms for CMDPS, one which has no constraint violations with high probability, but requires a known safe policy, and another which bounds the probability of constraint regret, but only requires the existence of a safe policy. The first algorithm picks pessimistically safe policies if they obtain a high enough value, but chooses a best reward policy otherwise. The second algorithm iteratively chooses the highest value policy subject to a dynamically tightening constraint. Both algorithms have a higher regret than previous approaches, but are provably safe  in the respective metrics
main_review: Strengths:

Broadly speaking the paper is well written.

The knowledge of safe policies are reasonable assumptions, and the two distinct cases seem natural. The relevance and novelty is clear.

The description of both procedures are clear and reproducible.

The theoretical aspects of the paper are thorough. 


Weaknesses:
The paper consistently refers to notation before it is introduced, making it difficult to read. While it is hard to summarise the work in the introduction without a formal problem definition, some of the more important terms, like regret, should be explained informally.

The problem formulation needs to more clearly state what parts of the CMDP are known vs unknown to the agent at start.

The two approaches lack intuition. With the appendix, it's clear why certain bounds were chosen, but motivation that ties to the problem would help the reader's understanding.

Finally, whilst I appreciate the focus of this paper is theory, it is presenting two algorithms, so I think an empirical evaluation would greatly strengthen the contribution. This could be done by moving some of the results in Section 5 to the appendix.


Specific comments/questions

* Is assumption 2.1 common? Further intuition on its need, and how strong it is, should be given

* In line 129, I don't follow the use of sup. Shouldn't it be lim k->infty?

* point (iii) in line 132 feels a bit irrelevant in the context of this paper

===UPDATE===
After reading the other reviews and the authors' thorough responses, I think the paper should probably be accepted, assuming some of the insights and clarifications provided in the responses are added to the paper.
limitations_and_societal_impact: No discussion on societal impact. Some limitations are mentioned.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper studies safety in reinforcement learning. It guarantees a zero constraint violation happens with high probability when strictly safe policy is known. The algorithm employs optimism in the face of uncertainty and achieves a regret of O(\sqrt{K}). For the case with no known strictly safe policy, it is proven that  the constraint violation is bounded.
main_review: The paper is well-written and the problem formulation and the contributions are clearly stated. However, numerical experiments that corroborate the theoretical guarantees of the paper are missing in the current version and I highly recommend to add some in the revision.

Questions:

1. My first question is whether the authors can extend their analysis to the case with focus on deterministic policy? 
2. My second question is whether either of the regret bounds and the constraint violation bound are tight in terms of c^0? 
3. Could the authors comment  on an example of safety-critical system where it is reasonable to assume the knowledge of a safe policy?


limitations_and_societal_impact: I believe this work does not have any potential negative societal impact.
review_title: null

Meta-review: This paper studies the problem of learning episodic CMDPs, which provides improved theoretical results comparing to previous works. This work is technically sound and novel with strong results. All the reviewers have reached a consensus on the acceptance of this work. We suggest that the authors further polish their paper to prepare a camera-ready version based on the reviewers’ comments.
Decision: Accept (Poster)