Safe and Efficient: A Primal-Dual Method for Offline Convex CMDPs under Partial Data Coverage

Authors: haobo  zhang
xiyue  peng
honghao  wei
xin  liu
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 13:10:44

Abstract: Offline safe reinforcement learning (RL) aims to find an optimal policy using a pre-collected dataset when data collection is impractical or risky. We propose a novel linear programming (LP) based primal-dual algorithm for convex MDPs that incorporates ``uncertainty'' parameters to improve data efficiency while requiring only partial data coverage assumption. Our theoretical results achieve a sample complexity of $\mathcal{O}(1/(1-\gamma)\sqrt{n})$ under general function approximation, improving the current state-of-the-art by a factor of $1/(1-\gamma)$, where $n$ is the number of data samples in an offline dataset, and $\gamma$ is the discount factor. The numerical experiments validate our theoretical findings, demonstrating the practical efficacy of our approach in achieving improved safety and learning efficiency in safe offline settings.

Main paper: 
 introduction: 
 Safe reinforcement learning (RL) aims to learn a reward-maximizing policy while satisfying multiple safety constraints, demonstrating its practicality in many real-world applications, such as autonomous driving [Kiran et al., 2021] , robotics [Levine et al., 2016] , and healthcare [Yu et al., 2021] . In these tasks, certain behaviors may potentially harm the agent or its surroundings, which is crucial for task completion. One way to mathematically characterize safe RL is through Constrained Markov Decision Processes (CMDPs) [Altman, 2021] , where safety constraints are incorporated into the problem when optimizing the objective.Offline RL aims to learn a sequence of actions from a pre-collected dataset to address scenarios where interacting with the environment is risky, expensive, or impractical. Ensuring sample efficiency in offline RL with function approximation typically requires additional assumptions about both the function classes and the dataset due to training instability and distribution shift issues [Fujimoto et al., 2019 , Kostrikov et al., 2021 , Paine et al., 2020] . Earlier studies [Chen and Jiang, 2019 , Liao et al., 2022 , Liu et al., 2019 , Wang et al., 2019 , Zhang et al., 2020b] in offline RL usually require that all functions in the function space are Bellman-complete and that the dataset has full coverage, meaning it covers the state-action distributions induced by all policies. This might be a mild and accepted assumption in offline RL without considering safety. However, it is highly unacceptable and impractical in safe offline RL, as it would require the dataset to cover all hazardous state-action pairs induced by all dangerous policies. To address the full coverage issue, later works [Chen and Jiang, 2022 , Rashidinejad et al., 2021 , Uehara and Sun, 2021 , Xie et al., 2021 , Zhan et al., 2022, Zhu et al. ,1 (1-γ) 2 √ n Ours Yes Partial General O 1 (1-γ) √ n2023] reduce the assumption to single-policy coverage by using pessimism in the face of uncertainty.Unfortunately, all existing studies [Chen et al., 2022 , Hong et al., 2024 , Le et al., 2019] in safe offline RL still require coverage for all policies.Beyond traditional offline safe RL, many applications do not fit the standard RL problem [Abel et al., 2021] . There is a substantial body of literature [Geist et al., 2022 , Mutti et al., 2023 , Zahavy et al., 2021] studying a more general scenario called convex MDPs, where the objective function is modeled as a convex (or concave) utility function instead of linear, as in the standard RL problem. This framework is quite general and captures various learning scenarios, including imitation [Abbeel and Ng, 2004] , exploration [Hazan et al., 2019] , and more. However, studying convex MDPs introduces additional challenges. In convex MDPs, moving beyond cumulative rewards means that the Bellman equation fails to hold due to the lack of reward additivity. This leads to breakdowns in many techniques based on Dynamic Programming (DP) [Zhang et al., 2020b] . Despite a large body of practical literature [Lee et al., 2021 , Xu et al., 2022 , Zheng et al., 2023] , robust theoretical analysis remains lacking in this setting.Figure 1 : Performance of our algorithm on FrozenLake with completely random data.To address the coverage issue and extend the general function approximation setting, we focus on convex MDPs in the safe offline setting. Our main contributions are summarized below (the detailed comparisons can be found in Table 1 ):• We are the first to study offline convex MDPs under safety constraints with partial data coverage assumption.We reformulate the problem using marginalized importance weights to avoid issues caused by the Bellman equation's failure in convex MDPs.• We analyze the convergence rate of our proposed approach under partial coverage assumption and theoretically prove that our algorithm achieves O1 (1-γ) √n in both objective and violation bounds with general function approximation, when the number of iteration is larger than n. The sample complexity of O 1 (1-γ) √ n improves the best existing result by a factor of 1/(1γ)2 .• Experimental results on Imitation Learning and standard CMDPs demonstrate the generality and effectiveness of our algorithm. As Figure 1 shows our algorithm performs well even with a completely random and safety-violated offline dataset with general function approximation, which verifies our theoretical findings.Offline Safe RL: The offline safe reinforcement learning setting entails the agent learning from a fixed dataset while adhering to safety constraints. This involves a blend of offline RL and safe RL, yet research on this approach, particularly concerning theoretical analysis, remains limited. BCQL augmented by BCQ [Fujimoto et al., 2019] optimizes the policy in the offline phase and applies the Lagrange method to handle constraints. CPQ [Xu et al., 2022] tackles the safety constraints by overestimating the cost value function of out-of-distribution ('unsafe') actions and updating the reward value function with 'safe' actions. Another line of work [Lee et al., 2021] using DICE-style technique optimizes policy by calculating the stationary distribution of state-action pairs instead of value function and extracts the policy by importance-sample behavior cloning. CDT [Liu et al., 2023b] combines Decision Transformer with safety constraints and utilizes data augmentation based on Pareto frontiers to enhance the safety and adaptability of the Transformer. It also focuses on the model's capability to different cost thresholds. The work [Le et al., 2019] proposes a meta-algorithm, using Fitted Q Evaluation and Fitted Q Iteration as subroutines to evaluate safety constraints and learn policy respectively. [Chen et al., 2022] analyzes the information-theoretic sample complexity lower bound and proposes a near-optimal primal-dual learning algorithm under partial data coverage but without function approximation. The most related work [Hong et al., 2024] approaches the problem from the perspective of the Actor-Critic algorithm, analyzing the sample complexity to be O(1 (1-γ) 2 √n ) under Slater's condition and full data coverage assumption. Convex MDP: Convex MDP problem extends the scope of MDP by focusing on convex objective functions of stationary distribution, rather than an inner product between reward and stationary distribution. To address the challenge, [Zhang et al., 2020b] introduces a variational Monte Carlo gradient estimation algorithm, demonstrating convergence to the optimal policy across general utility functions. The work [Zahavy et al., 2021] utilizes Fenchel duality to cast convex MDPs as min-max "two-player" games, proposing a meta-algorithm that addresses various convex MDPs through distinct subroutines. The work [Geist et al., 2022] approaches convex MDPs from the Mean-Field Game (MFG) perspective, establishing the equivalence between the optimal condition in convex MDPs and Nash equilibrium in MFGs. [Ying et al., 2023] studies the convex CMDP problem through a policy-based primal-dual algorithm and proves an O T -1/3 convergence rate in both optimality gap and constraint violation. The existing literature on convex MDPs primarily focuses on the online setting, while this paper specifically targets the offline scenario. 
