Research map / Reinforcement learning / MDPs and planning
A Primal-Dual Algorithm for Offline Constrained Reinforcement Learning with Linear MDPs
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 a computationally efficient primal-dual algorithm for offline linear MDPs (infinite-horizon discounted) and offline constrained RL that achieves O(ε^-2) sample complexity under partial (feature) coverage, improving on the O(ε^-4) of prior work.
Problem
Offline RL and offline constrained RL with linear function approximation in the infinite-horizon discounted setting: prior computationally efficient methods under partial data coverage need O(ε^-4) samples, and none achieve O(ε^-2) in this setting.
Approach
Replaces the double-loop primal-dual scheme with a single-loop four-player (policy, Lagrange-multiplier-like zeta, lambda, and constraint weight w) method. Lambda is restricted to a confidence set spanned by dataset features (via barycentric spanners), which enables uniform concentration over policies and parameters so that gradients can be estimated from one dataset, giving O(ε^-2) sample complex
Key results
- Sample complexity of the proposed primal-dual algorithm is O(ε^-2) (with d^3 and C*^2 dependence), improving on the O(ε^-4) of Gabbianelli et al. (2023).
- Extends the method to offline constrained linear CMDPs with sample complexity O(ε^-2) (with φ^-2 dependence on Slater slack), using a w-player on constraint weights.
- Partial coverage is handled via a feature coverage assumption, which is stronger than the one used in Gabbianelli et al.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the proposed primal-dual algorithm instead of the prior Primal-Dual method | Offline RL with linear MDPs under partial data coverage · Linear MDPs, partial coverage | sample complexity in ε: ε^{-4} -> ε^{-2} | Helped |
| Use the proposed primal-dual algorithm instead of PSPI | Offline RL with linear function approximation under partial data coverage · Linear, partial coverage | sample complexity in ε: ε^{-5} -> ε^{-2} | Helped |
| Extend the primal-dual algorithm with a w-player for constraint reward weights | Offline constrained linear MDPs · Offline constrained linear MDPs | sample complexity | Mixed |
Surprising findings
- The feature coverage assumption used is stronger than the notion used by prior work, a limitation the authors acknowledge.
Limitations
- Requires a stronger notion of feature coverage than prior work (Gabbianelli et al.)
- Sample complexity has d^3 dependence and C*^2 factor, and constrained result depends on Slater slack φ
- Theoretical paper with no empirical experiments
Experimental setup
Baselines: Gabbianelli et al. 2023 primal-dual PSPI (Xie et al. 2021)
Builds on: Gabbianelli et al. 2023 offline linear MDP primal-dual Zanette et al. 2021 provable offline actor-critic Jin et al. 2020 linear MDP Abbasi-Yadkori et al. 2011 linear bandits
Closest papers by meaning
- Offline Constrained Reinforcement Learning under Partial Data Coverage (NeurIPS 2026 · similarity 0.92)
- Safe and Efficient: A Primal-Dual Method for Offline Convex CMDPs under Partial Data Coverage (NeurIPS 2024 · similarity 0.92)
- Optimal Single-Policy Sample Complexity and Transient Coverage for Average-Reward Offline RL (NeurIPS 2025 · similarity 0.92)
- Worst-Case Offline Reinforcement Learning with Arbitrary Data Support (NeurIPS 2024 · similarity 0.91)
- Offline-Online Reinforcement Learning for Linear Mixture MDPs (NeurIPS 2026 · similarity 0.91)
- Online Optimization for Offline Safe Reinforcement Learning (NeurIPS 2025 · similarity 0.90)
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.