Exterior Penalty Policy Optimization with Penalty Metric Network under Constraints

1 Introduction

Deep reinforcement learning (RL) [Sutton and Barto, 2018] has demonstrated great potential in various real-world scenarios, including video games [Mnih et al., 2016; Wang et al., 2016; Vinyals et al., 2019], robotics control [Gu et al., 2016; Levine et al., 2016; Haarnoja et al., 2018], and Go [Silver et al., 2016; Silver et al., 2017]. However, many real-world problems inherit constraints when finding the optimal policy. For example, a robot agent should avoid obstacles while completing tasks. Such policy optimization with constraints is the focus of constrained RL (CRL), a critical field of RL research that expands the applicability of RL in real-world scenarios.

∗Corresponding Author.

CRL is generally modeled as Constrained Markov Decision Processes (CMDP) [Beutler and Ross, 1985; Ross and Varadarajan, 1989; Altman, 2021], in which agents aim to maximize rewards while satisfying constraints. CMDP integrates safety criteria in the form of constraints into RL and provides a fundamental mathematical framework.

Extensive research has been conducted in CMDP, but most existing methods have inherent oscillations or high computational complexity. CPO [Achiam et al., 2017] approximates the objective with a second-order expansion, leading to high computation costs of the high-dimensional inverse Fisher information matrix. Primal-dual methods convert constrained problems into unconstrained ones using the Lagrangian function to solve in the dual space. However, the learning dynamics exhibit high oscillations and constraint violations [Tessler et al., 2018; Yu et al., 2019; Paternain et al., 2019; Ding et al., 2020]. APPO [Dai et al., 2023] employs the augmented Lagrangian method to enhance the stability of the primal-dual algorithm, but it is sensitive to Lagrangian multiplier initialization [Chow et al., 2018; Stooke et al., 2020]. Projection-based methods, such as PCPO [Yang et al., 2020] and FOCOPS [Zhang et al., 2020], project actions back to the feasible region, presenting a costly computation and underperforming cumulative rewards [Zhang et al., 2023].

Penalty function methods impose constraints as penalties on the objective, addressing CRL in the primal space without introducing dual variables or requiring a complex secondorder Taylor expansion [Liu et al., 2020]. However, it is challenging to choose an appropriate penalty to trade off superior performance and efficient constraint satisfaction. An excessive penalty leads to a conservative policy that fails to explore the environment, while a minor penalty cannot guarantee the safety of the policy [Zhang et al., 2023]. IPO [Liu et al., 2020] restricts the policy within feasible regions with a logarithmic barrier function, which outputs excessive penalties near boundaries of the feasible region and cannot handle tasks where the initial policy violates constraints. P3O [Zhang et al., 2022] utilizes a linear penalty function with the ReLU operator to optimize policy. When constraints are severely violated, the linear relation cannot provide sufficient penalty to bring the policy back to the feasible region quickly.

In this paper, we divide the policy space based on the degree of constraint violation and introduce a Penalty Metric Network (PMN) comprising linear and quadratic cost value critics to capture penalties in different policy regions. The linear critic provides consistent incremental responses to small violations, while the quadratic critic imposes more severe penalties for larger violations, strongly discouraging substantial breaches. A dedicated weighting layer within PMN is used to aggregate different types of penalties, producing suitable penalties for efficient constraint satisfaction. A filter layer eliminates penalties in the feasible region, ensuring safe exploration for optimal performance. We propose a firstorder penalty function algorithm, Exterior Penalty Policy Optimization (EPO), which imposes penalties output from PMN on the objective to transform constrained policy optimization into an unconstrained one. EPO guarantees monotonically non-increasing constraints through convergence analysis by maximizing sequential subproblems. Furthermore, we present a surrogate penalty function using samples generated from the current policy and theoretically provide the worstcase constraint violation and approximation error. In practice, EPO employs a smooth surrogate penalty function and an adaptive penalty factor adjustment strategy to ensure a stable training process. Extensive experiments on challenging tasks demonstrate that EPO achieves faster constraint satisfaction and better policy performance compared to multiple baseline algorithms.

In summary, our contributions are as follows:

