Offline Constrained Multi-Objective Reinforcement Learning via Pessimistic Dual Value Iteration
Authors: Runzhe Wu
Yufeng Zhang
Zhuoran Yang
Zhaoran Wang
Venue: NeurIPS 2021 Poster (2021)
Keywords: reinforcement learning
offline learning
multiple objectives

Abstract: In constrained multi-objective RL, the goal is to learn a policy that achieves the best performance specified by a multi-objective preference function under a constraint. We focus on the offline setting where the RL agent aims to learn the optimal policy from a given dataset. This scenario is common in real-world applications where interactions with the environment are expensive and the constraint violation is dangerous. For such a setting, we transform the original constrained problem into a  primal-dual formulation, which is solved via dual gradient ascent. Moreover, we propose to combine such an approach with pessimism to overcome the uncertainty in offline data, which leads to our Pessimistic Dual Iteration (PEDI). We establish upper bounds on both the suboptimality and constraint violation for the policy learned by PEDI based on an arbitrary dataset, which proves that PEDI is provably sample efficient. We also specialize PEDI to the setting with linear function approximation. To the best of our knowledge, we propose the first provably efficient constrained multi-objective RL algorithm with offline data without any assumption on the coverage of the dataset.

Offline Constrained Multi-Objective Reinforcement Learning via Pessimistic Dual Value Iteration
Runzhe Wu Shanghai Jiao Tong University runzhe@sjtu. edu. en
Yufeng Zhang Northwestern University aatengzhaag0.3300u.noottveeeees
Zhuoran Yang Princeton University zy60princeton. edu
Zhaoran Wang
Northwestern University zhaoranvang@gmail.. com
Abstract
In constrained multi-objective RL, the goal is to learn a policy that achieves the best performance specified by a multi-objective preference function under constraint. We focus on the offline setting where the RL agent aims to learn the optimal policy from given dataset. This scenario is common in real-world applications where interactions with the environment are expensive and the constraint violation is dangerous. For such setting, transform the original constrained problem into a primal-dual formulation, which is solved via dual gradient ascent. Moreover, we propose to combine such an approach with pessimism overcome the uncertainty in offline data, which leads to our Pessimistic Dual Iteration (PEDI). We establish upper bounds on both the suboptimality and constraint violation for the policy learned by PEDI based on an arbitrary dataset, which proves that PEDI is provably sample efficient. We also specialize PEDI the setting with linear function approximation. To the best of our knowledge, we propose the first provably efficient constrained multi-objective RL algorithm with offline data without any assumption on the coverage of the dataset.
1 Introduction
There has been increased interest in multi-objectio RL in recent years, Compared with traditional single-objective RL, the goal of the multi-objective one depends on a preference function, which takes the multiple objectives as input and outputs a scalar. The multi-objective optimization problems are usually constrained, as otherwise, may cause danger malfunction in applications. For example, consider home automation system that helps humans monitor and control home attributes which can be regarded as nulti-objectives. Users at different times may value different aspects of its services. Some may think highly of lighting at night, while others may concern the climate. We can formulate the users' preference as a preference function on the multiple objectives. Therefore, dealing with multi-objective optimization problem. However, the system cannot optimize this problem without any constraints, which might go against human's 's will, such as generating extreme climate inside a house performing unacceptably energy-consumen operations.
system
We formulate the constrained multi-objective Markov decision process (CMOMDP), which is similar to the constrained Markov decision process (CMDP) (Altman 1999). The difference is that the objectives are multiple and constraints can be nonlinear. We aim to minimize the value of preference function, which takes multiple objectives as input and outputs scalar.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Most existing RL methods assume full accessibility of the environment for the agent, which tends to be impractical as the exploration could be expensive (Gottesman et al., 2019) and dangerous (Shalev Shwartz et al. 2016). Hence, we consider the offline case where the agent has only a historical dataset collected a priori and has no further interactions with the environment. This setting is common and embodied in various scenarios such as healthcare (Chakraborty and Murphy] (2044) and auto-driving (Sun et al. 2020). However, offline RL is less understood theoretically (Levine et al. 2020 than online RL, and how to maximally exploit the dataset remains unclear.
In this paper, we study the offline CMOMDP. The challenges are threefold:
(i) Different from CMDPs, the nonlinearity of the preference function and constraints of CMOMDPs makes the analysis challenging. Moreover, constraints can be neither convex nor concave in the policy, which means the optimization problems usually non-convex. It brings great difficulty to designing a provably efficient algorithm.
(ii) Since further interaction with the environment is prohibited, the dataset's quality is guaran- teed. The data collected by the experimenter may not sufficiently cover the trajectories induced by the optimal policy. Therefore, the information of the optimal policy could be limited, which probably makes the suboptimality and constraint violation arbitrarily large.
(iii) As the CMOMDP can be considered a generalization CMDP (see the reduction in Appendix any difficulties emerging in the CMDP will arise here too. For example, due to constraints, the Bellman optimality equation may not hold anymore. Therefore, most existing offline RL. algorithms based on dynamic programming inapplicable.
Challenge (i) is inherent in CMOMDPs, and certain requirements on the preference function and constraints are inevitable. Hence, We suppose they satisfy some conditions. For instance, a geometric analog of Slater's condition, which is usually assumed in CMDPs, is imposed. To tackle challenge (ii), existing works have put a great effort. One possible principle is pessimism, which applies penalties to ensure pessimistic estimation. This method is successful in ordinary RL, and we extend to CMOMDPs. We also note that we only impose a minimal assumption on the offline dataset's compliance in our analysis. For challenge (iii), we apply the convex conjugate and Fenchel's duality to transform the problem into a primal-dual formulation.
In summary, our work answers the following question:
Is it possible to develop a provably efficient offline algorithm for constrained multi-oojectivve reinforcement learning with minimal assumptions the dataset?
We propose the Pessimistic Dual Iteration (PEDI) algorithm. Theoretical contributions are as follows:
By transforming the original constrained optimization problem of CMOMDPs into primal-dual formulation via convex conjugate and duality, we develop the algorithm for general CMOMDPs with offline dataset, which iterates in a dual gradient ascent manner. Then, we instantiate the algorithm for linear kernel CMOMDPs, which is a large class of CMOMDPs that includes the tabular case.
(ii)
We show in Appendix | the significance of pessimism in offline CMOMDPs. To summarize, we decompose the discrepancy between a value function and the optimal one into spurious correlation, intrinsic uncertainty, and optimization error, among which the spurious correlation is the most difficult to control. However, by maintaining pessimistic estimates of the value functions, PEDI eliminates the spurious correlation.
(ii) We establish theoretical guarantees for PEDI. Specifically, we demonstrate that two metrics, the suboptimality and the constraint violation, can bounded from above by the optimiza- tion error of O(1/VK) and the intrinsic uncertainty, where K is the number of iterations. When specialized to linear kernel CMOMDPs, the upper bound of suboptimality matches the information-theome thhorretic lower bound up to the optimization error and multiplicative factors of constants related to the CMOMDP, which suggests the near-optimality of PEDI.
(iv) We show that the error of PEDI is data-dependent, i.c., it depends on how well the dataset covers the trajectories induced by the optimal policy. When the trajectories are assumed further to be sufficiently covered, the suboptimality and constraint violation are O(1v/N) where N is the number of trajectories in the dataset.

---

To the best of our knowledge, we are the first to propose provably efficient offline algorithm that considers the constrained multi-objective RL without any assumptions on the coverage of the dataset. As by-product, our method can be viewed as highly generalized one as it can easily reduce to certain simpler cases such as CMDPs, which is discussed in Appendix
1.1 Related works
Constrained RL. Our work is closely related to CMDPs (Altman 1999). Several recent works
(Efroni et al. 2020 Ding et. 2021 2021 Quu et al. 2020: Brantley al. 2020: Tessler et al. 2018) have studied the MDP with linear constraints and others (Bhatnagar and Lakshmanan 2012 Chow et al. 2017: Paternai al. 2019] have considered RL with more complex constraints. Most of them have provided algorithms with both regret and total constraint violation guarantees. However, while these approaches are successful in CMDPs, they cannot be applied CMOMDPs where objectives are multiple and constraints can be nonlinear. The difference between their methods and ours are (i) they usually assume the Slater's condition, while consider its geometric analog, and (ii) most works utilize the Lagrangian multiplier to handle constraints, while in our method, we obtain a primal-dua formulation via conjugate.
Multi-objective RL. Existing studies on multi-objective RL can be divided into two groups: the first maintains of Pareto-optimal policies (Barrett and Narayanan 2008 Castelletti et al. [011] 2012] Wang and Sebag] 2013). and the second collapses multi-objective vector into a scalar and then apply standard RL method (Barrett and Narayanan 2008) Natarajan and Tadepalli] 2005 Van Moffaert iet al. 2013) Cheung 2019). However, these methods are available in unconstrained multi-objectivy RL but unsuitable for constrained cases. The difficulty that the constraints invalidate the Bellman optimality principle, which is the cornerstone of these works.
Offline RL. Recent successful offline RL (Lange al. 2012 Levine et al. 2020) methods (Fujimoto
ct al. 2019; Laroche et al.] 2019; Jaques et al. [2199] Wu et al.) 2019; Kumar et al., 2019 2020
Agarwal ct al. 2020 Yu et 20220 Kidambi et |2.20 Siegel al. 2020 Nair et al. 2020 Luu
ett al.00 Wang et al. 2020a b) Tosatto et al. 2017] Farahmand et al., (010)]2010) fall into two pessimistic a algorithms and (ii) proximal pessimistic algorithms. (i) gives a lower estimate for states and actions less covered by the dataset, while (ii) avoids visiting these less visited states and actions by regularization. However, existing methods are largely based on approximate dynamic programming and do not take constraints into account, thus failing to apply. Our proposed method generalizes the ordinary pessimistic algorithm so that it is compatible with multiple objectives and constraints.
categories (Buckman al. 2020) (i) uncertainty-awe
In the analysis, we only assume the compliance of the dataset. In comparison with existing works, which assume the sufficient coverage of the dataset such as the finite concentrability coefficients (Antos al., 2008 Farahmand et al., 2010, Scherrer et al. 2015 Le et al. 2019 Chen and Jiang 2019 et al., 2020)) and uniformly lower bounded densities of visitation measures (Yin et al. 2021), require assumptions as they often fail to hold in practice. As Wang et al. (2020a) have studied the influence of insufficient coverage of the dataset, their conclusion is also reflected in our main results. Moreover, we do not impose any constraints the affinity of the behavior policy and the learned policy (Liu et al., 2020). In addition, our general algorithm uses convex conjugate, a technique used similarly in Yu et al. (202T); Miryoosefi and Jin (202I) but their method cannot apply to offline situations and Yu et al. 2202 do not address the function approximation setting.
1.2 Notations
For simplicity, we write (f.g)x Sx ((=))(())) dx as the inner product on space X' for functions
f.g : xx R. We also define the norms || = V(f, I'xx and || | = supxex [x()). We denote by [n] the set of positive integers not greater than n, i.e., [n]
{i E 2 < i S n). For two vectors x, x' E RD,, we write xe 2 x' (or x S x') if x is not smaller (or larger) than x' in an elementwise manner. We set x = (lzz). [z2)....,/20 (e)....,.1)) and x+ = (max(41, 0), max(x2, 0), ..... max(#D, 0})T. We denote by DD the D-dimensional unit Euclidean ball, i.c., BO = {a E R ||ح|| < 1). The set of probability distributions on a set X' is denoted by A A(Y). We denote by Ō(-) the big O notation ignoring logarithmic factors.
3

---

2 Preliminaries
2.1 Constrained multi-objective Markov decision process (CMOMDP)
We consider an episodic CMOMDP given by .M- = (S,A, H.P.c) where S is a state space. AA is an action space, H E + is the horizon, P = (Pr)k= is collection of transition kernels PA : S x A ((S), and c {cr 1/ is collection of cost functions C₁ S x A + [0, 1j Note that by P we mean both the probability density function and the probability mass function, as they can be unified (see Appendix for details). We suppose fixed initial state S for simplicity. However, a stochastic initial state poses no extra diffieulty to our analysis. In each episode, given a policy π {Th ) 1=1 where F S - (AA), the agent interacts with the environment as follows. At state 8n, the agent takes action an E AA according to TT. (8))) and then receives a stochastic cost CA E [0, 1j2, for which assume [E[c,, (&,; 0n Cb ca(s,)) a)- The system then transits the next state *1+1 according to (. 8h, a,). The episode terminates at state #1+1 where no action is taken and the cost is zero.
Given policy т, the state-value function V S - HD and the action-value function Q% : S8 A - [0, H)D at the h-th step are defined as (s) = EE C1(8;, a:) 8% =] and Q% = E,, 1E (s a.) st. = S, Oh a] where the expectation Ex taken with respect to a; ~ (- and 81+1 ~ valued, and we use bold letters to represent vectors. We denote their i-th scalar components by V,,"' and Oi respectively. For notational simplicity, we write: PA [ (s, a) = P (s'),, Bx [x][[(ss, a) (n(s,a) a) + PM[V a), and DD, [Q]()) Ea x) QQ a)]. Thereby, the Bellman equation for any (s, E S x A and h [H] can be written as Q7 a) B, [V, a), and (s) Dr (s). Our goal is to minimize the value of a preference function subject to some constraints. Formally, we define g RDD + R as the preference function and assume that g is 1 1-Lipschitz and convex and that g(x) g(z") holds as long as 2 x'. For example, g(æ²) can be the summation over { or the maximum among {-:] We aim to find the optimal policy n of the following constrained optimization problem,
0z) for i E [A: H]. Note that those value functions are D-dimensional vector-
min
g (V)
s.t. Ex
(1)
TEA(A) S.H)
where W S [0, H) is a target set. We use Vi = Vi" (s) to denote the state-value function of the optimal policy of ([) for simplicity.
Solving ① is impossible when have no geometric requirements on the target W Cor- responding to the Slater's condition commonly imposed in CMDPs, we establish its geometric analogue for CMOMDPs, studied in Yu al. (202T). Let V be the set of achievable values, i.e.,
v= (s) any policy T}. and W = Vn be the achievable values within the target set. We suppose W nonempty. We denote by OW and OV the boundaries of W and V, respectively. With a little abuse of notations, we set @w = OW n 8V as the intersection of boundaries. If OW is nonempty, then for each W &WW, we define the angle between support vector at W
7W)) = min { {<(a b) a, b are support vectors of W and V at W, respectively)
where L(a, b) denotes the angle between and b. We impose geometric requirements on the target set W as stated below.
Assumption 1. We assume the target set W is closed and convex, and there exists an upper bound Tuax E - 1)) such that max 7 (W) < "fmmxx Moreover, we assume W is a lower set, i.e., for any W W it holds that W' E W for any 0 < W' < W.
We write p = 2/ sin(Tmax) for notational simplicity. Explanations and justifications of Assumption I are provided in Appendix where we show that this assumption is reasonable and closely related to Slater's condition. However, the optimization problem ① is still hard even with these assumptions. Instead, we solve it by considering the suboptimality and constraint violation as performance metrics, which are defined as
SubOpt(#) o (s) (VV (s). Violation(1)) = dist (VT W*),
(2)
For CMDPs with constraints in the form of V < the Slater's condition assumes the existence of a policy 7 such that V <
The support vectors point normals to the support hyperplanes this point.

---

where we define dist(VP' (s), (s), W*) = minwew- [V] W
To show that the formulation of CMOMDPS is reasonable, state the relationship between CMOMDPs and CMDPs the following proposition, which suggests that the CMOMDP a generalization of the CMDP. The proof is deterred to Appendix
Proposition 1. The CMDP is special case of the CMOMDP, and the Slater's condition assumed in CMDPs corresponds to the existence of Ymax in Assumption I in CMOMDPs.
2.2 Offline learning
We consider the offline setting where we only have access dataset D {(S, di +))) with N trajectories collected priori by an experimentor. We only make the following assumption on the data collecting process.
Assumption 2 (Compliance of dataset). We assume that the dataset D compliant with the CMOMDP M, Le.,for any E [0, 1 S, E [H] and [N],
PRo 11 c Fh) Pr (s sh = c S7. ab a%)
(3)
where F7. is the o-algebra generated via FT, of((s , (n- S (T- 1) +))) The probability on the left-hand side of (3) is with respect to the joins distribution of the data collecting process, and that of the right- haand- side is with respect the underlying CMOMDP.
Assumption 2 is adapted from Jin et al. (020b). It implies that the dataset D is generated from the CMOMDP and possesses the Markov property. Such assumption holds when the experimenter collects the dataset by interacting with the CMOMDP. In particular, we do not require that the data collecting process well explores the state-action space. In other words, do not impose any assumption on the coverage of the dataset.
3 Pessimistic Dual Iteration (PEDI)
In this section, we first motivate our method solve CMOMDPs in Section 3.1 Then, we develop our algorithm, Pessimistic Dual Iteration (PEDI), for general CMOMDPs in Section 3.2 and introduce an instantiation for linear kernel CMOMDPs in Section 3.
3.1 Primal-dual formulation
To solve problems like (1. recent works usually apply Lagrangian multipliers to handle the constraints. However, seek to use another dual method. Specifically, consider the following problem:
p" min (SubOpt(x) + Violation(T)).
where v is a scaling constant that serves as a trade-off between suboptimality and constraint violation. In Appendix D we show that when 1, (1) and 44) share the solution, and thus they equivalent. We note that the formulation of (4) is different from existing works on CMDPs where v usually plays the role of the Lagrangian multiplier. Intuitively, a large lies more emphasis on satisfying the constraints, while small // focus on reducing the suboptimality.
However, p" is hard to solve in (4, since the relationship between the objective and the policy is complex. Therefore, we substitute the policy æ with the state-value function in the following way,
pa min (g(V)(s)) (x) - (V)(s)) + v dist (VT(s),
(5)
= min VEV
(g(V) - g (V' (8) + v dist (V, W*))
Nevertheless, solving this problem is still hard since the objective is nonlinear in V and thus standard RL cannot apply. Therefore, we utilize the convex conjugate to "linearize" the objective. This
technique is widely used in related works (Miryoosefi and Jin 2021 Yu et al. 2021). Specifically, by convex conjugate, we have
(V) = max
( (g)), dist(V, (,t (W") = max (a TV BEBD
max a T x))
(6)
aggo
=eW-
5

---

E-uncertainty quantifier if the for any V E V. The effective domains, BD, of both a and 3 are obtained by the 1-Lipschitzness and Corollary 13.3.3 Rockafeell (1970). To see why the second equality of (6) holds, we notice that
dist(V, W*) = max (a T max #ER
(a T x (as )"
aEBo
and (+) attains the maximum when æ W since a E B We call a and B the dual variables
throughout this paper. By plugging (6) into (5) we have
p" min max LVV; 3) = 3 - (3( 1000-g(1 (VV + va V max & x. NEW
VEV BEB
Its dual problem can be written as d' = maxo, D(xx, 3), where D(o,, 3) is the dual function defined D(a,, (3) minvey L(V; a, (3.. We notice that L(V; ar, is convex in V V and concave in at 3 E BD, which implies the strong duality, pa = d" Hence, dual methods can apply.
When and /3 are fixed, solving D(a, 3) is planning problem. When the model is known, it suffices to conduct value iteration on the model. However, what we have a dataset collected a priori develop the offline planning algorithm that is pessimistic variant of
in offline RL. Therefore, the value iteration (Jin et al. 2020b), which applies penalties to ensure pessimism. We explain why pessimism is erucial to offline CMOMDP in Appendix [F]
We now describe the high-level intuition of our approach. Consider a meta-algorithm that constructs the empirical transition kernel P and the empirical cost function è based on the dataset D. As defined below, we introduce the uncertainty quantifier that bounds the estimation error from above with a confidence parameter & (0, 1).
Definition 1 (f-uncertainty quantifier). We call , r following event
E = (P Pa(s'ss,a) a) S I ((,sa) - (s, S (s)
(8)
for all (s, 8') E A S, H E [D]}
holds with probability at least द. Here write lf (T D rx").
Then, we can construct the empirical counterparts of PA and B, by PA (s)
(V).,, Pa P s,a))s and [x]V[(s,a) = En a) + Px[V](s,a) Note that for any function
V: [0, H], under the event &, it holds for any a) E S x A and any h E [M] that
(PA - PPPIIV((ss = =1ʃ PPl
Pa(s ((s) ds' s H J (I(
Therefore, we define I' [s, a) = H (T ds', which quantifies the uncertainty arising from the transition kernel. We use the É-uncertainty quantifier as the penalty function for pessimistic plamning, which leads to a conservative estimation of the value function. We formally describe our planning method in Algorithm D where 0 denotes projection vector to be specified later. By adding the pessimistic penalty Ho + rg to the estimated value, we ensure a conservative estimation. We also truncate Q and V in (0, h + 1]" to improve the estimation.
It remains to solve maxx,BEss D(a, 3). We utilize the projected subgradient method which produces sequence of dual variables {a*1 === and {B*} that approximately solves the dual problem. detailed description of projected subgradient method is provided in Appendix H.6.2 For a brief' description, we update the dual variables via
Jk=1
a A+1 + --Igo fa + +1 (V arg max TT)}.
=EW*
(9)
gh+l + Igo B* + +1² (v* - 0g (B*1))
where V E arg minvey a( 3h)) and n/ is the step length at the k-th iteration.
As claimed in Proposition I the CMDP is special case of the CMOMDP. Moreover, we show in Appendix C that when reducing to the CMDP, the objective 7 reduces to the Lagrangian formulation of the CMDP problem. Hence, our proposed method has good generalization ability.

---

Algorithm/ 1 Pessimistic planning.
1: function PESSPLANNING D, (TT 11) ) h=1)
2:
for step H H I,..,, do
3:
Qn < (+) (V +T 1+ +
4:
Qx(:,-) + min { QQ (--,,, -H 1/
5:
(-) < arg ae Qx(:)))0
6: (.) f Dr, (+,l(-)
7: end for
8: return श {m Q (Qu V (Vil
9:
end function
3.2 General CMOMDPs
Based on the above analysis, we now develop the Pessimistic Dual Iteration (PEDI) (Algorithm 2 for general CMOMDPs, which motivated by the dual gradient method in solving the minimax optimization problem. Specifically, PEDI solves D(a, 33) via PESSPLANNING (Algorithm I and updates dual variables via (9), alternately. The output policy ã is a mixed policy executed by randomly Jk= with equal probability beforehand and then exclusively following
selecting policy x from {
x thereafter. Hence, it holds that, for the mixed policy मं V,*(s) = 1 Σk= V (s). Note that the mixed policy may not be Markov policy (Altman 1999). However, would be useful to extend the definition of policy क = {Tr !!1 so as to allow nr to depend not only on but also on some initial randomizing mechanism. That is, may have set of policies 2f and distribution g A(U). Then we define the mixed policy of 24 Tu. as a policy to be executed by first using & to choose some policy U and then proceeding with only that policy. The optima of (1] over the mixed policy is still attained by the Markov policy x². Thus, SubOpt(f) remains reasonable performance metric of our algorithm.
K
Algorithm 2 Pessimistic Dual Iteration (PEDI).
Input: offline dataset D, step length (1)* 1
1k=1 scaling parameter
Output: the mixed policy म { # of } kk=1
1: randomly initialize dual variables at 32 E BD, and set 0 vo+ + 31
2: construct { HH 1= and {Px) based on
3: construct the ξ-uncertainty quantifier {(1 1 based on
4: for iteration k = 1.2.....A K do
5: π.. Q*, V + PESSPLANNING 0h D. [17 12)
#
6: update at, 3h to ++1 g via
7: gh+1 x- va++1 gh+l
8: end for
3.3 Linear kernel CMOMDPs
In this section, we study PEDI settings with linear function approximation such as linear kernel CMOMDPs. To that end, we first introduce the linear kernel CMOMDP, which is generalization of the linear kernel MDP (Yang and Wang 2019 Jin et al. 2020a Cai et al. 2020). Then, propose
an instantiation of Algorithm for linear kernel CMOMDPs.
Definition 2 (Linear kernel CMOMDP). The CMOMDP (S, A, H.P, c) is linear kernel CMOMDP
with a known kernel feature map vo x A + Rdd and a known value feature map S x A + d2, for any h E [H) there exist unknown vectors On E TRds and 0 E dd for any E [D] such that for any (s, a. s') Ax
P v(s,,, On. (s p(s,a)Tef.
7

---

Let d = maxfd1, d2}.
We assume there exists a constant R > O such that
R max (y (bs a, a')) & J (u" ((ss,,,,'')) as' S d
max #EES
for any (s, E 8 x And y: 11yll2 S 1. Moreover, assume 100,122 S vd and 110g ll2 S fdr i [d]
The existence of constant It naturally holds when (5 a. -) is upper bounded and Lipschitz continuous for all (s, a) E S 5xAA Note that the tabular CMOMDP is special case the linear kernel CMOMDP with R (see Appendix for detailed discussion).
An instantiation of PEDI for linear kernel CMOMDPs is deferred to Appendix E where we propose a method to estimate the empirical transition kernel P and cost function and thereby construct a g-uncertainty quantifier.
4 Theoretical results
In this section, we first show upper bounds for suboptimality and constraint violation for PEDI on general CMOMDPs in Section 4.1 In Section 4.2 we show that PEDI achieves the minimax optimality up to the optimization error and multiplicative factors of constants related to the CMOMDP when specified linear kernel CMOMDPs. Moreover, when the dataset has sufficient coverage over the trajectories induced by the optimal policy, the intrinsic uncertainty is guaranteed to be (LIV/N) where N is the number of trajectories in the dataset.
4.1 Results of general CMOMDPs
By using pessimistic planning (Algorithm D. ensure pessimistic policy म. We formally state this notion in the following lemma.
Lemma (Pessimism). Suppose that Assumptions I and hold. By Algorithm under event defined in (). for any (s, a) E S x A and h E [H]. it holds that (s) 2 Vi (s), (x, 2 Q (8,a) a), and dist (V (s), W*) dist (Vr* (s), W*). Furthermore, it holds that
9 (V) 2 (V (s)
and dist (Vi(s), W") 2 dist (s),
where Vi(s) = Ex V (s) and प is the output of Algorithm 2
Proof of Lemmal
7
See Appendix H.I for detailed proof.
We are now ready to establish the following theorem, which characterizes the suboptimality and constraint violation of PEDI for general offline CMOMDPs.
Theorem (Suboptimality and constraint violation for general CMOMDPs), Suppose that Assump- tions 7 and 2 hold. Under event & defined in (8), for the output policy âे of Algorithm 2 when we set = p and n 2G-1 /D// (or 2G-1 VD/K K if K is predefied), where 2(1 v)H D, holds that
2 (cK + +IntUnccrtT)) Violation ( S
SubOpt(T)) S cg + "Intunn
(10)
where we let C denote absolute constant and define
DH K
H IntUntttt = + p) D
' =C(+P)
Σ E.
(I) an)loo 1 =
#=1
Proof of Theorem See Appendix consists of two steps.
H.2 for detailed proof. Here we provide proof sketch, which
H.2
First step: upper bounding (ubOpt(#) Violation(#), which is our objective Here
is the output of PEDI (Algorithm 2). By pessimism, we have SubOpt(*t Violation(f) <
8

---

((Vi(s) - (s) + dist( [V (s), W*) where vi(s) -
Ex=
Vf(s).
We do linearization
via convex conjugate and then get
K
K
SubOpt(ft) + Fiolation(t)
SK-
max
3
(+())
Σ
(3)
9 (VT()))
||
k=1
k=1
K
K
max |
(1))
max OF WEW
Recall that PEDI uses the projected subgradient method, which approximates the max operator above by sequence of variables at the expense of sublinear approximation eπror, which leads to
K
(0*)
vi(a) - 9- (8+) {
SubOpt(+)) + v Violation (t) SK 1
(Vi(())
1=1
{(((t)
+ K Σ (at) T vi(a)
(at)² T
max
#EW-
+ C(1 +
where C' is a constant. We rearrange the right-hand side above with some tricks and then obtain
Σ (0t) T (((v(()) ( -v(s)) + +V//D/DD/EEEE
K
SubOpt (t) + Violation(a) S K-1
The last term in the right hand side above is exactly ex. Intuitively, the term (V))) (a))) indicates the projected difference of state-value functions along O, which motivates the PESSPLANNING (Algorithm(]) [ We apply results from this pessimistic approach and then conclude
SubOpt(ft) +v Violation (t) = >=(((vi (vi(s) ( (Vi(ss) tu
t dist (Vi w²) I Ex Inttertn
Second step: upper bounding SubOpt(#) and Violation(1)) individually. This done by two facts: (i) dist (..-) 2 0, and (ii) y (V) g (v) 2 -v -v dist(V (V) (s)))/ We plug them into the resulting inequality in the first step and then complete the proof.
As shown in Theorem [ our pessimistic algorithm bounds the suboptimality and constraint violation from above by the sum of the optimization error еg E O(1/VK) and the intrinsic uncertainty IntUneert. The optimization error ex vanishes as K goes into infinity, Later, we will show that the intrinsic uncertainty, Tnt Uncert: impossible to eliminate through an analysis of PEDI on linear kernel CMOMDPs in Section 4.2
4.2 Results of linear kernel CMOMDPs
The following theorem characterizes the suboptimality and constraint violation of PEDI for linear kernel CMOMDPs. Recall that we instantiate PEDI to linear kernel CMOMDPs in Appendix E
Theorem 2 (Suboptimality and constraint violation for linear kernel CMOMDPs). We set X = 1 and CR log (dN) + log (DHHE) where C > 0 is an absolute constant. Then, under Assumptions aand 2 (TP. ) defined in (4 (Appendix E) is É-uncertainty quantifier. Hence, under the
same settings of v and n² in Theorem I (10) holds with probability at least for the output ß,
and the intrinsic uncertainty is specified to
H
Ex H ʃ
Inturettt = 2 p)
k. kellbbsh, on, an, Al ds' ho (oll:l/),,,aa
A=
Proof of Theorem
See Appendix H.3 for a detailed proof.
In what follows, we show that when the dataset sufficiently covers the trajectories of the optimal policy, the intrinsic uncertainty is O(L/VN) where N is the number of trajectories in the dataset.

---

Corollary (Dataset with sufficient coverage). Suppose that the T-th trajectory {(8 o ch) h=1 of the dataset is generated by behavior policy Tho for E [N]. Meanwhile, we assume that there exists a constant Ç >> O such that (5,(8,))/V b.t (8, a) S ş for any h E [H)T E [N], and Th=1 the visitation measures of π² and n. Then, have with probability at least 1 - that
}
(s, a) E S x A. Here {1) and (ph
IntUncert = p)HP-V//SINN)
Proof of Corollary 7 See Appendix H.3 for a detailed proof.
Here (S] denotes a certain measure on S. For instance, when S = [0, and we take the Lebesgue measure, we have [S] 1. Note that Corollary 1 holds under a weaker condition than the uniform coverage (Wang al., 2020a Rashidinejad et al. 2021 where the condition max, μ³ /²/pp" C for certain constant C. However, our algorithm is still able to achieve the intrinsic uncertainty of O(/I/N). In particular, our condition, n²/ 10/pbb < s. can hold when we have expert demonstration in the dataset D (Buckman et al. 2020).
In Theorem we notice that when the number of iteration K goes into infinity, the optimization error EK vanishes, and the suboptimality and constraint violation are bounded from above by the intrinsic uncertainty Int Uncert only. However, this is the best effort that we can put. The following theorem indicates that the term Int Uncert is impossible to eliminate since it arises from the information-theoretii lower bound.
Theorem 3 (Information-theoreee lower bound). For the output t of any algorithm of offline CMOMDPs, there exists linear kernel CMOMDP M with initial state E S and dataset DD compliant with M, such that
SubOpt(R)
ED
[IL((S, an)ll (np(s,aan)lx=) + +1S- 11 an, sh,,s')l s')ll ds = 2G
E Ex
where the expectation is taken with respect to the data collecting process, and c: >> O is an absolute constant.
Proof of Theorem
See Appendix H.4 for a detailed proof.
By Theorem 2 and Theorem we find that the upper bound of suboptimality of Algorithm 2 for linear kernel CMOMDP matches the information-theorest lower bound up the optimization error OLL/V/) K) and some multiplicative factors horizons, dimensions, and geometric properties the target set, which means that PEDI is near-optimal for linear kernel CMOMDP.
5 Experimental Results
We also conduct numerical experiments to verify theory. Please Appendix for details. The results show that the proposed algorithm not only provably efficient but also applicable.
6 Conclusion
In this paper, we propose a general algorithm, Pessimistic Dual Iteration (PEDI), for constrained multi- objective reinforcement learning with offline data. We show our algorithm delivers data-dependent upper bound for suboptimality and constraint violation. The upper bound is composed of the optimization error and the intrinsic uncertainty. Moreover, we show that the bound of suboptimality is minimax optimal for linear kernel CMOMDPs to the optimization error and multiplicative factors of constants related the CMOMDP, When the trajectories of optimal policy sufficiently covered, the intrinsic uncertainty is proved be O(1//N) where N the number of trajectories in the dataset.
10

---

Acknowledgments and Disclosure of Funding
We thank all anonymous reviewers for their useful comments. Zhaoran Wang acknowledges National Science Foundation (Awards 2048075, 2008827, 2015568, 1934931), Simons Institute (Theory of Reinforcement Learning), Amazon, J.P. Morgan, and Two Sigma for their supports. Zhuoran Yang acknowledges Simons Institute (Theory of Reinforcement Learning).
References
Abbasi-Yan Yadkori, Y., Pál, D., and Szepesvári, C. (2011). Improved algorithms for linear stochastic bandits. In NIPS, volume 11, pages 2312-2320
Abbasi-Yadkori,
Agarwal, R., Schuurmans, D., and Norouzi, M. (2020). An optimistic perspective offline rein- forcement learning. In International Conference on Machine Learning, pages 104-114, 11.. PMLR.
Altman, E. (1999). Constrained Markov decision processes, volume 7. CRC Press.
Antos, A., Szepesvári, C., and Munos, R. (2008). Learning near-optimal policies with bellman- residual minimization based fitted policy iteration and single sample path. Machine Learning, 71(1):89-129.
Barrett, L.. and Narayanan, S. (2008). Learning all optimal policies with multiple criteria. In Proceedings of the 25th international conference Machine learning, pages 41 41-47.
Bäuerle, N. and Rieder, U. (2010). Markov decision processes. Jahresbericht der Deutschen muuthemaiier--ereiniiiiin 1 11((4)21772443.
Bhatnagar, S. and Lakshmanan, K. (2012). An online actor-critic algorithm with function approxima- tion for constrained markov decision processes. Journal of Optimization Theory and Applications, 153(())688-708.
Brantley, K., Dudik, M.. Lykouris, T., Miryoosefi, S., Simchowitz, M., Slivkins, A., and Sun, W. (2020). Constrained episodic reinforcement learning in concave-convex and knapsack settings. arXiv preprint arXiv:2006.0500 0.
Buckman, J., Gelada, C., and Bellemare, M. G. (2020). The importance of pessimism in fixed-dataset policy optimization. arXiv preprint XiX::200000079999
Cai, Q. Yang, Z.. Jin, C., and Wang, Z. (2020). Provably efficient exploration in policy optimization. In International Conference on Machine Learning, pages 1283-1294. PMLR.
Castelletti, A., Pianosi, F., and Restelli, M. (2011). Multi-objective fitted q-iteration: Pareto frontier approximation in one single run. 2011 International Conference on Networking. Sensing and Control, pages 260-265. IEEE
Castelletti, A., Pianosi, F., and Restelli, M. (2012). Tree-based fitted q-iteration for multi-objective markov decision problems. In The 2012 international joint conference on neural networks (IJCNN), pages 1-8. IEEE.
Chakraborty, B. and Murphy, S. A. (2014). Dynamic treatment regimes. Annual review of statistics and its application, 1:447-464.
Chen, and Jiang, N. (2019). Information-theoree considerations in batch reinforcement learning. In International Conference on Machine Learning, pages 1042-1051. PMLR.
Cheung. W. C. (2019). Regret minimization for reinforcement learning with vectorial feedback and complex objectives. Advances in Neural Information Processing Systems, 32:726-736.
Chow, Y., Ghavamzadeh, M., Janson, I.., and Pavone, M. (2017). Risk-constrained reinforcement
learning with percentile risk criteria. The Journal of Machine Learning Research, 18(1):6070-613
Ding, D., Wei, X., Yang, Z., Wang, Z., and Jovanovie, M. (2021). Provably efficient safe exploration via puil policy optimization. In International Conference on Artificial Intelligence and Statistics, pages 3304-3312. PMLR.
11

---

Efroni, Y., Mannor, S., and Pirotta, M. (2020). Exploraion-explootation in constrained mdps. arXiv preprint ar XTXiv22003.02189
Farahmand, A.-m., Ghavamzadeh, M., Szepesvári, C., and Mannor, S. (2016). Regularized pol- icy iteration with nonparametric function spaces. The Journal of Machine Learning Research, 17(1):40094484.
Farahmand, A. M., Munos, R., and Szepesvári, C. (2010). Error propagation for approximate policy and value iteration. In Advances in Neural Information Processing Systems.
Fu, Z., Yang, Z., and Wang. Z. (2020). Single-timescale actor-critic provably finds globally optimal policy, arXiv preprint arXiv:2008. 00483.
Fujimoto, S., Meger, D., and Precup. D. (2019). Off-policy deep reinforcement learning without exploration. In International Conference Machine Learning, pages 2052-2062. PMLR.
Gottesman, O., Johansson, F., Komorowski, M., Faisal, A., Sontag, D., Doshi-Velez, F., and Celi. L. A. (2019), Guidelines for reinforcement learning in healthcare. Nature medicine, 25(1))16-18.
Jaques, N.. Ghandeharioun, A., Shen, J. H., Ferguson, C., Lapedriza, A., Jones, N., Gu, S., and Picard, R. (2019). Way off off-policy batch deep reinforcement learning of implicit human preferences in dialog. arXiv preprint arXiv: 1007 00056..
Jin, C., Yang, Z., Wang, Z., and Jordan, M. (2020a). Provably efficient reinforcement learning with linear function approximation. In Conference on Learning Theory, pages 2137-2143. PMLR.
Jin, Y., Yang. Z., and Wang, Z. (2020b). Is pessimism provably efficient for offline rI? arXiv preprint arXiv:2012. 15085.
Kidambi, R., Rajeswaran, A., Netrapalli, P., and Joachims, T. (2020). Morel: Model-based offline reinforcement learning. arXiv preprint arXiv:2005. 05951..
Kumar, A., Fu, J., Tucker, G., and Levine, S. (2019). Stabilizing off-policy q-learning via bootstrap- ping error reduction. arXiv preprini UrXiv:1906.0099 00949.
Kumar, A., Zhou, A., Tucker, G., and Levine, S. (2020). Conservative q-learning for offline reinforcement learning. arXiv preprint arXiv:2006.04779,
Lange, S., Gabel, T. and Riedmiller, M. (2012). Batch reinforcement learning. In Reinforcement learning, pages 45-73. Springer.
Laroche, R., Trichelair, P., and Des Combes, R. T. (2019). Safe policy improvement with baseline bootstrapping. In International Conference on Machine Learning, pages 3652-3661, PMLR.
Le, H., Voloshin, C., and Yue, Y. (2019). Batch policy learning under constraints. In International Conference on Machine Learning, pages 3703-3712. PMLR.
Levine, S., Kumar, A., Tucker, G., and Fu, J. (2020). Offline reinforcement learning: Tutorial, review, and perspectives open problems. arXiv preprint arXiv:2005.01643
Liu, Y., Swaminathan, A., Agarwal, A., and Brunskill, E. (2020). Provably good batch reinforcement learning without great exploration. arXiv preprint arXiv:2007.08202.
Miryoosefi, S. and Jin, C. (2021). A simple reward-free approach constrained reinforcement learning. arXiv preprint arXiv:2107.05216.
Nair, A., Dalal, M., Gupta, A., and Levine, S. (2020). Accelerating online reinforcement learning with offline datasets. arXiv preprint arXiv:2006.09:: 09359.
Natarajan, S. and Tadepalli, P. (2005). Dynamic preferences in multi-criteria reinforcement learning. In Proceedings of the 22nd International Conference on Machine learning, pages 601-608.
Paternain, S., Calvo-Fullana, M., Chamon, I.. F., and Ribeiro, A. (2019). Safe policies for reinforce- ment learning via primal-dusl methods. arXiv preprint ar arXiv:1911.09101.
12

---

Qiu, S., Wei, X., Yang, Z., Ye, J., and Wang, Z. (2020). Upper confidence primal-dual reinforcement learning for emdp with adversarial loss. arXiv e-prints, pages arXiv-2003.
Rashidinejad, P., Zhu, B., Ma, C., Jiao, J., and Russell, S. (2021). Bridging offline reinforcement learning and imitation learning: A tale of pessimism. arXiv preprint arXiv:2103./2000
Rockafellar, R. T. (1970). Convex analysis, volume 36. Princeton university press.
Scherrer, B., Ghavamzadeh, M., Gabillon, V., Lesner, B., and Geist, M. (2015). Approximate modified policy iteration and its application to the game of tetris. J. Mach. Learn. Res., 1626-1666.7.
Shalev-Shwarde S., Shammah, S., and Shashua, A. (2016). Safe, multi-agent, reinforcement learning for autonomous driving. arXiv preprint wwx.v::610.032900
Siegel, N. Y., Springenberg, T., Berkenkamp, F., Abdolmaleki, A., Neunert, M., Lampe, T., Hafner, R., Heess, N., and Riedmiller, M. (2020). Keep doing what worked: Behavioral modelling priors for offline reinforcement learning. arXiv preprint arXiv:2002. KKVV:2002.083966.
Sun, P., Kretzschmar, H., Dotiwalla, X., Chouard, A., Patnaik, V., Tsui, P., Guo, J., Zhou, Y., Chai, Y., Caine, B., et al. (2020). Scalability in perception for autonomous driving: Waymo open dataset. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 2446-2454.
Tessler, C., Mankowitz, D. J., and Mannor, (2018). Reward constrained policy optimization. arXiv preprint arXiv:1805.
Tosatto, S., Pirotta, M., d' d'Eramo, C., and Restelli, M. (2017). Boosted fitted q-iteration. In International Conference on Machine Learning, pages 3434-3443. PMLR.
Van Moffaert, K., Drugan, M. M., and Nowé, A. (2013). Scalarized multi-objective reinforcement learning: Novel design techniques. In 2013 IEEE Symposium on Adaptive Dynamic Programming and Reinforcement Learning (ADPRL), pages 191-199. IEEE.
Wang, R., Foster, D. P., and Kakade, S. M. (2020a). What are the statistical limits of offline rl with linear function approximation? arXiv preprini arXiv:2010.1 1895.
Wang, W. and Sebag, M. (2013). Hypervolume indicator and dominance reward based multi-objective monte-carlo tree search. Machine learning. 92(2-3):403- 4299
Wang, Z., Novikov, A., Zoina, K., Springenberg, J. T., Reed, S., Shahriari, B., Siegel, N., Merel, J., Gulcehre, C., Heess, N., et al. (2020b). Critic regularized regression. arXiv preprint arXiv:2006.1513
Wu, Y., Tucker, G., and Nachum, O. (2019). Behavior regularized offline reinforcement learning. arXiv preprint arXiv:1911.1136
Yang, L. and Wang, M. (2019). Sample-optimal parametric q-learning using linearly additive features. In International Conference on Machine Learning, pages 6995-7004. PMLR.
Yin, M., Bai, Y., and Wang. Y.-X. (2021). Near-optimal provable uniform convergence in offline policy evaluation for reinforcement learning. In International Conference on Artificial Intelligence and Statisties, pages 1567-1575. PMLR.
Yu, T., Thomas, G., Yu, L., Ermon, S., Zou, J., Levine, S., Finn, C., and Ma, T. (2020). Mopo: Model-based offline policy optimization. arXiv preprint 2005::200....39
Yu, T., Tian, Y., Zhang, J., and Sra. S. (2021). Provably efficient algorithms for multi-objective competitive rl. arXiv preprint arXiv:2
Zinkevich, M. (2003). Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the 20th international conference on machine learning (ieml-03), pages 928-936.
13


Reviews:
[{"review_id": "bg0odLFvJG", "reviewer": "Reviewer_NsPb", "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.", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n\nThe 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\n\nThe 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. \n\nThe 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.\n\nAnother 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.\n\nMinor comments:\n-\tThe Slater’s conditions is referred to in several places but not defined.\n-\tL.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.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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_text": "", "extra_scores": {"ethical_concerns": "None that I could identify.\n\n", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3 hours"}, "extra_text": {}}, {"review_id": "QKpinlKmfja", "reviewer": "Reviewer_M9Rz", "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.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I have some questions:\n\n- The related work section seems to be missing a large number of recent works in constrained RL, specially those using primal-dual approaches.\n\n- 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\n\n- In Section 3.1, the difference between using a standard primal-dual formulation and the formulation (4) should be better motivated.\n\n- 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.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "None", "review_text": "", "extra_scores": {"ethical_concerns": "None", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "9Kr1vrTi8MO", "reviewer": "Reviewer_6gH1", "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.\n\n", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n- 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?\n- 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?\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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_text": "", "extra_scores": {"ethical_concerns": "-", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "4asgY_-HcJ", "reviewer": "Reviewer_U6xP", "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.\n\nFor 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.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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. \n\nThe main issue with the current paper is significance, which I elaborate on below, considering three dimensions:\n\n(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.\n\n(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.\n\n(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.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "n/a", "review_text": "", "extra_scores": {"ethical_concerns": "n/a", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

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)