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

Tengyu Xu, Yingbin Liang, Guanghui Lan

Abstract

In safe reinforcement learning (SRL) problems, an agent explores the environment to maximize an expected total reward while avoiding violations of constraints on expected total costs. These problems typically involve non-convex objectives and constraints, making global optimality difficult to achieve. While most SRL algorithms use primal-dual structures with dual variables, we propose Constraint-Rectified Policy Optimization (CRPO), a purely primal approach that alternates between objective improvement and constraint satisfaction. Using Natural Policy Gradient (NPG), we show that CRPO achieves an $O(1/\sqrt{T})$ convergence rate to the global optimal policy and an $O(1/\sqrt{T})$ error bound on constraint satisfaction. This represents the first finite-time analysis of primal SRL algorithms with a global optimality guarantee. Empirical results show that CRPO significantly outperforms existing primal-dual baselines.

Introduction

Safe Reinforcement Learning (SRL) is critical for real-world applications like autonomous driving, where agents must maximize rewards (e.g., reaching a destination) while adhering to safety constraints (e.g., avoiding collisions). Mathematically, this is a constrained optimization problem where both the objective and constraints are typically non-convex.

Most existing SRL algorithms rely on primal-dual structures, utilizing Lagrange multipliers to penalize constraint violations. However, these methods are often highly sensitive to the learning rate of dual variables, exhibit slow responses to violations, and require complex projection steps to remain feasible.

The CRPO Algorithm

CRPO addresses these issues by directly tackling constraints without the baggage of dual variables. It employs an intuitive switching logic:

  • Constraint Satisfaction Mode: If any safety constraint is violated beyond a tolerance $\eta$, the algorithm ignores the reward and performs a policy update to minimize the violated constraint.
  • Objective Improvement Mode: If all constraints are satisfied, the algorithm performs a standard policy update to maximize the reward.

This "immediate switching" allows the agent to react instantly to safety risks. CRPO provides a flexible framework where each policy update can utilize various techniques, such as TRPO or PPO, though the authors focus on Natural Policy Gradient (NPG) for their theoretical analysis.

Theoretical Breakthroughs

The authors provide a rigorous theoretical analysis of CRPO in both tabular and function approximation settings. Key theoretical insights include:

  • Global Optimality: CRPO is proven to converge to a globally optimal safe policy, a significant milestone for primal methods.
  • Faster Convergence: The constraint violation decays at a rate of $O(1/\sqrt{T})$, which is significantly faster than the $O(1/T^{1/4})$ rate established for many leading primal-dual methods.
  • Novel Analysis: The proof captures the impact of dynamic "switches" between reward and cost functions, overcoming a major challenge in proving global optimality for primal methods.

Empirical Results

CRPO was evaluated on modified OpenAI Gym tasks, Cartpole and Acrobot, featuring multiple safety constraints.

Performance comparison of CRPO, PDO, and TRPO on Cartpole and Acrobot tasks. CRPO (red) demonstrates superior stability and faster constraint satisfaction compared to the Primal-Dual Optimization (PDO) baseline.

Performance and Stability

In both tasks, CRPO satisfied constraints much faster than the PDO baseline. Because CRPO can more effectively navigate the boundaries of the safe region, it achieved higher cumulative rewards. Unlike Lagrangian methods, CRPO eliminates the need for tuning dual learning rates, making it more robust in practice.

Boundary Exploration

A key advantage of CRPO is its ability to track the constraint boundary almost exactly. This allows the agent to explore the very edge of the feasible set, which often contains the optimal policy, whereas more conservative methods may fail to reach it.

Detailed constraint values for the Cartpole task. CRPO (red) maintains the constraint values right at the limit (dotted line), whereas the primal-dual method (blue) fluctuates and struggles to maintain the safety boundary.

Conclusion

CRPO offers a robust and theoretically sound primal approach to safe RL. By bypassing the complexities of dual variables, it simplifies deployment while improving performance and stability. Future research will explore extending these global convergence proofs to other architectures like PPO and incorporating momentum schemes to further accelerate convergence.

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{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