PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Tengyu Xu, Yingbin Liang, Guanghui Lan

arXiv:2011.05869v3cs.LGstat.ML

TL;DR

Safe reinforcement learning must maximize reward while satisfying cost constraints, but existing primal algorithms lack a provable global-convergence guarantee. The paper develops a primal approach and reports O(1/sqrt(T)) convergence to the global optimum with an O(1/sqrt(T)) constraint-satisfaction error bound, while experiments show faster constraint satisfaction than PDO.

  • Problem

    Safe reinforcement learning seeks a reward-maximizing policy that simultaneously satisfies multiple cost constraints, while existing primal algorithms lack provable convergence to a globally optimal feasible policy.

  • Method

    The paper develops a primal approach for safe reinforcement learning without the additional dual variables used by primal-dual methods.

  • Results

    O(1/sqrt(T)) convergence to the global optimum and an O(1/sqrt(T)) constraint-satisfaction error bound are reported; experiments show faster constraint satisfaction than PDO.

  • Takeaways & Limitations

    The primal approach provides a provable global-optimality guarantee, while CRPO sufficiently explores the feasible-set boundary and reaches higher return reward than PDO in the reported tasks.

  • Takeaways & Limitations

    The paper notes that existing primal algorithms lack guaranteed global convergence and strong demonstrations of performance competitive with primal-dual algorithms.

Abstract

from arXiv · show

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.

1. Introduction

Safe reinforcement learning requires maximizing reward while satisfying cost constraints, but existing primal methods lack a provable global convergence guarantee. CRPO addresses this gap with primal updates and achieves global convergence guarantees with constraint-violation bounds.

  • Motivation: Safe RL seeks a reward-maximizing policy that simultaneously satisfies multiple expected-cost constraints.The feasible policy set contains policies whose expected total cost for every constraint remains within its limit.
  • Motivation: Existing primal algorithms enforce constraints without dual variables, but none had a proven guarantee of convergence to a globally optimal feasible policy.Primal-dual methods were more widely used, while primal methods included barrier, Lyapunov, and safety-layer designs.
  • CRPO: CRPO alternates reward improvement with constraint rectification, using unconstrained policy updates to optimize reward or reduce violated constraints.The approach switches immediately to constraint minimization when a constraint is violated and can be implemented like unconstrained policy optimization.
  • Theoretical Guarantee: CRPO with NPG converges to a global optimum at O(1/sqrt(T)) in tabular and function-approximation settings, while constraint violation converges to zero at O(1/sqrt(T)).The guarantee covers function approximation with potentially infinite state spaces.
  • Comparison: In function approximation, CRPO matches the primal-dual value-function-gap rate while its constraint violation decays at O(1/sqrt(T)) versus O(1/T^1/4) for the primal-dual approach.The comparison is stated for the function-approximation setting.
  • Analysis: The analysis develops concentration tools for dynamically switching reward and constraint objectives and tools for selecting among multiple violated constraints.These developments support a high-probability convergence analysis for the stochastic process induced by CRPO.

2. Problem Formulation and Preliminaries

Safe reinforcement learning maximizes expected total reward while restricting expected costs, and policy parameterization turns this constrained problem into optimization over policy parameters.

  • 2.1. Markov Decision Process: An MDP comprises state and action spaces, reward and transition functions, an initial-state distribution, and discount factor γ.
  • 2.1. Markov Decision Process: A policy maps each state to a probability distribution over actions, inducing stationary and visitation measures used to evaluate its behavior.
  • 2.1. Markov Decision Process: The reward objective J0(π) is the expected discounted total reward, with value, action-value, and advantage functions describing policy performance.
  • 2.2. Safe Reinforcement Learning (SRL) Problem: SRL adds expected discounted cost constraints Ji(π) ≤ di to the MDP, restricting the allowable policy set ΩC.
  • 2.2. Safe Reinforcement Learning (SRL) Problem: The optimal safe policy maximizes J0(π) over ΩC, the set of policies satisfying every cost limit.
  • 2.3. Policy Parameterization and Policy Gradient: A parameterized policy class {πw : w ∈ W} converts the constrained SRL problem into optimization over w.
  • 2.3. Policy Parameterization and Policy Gradient: Policy gradients use score functions to differentiate Ji(πw), while natural policy gradients precondition these gradients with the Fisher information matrix.
  • 2.3. Policy Parameterization and Policy Gradient: Algorithm 1 evaluates reward and costs, adds feasible parameters to N0, updates reward when constraints pass, and minimizes a violated constraint otherwise.

3. Constraint-Rectified Policy Optimization (CRPO) Algorithm