convex cmdp problem: 
 We study a discounted constrained Markov decision process (CMDP), denoted by M = (S, A, R, C, T, γ, µ 0 ), where S is the state space (a finite set), A is the action space (a finite set), R : S × A → [0, 1] and C : S × A → [0, 1] are reward and cost functions, respectively, T : S × A → ∆(S) is the transition probability kernel, where ∆(•) denotes the probability simplex, γ ∈ [0, 1) denotes the discount factor, and µ 0 ∈ ∆(S) is the initial state distribution. We define a policy π : S → ∆(A) as a probability mapping from states to actions. At time slot t, the agent observes state s t and takes action a t according to the policy π. For a policy π, we define its discounted state-action occupancy measure d π as followsd π (s, a) = (1 -γ) ∞ t=0 γ t P π (s t = s, a t = a) , ∀s ∈ S, a ∈ A,where P π (s t , a t ) is the probability of state-action pair (s, a) being visited at time slot t under the policy π. Further, we let d π (s) = a∈A d π (s, a) be the discounted state occupancy measure.Given the occupancy measure above, we can formulate the following convex CMDP problemEQUATIONwhere f and g are both convex functions, and τ is the cost threshold. We present a single safety constraint for simple exposition, and our result can be readily generalized to the setting with multiple constraints. The set K is a probability simplex that satisfies global balance equations of the underlying Markov processK = {d | a d(s, a) = (1 -γ) µ 0 (s) + s ′ ,a ′ T (s | s ′ , a ′ ) d (s ′ , a ′ ) , ∀s ∈ S}.This set can also be written as a compact matrix form thatEQUATIONwhere1 |A| = [1, 1, • • • , 1] ⊤ ∈ R |A| and P ∈ R |S|×|S||A| is the transition probability matrix.The convex CMDP problem in (1) is quite general to capture various learning scenarios, including apprenticeship learning [Abbeel and Ng, 2004] , standard CMDPs [Altman, 2021] , pure exploration [Hazan et al., 2019] , and inverse reinforcement learning in contextual MDPs [Belogolovsky et al., 2021] . Take the standard CMDP as an example, the agent aims to find a policy that maximizes cumulative reward while satisfying the safety constraints [Altman, 2021] , which can be written asEQUATIONwhere f and g are linear functions w.r.t. the state-action occupancy measure.Take safety-aware apprenticeship learning [Zhou and Li, 2018] for another example, the agent aims to mimic the expert's demonstrations while avoiding the unsafe states in H, which can be written asEQUATION)where d e represents the empirical distribution of the expert's demonstration and F (•, •) is the convex distance function, such as KL-divergence or total variation distance [Zhang et al., 2020a] .However, solving these problems in the online setting can be time-consuming, costly, and potentially dangerous in safety-critical contexts. In contrast, by leveraging historical data, offline RL offers a promising avenue for developing safe and effective algorithms, as introduced next.In offline RL, we cannot interact with the environment and only have access to dataset with a finite number of samples. Let D = (s i , a i , r i , c i ) n i=1 be a collected offline dataset where we assume all the pairs (s i , a i ) n i=1 are generated independently and identically distributed (i.i.d.) from data distribution µ(s, a) induced by a behavior policy π µ . Let n D (s, a) represents the number of occurrences of the state-action pair (s, a) in the offline dataset D, then µ D (s, a) = n D (s, a)/n is an empirical version of µ(s, a). In offline RL, a major challenge is distribution shift, which measures the mismatch between data distribution and occupancy measure induced by candidate policies. To quantify the distribution shift, we make the following π * concentrability assumption that refers to partial data coverage, Assumption 1 (π * -concentrability). Let π * be the optimal policy to problem (1), there exists constant C π * > 0 such that d π * (s, a)/µ(s, a) ≤ C π * , for all s ∈ S, a ∈ A.This assumption controls the distribution shift between offline data distribution µ and the occupancy measure d π * induced by optimal policy π * . Specifically, the partial data coverage assumption indicates the offline dataset D should cover state-action pairs visited by the optimal policy π * . Unlike the common full data coverage assumption in previous works that the dataset D should encompass data visited by all policies [Chen and Jiang, 2019 , Hong et al., 2024 , Le et al., 2019] , our assumption is considerably more relaxed. Furthermore, in the field of safe RL, partial coverage assumption also offers significant advantages, as the full coverage implies the behavior policy needs to visit every dangerous state and action space, which is obviously impractical.Beyond using assumptions to limit distribution shift in offline RL, we consider Marginalized Importance Weight (MIW), a method widely used in the existing literature [Hong et al., 2024 , Ozdaglar et al., 2023 , Zhan et al., 2022] , to further address this challenge. Definition 1 (Marginalized Importance Weight). Given a policy π, let d be the occupancy measure induced by π. We define marginalized importance weight w : S × A → R + as w(s, a) = d (s,a) µ(s,a) , ∀s ∈ S, a ∈ A.Note w can be regarded as the density ratio between the normalized discounted occupancy measure and data distribution. Moreover, recall the definition of w and M in equation (2) , we define matrixK ∈ R |S|×|S||A| and K D ∈ R |S|×|S||A| as K(s ′ , (s, a)) = M (s ′ , (s, a)) • µ(s, a), K D (s ′ , (s, a)) = M (s ′ , (s, a)) • µ D (s, a),where K D can be seen as an empirical version of K in dataset D and it is straightforward to verify Kw = M d. With these notations, we establish an equivalent formulation with problem (1) w.r.t.w≥0 f (µ • w) (5) s.t. Kw = (1 -γ)µ 0 (6) g(µ • w) ≤ τ (7)where the operator "•" denotes the element-wise product of vectors. As we aim to establish the sample-efficient learning algorithms in large state-action spaces, we regard the importance weight w as a function, i.e. w : S × A → R + that belongs to the convex function class W in the following assumption.Assumption 2 (Realizability). We assume w * ∈ W where w * is the optimal solution to the problem (5)-( 7).This assumption assumes the optimal solution w * (π * ) can be realizable for a convex function class W. Note that the assumption of the convex function class W is reasonable and standard, which is also achievable with the convexification process in case the function class is non-convex. The convexification process is a common practice in the offline safe RL literature, particularly in the context of general function approximation [Le et al., 2019 , Hong et al., 2024] . Now we consider W as a discrete function class for simplicity and it readily extends to continuous settings (in Remark 1). Further, we introduce a completeness assumption that is used to relax the key constraint in (6).Assumption 3 (Completeness). Let x w be within the function class X . Define a mapping ϕ: such that ϕ(w)⊤ (Kw -(1 -γ)µ 0 ) = x ⊤ w (Kw -(1 -γ)µ 0 ) = ∥Kw -(1 -γ)µ 0 ∥ 1 .Then, we have (W, X )-completeness under the mapping ϕ, i.e. x w ∈ X for all w ∈ W.Intuitively, the completeness assumption allows us to replace the computation of the l 1 -norm with a linear product and simplifies our subsequent analysis. Next, we introduce the standard boundness assumption in offline RL literature with general function approximation [Chen and Jiang, 2019 , 2022 , Le et al., 2019 , Munos and Szepesvári, 2008] .Assumption 4 (Boundness of W and X ). We assume function classes W and X are bounded, i.e. ∥w∥ ∞ ≤ B w , ∀w ∈ W and ∥x w ∥ ∞ ≤ B w , ∀x w ∈ X .Combining this assumption with Assumption 1 implies B w ≥ C π * . Lastly, we impose a mild assumption for the reward and cost functions in the problem (1).Assumption 5 (Lipschitz condition). The functions f (x) and g(x) are convex and satisfy the Lipschitz condition, where there exist constants L f and L g such that for any x, y, the following inequalities hold|f (x) -f (y)| ≤ L f ∥x -y∥ and |g(x) -g(y)| ≤ L g ∥x -y∥. 
