Venue: NeurIPS 2022 Conference

Reviews:

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 studies the offline reinforcement learning in the framework of constrained Markov decision processes. The authors propose an offline primal-dual algorithm, prove near-optimal sample complexity under different assumptions on datasets, and propose an adaptive algorithm without prior knowledge on concentrability coefficient. 
strengths_and_weaknesses: ## Originality

- The proposed offline primal-dual algorithm is new in offline constrained reinforcement learning. 

- The sample complexity matches a lower bound except for the dependence on the discount factor. 

## Quality & Clarity

- Main results of the paper has been delivered well, except for a few concepts.

- All claims are supported by proofs, although I didn't check correctness. 

## Significance

- The proposed offline primal-dual algorithm takes either independent batch dataset or single trajectory sequence, which are two important settings in offline reinforcement learning.

- The optimality of sample complexity is studied by establishing lower bound. 

- An adaptive implementation of proposed algorithm is useful for practice due to the absence of prior knowledge on concentrability coefficient.
questions: - Notation $I$ is abused in Section 2.1.

- line 103: what is the sparse nature of optimal policy? LP only works for occupancy measures, not policy. 

- Can you explain how to determine $C^*$ in Assumption 2.3?

- Does saddle points always exist for (6) or (7)? How does constraints (8) work for (7)?  This constraint set looks a strong restriction.

- How to compute $\mu(s,a)/\hat \mu(s,a)$ for degenerate $\hat \mu(s,a)$ when finite concentrability is absent? An issue occurs in (9) also.

- How to compute $KL(\lambda \Vert \lambda^t)$ on $\Lambda$?


limitations: No, for example how to mitigate potential bias in offline data is not discussed.
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 manuscript investigates offline Constrained Markov Decision Process (CMDP), where on top of optimizing the cumulative reward r one must maintain (in a hard way) a cumulative constraint u to be non-negative. The offline setting uses only the offline data without a generative model. This manuscript proposes Deviation-controlled Primal-Dual Learning (DPDL), an algorithm that uses the saddle point formulation of MDP and a mirror descent-like update. When the concentrability coefficient of a CMDP is finite, assuming the Slater's condition, the algorithm guarantees the convergence and a proved sample complexity. An information-theoretic lower bound validates the optimality of this sample complexity up to a 1/(1-gamma) factor.
strengths_and_weaknesses: This paper improves previous works on CMDP by removing the generative model. Without a generative model, it is necessary to have the Slater's condition to satisfy the constraint. With the Slater's condition, the authors show a close-to-matching pair of upper and lower bounds of sample complexity (need concentrability assumption). The argument seems natural and the improvement is clear.

I would question the relevance of the manuscript as the assumptions needed to conclude the sample complexity are heavy. Despite one of them is necessary (Slater), it is not clear if this particular setting is worth investigating.

I also suggest the authors to highlight the technical contributions, if any.
questions: N/A
limitations: N/A
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 proposes a model-free off-policy reinforcement learning algorithm DPDL that aims to solve the constrained MDP (CMDP) problems given an offline static dataset, and also provides an information theoretic lower bound on the sample complexity in the offline CMDP setting. DPDL adopts the primal-dual approach and addresses the distribution shift challenge in the offline setting via an adaptive deviation control mechanism. 

strengths_and_weaknesses: An innovative aspect of this work is that it considers a combination of the offline reinforcement learning (RL) and safe RL formulated as a constrained MDP. Currently, there are limited existing work on this specific combination, while recent exploration on offline RL and safe RL separately are extensive. The paper could be further improved if the authors would elaborate on the factors that motivate the authors to combine the two settings from both theoretic and practical perspectives. 

In addition, while this paper analyzed the algorithm theoretically, it remains unclear whether it would be effective in solving real-world problems due to a number of issues. Towards this end, experiment results should be conducted to address this issue.  




questions: A large part of the analysis in this current version replies on an assumption that we know a reference distribution, while we actually don't have an access to such a distribution. Although the paper proposed to use an estimated distribution instead, this current does not provide a principled way to construct such a distribution estimation. 


limitations: As mentioned in the strengths and weaknesses section, some of the concerns include a lack of experiments that can demonstrate the practice effectiveness of the proposed DPDL algorithm as well as principled ways to derive a practical algorithms based on the theoretical analysis.
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 the offline CMDP through the linear programming (LP) formulation and the primal-dual based method. An upper bound is proved under the notion of the concentrability coefficient in offline RL literature. A lower bound is established to demonstrate the near-optimality of the proposed upper bound. Finally, an adaptive algorithm is proposed to address the situation when the optimal concentrability coefficient is unknown.
strengths_and_weaknesses: Strengths:

(1) The paper is well-written and the presentation is very clear.

(2) Offline/off-policy CMDP is an important problem and there are not as many offline/off-policy CMDP in the literature as for online CMDP.

(3) The theoretical results are solid. Both the upper bound and lower bound are provided, and the dependencies on the key parameters are very clear. In addition, an adaptive algorithm is proposed to address the situation when the optimal concentrability coefficient is unknown, without the optimality sacrifice.

Weaknesses:

(1) The assumption of having an offline dataset with a finite concentrability coefficient seems to be too strong in practice. Most of time, we would only have an offline dataset that does not well covers all state-action pairs.

(2) The LP-based approach is very restrictive and not scalable. This further restricts the application of this work to the practical implementations. 

(3) There are some other published works in offline CMDP that the author may need to compare. For example:

Wu, Runzhe, et al. "Offline Constrained Multi-Objective Reinforcement Learning via Pessimistic Dual Value Iteration." Advances in Neural Information Processing Systems 34 (2021): 25439-25451.

Xu, Haoran, Xianyuan Zhan, and Xiangyu Zhu. "Constraints penalized q-learning for safe offline reinforcement learning." Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 36. No. 8. 2022.


questions: (1) Could the authors discuss the potential of relaxing the assumption of a finite concentrability coefficient?

(2) Could authors discuss the technical challenges and contributions of this paper compared with some key references like [14, 30] and [23]?

limitations: N/A
review_title: null

Meta-review: metareview: This paper considers offline reinforcement learning in the constrained MDP framework. It proposes an algorithm that provably obtains a near-optimal policy (under a single-policy concentrability assumption) and proves an upper bound (and a corresponding lower-bound) on the resulting sample complexity. 

The reviewers found the paper well-motivated and technically sound, and unanimously recommend acceptance. Please incorporate the reviewers' feedback in the final version of the paper. In order to strengthen the final paper, it would be helpful to:
- Incorporate toy experiments and empirically validate some of the paper's claims
- Include a discussion about the tightness of the upper/lower bound. 


confidence: Certain
Decision: Accept