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