CRPO: A New Approach for Safe Reinforcement Learning with Convergence Guarantee

Tengyu Xu, Yingbin Liang, Guanghui Lan

Abstract

In safe reinforcement learning (SRL) problems, an agent explores the environment to maximize an expected total reward and meanwhile avoids violation of certain constraints on a number of expected total costs. In general, such SRL problems have nonconvex objective functions subject to multiple nonconvex constraints, and hence are very challenging to solve, particularly to provide a globally optimal policy. Many popular SRL algorithms adopt a primal-dual structure which utilizes the updating of dual variables for satisfying the constraints. In contrast, we propose a primal approach, called constraint-rectified policy optimization (CRPO), which updates the policy alternatingly between objective improvement and constraint satisfaction. CRPO provides a primal-type algorithmic framework to solve SRL problems, where each policy update can take any variant of policy optimization step. To demonstrate the theoretical performance of CRPO, we adopt natural policy gradient (NPG) for each policy update step and show that CRPO achieves an $\mathcal{O}(1/\sqrt{T})$ convergence rate to the global optimal policy in the constrained policy set and an $\mathcal{O}(1/\sqrt{T})$ error bound on constraint satisfaction. This is the first finite-time analysis of primal SRL algorithms with global optimality guarantee. Our empirical results demonstrate that CRPO can outperform the existing primal-dual baseline algorithms significantly.

Introduction

Reinforcement Learning (RL) excels at maximizing rewards, but real-world applications—such as autonomous driving or robotics—require strict adherence to safety constraints. Safe RL (SRL) aims to maximize rewards while ensuring that specific costs, such as collision probabilities, remain below predefined thresholds.

Traditionally, SRL problems are addressed using Primal-Dual methods, which employ Lagrange multipliers to penalize constraint violations. However, these methods suffer from high hyperparameter sensitivity (especially regarding the dual learning rate), delayed reactions to safety violations, and implementation complexity due to required projected gradient steps. This paper introduces Constraint-Rectified Policy Optimization (CRPO), a primal-only approach that simplifies the optimization process while providing stronger theoretical guarantees.

Methodology: Constraint-Rectified Policy Optimization (CRPO)

CRPO moves away from dual variables, instead utilizing a straightforward "if-else" logic at each iteration to balance reward maximization and constraint satisfaction. The algorithm follows a two-step process:

  1. Policy Evaluation: The agent estimates the current expected reward and the costs associated with all safety constraints.
  2. Constraint Check and Update: The agent checks if any safety constraints are violated beyond a small tolerance $\eta$.
  3. Safe State: If all constraints are satisfied, the agent performs a standard RL update (e.g., using Natural Policy Gradient) to maximize the reward.
  4. Unsafe State: If any constraint is violated, the agent selects a violated constraint and performs an update specifically to minimize that cost.

This immediate switching mechanism allows for rapid response to safety violations. Theoretically, when paired with Natural Policy Gradient (NPG), CRPO is proven to converge to a globally optimal safe policy with an $\mathcal{O}(1/\sqrt{T})$ rate for both optimality and constraint satisfaction.

Experimental Results

The effectiveness of CRPO was evaluated on modified OpenAI Gym benchmarks, specifically Cartpole (with danger zones) and Acrobot (with torque restrictions).

Performance comparison of CRPO, PDO, and TRPO on Cartpole and Acrobot benchmarks.

As shown in the performance comparison above, CRPO demonstrates several key advantages:

  • Faster Safety Convergence: CRPO reaches the safety boundary significantly faster than Primal-Dual Optimization (PDO).
  • Higher Returns: By effectively exploring the boundary of the feasible set, CRPO often achieves higher total rewards than competitors while remaining strictly safer.
  • Robustness: CRPO is less sensitive to its primary hyperparameter (tolerance $\eta$) compared to the delicate tuning required for dual learning rates in Lagrangian methods.

Conclusion

CRPO represents a significant shift in Safe RL by demonstrating that a primal-only "greedy switch" approach can outperform complex primal-dual architectures. It provides the first finite-time global convergence guarantees for a primal SRL algorithm. Future work includes extending these guarantees to other optimizers like PPO or SAC and exploring the performance of CRPO in environments with high-dimensional constraint sets.

Summary updated

Abstract

In safe reinforcement learning (SRL) problems, an agent explores the environment to maximize an expected total reward and meanwhile avoids violation of certain constraints on a number of expected total costs. In general, such SRL problems have nonconvex objective functions subject to multiple nonconvex constraints, and hence are very challenging to solve, particularly to provide a globally optimal policy. Many popular SRL algorithms adopt a primal-dual structure which utilizes the updating of dual variables for satisfying the constraints. In contrast, we propose a primal approach, called constraint-rectified policy optimization (CRPO), which updates the policy alternatingly between objective improvement and constraint satisfaction. CRPO provides a primal-type algorithmic framework to solve SRL problems, where each policy update can take any variant of policy optimization step. To demonstrate the theoretical performance of CRPO, we adopt natural policy gradient (NPG) for each policy update step and show that CRPO achieves an $\mathcal{O}(1/\sqrt{T})$ convergence rate to the global optimal policy in the constrained policy set and an $\mathcal{O}(1/\sqrt{T})$ error bound on constraint satisfaction. This is the first finite-time analysis of primal SRL algorithms with global optimality guarantee. Our empirical results demonstrate that CRPO can outperform the existing primal-dual baseline algorithms significantly.
BibTeX
@inproceedings{xu2021crpo,
  author = {Tengyu Xu and Yingbin Liang and Guanghui Lan},
  title = {{CRPO: A New Approach for Safe Reinforcement Learning with Convergence Guarantee}},
  booktitle = {International Conference on Machine Learning},
  year = {2021},
  url = {https://openreview.net/forum?id=9vlsIpz1Yv},
}
Figure