Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: This paper considers the problem of offline RL in a constrained multi-objective MDP (CMOMDP) environment, where the goal is to compute a policy that achieves the best performance with respect to the given preference function while satisfying the given cost constraints, only using a fixed offline dataset. Pessimism Dual Iteration (PEDI) is proposed, which is the first provably efficient offline RL algorithm for CMOMDP that exploits dual gradient ascent and does not make any assumption on dataset coverage. First, the constrained optimization problem is converted into its dual problem by the convex conjugate. Then, for fixed dual variables, the overall optimization is reduced to an unconstrained planning problem, where pessimistic planning that penalizes uncertainty for each state-action is performed. The dual variables are updated via projected subgradients that are computed by the value of primal variable obtained during planning. Finally, the output policy is a uniform mixture of policies that are obtained during overall iterations. An instantiation of PEDI for linear kernel CMOMDP is introduced. Theoretical results are presented, which bound the suboptimality and constraint violation, and it is minimax optimal for linear kernel CMOMDPs.


main_review: Recently, offline RL has been getting attention thanks to its potential applicability in real-world situations, but most of them focus on a single-objective RL problem. Still, many practical problems involve multi-objectiveness and constraints, where CMOMDP formulation, a generalization of CMDP,  can be more natural. This work provides the first provably efficient offline RL algorithm for constrained multi-objective problems, which is a valuable contribution. I didn't go through the proof in detail, but the statements look overall sounded.
- Can the analysis and the algorithm be extended to discounted infinite horizon setting? In an infinite-horizon discounted CMDP, there always exists an optimal policy, which is Markov and stationary, but generally stochastic. Can PEDI be also adapted to yield a Markov, stationary, stochastic policy?
- In constrained (MO)MDPs, the constraints are given as hard constraints, thus reducing violations should be the primary objective than reducing suboptimality. Would pessimism alone be sufficient for reducing the chance of cost violation when deployed to the true environment? Are there any further considerations for the robustness of constraint satisfaction?

limitations_and_societal_impact: It seems that the limitations of the work are not explicitly discussed, but I didn't find severe flaws in this work.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper proposes and analyzes the setting of off-policy constrained multi-objective Markov decision process.  This is a generalized of the constrained MDP setting.  An algorithm to learn the solution is proposed based on a minimax formulation with a pessimistic penalty.  Theoretical analysis defines upper bounds on the suboptimality of the objective and constraint violation. Efficient learning is also demonstrated, under the assumption that the off-policy data sufficiently covers the trajectories induced by the optimal policy.
main_review: The paper defines the setting of off-policy constrained multi-objective MDPs.  I can imagine what might be use cases for this, but it would be nice to present a brief illustrative case, to avoid confusion about what information belongs in the constraint vs in the objective (this is pretty simple when dealing with standard CMDPs but may be less clear with CMOMDP). This would help motivate the work.

The related work section is reasonably well done, but would benefit form including earlier references on offline RL. The novice reader would be tempted to think this originated in 2019. This survey has many earlier references: https://arxiv.org/pdf/2005.01643.pdf

The technical preliminaries are overall quite clearly and thoroughly described.  A strength of the paper is the interesting derivation of the Pessimistic Dual Iteration approach, which (as far as I know) is quite different from the standard CMDP approach (which are more based on adding Lipschitz constraints).   The derivation is quite dense, and the reader needs to be very attentive to follow the notation and construction of the algorithms.  The strong model-based approach (l.222-223) may be a limitation of the method; I see the value for the theoretical analysis, but it would be interesting to see how that plays out in practice. 

The theoretical proofs are all pushed to the appendix, and I did not verify them.  The paper would be improved by the additional of remarks to give more intuition on key steps of the proof.  It’s likely the paper would be better suited by a journal format, where proofs can be incorporated in the main body, and reviewers have several more weeks to evaluate the work.

Another limitation of the paper is the complete lack of any empirical results, even a very simple demonstration, to verify the most basic behavior of the algorithm.  This was somewhat disappointing. There is value to just having an implementation as a proof of concept, even if that is not the main claim of the work.