algorithm design and main results: 
 Despite the practical importance of offline safe RL in real-world applications, there is still a lack of theoretical research on this topic. The earlier literature on this setting often lacks robust theoretical analysis [Lee et al., 2021 , Liu et al., 2023b , Xu et al., 2022] , and articles with theoretical analysis either yield unsatisfactory results or rely on strong assumptions [Chen et al., 2022 , Hong et al., 2024 , Le et al., 2019] .In this section, we propose a provable algorithmic framework and establish the first theoretical result in offline convex CMDP, to the best of our knowledge. Moreover, when reducing to standard offline CMDP, we achieve a sample complexity of O1 (1-γ) √ nwith general function approximation, which improves the current state-of-the-art result by a factor of 1/(1γ).Inspired by [Ozdaglar et al., 2023] , we first introduce an empirical version of problem ( 5)-( 7) in the offline setting by incorporating a suitable relaxed parameter into the safety constraint. Intuitively, the empirical version of the problem is "close" to the original problem when the dataset is large. This is the key observation for analyzing the convergence performance and safety violations. To solve ( 5)-( 7), we present its empirical and relaxed problem:EQUATIONwhere µ D and K D are the empirical version of µ and K, respectively; ζ and κ are the relaxed hyperparameters for the validity constraint (Bellman equation) and safety constraint. Intuitively, the parameters of ζ and κ capture the "uncertainty" induced by the offline dataset D in terms of distribution shift and safety concerns. The values of these parameters will be specified later and play an important role in our analysis. Next, we demonstrate that the mismatch of the objective and constraint violation bound depends on the "uncertainty", which exhibitsO(1/ √ n) distance.Note that all parameters in the optimization problem ( 8)-( 10) can be determined from the offline dataset. When the state-action space is not large, this problem can be efficiently solved by convex optimization solvers. However, when the state-action space is large, and the function approximation is necessary (e.g., w is parameterized by a neural network), it would be quite challenging (if not impossible) to solve this problem. To address this challenge, we propose a primal-dual algorithm that is sample-efficient and computationally tractable to solve the problem iteratively. We first introduce the Lagrange function of problem ( 8)-( 10),EQUATIONwhere λ and ϕ are Lagrange multipliers.Algorithm 1: Primal-dual algorithm for Offline Convex CMDP (POCC)Input: Dataset D = {(s i , a i , r i , c i )} n i=1, the relaxed parameters κ, ζ, and the step size η = 1 √ K ; Initialization: Choose any w 1 ∈ W and the Lagrangian multipliersλ 1 = 0, ϕ 1 = 0; for k = 1, 2, . . . , K do Primal: w k+1 = P W w k -η∇L w (w k , λ k , ϕ k ) , Dual: ϕ k+1 = τ k -η∇L ϕ (w k , λ k , ϕ k ) ϕ k+1 max 0 , λ k+1 = λ k -η∇L λ (w k , λ k , ϕ k ) λ k+1 max 0, where P W is the projection onto set W and [•] h l is the projection onto interval [l, h]. Compute the average w K = K i=1 w i ; Extract the policy π K with formula (12); Output: Policy π K ;Given the Lagrange function above, we introduce our algorithm called POCC (in Algorithm 1), which takes the offline dataset D as input and runs a primal-dual method on the estimated Lagrange function. Specifically, at each iteration k, POCC updates the importance weight by gradient descent and projects it back to function class W, then updates Lagrange multipliers of validity constraint (6) and safety constraint (7) respectively. After K steps, POCC returns an averaged w K , we can extract the corresponding policy π K based on the offline dataset D as followsπ K (a | s) := w K (s,a)πµ(a|s) a ′ ∈A w K (s,a ′ )πµ(a ′ |s) , if a ′ ∈A w K (s, a ′ )π µ (a ′ | s) > 0 1 |A| , if a ′ ∈A w K (s, a ′ )π µ (a ′ | s) = 0 (12)where the second equality means that if a ′ ∈A w K (s, a ′ )π µ (a ′ | s) = 0 we randomly choose an action for state s.We present the theoretical results of our proposed approach in the following theorem.Theorem 1 (Sample complexity of π K ). Suppose Assumptions 1-7 hold. Denote π K as the corresponding policy induced by w K . Set the relaxed parametersζ = 2 √ 2Bw √ n log |W||X | δ and κ = √ 2LgBw √ n log 2|W| δ , and the step size η = 1 √ K . Let the constants υ = 1 1-γ (4B + 4L + 2ε) and ι = 1 1-γ B 2 + 4B + 4L + L 2 √ K + ε , we have, with at least 1 -8δ probability, J r (π K ) -J r (π * ) ≤ 6L f B w 2 log(|W||X |/δ) (1 -γ) √ n + ι 2 √ K (13) J c (π K ) -τ ≤ 6L g B w 2 log(2|W||X |/δ) (1 -γ) √ n + υ √ K (14) where J r (π K ) = f (d K ) and J c (π K ) = g(d K) are objective and constraint performance of policy π respectively, B represents the distance between initial value w 1 of the iteration and optimal solution w D to problem (8)-( 10), ε ≥ 0 is a constant, L is the max Lipschitz constant of Lagrange function and K is the number of iterations.Remark 1. We remark that Theorem 1 remains valid even when the function class W is a continuous set. In this case, the cardinality |W| can be replaced with the covering number of W, and the union bound can be applied to its ϵ-covering set. This adjustment also preserves the sample complexity order of O(1/ √ n), up to a constant dependent on ϵ. For further details on the extension from discrete W to a continuous set, please refer to [Le et al., 2019, Xie and Jiang, 2021] .Theorem 1 demonstrates that the convergence performance of our algorithm can be divided into two parts:O(1/ √ n) + O(1/ √ K).Regarding the first term, except for the size of dataset, it mainly depends on the function class (searching space) log |W||X | and relaxed parameters ζ and κ that capture the "uncertainty" for addressing the distribution shift and safety concern. Moreover, the second term O(1/ √ K) connects with the error bound between w K and optimal solution w D , which decays at the rate of 1/ √ K when the number of iterations increases. It is worth noting that the convergence rate of policy π K is still O(1/ √ n) when the iterative number is sufficient to satisfy K ≥ n. The algorithm is gradient-based and does not involve additional computations for solving the optimization problem ( 8)-( 10). This suggests that we can improve the convergence performance w.r.t. K by employing more advanced primal-dual techniques to reduce the convergence rate of the second term, such as those discussed in [Yu and Neely, 2017] with a convergence rate of O(1/K).Unlike most of the previous work focuses on convex MDPs in online setting [Bai et al., 2023 , Ying et al., 2023 , Zahavy et al., 2021 , Zhang et al., 2020b] , Theorem 1 to the best of our knowledge, is the first provable result in offline convex MDPs. Moreover, compared to the best result O1 (1-γ) 2 √ nin offline CMDP [Hong et al., 2024 , Chen et al., 2022] , our results achieve a sample complexity of O1 (1-γ) √n , which outperform the state-of-the-art by a factor of 1/(1γ). Besides, our algorithm is appropriate in the scenario with large-scale state-action space due to the general function approximation for w while the work [Chen et al., 2022] targets the tabular setting; our result is more favorable in the safety applications compared to [Hong et al., 2024] because we replace the realizability of value function ν with a slightly stronger completeness assumption but reduce the data coverage from full to partial. As stated in Assumption 1, the full data coverage not only implies access to a highly exploratory dataset but also is impractical for offline safe RL, as it assumes behavior policy needs to visit every dangerous state-action pair. Finally, we want to comment that the previous work all focuses on the standard RL, whose objective function is linear, while our algorithm is general enough to tackle the convex MDPs. Remark 2. In the theorem, we assume prior knowledge of the behavior policy π µ for the sake of exposition. However, in practice, it is often challenging to know the behavior policy in advance, as we typically only have access to the offline dataset. The most popular approach to tackle this challenge is behavior clone. It posits that πµ can be estimated as πµ (a|s) = n(s,a) n(s) , where n(s, a) denotes the number of the occurrences of the state-action pair (s, a) in the offline dataset. We employed this estimation method in the experiments and results demonstrate its effectiveness. 
theoretical analysis: 
 In this section, we present a sketch of the proof of Theorem 1. We focus on illustrating the analysis of the constraint violation, and the convergence of the objective follows similar steps. The detailed proof can be found in Appendix A.We first decompose the bound into different major terms and then sutdy them individuallyJ c (π K ) -τ = g(d π K ) -τ (15) = g(d π K ) -g(d K ) I + g(µ • w K ) -g(µ D • w K ) II + g(µ D • w K ) -τ III (16)The first equality holds due to the definition: J c (π K ) = g(d π K ),(d K ) = g(µ • w K ).It is worth noting that the decomposition is intuitive since terms I and II relates to the idea of constructing "uncertainty" parameter for the offline dataset and term III mainly depends on the convergence of primal-dual method.Specifically, term I is the distance between g(d K ) and g(d π K ). It represents the error that we rectify the unnormalized occupancy measure d K , which violates the validity constraint (6), to a satisfying one d π K . The term II illustrates the error incurred when applying the calculated w K from offline dataset D to the real environment µ, which depends on the sample size of the dataset. The term III is related to the relaxed parameter κ in safety constraint ( 7) and the distance between returned w K and optimal solution w D . Next, we present the following lemmas to bound these terms. Lemma 1. Suppose Assumptions 1-4 hold, we have, with probability at least 1 -2δ,J c (π K ) -g(d K ) ≤ 4L g B w 2 log(|W||X |/δ) (1 -γ) √ n .Lemma 2. Suppose Assumptions 1-4 hold. For w K ∈ W, we have, with probability at least 1δ,g(µ • w K ) -g(µ D • w K ) ≤ √ 2L g B w √ n log 2|W| δ .Lemma 3. Suppose Assumptions 1-7 hold. For w K ∈ W, we haveg(µ D • w K ) -τ ≤ κ + υ √ K .Combining the above lemmas, we have, with at least 1 -3δ probability,J c (π K ) -τ = g(d π K ) -g(d K ) I + g(µ • w K ) -g(µ D • w K ) II + g(µ D • w K ) -τ III ≤ 4L g B w 2 log(|W||X |/δ) (1 -γ) √ n + 2 √ 2L g B w √ n log 2|W| δ + υ √ K ≤ 6 √ 2L g B w 2 log(2|W||X |/δ) (1 -γ) √ n + υ √ K .wherewe set ζ = 2 √ 2Bw √ n log |W||X | δ , κ = √ 2LgBw √ n log 2|W| δ . 
