# Penalized Proximal Policy Optimization for Safe Reinforcement Learning

Linrui Zhang1 This work was done during Linrui Zhang’s internship at JD
Explore Academy, Beijing, China. Li Shen2 Corresponding Author. Long Yang3
Shixiang Chen2
Xueqian Wang1 Bo Yuan1 Dacheng Tao2 1Tsinghua Shenzhen International Graduate
School, Tsinghua University
2JD Explore Academy
3 School of Artificial Intelligence, Peking University
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Safe reinforcement learning aims to learn the optimal policy while satisfying
safety constraints, which is essential in real-world applications. However,
current algorithms still struggle for efficient policy updates with hard
constraint satisfaction. In this paper, we propose Penalized Proximal Policy
Optimization (P3O), which solves the cumbersome constrained policy iteration
via a single minimization of an equivalent unconstrained problem.
Specifically, P3O utilizes a simple-yet-effective penalty function to
eliminate cost constraints and removes the trust-region constraint by the
clipped surrogate objective. We theoretically prove the exactness of the
proposed method with a finite penalty factor and provide a worst-case analysis
for approximate error when evaluated on sample trajectories. Moreover, we
extend P3O to more challenging multi-constraint and multi-agent scenarios
which are less studied in previous work. Extensive experiments show that P3O
outperforms state-of-the-art algorithms with respect to both reward
improvement and constraint satisfaction on a set of constrained locomotive
tasks.

##  1 Introduction

Reinforcement Learning (RL) has achieved significant successes in playing
video games Vinyals et al. (2019), robotic manipulation Levine et al. (2016),
mastering Go Silver et al. (2017), etc. However, standard RL merely maximizes
cumulative rewards, which may lead to undesirable behaviors in real-world
applications especially for safety-critical tasks.

It is intractable to learn reasonable policies by directly penalizing unsafe
interactions onto the reward function, since varied intensities of the
punishment result in different Markov decision processes. There is still a
lack of theories revealing the explicit relationship between policy
improvement and safety satisfaction via reward shaping.

Constrained Markov decision process (CMDP) Altman (1999) is a more practical
and popular formulation that requires the agent to perform actions under given
constraints. A common approach to solving such constrained sequential
optimization is approximating the non-convex constraint function to a
quadratic optimization problem via Taylor’s formulation Achiam et al. (2017);
Yang et al. (2020). However, those algorithms still have the following
drawbacks: (1) The convex approximation to a non-convex policy optimization
results in non-negligible approximate errors and only learns near constraint-
satisfying policies; (2) The closed-form solution to the primal problem
involves the inversion of Hessian matrix, which is computationally expensive
in large CMDPs with deep neural networks; (3) If there is more than one
constraint, it is cumbersome to obtain the analytical solution without an
extra inner-loop optimization, which limits their applications in multi-
constraint and multi-agent scenarios; (4) If the primal problem is infeasible
under certain initial policies, above algorithms require additional
interactions for feasible recovery, which reduces their sample-efficiency.

To address above issues, we propose Penalized Proximal Policy Optimization
(P3O) algorithm that contains two key techniques. Firstly, we employ exact
penalty functions to derive an equivalent unconstrained optimization problem
that is naturally compatible with multiple constraints and arbitrary initial
policies. Secondly, we extend the clipped surrogate objective in Proximal
Policy Optimization (PPO) Schulman et al. (2017) to CMDPs, which eliminates
the trust-region constraint on both reward term and cost term. As a
consequence, our method removes the need for quadratic approximation and
Hessian matrix inversion. By minimizing the unconstrained objective instead,
the solution to the primal constrained problem can be obtained.

Conclusively, the proposed P3O algorithm has three main strengths: (1)
accuracy: P3O algorithm is accurate and sample-efficient with first-order
optimization over a theoretically equivalent unconstrained objective instead
of solving an approximate quadratic optimization; (2) feasibility: P3O
algorithm could admit arbitrary initialization with a consistent objective
function and doesn’t need additional recovery methods for infeasible policies;
(3) scalability: P3O is naturally scalable to multiple constraints or agents
without increasing complexity due to the exact penalty reformulation.

In the end, we summarize our contributions as four-fold:

  * •

We propose the Penalized Proximal Policy Optimization (P3O) algorithm for safe
RL, which employs first-order optimization over an equivalent unconstrained
objective.

  * •

We theoretically prove the exactness of the penalized method when the penalty
factor is sufficiently large (doesn’t have to go towards positive infinity)
and propose an adaptive penalty factor tuning algorithm.

  * •

We extend clipped surrogate objectives and advantage normalization tricks to
CMDPs, which are easy to implement and enable a fixed penalty factor for
general good results across different tasks.

  * •

We conduct extensive experiments to show that P3O outperforms several state-
of-the-art algorithms with respect to both reward improvement and constraint
satisfaction and demonstrate its efficacy in more difficult multi-constraint
and multi-agent scenarios which are less studied in previous safe RL
algorithms.

##  2 Related Work

Safety in reinforcement learning is a challenging topic formally raised by
Garcıa and Fernández Garcıa and Fernández (2015). Readers can refer to the
survey Liu et al. (2021) for recent advances in safe RL. In this section, we
only summarize the most related studies to our algorithm.

#### Primal-Dual solution.

Considering the success of Lagrangian relaxation in solving constrained
optimization problems, Primal-Dual Optimization (PDO) Chow et al. (2017) and
its variants Tessler et al. (2018); Stooke et al. (2020) leverage the
Lagrangian Duality in constrained reinforcement learning. Although plenty of
work has provided rigorous analysis on duality gap Paternain et al. (2019),
non-asymptotic convergence rate Ding et al. (2020) and regret bound Ding et
al. (2021), Primal-dual methods are still hard to be implemented and applied
in practical use due to their sensitivity to the initialization as well as the
learning rate of Lagrangian multipliers.

#### Primal solution.

Constrained Policy Optimization (CPO) Achiam et al. (2017) directly searches
the feasible policy in the trust region and guarantees a monotonic performance
improvement while ensuring constraint satisfaction by solving a quadratic
optimization problem with appropriate approximations. Projection-based CPO
Yang et al. (2020) updates the policy in two stages by firstly performing
regular TRPO Schulman et al. (2015) and secondly projecting the policy back
into the constraint set. Those methods based on local policy search mainly
suffer from approximate errors, the inversion of high-dimensional Hessian
matrices, and the poor scalability to multiple constraints. To address
drawbacks of the quadratic approximation, FOCOPS Zhang et al. (2020) solves
the optimum of constrained policy optimization within the non-parametric space
and then derives the first-order gradients of the $\ell_{2}$ loss function
within the parameter space. Nevertheless, FOCOPS has more auxiliary variables
to learn than our first-order optimization objective, and the analytical
solutions of FOCOPS are not straightforward with the increasing number of
constraints.

The most similar work to our proposed algorithm is Interior-point Policy
Optimization (IPO) Liu et al. (2020) which uses log-barrier functions as
penalty terms to restrict policies into the feasible set. However, the
interior-point method requires a feasible policy upon initialization which is
not necessarily fulfilled and needs a further recovery. Moreover, the log-
barrier function possibly leads to numerical issues when the penalty term goes
towards infinity, or the solution is not exactly the same as the primal
problem. By contrast, we employ the exact penalty function to derive an
equivalent unconstrained objective and restrict policy updates in the trust
region by clipping the important sampling ratio on both reward and cost terms
for the approximate error reduction, which is different from the prior work.

##  3 Preliminaries

A Markov decision process (MDP) Sutton and Barto (2018) is a tuple
$(S,A,R,P,\mu)$ ,where $S$ is the state space, $A$ is the action space,
$R:S\times A\times S\mapsto\mathbb{R}$ is the reward function, $P:S\times
A\times S\mapsto[0,1]$ is the transition probability function to describe the
dynamics of the environment, and $\mu:S\mapsto[0,1]$ is the initial state
distribution. A stationary policy $\pi:S\mapsto\cal{P}(A)$ maps the given
states to probability distributions over action space and $\Pi$ denotes the
set of all stationary policies $\pi$. The optimal policy $\pi^{*}$ maximizes
the expected discounted return
$J_{R}(\pi)=\mathop{\mathbb{E}}_{\tau\sim\pi}\big{[}\sum^{\infty}_{t=0}\gamma^{t}R(s_{t},a_{t},s_{t+1})\big{]}$
where $\tau=\\{(s_{t},a_{t})\\}_{t\geq 0}$ is a sample trajectory and
$\tau\sim\pi$ indicates the distribution over trajectories depending on
$s_{0}\sim\mu,a_{t}\sim\pi(\cdot|s_{t}),s_{t+1}\sim P(\cdot|s_{t},a_{t})$. The
value function is defined as
$V_{R}^{\pi}(s)=\mathop{\mathbb{E}}_{\tau\sim\pi}\big{[}\sum^{\infty}_{t=0}\gamma^{t}R(s_{t},a_{t},s_{t+1})|s_{0}=s\big{]}$,
the action-value function is defined as
$Q_{R}^{\pi}(s,a)=\mathop{\mathbb{E}}_{\tau\sim\pi}\big{[}\sum^{\infty}_{t=0}\gamma^{t}R(s_{t},a_{t},s_{t+1})|s_{0}=s,a_{0}=a\big{]}$
and the advantage function is defined as
$A_{R}^{\pi}(s,a)=Q_{R}^{\pi}(s,a)-V_{R}^{\pi}(s)$.

