Source-linked AI summary
Convergent Policy Optimization for Safe Reinforcement Learning
Ming Yu, Zhuoran Yang, Mladen Kolar, Zhaoran Wang
TL;DR
Safe reinforcement learning with nonlinear function approximation leads to constrained optimization with nonconvex reward and cost functions. The paper replaces them with locally constructed convex quadratic surrogates and proves almost-sure convergence of the resulting policy sequence to a stationary point, extending the approach to optimal control and constrained multi-agent settings.
Problem
Safe reinforcement learning with function approximation requires optimizing a nonconvex objective subject to a nonconvex safety constraint.
Source: §1 · p. 1Method
The algorithm iteratively solves convex constrained problems formed from quadratic surrogate reward and cost functions estimated with policy gradients.
Source: §1 · p. 2, §3 · pp. 4–5Results
Takeaways & Limitations
Abstract
from arXiv · showhide
We study the safe reinforcement learning problem with nonlinear function approximation, where policy optimization is formulated as a constrained optimization problem with both the objective and the constraint being nonconvex functions. For such a problem, we construct a sequence of surrogate convex constrained optimization problems by replacing the nonconvex functions locally with convex quadratic functions obtained from policy gradient estimators. We prove that the solutions to these surrogate problems converge to a stationary point of the original nonconvex problem. Furthermore, to extend our theoretical results, we apply our algorithm to examples of optimal control and multi-agent reinforcement learning with safety constraints.
1 Introduction
Safe reinforcement learning can be formulated as CMDP optimization, but function approximation makes both objective and constraint nonconvex and complicates saddle-point methods. The paper instead uses convex quadratic surrogates whose policy updates converge almost surely to a stationary point, with applications beyond standard CMDPs.
Motivation
- CMDPs define safety through expected cumulative cost constraints while optimizing expected cumulative reward over trajectories.This extends safety beyond individual state-action decisions to long-term trajectory behavior.Source: §1 · p. 1
Challenges
- With function approximation, CMDP objectives and constraints become nonconvex, while saddle-point methods require computationally expensive inner MDP solutions.Their theoretical guarantees can also depend on optimal inner solves and may be unstable because the Lagrangian is not convex-concave.Source: §1 · pp. 1–2
Proposed approach
- The proposed algorithm replaces reward and cost functions locally with convex quadratic surrogates built from policy-gradient estimates, then solves each constrained surrogate problem.The surrogates act as first-order Taylor expansions and convex relaxations of the original functions.Source: §1 · p. 2
Theoretical result
- The sequence of policy parameters converges almost surely to a stationary point of the original nonconvex constrained optimization problem.The paper analyzes this convergence for discrete-time CMDPs and assumes regularity conditions on the reward and cost functions.Source: §1 · p. 2
Contributions
- The paper adds an online actor-critic gradient estimator to reduce variance and applies the resulting algorithms to optimal control and constrained parallel or multi-agent reinforcement learning.The parallel and multi-agent applications are placed in supplementary material.Source: §1 · p. 2
2 Background
The background introduces MDPs, parametrized policies, policy-gradient updates, actor-critic variance reduction, and CMDPs with cumulative-cost constraints. These definitions establish the optimization objects used by the paper's safe policy-optimization method.
Markov decision processes
- An MDP is specified by state and action spaces, transition dynamics, discounting, rewards, and an initial-state distribution, while a policy maps states to action distributions.The paper uses a parametrized policy class to move from an infinite-dimensional policy space to finite-dimensional optimization.Source: §2 · p. 2
Policy gradient method
- Policy-gradient methods update policy parameters by gradient ascent using stochastic estimates of the expected cumulative reward gradient.The gradient can be estimated with the policy-gradient theorem.Source: §2 · p. 3
Actor-critic method
- Actor-critic methods estimate value functions alongside policy parameters to reduce policy-gradient variance, using a critic evaluation step and an actor update.The critic may use TD(0), while the actor uses estimated action values in the policy-gradient update.Source: §2 · p. 3
Constrained MDP
- A CMDP augments an MDP with state-action costs and requires expected cumulative cost to remain below a predefined threshold while reward is optimized.The constraint is defined on the model parameter θ through the cumulative cost function.Source: §2 · p. 3
3 Algorithm
The algorithm directly tackles nonconvex constrained policy optimization by constructing convex quadratic relaxations from sampled rewards, costs, and policy-gradient estimates. It alternates between solving these constrained subproblems, handling infeasibility through a relaxation problem, and optionally reducing estimator variance with actor-critic updates.
Successive convex relaxation
- Convex quadratic relaxations replace the nonconvex reward and cost functions using sampled function values and policy-gradient estimates, producing a tractable constrained QCQP at each iteration.The surrogate functions use a first-order expansion plus a quadratic term with τ > 0; the resulting problem can be solved efficiently, for example by an interior-point method.Source: §3 · p. 4
- When the relaxed constrained problem is infeasible, the algorithm instead solves a feasibility problem that minimizes the constraint relaxation before updating the policy.The method can start from a possibly infeasible policy parameter and uses this fallback because a feasible original problem does not guarantee a feasible convex relaxation.Source: §3 · p. 4
- Each iteration samples reward and cost realizations and their gradients, solves either the constrained or feasibility subproblem, and applies a learning-rate interpolation update.Algorithm 1 obtains Monte Carlo samples and policy-gradient estimates, then updates θk+1 using ηk.Source: §3 · pp. 4–5
Gradient and value estimation
- Infinite-horizon estimation uses a geometric stopping time with parameter 1 − γ to truncate trajectories while preserving an unbiased cumulative-reward estimate.The required trajectory length grows as γ approaches 1 because future rewards receive less discounting.Source: §3 · p. 5
Variance reduction
- Variance reduction averages multiple trajectories or subtracts a state-value baseline, replacing Qθ(s, a) with the advantage function without changing the expectation.The baseline approach corresponds to REINFORCE with Baseline and is described as significantly reducing policy-gradient variance.Source: §3 · p. 5
Actor-critic method
- The actor-critic variant uses nonlinear value and cost approximators with TD updates, replacing high-variance Monte Carlo quantities by online value-function estimates.Its actor step solves the same constrained or feasibility relaxation using reward and cost estimators derived from TD errors.Source: §3 · pp. 5–6
4 Theoretical Result
Under regularity, step-size, and initialization conditions, the algorithm’s convergent subsequences satisfy stationarity conditions for the original constrained policy-optimization problem almost surely. Feasibility of the limiting point is ensured under the theorem’s stated conditions, while safe exploration during training remains unguaranteed.
Assumptions
- The analysis requires decreasing learning rates with ηk/ρk → 0 and finite cumulative conditions on the penalty and step-size sequences.A practical schedule is ηk = k^-c1 and ρk = k^-c2 with 0.5 < c2 < c1 < 1.Source: §4 · p. 6
Main theorem
- The limiting policy parameter is feasible, satisfying D(θS) ≤ D0, under the theorem’s conditions.The proof uses the KKT conditions together with Slater’s condition to establish stationarity for the original constrained problem.Source: §4 · pp. 6–7
- Theorem 4 considers any convergent subsequence under Assumptions 1 and 2 with sufficiently small initial step size, assuming either feasible initialization or Assumption 3.Assumption 2 requires uniformly Lipschitz-continuous reward, cost, and derivative functions. Assumption 3 is useful only for infeasible initialization.Source: §4 · pp. 6–7
Initialization
- Assumption 3 prevents iterates from becoming stuck at an infeasible stationary point when training starts infeasibly.If a feasible point is reached during the iterates, it can serve as an initializer and Assumption 3 is unnecessary; otherwise, violating it may yield an infeasible stationary point.Source: §4 · pp. 6–7
Limitations
- The algorithm does not guarantee safe exploration during training, and finding a feasible starting point can itself be difficult.The authors report reaching a feasible point in every experimental replicate, but this does not remove the training-phase safety limitation.Source: §4 · p. 7
5 Application to Constrained Linear-Quadratic Regulator
The paper applies its constrained policy-optimization framework to LQR, where both objective and constraint are nonconvex in the linear controller. It also extends the algorithm to parallel and multi-agent constrained MDP applications.
5 Application to Constrained Linear-Quadratic Regulator
- LQR retains nonconvex objective and constraint functions in the controller parameter, despite positive-definite cost matrices.The constrained optimum may no longer be linear in the state, but the paper restricts attention to finding the best linear controller.Source: §5 · pp. 7–8
- The algorithm estimates reward and cost values and gradients, then solves a constrained optimization problem to produce each successive controller.The procedure alternates recursive estimates, sampling, surrogate construction, and constrained updates until convergence.Source: §5 · p. 8
- For random transition and control noise, the method samples states and repeatedly solves the constrained surrogate problem using the corresponding objective and gradient formulas.This preserves the algorithmic procedure when closed-form expectations are unavailable or when sampling is required.Source: §5 · p. 8
Other applications
- The algorithm also applies to constrained parallel MDPs and constrained multi-agent MDPs, with those applications relegated to supplementary material.The paper identifies these settings as extensions beyond the constrained LQR application.Source: §5 · p. 8
6 Experiment
The experiment evaluates constrained LQR from an initially infeasible controller and compares the proposed method with a Lagrangian baseline. The proposed method reaches comparable objective values with fewer policy updates.
Experiment setup and results
- The experiment uses a 15-dimensional state, an 8-dimensional control, random system matrices, and a zero initial controller.The constraint and initialization are chosen so that the initial controller is infeasible and the unconstrained solution violates the constraint.Source: §6 · p. 9
- A conservative step size keeps the closed-loop system stable by avoiding eigenvalues of A − BF leaving (−1, 1).This stability condition motivates the selected learning-rate schedule.Source: §6 · p. 9
- The proposed method becomes feasible after about 100 iterations, then generally decreases the objective without reaching the unconstrained minimum.The experiment starts infeasible, while the constrained problem itself is feasible and nontrivial.Source: §6 · p. 9
Comparison with the Lagrangian method
- Both methods achieve similar minimum objective values, while the proposed method uses fewer policy updates for exact and approximate minima.Table 1 reports means and standard deviations over 50 replicates; the approximate criterion allows an objective within 0.02% of the minimum.Source: §6 · p. 9
A.1 Constrained Parallel Markov Decision Process
The constrained parallel MDP extension uses multiple workers to estimate reward and cost quantities for a shared policy. A central controller averages these estimates and updates the policy through the proposed QCQP procedure.
A.1 Constrained Parallel Markov Decision Process
- Each worker has individual reward, cost, and initial-state distributions whose expectations match the shared MDP quantities.Workers otherwise share the state space, action space, transition distribution, and discount factor.Source: §A.1 · p. 14
- Multiple workers explore different trajectories, reducing behavioral correlation and potentially improving stability and convergence speed.Different initial states, transitions, and policy randomness expose workers to different parts of the state space.Source: §A.1 · p. 14
- The controller broadcasts θ_k, averages workers’ function-value and gradient estimators, then solves the QCQP to obtain θ_{k+1}.The process repeats until convergence.Source: §A.1 · p. 14
A.2 Constrained Multi-agent Markov Decision Process
The constrained multi-agent extension targets fully collaborative transition-independent MDPs with agent-specific states, actions, and constraints but a shared global reward. It distributes the surrogate optimization across agents.
A.2 Constrained Multi-agent Markov Decision Process
- Each agent has its own state space, action space, transition model, and constraint, while the global reward depends on the joint states and actions.The agents are fully collaborative and their transition and cost functions do not depend on other agents.Source: §A.2 · pp. 14–15
- The multi-agent problem can be treated as a large single-agent problem whose constraints decompose across agents.The objective is manually split into agent-specific parts to enable distributed optimization.Source: §A.2 · p. 15
- Instead of solving one large QCQP, each agent solves its own convex relaxation problem in a distributed manner.This distributed procedure is presented as more efficient than optimizing with the overall parameter θ.Source: §A.2 · p. 15
- If an agent’s convex relaxation is infeasible, it solves a feasibility problem instead, and the process continues until convergence.The update is performed agent by agent within the distributed procedure.Source: §A.2 · p. 15
B Proof of Theorem 4
The proof establishes that the surrogate iterates converge almost surely to a feasible point satisfying the original problem’s KKT conditions. It combines regularity of the surrogate sequence with feasibility recovery when a convex relaxation is infeasible.
Proof conditions
- Uniform strong convexity and Lipschitz continuity provide the regularity needed for analyzing each surrogate objective sequence.These properties hold for the iteration-dependent surrogate functions.Source: B Proof of Theorem 4 · p. 15
- Equicontinuity, compactness, and bounded discounted rewards yield a uniformly convergent limit for the surrogate reward sequence, with analogous properties for the constraint sequence.The proof invokes the Arzela-Ascoli theorem for this convergence argument.Source: B Proof of Theorem 4 · p. 16
- The remaining convergence argument follows the established surrogate-optimization proof under Assumptions 1–3.The chosen surrogate functions satisfy the technical conditions required by the referenced result.Source: B Proof of Theorem 4 · p. 16
Theorem 4
- The iterates converge almost surely to the original feasible region, even when some convex relaxation subproblems are infeasible.The algorithm switches to an alternative feasibility problem in those iterations.Source: B Proof of Theorem 4 · p. 16
- At the convergent point, the original problem’s KKT conditions hold almost surely, establishing stationarity.This follows from the KKT conditions of the surrogate problem together with the Slater condition.Source: B Proof of Theorem 4 · p. 16