Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This work provides finite-sample analysis for constrained MDPs in a generative model/simulator setting. For the first relaxed feasibility setting, the proposed method improves the prior art sample complexity by $S$ and matches the unconstrained minimax lower bound. For a strict feasibility setting, this work provides the first lower bound and also proposed a method that can match the minimax lower bound.
Especially, this work shows that with strict feasibility requirements, CMDPs have intrinsic more challenges than unconstrained MDPs.
strengths_and_weaknesses: Advantages:
1. For the strict feasibility of CMDP settings, this work is the first one that provides a tight lower bound and also proposes a method with a minimax sample complexity bound, characterizing the difficulty of solving CMDPs theoretically.
2. Furthermore, in the relaxed feasibility setting, it also improves the prior arts and achieves the minimax lower bound (unconstrained MDPs') sample complexity.

Disadvantages:
1. The presentation of the work can be polished more by showing more intuition and key technical tools and moving the proofing details to the appendix.


questions: 1. Do the result need the value accuracy gap $\varepsilon$ to be the same as the small constraint violation in Line 122? From my understanding after reading the proof sketch, they can be different. But the equation (2) may lead to some confusion as they are related and must be the same. If they can be different, using different variable notation may be better.
limitations: The author already mentioned the possible extension of this work in the discussion.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper studies the sample complexity for learning constrained MDPs with a generative model. The authors provide minimax optimal upper and lower bounds for two settings: relaxed feasibility, where one seeks the best policy matching the constraints up to a slack of epsilon, and strict feasibility, where instead one focuses on strictly matching the constraints. Interestingly, the authors show that the first setting is as easy as solving unconstrained MDPs (ie the same worst-case sample complexity is attainable and optimal), while the second setting is strictly harder.
strengths_and_weaknesses: Strengths:
- The paper studies a relevant problem (that of constrained MDPs)
- The results are significant as they close the gap between upper and lower bounds for this setting
- The algorithm and its analysis are, to my knowledge, novel
- The fact that CMDPs are as easy as standard MDPs in the relaxed feasibility regime is also an interesting and relevant result
- The paper is very well written. The proof sketches are very clear

Weaknesses:
- The paper assumes access to a generative model.
- The algorithm and its analysis need to handle the two settings (relaxed and strict feasibility) differently (see below).
- No numerical result is presented.
questions: Overall I think the paper provides a significant contribution to our understanding of learning constrained MDPs (though in a limited setting with a generative model). I thus vote for acceptance. Here are a few comments/questions.

1. One thing I find slightly weird is the definition of relaxed feasibility, where the same value \epsilon is used for both the objective  function and the constraint. Since r and c are different quantities with different meanings (and possibly on different scales), I was wondering whether it wouldn't be more reasonable to have two distinct parameters, say \epsilon_r and \epsilon_c, which can be used to properly tune the desired degree of sub-optimality and constraint violations.

2. Related to the previous point, if we imagine to have an algorithm and analysis for this case with two different values of \epsilon, it might be even possible to have a unified treatment for the relaxed and strict feasibility settings (right now the algorithm must be instantiated with different parameters -- eg b' -- for the two settings). In particular, the latter would be just a special case obtained by setting \epsilon_c = 0. A unified analysis might also be possible. Would there be any fundamental complication in handling two different values of epsilon for r and c?

3. Here a single constraint c is considered. What if we have multiple constraints to satisfy? How would the sample complexity scale with the number of constraints? Polynomially? Logarithmically? 

4. While I find the primal-dual approach interesting, it was not completely clear to me why we cannot simply solve the empirical MDP with, say, linear programming (or any black-box approach). Could the authors elaborate on that?

5. Footnote 1 mentions that the [0,1] bounded rewards assumption is only for simplicity and one can handle other ranges. Is it also easy to handle unbounded rewards (eg sub-Gaussian)?

6. The algorithm is not really adaptive as it requires a fixed number of samples N (to collect from each s,a) as input. Would it be possible to have a variant of the algorithm with an adaptive sampling and stopping rule?

7. I guess Theorem 8 should read as "for any sound algorithm and any values of the parameters (eg S, A, etc), there exists an MDP with S states, A actions, etc such that the algorithm must pay at least the stated sample complexity". While I see how the instance in Figure 1 can be made arbitrarily large in terms of number of actions A, it is not clear there how to do the same with the number of states S.
limitations: Limitations have been properly discussed. I would stress more in the paper that considering the tabular (finite S,A) setting with a generative model limits the practical impact.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: The paper considers Constrained MDPs and finds the sample complexity bounds. The paper results seem weaker than that in [6]. The paper mentions that [6] has a Lipshitz constant L. However, this constant is when the objective function and constraint function are convex, while is 1 for the setup of this paper. As such, [6] does not have the parameter L and thus the authors misrepresent the prior work. Given that the results in this work are not better than the state of the art, the reviewer does not believe that the paper can be accepted in its current form. 
strengths_and_weaknesses: The paper results seem weaker than that in [6]. The paper mentions that [6] has a Lipshitz constant L. However, this constant is when the objective function and constraint function are convex, while is 1 for the setup of this paper. As such, [6] does not have the parameter L and thus the authors misrepresent the prior work. Given that the results in this work are not better than the state of the art, the reviewer does not believe that the paper can be accepted in its current form. 

Based on the discussions with the authors, I am increasing the score. Some evaluations would be good in the paper. Also, more discussions on novelty would help. Use of zero constraint part achievability beyond that for relaxed setup is standard. The key contributions are: (i) lower bound on strict feasibility, (ii) achievability for relaxed setup. 
questions: Please see above
limitations: Please see above
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper studies sample complexity bounds for constraint MDPs with generative model under relaxed feasibility setting (where the algorithm needs to find a policy that achieves \epsilon-optimal reward and \epsilon constraint violation) and strict feasibility setting (where the algorithm needs to find a policy that achieves \epsilon-optimal reward and 0 constraint violation). For the relaxed feasibility setting, this paper achieves $O(SA(1-\gamma)^{-3}\epsilon^{-2})$ sample complexity, which is minimax optimal and matches the lower bound for unconstraint case. For strict feasibility setting, this paper achieves $O(SA(1-\gamma)^{-5}\epsilon^{-2}\zeta^{-2})$ sample complexity and proves a corresponding lower bound.

strengths_and_weaknesses: Originality. Although similar primal-dual methods are also considered in previous works, this paper provides novel analysis and therefore proves stronger results. The lower bound for the strict feasibility case is interesting and novel.

The following two related works are missing. In particular, Section 6 of [1] proves $O(\sqrt{SAT})$ regret for constrained MDPs without generative models, and [2] proves sample complexity bounds.
 
[1] Yu, Tiancheng, et al. Provably efficient algorithms for multi-objective competitive rl

[2] Miryoosefi, Sobhan, and Chi Jin. A simple reward-free approach to constrained reinforcement learning.


Quality. This paper is technically sound. I didn’t read through the appendix but the proofs that I read are morally correct.

Clarity. The exposition of the results could be improved:
-	The proof of Theorem 8 looks like a zero-knowledge proof and is hard to follow. The choice of constants are not explicitly stated, and some of the core ideas are hidden in the proof details. The intuition of why strict feasibility setting is harder than relaxed feasibility setting is unclear to me, as well as the idea of the hard instances.
-	While this paper proves a separation between relaxed and strict feasibility cases, the proof sketch for Theorem 2 & 3 looks very similar except the choice of parameters (e.g., b’, \epsilon_1). However, the choice of parameters is not justified in the first 9 pages. In particular, it’s unclear why the parameters have to be different without reading the full proof.

Significance. This paper proves minimax optimal sample complexity for constrained MDPs with generative model, and improves upon previous results. This paper partially answers the question that whether constrained MDPs are harder than unconstrained MDPs --- somewhat surprisingly, constrained MDPs with generatively model are not harder with relaxed feasibility.
For the strict feasibility case, the error decomposition (lemma 12) is novel and could be a useful tool to analyze constrained MDPs in different settings. The matching lower bound in this case demonstrates that the strict feasibility setting is strictly harder than the relaxed feasibility setting, which is an interesting result by itself.

questions: - The dependency on Slater constant ($\zeta=\max_\pi V^\pi_c(\rho)-b$) is interesting. Since the Slater constant doesn’t depend on the reward function, for any MDP one can always add a redundant state with r=0 and c=1 (and an action from the initial state that deterministically leads to this redundant state) so that the Slater constant becomes bigger. Consequently, the MDP becomes easier. If I understand correctly, with this redundant state the algorithm can somewhat “amortize” its reward and constraint: if the algorithm visits this redundant state with positive probability, its constraint will be increased but reward will be decreased. While the strict feasibility setting appears to be important in practice (e.g., we don’t want to break a robot arm), the behavior of the algorithm is somewhat undesired (it may output a mixture of an unsafe policy and extra-safe policy). Is there a way to address this mismatch?

- Do the bounds in [1] or [2] translated to the relaxed or strict feasibility setting? How does the bounds compare with each other?

limitations: The authors adequately addressed the limitations and potential negative societal impact.
review_title: null

Meta-review: metareview: The paper studies the sample complexity of constrained MDPs and provides (nearly) matching lower and upper bounds when the constraint needs to be satisfied exactly and when slackness is allowed. Reviewer KfEz initially had concerns about comparison with prior works, which were resolved during discussion period. Other than that, multiple reviewers point out that the main text writing is not particularly informative; much space in the main text was devoted to inconsequential details while key intuitions are missing. In addition, as Reviewer 3jqt points out and the AC agrees, the generative model + tabular setting is quite restrictive and limits the significance of the work. All that said, all reviewers also agree that this is a technically solid paper with multiple interesting insights (e.g., the separation between the strict and relaxed feasibility settings), and the final reviewer scores are unanimously on the positive side.
confidence: Certain
Decision: Accept