A Primal Approach to Constrained Policy Optimization: Global Optimality and Finite-Time Analysis

Tengyu Xu, Yingbin Liang, Guanghui Lan

Abstract

Safe reinforcement learning (SRL) problems are typically modeled as constrained Markov Decision Processes (CMDPs), where agents must maximize rewards while adhering to safety constraints. Traditional primal-dual methods often struggle with stability and hyperparameter sensitivity. We introduce Constraint-Rectified Policy Optimization (CRPO), a primal-only framework that alternatingly updates the policy for objective improvement and constraint satisfaction. We provide the first finite-time analysis for such an algorithm, proving that CRPO with Natural Policy Gradient (NPG) achieves an $O(1/T)$ convergence rate to the global optimal policy and an $O(1/T)$ bound on constraint satisfaction. Empirical evaluations on Cartpole and Acrobot environments demonstrate that CRPO significantly outperforms existing primal-dual baselines.

Introduction

In Safe Reinforcement Learning, agents must navigate environments where certain actions or states incur costs that must be kept below a threshold. This is formalized as a CMDP. Traditional approaches often rely on Lagrangian multipliers (primal-dual methods) to transform the constrained problem into an unconstrained one. However, these methods are notoriously finicky to tune and sensitive to initialization, often leading to unstable training or poor constraint satisfaction.

The CRPO Framework

CRPO ditches dual variables entirely in favor of a purely primal approach. The algorithm employs an intuitive switching mechanism at each iteration:

  • Constraint Rectification: If any constraint is violated beyond a small tolerance $\eta$, the algorithm ignores the reward and takes a policy gradient step to minimize the cost of the violated constraint.
  • Objective Improvement: If all constraints are satisfied, the algorithm takes a standard policy gradient step to maximize the reward.

This framework is flexible and can be implemented with various policy optimization methods, including TRPO and PPO. For theoretical rigor, the authors analyze CRPO using Natural Policy Gradient (NPG) in both tabular and function approximation (neural network) settings.

Theoretical Analysis and Global Optimality

A major contribution of this work is the first finite-time analysis for a primal-type safe RL algorithm. The authors prove that despite the non-convexity of the CMDP objective and constraints, the alternating gradient approach still converges to the global optimum. Specifically, CRPO achieves a convergence rate of $O(1/T)$ for the optimality gap and constraint violation. This ensures that the algorithm reliably approaches the best possible safe policy as training progresses.

Experimental Results

The effectiveness of CRPO was evaluated on modified OpenAI Gym tasks with added safety constraints, such as avoiding specific "danger zones" in the Cartpole environment or restricted joint movements in Acrobot.

Performance comparison on the Cartpole environment. CRPO (orange) maintains safety while achieving high rewards.

As shown in the Cartpole results, CRPO effectively navigates the boundary of the feasible set. While the TRPO baseline (green) achieves high rewards, it fails to satisfy the safety constraints. CRPO, however, stays within the safe region (indicated by the dotted red line) while outperforming the Primal-Dual Optimization (PDO) baseline (blue).

Performance comparison on the Acrobot environment. CRPO demonstrates superior stability and constraint adherence.

In the Acrobot environment, CRPO demonstrates its ability to "rectify" an initially unsafe policy quickly. It converges to a higher reward than PDO while maintaining a lower constraint violation profile, proving its robustness across different environment dynamics.

Conclusion

CRPO offers a simple, stable, and theoretically grounded alternative to primal-dual methods for safe RL. By decoupling reward maximization from constraint satisfaction through a primal switching mechanism, it avoids the complexities of dual variable tuning while providing strong global optimality guarantees. Future research will explore incorporating momentum schemes to further enhance sample efficiency and handling multiple simultaneous constraint violations more effectively.

Summary updated

Abstract

Safe reinforcement learning (SRL) problems are typically modeled as constrained Markov Decision Process (CMDP), in which an agent explores the environment to maximize the expected total reward and meanwhile avoids violating 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 O(1/T) convergence rate to the global optimal policy in the constrained policy set and an O(1/T) error bound on constraint satisfaction. This is the first finite-time analysis of SRL algorithms with global optimality guarantee. Our empirical results demonstrate that CRPO can outperform the existing primal-dual baseline algorithms significantly.
BibTeX
@inproceedings{xu2021primal,
  author = {Tengyu Xu and Yingbin Liang and Guanghui Lan},
  title = {{A Primal Approach to Constrained Policy Optimization: Global Optimality and Finite-Time Analysis}},
  booktitle = {International Conference on Machine Learning},
  year = {2021},
  url = {https://openreview.net/forum?id=9vlsIpz1Yv},
}
Figure