mlsanityData to 7 Oct 2026

A Near-Optimal Primal-Dual Method for Off-Policy Learning in CMDP

arXiv 2207.06147 ↗First posted 13 Jul 2022cs.LG cs.AI stat.MLcited by 5

Not on the map. Why?

Abstract (arXiv)

As an important framework for safe Reinforcement Learning, the Constrained Markov Decision Process (CMDP) has been extensively studied in the recent literature. However, despite the rich results under various on-policy learning settings, there still lacks some essential understanding of the offline CMDP problems, in terms of both the algorithm design and the information theoretic sample complexity lower bound. In this paper, we focus on solving the CMDP problems where only offline data are available. By adopting the concept of the single-policy concentrability coefficient C^*, we establish an Omegaleft(fracminleft|S||A|,|S|+Iright C^*(1-γ)3ε2right) sample complexity lower bound for the offline CMDP problem, where I stands for the number of constraints. By introducing a simple but novel deviation control mechanism, we propose a near-optimal primal-dual learning algorithm called DPDL. This algorithm provably guarantees zero constraint violation and its sample complexity matches the above lower bound except for an tildeO((1-γ)-1) factor. Comprehensive discussion on how to deal with the unknown constant C^* and the potential asynchronous structure on the offline dataset are also included.

Key facts. Cited by 5 papers in the map (data through 7 Oct 2026). Builds on 21 of its 36 references that are in the map. First posted on arXiv 13 Jul 2022.

Builds on

21 of 36 references.

References · 21

  1. 2021Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimismcited by 275
  2. 2019Batch Policy Learning under Constraintscited by 242
  3. 2021Policy Finetuning: Bridging Sample-Efficient Offline and Online Reinforcement Learningcited by 157
  4. 2020Exploration-Exploitation in Constrained MDPscited by 146
  5. 2020Provably Efficient Safe Exploration via Primal-Dual Policy Optimizationcited by 131
  6. 2020Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reductioncited by 93
  7. 2021Constraints Penalized Q-learning for Safe Offline Reinforcement Learningcited by 90
  8. 2022Pessimistic Q-Learning for Offline Reinforcement Learning: Towards Optimal Sample Complexitycited by 84
  9. 2022Settling the Sample Complexity of Model-Based Offline Reinforcement Learningcited by 82
  10. 2021Learning Policies with Zero or Bounded Constraint Violation for Constrained MDPscited by 78
  11. 2021Towards Instance-Optimal Offline Reinforcement Learning with Pessimismcited by 78
  12. 2021Near-Optimal Offline Reinforcement Learning via Double Variance Reductioncited by 56
9 more
  1. 2020Upper Confidence Primal-Dual Reinforcement Learning for CMDP with Adversarial Losscited by 46
  2. 2021Achieving Zero Constraint Violation for Constrained Reinforcement Learning via Primal-Dual Approachcited by 46
  3. 2022The Efficacy of Pessimism in Asynchronous Q-Learningcited by 41
  4. 2017Primal-Dual π Learning: Sample Complexity and Sublinear Run Time for Ergodic Markov Decision Problemscited by 32
  5. 2021Provably Efficient Algorithms for Multi-Objective Competitive RLcited by 20
  6. 2020Cautious Reinforcement Learning via Distributional Risk in the Dual Domaincited by 18
  7. 2021Concave Utility Reinforcement Learning with Zero-Constraint Violationscited by 18
  8. 2021Efficient Performance Bounds for Primal-Dual Reinforcement Learning from Demonstrationscited by 9
  9. 2021A Stochastic Composite Augmented Lagrangian Method For Reinforcement Learningcited by 2

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 1; 2024: 3; 2025: 0; 2026: 1.

5 papers.

  1. 2024Temporal Logic Specification-Conditioned Decision Transformer for Offline Safe Reinforcement Learningcited by 10
  2. 2023A Primal-Dual-Critic Algorithm for Offline Constrained Reinforcement Learningcited by 9
  3. 2024Adversarially Trained Weighted Actor-Critic for Safe Offline Reinforcement Learningcited by 4
  4. 2024SaVeR: Optimal Data Collection Strategy for Safe Policy Evaluation in Tabular MDPcited by 1
  5. 2026Near-Optimal Sample Complexity for Online Constrained MDPscited by 1