• We design the Penalty Metric Network (PMN) to capture suitable constraint penalties in different policy regions.
• We propose the EPO algorithm based on PMN, which guarantees stable convergence and efficient constraint satisfaction. Theoretical guarantees on worst-case constraint violation and approximation errors are provided.
• We conduct extensive experiments to compare EPO with multiple state-of-the-art algorithms. EPO outperforms the baselines with higher performance and better constraint satisfaction.

2 RelatedWork

In the tabular case, the CMDP problem has been extensively studied [Beutler and Ross, 1986; Ross, 1989; Ross and Varadarajan, 1991]. For high-dimensional problems, RL with constraints is a challenging topic. Many methods have been proposed in recent years, which can be roughly divided into primal methods and primal-dual methods.

Primal-Dual methods. Primal-dual methods transform constrained problems into unconstrained ones by introducing dual variables [Chow et al., 2017; Ding et al., 2021]. [Tessler et al., 2018] propose multi-timescale Lagrangian methods, which utilize penalty signals to guide the policy update towards constraint satisfaction. The traditional Lagrangian multiplier update behaves as integral control, and [Stooke et al., 2020] introduce proportional and differential control to reduce cost overshoot and oscillations in the learning dynamics. [Ding et al., 2020] establish the global convergence with sublinear rates regarding the optimality gap. The Augmented Lagrangian method is introduced in [Dai et al.,

2023] to reduce the oscillations during training. However, primal-dual approaches are still sensitive to initial parameters, limiting their applicability [Zhang et al., 2022].

Primal methods. Primal methods directly optimize the constrained problem in the primal space [Chow et al., 2018; Chow et al., 2019; Dalal et al., 2018; Yu et al., 2022]. CPO [Achiam et al., 2017] provides a lower bound on performance and an upper bound on constraint violation. PCPO [Yang et al., 2020] first improves the reward within the trust region, then projects the policy to the feasible region. However, second-order methods in CPO and PCPO, which are based on local policy search [Peters and Schaal, 2008], encounter computational challenges due to the high-dimensional Hessian matrix. FOCOPS [Zhang et al., 2020] proposes a first-order policy optimization method, which first solves the constraint problem in the nonparametric policy space and then projects the updated policy back into the parametric space. CUP [Yang et al., 2022] provides generalized theoretical guarantees for surrogate functions with a generalized advantage estimator [Schulman et al., 2015], effectively reducing variance while maintaining acceptable bias. However, projection approaches have poor performance since the correction only ensures feasibility but lacks equivalence with optimality [Zhang et al., 2023]. All the above methods involve solving primaldual subproblems, and the introduced dual variables lead to an unstable training process. Our approach offers a simpler first-order optimization method in the primal space, ensuring the stability of constraint satisfaction.

IPO [Liu et al., 2020] augments the objective with a logarithmic barrier function to restrict the policy to feasible regions. However, the logarithmic function becomes ineffective when constraints are violated, limiting the agent's exploration. P3O [Zhang et al., 2022] penalizes constraints with a ReLU operator to obtain an unconstrained problem. However, the linear penalty function in P3O cannot provide significant penalties for severe constraint violations, and the ReLU operator is non-differentiable at constraint boundaries, resulting in inaccurate gradient information. Compared to P3O and IPO, our PMN provides more appropriate penalties based on policy regions for faster constraint satisfaction. Theoretically, EPO provides convergence guarantees, continuous improvement constraints, and approximation errors, guaranteeing better performance and constraint satisfaction.

3 Preliminaries

RL can be modeled as a Markov decision process (MDP), represented by a tuple (S, A, R, P, ρ, γ), where S denotes the state space, A denotes the action space, R : S × A → R is the reward function, P : S × A → [0, 1] is the transition probability function, ρ is the initial state distribution, and γ ∈ (0, 1) is the discount factor of the reward. The policy π : S → A maps states to probability distributions over actions, where π(a|s) is the probability of choosing action a in state s, and Π is the set of all stationary policies. The discounted future state visitation distribution is defined as dπ (s) := (1 - γ) ∑∞t=0 γ tP(st = s|π). In RL, we aim to find the optimal policy by maximizing the expected discounted return JR(π) := Eτ∼π[∑∞t=0 γ tR(st, at)], where