A constrained Markov decision process (CMDP) Altman (1999) extends MDP with a
constraint set $C$ consisting of cost functions $C_{i}:S\times A\times
S\mapsto\mathbb{R},\ i=1,2,...,m$. We define the expected discounted cost-
return
$J_{C_{i}}(\pi)=\mathop{\mathbb{E}}_{\tau\sim\pi}\big{[}\Sigma^{\infty}_{t=0}\gamma^{t}C_{i}(s_{t},a_{t},s_{t+1})\big{]}$
and $V_{C_{i}}^{\pi},Q_{C_{i}}^{\pi},A_{C_{i}}^{\pi}$ similarly in MDPs. The
set of feasible stationary policies for a CMDP is denoted as
$\Pi_{C}=\\{\pi\in\Pi\ |J_{C_{i}}(\pi)\leq d_{i},\ \forall i\\}$, where
$d_{i}$ is the upper limit of the corresponding safety or cost constraint. The
goal of safe RL is to find an optimal policy over the hard safe constraint,
i.e., $\pi^{*}=\mathop{\arg\max}_{\pi\in\Pi_{C}}J_{R}(\pi)$.

##  4 Methodology

Iterative search for optimal policy is commonly used in literature Schulman et
al. (2015); Achiam et al. (2017); Zhang et al. (2020). We formulate the
unbiased constrained policy optimization problem over $s\sim d^{\pi}$ and
$a\sim\pi$ as:

$\displaystyle\pi_{k+1}=\mathop{\arg\max}_{\pi}\mathop{\mathbb{E}}_{\begin{subarray}{c}s\sim
d^{\pi}\\\ a\sim\pi\end{subarray}}[A^{\pi_{k}}_{R}(s,a)]$ (1)
$\displaystyle\mathrm{s.t.}\quad
J_{C_{i}}(\pi_{k})+\frac{1}{1-\gamma}\mathop{\mathbb{E}}_{\begin{subarray}{c}s\sim
d^{\pi}\\\ a\sim\pi\end{subarray}}\big{[}A_{C_{i}}^{\pi_{k}}(s,a)\big{]}\leq
d_{i},\ \forall i.$

where $d^{\pi}(s)=(1-\gamma)\sum^{\infty}_{t=0}\gamma^{t}P(s_{t}=s|\pi)$
denote the discounted future state distribution.

######  Proposition 1.

The new policy $\pi_{k+1}$ obtained from the current policy $\pi_{k}$ via
problem (1) yields a monotonic return improvement and hard constraint
satisfaction.

###### Proof.

See the supplemental material. ∎

In this paper, we consider the parametric policy $\pi(\theta)$, i.e., using
the neural network. Let $r(\theta)=\frac{\pi(\theta)}{\pi(\theta_{k})}$ be the
importance sampling ratio, then we rewrite the optimization problem (1) as
follows:

$\begin{aligned}
&\theta_{k+1}=\mathop{\arg\min}_{\theta}\mathop{\mathbb{E}}_{\begin{subarray}{c}s\sim
d^{\pi}\\\ a\sim\pi_{k}\end{subarray}}[-r(\theta)A^{\pi_{k}}_{R}(s,a)]\\\
&\mathrm{s.t.}\ \mathop{\mathbb{E}}_{\begin{subarray}{c}s\sim d^{\pi}\\\
a\sim\pi_{k}\end{subarray}}\big{[}r(\theta)A_{C_{i}}^{\pi_{k}}(s,a)\big{]}+(1-\gamma)(J_{C_{i}}(\pi_{k})-d_{i})\leq
0,\ \forall i.\\\ \end{aligned}$

(2)

Different from previous methods Achiam et al. (2017); Yang et al. (2020) that
approximate non-convex problem (2) to convex optimization via Taylor’s
formulation on the trust region, we penalize constraints with ReLU operators
to the objective function which yields an unconstrained problem:

$\begin{aligned}
\theta_{k+1}&=\mathop{\arg\min}_{\theta}\mathop{\mathbb{E}}_{\begin{subarray}{c}s\sim
d^{\pi}\\\
a\sim\pi_{k}\end{subarray}}[-r(\theta)A^{\pi_{k}}_{R}(s,a)]+\kappa\sum_{i}\max\\{0,\\\
&\quad\mathop{\mathbb{E}}_{\begin{subarray}{c}s\sim d^{\pi}\\\
a\sim\pi_{k}\end{subarray}}\big{[}r(\theta)A_{C_{i}}^{\pi_{k}}(s,a)\big{]}+(1-\gamma)(J_{C_{i}}(\pi_{k})-d_{i})\\}.\end{aligned}$

(3)

Intuitively, the penalized term takes effect when the agent violates the
corresponding constraint; otherwise, the objective equals the standard policy
optimization when all constraints are fulfilled. Below, we theoretically
analyze the equivalence between problem (2) and problem (3), i.e., the ReLU
operator constructs an exact penalty function with a finite penalty factor
$\kappa$. To our best knowledge, it is the first work to solve the constrained
policy optimization in the perspective of the exact penalty method.

######  Theorem 1.

Suppose $\bar{\lambda}$ is the corresponding Lagrange multiplier vector for
the optimum of problem (2). Let the penalty factor $\kappa$ be a sufficiently
large constant ($\kappa\geq||\bar{\lambda}||_{\infty}$), problem (2) and
problem (3) share the same optimal solution set.

###### Proof.

See the supplemental material. ∎

Notably, the finiteness of penalty factor $\kappa$ in Theorem 1 is critical
for policy updates because popular methods like square loss function and log-
barrier function require the penalty term to go towards positive infinity for
an infeasible solution. Otherwise, the optimal solution is not exactly the
same as problem (2) Liu et al. (2020). However, this would bring about
numerical issues in practice and result in unbounded approximate error which
will be discussed later.

By now, we construct an equivalent unconstrained objective with ReLU operators
and a finite penalty factor $\kappa$. It is still intractable to solve problem
(3) directly over the unknown future state distribution $s\sim d^{\pi}$ except
for cumbersome off-policy evaluation Jiang and Li (2016) from current policy
$\pi_{k}$. We replace $s\sim d^{\pi}$ with $s\sim d^{\pi_{k}}$ and minimize
the unconstrained objective over collected trajectories:

$\begin{aligned}
\theta_{k+1}\\!\\!&=\mathop{\arg\min}_{\theta}\mathop{\mathbb{E}}_{\begin{subarray}{c}s\sim
d^{\pi_{k}}\\\
a\sim\pi_{k}\end{subarray}}[-r(\theta)A^{\pi_{k}}_{R}(s,a)]+\kappa\sum_{i}\max\\{0,\\\
&\quad\mathop{\mathbb{E}}_{\begin{subarray}{c}s\sim d^{\pi_{k}}\\\
a\sim\pi_{k}\end{subarray}}\big{[}r(\theta)A_{C_{i}}^{\pi_{k}}(s,a)\big{]}+(1-\gamma)(J_{C_{i}}(\pi_{k})-d_{i})\\}.\end{aligned}$

(4)

This results in biases w.r.t problem (3), and we further provide the analysis
of approximate error for that replacement.

Algorithm 1 P3O: Penalized Proximal Policy Optimization

Input: initial policy $\pi_{\theta_{0}}$, value function $V^{\phi_{0}}_{R}$
and each cost-value function $V^{\psi^{i}_{0}}_{C_{i}},\forall i.$

1: for $k\mathrm{\ in\ }0,1,2,...K$ do

2: Collect set of trajectories $\mathcal{D}_{k}$ with policy
$\pi_{\theta_{k}}$.

3: Compute $\hat{R}_{t}=\sum^{T-t}_{k=0}\gamma^{k}R_{t+k}$ and
$\hat{A}^{\pi_{\theta_{k}}}_{R}(s_{t},a_{t})$.

4: Compute $\hat{C}^{i}_{t}=\sum^{T-t}_{k=0}\gamma^{k}C^{i}_{t+k}$ and
$\hat{A}^{\pi_{\theta_{k}}}_{C_{i}}(s_{t},a_{t}),\forall i$.

5: Update $\pi_{\theta_{k+1}}$ using Algorithm 2.

6:
$\phi_{k+1}=\mathop{\arg\min}_{\phi}\frac{1}{|\mathcal{D}_{k}|T}\sum(V^{\phi_{k}}_{R}(s_{t})-\hat{R}_{t})^{2}$.

7:
$\phi^{\prime}_{k+1}=\mathop{\arg\min}_{\phi^{\prime}}\frac{1}{|\mathcal{D}_{k}|T}\sum(V^{\psi^{i}_{k}}_{C_{i}}(s_{t})-\hat{C}^{i}_{t})^{2},\forall
i$.

8: end for

Output: Optimal policy $\pi_{\theta_{K}}$.

Algorithm 2 Exact Penalized Policy Search Algorithm

Input: current policy $\pi_{\theta_{k}}$.

1: for $n\mathrm{\ in\ }0,1,2,...N$ do

2: Compute $\mathcal{L}^{\mathrm{CLIP}}_{R}(\theta)$ in Eq. (6).

3: Compute $\mathcal{L}^{\mathrm{CLIP}}_{C_{i}}(\theta),\ \forall i=1,2...m$
in Eq. (7).

