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 2024 poster (2024)
Keywords: safe reinforcement learning
convex MDPs
offline
sample efficient.
Primary area: reinforcement_learning
TL;DR: An optimal sample complexity algorithm with partial data coverage for offline safe RL.

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.

Safe and Efficient: A Primal-Dual Method for Offline Convex CMDPs under Partial Data Coverage
Haobo Zhang ShanghaïTech University 2hanghb22255shhngaaatee... edu.
Xiyue Peng Shanghai University pengy:200440haagghatteh... edu.cn cn
Honghao Wei
Xin Liu"
Washington State University honghao.. wei@wsu. edu
ShanghaiTech University liuxin/@@hanghaittchh edu. cn
Abstract
Offline safe reinforcement learning (RL) aims to find an optimal policy using a pre-collected dataset when data collection is impractical risky. We propose novel linear programming (LP) based primal-dual algorithm for convex MDPs that incorporates "uncertainty" parameters improve data efficiency while requiring only partial data coverage assumption. Our theoretical results achieve a sample complexity of O(1/(1 /n) under general function approximation, improving the current state-of-the-art by a factor of 1/(1 - -7), where n is the number data samples in offline dataset, and y is the discount factor. The numerical experiments validate our theoretical findings, demonstrating the practical efficacy of approach in achieving improved safety and learning efficiency in safe offline settings.
Introduction
Safe reinforcement learning (RL) aims to learn reward-maximizzng policy while satisfying multiple safety constraints, demonstrating its practicality 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 crucial for task completion. One way mathematically characterize safe RL is through Constrained Markov Decision Processes (CMDPs) [Altman] 2001], 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, impractical. Ensuring sample efficiency in offline RL with function approximation typically requires additional assumptions about both the function classes and the dataset due training instability and distribution shift issues (Fujimoto
ct al. 2019 Kostrikov et al. 2021 Paine et al. 2020]. Earlier studies [Chen and Jiang 2019 Liao al.
2022 Liu et al. 2019 Wang 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 mild and accepted assumption in offline RL without considering safety. However, it is highly unacceptable and impractical in safe offline RL, would require the dataset 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. 202T
Uehara and Sun 202T
Xie et al. 202T
Zhan al. 2022 Zhu et al.
Conresponding author.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Table Comparison of algorithms for offline safe RL with function approximation.
Data
Function
Sample Complexity
Algorithm
Convex MDP
Coverage
Approximation
CoptiDICE
Lee et al.
2021]
No
Partial
General
None
DPDL
Chen et al.
2022
No
Partial
None
(1-2)
MBCL
Le et al. 2019
No
Full
General
(1-3) 2
PDCA
Hong et al.
2024
No
Full
General
0
(1-3)'v V
Ours
Yes
Partial
General
(1-7)vn
2023
reduce the assumption to single-policy coverage by using pessimism in the face of uncertainty.
Unfortunately, all existing studies [Chen al. 2022 Hong et al. 2024 Le al.) 2019] safe offline
RL still require coverage for all policies.
Beyond traditional offline safe RL, many applications do 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 al. 2021] studying more general scenario called convex MDPs, where the objec- tive 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 scenar- ios, including imitation [Abbeel and Ng. 2004), exploration (Hazan et al. [019]. and more. However, studying convex MDPs introduces additional challenges. beyond cumulative rewards means that the Bellman equation fails to hold due to the lack of reward additivity. This leads to breakdowns
convex MDPs, moving
many techniques based on Dynamic Program- ming (DP) IZhang al., 2020b] Despite 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. To address the coverage issue and extend the general func- tion approximation setting, we focus on convex MDPs the safe offline setting. Our main contributions sum- marized below (the detailed comparisons can be found in Table :):
We are the first to study offline convex MDPs under safety constraints with partial data coverage assumption. We reformulate the problem using marginalized impor- tance weights to avoid issues caused by the Bellman equa- tion's 's failure in convex MDPs.
Figure 1: Performance of our algorithm FrozenLake with completely random data.
We analyze the convergence rate of our proposed ap- proach under partial coverage assumption and theoretically prove that our algorithm achieves (1- in both objective and violation bounds with general function approximation, when
the number of iteration is larger than The sample complexity of O ((-))=) improves the best
existing result by a factor of 1/(1
Experimental results on Imitation Learning and standard CMDPs demonstrate the generality and effectiveness of our algorithm. As Figure shows algorithm performs well even with completely random and safett-violated offline dataset with general function approximation, which verifies our theoretical findings.
1.1 Related Work
Offline Safe RL: The offline safe reinforeement learning setting entails the agent learning from fixed dataset while adhering to safety constraints. This involves a blend of offline RL and safe RL, yet research this approach, particularly concerning theoretical analysis, remains limited. BCQL.
Note that, they consider standard CMDPs which is special of

---

augmented by BCQ FFjjimoto et al., 2019] optimizes the policy in the offline phase and applies the Lagrange method to handle constraints. CPQ [Xu al. [022] tackles the safety constraints by overestimating the cost value function of aut-of-distribution ("unsafe") actions and updating the reward value function with 'safe' actions. Another line of work [L.ee 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 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 -iremaatiooottorettic sample complexity lower bound and proposes near-optimal primal-dual learning algorithm under partial data coverage but without function approximation. The most related work (Hong al., [024] approaches the problem from the perspective of the Actor-Critic algorithm, analyzing the sample complexity to be under Slater's condition and full data coverage assumption.
( (1-2)* "" Vnn
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. 202T] utilizes Fenchel duality to cast convex MDPs as min- max "two-player" games, proposing a meta- aaaaa-lggorthmm 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.
2 Problem Setup
2.1 Convex CMDP problem
We study discounted constrained Markov decision process (CMDP), denoted by M (S, A, R, C,T,T, y, po). where S is the state space (a finite set), A is the action space (a finite set), R 8 x A 1) and C S A [0, are reward and cost functions, respectively, T S x A + ASS) is the transition probability kernel, where (-)) denotes the probability simplex, y E 10, 1) denotes the discount factor, and 140 E A(S) is the initial state distribution. We define a policy π : S + A(A) as a probability mapping from states to actions. At time slot t, the agent observes state 8t and takes action a according the policy æ. For a policy ,, we define its discounted state-action occupancy measure dz as follows
d= ds, = (1 - > TT (81= = 8, -0==a) a), vs E S, a A
where P., (st, ax) is the probability of state-action pair (s.a) being visited at time slot t under the policy т. Further, we let dx (s) = (s)=Eae da (s, a) be the discounted state occupancy measure.
Given the occupancy measure above, we can formulate the following convex CMDP problem min dyek
[dx) s.l. y (d=) ST,
where f and g are both convex functions, and 7 is the cost threshold. We present a single safety constraint for simple exposition, and our result can be readily generalized the setting with multiple constraints. The set K. is probability simplex that satisfies global balance equations of the underlying Markov process
K = {d] Σ
d(ss = (1-7) po(s) + Σ
Vs S}.
8'.0"
This set can also be written compact matrix form that
K {d] Md (1 (1 }, M Diag 11 ... ) -yP, (2)
3

---