τ = (s0, a0, s1, a1, · · · ) denotes the trajectory based on policy π. The value function based on policy π is V π R (s) := Eτ∼π[∑∞t=0 γ tR(st, at)|s0 = s], and action-value function is QπR(s, a) := Eτ∼π[∑∞t=0 γ tR(st, at)|s0 = s, a0 = a]. The advantage function measures the advantage of action a over the mean value: AπR(s, a) := QπR(s, a) - V π R (s).

The CMDP (S,A,R,C, P, ρ, γ) introduces constraints to the MDP to restrict allowable policies. C : S ×A → R is the cost function, mapping state-action pairs to costs. d denotes the constraints threshold, the expected cumulative discount cost aims to satisfy JC(π) := Eτ∼π[∑∞t=0 γ tC(st, at)] ≤ d. The cost value function V π C (s), cost action-value function QπC (s, a) and cost advantage function AπC (s, a) in CMDP can be obtained as in MDP by replacing the reward R with the cost C. The CRL aims to find an optimal policy by maximizing the expected discount return over the set of feasible policies ΠC := {π ∈ Π : JC(π) ≤ d}:

The following equation gives the performance difference between two arbitrary policies [Kakade and Langford, 2002]:

This implies that iterative updates to the policy, π′ (s) = argmaxa AπR(s, a), lead to performance improvement until convergence to the optimal solution.

4 Methodology

In this section, we present the EPO algorithm and its theoretical foundation. We first show the structure of the PMN. Then, we propose the EPO method based on the PMN. The convergence analysis and error bound are provided to ensure effectiveness. Finally, we propose a smooth penalty function with penalty factor terms, which can be easily optimized in practice using a first-order optimizer.

4.1 Exterior Penalty Function with PenaltyMetric Network

According to the performance difference equation (2), our problem is defined as a constrained optimization problem:

where policy π ∈ Πθ is parameterized with parameters θ, and πk represents the current policy. For simplification, we introduce the notations to represent the above objective function FR(π) := Es∼dπ ,a∼π[Aπk R (s, a)] and constraint function FC(π) := JC(πk) + 1 1-γ Es∼dπ ,a∼π [Aπk C (s, a)] - d.

FC(π) can be considered as a measure of the constraint distance between policy π and the constraint boundaries in the policy space, indicating the degree of constraint violation. We normalize FC(π) across samples in the current replay buffer for uniform scaling. Then we divide the policy space into near-boundary region and far-boundary region according to FC(π), defining the penalties within these regions as nearpenalty and far-penalty, respectively.

We propose a Penalty Metric Network to capture penalties across various regions. The PMN consists of two streams, representing the near-penalty and the far-penalty, as shown in Figure 1. We construct the linear cost value critic VN(s) and the quadratic cost value critic VF (s) as the backbone of nearpenalty and far-penalty streams, respectively. Both critics are designed to provide sufficient penalties in their respective regions, ensuring efficient constraint satisfaction. For sufficient safety exploration, a filter layer eliminates negative values in both critics to ensure the penalty in the feasible region is 0. A weighting layer then integrates the two streams to generate a penalty metric for the current policy. We denote the PMN as a function Φ(F + C (π)):

where α ∈ [0, 1] is the weight factor in weighting layer, and F + C (π) = max{(FC(π)), 0}, max{·} represents the filter operation. Imposing the penalty metric Φ(F + C (π)) to the objective function FR(π), we obtain the exterior penalty function P(π, µ), which transforms the original constrained problem into an unconstrained one:

where µ > 0 denotes the penalty factor. Now we get the new objective for (3) by maximizing the penalty function:

When constraints are satisfied, the objective focuses solely on maximizing the expected return. Conversely, when constraints are violated, the objective shifts to maximizing the expected return while simultaneously minimizing the cost.

Our Penalty Metric Network with linear and quadratic value estimators can provide appropriate penalties and bring the policy back to the feasible region ΠC quickly.

Properties 1. Normalize the FC(π) and define the policy space for FC(π) ≤ 1 2 as the near-boundary region, for FC(π) > 1 as the far-boundary region, and for 1 2 < FC(π) ≤ 1 as the mid-boundary region. Increasing α provides increased penalty Φ(F + C (π)) and gradient |∇πΦ(F + C (π))| in the near-boundary region. Decreasing α provides increased penalty Φ(F + C (π)) and gradient |∇πΦ(F + C (π))| in the far-boundary region. Increasing α provides increased penalty Φ(F + C (π)) and reduced gradient |∇πΦ(F + C (π))| in the mid-boundary region.