4: $\theta\leftarrow\theta-\eta\nabla\mathcal{L}^{\mathrm{P3O}}(\theta)$ in
Eq. (5).

5: $\kappa\leftarrow\min\\{\rho\kappa,\kappa_{\mathrm{max}}\\}\quad(\rho>1)$.

6: if $\mathop{\mathbb{E}}_{s\sim
d^{\pi}}\big{[}\mathrm{D}_{KL}(\pi_{\theta}||\pi_{\theta_{k}})[s]\big{]}\notin[\delta^{-}_{k},\delta^{+}_{k}]$
then

7: Break.

8: end if

9: end for

10: $\theta_{k+1}\leftarrow\theta$.

Output: next policy $\pi_{\theta_{k+1}}$.

(a) Circle (b) Gather

(c) Navigation (d) Simple Spread

Figure 1: Experimental benchmarks. (a) Circle: The agent is rewarded for
moving in a specified wide circle, but is constrained to stay within a safe
region smaller than the radius of the circle. (b) Gather: The agent is
rewarded for gathering green apples, but is constrained to avoid red bombs.
(c) Navigation: The agent is rewarded for reaching the target area(green) but
is constrained to avoid virtual hazards(light purple) and impassible
pillars(dark purple). Note that the cost for hazards and pillars are
calculated separately and hold different upper limits. (d) Simple Spread:
Agents are rewarded for reaching corresponding destinations, but are
constrained to the mutual collision. The observation of each agent is not
shared in the CMDP execution.

######  Theorem 2.

For any policy $\pi$ and the given $\pi_{k}$, define

$\delta=\mathop{\mathbb{E}}_{s\sim
d^{\pi_{k}}}\big{[}\mathrm{D}_{KL}(\pi||\pi_{k})[s]\big{]}.$

The worst-case approximate error is $\mathcal{O}(\kappa m\sqrt{\delta})$ if we
replace problem (3) with problem (4).

###### Proof.

See the supplemental material. ∎

Theorem 2 indicates the necessity of a finite penalty factor $\kappa$, or the
approximate error would not be controlled. On the other hand, we have to
restrict policy updates within the neighborhood of last $\pi_{k}$ (i.e.,
$\delta\rightarrow 0$) and improve the policy iteratively. Here, we
incorporate the trust-region constraint via clipped surrogate objective
Schulman et al. (2017) in the approximate exactly penalized problem (4) to
guarantee a proximal policy iteration. Then, the final optimization objective,
abbreviated as P3O (penalized PPO), is derived as:

$\mathcal{L}^{\mathrm{P3O}}(\theta)=\mathcal{L}^{\mathrm{CLIP}}_{R}(\theta)+\kappa\cdot\sum_{i}\max\\{0,\mathcal{L}^{\mathrm{CLIP}}_{C_{i}}(\theta)\\},$
(5)

where

$\displaystyle\mathcal{L}^{\mathrm{CLIP}}_{R}(\theta)=$
$\displaystyle\mathop{\mathbb{E}}_{\begin{subarray}{c}s\sim d^{\pi_{k}}\\\
a\sim\pi_{k}\end{subarray}}\big{[}-\min\big{\\{}r(\theta)A_{R}^{\pi_{k}}(s,a),$
(6)
$\displaystyle\mathrm{clip}(r(\theta),1-\epsilon,1+\epsilon)A_{R}^{\pi_{k}}(s,a)\big{\\}}\big{]}\
;$
$\displaystyle\mathcal{L}^{\mathrm{CLIP}}_{C_{i}}(\theta)=\mathop{\mathbb{E}}_{\begin{subarray}{c}s\sim
d^{\pi_{k}}\\\
a\sim\pi_{k}\end{subarray}}\big{[}\max\big{\\{}r(\theta)A_{C_{i}}^{\pi_{k}}(s,a),\mathrm{clip}(r(\theta),$
(7) $\displaystyle
1-\epsilon,1+\epsilon)A_{C_{i}}^{\pi_{k}}(s,a)\big{\\}}+(1-\gamma)(J_{C_{i}}(\pi_{k})-d_{i})\big{]}.$

Based on the clipped surrogate objective technique, we solve the difficult
constrained problem (2) by alternately estimating and minimizing the
unconstrained loss function (5).

The remaining problem is how to obtain the finite penalty factor $\kappa$ due
to the variety of the magnitude of $\mathcal{L}^{\mathrm{CLIP}}_{R}(\theta)$
and each $\mathcal{L}^{\mathrm{CLIP}}_{C_{i}}(\theta)$ that depends on
different tasks and up-to-date policies. The value of $\kappa$ is required to
be larger than the unknown greatest Lagrange multiplier according to Theorem
1, but Theorem 2 implies too large $\kappa$ decays the performance. Thus,
there is a trade-off among the hyper-parameter tuning. As shown in Algorithm
2, we increase $\kappa$ at every time step, and the early stopping condition
is fulfilled when the distance between solutions of two adjacent steps is
small enough or the current policy is out of the trust region. In practice, we
utilize the normalization trick that maps the advantage estimation to an
approximate standard normal distribution regardless of the tasks themselves.
We find this technique enables a fixed $\kappa$ for general good results
across different tasks. Experimental results show that both of above
algorithms work effectively and the learning processes are stable in a wide
range of $\kappa$.

Note that the first term in the P3O objective (5) is the same as standard PPO
and the rest terms are the clipped constraint objectives that prevent the new
policy from jumping out of the trust region during the penalty reduction. The
loss function in P3O is differentiable almost everywhere and can be solved
easily via the simple first-order optimizer Kingma and Ba (2014).
Conclusively, P3O inherits the benefits of PPO in CMDPs such as better
accuracy and sample efficiency than the approximating quadratic optimization
Achiam et al. (2017); Yang et al. (2020). Additionally, the P3O algorithm is
naturally scalable to multi-constraint scenarios by adding penalized terms
onto the objective (5). The pseudo-code of the P3O algorithm for solving
general multi-constraint CMDPs is shown in Algorithm 1. In the end, we extend
the P3O algorithm to the decentralized multi-agent setting in which the CMDP
is partially observable and the observation can not be shared between each
agent. Due to the space limitation, detailed algorithms are provided in the
supplementary material.

##  5 Experiments

(a) Episode Return(AntCircle) (b) Episode Cost(AntCircle) (c) Episode
Return(PointGather) (d) Episode Cost(PointGather)

Figure 2: Average episode return and cost in the single-constraint scenario.
The x-axis is the number of interactions with the emulator. The y-axis is the
average reward/cost-return. The solid line is the mean and the shaded area is
the standard deviation. Each tested algorithm runs over five different seeds.
The dashed line in the cost plot is the constraint threshold which is 50 for
Circle and 0.5 for Gather.

In this section, we empirically demonstrate the efficacy of the P3O algorithm
from the following four perspectives:

  * •

P3O outperforms the state-of-the-art algorithms, e.g. CPO Achiam et al.
(2017), PPO-Lagrangian Ray et al. (2019) and FOCOPS Zhang et al. (2020) in
safe RL benchmarks with a single constraint.

  * •

P3O is robust to more stochastic and complex environments Ray et al. (2019)
where previous methods fail to simultaneously improve the return effectively
and satisfy the constraint strictly.

  * •

P3O introduces only one additional hyper-parameter (i.e., the penalty factor
$\kappa$), which is easy to tune and insensitive to different settings and
constraint thresholds.

  * •

P3O can be extended to multi-constraint and multi-agent scenarios that are
barely tested in the previous work.

Task  |  | P3O (Ours) |   CPO Achiam et al. (2017) |   PPO-L Ray et al. (2019) |   FOCOPS Zhang et al. (2020)
---|---|---|---|---|---
AntCircle | Reward | $253.92\pm 11.67$ | $214.45\pm 26.32$ | $189.82\pm 52.12$ | $232.08\pm 19.87$
 Cost($\leq 50$) | $46.18\pm 7.49$ | $57.66\pm 9.42$ | $27.71\pm 7.33$ | $34.50\pm 11.21$
PointGather | Reward | $4.57\pm 0.54$ | $3.11\pm 0.29$ | $3.49\pm 0.33$ | $3.14\pm 0.79$
 Cost($\leq 0.5$) | $0.51\pm 0.10$ | $0.73\pm 0.17$ | $0.48\pm 0.09$ | $0.51\pm 0.14$
Table 1: Mean performance with normal 95% confidence interval on single-
constraint tasks.

(a) Episode Return (b) Episode Return

Figure 3: Performance of P3O for different $\kappa$ settings on AntCircle.

We design and conduct experiments in 2 single-constraint (Circle and Gather),
1 multi-constraint (Navigation) and 1 multi-agent (Simple Spread) safe RL
environments respectively, as illustrated in Figure 1.

To be fair in comparison, the proposed P3O algorithm and FOCOPS Zhang et al.
(2020) are implemented with same rules and tricks on the code-base of Ray et
al.Ray et al. (2019)111https://github.com/openai/safety-starter-agents for
benchmarking safe RL algorithms. Also, we take standard PPO as the reference
which ignores any constraint and serves as an upper bound baseline on the
reward performance.

More information about experiment environments and detailed parameters are
provided in the supplementary material.

#### Single-Constraint Scenario.

