Offline Constrained Multi-Objective Reinforcement Learning via Pessimistic Dual Value Iteration
Year: 2021

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.

text: 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.

heading: 1 Introduction
text: There has been increased interest in multi-objective 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, it may cause danger or malfunction in applications. For example, consider a home automation system that helps humans monitor and control home attributes which can be regarded as multi-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, the system is dealing with a multi-objective optimization problem. However, the system cannot optimize this problem without any constraints, which might go against human’s will, such as generating extreme climate inside a house or performing unacceptably energy-consuming operations.
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 a preference function, which takes multiple objectives as input and outputs a scalar.
35th Conference on Neural Information Processing Systems (NeurIPS 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 (ShalevShwartz 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, 2014) 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 are 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 not guaranteed. 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 of CMDP (see the reduction in Appendix C), 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 are 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 it 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-objective reinforcement learning with minimal assumptions on the dataset?
We propose the Pessimistic Dual Iteration (PEDI) algorithm. Theoretical contributions are as follows:
(i) By transforming the original constrained optimization problem of CMOMDPs into a 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 F 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.
(iii) We establish theoretical guarantees for PEDI. Specifically, we demonstrate that two metrics, the suboptimality and the constraint violation, can be bounded from above by the optimization error of O(1/ √ K) 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-theoretic 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.e., 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̃(1/ √ N) where N is
the number of trajectories in the dataset.
To the best of our knowledge, we are the first to propose a provably efficient offline algorithm that considers the constrained multi-objective RL without any assumptions on the coverage of the dataset. As a by-product, our method can be viewed as a highly generalized one as it can easily reduce to certain simpler cases such as CMDPs, which is discussed in Appendix C.

heading: 1.1 Related works
text: Constrained RL. Our work is closely related to CMDPs (Altman, 1999). Several recent works (Efroni et al., 2020; Ding et al., 2021; Qiu et al., 2020; Brantley et al., 2020; Tessler et al., 2018) have studied the MDP with linear constraints and others (Bhatnagar and Lakshmanan, 2012; Chow et al., 2017; Paternain et 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 to 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 we consider its geometric analog, and (ii) most works utilize the Lagrangian multiplier to handle constraints, while in our method, we obtain a primal-dual formulation via conjugate.
Multi-objective RL. Existing studies on multi-objective RL can be divided into two groups: the first maintains a set of Pareto-optimal policies (Barrett and Narayanan, 2008; Castelletti et al., 2011, 2012; Wang and Sebag, 2013), and the second collapses multi-objective vector into a scalar and then apply a standard RL method (Barrett and Narayanan, 2008; Natarajan and Tadepalli, 2005; Van Moffaert et al., 2013; Cheung, 2019). However, these methods are available in unconstrained multi-objective RL but unsuitable for constrained cases. The difficulty is that the constraints invalidate the Bellman optimality principle, which is the cornerstone of these works.
Offline RL. Recent successful offline RL (Lange et al., 2012; Levine et al., 2020) methods (Fujimoto et al., 2019; Laroche et al., 2019; Jaques et al., 2019; Wu et al., 2019; Kumar et al., 2019, 2020; Agarwal et al., 2020; Yu et al., 2020; Kidambi et al., 2020; Siegel et al., 2020; Nair et al., 2020; Liu et al., 2020; Wang et al., 2020a,b; Tosatto et al., 2017; Farahmand et al., 2016, 2010) fall into two categories (Buckman et al., 2020): (i) uncertainty-aware pessimistic 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.
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 et al., 2008; Farahmand et al., 2010; Scherrer et al., 2015; Le et al., 2019; Chen and Jiang, 2019; Fu et al., 2020) and uniformly lower bounded densities of visitation measures (Yin et al., 2021), we require no 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 on 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. (2021); Miryoosefi and Jin (2021) but their method cannot apply to offline situations and Yu et al. (2021) do not address the function approximation setting.

heading: 1.2 Notations
text: For simplicity, we write 〈f, g〉X = ∫ X f(x)g(x) dx as the inner product on space X for functions
f, g : X → R. We also define the norms ‖f‖2,X = √ 〈f, f〉X and ‖f‖∞,X = supx∈X |f(x)|. We denote by [n] the set of positive integers not greater than n, i.e., [n] = {i ∈ Z | 1 ≤ i ≤ n}. For two vectors x,x′ ∈ RD, we write x ≥ x′ (or x ≤ x′) if x is not smaller (or larger) than x′ in an elementwise manner. We set |x| = (|x1|, |x2|, . . . , |xD|)> and x+ = (max{x1, 0},max{x2, 0}, . . . ,max{xD, 0})>. We denote by BD theD-dimensional unit Euclidean ball, i.e., BD = {x ∈ RD : ‖x‖2 ≤ 1}. The set of probability distributions on a set X is denoted by ∆(X ). We denote by Õ(·) the big O notation ignoring logarithmic factors.

heading: 2 Preliminaries

heading: 2.1 Constrained multi-objective Markov decision process (CMOMDP)
text: We consider an episodic CMOMDP given by M = (S,A, H,P, c) where S is a state space, A is an action space, H ∈ N+ is the horizon, P = {Ph}Hh=1 is a collection of transition kernels Ph : S × A → ∆(S), and c = {ch}Hh=1 is a collection of cost functions ch : S × A → [0, 1]D. Note that by P we mean both the probability density function and the probability mass function, as they can be unified (see Appendix A for details). We suppose a fixed initial state s ∈ S for simplicity. However, a stochastic initial state poses no extra difficulty to our analysis. In each episode, given a policy π = {πh}Hh=1 where πh : S → ∆(A), the agent interacts with the environment as follows. At state sh, the agent takes action ah ∈ A according to πh(· | sh), and then receives a stochastic cost ch ∈ [0, 1]D, for which we assume E[ch|sh, ah] = ch(s, a). The system then transits to the next state sh+1 according to Ph(· | sh, ah). The episode terminates at state sH+1 where no action is taken and the cost is zero.
Given a policy π, the state-value function V πh : S → [0, H]D and the action-value functionQπh : S × A → [0, H]D at the h-th step are defined as V πh (s) = Eπ[ ∑H i=h ci(si, ai) | sh = s] andQπh(s, a) =
Eπ[ ∑H i=h ci(si, ai) | sh = s, ah = a] where the expectation Eπ is taken with respect to ai ∼ πi(· | si) and si+1 ∼ P(· | si, ai) for i ∈ [h : H]. Note that those value functions are D-dimensional vectorvalued, and we use bold letters to represent vectors. We denote their i-th scalar components by V i,πh and Qi,πh respectively. For notational simplicity, we write: Ph[V ](s, a) = Es′∼Ph(· | s,a)[V (s′)], Bh[V ](s, a) = ch(s, a) + Ph[V ](s, a), and Dπ[Q](s) = Ea∼π(· | s)[Q(s, a)]. Thereby, the Bellman equation for any (s, a) ∈ S × A and h ∈ [H] can be written as Qπh(s, a) = Bh[V πh ](s, a), and V πh (s) = Dπ[Qπh](s). Our goal is to minimize the value of a preference function subject to some constraints. Formally, we define g : RD → R as the preference function and assume that g is 1-Lipschitz and convex and that g(x) ≥ g(x′) holds as long as x ≥ x′. For example, g(x) can be the summation over {xi}ni=1 or the maximum among {xi}ni=1. We aim to find the optimal policy π∗ of the following constrained optimization problem,
min π∈∆(A |S,H)
g ( V π1 (s) ) s.t. V π1 (s) ∈ W∗, (1)
whereW∗ ⊆ [0, H]D is a target set. We use V ∗1 (s) = V π ∗
1 (s) to denote the state-value function of the optimal policy of (1) for simplicity.
Solving (1) is impossible when we have no geometric requirements on the target set W∗. Corresponding to the Slater’s condition1 commonly imposed in CMDPs, we establish its geometric analogue for CMOMDPs, as studied in Yu et al. (2021). Let V be the set of achievable values, i.e., V = {V π1 (s) : any policy π}, andW = V ∩W∗ be the achievable values within the target set. We suppose W is nonempty. We denote by ∂W∗ and ∂V the boundaries of W∗ and V , respectively. With a little abuse of notations, we set ∂W = ∂W∗ ∩ ∂V as the intersection of boundaries. If ∂W is nonempty, then for eachW ∈ ∂W , we define the angle between support vectors2 atW as
γ(W ) = min { ∠(a, b) |a, b are support vectors ofW∗ and V atW , respectively } where ∠(a, b) denotes the angle between a and b. We impose geometric requirements on the target setW∗ as stated below. Assumption 1. We assume the target setW∗ is closed and convex, and there exists an upper bound γmax ∈ [π2 , π) such that maxW∈∂W γ(W ) < γmax. Moreover, we assumeW
∗ is a lower set, i.e., for anyW ∈ W∗, it holds thatW ′ ∈ W∗ for any 0 ≤W ′ ≤W .
We write ρ = 2/ sin(γmax) for notational simplicity. Explanations and justifications of Assumption 1 are provided in Appendix B where we show that this assumption is reasonable and closely related to Slater’s condition. However, the optimization problem (1) 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(π) = g ( V π1 (s) ) − g ( V ∗1 (s) ) , Violation(π) = dist ( V π1 (s),W∗ ) , (2)
1For CMDPs with constraints in the form of V π ≤ b, the Slater’s condition assumes the existence of a policy π such that V π < b.
2The support vectors at a point are normals to the support hyperplanes at this point.
where we define dist(V π1 (s),W∗) = minW∈W∗ ‖V π1 (s)−W ‖2. To show that the formulation of CMOMDPs is reasonable, we state the relationship between CMOMDPs and CMDPs in the following proposition, which suggests that the CMOMDP is a generalization of the CMDP. The proof is deterred to Appendix C.1. Proposition 1. The CMDP is a special case of the CMOMDP, and the Slater’s condition assumed in CMDPs corresponds to the existence of γmax in Assumption 1 in CMOMDPs.

heading: 2.2 Offline learning
text: We consider the offline setting where we only have access to a dataset D = {(sτh, aτh, cτh)} H,N h,τ=1 with N trajectories collected a 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 is compliant with the CMOMDPM, i.e., for any c ∈ [0, 1]D, s′ ∈ S, h ∈ [H], and τ ∈ [N ],
PrD ( sτh+1 = s ′, cτh = c ∣∣Fτh) = Pr (sh+1 = s′, ch = c ∣∣ sh = sτh, ah = aτh), (3)
whereFτh is the σ-algebra generated viaFτh = σ({(sni , ani , cni ) | (n−1)H+i ≤ (τ−1)H+h}). The probability on the left-hand side of (3) is with respect to the joint distribution of the data collecting process, and that of the right-hand side is with respect to the underlying CMOMDP.
Assumption 2 is adapted from Jin et al. (2020b). It implies that the dataset D is generated from the CMOMDP and possesses the Markov property. Such an 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, we do not impose any assumption on the coverage of the dataset.

heading: 3 Pessimistic Dual Iteration (PEDI)
text: In this section, we first motivate our method to 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.

heading: 3.1 Primal-dual formulation
text: To solve problems like (1), recent works usually apply Lagrangian multipliers to handle the constraints. However, we seek to use another dual method. Specifically, we consider the following problem:
p∗ = min π
( SubOpt(π) + ν Violation(π) ) , (4)
where ν 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 (4) share the solution, and thus they are equivalent. We note that the formulation of (4) is different from existing works on CMDPs where ν usually plays the role of the Lagrangian multiplier. Intuitively, a large ν lies more emphasis on satisfying the constraints, while a 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,
p∗ = min π
( g ( V π1 (s) ) − g ( V ∗1 (s) ) + ν dist ( V π1 (s),W∗ )) = min V ∈V ( g(V )− g ( V ∗1 (s) ) + ν dist(V ,W∗)
) (5) 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
g(V ) = max β∈BD
( β>V − g∗(β) ) , dist(V ,W∗) = max
α∈BD (α>V − max x∈W∗ α>x) (6)
for any V ∈ V . The effective domains, BD, of both α and β are obtained by the 1-Lipschitzness and Corollary 13.3.3 in Rockafellar (1970). To see why the second equality of (6) holds, we notice that
dist(V ,W∗) = max α∈BD
( α>V − max
x∈RD
( α>x− dist(x,W∗) ) ︸ ︷︷ ︸
(∗)
) ,
and (∗) attains the maximum when x ∈ W∗ since α ∈ BD. We call α and β the dual variables throughout this paper. By plugging (6) into (5), we have
p∗ = min V ∈V max α,β∈BD
L(V ;α,β) = β>V − g∗(β)− g ( V ∗1 (s) ) + να>V − ν max
x∈W∗ α>x. (7)
Its dual problem can be written as d∗ = maxα,β∈BD D(α,β), where D(α,β) is the dual function defined as D(α,β) = minV ∈V L(V ;α,β). We notice that L(V ;α,β) is convex in V ∈ V and concave in α,β ∈ BD, which implies the strong duality, p∗ = d∗. Hence, dual methods can apply. When α and β are fixed, solving D(α,β) is a planning problem. When the model is known, it suffices to conduct value iteration on the model. However, what we have is a dataset collected a priori in offline RL. Therefore, we develop the offline planning algorithm that is a pessimistic variant of the value iteration (Jin et al., 2020b), which applies penalties to ensure pessimism. We explain why pessimism is crucial 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 ĉ 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 (ξ-uncertainty quantifier). We call {(ΓPh ,Γch)}Hh=1 a ξ-uncertainty quantifier if the following event
E = {∣∣P̂h(s′|s, a)− Ph(s′|s, a)∣∣ ≤ ΓPh (s, a, s′), ∣∣ĉih(s, a)− cih(s, a)∣∣ ≤ Γcih (s, a)
for all (s, a, s′) ∈ S ×A× S, h ∈ [H], i ∈ [D] } (8)
holds with probability at least 1− ξ. Here we write Γch = (Γc 1 h ,Γ c2 h , . . . ,Γ cD h ).
Then, we can construct the empirical counterparts of Ph and Bh by P̂h[V ](s, a) = 〈V (·), P̂h(· | s, a)〉S and B̂h[V ](s, a) = ĉh(s, a) + P̂h[V ](s, a). Note that for any function V : S → [0, H], under the event E , it holds for any (s, a) ∈ S ×A and any h ∈ [H] that∣∣(P̂h − Ph)[V ](s, a)∣∣ = ∣∣∣∣ ∫
S
( P̂h(s′|s, a)− Ph(s′|s, a) ) V (s′) ds′ ∣∣∣∣ ≤ H ∫ S ΓPh (s, a, s ′) ds′.
Therefore, we define Γh(s, a) = H ∫ S Γ P h (s, a, s
′) ds′, which quantifies the uncertainty arising from the transition kernel. We use the ξ-uncertainty quantifier as the penalty function for pessimistic planning, which leads to a conservative estimation of the value function. We formally describe our planning method in Algorithm 1, where θ denotes a projection vector to be specified later. By adding the pessimistic penalty Γh · 1 + Γch to the estimated value, we ensure a conservative estimation. We also truncateQkh and V k h in [0, H − h+ 1]D to improve the estimation.
It remains to solve maxα,β∈BD D(α,β). We utilize the projected subgradient method which produces a sequence of dual variables {αk}Kk=1 and {βk}Kk=1 that approximately solves the dual problem. A detailed description of projected subgradient method is provided in Appendix H.6.2. For a brief description, we update the dual variables via
αk+1 ← ΠBD { αk + ηk(V k − arg max
x∈W∗ (αk)>x)
} ,
βk+1 ← ΠBD { βk + ηk ( V k − ∂g∗(βk) )} .
(9)
where V k ∈ arg minV ∈V L(V ;αk,βk) and ηk is the step length at the k-th iteration. As claimed in Proposition 1, the CMDP is a special case of the CMOMDP. Moreover, we show in Appendix C.2 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, { (ΓPh ,Γ c h) }H h=1
) 2: for step h = H,H − 1, . . . , 1 do 3: Qh(·, ·)← ĉh(·, ·) + P̂h[Vh+1](·, ·) + Γh · 1 + Γch 4: Qh(·, ·)← min { Qh(·, ·), (H − h+ 1) · 1 } + 5: πh(·)← arg mina∈AQh(·, ·) · θ 6: Vh(·)← Dπh [Qh](·) 7: end for 8: return π = {πh}Hh=1,Q = {Qh}Hh=1,V = {Vh}Hh=1 9: end function