experiments: 
 This section aims to justify the effectiveness of our proposed framework through numerical experiments. We test a practical version of Algorithm 1, where we replace the gradient-type update with the "Adam"-type update (the detailed algorithm can be found in Algorithm 2 in the appendix). We test our algorithm to two specific offline convex CMDPs: 1) Safe imitation learning and 2) standard offline CMDP. Our objective is to address the following questions: (i) Are the experimental results consistent with our theory? (ii) how does the data quality affect the performance of our algorithm?The additional details can be found in the Appendix B.To showcase the generality of our algorithm, we choose imitation learning as a user case of convex MDPs and conduct the experiments in a maze environment. We design the environment, as illustrated in Figure 2 , modified from [Geist et al., 2022] . The problem of (safe) imitation learning can be formulated asF (d) = KL(d || d E ), where d E represents the stationary distribution of an expert. The environment is deterministic; agent has four actions (left, down, right, up); moving towards the wall (white) and the boundary does not change the state; the goal is to learn from the expert demonstrations (yellow) under safety constraints.We collect data by expert demonstrations in (a) but randomly remove 25% states. We intend for the algorithm to learn to fill in the gaps using its inherent properties and function approximation, as emphasized in our theory. We are presenting two sets of results: one that considers safety constraints with a cost threshold of 0, and another that does not consider safety constraints. It's important to note that we cannot simply take the stationary distribution of the dataset as our final result. This is due to several reasons, including the fact that expert demonstrations are incomplete (25% of states are removed), simple replacement leads to poor results, and it's not suitable when considering the safety of the agents. Our results are presented in Figure 2 . In Figure ( 2b), it is demonstrated that our policy can accurately replicate the expert distribution using function approximation and completely bridge the gap required by the expert. Additionally, when taking into account the safety constraints, which involve setting the cost in the entire top-right corners, it is evident that our policy avoids states with cost and behaves appropriately, aligning with our theoretical framework.We consider an 8x8 grid world environment FrozenLake, with the initial state being the top-left grid.The agent has four actions: N (north), S (south), E (east), and W (west). The primary objective is to reach the goal while avoiding all holes. The game terminates if the agent achieves the goal within 25 steps. A reward of 1 is obtained when the agent achieves the goal, and the main cost function assigns a cost of 1 if the agent falls into a hole and 0 otherwise. The diagram of the environment has been presented in Figure 1 in the introduction.Initially, we simulate a mixture of different percentages of optimal and uniform policies to collect the offline dataset. We employ various behavior policies π D , running 200 trajectories to collect the offline dataset D, with each trajectory having a maximum of 50 time steps to ensure that the optimal goal is included in the dataset.Additionally, we increase the difficulty of the environment compared to classical FrozenLake, such that if the agent falls into a hole, it can also come out in the next step. This implies that our cost constraint influences the training. We set the cost threshold as 0 here, which means that the agent is not supposed to incur any cost. Note that a higher percentage with a uniform policy indicates that the problem becomes more difficult. We set the discount factor as γ = 0.99, ζ = 0.1, and κ in our algorithm. Furthermore, we encode the environment with one-hot encoding and employ a more practical algorithm. We refer to w as a single hidden-layer neural network which we describe in Algorithm 2 in Appendix B. We set the learning rate of 10 -5 for w and 10 -4 for Lagrange multipliers.In remark (), we have stated that there are two approaches when facing with the scenario that the behavior policy is unknown, and here we choose to use the behavior clone method that we will estimate the behavior policy through the offline dataset. We compare our algorithm with COptiDICE [Lee et al., 2021] , which is a well-acknowledged baseline algorithm in the offline safe RL literature [Hong et al., 2024 , Liu et al., 2023b] . Denote p as the percentage of optimal policy within the behavior policy. We evaluate the algorithm with different behavior policies p = {0.75, 0.5, 0.25, 0} and dataset sizes. We present the results in Figure 3 . In the first two figures, it can be seen that our algorithm can consistently find the optimal path even with completely random data. Conversely, COptiDICE behaves well when the proportion of optimal policy is 0.75, but cannot even learn a logical and safe policy when the majority of the data in dataset is random and constraint violated. In the last two figures, we test the performance of algorithms in different sizes of dataset, where p = 0.5 in behavior policy. The results demonstrate that our algorithm can find a safe and optimal path as the dataset size increases. In contrast, the results from the COptiDICE algorithm show high variance, where it can only find a safe path in about 50% runs.In summary, our algorithm performs well across various behavior policies and dataset sizes, which is consistent with our theoretical results and assumptions. 