The numerical results of different algorithms are listed in Table 1. The
proposed P3O algorithm has +15%, +24%, +9% higher reward improvement over CPO,
PPO-Lagrangian, FOCOPS on the AntCircle task, and +34%, +23%, +31% on the
PointGather task respectively. Meanwhile, P3O converges to the upper limit of
the safety constraint more tightly which enlarges the parametric search space,
as well as satisfies the hard constraint.

As illustrated in Figure 2, P3O is the best for improving the policy while
satisfying the given constraint. Conversely, CPO has more constraint
violations and even fails to satisfy the constraint after convergence possibly
due to Taylor’s approximation. This is especially prominent in complex
environments like SafetyGym Ray et al. (2019) shown in Figure 7. The non-
negligible approximate error prevents the CPO agent from fully ensuring
constraints on virtually over these environments whereas it enjoys a
meaningless high return. As for PPO-Lagrangian, it is too conservative for the
trade-off between reward improvement and constraint satisfaction. Besides, it
fluctuates mostly on the learning curves which means it is less steady on the
learning process. FOCOPS is better-performed than the two baselines above.
However, the hyper-parameter $\lambda$ takes a great effect on the final
performance. At last, both PPO-Lagrangian and FOCOPS are more or less
sensitive to the initial value as well as the learning rate of the Lagrange
multiplier. Improper hyper-parameters would cause catastrophic performance on
reward and constraint value.

(a) Episode Return (b) Episode Return

Figure 4: Performance of P3O for different cost limit $d$ on AntCircle.

(a) Episode Return

(b) Episode Cost for hazards (c) Episode Cost for pillars

Figure 5: Average episode return(left), cost1(center, for hazards) and
cost2(right, for pillars) in the multiple-constraint scenario. The dashed line
in the cost plot is the constraint threshold which is 25 for cost1 and 20 for
cost2. Hazard/Pillar constrained means only taking cost1/cost2 into P3O loss
function whereas ignoring the other one.

#### Sensitivity Analysis.

The penalty factor $\kappa$ plays a critical role in P3O, which is supposed to
vary across different tasks depending on the specific value of $A_{R}$ and
each $A_{c_{i}}$. As shown in Algorithm 2, we can increase $\kappa$ at every
time steps. Otherwise we can map the advantage estimation to an approximate
standard normal distribution by applying advantage normalizing tricks and use
a fixed $\kappa$ for general good results. The experimental results are stable
in a wide range of $\kappa$, as illustrated in Figure 3.

We further verify that P3O works effectively for different threshold levels by
changing the cost limit $d$. Figure 4 shows P3O can effectively learn
constraint-satisfying policies for all the cases. Notably, P3O precisely
converges to the cost upper limit. By contrast, the baseline algorithms are
too conservative for policy updates and have more overshoot in the process of
cost violation reduction.

(a) Episode Return (b) Episode Return

Figure 6: Average episode return and cost in the multi-agent scenario. The
algorithm is decentralized with notation (dec).

#### Multi-Constraint Scenario.

It is convenient to extend P3O to multi-constraint scenarios by simply adding
exact penalty functions with the minor modification on the loss function.

Learning curves of average episode return and two independent costs for the
navigation task are shown in Figure 5. The unconstrained algorithm is the
original PPO. The hazard (pillar) constrained algorithm only takes the cost of
hazard (pillar) into P3O loss function whereas ignoring the other one. It can
be seen that those single-constrained algorithms maintain the specified
constraint under its upper limit but fail to control the other one. When both
constraints are incorporated into our algorithm, each one is well satisfied at
the convergence. The episode return is lower than unconstrained and single-
constrained settings, which is reasonable because the safety constraints are
more strict.

It is remarkable that at the beginning of training, the agent violates the
hazard constraint but barely hits pillars because there are more small hazards
around the starting point and the pillars are nearly unreachable by random
moving due to the initialization mechanism. However, with the increasing
velocity, the agent is less likely to satisfy the pillar constraint.
Satisfaction on the two types of constraints shows that P3O admits both
feasible and infeasible initial policies and finds a constraint-satisfying
solution in the end.

#### Multi-Agent Scenario.

We also study Multi-Agent Penalized Policy Optimization (MAP3O) in the
collaborative task and take unconstrained Multi-Agent PPO (MAPPO) Chao et al.
(2021) as the reference. To tackle the issue of partial observability,
recurrent networks are used in both algorithms.

The given task is a decentralized partially observable Markov decision process
(DEC-POMDP) in which each agent has an exclusive observation and a shared
global reward/cost. We replace the MAPPO loss function with Eq. (5) and
conduct a fully decentralized training and execution. The experimental results
show that MAP3O can improve the total reward while ensuring the mutual
collision constraint. Inspired by Chao et al.Chao et al. (2021), we enhance
MAP3O by learning a centralized critic for both global reward and cost that
takes in the concatenation of each agent’s local observation. The centralized
version of MAP3O has better reward performance and satisfies the constraint
more strictly. The learning curves of average episode return and cost are
shown in Figure 6.

(a) Episode Return (b) Episode Return

Figure 7: Average performance for P3O, CPO and PPO-Lagrangian on Safetygym
PointGoal.

##  6 Conclusion

In this paper, we propose Penalized Proximal Policy Optimization (P3O), an
effective and easy-to-implement algorithm for safe reinforcement learning. P3O
has an unconstrained optimization objective due to the exact penalty
reformulation and guarantees better performance on reward and constraint value
empirically. Meanwhile, it is naturally compatible with multi-constraint and
multi-agent scenarios. P3O adopts first-order minimization and avoids the
inversion of high-dimensional Hessian Matrix, which is especially beneficial
to large CMDPs with deep neural networks. Thus we consider the future work as
end-to-end visual tasks which are less studied in safe reinforcement learning.

## Acknowledgements

This work is supported by Science and Technology Innovation 2030 –“Brain
Science and Brain-like Research” Major Project (No. 2021ZD0201402 and No.
2021ZD0201405).

## References

  * Achiam et al. [2017] Joshua Achiam, David Held, Aviv Tamar, and Pieter Abbeel.  Constrained policy optimization.  In International Conference on Machine Learning, pages 22–31. PMLR, 2017.
  * Altman [1999] Eitan Altman.  Constrained Markov decision processes, volume 7.  CRC Press, 1999.
  * Chao et al. [2021] YU Chao, A VELU, E VINITSKY, et al.  The surprising effectiveness of ppo in cooperative, multi-agent games.  arXiv preprint arXiv:2103.01955, 2021.
  * Chow et al. [2017] Yinlam Chow, Mohammad Ghavamzadeh, Lucas Janson, and Marco Pavone.  Risk-constrained reinforcement learning with percentile risk criteria.  The Journal of Machine Learning Research, 18(1):6070–6120, 2017\.
  * Ding et al. [2020] Dongsheng Ding, Kaiqing Zhang, Tamer Basar, and Mihailo R Jovanovic.  Natural policy gradient primal-dual method for constrained markov decision processes.  In NeurIPS, 2020.
  * Ding et al. [2021] Dongsheng Ding, Xiaohan Wei, Zhuoran Yang, Zhaoran Wang, and Mihailo Jovanovic.  Provably efficient safe exploration via primal-dual policy optimization.  In International Conference on Artificial Intelligence and Statistics, pages 3304–3312. PMLR, 2021.
  * Garcıa and Fernández [2015] Javier Garcıa and Fernando Fernández.  A comprehensive survey on safe reinforcement learning.  Journal of Machine Learning Research, 16(1):1437–1480, 2015.
  * Jiang and Li [2016] Nan Jiang and Lihong Li.  Doubly robust off-policy value evaluation for reinforcement learning.  In International Conference on Machine Learning, pages 652–661. PMLR, 2016.
  * Kakade and Langford [2002] Sham Kakade and John Langford.  Approximately optimal approximate reinforcement learning.  In In Proc. 19th International Conference on Machine Learning. Citeseer, 2002.
  * Kingma and Ba [2014] Diederik P Kingma and Jimmy Ba.  Adam: A method for stochastic optimization.  arXiv preprint arXiv:1412.6980, 2014.
  * Levine et al. [2016] Sergey Levine, Chelsea Finn, Trevor Darrell, and Pieter Abbeel.  End-to-end training of deep visuomotor policies.  The Journal of Machine Learning Research, 17(1):1334–1373, 2016\.
  * Liu et al. [2020] Yongshuai Liu, Jiaxin Ding, and Xin Liu.  Ipo: Interior-point policy optimization under constraints.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 4940–4947, 2020.
  * Liu et al. [2021] Yongshuai Liu, Avishai Halev, and Xin Liu.  Policy learning with constraints in model-free reinforcement learning: A survey.  In Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, 2021.
  * Lowe et al. [2017] Ryan Lowe, Yi Wu, Aviv Tamar, Jean Harb, Pieter Abbeel, and Igor Mordatch.  Multi-agent actor-critic for mixed cooperative-competitive environments.  arXiv preprint arXiv:1706.02275, 2017.
  * Paternain et al. [2019] Santiago Paternain, Luiz FO Chamon, Miguel Calvo-Fullana, and Alejandro Ribeiro.  Constrained reinforcement learning has zero duality gap.  arXiv preprint arXiv:1910.13393, 2019.
  * Ray et al. [2019] Alex Ray, Joshua Achiam, and Dario Amodei.  Benchmarking safe exploration in deep reinforcement learning.  arXiv preprint arXiv:1910.01708, 7, 2019.
  * Schulman et al. [2015] John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz.  Trust region policy optimization.  In International conference on machine learning, pages 1889–1897. PMLR, 2015.
  * Schulman et al. [2017] John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov.  Proximal policy optimization algorithms.  arXiv preprint arXiv:1707.06347, 2017.
  * Silver et al. [2017] David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, et al.  Mastering the game of go without human knowledge.  nature, 550(7676):354–359, 2017.
  * Stooke et al. [2020] Adam Stooke, Joshua Achiam, and Pieter Abbeel.  Responsive safety in reinforcement learning by pid lagrangian methods.  In International Conference on Machine Learning, pages 9133–9143. PMLR, 2020.
  * Sutton and Barto [2018] Richard S Sutton and Andrew G Barto.  Reinforcement learning: An introduction.  MIT press, 2018.
  * Tessler et al. [2018] Chen Tessler, Daniel J Mankowitz, and Shie Mannor.  Reward constrained policy optimization.  arXiv preprint arXiv:1805.11074, 2018.
  * Vinyals et al. [2019] Oriol Vinyals, Igor Babuschkin, Wojciech M Czarnecki, Michaël Mathieu, Andrew Dudzik, Junyoung Chung, David H Choi, Richard Powell, Timo Ewalds, Petko Georgiev, et al.  Grandmaster level in starcraft ii using multi-agent reinforcement learning.  Nature, 575(7782):350–354, 2019.
  * Yang et al. [2020] Tsung-Yen Yang, Justinian Rosca, Karthik Narasimhan, and Peter J Ramadge.  Projection-based constrained policy optimization.  arXiv preprint arXiv:2010.03152, 2020.
  * Zhang et al. [2020] Yiming Zhang, Quan Vuong, and Keith W Ross.  First order constrained optimization in policy space.  arXiv preprint arXiv:2002.06506, 2020.

