Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: This paper generalizes the traditional constrained Markov decision process (CMDP) to a CMDP that has infinitely many constraints, which is called semi-infinitely CMDP (SICMDP). The main challenge of solving the optimal policy for such a SICMDP is to deal with a continuum of constraints, and existing constrained reinforcement learning (CRL) methods do not work anymore. In this paper, the authors propose the first RL algorithm for the tabular SICMDP based on linear semi-infinitely programming (LSIP). Specifically, they first construct a set of dynamics under the offline setting or the generative model setting, and formulate an optimistic planning problem. Then, they augment the state-action occupancy measure to the state-action-state occupancy measure, by which they transform the optimistic planning problem into LSIP. Finally, such LSIP is solved via an existing method. Furthermore, the authors prove the sample complexity and iteration complexity of their algorithm under some assumptions. In the experiments, they show the effectiveness of their method and the tightness of their theoretical bounds.
strengths_and_weaknesses: Strengths
1. This paper generalizes CMDP to SICMDP, which is a novel model that has many applications. 
2. This paper introduces tools from LSIP to RL and proposes the first RL algorithm for solving the optimal policy of SICMDP.
3. This paper provides the sample complexity and iteration complexity of their algorithm. 

Weaknesses
1. About solution: 
- Although this paper is the first one to focus on SICMDP, the proposed solution has limited novelty. Specifically, this paper constructs a confidence interval for the dynamic and formulates an optimistic planning problem, which is widely used in model-based papers, e.g., [14] and [21]. 
- This paper transforms the optimistic planning problem into LSIP form. Such transform is similar to [21]. At last, the LSIP is solved by an existing solver. 

2. About theory: 
- The PAC bound in this paper is flawed. The authors prove the sample complexity of their algorithm under the assumption that Problem (5) can be solved exactly, which is unreasonable. The authors should prove that, in order to get a $\epsilon$-optimal policy with probability $1-\delta$, how many samples and number of iterations are needed. 
- In Theorem 5.7 and 5.11, the authors say “a modification of SI-CRL is …”. But they do not describe what the modification is.

3. About experiments:
- In Discharge of Sewage domain, the authors compare the CMDP baseline obtained by discretizing the original problem. However, they only discretize the infinite set Y into 9 points, which may be unfavorable for such a CMDP baseline. They should add experiments about discretizing Y into more points.
- In Figure 5, the authors show the results of constraint violation. But they should also show the performance of the objective, i.e., the cumulative rewards, as in regular CRL papers.

4. About related work:
- The authors should explain the difference between this work and [21].
- The literature review on CRL works is far from thorough. The authors should add more related works about CRL.

5. About Writing:
- In the penultimate paragraph of Introduction, some notations (e.g., d, diam(Y)) are used 	before introducing them, which is confusing for readers.
questions: 1. In this paper, the reward and cost functions are known a priori. Do the method and theory still work when the reward and cost functions are unknown and learned from samples as the dynamic?

2. The method in this paper only works for tabular SICMDPs with small state and action spaces. RL algorithms for SICMDPs beyond the tabular case would be significant.

3. What is the technical difference between this work and [21], except that this work is a LSIP?

4. The authors should clarify their contributions more clearly.

5. It would be interesting to design algorithms for the episodic setting in addition to the generative model setting and offline setting, since the last two setting omit exploration and are somewhat easier.

limitations: 1. The PAC bound in this paper is flawed, and should consider both the statistical and optimization errors.

2. The technical difference between this work and [21] should be explained. And the authors should clarify their contributions more clearly.

3. The extensions of this paper to the episodic setting or large MDPs would be appreciated.
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: The paper "Semi-Infinitely Constrained Markov Decision Processes" proposes a generalization of CMDPs from finite constraints to a continuum of constraints. The authors devise a generative model based reinforcement learning algorithm for Semi-Infinitely Constrained Markov Decision Processes", and characterized the sample complexity. Numerical experiments are provided to validate the performance of algorithm.
strengths_and_weaknesses: The paper is reasonably well written, presentation easy to follow. The use cases in Section $3$ illustrate the applicability of this approach.

The theoretical results (sample complexity bounds) are strong. But the novelty in the analysis seems to be limited, since multiple works have addressed similar problems (classical CMDPs) in the past, and this approach is very similar to the earlier works. [HasanzadeZonuzy, 2021]. 

The algorithm is a generative model based, it only works with a data provided apriori.

Numerical experiments indicate the advantage of the algorithm w.r.t the baseline, but this section is weak.
questions: Remark 5.10: The sample complexity bounds do not seem to depend on $Y$. Will this result translate to classical CMDP case?

Because, existing bounds in the classical CMDP seem to suggest the sample complexity increases with the number of constraints. 


The details on the experiments are missing. How is the LISP being solved? 
limitations: Yes, this algorithm works for only tabular case, and only when a offline data set is provided apriori.
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: This paper proposes a generalization for the Constrained MDPs, coined as semi-infinitely constrained MDPs. This framework extends the general CMDP making it able to handle a continuum of constraints. They transform the semi-infinite CMDP into a linear semi-infinite programming problem and then apply tools from semi-infinite programming literature to solve it. They present solid theoretical derivation and supports the claims with thorough empirical analysis.
strengths_and_weaknesses: The paper is well organized and well written proposing a novel and important direction of incorporating a continuum of constraints into the CMDP framework. The theories and the algorithm are presented clearly with convincing empirical results.

Examples 3.1 and 3.2 presented in the paper are sound and makes the motivation of the proposed SICMDP framework pretty clear.

The SI-CRL algorithm presented in section 4 is simple, well organized and easy to follow.

The theoretical analysis presented in section 5 is rigorous. The authors provide both the computational complexity and sample complexity for the proposed algorithm.

Section 6 provides a detailed experimental analysis of SI-CRL algorithm on one toy  and one more realistic problem domain. The results clearly show that SI-CRL outperforms the baseline method both in terms of reducing constraint violations and minimizing the errors.
questions: The paper is carefully written answering most questions, thanks to the authors.

Line 128 refers to "the optimistic approach". But this was never introduced in the paper before, right? Please note what it is in the paper before referring.

Algorithm 1 incrementally adds new constraints from the set of constraints. Is this set of constraints discrete, not continuous? If yes, then is the claim of incorporating continuum of constraints correct? Also how it differs from the brute-force approach of discretizing a continuous set of constraints and the using the general CMDP framework? On the other hand, if the set of constraints is continuous, is it possible to clarify the process a bit on how the incremental constraint incorporation works in algorithm 1?
limitations: Yes
review_title: null

Meta-review: metareview: This paper develops an RL method for semi-infinitely constrained MDPs.  Apparently they are the first to do this, though the algorithmic contributions are not particularly innovative and the theoretical results are not particularly surprising.  I see this as a fine, albeit technical, contribution to the literature.  I am on the fence with regards to acceptance.
confidence: Less certain
Decision: Accept