conclusions: 
 In this work, we consider convex CMDPs in the offline setting. We propose a sample efficient RL approach that addresses the challenges in offline convex CMDPs. We theoretically prove that we can suffer O(1/ √ n) sample complexity in both performance and violation bound with general function approximation under mild data coverage assumption, which is the first result in offline convex MDPs as best of our knowledge and surpasses the state-of-the-art result in offline safe RL by a factor of 1/(1γ). Experimental studies further demonstrate the effectiveness and generality of our framework. g(µ D • w) -τ ≤ κ We set t = √ 2Bw √ n log 2|W| δ .Combine with the Hoeffding inequality, we haveEQUATIONFor the constraint function, recall we suppose that it satisfies the Lipschitz condition,|g(µ D • w) -g(µ • w)| ≤ L g ∥µ D • w -µ • w∥Before proceeding to the following derivation, we first state a fact:P (z ≥ t) ≤ δ and y ≤ z =⇒ P (y ≥ t) ≤ δThe above equation means that if a variable z is greater than t with probability less than or equal to δ, then any variable such as y that is lower than that variable must also be lower than t with probability less than or equal to δ.We getEQUATIONTake the union bound for w ∈ W, then∀w ∈ W, P (g(µ D • w) -g(µ • w) ≥ L g • t) ≤ δ (20)Then for all w * ∈ W,P (g(µ D • w * ) -g(µ • w * ) ≥ L g • t) ≤ δ (21)Because w * is the optimal solution for problem ( 5)-( 7) and we suppose the assumption of realizability is set up, then in equation ( 7), w * satisfiesg(µ • w * ) ≤ τCombing with equation ( 19), we getP (g(µ D • w * ) -τ ≥ L g • t) ≤ δ (22)So we have, with at least 1δ probability,g(µ D • w * ) -τ ≤ L g • t = κ (23)Next, we focus on the validity constraint function ( 6).Here, we take x ⊤ (K D -K)w as the random variable and note the fact that it lies in the interval[-2B w , 2B w ].Use the Hoeffding inequality we have that ∀x ∈ B,EQUATION) Set t = 2Bw √ 2 log(|W||X |/δ) √ n, the inequality becomes the form as:P x ⊤ (K D -K)w ≥ t ≤ δ |W||X | (25)Take the union bound for all w and x, we haveP x ⊤ (K D -K)w ≥ t ≤ δ , ∀w ∈ W, ∀x ∈ X (26)So for all w * ∈ W,P x ⊤ (K D -K)w * ≥ t ≤ δ (27)Note the fact ∥Kw * -(1γ)µ 0 ∥ = 0, we have the inequality for all w * ∈ WP x ⊤ (K D w * -(1 -γ) µ 0 ) ≥ t ≤ δ (28)That is, with at least 1δ probability,x ⊤ (K D w * -(1 -γ) µ 0 ) ≤ t = ζ (29)Take the union bound for equation ( 23) and ( 29) completes the proof.Next, we show thatf (µ D • w D ) is close to f (µ • w * ).Then the empirical covering number n(ϵ, W) is defined as the size of the smallest ϵ-cover. Intuitively, the ϵ cover set can represents the original set in the sense of ϵ. This definition is very useful when the original set is continuous and we want to take the union bound of it. By this ϵ cover we can take the union bound of the continuous set and the distance of them is measured by ϵ. Lemma 5. We havef (µ D • w D ) ≤ f (µ • w * ) + √ 2L f B w √ n log 2|W| δwith 1 -3δ probability.Proof. From Lemma 4, we havef (µ D • w D ) ≤ f (µ D • w * )with probability at least 1 -2δ. Now, we use Hoeffding inequality to bound f (µ D • w)f (µ • w). Take (µ Dµ) • w as the random variable and note it lies in interval [-B w , B w ], then we haveEQUATION) Set t = Bw √ 2 log(2|W|/δ) √ n, the inequality becomesP (| (µ D -µ) • w| ≥ t) ≤ δ |W|Use the Lipschitz condition and union bound of w, we have∀w ∈ W , P (f (µ D • w) -f (µ • w) ≥ L f • t) ≤ δ (31)Choose w * ∈ W and combine with the inequality f (µEQUATION)with at least 1 -3δ probability.Next, we prove term II that f (µ• w K ) is close to f (µ D • w K ).Lemma 6. We havef (µ • w K ) ≤ f (µ D • w K ) + √ 2L f B w √ n log 2|W| δwith probability 1δ.Proof. This is easy to prove as we have a general result for all w ∈ W in equation ( 31). Here we take w K ∈ W,P (f (µ • w K ) -f (µ D • w K ) ≥ t) ≤ δ (33)which completes the proof.Note that w K violates the validity constraint in problem ( 5). This means that the calculated result may not satisfy the quality of the occupancy measure. To find the relation, we utilize the analogous lemmas in [Ozdaglar et al., 2023] to get the error bound between validity constraint violation and absolute objective difference.Lemma 7. Let d K be a variable solved by Program (8) that violates the validity constraint (6) and π K is the policy induced by d K . We can get thatf (d π K ) ≤ f (d K ) + 2B w L f 2 log(|W||X |/δ) (1 -γ) √ nwith at least 1δ probability.Proof. Define the marginalized occupancy measure as dK (s) = a∈A d K (s, a) and dπ K (s) = ∈ R be the state transition matrix, i.e.,P π D (j, i) = a∈A P s i ,a (s j ) • π(a | s i ).Also, we define the matrix G π = Diag(π d (• | s 1 ), π d (• | s 2 ), • • • , π d (• | s |S| )) ∈ R |S||A|×|S| ,EQUATION)Here the last inequality is because γ∥P π ( dKdπ K )∥ 1 ≤ γ∥ dKdπ K ∥ 1 , which follows from the fact that P π is a column stochastic matrix.We have:EQUATION)The first inequality holds because of the Lipschitz condition of function f . So combining the above two inequalities, we getf (d π K ) -f d K ≤ L f ∥M d K -(1 -γ)µ 0 ∥ 1 1 -γ (38) = L f ∥Kw K -(1 -γ)µ 0 ∥ 1 1 -γ (39)which follows the definition of density ratio w. Next, we give the bound of ∥Kw K -(1γ)µ 0 ∥ 1 .From inequality (26) above we have thatP x ⊤ (K D -K)w ≥ ζ ≤ δ , ∀w ∈ W,∀x ∈ X Then take w as w K and x as 1-norm, with at least 1δ we have∥Kw K -(1 -γ)µ 0 ∥ 1 ≤∥K D w K -(1 -γ)µ 0 ∥ 1 + ∥(K -K D )w K ∥ 1 ≤ζ + ζ (40)where the first inequality is because of the triangle inequality and the last inequality follows the fact that w K is the optimal solution to problem (8) and the above inequality. Combining ( 40) and ( 38) completes the proof. Now, we have the bound of term I and II. To further demonstrate the final bound, we also need to investigate the distance between the returned value w K by primal-dual method and optimal solution w D .Our algorithm 1 is the classical type of primal-dual subgradient method and our analysis mostly refers to [Nedić and Ozdaglar, 2009] . We put it here for the sake of completeness and add the theoretical analysis of our algorithm.First, recall the Lagrange function and updated rules of the algorithmL (w, λ, ϕ) = f (µ D • w) + λ (∥K D w -(1 -γ))µ 0 ∥ 1 -ζ) + ϕ (g (µ D • w) -τ -κ) w k+1 = P W w k -η∇L w (w k , λ k , ϕ k ) λ k+1 = λ k -η∇L λ (w k , λ k , ϕ k ) λ k+1 max 0 ϕ k+1 = ϕ k -η∇L ϕ (w k , λ k , ϕ k ) ϕ k+1 max 0For simplicity, we combine the Lagrange multipliers into one variable and call it ν, accordingly, we set the constraint g (w) ≤ 0. Note that constraints are analogous and we would split them in the end. Now the updated rules becomeEQUATIONwhere ν k ∈ M and note that we turn the interval of ν into a projection set which is an equivalent transformation. The Lagrange function is denoted asEQUATIONTheorem 2 (Saddle-Point Theorem in [Bertsekas, 1997] ). The pair (w D , ν D ) is a primal-dual optimal solution if and only ifL (w D , ν) ≤ L (w D , ν D ) ≤ L (w, ν D ) , f or all w ∈ W, ν ≥ 0,where w D ∈ W and ν D ≥ 0.The analysis of convergence is based on this theorem and it is a standard result that characterizes the primal-dual optimal solutions as the saddle points of the Lagrange function [Nedić and Ozdaglar, 2009] . Theorem 3. According to the updated rules, denote the solution to problem (8) as w K . Compared to the optimal solution w D , we have the upper bound for performance and constraint violation:(1) ∥g(w K ) + ∥ ≤ 2∥w 1 -w D ∥ Kη + 2L √ K + ε (44) (2) f (w K ) ≤ f * + ∥w 1 -w D ∥ 2 2Kη + ηL 2 (45)where η is the constant learning rate, w 1 is an initial state, ε ≥ 0, K is the iteration step and L is the max subgradient of the Lagrange function. Furthermore, we denote,w * = w D , f (w K ) = f (µ D • w K ) and f * = f (µ D • w D ), we use the above notations for simplicity.We first introduce some lemmas and prove the theorem step by step. Lemma 8. Suppose that the sequence {w k } and {ν k } are generated by the updated rules. Then we have(1) ∀w ∈ W, ∥w k+1 -w∥ 2 ≤ ∥w k -w∥ 2 -2η (L (w k , ν k ) -L (w, ν k )) + η 2 ∥L w (w k , ν k ) ∥ 2 . (2) ∀ν ∈ M, ∥ν k+1 -ν∥ 2 ≤ ∥ν k -ν∥ 2 -2η (L (w k , ν k ) -L (w k , ν)) + η 2 ∥L ν (w k , ν k ) ∥ 2 .Proof. We prove (1) and ( 2) is similar to (1).∥w k+1 -w∥ 2 = ∥P (w k -ηL w (w k , ν k )) -w∥ 2 ≤ ∥w k -ηL w (w k , ν k ) -w∥ 2 = ∥w k -w∥ 2 -2ηL w (w k , ν k ) (w k -w) + η 2 ∥L w (w k , ν k ) ∥ 2 ≤ ∥w k -w∥ 2 -2η (L (w k , ν k ) -L (w, ν k )) + η 2 ∥L w (w k , ν k ) ∥ 2where the first equality comes from the update rule and the last inequality is because of the convexity of the Lagrange function.Assumption 6 (Boundness of subgradient). We assume that the subgradient of the Lagrange function is bounded, such as∥L w (w k , ν k ) ∥ ≤ L , ∥L ν (w k , ν k ) ∥ ≤ L, ∀k ≥ 0.where L is the max Lipschitz constant in Lagrange function.Lemma 9. Set w k = 1 k k i=1 w ki and ν k = 1 k k i=1 ν ki , we have (1) 1 k k i=1 L (w i , ν i ) -L (w, ν k ) ≤ ∥w 1 -w∥ 2 2ηk + ηL 2 2 , ∀w ∈ W. (2) - ∥ν 1 -ν∥ 2 2ηk - ηL 2 2 ≤ 1 k k i=1 L (w i , ν i ) -L (w k , ν) , ∀ν ∈ M.Proof. We only prove (1) and equation ( 2) is similar to (1). By using Lemma 8 we haveL (w i , ν i ) -L (w, ν i ) ≤ ∥w i -w∥ 2 -∥w i+1 -w∥ 2 2η + ηL 2 2 Sum it from 1 to k, 1 k k i=1 L (w i , ν i ) -L (w, ν i ) ≤ ∥w 1 -w∥ 2 -∥w k -w∥ 2 2η + ηL 2 2 ≤ ∥w 1 -w∥ 2 2η + ηL 2 2 (46)And combine with1 k k i=1 L (w, ν i ) ≥ L (w, ν k )which is because of Jensen's inequality, we haveEQUATIONAssumption 7 (Slater's condition). There exists a vector ŵ such thatg j ( ŵ) < 0, ∀j = 1, 2, • • • , Nwe refer to ŵ as a Slater's vector.Note that Slater's condition is assumed in many primal-dual method literature [Chen et al., 2022 , Hong et al., 2024 , Nedić and Ozdaglar, 2009] . Lemma 10. Under Assumption 7, suppose q * is the dual optimal solution and w is a vector that satisfies Slater's condition, we have∥ν∥ 1 ≤ 1 γ (f ( ŵ) -q * )where γ = min 1≤j≤m {-g j ( ŵ)} and m is the number of constraints.The proof is referred to [Hiriart-Urruty and Lemaréchal, 1996 ]. The lemma above motivates the choice of dual set, that isM = ν ≥ 0 | f ( ŵ) - q γ + rwhere q ≤ q * and r ≥ 0 is a constant.Proof. Now, we are ready to give the general proof of Theorem 3. Combine Lemma 8 and Assumption 6, we haveEQUATIONMoreover,(ν i -ν D ) L ν (w i , ν i ) ≤ L (w i , ν i ) -L (w i , ν D ) ≤ L (w i , ν i ) -f * (49)where the first equation is because of convexity of L ν and the last equation dues to the Slater's condition. We have, ∀ν ∈ M and i ≥ 1(ν -ν D ) ⊤ L ν (w i , ν i ) = (ν -ν D + ν i -ν i ) ⊤ L ν (w i , ν i ) = (ν -ν i ) ⊤ L ν (w i , ν i ) + (ν i -ν D ) L ν (w i , ν i ) ≤ ∥ν i -ν∥ 2 -∥ν i+1 -ν∥ 2 2η + ηL 2 2 + L (w i , ν i ) -f * (50) Then, sum over i = 1, • • • , k, k i=1 (ν -ν D ) ⊤ L (w i , ν i ) ≤ ∥ν 1 -ν∥ 2 2η + ηkL 2 2 + k-1 i=0 L (w i , ν i ) -kf * (51)Because the above function is for all ν, thenEQUATIONHence, if s + = 0, equation ( 52) holds. If s + ̸ = 0, define vector:ν = ν D + r s + ∥s + ∥ ≥ 0Combine Lemma 10, we haveEQUATIONwhich implies that for ν ∈ M,EQUATIONRecall the definition of s, we have(ν -ν D ) ⊤ s = r∥ k i=0 g (w i ) + ∥ ≤ r max ν∈M k i=1 (ν -ν D ) ⊤ L (w i , ν i ) ≤ 1 2η max ν∈M ∥ν 1 -ν∥ 2 + ηkL 2 2 + k i=1 L (w i , ν i ) -kf * ≤ 1 2η max ν∈M (∥ν 1 ∥ + ∥ν∥) 2 + ηkL 2 2 + ∥w 1 -w D ∥ 2 2ηk + ηL 2 2 ≤ 1 2η max ν∈M ∥ν∥ + ηkL 2 2 + ∥w 1 -w D ∥ 2 2ηk + ηL 2 2 ≤ 1 2η f ( ŵ) - q γ + r + ηkL 2 2 + ∥w 1 -w D ∥ 2 2ηk + ηL 2 2 (56) Then, ∥g (w k ) + ∥ ≤ ∥w 1 -w D ∥ 2 2ηk + ηL 2 2 + 2 kηr f ( ŵ) - q γ + r 2 (57)Until now, we assume the dual set is appropriately chosen in every iteration and we should quantify it. For the dual setM = ν ≥ 0|∥ν∥ ≤ f ( ŵ) - q γ + rand the result in (57), We should chooser = min r≥0 ∥w 1 -w D ∥ 2 2ηk + ηL 2 2 + 2 kηr f ( ŵ) - q γ + r 2 which is r * (k) = f ( ŵ) - q γ 2 + ∥w 1 -w D ∥ 2 4 + kη 2 L 2 4 , ∀k ≥ 1.So the dual set in every iteration isM k = ν ≥ 0|∥ν∥ ≤ f ( ŵ) - q γ + r * (k) which implies ∥g (w k ) + ∥ ≤ 4 kη   f ( ŵ) - q γ + f ( ŵ) - q γ 2 + ∥w 1 -w D ∥ 2 4 + kη 2 L 2 4   ≤ 4 ηk 2 (f ( ŵ) -q) γ + ∥w 1 -w D ∥ 2 + ηL √ k 2 (58)For simplicity, we take the first term as a constant which doesn't affect our result:EQUATIONThe result of (1) in Theorem 3 completes.Next, we give the bound of the objective value. From the definition of the Lagrange function,EQUATIONNote that0 ∈ M = ν ≥ 0|∥ν∥ ≤ f ( ŵ) - q γ + rSet ν = 0 and combine Lemma 8, we have∥ν k+1 ∥ 2 ≤ ∥ν k ∥ 2 + 2ην k g (w k ) + η 2 L 2 Then 2ην k g (w k ) ≤ ∥ν k ∥ 2 -∥ν k+1 ∥ 2 + η 2 L 2 Sum over i = 0, • • • , k -1, - k-1 i=1 ν i g (w i ) ≤ 1 2η ∥w 1 ∥ 2 -∥ν k ∥ 2 + η 2 L 2 k 2 (61)We get the final result,f (w k ) ≤ f * + ∥ν 1 ∥ 2 2η + ∥w 1 -w D ∥ 2 2ηk + η 2 L 2 2which completes the proof of Theorem 3.Then we have the all results to prove the regret bound in Theorem 1.Theorem 3 indicates that after K iterations the objective and violation bound for problem (8) aref (µ D • w K ) ≤ f (µ D • w D ) + ∥ν 1 ∥ 2 2η + ∥w 1 -w D ∥ 2 2ηK + η 2 L 2 2 = f (µ D • w D ) + B 2 2ηK + η 2 L 2 2 = f (µ D • w D ) + B 2 2 √ K + L 2 2K (62) x ⊤ (K D w K -(1 -γ) µ 0 ) ≤ ζ + 2∥w 1 -w D ∥ Kη + 2L √ K + ε √ K = ζ + 2B √ K + 2L √ K + ε √ K (63) g (h D • w K ) ≤ τ + κ + 2∥w 1 -w D ∥ Kη + 2L √ K + ε √ K = τ + κ + 2B √ K + 2L √ K + ε √ K (64)where we set the initial Lagrange values equal to 0, the constant step size η = 1 √ K and B is the distance between w 1 and optimal solution w D .And recall Lemma 7, we have with at least 1 -2δ probability,EQUATIONThen, we have, with at least 1δ probability, the bound is,J r (π K ) -J r (π * ) = f (d π K ) -f (d K ) I + f (µ • w K ) -f (µ D • w K ) II + f (µ D • w K ) -f (µ • w * ) III = f (d π K ) -f (d K ) I + f (µ • w K ) -f (µ D • w K ) II + f (µ • w K ) -f (µ D • w D ) + f (µ D • w D ) -f (µ D • w * ) III ≤ L f 1 -γ • ∥Kw K -(1 -γ)µ 0 ∥ 1 + √ 2B w L f √ n log 2|W| δ + B 2 2 √ K + L 2 2K + √ 2B w L f √ n log 2|W| δ ≤ 1 1 -γ 6 √ 2L f B w √ n log 2|W||X | δ + 2B √ K + 2L √ K + B 2 2 √ K + L 2 2K + ε √ K ≤ 1 1 -γ 6 √ 2L f B w √ n log 2|W||X | δ + ι 2 √ K ≤ O(1/ √ n) + O(1/ √ K)where we set ι = 4B + 4L + B 2 + L 2 √ K + ε. 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?Answer: [Yes] Justification: The research conducted in this paper conform with the NeurIPS Code of Ethics.Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed? 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: The paper poses no such risks.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [Yes] Justification: We cite the original paper and abide by the license.Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. 
 
 Appendix: In the main text, we split the violation bound into three parts and list the relevant lemmas. Here we give the proofs for these lemmas and theorem.Proof. This proof is quite similar to Lemma 7 since we always want to establish connections between the required function and validity error bound. The main difference is the objective function and constraint function. So we keep the first half conclusion of the Lemma 7 which isEQUATIONThen for the safety constraint function, we haveEQUATIONwhere the first inequality is because Lipschitz condition of the safety constraint function. Also by combining the above functions, we haveEQUATIONAnd in Lemma 7 we have already established the bound of ∥KwK -(1 -γ)µ 0 ∥ 1 , then with at least 1 -2δ probability g(d K ) ≤ g(d π K ) + 2L g B w 2 log(|W||X |/δ) (1 -γ) √ n .which completes the proof.Proof. In this lemma, actually, we will prove that g (µ• w K ) is close to g (µ D • w K ).We take (µµ D ) • w as the random variable and it lies in [-B w , B w ]. We have the Hoeffding inequalityEQUATIONwhere we set t = √ 2Bw √ n log 2|W| δ . Next, take the union bound for w and use the Lipschitz condition for g, we have ∀w ∈ W, P (g (µEQUATIONwhich means that with at least 1δ probability,g (µ D • w K ) -g (µ • w K ) ≤ √ 2L g B w √ n log 2|W| δ .The proof is complete.Proof. This lemma is easy to be verified because we choose the relax parameter κ is equal to√ 2LgBw √ n log 2|W|δ and recall the result in Theorem 3 which completes the proof.Thus, take the Lemma 1, 2 and 3 together, we have, with at least 1 -3δ,J c (π K ) -τ = g(d π K ) -g(d K ) I + g(µ • w K ) -g(µ D • w K ) II + g(µ D • w D ) -τ III ≤ L g 1 -γ • ∥Kw K -(1 -γ)µ 0 ∥ 1 + √ 2B w √ n log 2|W| δ + κ + 2B √ K + 2L √ K + ε √ K ≤ 1 1 -γ 6 √ 2L g B w √ n log 2|W||X | δ + 2B √ K + 2L √ K + ε √ K + 2B √ K + 2L √ K + ε √ K ≤ 6 √ 2L g B w (1 -γ) √ n log 2|W||X | δ + υ √ K ≤ O(1/ √ n) + O(1/ √ K)where we set υ = 1 1-γ (4B + 4L + 2ε) which completes the proof.We introduce a practical version of our primal-dual algorithm, following the key structure in Algorithm 1. We utilize this algorithm to conduct various experiments in this paper.Algorithm 2: Practical version of POCCInput: Dataset D = {(s i , a i , r i , c i )} n i=1, cost threshold τ , learning rate η λ , η w , η ϕ , relaxed parameter ζ, κ.; Initialize network of importance weight w ψ ; for k = 1, 2, . . . , K do Jointly optimize:w k+1 ψ = Adam w k ψ -η ϕ ∇L(w ψ , λ k , ϕ k ) , λ k+1 = Adam λ k -η λ ∇L(w k ψ , λ, ϕ k , ϕ k+1 = Adam ϕ k -η τ ∇L(w k ψ , λ k , ϕ) .Compute the importance weight: ∀(s, a), w(s, a) = w ψ (s, a); Extract the policy: π(a | s) = w ψ (s,a)πµ(a|s)a ′ ∈A w ψ (s,a ′ )πµ(a ′ |s) ; Output: Policy π ; Hyperparameters In the experiments of maze and FrozenLake environments, we set the discount factor as γ = 0.99 and the cost threshold as τ = 0, indicating that the agent is not supposed to incur any cost. For our algorithm 2 and COptiDICE [Lee et al., 2021] , we perform a grid search on the set {0.00001, 0.00005, 0.0001, 0.0005, 0.001, 0.005} to determine the learning rate for parameters. We ultimately select a learning rate of 0.00001 for the neural network and a Lagrange scalar learning Justification: We provide the sufficient information on the computer resources.Guidelines:• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage. • The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute. • The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).Justification: There is no societal impact of the work performed.Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).Note that, they consider standard CMDPs which is a special case of ours. 


Decision: This work on constrained MDPs studies sample complexity under general function approximation, partial coverage, and general (convex) objective functionals. The proposed primal-dual approach achieves better sample complexity w.r.t. the state of the art, and under more general conditions.

The reviewers questioned the technical novelty of the contribution and the limited scope of the experiments.
However, during the discussion phase, the authors provided additional experiments on different environments, and clarified what are the improvements over the state of the art and the technical challenges that were involved.

For this reason, I recommend acceptance of this paper, conditional on the inclusion of the new experiments in the camera ready version, and the implementation of the other improvements suggested by the reviewers, especially regarding presentation. I also suggest to add to the manuscript a discussion on the technical novelty, in order to prevent further misunderstandings.

Reviews: review: paper_summary: paper_summary: This paper studies the offline safe reinforcement learning (RL) problem and proposes a primal-dual algorithm to solve this problem. The key contributions are that the paper focuses on the more general setting of convex Markov Decision Processes (convex MDPs), where the objective function is a convex utility function, rather than the standard linear rewards. The authors propose a primal-dual algorithm that can handle the offline safe RL problem under the convex MDP setting, crucially requiring only partial data coverage, a weaker assumption compared to previous work. The theoretical analysis provides the sample complexity of the proposed algorithm. Experimental results validate the theoretical findings and demonstrate the practical efficacy of the approach.
strength_weakness: strength_weakness: My main concern with this paper is the limited technical novelty of the contributions. The proposed formulation (8)-(10) appears to be a direct extension of the setup in prior work [26], where the linear reward and cost functions are generalized to convex functions. The algorithm itself is a standard primal-dual method for solving convex optimization problems, rather than a new technical innovation.

Furthermore, the experimental evaluation is quite limited in scope. The authors only compare their approach against a small number of baseline methods, and the experiments are run on a relatively small set of problem instances. This raises questions about the generalizability and practical significance of the empirical results.

While the paper tackles an important and relevant problem in offline safe reinforcement learning, the technical contributions seem incremental given the prior work in this area.
questions: questions: -- line 181, how large the dataset has to be in order for (8)-(10) to be close to (5)-(7)?

-- When w is parametrized by a neural network, does the proposed formulation satisfy all the assumptions made?
limitations: limitations: see weakness
paper_summary: paper_summary: This paper proposes a novel linear programming based primal-dual algorithm for convex MDPs which incorporates “uncertainty” parameters to improve data efficiency, while requiring only partial data coverage assumption. The authors provide theoretical results achieve a sample complexity of $O(1/((1-\gamma)\sqrt{n}))$ under general function approximation, improving the current state-of-the-art by a factor of $1/(1 − \gamma)$, where $n$ is the number of data samples in an offline dataset, and $\gamma$ is the discount factor. The authors also run experiments to validate their theoretical findings, which demonstrate the practical efficacy of their approach in achieving improved safety and learning efficiency in safe offline settings.
strength_weakness: strength_weakness: 1.	Can the authors give more explanations on Assumptions 2-4. Why do you introduce the set $\mathcal{W}$ and $\mathcal{X}$. Does the algorithm need to know these two sets in advance? If yes, what does it mean in practice?
2.	Does the algorithm need to know the behavior policy $\mu(a|s)$ in advance (in Eq. (12))? This is not a practical assumption.
3.	The authors should give more comparison to the existing results for offline (linear) constrained RL, since (linear) constrained MDPs is an important example of convex MDPs.
4.	What are the technical challenges and novelty in the offline convex MDP (RL) problem, compared to the existing online convex MDP (RL) works?
questions: questions: Please see the weaknesses above.
limitations: limitations: Please see the weaknesses above.
paper_summary: paper_summary: This paper investigates batch RL with safety constraints and function approximation, which is a question of both theoretical and practical importance.
strength_weakness: strength_weakness: (1) The presentation is a bit messy. The class X is not well-explained. The Lipschitz constant L appeared in Theorem 1 is not defined in the main text. Is L bounded by L_f, L_g and other parameters?

(2) There is an unstated assumption: the convergence of the proposed algorithm actually relies on the convexity of W (Lemma 8).  

(3) The upper bounds are stated in terms of log|W|, the log-cardinality of the function class W. However, it may be problematic to assume W is finite: if W is both convex and finite, then W must be a singleton, and the results are vacuous. Therefore, the upper bounds should instead be stated in terms of the log covering number of W.
questions: questions: Q1. Is there a relationship between the proposed primal-dual update rules and the actor-critic algorithms?

Q2. In assumption 4, it is required that all functions in W have a uniform upper bound B_w, which implies $B_w\geq C_\pi^\star $. It would be better to explicitly state that it requires prior knowledge on the concentrability constant.

Q3. The class X does not appear in the algorithm. Is it introduced purely for the sake of analysis?
limitations: limitations: N/A
paper_summary: paper_summary: This paper formulates offline convex MDPs under safety constraints and proposes a linear programming-based primal-dual algorithm for solving it. The authors make a partial data coverage assumption yet achieve a sample complexity of $\mathcal{O}(\frac{1}{(1-\gamma)\sqrt{n}})$ while the current SOTA is $\mathcal{O}(\frac{1}{(1-\gamma)^2\sqrt{n}})$. This paper also conducted the empirical evaluation and showed that the proposed algorithm achieves better performance in terms of reward and safety.
strength_weakness: strength_weakness: - While I admit that the main contribution of this paper is theory, I consider that the empirical experiments are not fully conducted. Both environments are toy problems, and there is no baseline method in 5.1. In 5.2, the benchmark task is the frozen lake, which is a much easier task than previous work tried to solve. I know COptiDICE is a well-known baseline algorithm, but there are many more algorithms that perform better than COptiDICE.
- The authors say "We include the limitations in our assumptions", but I do not think that the limitations of this paper exist except for the assumptions. I would recommend that the authors discuss the limitations such as scalability, empirical performance in more complicated tasks, etc.

**Minor Comments and Typos**
- Line 45: The following sentence seems weird to me. Should this be "We formulate ..."?
    - "We for the first study the offline."
- Figure 3: (a), (b), ..., (d) do not exist in Figure 3 while they are mentioned in the caption.
questions: questions: - In lines 229 - 238, the authors claim as follows. However, the empirical results are provided for grid-world environments. The size of the grid world is rather small (i.e., $8 \times 8$). Could you tell me why the authors used such small environments? I personally think that the following claim is not fully supported.
> Besides, our algorithm is appropriate in the scenario with large-scale state-action space
- I think I could follow the theorem and proof, but could you tell me what enables the authors to achieve the SOTA sample complexity $\mathcal{O}(\frac{1}{(1-\gamma)\sqrt{n}})$? What is the biggest reason why the author could improve the current SOTA by a factor of $1/(1-\gamma)$?
limitations: limitations: Though the authors discuss the limitations regarding assumptions, I think there are other limitations such as the applicability to more complicated tasks with continuous state-action spaces, computational complexity, etc.

Comments: title: I increased my score to 6
Responses
References
References
References
References
comment: We sincerely thank the reviewer for considering our response and revising the score. Much appreciate! Please let us know if you have any follow-up questions. We will be happy to answer them.
We sincerely thank you for the constructive suggestions that helps us improve our paper. Much appreciated! Please let us know if you have any follow-up questions. We will be happy to answer them.
Thank the authors for their repsonse and added empirical results. I increased my score to 6.
Given your responses and the promised changes, I will raise my rating to 5, favoring the acceptance of this paper.
We greatly appreciate your comments on the function class $\mathcal W$ and would like to respond to them as follows. 

**When comparing our results with existing works, it is necessary to highlight the necessity of convexity:** We will highlight our results based on the convex or convexified function class $\mathcal W$ and clarify that this is consistent with our most related work [7, 14, 17] (in Table 1) as they also require a similar convex property (either a tabular setting in [7] or convexified policy class in [14, 17]). 

**Elaboration on the function class $\mathcal W$:** We apologize for any misunderstandings and for any unintentional impression of dishonesty regarding our claim on the function class $\mathcal W$ due to the missing definition and statement. We would certainly clarify the definition of $\mathcal W$ and $|\mathcal W|$ (e.g., emphasize the continuous property and the covering radius and number). 

We thank the reviewer once again for the detailed comments, which have definitely helped improve the quality of our paper. We sincerely hope our response addresses your major concerns and that you will consider reevaluating our work. Please let us know if you have any further comments, and we will do our best to address them.
Thank you for your response. Some comments:

> However, when W is not convex, the operation of convexification on function class W is reasonable and common in offline safe RL

While the algorithm can operate on the convexified function class, the log covering number of the convexified function class can be much larger than the log covering number of W. Therefore, when you compare your results with existing works, it is necessary to highlight the necessity of convexity.

> In our paper, we do not assume the function class W is finite

I don't think this is an honest claim, given that your current proof of Lemma 5 directly uses the union bound over W. You don't even mention how cardinality is defined for continuous W: The word "covering" does not appear in the paper. Further, if it is indeed defined as the covering number, it has to depend on the covering radius, which is also not mentioned.

Of course, this is a relatively minor issue. However, you shall admit that it is a mistake, instead of denying it.
Thanks a lot for your precious time in helping us improve our paper. Much appreciated! Please let us know if you have any follow-up questions. We will be happy to answer them.
Thanks a lot for your precious time in helping us improve our paper. Much appreciated! Please let us know if you have any follow-up questions. We will be happy to answer them.
Thank you for the clarification and additional experiments. The concerns I had at the time of the initial review are resolved. After reading other reviews and authors' rebuttals, I still recommend acceptance of this paper. That said, I think that the impact of this paper would be moderate-to-high, so I keep the original score of 6.

> 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
I would like to thank the authors for their rebuttal, and I have read it. I keep my score and remain positive about this paper.
[R1]: Hoang Le, Cameron Voloshin, and Yisong Yue. "Batch policy learning under constraints." In International Conference on Machine Learning, pages 3703–3712. PMLR, 2019.

[R2]: Kihyuk Hong, Yuhang Li, and Ambuj Tewari. "A primal-dual-critic algorithm for offline constrained reinforcement learning." In International Conference on Artificial Intelligence and Statistics, pages 280–288. PMLR, 2024.

[R3]: Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. "A convergence theory for deep learning via over-parameterization. In International conference on machine learning." pages 242–252. PMLR, 2019.

[R4]: Asuman E Ozdaglar, Sarath Pattathil, Jiawei Zhang, and Kaiqing Zhang. "Revisiting the linear-
programming framework for offline rl with general function approximation." In International
Conference on Machine Learning, pages 26769–26791. PMLR, 2023.

[R5]: Ofir Nachum, Yinlam Chow, Bo Dai, and Lihong Li. "Dualdice: Behavior-agnostic estimation of
discounted stationary distribution corrections." Advances in neural information processing systems,
32, 2019.

[R6]: Jongmin Lee, Wonseok Jeon, Byungjun Lee, Joelle Pineau, and Kee-Eung Kim. "Optidice: Offline
policy optimization via stationary distribution correction estimation." In International Conference
on Machine Learning, pages 6120–6130. PMLR, 2021.

[R7]: Jongmin Lee, Cosmin Paduraru, Daniel J Mankowitz, Nicolas Heess, Doina Precup, Kee-Eung Kim, and Arthur Guez. "Coptidice: Offline constrained reinforcement learning via stationary distribution correction estimation." In International Conference on Learning Representations, 2021.
[R1]: Kihyuk Hong, Yuhang Li, and Ambuj Tewari. "A primal-dual-critic algorithm for offline constrained
reinforcement learning." In International Conference on Artificial Intelligence and Statistics, pages
280–288. PMLR, 2024.

[R2]: Jongmin Lee, Cosmin Paduraru, Daniel J Mankowitz, Nicolas Heess, Doina Precup, Kee-Eung Kim,
and Arthur Guez. "Coptidice: Offline constrained reinforcement learning via stationary distribution
correction estimation." In International Conference on Learning Representations, 2021.

[R3]: Haoran Xu, Xianyuan Zhan, and Xiangyu Zhu. "Constraints penalized q-learning for safe offline
reinforcement learning." In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36,
pages 8753–8760, 2022.

[R4]: Aviral Kumar, Justin Fu, Matthew Soh, George Tucker, and Sergey Levine. "Stabilizing off-policy
q-learning via bootstrapping error reduction." Advances in neural information processing systems,
32, 2019.

[R5]: Adam Stooke, Joshua Achiam, and Pieter Abbeel. "Responsive safety in reinforcement learning
by pid lagrangian methods." In International Conference on Machine Learning, pages 9133–9143.
PMLR, 2020.
[R1]: Aviral Kumar, Joey Hong, Anikait Singh, and Sergey Levine. "Should i run offline reinforcement
learning or behavioral cloning?" In International Conference on Learning Representations, 2021.

[R2]: Hoang Le, Cameron Voloshin, and Yisong Yue. "Batch policy learning under constraints." In International Conference on Machine Learning, pages 3703–3712. PMLR, 2019.

[R3]: Fan Chen, Junyu Zhang, and Zaiwen Wen. "A near-optimal primal-dual method for off-policy learning in cmdp." Advances in Neural Information Processing Systems, 35:10521–10532, 2022.

[R4]: Kihyuk Hong, Yuhang Li, and Ambuj Tewari. "A primal-dual-critic algorithm for offline constrained reinforcement learning." In International Conference on Artificial Intelligence and Statistics, pages 280–288. PMLR, 2024.

[R5]: Haoran Xu, Xianyuan Zhan, and Xiangyu Zhu. "Constraints penalized q-learning for safe offline reinforcement learning." In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 8753–8760, 2022.

[R6]: Jongmin Lee, Cosmin Paduraru, Daniel J Mankowitz, Nicolas Heess, Doina Precup, Kee-Eung Kim, and Arthur Guez. "Coptidice: Offline constrained reinforcement learning via stationary distribution correction estimation." In International Conference on Learning Representations, 2021.

[R7]: Aviral Kumar, Justin Fu, Matthew Soh, George Tucker, and Sergey Levine. "Stabilizing off-policy q-learning via bootstrapping error reduction." Advances in neural information processing systems, 32, 2019.

[R8]: Adam Stooke, Joshua Achiam, and Pieter Abbeel. "Responsive safety in reinforcement learning by pid lagrangian methods." In International Conference on Machine Learning, pages 9133–9143. PMLR, 2020.

[R9]: Tom Zahavy, Brendan O’Donoghue, Guillaume Desjardins, and Satinder Singh. "Reward is enough
for convex mdps." Advances in Neural Information Processing Systems, 34:25746–25759, 2021.
[R1]: Hoang Le, Cameron Voloshin, and Yisong Yue. "Batch policy learning under constraints." In
International Conference on Machine Learning, pages 3703–3712. PMLR, 2019.

[R2]: Fan Chen, Junyu Zhang, and Zaiwen Wen. "A near-optimal primal-dual method for off-policy
learning in cmdp." Advances in Neural Information Processing Systems, 35:10521–10532, 2022.

[R3]: Kihyuk Hong, Yuhang Li, and Ambuj Tewari. "A primal-dual-critic algorithm for offline constrained
reinforcement learning." In International Conference on Artificial Intelligence and Statistics, pages
280–288. PMLR, 2024.

[R4]: Jongmin Lee, Cosmin Paduraru, Daniel J Mankowitz, Nicolas Heess, Doina Precup, Kee-Eung Kim,
and Arthur Guez. "Coptidice: Offline constrained reinforcement learning via stationary distribution
correction estimation." In International Conference on Learning Representations, 2021.

[R5]: Haoran Xu, Xianyuan Zhan, and Xiangyu Zhu. "Constraints penalized q-learning for safe offline
reinforcement learning." In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36,
pages 8753–8760, 2022.

[R6]: Aviral Kumar, Justin Fu, Matthew Soh, George Tucker, and Sergey Levine. "Stabilizing off-policy
q-learning via bootstrapping error reduction." Advances in neural information processing systems,
32, 2019.

[R7]: Adam Stooke, Joshua Achiam, and Pieter Abbeel. "Responsive safety in reinforcement learning
by pid lagrangian methods." In International Conference on Machine Learning, pages 9133–9143.
PMLR, 2020.