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

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

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

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

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

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

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.

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.

But, 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$.

We 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.

The 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. Note 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.

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.

Minor comments and Typos: Thank you for your detailed read and we will fix it in our paper.

Thank you for your insightful comments. We would like to address your concerns point by point.

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.

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.

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.

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.

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.

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

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

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

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

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

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

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

Thank you for your response. Some comments:

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

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

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

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

Of course, this is a relatively minor issue. However, you shall admit that it is a mistake, instead of denying it.

[R1]: Aviral Kumar, Joey Hong, Anikait Singh, and Sergey Levine. "Should i run offline reinforcement learning or behavioral cloning?" In International Conference on Learning Representations, 2021.

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

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

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

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

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

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

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

[R9]: Tom Zahavy, Brendan O’Donoghue, Guillaume Desjardins, and Satinder Singh. "Reward is enough for convex mdps." Advances in Neural Information Processing Systems, 34:25746–25759, 2021.

Thank you for your positive feedback and detailed comments on our paper. We will respond to the major concern in the following.

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.

The 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.

Thank you for your advice, we will further explain this in our paper.

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.

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.

In 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$.

We 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.

The 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. Note 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.

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.

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

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

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

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

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

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

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

We greatly appreciate the reviewers' detailed comments. Please find our point-by-point response to your questions below.

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. There 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.

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.

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.

But, 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$.

We 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.

The 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. Note 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.

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.

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.