Research map / Reinforcement learning / MDPs and planning
Safe and Efficient: A Primal-Dual Method for Offline Convex CMDPs under Partial Data Coverage
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes POCC, a primal-dual LP-based method for offline convex CMDPs under partial (pi*-only) data coverage, with uncertainty-relaxed constraints achieving O(1/((1-γ)√n)) sample complexity under general function approximation.
Problem
Offline safe RL and convex CMDPs with function approximation typically require full data coverage over all policies, which is impractical when dangerous state-actions must be covered; theory for offline convex MDPs was lacking.
Approach
Reformulate offline convex CMDP with marginalized importance weights, relax the empirical Bellman-flow and safety constraints by data-dependent "uncertainty" parameters (zeta, kappa), and solve the resulting problem with a primal-dual gradient method under only pi*-concentrability and a completeness assumption.
Key results
- Theory: with probability at least 1-8δ, objective and constraint violation bounds are O(1/((1-γ)√n)) + O(1/√K), improving prior offline CMDP sample complexity by a factor of 1/(1-γ).
- On FrozenLake with completely random data (p=0), POCC consistently finds the optimal safe path while COptiDICE fails to learn a safe policy when most data is random and constraint-violating.
- On SafetyGym, POCC attains cost 0.0 on CarRun and BallRun-type tasks with reward 0.90 on CarRun, but has higher cost than some baselines on BallCircle (0.93 vs 0.76 for CPQ) and AntRun reward 0.6 with cost 0.01.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use POCC instead of COptiDICE | Offline safe RL · AntRun | cost: 0.94 -> 0.01 | Helped |
| Use POCC instead of PDCA | Offline safe RL · CarRun | reward: 0.91 -> 0.90 | Hurt |
| Use POCC instead of PDCA | Offline safe RL · BallRun | cost: 3.38 -> 0.0 | Helped |
| Use POCC instead of CPQ | Offline safe RL · BallCircle | reward: 0.64 -> 0.39 | Hurt |
| Use POCC instead of CPQ | Offline safe RL · CarPush1 | reward: -0.03 -> 0.20 | Helped |
| Use partial data coverage and general function approximation in POCC | Offline CMDPs · Theoretical sample complexity | sample complexity: O(1/(1−γ)2√n) -> O(1/(1−γ)√n) | Helped |
Surprising findings
- The algorithm finds the optimal safe path even when the offline dataset is completely random and safety-violating.
- The paper's result is an O(1/√n) rate matching the best-known offline CMDP bound, reached with partial coverage rather than full coverage.
Limitations
- Requires Slater's condition, completeness of the function class, and convexified function classes (strong assumptions).
- The rate is O(1/√K) in the optimization term, so the O(1/√n) rate holds only when K≥n; the practical version uses Adam and behavior cloning for unknown behavior policy without theory.
- Experiments are small (FrozenLake, maze) plus a limited SafetyGym comparison with mixed results; no code release stated.
Experimental setup
Datasets: FrozenLake offline data from mixed optimal/uniform behavior policies maze expert demonstrations SafetyGym offline datasets from Liu et al. 2023a
Benchmarks: FrozenLake (8x8, offline CMDP) maze imitation learning SafetyGym (AntRun, CarRun, BallRun, BallCircle, CarPush1)
Metrics: reward cost constraint violation objective gap
Baselines: COptiDICE CPQ BEAR-Lagrangian PDCA
Builds on: COptiDICE Ozdaglar et al. 2023 offline MIW formulation Nedić and Ozdaglar primal-dual subgradient analysis Chen et al. 2022 DPDL
Closest papers by meaning
- A Primal-Dual Algorithm for Offline Constrained Reinforcement Learning with Linear MDPs (ICML 2024 · similarity 0.92)
- Off-Policy Primal-Dual Safe Reinforcement Learning (ICLR 2024 · similarity 0.90)
- Offline Constrained Reinforcement Learning under Partial Data Coverage (NeurIPS 2026 · similarity 0.89)
- Worst-Case Offline Reinforcement Learning with Arbitrary Data Support (NeurIPS 2024 · similarity 0.89)
- Online Optimization for Offline Safe Reinforcement Learning (NeurIPS 2025 · similarity 0.89)
- Truly No-Regret Learning in Constrained MDPs (ICML 2024 · similarity 0.89)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.