The weight α in the weighting layer is chosen based on FC(π). This ensures that PMN consistently generates large penalties and gradients when constraints are violated, enabling the policy to quickly return to the feasible region. In this paper, we set α = 0 in the far-boundary region, 1 in the near-boundary region, and 0.5 in the mid-boundary region.

We use two neural networks VN(υ) and VF (ψ), parameterized by υ and ψ respectively, to capture the near-boundary cost value and far-boundary cost value. The Penalty Metric Network is updated by:

4.2 Exterior Penalty Policy Optimization and Convergence Analysis

Consider a decreasing sequence of penalty factors {µt} with µt → 0 as t → ∞, where t denotes the iteration number of penalty factor. For each penalty factor µt, we solve a maximization problem of the penalty function P(π, µt) to obtain the corresponding global maximum policy πt. By decreasing the penalty factor µt, the updated policy in EPO is guided towards the feasible region and eventually converges to the optimal policy under certain conditions. Below, we present the theoretical guarantees.

Lemma 1. Suppose πt is the global maximum policy of the penalty function P(π, µt) with factor µt, ¯π is the optimal solution of the constrained problem (3), and FR(π) is the objective function, then the inequality holds

Decreasing the penalty factor µt+1 < µt, we get

The constraint FC(πt) is monotonically non-increasing with the decreasing µt and same α if constraint is violated

Proof. See the supplemental material.

Lemma 1 demonstrates that when the policy πt violates constraints, the maximum value of the penalty function P(πt, µt) is greater than or equal to the optimal value FR(¯π) of problem (3). By decreasing the penalty factor from µt to µt+1, both P(πt+1, µt+1) and FR(πt+1) approach the solution FR(¯π), and the policy approaches the feasible region with a monotonically non-increasing constraint. Furthermore, we establish the conditions ensuring that the updated policy in the penalty function satisfies the constraints.

Theorem 1. Define a decreasing sequence of penalty factors {µt}, suppose that the objective function FR(π) has an upper bound and πt is the global maximum policy of penalty function P(π, µt) with factor µt. When µt → 0, the corresponding limit π∗ of the sequence {πt} is a solution of the constrained problem (3).

Corollary 1. Consider the weight factor α = 1, πt is the global maximum policy of penalty function P (π, µt) with factor µt, λ∗ is the Lagrange multiplier corresponding to the optimum ¯π of the primal problem. When µt < 1 ∥λ∗ ∥∞ , πt is the solution of the constrained problem (3).

Proof. See the supplemental material.

According to Theorem 1, we need to solve the sequential subproblems with decreasing µt to obtain the optimal solution of the problem (3). As µt decreases, policy πt converges to the optimal policy. Corollary 1 guides us to raise α to 1 within the near-boundary region, guaranteeing the policy returns to the feasible region with a finite penalty factor.

Algorithm 1 EPO: Exterior Penalty Policy Optimization

Input: Initialize policy network πθ, value networks V ω R , V υ N and V ψ F . Set the hyperparameter for PPO clip rate, µ, α for penalty function and learning rate η.

Output: The optimal policy parameter θ.

• 1: for epoch k = 0, 1, 2, ... do
• 2: Sample N trajectories τ1, ..., τN under the current policy πθk .
• 3: Process the trajectories to C-returns, and calculate advantage functions with V υ N and V ψ F .
• 4: for K iterations do
• 5: Update value networks V ω R , V υ N and V ψ F .
• 6: Update policy network πθ with firstorder optimizer θk+1 = θk + η ▽θ (LCLIP R (θ) -Ψ(µ)Φ(log(1+ eLCLIP C (θ) ))).

• 9: end if
• 10: end for
• 11: Decrease µt+1 ∈ (0, µt) and adjust α ∈ [0, 1] based on FC(π).
• 12: end for
• 13: return policy parameters θ = θk+1.

4.3 Surrogate Penalty Function within Trust Region and Theoretical Bounds