CRPO alternates unconstrained reward improvement with constraint rectification: it reduces a violated cost and otherwise optimizes reward, using standard policy-optimization updates.

  • CRPO alternates maximizing reward J0(πwt) with reducing a violated constraint Ji(πwt) along that constraint’s descent direction.
  • At each iteration, CRPO estimates reward and cost value functions under the current policy before checking constraint satisfaction.
  • Constraint estimates use weighted sums of approximated state-action values, with samples generated from ξ·πwt without additional environment interaction.
  • If any estimated constraint exceeds di + η, CRPO minimizes one violated constraint; if all pass, it maximizes the reward objective.
  • CRPO can use NPG, TRPO, PPO, ACKTR, DDPG, or SAC for its policy-optimization step.
  • Unlike primal-dual methods, CRPO switches immediately when violations occur and avoids delays from dual variables that remain nonzero after constraints are satisfied.
  • CRPO avoids dual-variable updates and their learning-rate and projection-threshold tuning, while handling nonconvex objectives, nonconvex constraints, and multiple constraints unlike CSA.

4. Convergence Analysis of CRPO

The analysis establishes global convergence and vanishing constraint violation for CRPO with NPG in tabular and neural function-approximation settings, while identifying dynamic objective switching as the main technical challenge.

  • Setup and analysis: NPG serves as the representative CRPO optimizer, with convergence implications extending to TRPO and ACKTR through adaptive stepsizes.
  • 4.1. Tabular Setting: In the tabular setting, CRPO uses softmax policies and TD learning to estimate reward and cost state-action values before policy updates.
  • 4.1. Tabular Setting: Constraint estimates are formed over all state-action pairs, and their approximation accuracy depends on the accuracy of the estimated value functions.
  • 4.1. Tabular Setting: The tabular policy update uses natural policy gradients based on estimated action values and a stepsize-scaled update direction.
  • Analysis challenge: The analysis addresses stochastic approximation with random, dynamic switches between reward optimization and constraint targets, including actor-critic interaction error.
  • 4.1. Tabular Setting: O(1/√T) convergence reaches the globally optimal feasible policy, while constraint violation also decays at O(1/√T) from arbitrary initialization.
  • 4.1. Tabular Setting: T = O(ε^-2) iterations suffice for ε objective and constraint errors, providing the first global convergence guarantee for a primal method with nonconcave objective and constraints.
  • 4.2. Function Approximation Setting: With neural function approximation, CRPO retains O(1/√T) rates but incurs approximation error O(m^-1/8), which decreases as network width m increases.

5. Experiments

Experiments compare CRPO with PDO and unconstrained TRPO on constrained Cartpole and Acrobot tasks. CRPO tracks constraint limits closely while achieving higher and more stable reward than PDO.

  • Experimental comparison: CRPO and PDO are compared on two OpenAI Gym tasks with multiple constraints, using neural softmax policies and TRPO updates.The tasks are Cartpole and Acrobot; both methods use two hidden layers of size (128, 128).
  • Experimental comparison: Unconstrained TRPO achieves the best reward but does not satisfy the constraints.
  • Experimental comparison: Figure 1 reports average performance for CRPO, PDO, and unconstrained TRPO over 10 seeds, with red dotted constraint limits.
  • Constraint satisfaction: CRPO tracks constraint returns almost exactly to their limits in both tasks, indicating exploration near the feasible-set boundary.
  • Constraint satisfaction: PDO eventually satisfies constraints but over- or under-enforces them, producing lower reward and unstable constraint satisfaction.

6. Conclusion

The paper concludes that CRPO is an easy-to-implement primal approach with a provable global optimality guarantee. With NPG updates, it achieves O(1/sqrt(T)) convergence and constraint-error rates.

  • Contributions: CRPO provides a primal policy-optimization approach with a provable global optimality guarantee.
  • Theoretical guarantee: O(1/sqrt(T)) convergence rate to the global optimum is established for CRPO with NPG updates.
  • Theoretical guarantee: O(1/sqrt(T)) constraint-error decay is established when NPG updates are used.
  • Contributions: The paper identifies CRPO as the first primal SRL algorithm with a provable convergence guarantee to a global optimum.

A. Experimental Setting

The experiments define constrained Cartpole and Acrobot environments and compare CRPO's tolerance robustness with PDO's dual-step-size sensitivity. CRPO's learning curves remain similar across a wide range of tolerance values.

  • Cartpole: Cartpole rewards upright-pole control and penalizes entering specified areas or exceeding a 6-degree pole angle.Episodes last at most 200 steps, and the cart is restricted to [−2.4, 2.4].
  • Acrobot: Acrobot rewards reaching height 0.5 and penalizes torque applied during prohibited anticlockwise motions of either pendulum.Each episode has length 500.
  • Hyperparameter comparison: PDO performance is highly sensitive to the dual-variable step size: small values delay constraint enforcement, while large values reduce reward.
  • Tolerance robustness: CRPO learning curves are almost identical for η values {10, 5, 2, 1, 0.5} in Acrobot.Figure 2 compares these tolerance settings.
  • Tolerance robustness: The tolerance parameter η does not cause much parameter-tuning cost for CRPO.