## Supplementary Material

To make this work self-contained and easy to read, the supplementary material
is organized as follows: In the first 3 sections, we provide the detailed
proof of proposition and theorems claimed in the main paper. In Section 4, we
propose the Multi-agent P3O algorithm in detail. In Section 5, we give the
implementation details of experiment environments, agents, and algorithms.

##  1 Proof of Proposition 1.

The following lemma adapts Performance Difference Lemma Kakade and Langford
[2002] to more general settings.

######  Lemma 1.

For any function $f:S\times A\times S\mapsto\mathbb{R}$ and any policies $\pi$
and $\pi^{\prime}$, define
$J_{f}(\pi)=\mathop{\mathbb{E}}_{\tau\sim\pi}\big{[}\Sigma^{\infty}_{t=0}\gamma^{t}f(s_{t},a_{t},s_{t+1})\big{]}$
and $d^{\pi}(s)=(1-\gamma)\sum^{\infty}_{t=0}\gamma^{t}P(s_{t}=s|\pi)$. Then
the following equation holds:

$J_{f}(\pi^{\prime})-J_{f}(\pi)=\frac{1}{1-\gamma}\mathop{\mathbb{E}}_{\begin{subarray}{c}s\sim
d^{\pi^{\prime}}\\\ a\sim\pi^{\prime}\end{subarray}}[A_{f}^{\pi}(s,a)]$

###### Proof.

First, $J_{f}(\pi^{\prime})$ can be reformulated as:

$\begin{aligned}
&J_{f}(\pi^{\prime})=\mathop{\mathbb{E}}_{\tau\sim\pi^{\prime}}\big{[}\sum^{\infty}_{t=0}\gamma^{t}f(s_{t},a_{t},s_{t+1})\big{]}\\\
&=\mathop{\mathbb{E}}_{\tau\sim\pi^{\prime}}\big{[}\sum^{\infty}_{t=0}\gamma^{t}f(s_{t},a_{t},s_{t+1})-\sum^{\infty}_{t=0}\gamma^{t}V_{f}^{\pi}(s_{t})+\sum^{\infty}_{t=0}\gamma^{t}V_{f}^{\pi}(s_{t})\big{]}\\\
&=\mathop{\mathbb{E}}_{\tau\sim\pi^{\prime}}\big{[}\sum^{\infty}_{t=0}\gamma^{t}\big{(}f(s_{t},a_{t},s_{t+1})-V_{f}^{\pi}(s_{t})\\\
&\qquad\qquad\qquad\qquad\qquad\qquad+\gamma
V_{f}^{\pi}(s_{t+1})\big{)}\big{]}+\mathop{\mathbb{E}}_{\tau\sim\pi^{\prime}}\big{[}V_{f}^{\pi}(s_{0})\big{]}\\\
&=\mathop{\mathbb{E}}_{\tau\sim\pi^{\prime}}\big{[}\sum^{\infty}_{t=0}\gamma^{t}A_{f}^{\pi}(s_{t},a_{t})\big{]}+\mathop{\mathbb{E}}_{s_{0}\sim\mu}\big{[}V_{f}^{\pi}(s_{0})\big{]}\\\
&=\mathop{\mathbb{E}}_{\tau\sim\pi^{\prime}}\big{[}\sum^{\infty}_{t=0}\gamma^{t}A_{f}^{\pi}(s_{t},a_{t})\big{]}+J_{f}(\pi)\end{aligned}$

Next, replace $\tau\sim\pi^{\prime}$ with $s\sim d^{\pi^{\prime}}$ and
$a\sim\pi^{\prime}$:

$\begin{aligned}
&\quad\mathop{\mathbb{E}}_{\tau\sim\pi^{\prime}}\big{[}\sum^{\infty}_{t=0}\gamma^{t}A_{f}^{\pi}(s_{t},a_{t})\big{]}\\\
&=\mathbb{E}\big{[}\sum^{\infty}_{t=0}\sum_{s}P(s_{t}=s)\sum_{a}\pi(a_{t}=a|s_{t}=s)\gamma^{t}A_{f}^{\pi}(s_{t},a_{t})\big{]}\\\
&=\mathbb{E}\big{[}\big{(}\sum_{s}\sum^{\infty}_{t=0}\gamma^{t}P(s_{t}=s)\big{)}\sum_{a}\pi(a_{t}=a|s_{t}=s)A_{f}^{\pi}(s_{t},a_{t})\big{]}\\\
&=\frac{1}{1-\gamma}\mathop{\mathbb{E}}_{\begin{subarray}{c}s\sim
d^{\pi^{\prime}}\\\
a\sim\pi^{\prime}\end{subarray}}\big{[}A_{f}^{\pi}(s_{t},a_{t})\big{]}\end{aligned}$

Thus, the following equation holds:

$J_{f}(\pi^{\prime})-J_{f}(\pi)=\frac{1}{1-\gamma}\mathop{\mathbb{E}}_{\begin{subarray}{c}s\sim
d^{\pi^{\prime}}\\\ a\sim\pi^{\prime}\end{subarray}}[A_{f}^{\pi}(s,a)].$

The proof of Lemma 1 is completed. ∎

For a better readability, we rewrite Proposition 1 as below.

######  Proposition.

The new policy $\pi_{k+1}$ obtained from the current policy $\pi_{k}$ via the
following problem:

$\displaystyle\pi_{k+1}=\mathop{\arg\max}_{\pi}\mathop{\mathbb{E}}_{\begin{subarray}{c}s\sim
d^{\pi}\\\ a\sim\pi\end{subarray}}[A^{\pi_{k}}_{R}(s,a)]$ (8)
$\displaystyle\mathrm{s.t.}\quad
J_{C_{i}}(\pi_{k})+\frac{1}{1-\gamma}\mathop{\mathbb{E}}_{\begin{subarray}{c}s\sim
d^{\pi}\\\ a\sim\pi\end{subarray}}\big{[}A_{C_{i}}^{\pi_{k}}(s,a)\big{]}\leq
d_{i},\ \forall i.$

yields a monotonic return improvement and hard constraint satisfaction.

###### Proof of Proposition 1.

The goal is to obtain new policy $\pi_{k+1}$ which is the solution of the
following problem:

$\displaystyle\pi_{k+1}=\mathop{\arg\max}_{\pi}J_{R}(\pi)$ (9)
$\displaystyle\mathrm{s.t.}\quad J_{C_{i}}(\pi)\leq d_{i},\ \forall i.$

Replace $f$ with reward function $R$ and each cost function $C_{i}$
respectively in Lemma 1, we have:

$J_{R}(\pi)-J_{R}(\pi_{k})=\frac{1}{1-\gamma}\mathop{\mathbb{E}}_{\begin{subarray}{c}s\sim
d^{\pi}\\\ a\sim\pi\end{subarray}}[A_{R}^{\pi_{k}}(s,a)]$ (10)
$J_{C_{i}}(\pi)-J_{C_{i}}(\pi_{k})=\frac{1}{1-\gamma}\mathop{\mathbb{E}}_{\begin{subarray}{c}s\sim
d^{\pi^{\prime}}\\\
a\sim\pi^{\prime}\end{subarray}}[A_{C_{i}}^{\pi_{k}}(s,a)],\ \forall i$ (11)

Thus, the above problem (8) can be reformulated as:

$\displaystyle\pi_{k+1}=\mathop{\arg\max}_{\pi}\big{(}J_{R}(\pi_{k})+\frac{1}{1-\gamma}\mathop{\mathbb{E}}_{\begin{subarray}{c}s\sim
d^{\pi}\\\ a\sim\pi\end{subarray}}[A^{\pi_{k}}_{R}(s,a)]\big{)}$ (12)
$\displaystyle\mathrm{s.t.}\quad
J_{C_{i}}(\pi_{k})+\frac{1}{1-\gamma}\mathop{\mathbb{E}}_{\begin{subarray}{c}s\sim
d^{\pi}\\\ a\sim\pi\end{subarray}}\big{[}A_{C_{i}}^{\pi_{k}}(s,a)\big{]}\leq
d_{i},\ \forall i.$

The proof is completed by omitting the constant term in the optimization
objective. ∎

##  2 Proof of Theorem 2.

We rewrite problem (2) as:

$\begin{aligned}
&\theta_{k+1}=\mathop{\arg\min}_{\theta}\mathcal{L}_{R}(\theta)\\\
&\mathrm{s.t.}\quad\mathcal{L}_{C_{i}}(\theta)\leq 0,\ \forall i\\\
\end{aligned}$

(P)

and rewrite problem (3) as:

$\theta_{k+1}=\mathop{\arg\min}_{\theta}\mathcal{L}_{R}(\theta)+\kappa\sum_{i}\max\\{0,\mathcal{L}_{C_{i}}(\theta)\\}$
(Q)

Here we shorthand
$\mathcal{L}_{R}(\theta)=\mathop{\mathbb{E}}_{\begin{subarray}{c}s\sim
d^{\pi}\\\ a\sim\pi_{k}\end{subarray}}[-r(\theta)A^{\pi_{k}}_{R}(s,a)]$ and
$\mathcal{L}_{C_{i}}=\mathop{\mathbb{E}}_{\begin{subarray}{c}s\sim d^{\pi}\\\
a\sim\pi_{k}\end{subarray}}\big{[}r(\theta)A_{C_{i}}^{\pi_{k}}(s,a)\big{]}+(1-\gamma)(J_{C_{i}}(\pi_{k})-d_{i}),\
\forall i$.

######  Lemma 2.

Suppose $\bar{\theta}$ is the optimum of the constrained problem (P). Let
$\bar{\lambda}$ be the corresponding Lagrange multiplier vector for its dual
problem. Then for $\kappa\geq||\bar{\lambda}||_{\infty}$, $\bar{\theta}$ is
also a minimizer of its penalized optimization problem (Q).

###### Proof.

Since $\kappa\geq||\bar{\lambda}||_{\infty}$, by taking $[\cdot]^{+}$ as
shorthand for $\max\\{0,\cdot\\},$it follows that:

$\displaystyle\mathcal{L}_{R}(\theta)+\kappa\sum_{i}\mathcal{L}^{+}_{C_{i}}(\theta)$
$\displaystyle\geq\mathcal{L}_{R}(\theta)+\sum_{i}\bar{\lambda_{i}}\mathcal{L}^{+}_{C_{i}}(\theta)$
(13)
$\displaystyle\geq\mathcal{L}_{R}(\theta)+\sum_{i}\bar{\lambda_{i}}\mathcal{L}_{C_{i}}(\theta)$
(14)

By assumption, $\bar{\theta}$ is a Karush-Kuhn-Tucker point in the constrained
problem (P), at which KKT conditions are satisfied with the Lagrange
multiplier vector $\bar{\lambda}$. It gives:

$\displaystyle\mathcal{L}_{R}(\theta)+\sum_{i}\bar{\lambda_{i}}\mathcal{L}_{C_{i}}(\theta)$
$\displaystyle\geq\mathcal{L}_{R}(\bar{\theta})+\sum_{i}\bar{\lambda_{i}}\mathcal{L}_{C_{i}}(\bar{\theta})$
(15)
$\displaystyle=\mathcal{L}_{R}(\bar{\theta})+\sum_{i}\bar{\lambda_{i}}\mathcal{L}^{+}_{C_{i}}(\bar{\theta})$
(16)
$\displaystyle=\mathcal{L}_{R}(\bar{\theta})+\kappa\sum_{i}\mathcal{L}^{+}_{C_{i}}(\bar{\theta})$
(17)

(15) holds because $\bar{\theta}$ minimizes the Lagrange function. (16) is
derived from the complementary slackness.

Then, by (13)-(17), we conclude that
$\mathcal{L}(\theta)\geq\mathcal{L}(\bar{\theta})$ holds for all
$\theta\in\Theta$, which means $\bar{\theta}$ is a minimizer of the penalized
optimization problem (Q).

The proof of Lemma 2 is completed. ∎

######  Lemma 3.

Let $\widetilde{\theta}$ be a minimizer of the penalized optimization problem
(Q). $\bar{\theta}$ and $\bar{\lambda}$ are the same as they are defined in
Theorem 2. Then for $\kappa\geq||\bar{\lambda}||_{\infty}$,
$\widetilde{\theta}$ is also optimal in the constrained problem (P).

###### Proof.

If $\widetilde{\theta}$ is in the set of feasible solutions
$D=\\{\theta|\mathcal{L}_{C_{i}}(\theta)\leq 0,\ \forall i\\}$, it gives:

$\displaystyle\mathcal{L}_{R}(\widetilde{\theta})$
$\displaystyle=\mathcal{L}_{R}(\widetilde{\theta})+\kappa\sum_{i}\mathcal{L}^{+}_{C_{i}}(\widetilde{\theta})$
(18)
$\displaystyle\leq\mathcal{L}_{R}(\theta)+\kappa\sum_{i}\mathcal{L}^{+}_{C_{i}}(\theta)=\mathcal{L}_{R}(\theta)$
(19)

The inequality above indicates $\widetilde{\theta}$ is also optimal in the
constrained problem (P).

If $\widetilde{\theta}$ is not feasible, we have:

$\displaystyle\mathcal{L}_{R}(\bar{\theta})+\kappa\sum_{i}\mathcal{L}^{+}_{C_{i}}(\bar{\theta})=\mathcal{L}_{R}(\bar{\theta})+\sum_{i}\bar{\lambda_{i}}\mathcal{L}^{+}_{C_{i}}(\bar{\theta})$
(20)
$\displaystyle=\mathcal{L}_{R}(\bar{\theta})+\sum_{i}\bar{\lambda_{i}}\mathcal{L}_{C_{i}}(\bar{\theta})\leq\mathcal{L}_{R}(\widetilde{\theta})+\sum_{i}\bar{\lambda_{i}}\mathcal{L}_{C_{i}}(\widetilde{\theta})$
(21)
$\displaystyle\leq\mathcal{L}_{R}(\widetilde{\theta})+\sum_{i}\bar{\lambda_{i}}\mathcal{L}^{+}_{C_{i}}(\widetilde{\theta})\leq\mathcal{L}_{R}(\widetilde{\theta})+\kappa\sum_{i}\mathcal{L}^{+}_{C_{i}}(\widetilde{\theta})$
(22)

which is a contradiction to the assumption that $\widetilde{\theta}$ is a
minimizer of the penalized optimization problem (Q).Thus, $\widetilde{\theta}$
can only be the feasible optimal solution for problem (P).

The proof of Lemma 3 is completed. ∎

For a better readability, we rewrite Theorem 2 as below.

######  Theorem.

Suppose $\bar{\lambda}$ is the corresponding Lagrange multiplier vector for
the optimum of problem (P). Let the penalty factor $\kappa$ be a sufficiently
large constant ($\kappa\geq||\bar{\lambda}||_{\infty}$), the two problems (P)
and (Q) share the same optimal solution set.

###### Proof of Theorem 2.

The proof is completed with Lemma 2 and Lemma 3. ∎

##  3 Proof of Theorem 3.

We rewrite problem (3) as:

$\mathcal{L}^{\pi}(\theta)=\mathcal{L}^{\pi}_{R}(\theta)+\kappa\sum_{i}\max\\{0,\mathcal{L}^{\pi}_{C_{i}}(\theta)\\}$
(M)

Here we shorthand
$\mathcal{L}^{\pi}_{R}(\theta)=\mathop{\mathbb{E}}_{\begin{subarray}{c}s\sim
d^{\pi}\\\ a\sim\pi_{k}\end{subarray}}[-r(\theta)A^{\pi_{k}}_{R}(s,a)]$ and
$\mathcal{L}^{\pi}_{C_{i}}(\theta)=\mathop{\mathbb{E}}_{\begin{subarray}{c}s\sim
d^{\pi}\\\
a\sim\pi_{k}\end{subarray}}\big{[}r(\theta)A_{C_{i}}^{\pi_{k}}(s,a)\big{]}+(1-\gamma)(J_{C_{i}}(\pi_{k})-d_{i}),\
\forall i$.

We rewrite problem (4) as:

$\mathcal{L}^{\pi}_{k}(\theta)=\mathcal{L}^{\pi_{k}}_{R}(\theta)+\kappa\sum_{i}\max\\{0,\mathcal{L}^{\pi-K}_{C_{i}}(\theta)\\}$
(N)

Here we shorthand
$\mathcal{L}^{\pi_{k}}_{R}(\theta)=\mathop{\mathbb{E}}_{\begin{subarray}{c}s\sim
d^{\pi_{k}}\\\ a\sim\pi_{k}\end{subarray}}[-r(\theta)A^{\pi_{k}}_{R}(s,a)]$
and
$\mathcal{L}^{\pi_{k}}_{C_{i}}(\theta)=\mathop{\mathbb{E}}_{\begin{subarray}{c}s\sim
d^{\pi_{k}}\\\
a\sim\pi_{k}\end{subarray}}\big{[}r(\theta)A_{C_{i}}^{\pi_{k}}(s,a)\big{]}+(1-\gamma)(J_{C_{i}}(\pi_{k})-d_{i}),\
\forall i$.