Minor comments:
-	The Slater’s conditions is referred to in several places but not defined.
-	L.84 says “without any assumptions on the coverage of the dataset”, but l.81 (and theoretical analysis later) say  that the analysis assumes that “the trajectories are sufficiently covered”.  Be careful when stating assumptions to avoid confusion about the claims.

limitations_and_societal_impact: Not discussed. I don’t anticipate any negative impact.  The work may be able to introduce safety constraints into multi-objective MDPs, which would be valuable.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This work considers constrained multi-objective Markov decision processes (CMOMDPs). The authors propose an algorithm to obtain the optimal policy in the offline setting. Optimality and constraint violation bounds are provided.
main_review: I have some questions:

- The related work section seems to be missing a large number of recent works in constrained RL, specially those using primal-dual approaches.

- A better motivation of the differences between the authors approach and previous work. It seems like the approach that the authors are taking to CMOMDPs could also be applied to CMDPS. A discussion on this regard would be helpful to the reader

- In Section 3.1, the difference between using a standard primal-dual formulation and the formulation (4) should be better motivated.

- The lack of numerical results seems like a major omission. It is difficult to evaluate the proposed algorithm without experiments nor comparisons with previous art.
limitations_and_societal_impact: None
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper considers policy optimization in a difficult setting involving multiple challenges: (1) multi-objective -- rather than simply optimizing a scalar reward, the policy must optimize a convex function g on vectors of cumulative costs; (2) constrained -- while optimizing g the policy must also satisfy a constraint on the cumulative costs; (3) offline -- the policy learning algorithm cannot actively query the environment, and only has offline access to experience.

For this setting, the paper presents an algorithm with corresponding theoretical analysis. The algorithm follows a primal-dual optimization to handle (1) and (2) above while proposing pessimistic value iteration to handle (3) above. Theoretical analysis provides guarantees on the convergence of the algorithm to an optimal policy under idealized conditions in both general MDPs and kernelized MDPs.
main_review: The paper is written well, especially for a theoretical paper. I appreciate the time the authors took to organize and polish the writing to this point. Content-wise, the theoretical analysis appears detailed, clean, and comprehensive. 

The main issue with the current paper is significance, which I elaborate on below, considering three dimensions:

(A) Algorithmically: Algorithmically, the proposed techniques are only marginally novel. Certainly, pessimistic approaches to offline RL are ubiquitous, as detailed in the paper's related work, and these existing approaches are arguably identical to the paper's proposed approach. Similarly, primal-dual approaches have been proposed for constrained RL, although I concede that, as the paper notes, these previous works typically consider linear constraints/cost functions.

(B) Theoretically: The contributions theoretically appear to be (1) formalization of the CMOMDP problem and (2) guarantees on the proposed algorithm. These contributions largely appear to be straightforward extensions of previous work (e.g., the CMOMDP is essentially a combination of C(onstrained)MDPs and M(ulti)O(bjective)MDPs). It is unclear if there are any insights that come out from these generalizations of existing guarantees, beyond the ideas behind Assumption 1 (generalization of Slater's conditions), which I concede is a significant & novel contribution.

(C) Experimentally: The paper does not include any empirical analysis of the algorithm. Personally, as someone who has practical experience with multi-objective, constrained, and offline RL algorithms, I know how difficult it is to get such algorithms to work empirically. An algorithm as complex as the one proposed in the paper is further unlikely to work well in practice, so without empirical evaluations, the reader is left to assume that the algorithm is exclusively theoretical, with no practical ramifications.
limitations_and_societal_impact: n/a
review_title: null

Meta-review: 
In this paper, the authors consider the offline learning for constrained multi-objective MDP (CMOMDP). Specifically, the authors proposed an algorithm which exploits the primal dual structure with pessimistic planning. The algorithm is extended for linear kernel CMOMDP. Moreover, the authors also provided rigorous suboptimality and constraint violation guarantees. 

Although as most of the reviewers pointed out, the original version of the paper is lacking some related work discussion about offline RL and constrained RL, and empirical justification of the algorithm, the authors provided these parts during the rebuttal period, therefore,  making the paper more convincing. I recommend acceptance for this paper. Please take the reviewers's other suggestions, especially adding the intuition/sketch of the proof into main text, to improve the paper. 
Decision: Accept (Poster)