📊 statistics

Offline Constrained Reinforcement Learning under Partial Data Coverage

This paper proposes PDOCRL, an oracle-efficient primal-dual algorithm for offline constrained reinforcement learning with general function approximation that achieves near-optimal and near-feasible performance under partial data coverage without requiring knowledge of the data-generating distribution, while addressing the issue of spurious saddle points through a stronger realizability condition.

Original authors: Seokmin Ko, Ambuj Tewari, Kihyuk Hong

Published 2026-05-13

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Seokmin Ko, Ambuj Tewari, Kihyuk Hong

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to teach a robot to drive a car, but you can't let the robot drive on real roads to learn. It's too dangerous and expensive. Instead, you only have a giant video library of a human driver's past trips. Your goal is to teach the robot to drive as fast as possible (maximize reward) while never speeding or hitting a curb (satisfying safety constraints).

This is the problem of Offline Constrained Reinforcement Learning. The paper you provided, titled "Offline Constrained Reinforcement Learning under Partial Data Coverage," introduces a new method called PDOCRL to solve this.

Here is the breakdown of the problem and their solution, using simple analogies.

The Problem: The "Blind Spot" and the "Ghost Policy"

1. The Partial Coverage Problem (The Blind Spot)
Imagine your video library only has footage of the human driver taking the highway. It has no footage of them driving through a narrow city alley.

If you try to teach the robot to drive through that alley, the robot is guessing. It doesn't know what happens if it turns left there because it's never seen it.
Previous methods tried to be "pessimistic" (assume the worst) about these blind spots. However, in a constrained setting (where safety is key), these methods often get stuck. They try to evaluate "what if" scenarios for intermediate strategies the robot is testing. If those strategies lead to a blind spot, the evaluation fails, and the robot can't learn safely.

2. The "Ghost Policy" Problem (The Missing Recipe)
Many existing methods work like this:

They calculate a "density ratio" (a fancy way of saying: "How much more often does the robot visit this spot compared to the human?").
They then try to turn that ratio back into a driving policy.
The Catch: To do step 2, they need to know the exact probability of the human driver being in every single spot in the video library. But in the real world, you don't have that "master list" of the human's habits. It's like trying to bake a cake using a recipe that requires an ingredient you don't have the label for.

The Solution: PDOCRL

The authors propose PDOCRL (Primal-Dual Offline Constrained Reinforcement Learning). They solve the problems above with two clever tricks.

Trick 1: The "Decomposed" Kitchen (Avoiding the Ghost)

Instead of trying to bake the cake (the policy) after figuring out the ingredient ratios (the density), PDOCRL changes the recipe entirely.

Old Way: Calculate ratios $\rightarrow$ Try to guess the missing ingredient list $\rightarrow$ Bake the cake. (Fails if you don't know the ingredient list).
PDOCRL Way: They split the problem into two separate tasks that talk to each other.
- Task A: Figure out the ratios (how much to trust the data).
- Task B: Directly adjust the robot's driving strategy (the policy).
- The Magic: They re-wrote the math so that the robot's driving strategy becomes a direct variable in the equation. This means the robot learns the driving style directly, without ever needing to know the "master list" of the human driver's habits. It bypasses the need for the missing ingredient label entirely.

Trick 2: The "Spurious Trap" (Avoiding Fake Solutions)

When you have a complex math problem with many variables, sometimes you find a "solution" that looks perfect on paper but is actually a trap. In math terms, these are called spurious saddle points.

The Analogy: Imagine you are looking for the highest peak in a mountain range. You find a spot that looks like a peak from one angle, but if you walk around it, you realize it's actually a small hill surrounded by a deep valley. You thought you found the top, but you didn't.
The Fix: The paper proves that if you only assume the "best" solution exists in your data, you might fall into these traps. To fix this, they add a stronger rule: The robot's "brain" (the function approximator) must be smart enough to understand any possible driving style, not just the best one.
By forcing the robot's brain to be capable of evaluating any strategy, they guarantee that the "peak" they find is the real highest peak, not a fake one.

The Result: A Safe, Efficient Learner

The paper claims that PDOCRL achieves three things that previous methods couldn't do all at once:

Partial Coverage: It works even if the data library has big blind spots (as long as the best path is covered).
Oracle Efficiency: It is computationally fast. It doesn't need to solve impossible math puzzles; it just uses standard optimization tools (like a chef using standard knives rather than inventing new ones).
No "Master List" Needed: It doesn't need to know the underlying distribution of the data (the human's habits). It learns directly from the videos.