The complex dependency of state visitation distribution dπ (s) on the unknown policy π makes (6) difficult to optimize directly. In this paper, we use samples generated by the current policy πk to locally approximate the original problem (3) within the trust region:

where Πθ represents the policy set parameterized by parameter θ, D(π∥πk) = Es∼πk [DKL(π∥πk)[s]], DKL is the KL divergence, and δ > 0 is the step size. The set {π ∈ Πθ : D(π∥πk) ≤ δ} is the trust region. The surrogate objective and constraint are defined in a simplified formulation:

Then the surrogate penalty objective function is:

EPO is a trust region method, so it satisfies the worst-case bound for the updated policy in CPO.

Proposition 1 ([Achiam et al., 2017]). Suppose surrogate constraint Lπk C (πk+1) is satisfied, the upper bound on constraint violation for each update is

The local approximation approach introduces bias. We further give the worst-case error bound for the surrogate penalty function compared to the original penalty function. We denote the surrogate penalty function for problem (11) as P πk (π, µt) = Lπk R (π) - 1 µt Φ(Lπk+ C (π)).

Theorem 2. Suppose surrogate constraint Lπk C (π) is satisfied, the upper bound on the approximation error between the surrogate and the original penalty functions is

where ϵπR := maxs |Ea∼π[Aπk R (s, a)]|, and ϵπC := maxs |Ea∼π[Aπk C (s, a)]|.

Proof. See the supplemental material.

4.4 Smooth Penalty Function in Practical Implementation

The penalty function in (13) is mostly smooth except at the constraint boundary. However, the constraint boundary is crucial in CRL, particularly when the optimal policy lies close to it. The first-order optimizer needs precise gradient information during policy updates. To address these issues, we propose a novel smooth penalty function containing smoothing and factor terms in the implementation:

where log denotes the natural logarithm, log(1 + eFC(π) ) is the smoothing term. Φ(x) = αx + (1 - α)x2 represents the penalty term, Ψ(µ) is the penalty factor term.

The smooth term ensures that the penalty function remains differentiable throughout the parameter space. The adaptive factor function Ψ(µ) serves as a strategy for determining the penalty factor based on the empirical value of FC, and it remains detached from the gradient calculation. This effectively reduces the frequency of factor adjustments, thus decreasing the number of sub-problems. For this implementation version in (16), Lemma 1 still guarantees monotonically non-increasing constraints, and Theorem 1 ensures that the practical policy converges to the feasible region. The proof is shown in the supplemental material.

To address the divergence constraint in the surrogate objective function (11), we employ the clipped surrogate function of the PPO [Schulman et al., 2017] for approximation. Then, we get the final penalty objective in practice:

where r(π) = π πk is the importance sampling ratio, ϵ is the clip ratio. Algorithm 1 presents a summary of EPO.

5 Experiment

We train different agents and design comparison experiments in four navigation tasks based on Safety Gymnasium [Brockman et al., 2016] and four MuJoCo physical simulator tasks [Todorov et al., 2012]. Baselines include the primal-dual method PPO Lagrangian [Chow et al., 2017; Schulman et al., 2017], the second-order optimization method CPO [Achiam et al., 2017], the augmented Lagrangian method APPO [Dai et al., 2023], and the penalty function method IPO [Liu et al., 2020] and P3O [Zhang et al., 2022]. For fairness of the results, we conduct multiple comparison experiments in the same environment and with the same settings. Extensive experiments demonstrate that (1) EPO outperforms current state-of-the-art algorithms on policy performance and constraint satisfaction, and (2) provides stable convergence and fewer constraint violations during training.

Scenario Description. All tasks aim to maximize the expected reward (the higher, the better) while satisfying the constraint (the lower, the better). In Safety Gymnasium, we train different agents, including Point and Car, for various navigation tasks: (1) the Goal task, where agents navigate to the goal location while circumventing hazards, and (2) the Button task, where agents navigate to the goal button and touch the correct goal button while avoiding gremlins and hazards. Additionally, we test the more difficult Goal2 and Button2 tasks, requiring avoiding more hazards and vases, which have not been proven to be effectively solved by baselines. In Safety MuJoCo, different agents are rewarded for running along a straight line with a velocity limit for safety and stability.