######  Lemma 4.

For any function $f:S\times A\times S\mapsto\mathbb{R}$ and any policies $\pi$
and $\pi^{\prime}$, define

$\displaystyle\delta$ $\displaystyle=\mathop{\mathbb{E}}_{s\sim
d^{\pi}}\big{[}\mathrm{D}_{KL}(\pi^{\prime}||\pi)[s]\big{]}$
$\displaystyle\varepsilon^{\pi^{\prime}}_{f}$
$\displaystyle=\mathop{\max}_{s}|\mathop{\mathbb{E}}_{a\sim\pi^{\prime}}A_{f}^{\pi}(s,a)|$
$\displaystyle D^{\pm}_{\pi,f}(\pi^{\prime})$
$\displaystyle=\frac{1}{1-\gamma}\mathop{\mathbb{E}}_{\begin{subarray}{c}s\sim
d^{\pi}\\\
a\sim\pi\end{subarray}}\bigg{[}\frac{\pi^{\prime}(s,a)}{\pi(s,a)}A^{\pi}_{f}(s,a)\pm\frac{\gamma\varepsilon^{\pi^{\prime}}_{f}\sqrt{2\delta}}{1-\gamma}\bigg{]}$

The following bounds hold:

$D^{+}_{\pi,f}(\pi^{\prime})\geq J_{f}(\pi^{\prime})-J_{f}(\pi)\geq
D^{-}_{\pi,f}(\pi^{\prime})$

###### Proof.

See Achiam et al. [2017] for details. ∎

For a better readability, we rewrite Theorem 3 as below.

######  Theorem.

For any policies $\pi$, define

$\delta=\mathop{\mathbb{E}}_{s\sim
d^{\pi_{k}}}\big{[}\mathrm{D}_{KL}(\pi||\pi_{k})[s]\big{]}.$

The worst-case approximate error is $\mathcal{O}(\kappa m\sqrt{\delta})$ if we
replace problem (M) with problem (N).

###### Proof of Theorem 3.

According to Lemma 1 and Lemma 4, we have:

$\displaystyle\quad\ \
|\mathcal{L}^{\pi}(\theta)-\mathcal{L}^{\pi}_{k}(\theta)|$ (23)
$\displaystyle\leq|\mathcal{L}^{\pi}_{R}(\theta)-\mathcal{L}^{\pi_{k}}_{R}(\theta)|+\kappa\sum_{i}|[\mathcal{L}^{\pi}_{C_{i}}(\theta)]^{+}-[\mathcal{L}^{\pi_{k}}_{C_{i}}(\theta)]^{+}|$
(24)
$\displaystyle\leq|\mathcal{L}^{\pi}_{R}(\theta)-\mathcal{L}^{\pi_{k}}_{R}(\theta)|+\kappa\sum_{i}|\mathcal{L}^{\pi}_{C_{i}}(\theta)-\mathcal{L}^{\pi_{k}}_{C_{i}}(\theta)|$
(25)
$\displaystyle\leq\frac{\gamma\varepsilon^{\pi^{\prime}}_{R}\sqrt{2\delta}}{1-\gamma}+\kappa\sum_{i}\frac{\gamma\varepsilon^{\pi^{\prime}}_{C_{i}}\sqrt{2\delta}}{1-\gamma}$
(26) $\displaystyle\leq(1+\kappa
m)\frac{\gamma||\varepsilon^{\pi^{\prime}}||_{\infty}\sqrt{2\delta}}{1-\gamma}.$
(27)

Then, the proof is completed. ∎

##  4 Multi-Agent P3O

In this section, we extend P3O to the decentralized multi-agent refinement
learning (MARL) scenarios and denote it as MAP3O, inspired by MAPPO Chao et
al. [2021].

A decentralized partially observed constrained Markov decision process (DEC-
POCMDP) is defined by a 7-tuple $(S,\\{A_{i}\\},T,\\{\Omega_{i}\\},O,R,C)$,
where $S$ is the state space, $A_{i}$ is the action space for agent i,
$A=\times_{i}A_{i}$ is the joint action space, $\Omega_{i}$ is the observation
space for agent i, $\Omega=\times_{i}\Omega_{i}$ is the joint observation
space, $T(s,a,s^{\prime})=P(s^{\prime}|s,a)$ and $O(s,a,o)=P(o|s^{\prime},a)$
are transition probabilities, $R$ is the global reward function and $C$ is a
set of global constraint functions.
$J_{R}(\pi)=\mathop{\mathbb{E}}_{\tau\sim\pi}\big{[}\sum^{\infty}_{t=0}\gamma^{t}R(s_{t},\boldsymbol{a_{t}},s_{t+1})\big{]}$
and
$J_{C}(\pi)=\mathop{\mathbb{E}}_{\tau\sim\pi}\big{[}\Sigma^{\infty}_{t=0}\gamma^{t}C(s_{t},\boldsymbol{a_{t}},s_{t+1})\big{]}$.
The goal of Multi-agent safe RL is to optimize the joint policy, i.e.,
$\pi^{*}=\mathop{\arg\max}_{\pi\in\Pi_{C}}J_{R}(\pi)$ where
$\Pi_{C}=\\{\pi\in\Pi\ |J_{C}(\pi)\leq d\\}$.

The detailed iterates scheme of fully decentralized MAP3O for agent $i$ is
summarized in Algorithm 3.

Algorithm 3 MAP3O (dec): Decentralized Multi-Agent Penalized Proximal Policy
Optimization

Input: initial policy $\pi(\theta^{i}_{0})$, value function
$V_{R}(\phi^{i}_{0})$ and cost-value function $V_{C}(\psi^{i}_{0})$.

1: for $k\mathrm{\ in\ }0,1,2,...K$ do

2: Empty data buffer $\mathcal{D}_{k}$.

3: while $\mathcal{D}_{k}$ is not full do

4: Reset a new trajectory $\tau$.

5: Initialize actor RNN state $h^{i}_{0,\pi}$.

6: Initialize critic RNN states $h^{i}_{0,V_{R}}$ and $h^{i}_{0,V_{C}}$.

7: for $t\mathrm{\ in\ }1,2,...T$ do

8: $p^{i}_{t},h^{i}_{t,\pi}=\pi(o^{i}_{t},h^{i}_{t-1,\pi};\theta^{i}_{t-1})$.

9: Sample $a^{i}_{t}$ over $p^{i}_{t}$.

10:
$v^{i}_{t,R},h^{i}_{t,V_{R}}=V_{R}(o^{i}_{t},h^{i}_{t-1,V_{R}};\phi^{i}_{t-1})$.

11:
$v^{i}_{t,C},h^{i}_{t,V_{C}}=V_{C}(o^{i}_{t},h^{i}_{t-1,V_{C}};\psi^{i}_{t-1})$.

12: Execute $a^{i}_{t}$ and record $r_{t},c_{t},o^{i}_{t+1}$.

13:
$\tau+=[o^{i}_{t},a^{i}_{t},h^{i}_{t,\pi},v^{i}_{t,R},h^{i}_{t,V_{R}},v^{i}_{t,C},h^{i}_{t,V_{C}},r_{t},c_{t},o^{i}_{t+1}]$.

14: end for

15: Compute every $\hat{R}_{t}=\sum^{T-t}_{k=0}\gamma^{k}r_{t+k}$ and
$\hat{A}^{i}_{R}(o^{i}_{t},a^{i}_{t})$.

16: Compute every $\hat{C}_{t}=\sum^{T-t}_{k=0}\gamma^{k}c_{t+k}$ and
$\hat{A}^{i}_{C}(o^{i}_{t},a^{i}_{t})$.

17: Add data into $\mathcal{D}_{k}$.

18: end while

19: for $n\mathrm{\ in\ }0,1,2,...N$ do

20: Update the RNN hidden states in data buffer $\mathcal{D}_{k}$.

21: Compute $\mathcal{L}^{\mathrm{CLIP}}_{R}(\theta^{i}_{k})$ in Eq. (6).

22: Compute $\mathcal{L}^{\mathrm{CLIP}}_{C}(\theta^{i}_{k})$ in Eq. (7).

23:
$\theta^{i}_{k}\leftarrow\theta^{i}_{k}-\eta\nabla\mathcal{L}^{\mathrm{P3O}}(\theta^{i}_{k})$
in Eq. (5).

24: end for

25: $\theta^{i}_{k+1}\leftarrow\theta^{i}_{k}$.

26: Update $\phi^{i}_{k+1}$ and $\psi^{i}_{k+1}$ with value regression
objective.

27: end for

Output: Optimal policy $\pi(\theta^{i}_{K})$.

Centralized training and decentralized execution (CTDE) is a popular framework
to learn a single policy and avoid the joint action as inputs at the same
time. The key technique is to learn a centralized critic that takes in the
concatenation of each agent’s local observation, as shown in Algorithm 4.

Algorithm 4 MAP3O: Multi-Agent Penalized Proximal Policy Optimization

Input: initial policy $\pi(\theta_{0})$, value function $V_{R}(\phi_{0})$ and
cost-value function $V_{C}(\psi_{0})$.