B.1. Supporting Lemmas for Poof of Theorem 1

The supporting lemmas establish policy-gradient properties, performance bounds, and high-probability control of CRPO's alternating updates. Together they support convergence analysis in the tabular setting.

  • Supporting results: The supporting results include TD-learning convergence and softmax policy-gradient properties for the tabular setting.
  • Assumptions: The analysis assumes a nondegenerate stationary distribution and uses stepsizes β_k = Θ(1...).
  • NPG bounds: Approximated NPG updates receive performance-improvement and optimality-gap bounds for reward optimization.
  • NPG bounds: The same NPG analysis extends to constraint updates for each constraint index i ∈ {1, · · ·, p}.
  • CRPO convergence: Lemma 8 provides a high-probability bound for CRPO using K_in = Θ(T^(1/σ) log^(2/σ)(|S|^2|A|^2T^(1+2/σ)/δ)).
  • Proof structure: The proof uses concentration events, union bounds, and a case analysis involving the set of reward-optimization steps N_0.

B.2. Proof of Theorem 1

The proof establishes Theorem 1 by combining policy-evaluation guarantees, stochastic-gradient bounds, and objective and constraint analyses under high-probability events.

  • Theorem statement: Theorem 3 restates Theorem 1 for the tabular setting with explicit parameter choices.The result is presented under the policy-evaluation setting of Lemma 2 and with probability at least 1 −δ.
  • Objective convergence: The proof analyzes the objective convergence rate on the event defined in eq. (18).When the objective-improvement iterations comprise at least half the iterations, the resulting convergence-rate bound follows.
  • Constraint satisfaction: The proof separately bounds each constraint violation under the same high-probability event.The analysis introduces per-constraint bounds and aggregates them through the CRPO iteration sets.
  • Gradient analysis: The stochastic semi-gradient analysis compares sampled gradients with full gradients and controls their deviations using concentration inequalities.The proof invokes Markov’s inequality, Bernstein’s inequality for martingales, and union bounds to obtain simultaneous high-probability control.
  • Final bound: The resulting objective-gap expression contains a 1/√T convergence term involving the policy-space size, discount factor, and initialization divergence.The displayed bound is stated for the averaged output policy and includes Es∼ν∗DKL(π∗||πw0).

C.3. Supporting Lemmas for Proof of Theorem 2

This section develops supporting results for neural-network CRPO analysis, including the approximate natural policy-gradient update and bounds needed for objective and constraint guarantees.

  • Neural NPG update: The approximate NPG update uses the solution of a linear regression problem instead of solving the problem in eq. (10) directly.The approximation is justified when the policy and value-function networks share the same initialization.
  • Neural NPG update: Lemma 15 provides an upper bound on the optimality gap for neural NPG updates.The bound is used in the neural-network approximation analysis of CRPO.
  • Approximation control: The proof controls neural approximation errors through Lipschitz properties of log(πW(a|s)) and related gradient bounds.These bounds support comparisons between nearby policy parameterizations and visitation distributions.
  • CRPO analysis: Lemma 16 analyzes CRPO updates in the neural-network approximation setting under specified inner-loop and sampling parameters.Its result is stated with probability at least 1 −δ and supplies the event used in the subsequent theorem proof.
  • CRPO analysis: The proof distinguishes iterations selected for objective improvement from those selected to minimize individual constraints.The sets Ni identify iterations on which CRPO minimizes the i-th constraint.

C.4. Proof of Theorem 2

The proof of Theorem 2 combines the neural CRPO event with objective and constraint analyses to derive high-probability performance guarantees.

  • Theorem statement: Theorem 4 restates Theorem 2 for neural-network approximation under Assumptions 1–4 and specified parameter choices.The theorem considers a fixed number of inner iterations at each CRPO iteration and gives a probability-at-least-1 −δ guarantee.
  • High-probability event: The proof begins by conditioning on the event supplied by Lemma 16.This event occurs with probability at least 1 −δ and supports the remainder of the objective and constraint analysis.
  • Objective convergence: The objective convergence analysis uses the iterations in N0 and derives a convergence-rate bound when their count is sufficiently large.The proof explicitly considers the case |N0| ≥ T/2.
  • Constraint satisfaction: The proof then bounds constraint violation for each constraint using the estimates established in the supporting lemmas.The argument invokes the bounds corresponding to eq. (61) and eq. (63).
Loading 2011.05869v3…