The "Taste Test" (Experiments)

The authors tested their method on standard driving simulations (BulletGym).

The Baseline: They compared it to other top-tier "safe" driving algorithms.
The Outcome: PDOCRL was the only algorithm that consistently stayed under the speed limit (satisfied the safety constraint) across all tasks while still driving fast enough to be competitive.
The Ablation Study: They also tested what happens if they did use the old "Ghost Policy" method (extracting the policy from ratios). The result? The robot crashed or drove terribly. This proved that their new "direct policy" trick was essential.

Summary

PDOCRL is a new algorithm that teaches robots to be safe and efficient using only past data, even when that data is incomplete. It does this by:

Skipping the step of trying to guess the data's hidden patterns.
Directly optimizing the robot's behavior.
Using a stricter mathematical rule to ensure the robot doesn't get tricked by fake "solutions."

It's like teaching a student to drive by showing them videos, but instead of asking them to memorize the teacher's every move, you teach them the rules of the road directly, ensuring they can drive safely even in parts of the city the teacher never visited.

Technical Summary: Offline Constrained Reinforcement Learning under Partial Data Coverage

Problem Statement

The paper addresses Offline Constrained Reinforcement Learning (Offline Constrained RL) within the framework of discounted Constrained Markov Decision Processes (CMDPs). The objective is to learn a policy from a fixed, offline dataset that maximizes a primary reward signal while satisfying multiple auxiliary safety or resource constraints.

A central challenge in this setting is partial data coverage. Reliable optimization typically requires the dataset to cover the state-action occupancy of the policies being evaluated. In unconstrained offline RL, pessimistic actor-critic methods have shown success under insufficient coverage. However, in the constrained setting, primal-dual methods face a specific obstruction: updating dual multipliers requires estimating constraint violations for intermediate policies. Under partial coverage, these intermediate policies may not be supported by the dataset, rendering dual updates unreliable and effectively reintroducing strong coverage requirements.

Furthermore, existing methods often rely on policy extraction steps that require knowledge of the unknown data-generating distribution ( $\mu_D$ ) or a reference policy, which is impractical in real-world scenarios.

Methodology: PDOCRL

The authors propose PDOCRL (Primal-Dual Oracle-Efficient Constrained Reinforcement Learning), an algorithm designed to be oracle-efficient, sample-efficient under partial coverage, and independent of the data-generating distribution.

1. Decomposed Linear Programming Formulation

Standard LP formulations for CMDPs optimize over occupancy measures ( $\mu$ ). Recovering a policy from $\mu$ typically requires normalizing by the data distribution $\mu_D$ , which is unknown. To circumvent this, the authors employ a Lagrangian decomposition:

They introduce a copy variable $\nu$ for the occupancy measure $\mu$ .
They separate the roles: $\mu$ is used for Lagrangian estimation (via change of measure to the data distribution), while $\nu$ is used for policy extraction.
Crucially, they reparameterize $\nu$ in terms of the occupancy measure $\mu$ and the policy $\pi$ directly: $\nu_{\mu, \pi}(s, a) = \pi(a|s)((1-\gamma)d_0(s) + \gamma[P^\top \mu](s))$ .
This makes the policy $\pi$ an explicit optimization variable, eliminating the need for a separate policy extraction step that depends on $\mu_D$ .

2. Handling Spurious Saddle Points

The authors identify that restricted saddle-point formulations using general function approximation can admit spurious saddle points. Even if the function classes contain the optimal policy, its occupancy measure, and optimal action-value functions, a saddle point of the restricted Lagrangian may not correspond to an optimal policy.