heading: 3.2 General CMOMDPs
text: Based on the above analysis, we now develop the Pessimistic Dual Iteration (PEDI) (Algorithm 2) for general CMOMDPs, which is motivated by the dual gradient method in solving the minimax optimization problem. Specifically, PEDI solves D(α,β) via PESSPLANNING (Algorithm 1) and updates dual variables via (9), alternately. The output policy π̂ is a mixed policy executed by randomly selecting a policy πk from {πk}Kk=1 with equal probability beforehand and then exclusively following πk thereafter. Hence, it holds that, for the mixed policy π̂, V π̂1 (s) = 1 K ∑K k=1 V πk
1 (s). Note that the mixed policy may not be a Markov policy (Altman, 1999). However, it would be useful to extend the definition of a policy π = {πh}Hh=1 so as to allow πh to depend not only on h but also on some initial randomizing mechanism. That is, we may have a set of policies U and a distribution q ∈ ∆(U). Then we define the mixed policy of U , πU , as a policy to be executed by first using q 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 π∗. Thus, SubOpt(π̂) remains a reasonable performance metric of our algorithm.
Algorithm 2 Pessimistic Dual Iteration (PEDI).
Input: offline dataset D, step length {ηk}Kk=1, scaling parameter ν Output: the mixed policy π̂ = {π̂h}Hh=1 of {πk}Kk=1
1: randomly initialize dual variables α1,β1 ∈ BD, and set θ1 = να1 + β1 2: construct {ĉh}Hh=1 and {P̂h}Hh=1 based on D 3: construct the ξ-uncertainty quantifier {(ΓPh ,Γch)}Hh=1 based on D 4: for iteration k = 1, 2, . . . ,K do 5: πk,Qk,V k ← PESSPLANNING ( θk,D, { (ΓPh ,Γ c h) }H h=1
) 6: update αk,βk to αk+1,βk+1 via (9) 7: θk+1 ← ναk+1 + βk+1 8: end for