Safety Gymnasium. Navigation tasks in Safety Gymnasium with infeasible initial policies are challenging. Figure 2 presents the learning curves of EPO and baselines. Table 1 in the supplemental material shows the mean performance of different algorithms. EPO demonstrates impressive policy performance and faster constraint satisfaction compared to baselines in challenging tasks. In tasks with infeasible initial policies, EPO converges faster and generates fewer constraint violations, as illustrated in Table 2 in the supplemental material, demonstrating the effectiveness of PMN in providing appropriate penalties when constraints are violated. In contrast, IPO tends to generate conservative policies restricted by excessive penalties and struggles with infeasible initial policies for constraint satisfaction. P3O fails to provide enough penalties when the initial constraint is large, resulting in a slow decrease in constraints. PPO Lagrangian requires waiting for an increase in the dual variable to mitigate constraints, leading to a slower convergence rate of constraints. APPO outperforms PPO Lagrangian in performance and stability but is sensitive to the initial Lagrangian multiplier. In PointGoal2-v0 and PointButton2-v0, most baselines update the policy conservatively to ensure constraint satisfaction, while EPO shows better performance under the cost limit.

Safety MuJoCo. To increase the challenge, we set a cost limit of 25 for all tasks in Safety MuJoCo. Figure 3 illustrates the learning curves of EPO and baseline algorithms. The results indicate that EPO maintains excellent performance with stable training processes, keeping the policy in the feasible region for tasks with feasible initial policies. P3O struggles to provide suitable penalties to keep the policy within the feasible domain, showing poor performance in Swimmerv4. In Safety MuJoCo tasks, the optimal policy often resides near constraint boundaries, while the ReLU operator used in P3O eliminates gradient information around these boundaries, making it challenging to identify the optimal policy. Experimental results demonstrate the effectiveness of our smooth penalty function, leading to enhanced policy performance. CPO shows faster performance convergence than EPO in Ant-v4. However, the computational burden imposed by the inverse of the high-dimensional Fisher information matrix leads to training times more than twice as long as EPO. PPO Lagrangian outperforms EPO in HalfCheetah-v4 and Humanoid-v4 due to the slower updates of Lagrange multipliers compared to policy iterations. The policy is not penalized promptly when it reaches the infeasible region, which leads to higher rewards but large constraint oscillations. APPOmitigates these oscillations through the augmented Lagrangian method but decreases policy performance.

Ablation Experiments. We conduct ablation experiments to verify the effectiveness of components in EPO. First, we compare the PMN with linear and quadratic critics. The results in Figure 4(a)(b) show the EPO with PMN outperforms the other two. The linear critic imposes larger penalties near the constraint boundary, guiding the policy to the feasible region, while the quadratic one imposes larger penalties far from the boundary, accelerating the policy to approach the feasible region. PMN combines the benefits from the linear and quadratic critics, making a trade-off between constraint satisfaction and reward maximization based on the degree of constraint violation. Second, we compare the smooth EPO function with the non-smooth ReLU function, the results in Figure 4(c)(d) show that the smooth function enhances training stability, especially near constraint boundaries, by providing gradient information across the policy space.

Cost Limit Sensitivity. We further verify the robustness of EPO at various threshold levels. Figure 5 indicates that our method can satisfy different constraint limits while maintaining good policy performance.

6 Conclusion

In this work, we propose Exterior Penalty Policy Optimization (EPO) for training CRL agents with superior performance and efficient constraint satisfaction. The Penalty Metric Network (PMN) generates appropriate penalties for fast constraint satisfaction in the infeasible region and safe exploration in the feasible region. Convergence analysis guarantees consistent constraint satisfaction. We further provide the worst-case constraint violation and approximation error analysis for the surrogate function, along with a practical implementation of EPO. EPO is compared with multiple baselines across a wide range of safety tasks, demonstrating its effectiveness in ensuring constraint satisfaction while maintaining policy performance. Future work includes adopting offpolicy methods and addressing different types of constraints.

Acknowledgments

This work was supported by the National Key Research and Development Plan No. 2022YFB3904204, NSF China under Grant No. 62202299, 62020106005, 61960206002, Shanghai Natural Science Foundation No. 22ZR1429100.