1: for $k\mathrm{\ in\ }0,1,2,...K$ do

2: Empty data buffer $\mathcal{D}_{k}$.

3: while $\mathcal{D}_{k}$ is not full do

4: Reset a new trajectory $\tau$.

5: Initialize each actor RNN state $h^{i}_{0,\pi}$.

6: Initialize each critic RNN states $h^{i}_{0,V_{R}}$ and $h^{i}_{0,V_{C}}$.

7: for $t\mathrm{\ in\ }1,2,...T$ do

8: for each agent $i$ do

9: $p^{i}_{t},h^{i}_{t,\pi}=\pi(o^{i}_{t},h^{i}_{t-1,\pi};\theta_{t-1})$.

10: Sample $a^{i}_{t}$ over $p^{i}_{t}$.

11:
$v^{i}_{t,R},h^{i}_{t,V_{R}}=V_{R}(\boldsymbol{o}_{t},h^{i}_{t-1,V_{R}};\phi_{t-1})$.

12:
$v^{i}_{t,C},h^{i}_{t,V_{C}}=V_{C}(\boldsymbol{o}_{t},h^{i}_{t-1,V_{C}};\psi_{t-1})$.

13: end for

14: Execute $\boldsymbol{a}_{t}$ and record
$r_{t},c_{t},\boldsymbol{o}_{t+1}$.

15:
$\tau+=[\boldsymbol{o}_{t},\boldsymbol{a}_{t},\boldsymbol{h}_{t,\pi},\boldsymbol{v}_{t,R},\boldsymbol{h}_{t,V_{R}},\boldsymbol{v}_{t,C},\boldsymbol{h}_{t,V_{C}},r_{t},c_{t},\boldsymbol{o}_{t+1}]$.

16: end for

17: Compute every $\hat{R}_{t}=\sum^{T-t}_{k=0}\gamma^{k}r_{t+k}$ and
$\hat{A}_{R}(\boldsymbol{o}_{t},\boldsymbol{a}_{t})$.

18: Compute every $\hat{C}_{t}=\sum^{T-t}_{k=0}\gamma^{k}c_{t+k}$ and
$\hat{A}_{C}(\boldsymbol{o}_{t},\boldsymbol{a}_{t})$.

19: Add data into $\mathcal{D}_{k}$.

20: end while

21: for $n\mathrm{\ in\ }0,1,2,...N$ do

22: Update the RNN hidden states in data buffer $\mathcal{D}_{k}$.

23: Compute $\mathcal{L}^{\mathrm{CLIP}}_{R}(\theta_{k})$ in Eq. (6).

24: Compute $\mathcal{L}^{\mathrm{CLIP}}_{C}(\theta_{k})$ in Eq. (7).

25:
$\theta_{k}\leftarrow\theta_{k}-\eta\nabla\mathcal{L}^{\mathrm{P3O}}(\theta_{k})$
in Eq. (5).

26: end for

27: $\theta_{k+1}\leftarrow\theta_{k}$.

28: Update $\phi_{k+1}$ and $\psi_{k+1}$ with value regression objective.

29: end for

Output: Optimal policy $\pi(\theta_{K})$.

##  5 Implementation Details.

Table 2: Algorithm-specific parameters. Parameter |  P3O |  CPO |  PPO-L |  FOCOPS |  PPO
---|---|---|---|---|---
Number of Hidden layers |  2 |  2 |  2 |  2 |  2
Number of Hidden nodes |  255 |  255 |  255 |  255 |  255
Activation Function |  $\tanh$ |  $\tanh$ |  $\tanh$ |  $\tanh$ |  $\tanh$
Discount Factor $\gamma$ |  0.99 |  0.99 |  0.99 |  0.99 |  0.99
GAE parameter $\lambda^{\mathrm{GAE}}$ |  0.97 |  0.97 |  0.97 |  0.97 |  0.97
Actor Learning Rate $\eta_{\pi}$ |  3e-4 |  N/A |  3e-4 |  3e-4 |  3e-4
Critic Learning Rate $\eta_{V_{R}}$ |  1e-3 |  1e-3 |  1e-3 |  1e-3 |  1e-3
Critic Learning Rate $\eta_{V_{C}}$ |  1e-3 |  1e-3 |  1e-3 |  1e-3 |  N/A
Penalty Factor $\kappa$ |  20 |  N/A |  N/A |  N/A |  N/A
Clip Ratio $\epsilon$ |  0.2 |  N/A |  0.2 |  N/A |  0.2
Trust Region $[\delta^{-},\delta^{+}]$ |  [0,1e-2] |  [0,1e-2] |  [0,1e-2] |  [0,1e-2] |  [0,1e-2]
Damping Coefficient |  N/A |  0.1 |  N/A |  N/A |  N/A
Backtrack Learning Rate |  N/A |  0.8 |  N/A |  N/A |  N/A
Backtrack Iterations |  N/A |  10 |  N/A |  N/A |  N/A
Penalty Initial Value $\nu_{0}$ |  N/A |  N/A |  1 |  1 |  N/A
Penalty Learning Rate $\eta_{\nu}$ |  N/A |  N/A |  0.05 |  0.01 |  N/A
Temperature Factor $\lambda$ |  N/A |  N/A |  N/A |  1.5 |  N/A
Table 3: Experiment-specific parameters. Parameter |  Circle |  Gather |  Navigation |  Simple Spread |  PointGoal
---|---|---|---|---|---
State Space $|S|$ |  $\mathbb{R}^{113}$ |  $\mathbb{R}^{86}$ |  $\mathbb{R}^{60}$ |  $\mathbb{R}^{54}$ |  $\mathbb{R}^{60}$
Action Space $|A|$ |  $\mathbb{R}^{8}$ |  $\mathbb{R}^{2}$ |  $\mathbb{R}^{2}$ |  5 |  $\mathbb{R}^{2}$
Cost Limit $d$ |  50 |  0.5 |  25,20 |  0.5 |  25
Rollout Length $T$ |  1e3 |  1e2 |  1e3 |  25 |  1e3
Buffer Size $|\mathcal{D}|$ |  3e4 |  3e3 |  3e4 |  1e3 |  3e4
Total Interactions |  1e7 |  1e7 |  1e7 |  5e6 |  1e7

###  5.1 Environments

#### Circle

This environment is inspired by Achiam et al. Achiam et al. [2017]. Reward is
maximized by moving along a circle of radius $d$:

$R=\frac{v^{\mathrm{T}}[-y,x]}{1+\big{|}\sqrt{x^{2}+y^{2}}-d\big{|}},$

but the safety region $x_{\mathrm{lim}}$ is smaller than the radius $d$:

$C=\mathbf{1}[x>x_{\mathrm{lim}}].$

In our setting, $d=10,x_{\mathrm{lim}}=3$ and the constraint threshold is 50
by default, which indicates the agent is only allowed to move in a narrow
space for safety requirements.

#### Gather

This environment is inspired by Achiam et al. Achiam et al. [2017]. The agent
receives a reward of +1 for collecting an apple (green ball) and a reward of
-1 for collecting a bomb (red ball). It also receives a cost of +1 when
encountering the bomb. 8 apples and bombs spawn respectively on the map at the
start of each episode.

In our settings, we set the constraint threshold to be 0.5. Notably, the
punishment in reward function, to some extent, keeps the agent from collecting
bombs even trained by the unconstrained PPO. But it still has many safety
violations and fails to satisfy the constraint threshold.

#### Navigation

This environment is inspired by Ray et al. Ray et al. [2019]. Reward is
maximized by getting close to the destination:

$R=\mathrm{Dist}(target,s_{t-1})-\mathrm{Dist}(target,s_{t}),$

but it yields a cost of +1 when the agent hits the hazard or the pillar. The
two different types of cost functions are returned separately and have
different thresholds. In out setting, $d_{1}=25$ for the hazard constraint and
$d_{2}=20$ for the pillar constraint.

#### Simple Spread

This environment is inspired by Lowe et al. Lowe et al. [2017]. In our
experiment, 3 agents and 3 endpoints spawn respectively on the 2D arena at the
start of each episode. The agents are collaborative and rewarded for moving
towards corresponding endpoints:

$R=-\sum_{i=1}^{3}\mathrm{Dist}(endpoint_{i},s_{it}),$

but it yields a cost of +1 if any pair of agents collide. We set $d=0.5$.

###  5.2 Agents

For single-constraint scenarios, Point agent is a 2D mass
point($A\subseteq\mathbb{R}^{2}$) and Ant agent is an quadruped
robot($A\subseteq\mathbb{R}^{8}$). For the multi-constraint scenario which is
modified from OpenAI SafetyGym Ray et al. [2019],
$S\subseteq\mathbb{R}^{28+16\cdot m}$ where $m$ is the number of pseudo-
radars(one for each type of obstacles and we set two different types of
obstacles in the Navigation task) and $A\subseteq\mathbb{R}^{2}$ for a mass
point or a wheeled car. For the multi-agent scenario which is inspired by
OpenAI Multi-Agent Particle Environment Lowe et al. [2017],
$O\subseteq\mathbb{R}^{18}$ each (the state is partially observable) and $|A|$
is 5 for any particle moving up/down/left/right and remaining still.

###  5.3 Parameters

We summarize the algorithm-specific parameters and experiment-specific
parameters in Table 2 and Table 3 , respectively.