Constrained Offline Policy Optimization

Nicholas Polosky, Bruno C. da Silva, Madalina Fiterau, Jithin JagannathICML 2022 · OpenReview

TL;DR

Researchers have introduced Constrained Offline Policy Optimization (COPO), the first algorithm for offline reinforcement learning that provides robust, non-asymptotic confidence bounds on a policy's cost. By combining a novel cost-projection method with distribution correction estimation, COPO ensures that learned policies remain safe even when trained on limited, static datasets where traditional methods often fail.

What Problem Does This Paper Address?

Reinforcement Learning (RL) is powerful, but in the real world, we rarely have the luxury of letting an agent learn through trial and error in a live environment—especially when "error" means crashing a drone or mismanaging a patient's medication. This leads us to Offline RL, where we learn from a pre-collected, static dataset.

The challenge is twofold:

  1. Constraints: We need the agent to maximize rewards while staying under a "cost budget" (e.g., "go as fast as possible, but never exceed a specific velocity").
  2. Distributional Shift: The policy we are learning will likely behave differently than the policy that collected the data. This shift makes it incredibly hard to estimate the true cost of a new policy accurately.

Existing state-of-the-art methods like Batch Policy Learning under Constraints (BPLC) provide "point estimates" of cost. However, point estimates are brittle; they don't account for the uncertainty inherent in finite data. If your estimate is slightly off, your "safe" policy might be catastrophic in practice.

Methods

COPO tackles this by framing the problem as a Constrained Projection. The algorithm follows a three-step high-level logic:

  1. Find a Reward-Optimal Policy: Use standard offline RL techniques to find a policy that maximizes reward.
  2. Estimate Visitation Density: Determine how often that policy visits specific state-action pairs using "DICE" (Distribution Correction Estimation) methods.
  3. Project onto the Feasible Set: This is the core novelty. COPO takes the reward-optimal (but potentially unsafe) policy and "projects" it to the nearest policy that satisfies all cost constraints.

To make this computationally feasible, the authors use Fenchel-Rockafeller duality to transform a complex, constrained optimization problem into an unconstrained saddle-point problem. This allows them to use various distance metrics (like Wasserstein distance or f-divergences) to define what "nearest" means. Crucially, they incorporate generalized empirical likelihood to derive high-probability confidence intervals, ensuring the true cost of the policy is unlikely to exceed the calculated bound.

Datasets

The authors evaluated COPO on two primary environments:

  • Walk-Around-Grid: A custom 5x5 grid world designed for robotic navigation. The agent gets rewards for moving counter-clockwise but incurs costs for entering specific "unsafe" columns.
Walk-Around-Grid Environment
  • BipedalWalker (Modified): A continuous control task from OpenAI Gym. The authors modified it to include a safety constraint: the robot must walk as far as possible without its linear velocity exceeding a specific threshold.

Key Insights and Ideas

  • From Points to Bounds: The biggest "aha" moment is the shift from predicting a single cost value to predicting a confidence interval. In safety-critical systems, knowing the "worst-case" cost is far more valuable than knowing the "average" cost.
  • Duality as a Tool for Tractability: By using Fenchel duality, the authors turned a hard-to-solve constrained problem into a saddle-point objective that can be optimized using standard gradient-based methods.
  • Robustness to Finite Data: COPO is explicitly designed for the "small data" regime. Because it accounts for the stochasticity of the underlying Markov Decision Process (MDP), it produces policies that are more consistent across different training samples than previous methods.

Key Results

In the Walk-Around-Grid experiments, COPO significantly outperformed the baseline (BPLC):

  • Lower Cost Spread: COPO’s "cost spread" (a measure of consistency) was often an order of magnitude lower than BPLC’s (e.g., 7.396e-3 vs 3.714e-2 at a 0.4 budget).
  • Higher Rewards: While staying safer, COPO also achieved higher mean per-step rewards (e.g., 0.897 average vs 0.821 for BPLC).
BipedalWalker Performance Comparison
  • Safety Guarantees: In the BipedalWalker task, BPLC identified policies that were actually 10.4% over the cost budget in practice, whereas COPO’s policies remained strictly within the safety limits, successfully minimizing cost while maintaining competitive rewards.

Limitations and Future Work

While COPO represents a significant step forward, the authors note a few areas for improvement:

  • Distance Metric Selection: The choice of distance function (Wasserstein vs. f-divergence) in the projection step impacts performance. Future work is needed to characterize which metrics work best for specific types of MDPs.
  • Sim-to-Real Gap: The current results are in simulation. The authors aim to test COPO on physical, non-simulated systems where data is even more scarce and safety is even more critical.
  • Computational Overhead: The projection step involves solving a saddle-point problem, which may be more computationally intensive than simpler point-estimation methods in very high-dimensional spaces.

Summary updated

Abstract

In this work we introduce Constrained Offline Policy Optimization (COPO), an offline policy optimization algorithm for learning in MDPs with cost constraints. COPO is built upon a novel offline cost-projection method, which we formally derive and analyze. Our method improves upon the state-of-the-art in offline constrained policy optimization by explicitly accounting for distributional shift and by offering non-asymptotic confidence bounds on the cost of a policy. These formal properties are superior to those of existing techniques, which only guarantee convergence to a point estimate. We formally analyze our method and empirically demonstrate that it achieves state-of-the-art performance on discrete and continuous control problems, while offering the aforementioned improved, stronger, and more robust theoretical guarantees.
BibTeX
@inproceedings{polosky2022constrained,
  author = {Nicholas Polosky and Bruno C. da Silva and Madalina Fiterau and Jithin Jagannath},
  title = {{Constrained Offline Policy Optimization}},
  booktitle = {International Conference on Machine Learning},
  year = {2022},
  url = {https://openreview.net/forum?id=fi2HyVWNIl},
}
Figure