heading: 3.3 Linear kernel CMOMDPs
text: In this section, we study PEDI on settings with linear function approximation such as linear kernel CMOMDPs. To that end, we first introduce the linear kernel CMOMDP, which is a generalization of the linear kernel MDP (Yang and Wang, 2019; Jin et al., 2020a; Cai et al., 2020). Then, we propose an instantiation of Algorithm 2 for linear kernel CMOMDPs.
Definition 2 (Linear kernel CMOMDP). The CMOMDP (S,A, H,P, c) is a linear kernel CMOMDP with a known kernel feature map ψ : S×A×S → Rd1 and a known value feature map ϕ : S×A → Rd2 , if for any h ∈ [H] there exist unknown vectors θh ∈ Rd1 and θc i
h ∈ Rd2 for any i ∈ [D] such that for any (s, a, s′) ∈ S ×A× S ,
Ph(s′ | s, a) = ψ(s, a, s′)>θh, cih(s, a) = ϕ(s, a)>θc i h .
Let d = max{d1, d2}. We assume there exists a constant R > 0 such that
R−2 max s′∈S
( y>ψ(s, a, s′) )2 ≤ ∫ S ( y>ψ(s, a, s′) )2 ds′ ≤ d
for any (s, a) ∈ S ×A and y : ‖y‖2 ≤ 1. Moreover, we assume ‖θh‖2 ≤ √ d and ‖θcih ‖2 ≤ √ d for i ∈ [d].
The existence of constantR naturally holds when ψ(s, a, ·) is upper bounded and Lipschitz continuous for all (s, a) ∈ S×A. Note that the tabular CMOMDP is a special case of the linear kernel CMOMDP with R = 1 (see Appendix G for a 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 ĉ and thereby construct a ξ-uncertainty quantifier.

heading: 4 Theoretical results
text: 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 to 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 Õ(1/ √ N) where N is the number of trajectories in the dataset.

heading: 4.1 Results of general CMOMDPs
text: By using pessimistic planning (Algorithm 1), we ensure a pessimistic policy π̂. We formally state this notion in the following lemma. Lemma 1 (Pessimism). Suppose that Assumptions 1 and 2 hold. By Algorithm 2, under event E defined in (8), for any (s, a) ∈ S × A and h ∈ [H], it holds that V kh (s) ≥ V π k h (s), Q k h(s, a) ≥ Qπ k h (s, a), and dist ( V k1 (s),W∗ ) ≥ dist ( V π k 1 (s),W∗ ) . Furthermore, it holds that
g ( V̂1(s) ) ≥ g ( V π̂1 (s) ) and dist ( V̂1(s),W∗ ) ≥ dist ( V ∗1 (s),W∗ ) ,
where V̂1(s) = 1K ∑K k=1 V k 1 (s) and π̂ is the output of Algorithm 2.
Proof of Lemma 1. See Appendix H.1 for a 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 1 (Suboptimality and constraint violation for general CMOMDPs). Suppose that Assumptions 1 and 2 hold. Under event E defined in (8), for the output policy π̂ of Algorithm 2, when we set ν = ρ and ηk = 2G−1 √ D/k (or 2G−1 √ D/K if K is predefined), where G = 2(1 + ν)H √ D, it holds that
SubOpt(π̂) ≤ K + IntUncertπ ∗ D , Violation(π̂) ≤ 2
ρ ( K + IntUncert
π∗ D ), (10)
where we let C denote an absolute constant and define
K = C(1+ρ)
√ DH2
K , IntUncertπ
∗ D = 2(1 + ρ) √ D H∑ h=1 Eπ∗ [ Γh(sh, ah)+‖Γch(sh, ah)‖∞ | s1 = s ] .
Proof of Theorem 1. See Appendix H.2 for a detailed proof. Here we provide a proof sketch, which consists of two steps.
First step: upper bounding SubOpt(π̂) + ν Violation(π̂), which is our objective (4). Here π̂ is the output of PEDI (Algorithm 2). By pessimism, we have SubOpt(π̂) + ν Violation(π̂) ≤
g(V̂ 1(s))− g (V ∗1(s)) + ν dist(V̂ 1(s),W∗) where V̂ 1(s) = 1K ∑K k=1 V k 1(s). We do linearization via convex conjugate (6) and then get
SubOpt(π̂) + ν Violation(π̂) ≤K−1 max ‖β‖≤1
{ β ·
K∑ k=1 V k1(s)− K∑ k=1 g∗(β) } − g (V ∗1(s))
+K−1ν max ‖α‖≤1
{ α ·
K∑ k=1 V k1(s)− K∑ k=1 max x∈W∗ α · x
} .
Recall that PEDI uses the projected subgradient method, which approximates the max operator above by a sequence of variables at the expense of a sublinear approximation error, which leads to
SubOpt(π̂) + ν Violation(π̂) ≤K−1 K∑ k=1 {( βk )> V k1(s)− g∗ ( βk )} − g (V ∗1(s))
+K−1ν K∑ k=1 {( αk )> V k1(s)− max x∈W∗ ( αk )> x } + C(1 + ν) √ DH2/K,
where C is a constant. We rearrange the right-hand side above with some tricks and then obtain
SubOpt(π̂) + ν Violation(π̂) ≤ K−1 K∑ k=1 [( θk )> ( V k1(s)− V ∗ 1(s) )] + C(1 + ν) √ DH2/K.
The last term in the right hand side above is exactly K . Intuitively, the term (θk)>(V k1(s) − V ∗1(s)) indicates the projected difference of state-value functions along θ, which motivates the PESSPLANNING (Algorithm 1). We apply results from this pessimistic approach and then conclude
SubOpt(π̂)+ν Violation(π̂) = g ( V π̂1 (s) ) −g ( V ∗1(s) ) +ν dist ( V π̂1 (s),W∗ ) ≤ K+IntUncertπ ∗ D .
Second step: upper bounding SubOpt(π̂) and Violation(π̂) individually. This is done by two facts: (i) dist (·, ·) ≥ 0, and (ii) g(V π̂1 (s))− g (V ∗ 1(s)) ≥ −ν dist(V π̂ 1 (s),V ∗ 1(s))/2. We plug them into the resulting inequality in the first step and then complete the proof.
As shown in Theorem 1, our pessimistic algorithm bounds the suboptimality and constraint violation from above by the sum of the optimization error K ∈ O(1/ √ K) and the intrinsic uncertainty IntUncertπ ∗
D . The optimization error K vanishes as K goes into infinity. Later, we will show that the intrinsic uncertainty, IntUncertπ ∗
D , is impossible to eliminate through an analysis of PEDI on linear kernel CMOMDPs in Section 4.2.

heading: 4.2 Results of linear kernel CMOMDPs
text: 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 λ = 1 and κ = CR √ d log(dN) + log(DH/ξ) where C > 0 is an absolute constant. Then, under Assumptions 1 and 2, {ΓPh ,Γrh}Hh=1 defined in (24) (Appendix E) is a ξ-uncertainty quantifier. Hence, under the same settings of ν and ηk in Theorem 1, (10) holds with probability at least 1− ξ for the output π̂, and the intrinsic uncertainty is specified to
IntUncertπ ∗ D = 2(1 + ρ) √ D H∑ h=1 Eπ∗ [ H ∫ S κ·‖ψ(sh, ah, s′)‖Λ−1h ds ′+κ·‖ϕ(sh, ah)‖Λ−1ϕ,h |s1 = s ] .
Proof of Theorem 2. 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(1/ √ N) where N is the number of trajectories in the dataset.
Corollary 1 (Dataset with sufficient coverage). Suppose that the τ -th trajectory {
(sτh, a τ h, c τ h) }H h=1
of the dataset D is generated by a behavior policy πb,τ for τ ∈ [N ]. Meanwhile, we assume that there exists a constant ς > 0 such that µ∗h(s, a)/µ b,τ h (s, a) ≤ ς for any h ∈ [H], τ ∈ [N ], and (s, a) ∈ S ×A. Here {µ∗h}Hh=1 and {µ b,τ h }Hh=1 are the visitation measures of π∗ and πb,τ . Then, we have with probability at least 1− ξ that
IntUncertπ ∗ D ∈ Õ ( Cςκ(1 + ρ)H2 √ d|S|/N ) .
Proof of Corollary 1. See Appendix H.5 for a detailed proof.
Here |S| denotes a certain measure on S. For instance, when S = [0, 1] and we take the Lebesgue measure, we have |S| = 1. Note that Corollary 1 holds under a weaker condition than the uniform coverage (Wang et al., 2020a; Rashidinejad et al., 2021), where the condition is maxπ µπ/µb ≤ C for a certain constant C. However, our algorithm is still able to achieve the intrinsic uncertainty of Õ( √
1/N). In particular, our condition, µ∗/µb ≤ ς , can hold when we have expert demonstration in the dataset D (Buckman et al., 2020). In Theorem 2, we notice that when the number of iteration K goes into infinity, the optimization error K vanishes, and the suboptimality and constraint violation are bounded from above by the intrinsic uncertainty IntUncertπ ∗
D only. However, this is the best effort that we can put. The following theorem indicates that the term IntUncertπ ∗
D is impossible to eliminate since it arises from the information-theoretic lower bound.
Theorem 3 (Information-theoretic lower bound). For the output π̂ of any algorithm of offline CMOMDPs, there exists a linear kernel CMOMDPM with initial state s ∈ S and a dataset D compliant withM, such that
ED  SubOpt(π̂)∑H h=1 Eπ∗ [ ‖ϕ(sh, ah)‖Λ−1ϕ,h + |S| −1 ∫ S ‖ψ(sh, ah, s′)‖Λ−1h ds ′ ∣∣∣ s1 = s]  ≥ c, where the expectation is taken with respect to the data collecting process, and c > 0 is an absolute constant.
Proof of Theorem 3. See Appendix H.4 for a detailed proof.
By Theorem 2 and Theorem 3, we find that the upper bound of suboptimality of Algorithm 2 for linear kernel CMOMDP matches the information-theoretic lower bound up to the optimization error O(1/ √ K) and some multiplicative factors of horizons, dimensions, and geometric properties of the target set, which means that PEDI is near-optimal for linear kernel CMOMDP.

heading: 5 Experimental Results
text: We also conduct numerical experiments to verify our theory. Please see Appendix I for details. The results show that the proposed algorithm is not only provably efficient but also applicable.

heading: 6 Conclusion
text: In this paper, we propose a general algorithm, Pessimistic Dual Iteration (PEDI), for constrained multiobjective reinforcement learning with offline data. We show our algorithm delivers a 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 up to the optimization error and multiplicative factors of constants related to the CMOMDP. When the trajectories of optimal policy are sufficiently covered, the intrinsic uncertainty is proved to be Õ(1/ √ N) where N is the number of trajectories in the dataset.
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).

Review summaries:
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.

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.  

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.

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.