  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.