where A| = [1,1, ,1 E ERAI and P E RSSX 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] [202], 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 (Aluman 2021]. which can be written as
Er(s, (d(s) d EK
max
s.t. Σ (ss ST
(3)
8,0
8,0
where 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 as
min dy
F (dz, de) s.t. ds(s) S T, Vs E H.
where de 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 promising avenue for developing safe and effective algorithms, as introduced next.
2.2 Offiine Reinforcement Learning
In offline RI., we cannot interact with the environment and only have access to dataset with finite number of samples. Let D = (8;, a, ri, (a) o²);== be a collected offline dataset where we assume all the pairs (s;, a.) are generated independently and identically distributed (i.i.d.) from data distribution u(s, a) induced by behavior policy тμ- Let nep(s, a) represents the number of occurrences of the state-action pair (s, a) in the offline dataset D, then (s a) = r ss a)/n is an empirical version of u(s, a). In offline RL, 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 x² concentrability assumption that refers to partial data coverage,
Assumption 1 (πr -r'ceennetrrbbllity)) Let n² be the optimal policy to problem Cz- > O such that d (8, a) ((s a) S Cx., for all s E S, a E A.
I. there exists constant
This assumption controls the distribution shift between offline data distribution μ and the occupancy measure dz- 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 n². 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 al. 2024 Le et al. 2019], our assumption 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 Impor- tance 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 (Marginalized Importance Weight). Given a policy let d be the occupancy measure d(s.a)
induced by и. We define marginalized importance weight w S x A + Rt as w(s,a) p(s,aa Vs E S, a 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 us and M in equation 2 we define matrix K R (18 (SIIA) and KD E [[S)A
as
K(s', (s, a)) = M(s', a)) a(s,a), KD(s', (s, = M(s,, (s. a)) (D(s,a),
where KD can be seen as an empirical version of K in dataset D and it straightforward to verify Kw Md. d. With these notations, we establish an equivalent formulation with problem (I w.r.t

---

MIW
min f(u w)
(5)
s.t. Kw = (1-
(6)
g(u w) T
where the operator "." denotes the element-wise product of vectors. As aim establish the sample-efficient learning algorithms in large state-action spaces, we regard the importance weight w as function, i.c. & A E+ that belongs to the convex function class W in the following assumption.
Assumption 2 (Realizability). We assume w" E W where w" is the optimal solution to the problem
This assumption assumes the optimal solution w=""") can be realizable for convex function class W. Note that the assumption of the convex function class W reasonable and standard, which also achievable with the convexífication 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 al. 2024). Now consider W as discrete function class for simplicity and it readily extends to continuous settings (in Remark I Further, we introduce completeness assumption that used relax the key constraint in (6).
Assumption 3 (Completeness). Let zw be within the function class Define mapping Φr such that o(w) (Kw (1 - 7)Ho)) = x (K w - 7)po) K - (1 - 7)lll11 Then, we have (W,X) complleeens under the mapping @, iee. Fw E X X for w W.
Intuitively, the completeness assumption allows replace the computation of the 1--ormm with 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. || S Ba,, Yu E W and || I Bw, Vxn X.
Combining this assumption with Assumption [ implies B 2 Cx., Lastly, we impose mild assumption for the reward and cost functions in the problem (I.
Assumption 5 (Lipschitz condition). The functions fz) and g(x) are convex and satisfy the Lipschitz condition, where there exist constants Ly and Ly such that for any x, y, the following inequalities hold [f(x) - f(y) s Ly]|= - yll and [g(z) g(y)l I Lg x yll-
3 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., |02 Liu et al. 2023b Xu et al. 2022], and articles with theoretical analysis
either yield unsatisfattory 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 O (1~>)< with general function approximation, which improves the current state-of-the-arr result by a factor of 1/(1 (1))).
3.1 Algorithm Design
Inspired by [Ozdaglar et al., 2023), we first introduce an empirical version of problem (57 the offline setting by incorporating suitable relaxed parameter into the safety constraint. Intuitively, the empirical version of the problem "close" to the original problem when the dataset large. This is the key observation for analyzing the convergence performance and safcty violations. To solve
5

---

5
we present its empirical and relaxed problem:
f(UD-1 - w) min WEW
(8)
s.t.
||DDw (1 - (1)o) S,
(9)
g(PD w) - - K.
(10)
where up and Kp are the empirical version of μt and K, respectively; Ç and are the relaxed perpaaraaeters for the validity constraint (Bellman equation) and safety constraint. Intuitively, the parameters of Ç and k capture the "uncertainty" induced by the offline dataset 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 the objective and constraint violation bound depends on the "uncertainty" which exhibits O(1/ distance.
Note that all parameters in the optimization problem 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., is parameterized by a neural network), it would be quite challenging (if not impossible) to solve this problem. To address this challenge, we propose primal-dual algorithm that sample-efficien and computationally tractable to solve the problem iteratively. We first introduce the Lagrange function of problem
10p can determined from the offline
I0).
C (w; X, Φ) = f (ND w) + A K (1 7)) - -) + d (g (MD w) - -T-M -K), (11)
where \ and @ are Lagrange multipliers.
Algorithm 1: Primal-dual algorithm for Offline Convex CMDP (POCC)
Input: Dataset D {(ss, a, Tı, cx) cy) the relaxed parameters K, S, and the step size 7 VR
Initialization: Choose any w E W and the Lagrangian multipliers A = 0, o² = 0:
for l = 1,2, ... K do
Primal: wht Pw [w Vou *t,
Dual: gh+11 = 1 1/V (w A )
A [ 1 A [0)
where Pw is the projection onto set W and [:] is the projection onto interval [t, h].
5
Compute the average WK- = Σ w²:
Extract the policy H with formula
7 Output: Policy क
Given the Lagrange function above, we introduce our algorithm called POCC (in Algorithm D which takes the offline dataset D input and runs 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 म based on the offline dataset 'D as follows
(x(ssa) Eee (x(aaa))
if EweAwK(S, a') (T) (8)
k (a
s)
(12)
if Eves a'
= 0
where the second equality means that if Ed' wK(s, d') = 0 we randomly choose an action for state
3.2 Theoretical Results
We present the theoretical results of our proposed approach in the following theorem.
Theorem 1 (Sample complexity of Tg). Suppose Assumptions hold. Denote T as the
corresponding policy induced by Wg. Set the relaxed parameters
2v/2B.. Vn
log 5
| and

---

v2L,Bo Bv
V log 2|W| and the step size 1)
1
1 Let the constants
1-y (4B
+ 4L 2
v
JK"
and I-7
1
B3 + AB + 4L +
I.2 JK
+ 8). we have, with at least 1 - 8I probability,
BL (2logg(W]]])
Jx(TK) }x(TT)
(13)
(1 (1-1) vn
2VK
Je (Tx) - BL 220g
V
(14)
(1-7)
VK
where J, (T = s(dx) and JA(TK)= g(dx) are objective and constraint performance of policy respectively, represents the distance between initial value we of the teeaaion and optimal solution
wD to problem (8 (8), & 2 0 is a constant, I, is the max Lipschitz constant of Lagrange function and K is the number of iterations.
Remark 1. We remark that Theorem 7 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 W, and the union bound can be applied to its e-covering set. This adjustment also preserves the sample complexity order of (L//VR), up to constant dependent on c. For further details on the extension,frm discrete
W to a continuous set, please refer to [Le et al. 2019 Xie and Jiang [022]].
Theorem demonstrates that the convergence performance of our algorithm can be divided into two parts: ((/vV) + O(1/VK) 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(I//)) connects with the error bound between wK and optimal solution wD, which decays at the rate of 1/vK when the number of iterations increases. It is worth noting that the convergence rate of policy T is still (L//VT) when the iterative number is sufficient to satisfy K n. The algorithm is gradient-basee the optimization problem ( (TO). 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 Yuu and Neely 2017 with a convergence rate of O1/K))
and does not involve additional computations for solving
Unlike most of the previous work focuses on convex MDPs in online setting [Bai et al. 2023 Ying et al. 2023 Zahavy al. 2021 Zhang et al. 2020b), Theorem t to the best of our knowledge is the
first provable result in offline convex MDPs. Moreover, compared to the best result O
(I-))>m
in offline CMDP Hong et al. 2024 Chen et al. 2022 our results achieve a sample complexity
of O algorithm 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 al. 2024] because replace the realizability of value function / with slightly stronger completeness assumption but reduce the data coverage from full to partial. As stated in Assumption I the full data coverage not only implies access to a highly exploratory dataset but also is impractical for offline safe RI, as it assumes behavior policy needs 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
(1-))/ which outperform the state-of-the-art by a factor of 1/(1 - -). Besides, our
Remark 2. In the theorem, we assume prior knowledge of the behavior policy n. for the sake of exposition. However, in practice, it is often challenging to know the behavior policy in advance, rypically only have access to the offline dataset. The most popular approach to tackle this challenge is behavior clone. It posits that ît, can be estimated as (ty(a)s) m((,a) a(ss) 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.
4 Theoretical Analysis
In this section, we present sketch of the proof of Theorem I 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
7

---

We first decompose the bound into different major terms and then sutdy them individually
Je(TK) - = g(dxxx = g[ g(dx)= g(p. wx) g(u wx) + g(UD wx) -
(15)
(16)
III
The first equality holds due to the definition: Jo(TK) = g(drx)) where dxx represents the occupancy measure induced by returned policy kx. Recall the definition w(s, a) (((s, d(s, a), we then have g(dx) ) g( Wx). It is worth noting that the decomposition is intuitive since terms and II relates to the idea of constructing "uncertainty" parameter for the offline dataset and term III mainly depends the convergence of primal-dual method.
Specifically, term I is the distance between g(dx) and g(dTx). ). It represents the error that we rectify the unnormalized occupancy measure dx, which violates the validity constraint (6. to satisfying one x The term illustrates the error incurred when applying the calculated W from offline dataset D to the real environment μ4, which depends on the sample size of the dataset. The term III is related to the relaxed parameter
safety constraint (7) and the distance between returned w and optimal solution WpD Next, we present the following lemmas to bound these terms.
Lemma 1. Suppose Assumptions H hold, we have, with probability at least 26,
Jc(Tk) g(dx) S 4Lg Bu / /2 (2
(1- (1-7)vn
Lemma 2. Suppose Assumptions 7 hold. For wK E W. we have, with probability least 1 6,
f wx) -9(WD wx) v2L,Bu. Bu
2
Vlog
vn
6
Lemma 3. Suppose Assumptions 77 hold. For wK E W. we have
U(D wx) KK
VK
Combining the above lemmas, have, with least 38 probability,
Jc(TK) g(d=x) ) g(dx)= g(p wx) g(UD wx) + g(pD wx)
4Lg B w V / (2) (1 - 7'
2V B.r Vn
2|W1
log
5 + VK
6v 2L Bm /2
(1 7)
VK
where we set (
2v2B vn
log
|
K
V B.
log
2|W]
Experiments
This section aims to justify the effectiveness of our proposed framework through numerical experi- ments. We test a practical version of Algorithm [ where we replace the gradient-type update with the "Adam" -type update (the detailed algorithm
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
5.1 Safe Imitation Learning
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, illustrated
8

---

in Figure 2 modified from Geist et al. 2022]. The problem of (safe) imitation learning can be formulated as F(d) (d dE), where de 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 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 poor results, and it's not suitable when considering the safety of the agents.
G
Figure 2: Reading order: (a) target demonstrations in yellow, wall in white; (b) result for log- density without considering the safety constraint; (c) target demonstrations that all states in top-right corners have cost; (d) result for log-density with safety constraint.
Our results are presented in Figure 2 In Figure (2p), it 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 cost in the entire top-right corners, is evident that our policy avoids states with cost and behaves appropriately, aligning with our theoretical framework.
5.2
Offline CMDP
We consider 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 is obtained when the agent achieves the goal, and the main cost function assigns cost of if the agent falls into hole and 0 otherwise. The diagram of the environment has been presented in Figure in the introduction.
Initially, simulate mixture of different percentages of optimal and uniform policies collect the offline dataset. We employ various behavior policies Tp, running 200 trajectories to collect the offline dataset D. with each trajectory having 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 Frozenl_ake. such that if the agent falls into hole, can also come out in the next step. This implies that our cost constraint influences the training. We set the cost threshold not supposed to incur any cost. Note that higher percentage with a uniform policy indicates that the problem becomes more difficult. We set the discount factor in our algorithm. Furthermore, we encode the environment with one-hot encoding and employ a more practical algorithm. We refer to
here, which means that the agent
0.99, 0.1, and
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 well-acknow.edded baseline algorithm in the offline safe RL literature Hong a.. 2024
Liu et al. 2023b
Rewnrd
0.70
0.8
0.30
0.00
150
2001
0.4
10P
10
10.
Teaning
10P
Training
X30
Datasize
Datasize
Our
COpoDICE
0.23
0.20
0.0
Figure: 3: Performance on FrozenLake with general function approximation. Reading order: (a) and (b) show the training result with four different behavior policies of COptiDICE and ours. (c) and (d) demonstrate the variations in rewards and costs as the dataset increases. Each point the average result of 10 independent runs.
Denote 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 the first two figures, 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 figures, we test the performance of 0.5 in behavior policy. The results demonstrate
algorithms in different sizes of dataset, where that our algorithm can find safe and optimal path the dataset size increases. In contrast, the results from the COptiDICE algorithm show high variance, where it can only find 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.
6 Conclusions
In this work, we consider convex CMDPs in the offline setting. We propose sample efficient RI. approach that addresses the challenges offline convex CMDPs. We theoretically prove that we can suffer O(1/vn) sample complexity in both performance and violation bound with general function approximation under mild data coverage assumption, which the first result offline convex MDPs best of our knowledge and surpasses the state-of-the-art result in offline safe RL by a factor 1/(1 - 7). Experimental studies further demonstrate the effectiveness and generality of our framework.
10

---

References
Pieter Abbeel and Andrew Ng. Apprenticeship learning via inverse reinforcement learning. In Proceedings of the twenty-first international conference Machine learning, page 1, 2004.
David Abel, Will Dabney, Anna Harutyunyan, Mark K Ho, Michael Littman. Doina Precup, and Satinder Singh. On the expressivity of markov reward. Advances in Neural Information Processing Systems, 34:7799-7812, 2021.
Eitan Altman. Constrained Markov decision processes. Routledge, 2021.
Qinbo Bai, Amrit Singh Bedi, Mridul Agarwal, Alec Koppel, and Vaneet Aggarwal. Achieving
zero constraint violation for concave utility constrained reinforcement learning via primal-dual approach. Journal of Artificial Intelligence Research, 78:975-1016, 2023.
Stav Belogolovsky, Philip Korsunsky, Shie Mannor, Chen Tessler, and Tom Zahavy. Inverse rein- forcement learning in contextual mdps. Machine Learning, 11009):225--2334 2021.
Dimitri P Bertsekas. Nonlinear programming. Journal of the Operational Research Society, 48(3): 334-334, 1997.
Fan Chen, Junyu Zhang, and Zaiwen Wen. A near-optimal primal-dual method for off- off-policy learning in cmdp. Advances Neural Information Processing Systems, 35:10521-10532 2022.
Jinglin Chen and Nan Jiang. Information-theoretii considerations batch reinforcement learning. In International Conference Machine Learning, pages 1042-1051. PMLR, 2019.
Jinglin Chen and Nan Jiang. Offline reinforcement learning under value and density-ratio realizability: the power of gaps. In Uncertainty in Artificial Intelligence, pages 378-388, PMLR, 2022.
Scott Fujimoto, David Meger, and Doina Precup. Off-policy deep reinforcement learning without exploration. In International conference on machine learning, pages 2052-2062. PMLR, 2019.
Matthieu Geist, Julien Pérolat, Mathieu Laurière, Romuald Elie, Sarah Perrin, Oliver Bachem, Rémi Munos, and Olivier Pietquin. Concave utility reinforcement learning: The mean-field game viewpoint. In Proceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems, pages 489-497, 2022.
Elad Hazan, Sham Kakade, Karan Singh, and Abby Van Soest. Provably efficient maximum entropy exploration. In International Conference Machine Learning, pages 2681-2691. PMLR, 2019.
DeatiBap Hiriart- Hiriart-Urruty and Claude Lemaréchal. Convex analysis and minimization algorithms I: Fundamentals, volume 305. Springer science & business media, 1996.
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.
Ravi Kiran, Ibrahim Sobh, Victor Talpaert, Patrick Mannion, Ahmad A Al Sallab, Senthil Yogamani, and Patrick Pérez. Deep reinforcement learning for autonomous driving: A survey. IEEE Transactions on Intelligent Transportation Systems, 23(6):4909 4926, 2021.
Ilya Kostrikov, Ashvin Nair, and Sergey Levine. Offline reinforcement learning with implicit q-learning arXiv preprint arXiv:21 2021.
Hoang Le, Cameron Voloshin, and Yisong Yue. Batch policy learning under constraints. In Interna-
tional Conference on Machine Learning, pages 3703-3712. PMLR, 2019.
Jongmin Lee, Cosmin Paduraru, Daniel 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.
Sergey Levine, Chelsea Finn, Trevor Darrell, and Pieter Abbeel. End-to-end training of deep visuomotor policies. Journal of Machine Learning Research, 17(39):1-40, 2016.

---

Peng Liao, Zhengling Qi. Runzhe Wan, Predrag Klasnja, and Susan A Murphy, Batch policy learning in average reward markov decision processes. Aunals of statistics, 50(6):3364, 2022.
Boyi Liu, Qi Cai, Zhuoran Yang, and Zhaoran Wang. Neural trust region/proximal policy optimization attains globally optimal policy. Advances in neural information processing systems, 32, 2019.
Zuxin Liu, Zijian Guo, Haohong Lin, Yihang Yao, Jiacheng Zhu, Zhepeng Cen, Hanjiang Hu, Wenhao Yu, Tingnan Zhang, Jie Tan, et al. Datasets and benchmarks for offline safe reinforcement learning. arXiv preprint arXiv:2306. 00t:::00000033,, 2023a.
Zuxin Liu, Zijian Guo, Yihang Yao, Zhepeng Cen, Wenhao Yu, Tingnan Zhang. and Ding Zhao. Con- strained decision transformer for offline safe reinforcement learning. In International Conference on Machine Learning, pages 2-611-0 PMLR, 2023b.
Rémi Munos and Csaba Szepesvári. Finite-time bounds for fitted value iteration. Journal of Machine Learning Research, 95), 2008.
Mirco Mutti, Riceardo De Santi, Piersilvio De Bartolomeis, and Marcello Restelli. Convex reinforee- ment learning in finite trials. Journal of Machine Learning Research, 24(250))1-422 2023.
Angelia Nedié and Asuman Ozdaglar. Subgradient methods for saddle-poin poille-pointttt problems. Journal of optimization theory and applications, 142:205-222 228, 2009.
Asuman E Ozdaglar, Sarath Pattathil, Jiawei Zhang, and Kaiqing Zhang. Revisiting the linear- programming framework for offiin with general function approximation. In International PMLR, 2023.
Conference on Machine Learning, pages
Tom Le Paine, Cosmin Paduraru, Andrea Michi, Caglar Gulcehre, Konrad Zolna, Alexander Novikov, Ziyu Wang, and Nando Freitas. Hyperparameter selection for offline reinforcement learning. arXiv preprint arXi::2007.09055 2020.
Paria Rashidinejad, Banghua Zhu, Cong Ma, Jiantao Jiao, and Stuart Russell. Bridging offline rein- forcement learning and imitation learning: A tale of pessimism. In Advances Neural Information Processing Systems (NeurIPS), volume 34, pages 11702-11716, 2021.
Masatoshi Uehara and Wen Sun. Pessimistic model-based offline reinforcement learning under partial coverage. arXiv preprint arXiv:2107.063: 2021.
Lingxiao Wang, Qi Cai, Zhuoran Yang, and Zhaoran Wang. Neural policy gradient methods: Global optimality and rates of convergence. arXiv preprint 1rXiv:1909.0115:0 2019.
Tengyang Xie and Nan Jiang. Batch value-function approximation with only realizability. In Int. Conf. Machine Learning (ICML), pages 11404-11413. PMLR, 2021.
Tengyang Xie, Ching-An Cheng, Nan Jiang, Paul Mineiro, and Alekh Agarwal. Bellman-consisten pessimism for offline reinforcement learning. Advances in neural information processing systems, 34:6683-6694, 2021.
Haoran Xu, Xianyuan Zhan, and Xiangyu Zhu, Constraints penalized q-learning for safe offline rein- forcement learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 8753-8760, 2022.
Donghao Ying, Mengzi Amy Guo, Yuhao Ding, Javad Lavaei, and Zuo-Jun Shen. Volicy-based primal-dual methods for convex constrained markov decision processes. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pages 10963-10971, 2023.
Chao Yu, Jiming Liu, Shamim Nemati, and Guosheng Yin. Reinforcement learning in healthcare: A survey. ACM Computing Surveys (CSUR), 55(1):1-36, 2021.
Hao Yu and Michael J Neely. A simple parallel algorithm with an o(1/) convergence rate for general convex programs. SIAM Journal on Optimization, 27(2):55--783, 2017.
Tom Zahavy, Brendan O' O'nnggue,,, Guillaume Desjardins, and Satinder Singh. Reward is enough for convex mdps. Advances in Neural Information Processing Systems, 34:25746-25755 257559, 2021.
12

---

Wenhao Zhan, Baihe Huang, Audrey Huang, Nan Jiang, and Jason Lee. Offline reinforcement learning with realizability and single-policy concentrability. In Conference Learning Theory, pages 2730-2775. PMLR, 2022.
Junyu Zhang, Amrit Singh Bedi, Mengdi Wang, and Alec Koppel. Cautious reinforcement learning via distributional risk in the dual domain. arXiv preprint arXiv:2002.12445, 2020a.
Junyu Zhang, Alec Koppel, Amrit Singh Bedi, Csaba Szepesvari, and Mengdi Wang. Variational policy gradient method for reinforcement learning with general utilities. Advances in Neural Information Processing Systems, 33:4572-4583, 2020b.
Yinan Zheng, Jianxiong Li, Dongjie Yu, Yujie Yang. Shengbo Eben Li, Xianyuan Zhan, and Jingjing Liu. Feasibility- safe offline reinforcement learning. In The Twelfth International Conference on Learning Representations, 2023.
Weichao Zhou and Wenchao Li. Safety-awart apprenticeship learning. In Computer Aided Verifica- tion: 30th International Conference, CAV 2018, Held as Part of the Federated Logic Conference, FloC 2018, Oxford, UK, July 14-17, 2018, Proceedings, Part 30, pages 662-680, Springer, 2018.
Hanlin Zhu, Paria Rashidinejad, and Jiantao Jiao. Importance weighted actor-critic for optimal conservative offline reinforcement learning. arXiv preprint arXiv:2301.12714 2023.
13

---

Appendix
A Proof of Theorem 1
In this section, we give the complete proof of Theorem [ constraint violation second. Hence, we first present some auxiliary lemmas and combine them to prove the final theorem.
Specifically, we bound the regret first and
Proof of objective bound
We also decompose the expression by adding and subtracting corresponding terms and prove them individually.
(T (,(T)) f(dax) ) f(d")
f(dTx) f(dk) + -(dd)) f(d")
f(dTx) f(dk) + f(u- wx) f(u w²)
f(dTx) f(dk) + f(u wx) - flDD wx) + f(D Tx) f(p w²)
Next, we will prove these items individually.
Lemma 4, Vw" E W, w" satisfies constraint functionn (6 and 7 with at least 26 probability.
Proof. First, focus the safety constraint Hoeffding inequality:
We prove with Hoeffding inequality. Recall the
2n²t²
P P(X- 2 1) < 2exp
Ci=l (b. a,,²
Take pr w as the random variable, we have
E[(HD 41) w/ =
Since u(s, a) E [0, 1]. and meanwhile lies in [-B Bul, we have (ND ()) lies in interval
[- Bw: Bw]. To satisfy the safety constraint function:
g(PD w) TSK
We set VBB v
Vlog 2|W1
Combine with the Hoeffding inequality, we have
(luD w - p
(17)
For the constraint function, recall we suppose that satisfies the Lipschitz condition, I w) g(u w)l < Lg ll u w|l
Before proceeding to the following derivation, we first state a fact:
( 2 < and y S
Ply
The above equation means that if variable z is greater than t with probability less than equal 8, then any variable such as y that is lower than that variable must also lower than with probability less than equal to 8.
We get
IP ((g(UD w) - g(# w)l 2 Lg t) S
(18)
|W
Note the fact that (NN u w) is obviously lower than
PD w|. then
P (g(Up w) - g(u w) > Lg t) < W
(19)
14

---

Take the union bound for w E W, then
Yu E W, (g((D (olUD-w)-. w) g(v: - w) 2 Lg t) 5
(20)
Then for all w" E W,
(gluD- . w²) g(p . w" 2 وg = 8
(21)
Because w" is the optimal solution for problem (5) 7 and we suppose the assumption realizability set up, then in equation 77. w" satisfies
g(p w ST
Combing with equation 19 get
P (glUD -") - 2 Tig .1) 5
(22)
So we have, with at least 1 - å probability,
((DD - --)--==-----
T S Tug t ==
(23)
Next, we focus on the validity constraint function 66
Here, we take x: T (Kn K'w as the random variable and note the fact that it lies in the interval [~2 2. Use the Hoeffding inequality we have that Va: E B,
2n 2t
P(x (KD -K) 2 t) & exp
(b; 0,
-nt?
exp
(24)
8B2
2B /2 22
Set /
the inequality becomes the form
vn
8
P (x (KD K)w 2 21 s
(25)
Take the union bound for all and x, we have
IP (x (KD K)w 2 t) 2 Ye E W, Vo E X
(26)
So for all w" E W.
fxx (KD K)w" 2) <
(27)
Note the fact |Kw" - -1- m)ll have the inequality for all w" W
P (x (Kow" - (1 - mn) 2 t) 2
(28)
That is, with at least 1 probability,
x (Kow" -(1 7) po) st=
(29)
Take the union bound for equation 23 and (9) completes the proof.
Next, we show that f (JD WD) is close to (μ ww".
Then the empirical covering number nee,, W) defined as the size the smallest e-cover. Intuitively, the cover set can represents the original set in the sense of e. This definition is very useful when the original set continuous and we want take the union bound of it. By this cover can take the union bound of the continuous set and the distance of them is measured by
Lemma 5. We have
f (HD wp) (u w²) V2L,BB. Bu
2|W] log
Vn
8
with 35 probability.
15

---

Proof.
Here we From Lemma
we have
f (ND wp) S (UD - w²)
with probability at least - 28. Now, we use Hoeffding inequality to bound I (uD - w) f (f w).
Take (JID (4) the random variable and note it lies in interval
|- Bws Buc] then we have
2n²t²
P (HD - (e) wl 2t) S exx
Σ Bi=l
(b, a;)²
-ntt
exp
(30)
2
Bu Bu the inequality becomes
Set t
v/
(I 14) w 2 t) S
[W
Use the Lipschitz condition and union bound of w. we have
Vw E W, (f (ND w) (1 w)) 2 L.g 1) 5
(31)
Choose w W and combine with the inequality / (uD . wp) S f (ND w²), ) we get the final result
f (ND wD) S f (1 w²) + v Bw
2
log 8
(32)
vn
with at least 36 probability.
Next, we prove term that f (μ wx) is close to f (uD wx).
Lemma 6. We have
f (u. k.) S (uD wx) + 2T B
2|
vn V log
with probability
Proof. This is easy to prove as we have a general result for all E W equation take Wk W.
IP (f (u wx) - f (uD Wk < 5
(33)
which completes the proof.
Note that W 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 [Ozaallr lar et al. [2023] to get the error bound between validity constraint violation and absolute objective difference.
Lemma 7, Let dx be a variable solved by Program T is the policy induced by dx. We can get that
8 that violates the validity constraint 6 and
2B L (1
(1 7)
with at least 1 8 probability.
Proof. Define the marginalized occupancy measure as dx(ss = EoEA (s, and d = Easa dan (8, a). Then, we can write
dx(s)= = (s
and ( d7x
(34)
aEA
aEA
16

---

Let |1SlI-1 E IR be the state transition matrix, i.e.,
PT (i. -
" Par T(a s²).
aEA
Also, we define the matrix G2 = Diag(Tal: 1 TTl. 1.,,.... Ta(- sl))) E || and notice the fact that MG, = I 7Px. Now, since dn satisfies the constraints in Problem, we have Mdg = (1 7)uo. This implies:
||Mdx (1 - rolll
[lM(dx dax )l1
= || (dx dxx 111
II(1 (dx dx
2 (1 - (1-))](dx- ddxxll 1l1
(35)
Here the last inequality is because P (dx - d 111 S <>ldxx drx 11 which follows from the fact that Px is a column stochastic matrix.
We have:
[f(dx) f(dxx) S Ly|dx daxl
(36)
=T - dxx))
$ L - d= 111.
(37)
The first inequality holds because of the Lipschitz condition of function f. So combining the above two inequalities, we get
L - (1 -1 -7)44llll
f 5
(38)
1-7 L,l|KuK - -11-7)moll
(39)
1-7
which follows the definition of density ratio w. Next, we give the bound of |[wu - (1 - 7)11111 From inequality (26) above have that
P (x (Ko K)w 2 5) 5 Vw E W, Vr e X
Then take ur as wk and x as 1-norm, with least 1 we have
Kwx (1 poll KDkk - (1 7)oll + II(K - KD)wal1ı
<<+<
(40)
where the first incquality is because of the triangle inequality and the last inequality follows the fact that WK is the optimal solution problem (8) and the above inequality. Combining (40) and (38)
completes the proof.
Now, we have the bound of term and II. To further demonstrate the final bound, we also need to investigate the distance between the returned value Wx by primal-dual method and optimal solution WD.
Our algorithm I 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 algorithm
L (w, A, Φ) = f (ND w) + > ( - (1 7)) - () + db (g (ND w) T x))
" k+1 = Pw R - Lno ( * x**)
*++ [1 "/V A [ 1
d++1 1ot (w* A², 00)
17

---

For simplicity, we combine the Lagrange multipliers into one variable and call it v, accordingly, we set the constraint g (w) < Note that constraints are analogous and we would split them in the end. Now the updated rules become
w k+1 Pw [w* 1/ v (w 211) ++1 = PM [ut - C, (w+ []]]
(41)
(42)
where ut M and note that turn the interval of into projection which is equivalent transformation. The Lagrange function is denoted as
L (w, v) - f (w) + ug (w)
(43)
Theorem 2 (Saddle-Point Theorem in [Bertsekas] optimal solution if and only if
1997
The pair (UD,YD) is a primal-dual
L (w>; v) s (WD, uD) s (wr, for all W, v v20,
where wp W and PD 2
The analysis of convergence is based on this theorem and it is standard result that characterizes the primal-dual optimal solutions as the saddle points of the Lagrange function Nedic and Ozdaglar 2009].
Theorem 3. According to the updated rules, denote the solution to problem ( as WK. Compared to the optimal solution WD, we have the upper bound for performance and constraint violation:
2||w1 WDl
2L
(1) 11g (wx)* 1
+
(44)
Kn
VK
[1 WD
112
(2) f(Tk) S
+ +nL²
(45)
2K
where 1j is the constant learning rate, Wi is an initial state, E 2 K is the iteration step and L is the max subgradient of the Lagrange function. Furthermore, we denote, w² = =DD. (Tx) (ND wx) and f = f (pD WD), 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 {wx} and {vk are generated by the updated rules. Then we have
|| w|12 S |lurs - wwll 2n (L (wks uk) - L (w, vk)) + 1) 11 (wks uk) 11? (1) Ve E,
(2) Vv WEE,, M, || - w1/2 < ||s - w112 2n (C (wx, vx) - L (wk: v)) + 17 C (wk, v%) 112
Proof. We prove (I) and (2) is similar to (1).
| w| 2 IP (we nLo (wk, vk)) w/l
< Li nhow (wk, vk) - w|(
wr wll1 2n (wk, vx) (wx w) + Low (wk: Mx) 1|2
I lw w|l2 - 2n (C (Wk, mx) - L (w, vx)) + 1/ Cl (wx, (x) l|2
where the first equality comes from the update rule and the last inequality 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
Cw (Wk, vR) L. [| (wk, Mx) 1l Vk 2620 O.
where L is the max Lipschitz constant in Lagrange function.
18

---

Lemma 9. Set wi
1 3 E Whe and Dy = \/4 Ei=i Day we have
1
| w|l2
n12
(1)
L (W,, u:) L [ww, vx) $
+
Vw W.
2/p
2
1/1 2
nL2
1
(2)
C
(wr, L (T),
M.
2nyk
k i=1
Proof. We only prove (1) and equation (2) is similar to (1). By using Lemma
8
we have
C (wi, v.) L (w,, vz) S |we
w|
|10411 w| +
nL²
27
2
Sum it from to k,
1|11
w0/12 - ||:0R
w012
n1?
(w/, C (w,
+
21
2
||w01
n1..2
+
(46)
27
2
And combine with Ex= L (w, 2 L (w, D2) which is because of Jensen's inequality, have
k h
[w]
w|
nL
(w,,vi) C (w,
+
(47)
2n
2
Assumption 7 (Slater's condition). There exists vector v such that
( < O,
Vj = 1,2, NN
we 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 vector that satisfies Slater's condition, we have
|1l|1 < (10)-
where 7 = min muinsism((9p (w)} and m is the number of constraints.
The proof referred to [Hiriart-Urutt and Lemaréchal 1996). choice of dual set, that is
The lemma above motivates
f(i) á tr] v 2 0
M
where q 5 9" and 2 a constant.
Proof.
Now, we are ready to give the general proof of Theorem 3 we have
Combine LemmaaBand Assumption
| w112 < || w112 -21 (C (wk, vk) L (wk, + 1 (wks Mk) 1|2
(48)
Moreover,
(n - UD) Lu (wis vs) S (wi, vs) L (wi, vD)
< L (wi, v;) - f
(49)
19

---

where the first equation is because of convexity of L, and the last equation dues to the Slater's s condition. We have, Av M and 2
(v-vD) vDD Ly (w: = (v- - 1DD + Vs - vi) Lu (wi, vz)
(v -v,) Lv (wi, 14) + (vi 1/D Lu (w),
|lus 111 |1 - 111 +
nl?
+ L (wi, Uz) -
(50)
2n
2
Then, sum over i = 1, ki
111 u12
nkI
k-1
Σ (v [v vD) L v1) 1=1
+
C (w,, (.) - kf
(51)
2n
2
==0
Because the above function is for all v, then
Σ (v - uD) L (wis, ui)
S max || - -1112
Σ (wi; - kk"" (52)
max VEM
+
2n NEM
2
Set
k
k
Ly (Wi, u1) = Σ (wi) 2 kg (wx)
(53)
[=1
Hence, if s* = 0, equation 52
holds. If st + 0, define vector:
ù = VD + |s+ 2 0
Combine Lemma we have
f
|0l|| S |1 +r
(54)
7
which implies that for E M,
(D - (D-DD) T == Σ (D vD) L (wis v))
1=1
(v -p) L (1), }
S max
Σ
(55)
Recall the definition of s, we have
(0- vp) s s=
Σ 9 (wx)
(v - vp) T L (ws,
r max vE
i=1
max
|| -1122
+
Σ
L (wi,vs) - kf
2n
WEM
2
i=1
||w|
WDl12
I12
(1|21|1
1011)
+
2n DEM
2
277h
1
||
wp
1|2
nL2
||+i| +
+
2n FEM
2
2nk
s (10)
- 7
112
||W]
WD
1|2
T11.2
+
+
+
(56)
2m
7
2
2
2
20

---

Then.
1
nL
2
f [[())
-
2
[gg (Tx)**
#1
||
+
(57)
21yk
2
kmp
Until now, assume the dual set is appropriately chosen in every iteration and should quantify it. For the dual set
S (1))
7 rr
M V 2
0||l||
and the result in 57 We should choose
[11 WD 11?
nL
2 f(0) +
2
min 200
+
2nk
kerp
which is
f [ 9
2
[w uD
knp I
(k) -
Wk 21
So the dual set in every iteration is
( q
1
Mr
+ (R:)
which implies
llg (wx) ) 1+>+++11+ 11
4
f (10)-9) +1 +1
+1(((0))
+
||w1
wD
1
knj² L2
kn
7
7
4
4
4
2 (10) ②
wpl
LLV/
(58)
ryk
2
For simplicity, we take the first term as a constant which doesn't 't affect our result:
21[w1
wpll
2L
lg (wx) + || S E +
+
(59)
kn
V
The result (1) in Theorem 3 completes. Next, we give the bound of the objective value. From the definition of the Lagrange function,
f TT
(w,)
Σ 1=
c
(ws, v.)
Σ (w)) 1
1=1
1=1
Then,
1 *
1 b
f
(
f"
L
(w,, vz)
Σ
9
(wi) 24 f
k 1=1
k
1=1
||
111
1T.
1
Vig (w:)
(60)
277
2
k
Note that
f [(w)
0 M
z 01l|||
Set 0 and combine Lemma we have
|| ||2 < || + 2nvnn (ww) + 122
21

---

Then
2 (wxx S || | 112 + 17² 1,2
Sum over i = 0, 1...., 1, #
L22k
vig (wi) S 21
(1|w)) 122 11-111 122) +
(61)
2
We get the final result,
||111
| wD
1|2
17
(wkk) S +
+
2nj
2xple
which completes the proof of Theorem 3
Then we have the all results to prove the regret bound in Theorem
Theorem indicates that after K iterations the objective and violation bound for problem (8)
are
f (HD wk) S f (MD wD) + | 11
|
WD
12
17
2
+
2Tj
21/
1
1
f wD) +
+
2n/
B
1
[ WD) +
+
(62)
2vK
2K
2 W1
WDll
2L
E
I (KDUK (1 7) po) 5
Kn
VK
VK
2B
2h
=(+
+
(63)
VK
VK
VK
2 21|w0 WDl
2L
g (hp Tx) S T
K1
VK
VK
2B
2L
E
= K
+
(64)
VK
VK
VK
where we set the initial Lagrange values equal to O, the constant step size 7) VK and B is the distance between wi and optimal solution wr.
And recall Lemma 7 we have with least 1 26 probability,
KK - >)olll <|| KD (1 7)Holl 11 + 11(KK
KD WKll1
2 [m] wDl
2L
< VK Kn
(65)
VK
Then, we have, with least 1 probability, the bound is,
J+(TK) J,(TT)
=((dxx) f(dk) + f(u wK) f(UD wx) + f(D Wx)
-[(dxx) ) - -((xx) + f(u-wwk f(UD wxx + f(p wx) S(UD WD) + s(u wD) - f(po w
III
< T.f.
22 2(W1 log
B²
||WWK- - (1 7)Holl1 +
5 +
1 1-1
nn
2/K
1,2
V2
2|W]
+
log 5
2K
Vn
22

---

6 B
2 X
2B
2L
B
L
log
1-7
Vni
VK
VK
2vK
2K
VK
1
66/2L Bw
2/W X
log
1-7
Vn
5
2VK K
S O(I/T)) + +01/VK)
where we 4B 4L
B
L VK
+E.
Proof of violation bound
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 of Lemma
Proof. This proof is quite similar Lemma since we always want 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 which is
|M (1 ooll [M drx)lli
2 (1 >)1ddx d=xll1-
(66)
Then for the safety constraint function, have
lg(dx) g(d
S Lgldx d=xl
(67)
= L (dx - dixx)
s Ly [gl - d=x I11-
(68)
where the first inequality is because Lipschitz condition of the safety constraint function. Also by combining the above functions, we have
g(dk) g(dTx))== S LgllMdx - (1 (1-7) Holll
(69)
1-7 L KulK - (1 - -1)mol1
(70)
1-
And in Lemma 7 we have already established the bound of |KWK - - -)oooll then with least
1 - 25 probability
g(dk) g(dxx)+ 2L Bu / log W| x1/88)
(1-7)vm
which completes the proof.
Proof of Lemma 2
Proof. In this lemma. actually, will prove that (μ wx) is close to (pD Wk). We take
(μ (DD) w as the random variable and lies in [-Bm, Bm.. We have the Hoeffding inequality
(- Ei
2n
5
PP (Iu w - uD w| 2 1) S 2 2exp
(71)
(b. a,)3
[
where set t for g, we have
B vn
log
2
Next, take the union bound for w and use the Lipschitz condition
Vw E W,
(g (uD w) g (μ w) > Lg t) 5
(72)
So for wk E W,
P (g (uD wK) g (n TK) Ly <
(73)
23

---

which means that with at least 1 - probability,
S V2LgBB. vnn
2 2|
(JD wx) (1x - ..)
log
The proof is complete. Proof of Lemma
Proof. This lemma is easy to be verified because we choose the relax parameter k is equal to log 2wi and recall the result in Theorem which completes the proof.
v/2r,, B Vn
Thus, take the Lemma 2 and together, we have, with at least 1 36,
Je(Tk)
g(dxx) g(dx) + g(p wx) I(PD wK)
g(MD wD)
Lg
|KWKK (1 7)olll + v2B w
2
2B
2L
-
log
+ K
1 7
VTi
8
VK
VK
VK
GV2L,B
V Vlog
log
2|
2B
2L
2B
2L
9
1 1-7
vn
K
VK
VK K
VK
V K
VK
6v GV
log
(1 - 7)
K
$ (11/111) + +(11/K))
where we set
-
(4B 4L + 2z) which completes the proof.
B
Experiments
We introduce practical version of our primal-dual algorithm, following the key structure in Algorithm 1 We utilize this algorithm conduct various experiments this paper.
Algorithm 2: Practical version of POCC
Input: Dataset D) = {(s, Q,, Fi, 4) cost threshold т, learning rate 7), Tao No. relaxed parameter Ç, K.; Initialize network of importance weight Wpi
for k 1,,,...,k do Jointly optimize:
w k+1 Adam (w no (L X+ (t)
A k+1 Adam (X* VA VL ; d, (bt).
x++1 Adam (o* 7/ VI. 2 .b))
5 Compute the importance weight: V(8, a), w(s,a) = wp (8, a):
Extract the policy: T(a s) Evtes wy (ol 161
Output: Policy x:
Hyperparameters In the experiments of maze and FrozenLake environments, we set the discount factor as 7 = 0.99 and the cost threshold as т = 0. indicating that the agent is not supposed to incur any cost. For our algorithm and COptiDICE [Lee et al. 2021], we perform grid search on the set (0.00001, 0.00005, 0.0001, 0.0005, 0.001, 0.005} determine the learning rate for parameters. We ultimately select Icarning rate of 0.00001 for the neural network and Lagrange scalar learning
24

---

rate of 0.0001. We set Ç 0.1 and K 0.001 in our algorithm, and we set a = 0.5 in COptiDICE. In both environments. we run the algorithm for 100000 iterations ensure model convergence. Additionally, we use fully-connected neural networks with single hidden layer of width 64.
Continuous environments We also run list of experiments in SyfetyGym with offline datasets provided by (Liu et al. 2023a] and compare with comprehensive baselines (e.g.. CPQ in [R5]. PDCA [R4], CoptiDICE [R6], and BEAR-Lagrangian [R7]. [R8]). Note that only PDCA and our algorithm provide theoretical results. In these experiments, to deal with the continuous state-action space, we use the fully connected single hidden-layer neural network of width 128 to represent w. We summarize the evaluation results in the following table. All the rewards and costs normalized and the cost threshold is Each value is averaged over 20 evaluation episodes and random seeds.
Table 2: All the rewards and costs are normalized. The cost threshold is 1. Blue: Safe agents with the highest reward.
COptiDICE Rewardd Cost]
CPQ
BEAR-Lag RReward, Cost]
PDCA Rewardd Cost]
Ours [Reward, Cost]
Task
[Reward, Cost
AntRun
0.6, 0.94
[0.03, 0.02]
0..15, 0.73
[0.28, 0.93]
[0.6. 0.01]
CarRun
00.87, 0.0
[0.95, 1.79
[0.68, 7.78
[0.91, 0.0]
[0.90,
BallRun
0.59, 3.52
[0.22, 1.27
[00.77, 5.03)
3.38
00.24,
BallCirele
0.770, 2.61
[0.64, 0.76
00866, 3.09]
0.63, 2.29.2229
0.39.. 0.93
CarPush1
[0.23, 0.5]
--003, 0.95]
[0.21, 0.54]
00.17.0.41]
[0.20, 0.4]
Compute setting
We run the experiments with NVIDIA GeForce RTX 3080 Ti 8-Core Processor:
25

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Claims in the abstract and introduction accurately reflect our paper's contribu- tions.
Justification:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We include the limitations in our assumptions.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
26

---

Justification:
We provide proof sketch of our theorem in the main paper and complete the full proof in the supplemental material.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof's can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification:
We disclose all the information needed reproduce the main experiments.
Guidelines:
The answer NA means that the paper does include experiments. If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
27

---

Answer: [Yes]
Justification:
We provide the data and code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cm
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ ccpppp.ccppulli//uuuii wwwticccguie//eeiee CoodeSubeiiieeee ssi wswonnolli onnolicy)))) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
We specify the experimental settings in the supplemental material.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification:
We report error bars correctly in the paper.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
28

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of exccution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We provide the sufficient information on the computer resources.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well 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 failed experiments that didn't make into the paper).
9. Code Of Ethics
Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics ptttps://eeurip... http://.....cp..bctctcccccciceaa
Question:
Answer: [Yes]
Justification: Ethics.
The research conducted in this paper conform with the NeurIPS Code of
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g.. if there is special consid- cration due to laws or regulations their jurisdiction..
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
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 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.
29

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is 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 being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there 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 monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have 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 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 best faith effort.
12. Lieenses for existing assets
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?
Question:
Answer: [Yes]
Justification: We cite the original paper and abide by the license.
Guidelines:
The answer NA means that the paper does not 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 URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.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, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of 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.
30

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets,
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
31


Reviews:
[{"review_id": "nyL6g8xUt6", "reviewer": "Reviewer_61FL", "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.", "questions": "-- line 181, how large the dataset has to be in order for (8)-(10) to be close to (5)-(7)?\n\n-- When w is parametrized by a neural network, does the proposed formulation satisfy all the assumptions made?", "limitations": "see weakness", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "This paper studies a very interesting and important topic in the RL community. The writing is clear and the results are well presented.", "weaknesses": "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.\n\nFurthermore, 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.\n\nWhile 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We greatly appreciate the reviewers' detailed comments. Please find our point-by-point response to your questions below.\n\n**Concern of the novelty of the contributions**:  We would like to emphasize that we are the first to study offline convex CMDPs and provide state-of-the-art theoretical results under mild assumptions. \nThere are only a few theoretical studies on the offline (linear) CMDPs [R1, R2, R3]. However, these papers either need strong assumptions (full data coverage, Bellman completeness) or can not combine with the general function approximation settings. For this purpose, we develop an efficient algorithm that only needs partial data coverage and meanwhile achieves state-of-the-art theoretical results with general function approximation. The assumption of weak data coverage, the ability to handle large state-action spaces, and the best theoretical results are important aspects that were not addressed in previous works. We would also like to emphasize that the partial data coverage assumption is extremely important in the CMDP setting. A full coverage assumption would mean that each state and action should be covered by the dataset, including the most dangerous states and actions, which is unrealistic and undesirable.\n\n**The proposed formulation appears to be a direct extension of the setup in prior work [26]**: The prior work [26] does not consider the cost function in their formulation. Note that adding the cost function makes the problem more challenging and significantly different from the unconstrained setting. For example, the optimal policy is no longer a greedy policy, as a trade-off needs to be made between reward and costs. This is why CMDP problems are usually much more difficult. In addition, when safety constraints are considered, the gap between program (5)-(7) and approximate program (8)-(10) changes and is unknown in the previous work. Second, extending the program (5)-(7) to program (8)-(10) directly leads to suboptimal results. Finally, the optimal rate of sample complexity is still unknown when considering safety constraints. We focus on answering these questions in our paper.\n\n**The experimental evaluation is limited in the paper**: As our paper is primarily on the theory side, the experiments are used to justify the theoretical results, including the data coverage, function approximation assumption, and the result of sample complexity of our algorithm. According to the comprehensive experiments in [R3] and [R4], CoptiDICE is the most stable and effective algorithm, so we consider CoptiDICE as the baseline in our submission.\n\nBut, following the reviewer's suggestions, we conduct a list of experiments in a popular, challenging, and continuous environment--SafetyGym with comprehensive baselines (e.g., CPQ in [R5], PDCA in [R3], CoptiDICE in [R4], and BEAR-Lagrangian in [R6], [R7]). Note that only PDCA and our algorithm provide theoretical results. In these experiments, to deal with the continuous state-action space, we use the fully connected single hidden-layer neural network of width 128 to represent $w$.\n\nWe summarize the evaluation results in the following table. All the rewards and costs are normalized. The cost threshold is 1. Each value is averaged over 20 evaluation episodes and 3 random seeds. \n\n| **Task**     | **COptiDICE** |                | **CPQ**    |                | **BEAR-Lag** |                | **PDCA**   |                | **Ours**   |                |\n|--------------|---------------|----------------|------------|----------------|--------------|----------------|------------|----------------|------------|----------------|\n|              | **[Reward, Cost]** |             | **[Reward, Cost]** |           | **[Reward, Cost]** |           | **[Reward, Cost]** |           | **[Reward, Cost]** |           |\n| **AntRun**   | **[0.6, 0.94]** |       | [0.03, 0.02] |      | [0.15, 0.73] |     | [0.28, 0.93] |    | **[0.6, 0.01]** |   |\n| **BallRun**  | [0.59, 3.52] |       | [0.22, 1.27] |      | [-0.47, 5.03] |     | [0.55, 3.38] |    | **[0.24, 0.0]** |   |\n| **BallCircle** | [0.70, 2.61] |     | **[0.64, 0.76]** |      | [0.86, 3.09] |     | [0.63, 2.29] |    | [0.39, 0.93] |  |\n| **CarPush1** | [0.23, 0.5] |        | [-0.03, 0.95] |     | **[0.21, 0.54]** |     | [0.17, 0.41] |   | [0.20, 0.4] |  |\n| **CarRun**   | [0.87, 0.0] |       | [0.95, 1.79] |      | [0.68, 7.78] |     | [0.85, 0.0] |          | **[0.90, 0.0]** |   |\n\nThe results show our algorithm is the only one to guarantee safety across all environments. In AntRun, BallRun, and CarRun tasks, our algorithm can achieve the highest reward and small cost among all baseline algorithms. \nNote our algorithm is very flexible to incorporate more sophisticated function approximations (e.g., deeper and more advanced neural networks) to potentially achieve better empirical performance. \n\n**How large the dataset has to be in order for (8)--(10) to be close to (5)--(7)?**: Our theoretical results in Theorem 1 show (8)--(10) will ``converge to'' (5)--(7) with the rate of $\\mathcal O(1/\\sqrt{n})$, where $n$ is the size of dataset. \n\n**When w is parametrized by a neural network, does the proposed formulation satisfy all the assumptions made?**: Yes. When $w$ is parameterized by a neural network, Assumption 2 (Realizability Assumption) can be satisfied by choosing proper network parameters. In Assumption 3 (Completeness Assumption), the operator $\\phi(w)$ or $x$ aims to calculate the $l_1$ norm of constraint function $Kw - (1-\\gamma)\\mu_0$. The completeness assumption is set up if $l_1$ norm of the constraint function exists, and it works for the case that $w$ is a neural network. In Assumption 4 (Boundness Assumption), if the output of the neural network $w$ is bounded, the assumption is also satisfied.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ckPQFWQSpg", "reviewer": "Reviewer_Za97", "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.", "questions": "Please see the weaknesses above.", "limitations": "Please see the weaknesses above.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1.\tThe studied problem, i.e., safe offline RL in convex MDPs, is well-motivated and can be applied to autonomous driving, robotics, etc. \n2.\tThe authors design a novel linear programming based primal-dual algorithm for convex MDPs under only the partial coverage assumption, instead of the full coverage assumption. The authors also provide sample complexity for this algorithm, which improves the current result by a factor of $1/(1 − \\gamma)$.\n3.\tEmpirical evaluations are also presented to validate the practical efficacy of the proposed algorithm.", "weaknesses": "1.\tCan 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?\n2.\tDoes the algorithm need to know the behavior policy $\\mu(a|s)$ in advance (in Eq. (12))? This is not a practical assumption.\n3.\tThe 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.\n4.\tWhat are the technical challenges and novelty in the offline convex MDP (RL) problem, compared to the existing online convex MDP (RL) works?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your positive feedback and detailed comments on our paper. We will respond to the major concern in the following.\n\n**Need more explanations on Assumptions 2-4 and the reason for introducing the set $\\mathcal W$ and $\\mathcal X$.**: Assumption 2 assumes the optimal policy $\\pi^*$ $(w^*)$ is included in the function class $\\mathcal W.$ It means (5)--(7) (with $w \\in \\mathcal W$) is a proper baseline as it includes the optimal policy. Assumption 3 is a completeness-type assumption. Operator $\\phi(w)$ or $x$ aims to calculate the $l_1$ norm of the constraint function $Kw - (1-\\gamma)\\mu_0$. It assumes that for all $w \\in \\mathcal W$, $l_1$ norm of the constraint function exists and thus can be used to calculate the constraint violation (or called Bellman error). Only when the constraint violation is a computable quantity can we relax the equality constraint (6) and obtain an approximate program (8)-(10). Assumption 4 is a standard assumption in offline RL that assumes the boundness of function classes $\\mathcal W$ since we always do not want variable $w$ to be infinite.\n\nThe introduction of set $\\mathcal W$ and $\\mathcal X$ helps our analysis. In our algorithm, we want to measure the distance between program (5)-(7) and the approximate program (8)-(10). So if we assume the optimal solutions to program (5)-(7) and program (8)-(10) are in the same function class $\\mathcal W$, the distance between the above two programs can be directly in function class $\\mathcal W$. Moreover, $x \\in \\mathcal X$ is used to calculate the $l_1$ norm of the constraint function and further measure the constraint violation as we state above. Actually, we do not need to know set $\\mathcal W$ and $\\mathcal X$ in advance since they are used for the sake of analysis. \n\nThank you for your advice, we will further explain this in our paper. \n\n**Does the algorithm need to know the behavior policy in advance?**: The algorithm does not need to know the behavior policy $\\mu(a | s)$ in advance. For ease of exposition, we assume the behavior policy is known. When it is unknown in practice, behavior clone is an effective approach to extract the behavior policy from the dataset. Specifically, we can estimate the learned behavior policy $\\hat{\\pi}$ by $\\hat{\\pi} (a | s) = \\frac{n(s,a)}{n(s)}$, where $n(s,a)$ is the number of $(s,a)$ state-action pairs in the offline dataset. It can be shown that the gap between the learned policy $\\hat{\\pi}$ and the real behavior policy $\\pi_\\mu$ is upper bounded by $\\min ( 1, |\\mathcal S| / n )$ [R1], which does not affect our sample complexity. Furthermore, the experiments in our paper do not assume the behavior policy and utilize the behavior clone to estimate the behavior policy, where our algorithms also achieve great results.\n\n**More comparison to the existing results for offline (linear) constrained RL**: In theory, our algorithm achieves state-of-the-art results with general function approximation under partial data coverage. However, in previous works, [R2] proposes a meta-algorithm combining with general function approximation but achieves $\\mathcal O \\left( \\frac{1}{(1-\\gamma)^5 \\sqrt{n}}\\right)$ sample complexity under the strong Bellman completeness assumption. [R3] also focuses on occupancy measures but their algorithm can just apply to discrete state-action spaces. The most related work [R4] approaches the problem from the perspective of the Actor-Critic algorithm, analyzing the sample complexity to be $\\mathcal O \\left( \\frac{1}{(1-\\gamma)^2 \\sqrt{n}}\\right)$ under a stronger full data coverage assumption. \n\nIn experiments, following the reviewer's suggestions, we conduct a list of experiments in the challenging and continuous environment--SafetyGym with comprehensive baselines (e.g., CPQ in [R5], PDCA in [R4], CoptiDICE in [R6], and BEAR-Lagrangian in [R7], [R8]). Note that only PDCA and our algorithm provide theoretical results. In these experiments, to deal with the continuous state-action space, we use the fully connected single hidden-layer neural network of width 128 to represent $w$.\n\nWe summarize the evaluation results in the following table. All the rewards and costs are normalized. The cost threshold is 1. Each value is averaged over 20 evaluation episodes and 3 random seeds. \n\n|**Task**|**COptiDICE**||**CPQ**||**BEAR-Lag**||**PDCA**||**Ours**||\n|-|-|-|-|-|-|-|-|-|-|-|\n||**[Reward,Cost]**||**[Reward,Cost]**||**[Reward,Cost]**||**[Reward,Cost]**||**[Reward,Cost]**||\n|**AntRun**|**[0.6,0.94]**|| [0.03,0.02]||[0.15,0.73]||[0.28,0.93]||**[0.6,0.01]**||\n|**BallRun**|[0.59, 3.52]||[0.22,1.27]||[-0.47,5.03]||[0.55,3.38]||**[0.24,0.0]**||\n|**BallCircle**|[0.70,2.61]||**[0.64,0.76]**||[0.86,3.09]||[0.63,2.29]||[0.39,0.93]||\n|**CarPush1**|[0.23,0.5]||[-0.03,0.95]||**[0.21,0.54]**||[0.17,0.41]||[0.20,0.4]||\n|**CarRun**|[0.87,0.0]||[0.95,1.79]||[0.68,7.78]||[0.85,0.0] ||**[0.90,0.0]**||\n\nThe results show our algorithm is the only one to guarantee safety across all environments. In AntRun, BallRun, and CarRun tasks, our algorithm can achieve the highest reward and small cost among all baseline algorithms. \nNote our algorithm is very flexible to incorporate more sophisticated function approximations (e.g., deeper and more advanced neural networks) to potentially achieve better empirical performance. \n\n**The challenge between online convex MDP and offline convex MDP.**: We think the main challenge between online convex MDPs and offline convex MDPs lies in data, including data quality and data assumptions. For example, in R[9], they propose a method that uses standard RL algorithms to solve convex MDPs. However, in the offline setting, each RL algorithm has its own data assumption. It is challenging to satisfy all data assumptions of these algorithms, so many online convex MDP algorithms can not apply to the offline setting directly.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "EMWMKL7huo", "reviewer": "Reviewer_9gP2", "summary": "This paper investigates batch RL with safety constraints and function approximation, which is a question of both theoretical and practical importance.", "questions": "Q1. Is there a relationship between the proposed primal-dual update rules and the actor-critic algorithms?\n\nQ2. 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.\n\nQ3. The class X does not appear in the algorithm. Is it introduced purely for the sake of analysis?", "limitations": "N/A", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "The assumptions considered in this paper are less restrictive compared to previous works. In particular, most previous works consider linear objective, and this paper relaxes linearity to convexity, which makes the results apply to a broader class of learning problems (e.g. batch RL with entropy regularization). It is also good to see the experimental results.", "weaknesses": "(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?\n\n(2) There is an unstated assumption: the convergence of the proposed algorithm actually relies on the convexity of W (Lemma 8).  \n\n(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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your insightful comments. We would like to address your concerns point by point.\n\n**The class $\\mathcal X$ is not well-explained**: In Assumption 3, operator $\\phi(w)$ or $x$ aims to calculate the $l_1$ norm of the constraint function $Kw - (1-\\gamma)\\mu_0$. It assumes that for all $w \\in \\mathcal W$, $l_1$ norm of the constraint function exists and thus can be used to calculate the validity constraint violation (or called Bellman error). Only when the constraint violation is a computable quantity can we relax the equality constraint (6) and obtain an approximate program (8)-(10). So class $\\mathcal X$ is used to depict the validity constraint violation and simplify our analysis. We will add this explanation to our paper.\n\n**The convergence of the proposed algorithm relies on the convexity of $\\mathcal W$**: Thank you for your detailed discussion and we will add this to our revision. In fact, if we want program (8)-(10) to be computationally tractable, function class $\\mathcal W$ is supposed to be convex. However, when $\\mathcal W$ is not convex, the operation of convexification on function class $\\mathcal W$ is reasonable and common in offline safe RL [R1, R2]. Even if $w$ is parameterized by the neural network, as studied in [R3], when the neural network is over-parameterized, it would have some almost convex properties such that stochastic gradient descent (SGD) can find global minima on the training objective of neural networks. Thus in our algorithm, if the neural network is over-parameterized, it will also have the property of convergence.\n\n**Question about the log-cardinality of the function class $\\mathcal W$**: In our paper, we do not assume the function class $\\mathcal W$ is finite. When $\\mathcal W$ is a continuous set, the cardinality represents the covering number or the number of extreme points of the function class [R4], and it does not affect our results.\n\n**Relationship between the proposed primal-dual update rules and the actor-critic algorithm**: We think that our algorithm can be viewed from the perspective of actor-critic in some sense. For example, as studied in [R5, R6, R7], in the LP formulation of CMDP, the Lagrange multipliers of Bellman flow constraints are value functions. Because the value function is the dual variable of the occupancy measure in LP formulation. So the Lagrange multiplier $\\lambda$ in our algorithm refers to the critic in actor-critic algorithm. And $w$ refers to the actor in actor-critic algorithm since $w$ equals to the occupancy measure in some sense and represents the policy in our algorithm.\n\n**The Lipschitiz constant $L$ and the prior knowledge on concentrability constant**: The Lipschitz constant $L$ is defined in the appendix and it is the upper bound of $L_f$ and $L_g$. And $B_w$ actually requires prior knowledge on the concentrability constant. Thank you for your detailed advice and we will add these to our paper.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "7FFmIzox1F", "reviewer": "Reviewer_H1LM", "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.", "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.\n> Besides, our algorithm is appropriate in the scenario with large-scale state-action space\n- 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": "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.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Offline convex CMDPs are promising formulation that covers wide-ranging problems including safe imitation learning or standard offline CMDPs.\n- The theoretical results are strong. The sample complexity is improved by $1-\\gamma$ compared to the SOTA, which is an important contribution to the offline safe RL community. The assumptions the authors make are 1) concentrability of the optimal policy, 2) realizability, 3) completeness, 4) Boundness of $\\mathcal{W}$ and $\\mathcal{X}$, and 5) Lipschitz continuity of the $f$ and $g$. Though the number of assumptions is large and each assumption is strong, all of them are standard assumptions in previous work and we understand that it is almost impossible to prove sample complexity without them.\n- While this paper is highly theoretical, the authors also provide empirical results. I think it is nice to evaluate their algorithm in two settings: safe imitation learning and offline safe RL.", "weaknesses": "- 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.\n- 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.\n\n**Minor Comments and Typos**\n- Line 45: The following sentence seems weird to me. Should this be \"We formulate ...\"?\n    - \"We for the first study the offline.\"\n- Figure 3: (a), (b), ..., (d) do not exist in Figure 3 while they are mentioned in the caption.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your positive feedback on our paper! We appreciate your support and comments. We'd like to respond to the major comments in the following.\n\n**The experiments are toy examples and have limitations when extending to complicated continuous state-action space.**: As our paper is primarily on the theory side, the experiments are used to justify the theoretical results, including the data coverage, function approximation assumption, and the sample complexity of our algorithm. According to the comprehensive experiments in [R1] and [R2], CoptiDICE is the most stable and effective algorithm, so we consider CoptiDICE as the baseline in our submission.\n\nBut, following the reviewer's suggestions, we conduct a list of experiments in the challenging and continuous environment--SafetyGym with comprehensive baselines (e.g., CPQ in [R3], PDCA in [R1], CoptiDICE in [R2], and BEAR-Lagrangian in [R4], [R5]). Note that only PDCA and our algorithm provide theoretical results. In these experiments, to deal with the continuous state-action space, we use the fully connected single hidden-layer neural network of width 128 to represent $w$.\n\nWe summarize the evaluation results in the following table. All the rewards and costs are normalized. The cost threshold is 1. Each value is averaged over 20 evaluation episodes and 3 random seeds. \n\n|**Task**|**COptiDICE**||**CPQ**||**BEAR-Lag**||**PDCA**||**Ours**||\n|-|-|-|-|-|-|-|-|-|-|-|\n||**[Reward,Cost]**||**[Reward,Cost]**||**[Reward,Cost]**||**[Reward,Cost]**||**[Reward,Cost]**||\n|**AntRun**|**[0.6,0.94]**|| [0.03,0.02]||[0.15,0.73]||[0.28,0.93]||**[0.6,0.01]**||\n|**BallRun**|[0.59, 3.52]||[0.22,1.27]||[-0.47,5.03]||[0.55,3.38]||**[0.24,0.0]**||\n|**BallCircle**|[0.70,2.61]||**[0.64,0.76]**||[0.86,3.09]||[0.63,2.29]||[0.39,0.93]||\n|**CarPush1**|[0.23,0.5]||[-0.03,0.95]||**[0.21,0.54]**||[0.17,0.41]||[0.20,0.4]||\n|**CarRun**|[0.87,0.0]||[0.95,1.79]||[0.68,7.78]||[0.85,0.0] ||**[0.90,0.0]**||\n\nThe results show our algorithm is the only one to guarantee safety across all environments. In AntRun, BallRun, and CarRun tasks, our algorithm can achieve the highest reward and small cost among all baseline algorithms. \nNote our algorithm is very flexible to incorporate more sophisticated function approximations (e.g., deeper and more advanced neural networks) to potentially achieve better empirical performance. \n\n**Question about SOTA sample complexity**: We think the most important reason that we can achieve the SOTA sample complexity is that our algorithm is direct enough. Our algorithm actually is to measure the distance between program (5)-(7) and the approximate program (8)-(10). In our proof, the discounted factor $\\gamma$ only exists in Lemma 2 which depicts the distance between the reward and the constraint violation. However, most previous works are more complex compared with ours. For example, the paper [R1] has to use two oracles in their algorithm, introducing additional factors $(1-\\gamma)^{-1}$, which makes their result weaker than ours.\n\n**Minor comments and Typos**: Thank you for your detailed read and we will fix it in our paper.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: 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.
Decision: Accept (poster)