To resolve this, they impose two key conditions:

Slater's Condition (Assumption B): Ensures the existence of a feasible policy that satisfies constraints with a positive margin $\phi$ . This bounds the optimal dual variables.
All-Policy Value Function Realizability (Assumption C): A strong realizability condition requiring that for every policy $\pi$ in the class, the value functions $Q^\pi_0$ and $Q^\pi_0 + (1 + 1/\phi)Q^\pi_i$ are contained within the function class $\mathcal{Q}$ . This is stronger than single-policy realizability but necessary to rule out spurious saddle points in the decomposed formulation.

3. Oracle-Efficient Primal-Dual Algorithm

PDOCRL solves the empirical saddle-point problem using standard oracles, avoiding intractable min-max optimization:

Primal Players:
- Density Ratio ( $w$ ): Uses a no-regret online linear optimization oracle ( $\mathcal{O}_{LOW}$ ) over the function class $\mathcal{W}$ .
- Policy ( $\pi$ ): Uses a no-regret policy optimization oracle ( $\mathcal{P}_{O\Pi,\mathcal{Q}}$ ) over the policy class $\Pi$ .
Dual Players:
- Q-function ( $Q$ ): Uses a linear minimization oracle ( $\mathcal{LMO}_{\mathcal{Q}}$ ) over $\mathcal{Q}$ .
- Lagrange Multipliers ( $\lambda$ ): Uses a linear minimization oracle ( $\mathcal{LMO}_{B\Delta_I}$ ) over the dual bound.

The algorithm iterates $T$ times, updating these variables and returning a policy sampled uniformly from the sequence $\pi_1, \dots, \pi_T$ .

Key Contributions

Algorithm Design: PDOCRL is the first method to simultaneously achieve partial-coverage guarantees, oracle efficiency, and independence from the data-generating distribution ( $\mu_D$ ) in offline constrained RL with general function approximation.
Theoretical Insight on Saddle Points: The paper demonstrates that naive restricted saddle formulations can fail due to spurious saddle points and identifies a stronger all-policy realizability condition under which every restricted saddle point is optimal.
Decomposition Technique: By reparameterizing the occupancy measure to make the policy an explicit variable, the method avoids the statistical fragility of extracting policies from density ratios when $\mu_D$ is unknown.
Sample Complexity: Under the stated assumptions, PDOCRL returns a near-optimal and near-feasible policy with a sample complexity of $\tilde{O}(\epsilon^{-2})$ .

Experimental Results

The authors evaluated PDOCRL on the BulletGym benchmark using datasets from the DSRL package.

Baselines: Compared against BC-All, BC-Safe, CDT, BCQ-Lag, BEAR-Lag, CPQ, and COptiDICE.
Performance: PDOCRL was the only algorithm that consistently satisfied safety constraints (normalized cost $\le 1$ ) across all tasks while maintaining competitive reward performance.
Ablation Study: A variant of PDOCRL that reverts to the standard policy extraction step (requiring knowledge of $\mu_D$ ) performed significantly worse, confirming that the proposed reparameterization is critical for performance in the offline setting.

Significance and Claims

The paper claims that PDOCRL addresses a fundamental gap in offline constrained RL: the trade-off between coverage requirements, computational efficiency, and the need for data distribution knowledge.

Unlike prior actor-critic methods (e.g., PDCA, WSAC) that require full coverage or intractable optimization, PDOCRL operates under partial coverage with oracle efficiency.
Unlike density-ratio methods (e.g., COptiDICE, POCC) that rely on $\mu_D$ for policy extraction, PDOCRL optimizes the policy directly.
The work highlights that while strong realizability assumptions (all-policy) are required to guarantee optimality in the presence of spurious saddle points, this is a necessary theoretical price for achieving oracle efficiency and avoiding distributional assumptions in the general function approximation setting.

The authors conclude that PDOCRL provides a provably efficient framework for safe offline learning, though they note that relaxing the all-policy realizability condition toward single-policy realizability remains a direction for future work.