# Constrained Update Projection Approach to Safe Policy Optimization

Long Yang1,2,∗ Jiaming Ji1, L.Yang and J.Ji share equal contributions.
${\dagger}$ G.Pan is the corresponding author.  Juntao Dai1 Linrui Zhang3
Binbin Zhou  4 Pengfei Li  1 Yaodong Yang2,5 Gang Pan1,†
1College of Computer Science and Technology  Zhejiang University  China
2 School of Artificial Intelligence  Peking University  China
3 Tsinghua Shenzhen International Graduate School  Tsinghua University  China
4 Department of Computer Science and Computing  Zhejiang University City
College  China
5 Institute for Artificial Intelligence  Peking University & BIGAI  China
<EMAIL_ADDRESS><EMAIL_ADDRESS>

###### Abstract

Safe reinforcement learning (RL) studies problems where an intelligent agent
has to not only maximize reward but also avoid exploring unsafe areas. In this
study, we propose CUP, a novel policy optimization method based on Constrained
Update Projection framework that enjoys rigorous safety guarantee. Central to
our CUP development is the newly proposed surrogate functions along with the
performance bound. Compared to previous safe RL methods, CUP enjoys the
benefits of 1) CUP generalizes the surrogate functions to generalized
advantage estimator (GAE), leading to strong empirical performance. 2) CUP
unifies performance bounds, providing a better understanding and
interpretability for some existing algorithms; 3) CUP provides a non-convex
implementation via only first-order optimizers, which does not require any
strong approximation on the convexity of the objectives. To validate our CUP
method, we compared CUP against a comprehensive list of safe RL baselines on a
wide range of tasks. Experiments show the effectiveness of CUP both in terms
of reward and safety constraint satisfaction. We have opened the source code
of CUP at this link https://github.com/zmsn-2077/CUP-safe-rl.

##  1 Introduction

Reinforcement learning (RL) (Sutton and Barto, 1998) has achieved significant
successes in many fields (e.g., (Mnih et al., 2015; Silver et al., 2017;
OpenAI, 2019; Afsar et al., 2021; Yang et al., 2022)). However, most RL
algorithms improve the performance under the assumption that an agent is free
to explore any behaviors. In real-world applications, only considering return
maximization is not enough, and we also need to consider safe behaviors. For
example, a robot agent should avoid playing actions that irrevocably harm its
hardware, and a recommender system should avoid presenting offending items to
users. Thus, it is crucial to consider _safe exploration_ for RL, which is
usually formulated as constrained Markov decision processes (CMDP) (Altman,
1999).

It is challenging to solve CMDP since traditional approaches (e.g., Q-learning
(Watkins, 1989) & policy gradient (Williams, 1992)) usually violate the safe
exploration constraints, which is undesirable for safe RL. Recently, Achiam et
al. (2017); Yang et al. (2020); Bharadhwaj et al. (2021) suggest to use some
surrogate functions to replace the objective and constraints. However, their
implementations involve some convex approximations to the non-convex objective
and safe constraints, which leads to many error sources and troubles.
Concretely, Achiam et al. (2017); Yang et al. (2020); Bharadhwaj et al. (2021)
approximate the non-convex objective (or constraints) with first-order or
second Taylor expansion, but their implementations still lack a theory to show
the error difference between the original objective (or constraints) and its
convex approximations. Besides, their approaches involve the inverse of a
high-dimension inverse Fisher information matrix, which causes their
algorithms require a costly computation for each update when solving high-
dimensional RL problems.

To address the above problems, we propose the _constrained update projection_
(CUP) algorithm with a theoretical safety guarantee. We derive the CUP bases
on the newly proposed surrogate functions with respect to objectives and
safety constraints, and provide a practical implementation of CUP that does
not depend on any convex approximation to adapt high-dimensional safe RL.

Concretely, in Section 3, Theorem 1 shows generalized difference bounds
between two arbitrary policies for the objective and constraints. Those bounds
provide principled approximations to the objective and constraints, which are
theoretical foundations for us to use those bounds as surrogate functions to
replace objective and constraints to design algorithms. Although using
difference bounds as surrogate functions to replace the objective has appeared
in previous works (e.g., (Schulman et al., 2015; Achiam et al., 2017)),
Theorem 1 refines those bounds (or surrogate functions) at least two aspects:
(i) Firstly, our rigorous theoretical analysis shows a bound with respect to
generalized advantage estimator (GAE) (Schulman et al., 2016). GAE
significantly reduces variance empirically while maintaining a tolerable level
of bias, the proposed bound involves GAE is one of the critical steps for us
to design efficient algorithms. (ii) Our new bounds unify the classic result
of CPO Achiam et al. (2017), i.e., the classic performance bound of CPO is a
special case of our bounds. Although existing work (e.g., Zhang et al. (2020);
Kang et al. (2021)) has applied the key idea of CPO with GAE to solve safe RL
problems, their approaches are all empirical and lack a theoretical analysis.
Thus, the proposed newly bound partially explains the effectiveness of the
above safe RL algorithms. Finally, we should emphasize that although GAE has
been empirically applied to extensive reinforcement learning tasks, this work
is the first to show a rigorous theoretical analysis to extend the surrogate
functions with respect to GAE.

In Section 4, we provide the necessary details of the proposed CUP. The CUP
contains two steps: it first performs a policy improvement, which may produce
a temporary policy violates the constraint. Then in the second step, CUP
projects the policy back onto the safe region to reconcile the constraint
violation. Theorem 2 shows the worst-case performance degradation guarantee
and approximate satisfaction of safety constraints of CUP, result shows that
with a relatively small parameter that controls the penalty of the distance
between the old policy and current policy, CUP shares a desirable toleration
for both policy improvements and safety constraints. Furthermore, we provide a
practical implementation of sample-based CUP. This implementation allows us to
use deep neural networks to train a model, which is an efficient iteration
without strongly convex approximation of the objective or constraints (e.g.,
(Achiam et al., 2017; Yang et al., 2020)), and it optimizes the policy
according to the first-order optimizer. Finally, extensive high-dimensional
experiments on continuous control tasks show the effectiveness of CUP where
the agent satisfies safe constraints.

##  2 Preliminaries

Reinforcement learning (RL) (Sutton and Barto, 1998) is often formulated as a
_Markov decision process_ (MDP) (Puterman, 2014) that is a tuple
$\mathcal{M}=(\mathcal{S},\mathcal{A},\mathbb{P},{r},\rho_{0},\gamma)$. Here
$\mathcal{S}$ is state space, $\mathcal{A}$ is action space.
$\mathbb{P}(s^{{}^{\prime}}|s,a)$ is probability of state transition from $s$
to $s^{{}^{\prime}}$ after playing $a$.
$r(\cdot):\mathcal{S}\times\mathcal{S}\times\mathcal{A}\rightarrow\mathbb{R}$,
and $r(s^{\prime}|s,a)$ denotes the reward that the agent observes when state
transition from $s$ to $s^{{}^{\prime}}$ after it plays $a$.
$\rho_{0}(\cdot):\mathcal{S}\rightarrow[0,1]$ is the initial state
distribution and $\gamma\in(0,1)$.

A stationary parameterized policy $\pi_{\bm{\theta}}$ is a probability
distribution defined on $\mathcal{S}\times\mathcal{A}$,
$\pi_{\bm{\theta}}(a|s)$ denotes the probability of playing $a$ in state $s$.
We use $\Pi_{\bm{\theta}}$ to denote the set of all stationary policies, where
$\Pi_{{{\bm{\theta}}}}=\\{\pi_{{{\bm{\theta}}}}:{{\bm{\theta}}}\in\mathbb{R}^{p}\\}$,
and ${{\bm{\theta}}}$ is a parameter needed to be learned. Let
$\mathbf{P}_{\pi_{\bm{\theta}}}\in\mathbb{R}^{|\mathcal{S}|\times|\mathcal{S}|}$
be a state transition probability matrix, and their components are:
$\mathbf{P}_{\pi_{\bm{\theta}}}[s,s^{\prime}]=\sum_{a\in\mathcal{A}}\pi_{\bm{\theta}}(a|s)\mathbb{P}(s^{\prime}|s,a)=:\mathbb{P}_{\pi_{\bm{\theta}}}(s^{{}^{\prime}}|s),$
which denotes one-step state transformation probability from $s$ to
$s^{{}^{\prime}}$ by executing $\pi_{\bm{\theta}}$. Let
$\tau=\\{s_{t},a_{t},r_{t+1}\\}_{t\geq 0}\sim\pi_{\bm{\theta}}$ be a
trajectory generated by $\pi_{\bm{\theta}}$, where $s_{0}\sim\rho_{0}(\cdot)$,
$a_{t}\sim\pi_{\bm{\theta}}(\cdot|s_{t})$,
$s_{t+1}\sim\mathbb{P}(\cdot|s_{t},a_{t})$, and
$r_{t+1}=r(s_{t+1}|s_{t},a_{t})$. We use
$\mathbb{P}_{\pi_{\bm{\theta}}}(s_{t}=s^{{}^{\prime}}|s)$ to denote the
probability of visiting the state $s^{{}^{\prime}}$ after $t$ time steps from
the state $s$ by executing $\pi_{\bm{\theta}}$. Due to the Markov property in
MDP, $\mathbb{P}_{\pi_{\bm{\theta}}}(s_{t}=s^{{}^{\prime}}|s)$ is
$(s,s^{{}^{\prime}})$-th component of the matrix
$\mathbf{P}^{t}_{\pi_{\bm{\theta}}}$, i.e.,
$\mathbb{P}_{\pi_{\bm{\theta}}}(s_{t}=s^{{}^{\prime}}|s)=\mathbf{P}^{t}_{\pi_{\bm{\theta}}}[s,s^{{}^{\prime}}].$
Finally, let
$d_{\pi_{\bm{\theta}}}^{s_{0}}(s)=(1-\gamma)\sum_{t=0}^{\infty}\gamma^{t}\mathbb{P}_{\pi_{\bm{\theta}}}(s_{t}=s|s_{0})$
be the stationary state distribution of the Markov chain (starting at $s_{0}$)
induced by policy $\pi_{\bm{\theta}}$. We define
$d_{\pi_{\bm{\theta}}}^{\rho_{0}}(s)=\mathbb{E}_{s_{0}\sim\rho_{0}(\cdot)}[d_{\pi_{\bm{\theta}}}^{s_{0}}(s)]$
as the discounted state visitation distribution on initial distribution
$\rho_{0}(\cdot)$.

The _state value function_ of $\pi_{\bm{\theta}}$ is defined as
$V_{\pi_{\bm{\theta}}}(s)=\mathbb{E}_{\pi_{\bm{\theta}}}[\sum_{t=0}^{\infty}\gamma^{t}r_{t+1}|s_{0}=s],$
where $\mathbb{E}_{\pi_{\bm{\theta}}}[\cdot|\cdot]$ denotes a conditional
expectation on actions which are selected by $\pi_{\bm{\theta}}$. Its _state-
action value function_ is
$Q_{\pi_{\bm{\theta}}}(s,a)=\mathbb{E}_{\pi_{\bm{\theta}}}[\sum_{t=0}^{\infty}\gamma^{t}r_{t+1}|s_{0}=s,a_{0}=a]$,
and advantage function is
$A_{\pi_{\bm{\theta}}}(s,a)=Q_{\pi_{\bm{\theta}}}(s,a)-V_{\pi_{\bm{\theta}}}(s)$.
The goal of reinforcement learning is to maximize
$J(\pi_{\bm{\theta}})=\mathbb{E}_{s\sim\rho_{0}(\cdot)}[V_{\pi_{\bm{\theta}}}(s)].$

###  2.1 Policy Gradient and Generalized Advantage Estimator (GAE)

Policy gradient (Williams, 1992; Sutton et al., 2000) is widely used to solve
policy optimization, which maximizes the expected total reward by repeatedly
estimating the gradient $g=\nabla J(\pi_{\bm{\theta}})$. Schulman et al.
(2016) summarize several different related expressions for the policy
gradient:

$\displaystyle g=\nabla
J(\pi_{\bm{\theta}})=\mathbb{E}\left[\sum_{t=0}^{\infty}\Psi_{t}\nabla\log\pi_{\bm{\theta}}(a_{t}|s_{t})\right],$
(1)

where $\Psi_{t}$ can be total discounted reward of the trajectory, value
function, advantage function or temporal difference (TD) error. As stated by
Schulman et al. (2016), the choice $\Psi_{t}=A(s_{t},a_{t})$ yields almost the
lowest possible variance, which is consistent with the theoretical analysis
(Greensmith et al., 2004; Wu et al., 2018). Furthermore, Schulman et al.
(2016) propose generalized advantage estimator ($\mathtt{GAE}$)
$\hat{A}^{\mathtt{GAE}(\gamma,\lambda)}_{t}(s_{t},a_{t})$ to replace
$\Psi_{t}$: for any $\lambda\in[0,1]$,

$\displaystyle\hat{A}^{\mathtt{GAE}(\gamma,\lambda)}_{t}(s_{t},a_{t})=\sum_{\ell=0}^{\infty}(\gamma\lambda)^{\ell}\delta^{V}_{t+\ell},$
(2)

where $\delta^{V}_{t}=r_{t+1}+\gamma V(s_{t+1})-V(s_{t})$ is TD error, and
$V(\cdot)$ is an estimator of value function. GAE is an efficient technique
for data efficiency and reliable performance of reinforcement learning.

###  2.2 Safe Reinforcement Learning

Safe RL is often formulated as a constrained MDP (CMDP)
$\mathcal{M}\cup\mathcal{C}$ (Altman, 1999), which is a standard MDP
$\mathcal{M}$ augmented with an additional constraint set $\mathcal{C}$. The
set $\mathcal{C}=\\{(c_{i},b_{i})\\}_{i=1}^{m}$, where $c_{i}$ are cost
functions: $c_{i}:\mathcal{S}\times\mathcal{A}\rightarrow\mathbb{R}$, and
limits are $b_{i}$, $i=1,\cdot,m$. The _cost-return_ is defined as:
$J^{c_{i}}(\pi_{\bm{\theta}})=\mathbb{E}_{\pi_{\bm{\theta}}}\left[\sum_{t=0}^{\infty}\gamma^{t}c_{i}(s_{t},a_{t})\right]$,
then we define the feasible policy set $\Pi_{\mathcal{C}}$ as:
$\Pi_{\mathcal{C}}=\cap_{i=1}^{m}\left\\{\pi_{\bm{\theta}}\in\Pi_{\bm{\theta}}~{}~{}\text{and}~{}~{}J^{c_{i}}(\pi_{\bm{\theta}})_{\leq}b_{i}\right\\}.$
The goal of CMDP is to search the optimal policy $\pi_{\star}$:

$\displaystyle\pi_{\star}=\arg\max_{\pi_{\bm{\theta}}\in\Pi_{\mathcal{C}}}J(\pi_{\bm{\theta}}).$
(3)

Furthermore, we define value functions, action-value functions, and advantage
functions for the auxiliary costs in analogy to
$V_{\pi_{\bm{\theta}}},Q_{\pi_{\bm{\theta}}}$, and $A_{\pi_{\bm{\theta}}}$,
with $c_{i}$ replacing $r$ respectively, we denote them as
$V^{c_{i}}_{\pi_{\bm{\theta}}},Q^{c_{i}}_{\pi_{\bm{\theta}}}$, and
$A^{c_{i}}_{\pi_{\bm{\theta}}}$. For example,
$V^{c_{i}}_{\pi_{\bm{\theta}}}(s)=\mathbb{E}_{\pi_{\bm{\theta}}}\left[\sum_{t=0}^{\infty}\gamma^{t}c_{i}(s_{t},a_{t})|s_{0}=s\right]$.
Without loss of generality, we will restrict our discussion to the case of one
constraint with a cost function $c$ and upper bound $b$. Finally, we extend
the GAE with respect to auxiliary cost function $c$:

$\displaystyle\hat{A}^{\mathtt{GAE}(\gamma,\lambda)}_{C,t}(s_{t},a_{t})=\sum_{\ell=0}^{\infty}(\gamma\lambda)^{\ell}\delta^{C}_{t+\ell},$
(4)

where $\delta^{C}_{t}=r_{t+1}+\gamma C(s_{t+1})-C(s_{t})$ is TD error, and
$C(\cdot)$ is an estimator of cost function $c$.

##  3 Generalized Policy Performance Difference Bounds

In this section, we show some generalized policy optimization performance
bounds for $J(\pi_{\bm{\theta}})$ and $J^{c}(\pi_{\bm{\theta}})$. The proposed
bounds provide some new surrogate functions with respect to the objective and
cost function, which are theoretical foundations for us to design efficient
algorithms to improve policy performance and satisfy constraints. Before we
present the new performance difference bounds, let us revisit a classic
performance difference from Kakade and Langford (2002),

$\displaystyle
J(\pi_{{\bm{\theta}}})-J(\pi_{{\bm{\theta}}^{{}^{\prime}}})=(1-\gamma)^{-1}\mathbb{E}_{s\sim
d_{\pi_{\bm{\theta}}}^{\rho_{0}}(\cdot),a\sim\pi_{\bm{\theta}}(\cdot|s)}\left[A_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}(s,a)\right].$
(5)

Eq.(5) shows a difference between two arbitrary policies $\pi_{\bm{\theta}}$
and $\pi_{{\bm{\theta}}^{{}^{\prime}}}$ with different parameters
$\bm{\theta}$ and $\bm{\theta}^{{}^{\prime}}$. According to (5), we rewrite
the policy optimization (3) as follows

$\displaystyle\pi_{\star}=\arg\max_{\pi_{\bm{\theta}}\in\Pi_{\mathcal{C}}}\mathbb{E}_{s\sim
d_{\pi_{\bm{\theta}}}^{\rho_{0}}(\cdot),a\sim\pi_{\bm{\theta}}(\cdot|s)}\left[A_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}(s,a)\right].$
(6)

However, Eq.(5) or (6) is very intractable for sampling-based policy
optimization since it requires the data comes from the (unknown) policy
$\pi_{\bm{\theta}}$ that needed to be learned. In this section, we provide a
bound refines the result (5), which provide the sights for surrogate functions
to solve problem (3).

###  3.1 Some Additional Notations

We use a bold lowercase letter to denote a vector, e.g.,
$\mathbf{a}=(a_{1},a_{2},\cdots,a_{n})$, and its $i$-th element
$\mathbf{a}[i]=:a_{i}$. Let $\varphi(\cdot):\mathcal{S}\rightarrow\mathbb{R}$
be a function defined on $\mathcal{S}$,
$\delta_{t}^{\varphi}=r(s_{t+1}|s_{t},a_{t})+\gamma\varphi(s_{t+1})-\varphi(s_{t})$
is TD error with respect to $\varphi(\cdot)$. For two arbitrary policies
$\pi_{\bm{\theta}}$ and $\pi_{{\bm{\theta}}^{{}^{\prime}}}$, we denote
$\delta^{\varphi}_{\pi_{\bm{\theta}},t}(s)$ as the expectation of TD error,
and define
$\Delta_{t}^{\varphi}(\pi_{\bm{\theta}},\pi_{{\bm{\theta}}^{{}^{\prime}}},s)$
as the difference between $\delta^{\varphi}_{\pi_{\bm{\theta}},t}(s)$ and
$\delta^{\varphi}_{\pi_{{\bm{\theta}}^{{}^{\prime}}},t}(s)$:

$\displaystyle\delta^{\varphi}_{\pi_{\bm{\theta}},t}(s)=\underset{\begin{subarray}{c}s_{t}\sim\mathbb{P}_{\pi_{\bm{\theta}}}(\cdot|s)\\\
a_{t}\sim{\pi_{\bm{\theta}}}(\cdot|s_{t})\\\
s_{t+1}\sim\mathbb{P}(\cdot|s_{t},a_{t})\end{subarray}}{\mathbb{E}}\left[\delta_{t}^{\varphi}\right],\Delta_{t}^{\varphi}(\pi_{\bm{\theta}},\pi_{{\bm{\theta}}^{{}^{\prime}}},s)=\underset{\begin{subarray}{c}s_{t}\sim\mathbb{P}_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}(\cdot|s)\\\
a_{t}\sim{\pi_{{\bm{\theta}}^{{}^{\prime}}}}(\cdot|s_{t})\\\
s_{t+1}\sim\mathbb{P}(\cdot|s_{t},a_{t})\end{subarray}}{\mathbb{E}}\left[\left(\dfrac{\pi_{\bm{\theta}}(a_{t}|s_{t})}{\pi_{{\bm{\theta}}^{{}^{\prime}}}(a_{t}|s_{t})}-1\right)\delta_{t}^{\varphi}\right].$

Furthermore, we introduce two vectors
$\bm{\delta}^{\varphi}_{\pi_{\bm{\theta}},t},\bm{\Delta}_{t}^{\varphi}(\pi_{\bm{\theta}},\pi_{{\bm{\theta}}^{{}^{\prime}}})\in\mathbb{R}^{|\mathcal{S}|}$,
and their components are:

$\displaystyle\bm{\delta}^{\varphi}_{\pi_{\bm{\theta}},t}[s]=\delta^{\varphi}_{\pi_{\bm{\theta}},t}(s),~{}~{}~{}\bm{\Delta}_{t}^{\varphi}(\pi_{\bm{\theta}},\pi_{{\bm{\theta}}^{{}^{\prime}}})[s]=\Delta_{t}^{\varphi}(\pi_{\bm{\theta}},\pi_{{\bm{\theta}}^{{}^{\prime}}},s).$
(7)

Let matrix
$\mathbf{P}^{(\lambda)}_{\pi_{\bm{\theta}}}=(1-\gamma\lambda)\sum_{{t}=0}^{\infty}(\gamma\lambda)^{{t}}\mathbf{P}^{{t}+1}_{\pi_{\bm{\theta}}}$,
where $\lambda\in[0,1]$. It is similar to the normalized discounted
distribution $d_{\pi_{\bm{\theta}}}^{\rho_{0}}(s)$, we extend it to
$\lambda$-version and denote it as ${d}_{\pi_{\bm{\theta}}}^{\lambda}(s)$:

${d}_{\pi_{\bm{\theta}}}^{\lambda}(s)=\mathbb{E}_{s_{0}\sim\rho_{0}(\cdot)}\left[(1-\tilde{\gamma})\sum_{t=0}^{\infty}{\tilde{\gamma}}^{t}{\mathbb{P}}^{(\lambda)}_{\pi_{\bm{\theta}}}(s_{t}=s|s_{0})\right],$

where $\tilde{\gamma}=\frac{\gamma(1-\lambda)}{1-\gamma\lambda}$, the
probability $\mathbb{P}^{(\lambda)}_{\pi_{\bm{\theta}}}(s_{t}=s|s_{0})$ is the
$(s_{0},s)$-th component of the matrix product
$\left(\mathbf{P}^{(\lambda)}_{\pi_{\bm{\theta}}}\right)^{t}$. Finally, we
introduce a vector
$\mathbf{d}_{\pi_{\bm{\theta}}}^{\lambda}\in\mathbb{R}^{|\mathcal{S}|}$, and
its components are:
$\mathbf{d}_{\pi_{\bm{\theta}}}^{\lambda}[s]=d_{\pi_{\bm{\theta}}}^{\lambda}(s).$

###  3.2 Main Results

######  Theorem 1 (Generalized Policy Performance Difference).

For any function $\varphi(\cdot):\mathcal{S}\rightarrow\mathbb{R}$, for two
arbitrary policies $\pi_{\bm{\theta}}$ and
$\pi_{{\bm{\theta}}^{{}^{\prime}}}$, for any $p,q\in[1,\infty)$ such that
$\frac{1}{p}+\frac{1}{q}=1$, we define two error terms:

$\displaystyle\epsilon^{\varphi,(\lambda)}_{p,q,t}(\pi_{\bm{\theta}},\pi_{{\bm{\theta}}^{{}^{\prime}}})=:\|\mathbf{d}_{\pi_{\bm{\theta}}}^{\lambda}-\mathbf{d}_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}^{\lambda}\|_{p}\|{\bm{\delta}}^{\varphi}_{\pi_{\bm{\theta}},t}\|_{q},$
(8) $\displaystyle
L^{\varphi,\pm}_{p,q}(\pi_{\bm{\theta}},\pi_{{\bm{\theta}}^{{}^{\prime}}})$
$\displaystyle=:\dfrac{1}{1-\tilde{\gamma}}\sum_{t=0}^{\infty}\gamma^{t}\lambda^{t}\mathbb{E}_{s\sim{d}_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}^{\lambda}(\cdot)}\left[\Delta_{t}^{\varphi}(\pi_{\bm{\theta}},\pi_{{\bm{\theta}}^{{}^{\prime}}},s)\pm\epsilon^{\varphi,(\lambda)}_{p,q,t}(\pi_{\bm{\theta}},\pi_{{\bm{\theta}}^{{}^{\prime}}})\right].$
(9)

Then, the following bound with respect to policy performance difference
$J(\pi_{\bm{\theta}})-J(\pi_{{\bm{\theta}}^{{}^{\prime}}})$ holds:

$\displaystyle
L^{\varphi,-}_{p,q,}(\pi_{\bm{\theta}},\pi_{{\bm{\theta}}^{{}^{\prime}}})\leq
J(\pi_{\bm{\theta}})-J(\pi_{{\bm{\theta}}^{{}^{\prime}}})\leq
L^{\varphi,+}_{p,q,}(\pi_{\bm{\theta}},\pi_{{\bm{\theta}}^{{}^{\prime}}}).$
(10)

###### Proof.

See Appendix E. ∎

The bound (10) is well-defined, i.e., if
$\pi_{\bm{\theta}}=\pi_{{\bm{\theta}}^{{}^{\prime}}}$, all the three terms in
Eq.(10) are zero identically. From Eq.(9), we know the performance difference
bound
$L^{\varphi,\pm}_{p,q}(\pi_{\bm{\theta}},\pi_{{\bm{\theta}}^{{}^{\prime}}})$
(10) can be interpreted by two distinct difference parts: (i) the first
difference part, i.e., the expectation
$\Delta_{t}^{\varphi}(\pi_{\bm{\theta}},\pi_{{\bm{\theta}}^{{}^{\prime}}},s)$,
which is determined by the difference between TD errors of $\pi_{\bm{\theta}}$
and $\pi_{{\bm{\theta}}^{{}^{\prime}}}$; (ii) the second difference part,
i.e., the discounted distribution difference
$\epsilon^{\varphi,(\lambda)}_{p,q,t}(\pi_{\bm{\theta}},\pi_{{\bm{\theta}}^{{}^{\prime}}})$,
which is determined by the gap between the normalized discounted distribution
of $\pi_{\bm{\theta}}$ and $\pi_{{\bm{\theta}}^{{}^{\prime}}}$. Thus, the
difference of both TD errors and discounted distribution determine the policy
difference $J(\pi_{\bm{\theta}})-J(\pi_{{\bm{\theta}}^{{}^{\prime}}})$.

The different choices of $p$ and $q$ lead Eq.(10) to be different bounds. If
$p=1,q=\infty$, we denote
$\epsilon^{\varphi}_{\pi_{\bm{\theta}},t}=:\|{\bm{\delta}}^{\varphi}_{\pi_{\bm{\theta}},t}\|_{q}=\max_{s_{t}\in\mathcal{S}}\mathbb{E}_{a_{t}\sim\pi_{\bm{\theta}}(\cdot|s_{t}),s_{t+1}\sim\mathbb{P}(\cdot|s_{t},a_{t})}[|\delta_{t}^{\varphi}|]$,
then, according to Lemma 2 (see Appendix F.2), when $p=1,q=\infty$, then error
$\epsilon^{\varphi,(\lambda)}_{p,q,t}(\pi_{\bm{\theta}},\pi_{{\bm{\theta}}^{{}^{\prime}}})$
is reduced to:

$\displaystyle\epsilon^{\varphi,(\lambda)}_{p,q,t}(\pi_{\bm{\theta}},\pi_{{\bm{\theta}}^{{}^{\prime}}})\big{|}_{p=1,q=\infty}\leq\dfrac{\tilde{\gamma}\left(\gamma\lambda(|\mathcal{S}|-1)+1\right)\epsilon^{\varphi}_{\pi_{\bm{\theta}},t}}{(1-\tilde{\gamma})(1-\gamma\lambda)}\mathbb{E}_{s\sim
d_{\pi_{\bm{\theta}}}^{\lambda}(\cdot)}\left[2D_{\mathrm{TV}}(\pi_{{\bm{\theta}}^{{}^{\prime}}},\pi_{\bm{\theta}})[s]\right],$

where
$D_{\mathrm{TV}}(\pi_{{\bm{\theta}}^{{}^{\prime}}},\pi_{\bm{\theta}})[s]$ is
the total variational divergence between action distributions at state $s$,
i.e.,

$2D_{\mathrm{TV}}(\pi_{{\bm{\theta}}^{{}^{\prime}}},\pi_{\bm{\theta}})[s]=\sum_{a\in\mathcal{A}}\left|{{\pi_{{\bm{\theta}}^{{}^{\prime}}}}}(a|s)-{{\pi_{\bm{\theta}}}}(a|s)\right|.$

Finally, let $\varphi=V_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}$, the left side of
(10) in Theorem 1 implies a lower bound of performance difference, which
illustrates the worse case of approximation error, we present it in
Proposition 1.

######  Proposition 1.

For any two policies $\pi_{\bm{\theta}}$ and
$\pi_{{\bm{\theta}}^{{}^{\prime}}}$, let
$\epsilon^{V}_{\pi_{\bm{\theta}}}(\pi_{{\bm{\theta}}^{{}^{\prime}}})=:\sup_{t\in\mathbb{N}^{+}}\\{\epsilon^{\varphi}_{\pi_{\bm{\theta}},t}:\varphi=V_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}\\}$,
then

$\displaystyle
J(\pi_{\bm{\theta}})-J(\pi_{{\bm{\theta}}^{{}^{\prime}}})\geq\frac{1}{1-\tilde{\gamma}}\mathbb{E}_{s\sim{d}_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}^{\lambda}(\cdot),a\sim\pi_{\bm{\theta}}(\cdot|s)}\Bigg{[}A^{\mathtt{GAE}(\gamma,\lambda)}_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}(s,a)$
$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}-\dfrac{2\tilde{\gamma}\left(\gamma\lambda(|\mathcal{S}|-1)+1\right)\epsilon^{V}_{\pi_{\bm{\theta}}}(\pi_{{\bm{\theta}}^{{}^{\prime}}})}{(1-\tilde{\gamma})(1-\gamma\lambda)}D_{\mathrm{TV}}(\pi_{{\bm{\theta}}^{{}^{\prime}}},\pi_{\bm{\theta}})[s]\Bigg{]}.$
(11)

The refined bound (11) contains $\mathtt{GAE}$ technique that significantly
reduces variance while maintaining a tolerable level of bias empirically
(Schulman et al., 2016), which implies using the bound (11) as a surrogate
function could improve performance potentially for practice. Although
$\mathtt{GAE}$ has been empirically applied to extensive reinforcement
learning tasks, to the best of our knowledge, the result (11) is the first to
show a rigorous theoretical analysis to extend the surrogate functions to
$\mathtt{GAE}$.

######  Remark 1 (Unification of (Achiam et al., 2017)).

If $\lambda\rightarrow 0$, then the distribution
${d}_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}^{\lambda}(\cdot)$ is reduced to
${d}_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}^{\rho_{0}}(\cdot)$ and the bound (11)
is reduced to

$\displaystyle
J(\pi_{\bm{\theta}})-J(\pi_{{\bm{\theta}}^{{}^{\prime}}})\geq\frac{1}{1-\gamma}\mathbb{E}_{s\sim{d}_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}^{\rho_{0}}(\cdot),a\sim\pi_{\bm{\theta}}(\cdot|s)}\left[A_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}(s,a)-2\dfrac{\gamma}{1-\gamma}\epsilon^{V}_{\pi_{\bm{\theta}}}(\pi_{{\bm{\theta}}^{{}^{\prime}}})D_{\mathrm{TV}}(\pi_{{\bm{\theta}}^{{}^{\prime}}},\pi_{\bm{\theta}})[s]\right],$
(12)

which matches the result of (Achiam et al., 2017, Corollary 1). That is to say
the proposed bound (11) unifies the classic bound (12)

Let $\varphi=V^{c}_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}$, Theorem 1 implies an
upper bound of cost function as presented in the next Proposition 2, we will
use it to make guarantee for safe policy optimization.

######  Proposition 2.

For any two policies $\pi_{\bm{\theta}}$ and
$\pi_{{\bm{\theta}}^{{}^{\prime}}}$, let
$\epsilon^{C}_{\pi_{\bm{\theta}}}(\pi_{{\bm{\theta}}^{{}^{\prime}}})=:\sup_{t\in\mathbb{N}^{+}}\\{\epsilon^{\varphi}_{\pi_{\bm{\theta}},t}:\varphi=V^{c}_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}\\}$,
then

$\displaystyle
J^{c}(\pi_{\bm{\theta}})-J^{c}(\pi_{{\bm{\theta}}^{{}^{\prime}}})\leq\dfrac{1}{1-\tilde{\gamma}}\mathbb{E}_{s\sim{d}_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}^{\lambda}(\cdot),a\sim\pi_{\bm{\theta}}(\cdot|s)}\Bigg{[}A^{\mathtt{GAE}(\gamma,\lambda)}_{\pi_{{\bm{\theta}}^{{}^{\prime}}},C}(s,a)$
$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}+\dfrac{2\tilde{\gamma}\left(\gamma\lambda(|\mathcal{S}|-1)+1\right)\epsilon^{C}_{\pi_{\bm{\theta}}}(\pi_{{\bm{\theta}}^{{}^{\prime}}})}{(1-\tilde{\gamma})(1-\gamma\lambda)}D_{\mathrm{TV}}(\pi_{{\bm{\theta}}^{{}^{\prime}}},\pi_{\bm{\theta}})[s]\Bigg{]}.$
(13)

where we calculate
$A^{\mathtt{GAE}(\gamma,\lambda)}_{\pi_{{\bm{\theta}}^{{}^{\prime}}},C}(s,a)$
according to the data sampled from $\pi_{{\bm{\theta}}^{{}^{\prime}}}$ and the
estimator (4).

All above bound results (11) and (13) can be extended for a total variational
divergence to KL-divergence between policies, which are desirable for policy
optimization.

######  Proposition 3.

All the bounds in (11) and (13) hold if we make the following substitution:

$\mathbb{E}_{s\sim{d}_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}^{\lambda}(\cdot)}\left[D_{\mathrm{TV}}(\pi_{{\bm{\theta}}^{{}^{\prime}}},\pi_{\bm{\theta}})[s]\right]\leftarrow\sqrt{\frac{1}{2}\mathbb{E}_{s\sim{d}_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}^{\lambda}(\cdot)}\left[\emph{KL}(\pi_{{\bm{\theta}}^{{}^{\prime}}},\pi_{\bm{\theta}})[s]\right]},$

where $\mathrm{KL}(\cdot,\cdot)$ is KL-divergence, and
$\mathrm{KL}(\pi_{{\bm{\theta}}^{{}^{\prime}}},\pi_{\bm{\theta}})[s]=\mathrm{KL}(\pi_{{\bm{\theta}}^{{}^{\prime}}}(\cdot|s),\pi_{\bm{\theta}}(\cdot|s))$.

##  4 CUP: Constrained Update Projection

It is challenging to implement CMDP (3) directly since it requires us to judge
whether a proposed policy $\pi_{\bm{\theta}}$ is in the feasible region
$\Pi_{\mathcal{C}}$. According to the bounds in Proposition 1-3, we develop
new surrogate functions to replace the objective and constraints. We propose
the CUP (constrained update projection) algorithm that is a two-step approach
contains _performance improvement_ and _projection_. Due to the limitation of
space, we present all the details of the implementation in Appendix C and
Algorithm 1.

###  4.1 Algorithm

Step 1: Performance Improvement. According to Proposition 1 and Proposition 3,
for an appropriate coefficient $\alpha_{k}$, we update policy as:

$\displaystyle\pi_{{\bm{\theta}}_{k+\frac{1}{2}}}$
$\displaystyle=\arg\max_{\pi_{{\bm{\theta}}}\in\Pi_{{\bm{\theta}}}}\left\\{\underset{\begin{subarray}{c}s\sim{d}_{\pi_{\bm{\theta}_{k}}}^{\lambda}(\cdot)\\\
a\sim\pi_{\bm{\theta}_{k}}(\cdot|s)\end{subarray}}{\mathbb{E}}\left[\frac{\pi_{\bm{\theta}}(a|s)}{\pi_{{\bm{\theta}}_{k}}(a|s)}A^{\mathtt{GAE}(\gamma,\lambda)}_{{\pi_{\bm{\theta}_{k}}}}(s,a)\right]-\alpha_{k}\sqrt{\mathbb{E}_{s\sim{d}_{{\pi_{\bm{\theta}_{k}}}}^{\lambda}(\cdot)}\left[\mathrm{KL}(\pi_{\bm{\theta}_{k}},\pi_{\bm{\theta}})[s]\right]}\right\\}.$
(14)

This step is a typical minimization-maximization (MM) algorithm (Hunter and
Lange, 2004), it includes return maximization and minimization the distance
between old policy and new policy. the expectation (14) by sample averages
according to the trajectories collected by $\pi_{\bm{\theta}_{k}}$.

Step 2: Projection. According to Proposition 2 and Proposition 3, for an
appropriate coefficient $\beta_{k}$, we project the policy
$\pi_{{\bm{\theta}}_{k+\frac{1}{2}}}$ onto the safe constraint set,

$\displaystyle\pi_{{\bm{\theta}}_{k+1}}=\arg\min_{\pi_{{\bm{\theta}}}\in\Pi_{{\bm{\theta}}}}~{}D\left(\pi_{{\bm{\theta}}},\pi_{{\bm{\theta}}_{k+\frac{1}{2}}}\right),~{}\text{s.t.}~{}C_{\pi_{\bm{\theta}_{k}}}(\pi_{\bm{\theta}},\beta_{k})\leq
b,$ (15)

where $D(\cdot,\cdot)$ (e.g., KL divergence or $\ell_{2}$-norm) measures
distance between $\pi_{{\bm{\theta}}_{k+\frac{1}{2}}}$ and
$\pi_{\bm{\theta}}$,

$C_{\pi_{\bm{\theta}_{k}}}(\pi_{\bm{\theta}},\beta)=J^{c}(\pi_{{\bm{\theta}}_{k}})+\frac{1}{1-\tilde{\gamma}}\mathbb{E}_{s\sim{d}_{\pi_{\bm{\theta}_{k}}}^{\lambda}(\cdot),a\sim\pi_{\bm{\theta}}(\cdot|s)}\left[A^{\mathtt{GAE}(\gamma,\lambda)}_{{\pi_{\bm{\theta}}},C}(s,a)\right]+\beta\sqrt{\mathbb{E}_{s\sim{d}_{{\pi_{\bm{\theta}_{k}}}}^{\lambda}(\cdot)}\left[\mathrm{KL}(\pi_{\bm{\theta}_{k}},\pi_{\bm{\theta}})[s]\right]}.$

Until now, the particular choice of surrogate function is heuristically
motivated, we show the worst-case performance degradation guarantee and
approximate satisfaction of safety constraints of CUP in Theorem 2, and its
proof is shown in Appendix G.

######  Theorem 2.

Let
$\chi_{k}=\mathbb{E}_{s\sim{d}_{{\pi_{\bm{\theta}_{k}}}}^{\lambda}(\cdot)}[\emph{KL}(\pi_{\bm{\theta}_{k}},\pi_{\bm{\theta}_{k+\frac{1}{2}}})[s]]$,
$\iota=:\frac{\tilde{\gamma}\left(\gamma\lambda(|\mathcal{S}|-1)+1\right)}{(1-\tilde{\gamma})(1-\gamma\lambda)}$.If
$\pi_{\bm{\theta}_{k}}$ and $\pi_{\bm{\theta}_{k+1}}$ are generated according
to (14)-(15), then the lower bound on policy improvement, and upper bound on
constraint violation are

$\displaystyle J(\pi_{\bm{\theta}_{k+1}})-J(\pi_{\bm{\theta}_{k}})\geq$
$\displaystyle-\dfrac{\iota\alpha_{k}\sqrt{2\chi_{k}}}{1-\tilde{\gamma}}\epsilon^{V}_{\pi_{\bm{\theta}_{k+1}}}(\pi_{\bm{\theta}_{k}}),~{}~{}~{}J^{c}(\pi_{\bm{\theta}_{k+1}})\leq
b+\dfrac{\iota\beta_{k}\sqrt{2\chi_{k}}}{1-\tilde{\gamma}}\epsilon^{C}_{\pi_{\bm{\theta}_{k+1}}}(\pi_{\bm{\theta}_{k}}).$

######  Remark 2 (Asymptotic Safety Guarantee).

Let $\alpha_{k}\rightarrow 0,\beta_{k}\rightarrow 0$ as $k\rightarrow\infty$,
Theorem 2 implies a monotonic policy improvement with an asymptotic safety
guarantee.

###  4.2 Practical Implementation

Now, we present our sample-based implementation for CUP (14)-(15). Our main
idea is to estimate the objective and constraints in (14)-(15) with samples
collected by current policy $\pi_{\bm{\theta}_{k}}$, then solving its
optimization problem via first-order optimizer.

Let $\\{(s_{t},a_{t},r_{t+1},c_{t+1})\\}_{t=1}^{T}\sim\pi_{\bm{\theta}_{k}}$,
we denote the empirical KL-divergence with respect to $\pi_{\bm{\theta}}$ and
$\pi_{{\bm{\theta}}^{{}^{\prime}}}$ as:

$\hat{D}_{\mathrm{KL}}(\pi_{\bm{\theta}},\pi_{{\bm{\theta}}^{{}^{\prime}}})=\frac{1}{T}\sum_{t=1}^{T}\mathrm{KL}(\pi_{\bm{\theta}}(a_{t}|s_{t}),\pi_{{\bm{\theta}}^{{}^{\prime}}}(a_{t}|s_{t})).$

We update performance improvement (14) step as follows,

$\displaystyle\pi_{{\bm{\theta}}_{k+\frac{1}{2}}}$
$\displaystyle=\arg\max_{\pi_{\bm{\theta}}\in\Pi_{\theta}}\left\\{\dfrac{1}{T}\sum_{t=1}^{T}\dfrac{\pi_{\bm{\theta}}(a_{t}|s_{t})}{\pi_{{\bm{\theta}}_{k}}(a_{t}|s_{t})}\hat{A}_{t}-\alpha_{k}\sqrt{\hat{D}_{\mathrm{KL}}(\pi_{{\bm{\theta}}_{k}},\pi_{{\bm{\theta}}})}\right\\},$

where $\hat{A}_{t}$ is an estimator of
$A^{\mathtt{GAE}(\gamma,\lambda)}_{\pi_{{\bm{\theta}}_{k}}}(s,a)$.

Then we update the projection step by replacing the distance $D$ by KL-
divergence, the next Theorem 3 (for its proof, see Appendix C.2) provides a
fundamental way for us to solve projection step (15).

######  Theorem 3.

The constrained problem (40) is equivalent to the following primal-dual
problem:

$\displaystyle\max_{\nu\geq
0}\min_{\pi_{\bm{\theta}}\in\Pi_{\bm{\theta}}}\left\\{D\left(\pi_{{\bm{\theta}}},\pi_{{\bm{\theta}}_{k+\frac{1}{2}}}\right)+\nu\left(C_{\pi_{\bm{\theta}_{k}}}(\pi_{\bm{\theta}},\beta)-b\right)\right\\}.$

According to Theorem 3, we solve the constraint problem (15) by the following
primal-dual approach,

$\displaystyle(\pi_{{\bm{\theta}}_{k+1}},\nu_{k+1})=\arg\min_{\pi_{\bm{\theta}}\in\Pi_{\bm{\theta}}}\max_{\nu\geq
0}\left\\{\hat{D}_{\mathrm{KL}}(\pi_{{\bm{\theta}}_{k+\frac{1}{2}}},\pi_{{\bm{\theta}}})+\nu\hat{C}(\pi_{\bm{\theta}},\pi_{{\bm{\theta}}_{k}})\right\\}$

where
$\hat{C}(\pi_{\bm{\theta}},\pi_{{\bm{\theta}}_{k}})=\hat{J}^{C}+\frac{1}{1-\tilde{\gamma}}\cdot\frac{1}{T}\sum_{t=1}^{T}\frac{\pi_{\bm{\theta}}(a_{t}|s_{t})}{\pi_{{\bm{\theta}}_{k}}(a_{t}|s_{t})}\hat{A}^{C}_{t}+\beta_{k}\sqrt{\hat{D}_{\mathrm{KL}}(\pi_{{\bm{\theta}}_{k}},\pi_{{\bm{\theta}}})}-b,$
$\hat{J}^{C}$and $\hat{A}^{C}_{t}$ are estimators for cost-return and cost-
advantage.

Finally, let

$\displaystyle\hat{\mathcal{L}}_{\text{c}}\left(\pi_{\bm{\theta}},\pi_{{\bm{\theta}}_{k}},{\bm{\theta}}_{k+\frac{1}{2}},\nu\right)=:\hat{D}_{\mathrm{KL}}(\pi_{{\bm{\theta}}_{k+\frac{1}{2}}},\pi_{{\bm{\theta}}})+\nu\hat{C}(\pi_{\bm{\theta}},\pi_{{\bm{\theta}}_{k}}),$
(16)

we update the parameters $({\bm{\theta}}_{k+1},\nu_{k+1})$ as follows,

$\displaystyle\bm{\theta}_{k+1}$
$\displaystyle\leftarrow\bm{\theta}_{k}-\eta\dfrac{\partial}{\partial\bm{\theta}}\hat{\mathcal{L}}_{\text{c}}\left(\pi_{\bm{\theta}},\pi_{{\bm{\theta}}_{k}},{\bm{\theta}}_{k+\frac{1}{2}},\nu\right)\Big{|}_{\bm{\theta}=\bm{\theta}_{k},\nu=\nu_{k}},$
(17) $\displaystyle\nu_{k+1}$
$\displaystyle\leftarrow\left\\{\nu_{k}+\eta\dfrac{\partial}{\partial\nu}\hat{\mathcal{L}}_{\text{c}}\left(\pi_{\bm{\theta}},\pi_{{\bm{\theta}}_{k}},{\bm{\theta}}_{k+\frac{1}{2}},\nu\right)\Big{|}_{\bm{\theta}=\bm{\theta}_{k},\nu=\nu_{k}}\right\\}_{+},$
(18)

where $\eta>0$ is step-size, $\\{\cdot\\}_{+}$ denotes the positive part,
i.e., if $x\leq 0$, $\\{x\\}_{+}=0$, else $\\{x\\}_{+}=x$. We have shown all
the details of the implementation in Algorithm 1.

##  5 Related Work

Due to the limitation of space, for more discussions and comparisons, see
Appendix B and Table 2.

###  5.1 Local Policy Search and Lagrangian Approach

A direct way to solve CMDP (3) is to apply _local policy search_ (Peters and
Schaal, 2008; Pirotta et al., 2013) over the policy space $\Pi_{\mathcal{C}}$,
i.e.,

$\displaystyle\pi_{{{\bm{\theta}}}_{k+1}}=\arg\max_{\pi_{{\bm{\theta}}}\in\Pi_{{\bm{\theta}}}}J(\pi_{{\bm{\theta}}}),~{}\text{s.t}.~{}J^{c}(\pi_{{\bm{\theta}}})\leq
b,~{}\text{and}~{}D(\pi_{{\bm{\theta}}},\pi_{{{\bm{\theta}}}_{k}})<\delta,$
(19)

where $\delta$ is a positive scalar, $D(\cdot,\cdot)$ is some distance
measure. For practice, the local policy search (19) is challenging to
implement because it requires evaluation of the constraint function $c$ to
determine whether a proposed point $\pi$ is feasible (Zhang et al., 2020).
Besides, Li and Belta (2019); Cheng et al. (2019); Liu et al. (2020) provide a
local policy search via the barrier function. The key idea of the proposed CUP
is parallel to Barrier functions. When updating policy according to samples,
local policy search (19) requires off-policy evaluation (Achiam et al., 2017),
which is very challenging for high-dimension control problem (Duan et al.,
2016; Yang et al., 2018, 2021a).

A way to solve CMDP (3) is Lagrangian approach that is also known as primal-
dual problem:

$\displaystyle(\pi_{\star},\lambda_{\star})=\arg\min_{\lambda\geq
0}\max_{\pi_{\bm{\theta}}\in\Pi_{\bm{\theta}}}\left\\{J(\pi_{\bm{\theta}})-\lambda(J^{c}(\pi_{\bm{\theta}})-b)\right\\}.$
(20)

Although extensive canonical algorithms are proposed to solve problem (20),
e.g., (Liang et al., 2018; Tessler et al., 2019; Paternain et al., 2019; Le et
al., 2019; Russel et al., 2020; Satija et al., 2020; Chen et al., 2021), the
policy updated by Lagrangian approach may be infeasible w.r.t. CMDP (3). This
is hazardous in reinforcement learning when one needs to execute the
intermediate policy (which may be unsafe) during training (Chow et al., 2018).

Constrained Policy Optimization (CPO). Recently, Achiam et al. (2017) suggest
to replace the cost constraint with a surrogate cost function which evaluates
the constraint $J^{c}(\pi_{{\bm{\theta}}})$ according to the samples collected
from the current policy $\pi_{{\bm{\theta}}_{k}}$, see Eq.(21)-(23). For a
given policy $\pi_{{\bm{\theta}}_{k}}$, CPO (Achiam et al., 2017) updates new
policy $\pi_{{\bm{\theta}}_{k+1}}$ as follows:

$\displaystyle\pi_{{\bm{\theta}}_{k+1}}=\arg\max_{\pi_{{\bm{\theta}}}\in\Pi_{{\bm{\theta}}}}~{}~{}~{}~{}\mathbb{E}_{s\sim
d^{\rho_{0}}_{\pi_{{\bm{\theta}}_{k}}}(\cdot),a\sim\pi_{{\bm{\theta}}}(\cdot|s)}\left[A_{\pi_{{\bm{\theta}}_{k}}}(s,a)\right]$
(21)
$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}\text{s.t.}~{}~{}J^{c}(\pi_{{\bm{\theta}}_{k}})+\frac{1}{1-\gamma}\mathbb{E}_{s\sim
d^{\rho_{0}}_{\pi_{{\bm{\theta}}_{k}}}(\cdot),a\sim\pi_{{\bm{\theta}}}(\cdot|s)}\left[A^{c}_{\pi_{{\bm{\theta}}_{k}}}(s,a)\right]\leq
b,$ (22)
$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}\bar{D}_{\text{KL}}(\pi_{{\bm{\theta}}},\pi_{{\bm{\theta}}_{k}})=\mathbb{E}_{s\sim
d^{\rho_{0}}_{\pi_{{\bm{\theta}}_{k}}}(\cdot)}[\text{KL}(\pi_{{\bm{\theta}}},\pi_{{\bm{\theta}}_{k}})[s]]\leq\delta.$
(23)

Existing recent works (e.g., (Achiam et al., 2017; Vuong et al., 2019; Yang et
al., 2020; Han et al., 2020; Bisi et al., 2020; Bharadhwaj et al., 2021)) try
to find some convex approximations to replace the term
$A_{\pi_{{\bm{\theta}}_{k}}}(s,a)$ and
$\bar{D}_{\text{KL}}(\pi_{{\bm{\theta}}},\pi_{{\bm{\theta}}_{k}})$ in
Eq.(24)-(26). Such first-order and second-order approximations turn a non-
convex problem (24)-(26) to be a convex problem, it seems to make a simple
solution, but this approach results in many error sources and troubles in
practice. Firstly, it still lacks a theory analysis to show the difference
between the non-convex problem (24)-(26) and its convex approximation. Policy
optimization is a typical non-convex problem (Yang et al., 2021b); its convex
approximation may introduce some error for its original issue. Secondly, CPO
updates parameters according to conjugate gradient (Süli and Mayers, 2003),
and its solution involves the inverse Fisher information matrix, which
requires expensive computation for each update.

Instead of using a convex approximation for the objective function, the
proposed CUP algorithm improves CPO and PCPO at least two aspects. Firstly,
the CUP directly optimizes the surrogate objective function via the first-
order method, and it does not depend on any convex approximation. Thus, the
CUP effectively avoids the expensive computation for the inverse Fisher
information matrix. Secondly, CUP extends the surrogate objective function to
GAE. Although Zhang et al. (2020) has used the GAE technique in experiments,
to the best of our knowledge, it still lacks a rigorous theoretical analysis
involved GAE before we propose CUP.

##  6 Experiment

In this section, we aim to answer the following three issues:

  * •

Does CUP satisfy the safety constraints in different environments? Does CUP
performs well with different cost limits?

  * •

How does CUP compare to the state-of-the-art safe RL algorithms?

  * •

Does CUP play a sensibility during the hyper-parameters in the tuning
processing?

We train different robotic agents using five MuJoCo physical simulators
(Todorov et al., 2012) which are open by OpenAI Gym API (Brockman et al.,
2016), and Safety Gym (Ray et al., 2019). For more details, see Appendix H.2.
Baselines includes CPO (Achiam et al., 2017), PCPO (Yang et al., 2020), TRPO
Lagrangian (TRPO-L), PPO Lagrangian (PPO-L) and FOCOPS (Zhang et al., 2020).
TRPO-L and PPO-L are improved by (Chow et al., 2018; Ray et al., 2019), which
are based on TRPO (Schulman et al., 2015) and PPO (Schulman et al., 2017).
These two algorithms use the Lagrangian method (Bertsekas, 1997), which
applies adaptive penalty coefficients to satisfy the constraint.

Figure 1: Comparison of CUP to baseline algorithms over 10 seeds on Mujoco.
Figure 2: Comparison of CUP to to baseline algorithms over 3 seeds on Satety-
Gym.

###  6.1 Evaluation CUP and Comparison Analysis

We have shown the Learning curves for CUP, and other baselines in Figure 1-2,
and Table 1 summarizes the performance of all algorithms. Results show that
CUP quickly stabilizes the constraint return around the limit value while
converging the objective return to higher values faster. In most cases, the
traces of constraint from CUP almost coincide with the dashed black line of
the limit. By contrast, the baseline algorithms frequently suffer from over or
under the correction.

From Figure 1, we know initial policies of the baseline algorithms are not
guaranteed to be feasible, such as in Swimmer-v3, while CUP performs the best
and keeps safety learning in Swimmer-v3 tasks. In the HumanoidCircle task, all
the algorithms learn steadily to obtain a safe policy, except PPO-L.
Additionally, we observed that CUP brings the policy back to the feasible
range faster than other baselines in the HumanoidCircle task. In the Ant-v3
task, only the FOCOPS and the proposed CUP learn safely, and both CPO and
TRPO-L violate the safety constraints significantly. Besides, although FOCOPS
and CUP converge to a safe policy, CUP obtains a better reward performance
than FOCOPS in the Ant-v3 task. The result of Figure 2 is relatively complex,
the initial policies of the CPO and PCPO are not guaranteed to be feasible on
both Safexp-PointGoal1-v0 and Safexp-PointButton1-v0. We think it is not
accidental, but it partially provides corroboration of the previous
discussions in Appendix B. Both CPO and PCPO use first-order and second-order
approximation to approximate a non-convex problem as a convex problem, which
inevitably produces a significant deviation from the original RL problem, and
it is more serious in large-scale and complex control systems.

From Table 1, we know although PPO-L achieves a reward of $35.58\pm 5.68$
outperforms CUP in Swimmer-v3, PPO-L obtains a cost of $54.91\pm 3.93$ that
violates the cost limit of $24.5$ significantly, which implies PPO-L learns a
dangerous policy under this setting. On the other hand, Figure 1 has shown
that CUP generally gains higher returns than different baselines while
enforcing the cost constraint. Mainly, CUP achieves a reward performance of
${2025.56\pm 122.35}$ that significantly outperforms all the baseline
algorithms. Additionally, after equal iterations, CUP performs a greater speed
of stabilizing the constraint return around the limit value and is quicker to
find feasible policies to gain a more significant objective return.

Environment CPO TRPO-L PPO-L PCPO FOCOPS CUP Ant-v3 Return $1030.17\pm 8.15$
$480.86\pm 161.05$ $1012.02\pm 17.26$ $90.83\pm 17.66$ $1662.53\pm 17.40$
$\bm{1743.66\pm 40.5}$ cost limit: 103 Constraint
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color<EMAIL_ADDRESS>4.80}$
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color<EMAIL_ADDRESS>67.9}$
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color<EMAIL_ADDRESS>15.48}$
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color<EMAIL_ADDRESS>5.53}$ $101.31\pm 0.41$ $99.11\pm 0.93$ Hopper-v3 Return $875.89\pm 285.17$
$1025.49\pm 10.68$ $1010.2\pm 61.48$ $214.90\pm 101.22$ $1687.72\pm 24.38$
$\bm{2025.56\pm 122.35}$ cost limit: 83 Constraint $76.6\pm 10.62$ $40.36\pm
4.75$
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color<EMAIL_ADDRESS>31.19}$ $36.63\pm 12.54$
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color<EMAIL_ADDRESS>1.455}$ $79.98\pm 2.306$ Swimmer-v3 Return $18.77\pm 6.56$ $27.35\pm 10.07$
$\bm{35.58\pm 5.68}$ $37.73\pm 3.56$ $28.15\pm 4.30$ $33.38\pm 0.54$ cost
limit: 24.5 Constraint
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color<EMAIL_ADDRESS>3.31}$
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color<EMAIL_ADDRESS>7.46}$
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color<EMAIL_ADDRESS>3.93}}$
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color<EMAIL_ADDRESS>22.71}}$
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color<EMAIL_ADDRESS>4.16}$ $23.31\pm 0.052$ Humanoid-v3 Return $326.95\pm 16.00$ $307.71\pm 24.71$
$322.11\pm 25.54$ $962.13\pm 57.94$ $542.5\pm 4.76$ $\bm{1066.83\pm 266.12}$
cost limit: 20.0 Constraint
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color<EMAIL_ADDRESS>2.13}$ $18.22\pm 3.04$
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color<EMAIL_ADDRESS>4.54}$
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color<EMAIL_ADDRESS>3.52}$ $20.04\pm 0.19$ $19.91\pm 0.36$ Humanoid-Circle Return $237.54\pm
23.20$ $384.45\pm 47.66$ $243.35\pm 37.90$ $525.23\pm 48.32$ $713.04\pm 9.25$
$\bm{768.65\pm 63.70}$ cost limit: 50.0 Constraint $43.64\pm 1.91$
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color<EMAIL_ADDRESS>1.48}$ $41.17\pm 3.98$ $50.80\pm 4.57$ $47.73\pm 0.64$ $48.23\pm 0.65$

Table 1: Average results for baseline algorithms and CUP over 10 seeds the
last 500 iterations.

(a) Cost constraint with respect to hyper-parameter $\nu$ (defined in
Projection step). (b) Performance w.r.t. penalty factor $\alpha$. (c)
Performance w.r.t. cost limit.

Figure 3: Sensitivity analysis for hyper-parameters tuning with respect to
$\nu$, $\alpha$ and cost limit.

###  6.2 Sensitivity Analysis for Hyper-Parameters Tuning

Hyper-parameters tuning is necessary to achieve efficient policy improvement
and enforce constraints. We investigate the performance with respect to the
parameters: $\nu$, step-size $\alpha$, and cost limit $b$.

From Figure 3 (a), we know if the estimated cost under the target threshold
$b$, then $\nu$ keeps calm, which implies $\nu$ is not activated. Such an
empirical phenomenon gives significant expression to the Ant-v3, Humanoid-v3,
and Hopper-v3 environments. While if the estimated cost exceeds the target
threshold $b$, $\nu$ will be activated, which requires the agent to play a
policy on the safe region. Those empirical results are consistent with the
update rule of $\nu$:

$\nu_{k+1}=\\{\nu_{k}+\eta(\hat{J}_{k}^{C}-b)\\}_{+},$

which implies the projection of CUP plays an important role for the agent to
learn a safe policy. Additionally, Figure 3 (a) provides a visualization way
to show the difficulty of different tasks, where the task actives much
quantification of $\nu$, such a task is more challenging to obtain a safe
policy. Furthermore, Figure 3 (b) shows that the performance of CUP is still
very stable for different settings of $\alpha$, and the constraint value of
CUP also still fluctuates around the target value. The different value
achieved by CUP in different setting $\alpha$ is affected by the simulated
environment and constraint thresholds, which are easy to control. Finally,
Figure 3 (c) shows that CUP learns safe policies stably under the cost limit
thresholds. We compare policy performance and cost under different cost limit
settings. For example, in the Swimmer-v3, we set cost limit $b$ among
$\\{10,15,20,25,30\\}$. Different cost limit setting implies different
difficulty for learning, results show that CUP is scalable to various complex
tasks, which means CUP is robust to different cost limit settings for various
safe RL tasks.

##  7 Conclusion

This paper proposes the CUP algorithm with a theoretical safety guarantee. We
derive the CUP based on the newly proposed surrogate functions with respect to
objectives and constraints and provide a practical implementation of CUP that
does not depend on any convex approximation. We compared CUP against a
comprehensive list of safe RL baselines on a wide range of tasks, which shows
the effectiveness of CUP where the agent satisfies safe constraints.

## References

  * Achiam et al. [2017] Joshua Achiam, David Held, Aviv Tamar, and Pieter Abbeel.  Constrained policy optimization.  In Proceedings of International Conference on Machine Learning (ICML), volume 70, pages 22–31, 2017.
  * Afsar et al. [2021] M Mehdi Afsar, Trafford Crump, and Behrouz Far.  Reinforcement learning based recommender systems: A survey.  arXiv preprint arXiv:2101.06286, 2021.
  * Altman [1999] Eitan Altman.  Constrained Markov decision processes.  CRC Press, 1999.
  * Bellman [1957] Richard Bellman.  A markovian decision process.  Journal of mathematics and mechanics, 6(5):679–684, 1957.
  * Bertsekas [1997] Dimitri P Bertsekas.  Nonlinear programming.  Journal of the Operational Research Society, 48(3):334–334, 1997\.
  * Bharadhwaj et al. [2021] Homanga Bharadhwaj, Aviral Kumar, Nicholas Rhinehart, Sergey Levine, Florian Shkurti, and Animesh Garg.  Conservative safety critics for exploration.  In International Conference on Learning Representations (ICLR), 2021\.
  * Bisi et al. [2020] Lorenzo Bisi, Luca Sabbioni, Edoardo Vittori, Matteo Papini, and Marcello Restelli.  Risk-averse trust region optimization for reward-volatility reduction.  In Christian Bessiere, editor, Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI-20, pages 4583–4589, 2020.
  * Boyd and Vandenberghe [2004] Stephen P Boyd and Lieven Vandenberghe.  Convex optimization.  Cambridge university press, 2004.
  * Brockman et al. [2016] Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojciech Zaremba.  Openai gym.  arXiv preprint arXiv:1606.01540, 2016.
  * Chen et al. [2021] Yi Chen, Jing Dong, and Zhaoran Wang.  A primal-dual approach to constrained markov decision processes.  arXiv preprint arXiv:2101.10895, 2021.
  * Cheng et al. [2019] Richard Cheng, Gábor Orosz, Richard M. Murray, and Joel W. Burdick.  End-to-end safe reinforcement learning through barrier functions for safety-critical continuous control tasks.  In Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence. AAAI Press, 2019.
  * Chow et al. [2018] Yinlam Chow, Ofir Nachum, Edgar Duenez-Guzman, and Mohammad Ghavamzadeh.  A lyapunov-based approach to safe reinforcement learning.  In Advances in Neural Information Processing Systems (NeurIPS), 2018\.
  * Csiszár and Körner [2011] Imre Csiszár and János Körner.  Information theory: coding theorems for discrete memoryless systems.  Cambridge University Press, 2011.
  * Dalal et al. [2018] Gal Dalal, Krishnamurthy Dvijotham, Matej Vecerik, Todd Hester, Cosmin Paduraru, and Yuval Tassa.  Safe exploration in continuous action spaces.  arXiv preprint arXiv:1801.08757, 2018.
  * Duan et al. [2016] Yan Duan, Xi Chen, Rein Houthooft, John Schulman, and Pieter Abbeel.  Benchmarking deep reinforcement learning for continuous control.  In International Conference on Machine Learning (ICML), pages 1329–1338, 2016.
  * Greensmith et al. [2004] Evan Greensmith, Peter L Bartlett, and Jonathan Baxter.  Variance reduction techniques for gradient estimates in reinforcement learning.  Journal of Machine Learning Research (JMLR), 5(Nov):1471–1530, 2004\.
  * Han et al. [2020] Minghao Han, Lixian Tian, Yuanand Zhang, Jun Wang, and Wei Pan.  Reinforcement learning control of constrained dynamic systems with uniformly ultimate boundedness stability guarantee.  arXiv preprint arXiv:2011.06882, 2020.
  * Hunter and Lange [2004] David R Hunter and Kenneth Lange.  A tutorial on mm algorithms.  The American Statistician, 58(1):30–37, 2004.
  * Kakade and Langford [2002] Sham Kakade and John Langford.  Approximately optimal approximate reinforcement learning.  In Proceedings of International Conference on Machine Learning (ICML), volume 2, pages 267–274, 2002.
  * Kang et al. [2021] Bingyi Kang, Shie Mannor, and Jiashi Feng.  Learning safe policies with cost-sensitive advantage estimation, 2021\.  https://openreview.net/forum?id=uVnhiRaW3J.
  * Le et al. [2019] Hoang Le, Cameron Voloshin, and Yisong Yue.  Batch policy learning under constraints.  In International Conference on Machine Learning (ICML), pages 3703–3712, 2019.
  * Li and Belta [2019] Xiao Li and Calin Belta.  Temporal logic guided safe reinforcement learning using control barrier functions.  arXiv preprint arXiv:1903.09885, 2019.
  * Liang et al. [2018] Qingkai Liang, Fanyu Que, and Eytan Modiano.  Accelerated primal-dual policy optimization for safe reinforcement learning.  arXiv preprint arXiv:1802.06480, 2018.
  * Liu et al. [2020] Yongshuai Liu, Jiaxin Ding, and Xin Liu.  Ipo: Interior-point policy optimization under constraints.  Proceedings of the AAAI Conference on Artificial Intelligence, 34(04), 2020.
  * Mnih et al. [2015] Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Marc G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al.  Human-level control through deep reinforcement learning.  Nature, 518(7540):529, 2015.
  * OpenAI [2019] OpenAI.  Openai five defeats dota 2 world champions, 2019.  https://openai.com/blog/openai-five-defeats-dota-2-world-champions/.
  * Paternain et al. [2019] Santiago Paternain, Luiz FO Chamon, Miguel Calvo-Fullana, and Alejandro Ribeiro.  Constrained reinforcement learning has zero duality gap.  In Advances in Neural Information Processing Systems (NeurIPS), 2019\.
  * Peters and Schaal [2008] Jan. Peters and Stefan. Schaal.  Reinforcement learning of motor skills with policy gradients.  Neural Netw, 21(4):682–697, 2008.
  * Pirotta et al. [2013] M. Pirotta, M. Restelli, A. Pecorino, and D. Calandriello.  Safe policy iteration.  In International Conference on Machine Learning (ICML), pages 307–315, 2013.
  * Puterman [2014] Martin L Puterman.  Markov decision processes: discrete stochastic dynamic programming.  John Wiley & Sons, 2014.
  * Ray et al. [2019] Alex Ray, Joshua Achiam, and Dario Amodei.  Benchmarking Safe Exploration in Deep Reinforcement Learning.  2019\.
  * Russel et al. [2020] Reazul Hasan Russel, Mouhacine Benosman, and Jeroen Van Baar.  Robust constrained-mdps: Soft-constrained robust policy optimization under model uncertainty.  arXiv preprint arXiv:2010.04870, 2020.
  * Satija et al. [2020] Harsh Satija, Philip Amortila, and Joelle Pineau.  Constrained markov decision processes via backward value functions.  In International Conference on Machine Learning (ICML), pages 8502–8511, 2020.
  * 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 (ICML), pages 1889–1897, 2015.
  * Schulman et al. [2016] John Schulman, Philipp Moritz, Sergey Levine, Michael Jordan, and Pieter Abbeel.  High-dimensional continuous control using generalized advantage estimation.  International Conference on Learning Representations (ICLR), 2016\.
  * 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, 2017.
  * Süli and Mayers [2003] Endre Süli and David F Mayers.  An introduction to numerical analysis.  Cambridge university press, 2003.
  * Sutton and Barto [1998] Richard S Sutton and Andrew G Barto.  Reinforcement learning: An introduction.  MIT press, 1998.
  * Sutton et al. [2000] Richard S Sutton, David A McAllester, Satinder P Singh, and Yishay Mansour.  Policy gradient methods for reinforcement learning with function approximation.  In Advances in Neural Information Processing Systems (NeurIPS), pages 1057–1063, 2000.
  * Tessler et al. [2019] Chen Tessler, Daniel J Mankowitz, and Shie Mannor.  Reward constrained policy optimization.  International Conference on Learning Representation (ICLR), 2019\.
  * Todorov et al. [2012] Emanuel Todorov, Tom Erez, and Yuval Tassa.  Mujoco: A physics engine for model-based control.  In 2012 IEEE/RSJ International Conference on Intelligent Robots and Systems, pages 5026–5033. IEEE, 2012.
  * Vuong et al. [2019] Quan Vuong, Yiming Zhang, and Keith W Ross.  Supervised policy update for deep reinforcement learning.  In International Conference on Learning Representation (ICLR), 2019\.
  * Watkins [1989] Christopher John Cornish Hellaby Watkins.  Learning from delayed rewards.  1989\.
  * Williams [1992] Ronald J Williams.  Simple statistical gradient-following algorithms for connectionist reinforcement learning.  Machine learning, 8(3-4):229–256, 1992.
  * Wu et al. [2018] Cathy Wu, Aravind Rajeswaran, Yan Duan, Vikash Kumar, Alexandre M Bayen, Sham Kakade, Igor Mordatch, and Pieter Abbeel.  Variance reduction for policy gradient with action-dependent factorized baselines.  International Conference on Learning Representation (ICLR), 2018\.
  * Yang et al. [2018] Long Yang, Minhao Shi, Qian Zheng, Wenjia Meng, and Gang Pan.  A unified approach for multi-step temporal-difference learning with eligibility traces in reinforcement learning.  In Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, IJCAI-18, pages 2984–2990, 2018.
  * Yang et al. [2020] Tsung-Yen Yang, Justinian Rosca, Karthik Narasimhan, and Peter J Ramadge.  Projection-based constrained policy optimization.  In International Conference on Learning Representation (ICLR), 2020\.
  * Yang et al. [2021a] Long Yang, Gang Zheng, Yu Zhang, Qian Zheng, Pengfei Li, and Gang Pan.  On convergence of gradient expected sarsa ($\lambda$).  In AAAI, 2021.
  * Yang et al. [2021b] Long Yang, Qian Zheng, and Gang Pan.  Sample complexity of policy gradient finding second-order stationary points.  In AAAI, 2021.
  * Yang et al. [2022] Long Yang, Gang Zheng, Haotian Zhang, Yu Zhang, Qian Zheng, and Gang Pan.  Policy optimization with stochastic mirror descent.  Association for the Advancement of Artificial Intelligence (AAAI), 2022.
  * Zhang et al. [2020] Yiming Zhang, Quan Vuong, and Keith Ross.  First order constrained optimization in policy space.  In Advances in Neural Information Processing Systems (NeurIPS), volume 33, 2020.

## Checklist

The checklist follows the references. Please read the checklist guidelines
carefully for information on how to answer these questions. For each question,
change the default [TODO] to [Yes] , [No] , or [N/A] . You are strongly
encouraged to include a justification to your answer, either by referencing
the appropriate section of your paper or providing a brief inline description.
For example:

  * •

Did you include the license to the code and datasets? [Yes] See Section
LABEL:gen_inst.

  * •

Did you include the license to the code and datasets? [No] The code and the
data are proprietary.

  * •

Did you include the license to the code and datasets? [N/A]

Please do not modify the questions and only use the provided macros for your
answers. Note that the Checklist section does not count towards the page
limit. In your paper, please delete this instructions block and only keep the
Checklist section heading above along with the questions/answers below.

  1. 1.

For all authors…

    1. (a)

Do the main claims made in the abstract and introduction accurately reflect
the paper’s contributions and scope? [Yes] See Abstract and Section 1.

    2. (b)

Did you describe the limitations of your work? [No]

    3. (c)

Did you discuss any potential negative societal impacts of your work? [No]

    4. (d)

Have you read the ethics review guidelines and ensured that your paper
conforms to them? [Yes] We ensure our paper to conform to the ethics review
guidelines.

  2. 2.

If you are including theoretical results…

    1. (a)

Did you state the full set of assumptions of all theoretical results? [Yes]
See Section 3 and Section 4.

    2. (b)

Did you include complete proofs of all theoretical results? [Yes] See Appendix
E and Appendix G.

  3. 3.

If you ran experiments…

    1. (a)

Did you include the code, data, and instructions needed to reproduce the main
experimental results (either in the supplemental material or as a URL)? [Yes]
See the URL in the supplementary material for the code, and see H for
environments of experiments.

    2. (b)

Did you specify all the training details (e.g., data splits, hyperparameters,
how they were chosen)? [Yes] See Appendix H

    3. (c)

Did you report error bars (e.g., with respect to the random seed after running
experiments multiple times)? [Yes] See Appendix H

    4. (d)

Did you include the total amount of compute and the type of resources used
(e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] See Appendix
H

  4. 4.

If you are using existing assets (e.g., code, data, models) or
curating/releasing new assets…

    1. (a)

If your work uses existing assets, did you cite the creators? [Yes]

    2. (b)

Did you mention the license of the assets? [Yes]

    3. (c)

Did you include any new assets either in the supplemental material or as a
URL? [Yes] We provide the code for our implementation of CUP in the
supplemental material.

    4. (d)

Did you discuss whether and how consent was obtained from people whose data
you’re using/curating? [Yes] We use open source safe reinforcement learning
environments, see Appendix H.2

    5. (e)

Did you discuss whether the data you are using/curating contains personally
identifiable information or offensive content? [Yes] Our data does not contain
any personally identifiable information or offensive content.

  5. 5.

If you used crowdsourcing or conducted research with human subjects…

    1. (a)

Did you include the full text of instructions given to participants and
screenshots, if applicable? [N/A]

    2. (b)

Did you describe any potential participant risks, with links to Institutional
Review Board (IRB) approvals, if applicable? [N/A]

    3. (c)

Did you include the estimated hourly wage paid to participants and the total
amount spent on participant compensation? [N/A]

##  Appendix A Notations

###  A.1 Matrix Index

In this paper, we use a bold capital letter to denote matrix, e.g.,
$\mathbf{A}=(a_{i,j})\in\mathbb{R}^{m\times n}$, and its $(i,j)$-th element
denoted as

$\mathbf{A}[i,j]=:a_{i,j},$

where $1\leq i\leq m,1\leq j\leq n$. Similarly, a bold lowercase letter
denotes a vector, e.g.,
$\mathbf{a}=(a_{1},a_{2},\cdots,a_{n})\in\mathbb{R}^{n}$, and its $i$-th
element denoted as

$\mathbf{a}[i]=:a_{i},$

where $1\leq i\leq n$.

###  A.2 Key Notations of Reinforcement Learning

For convenience of reference, we list key notations that have be used in this
paper.

####  A.2.1 Value Function and Dynamic System of MDP.

$\mathbf{r}_{\pi_{\bm{\theta}}},~{}R_{\pi_{\bm{\theta}}}(s),$ | : |  $\mathbf{r}_{\pi_{\bm{\theta}}}\in\mathbb{R}^{|\mathcal{S}|}$ is the expected vector reward according to $\pi_{\bm{\theta}}$, i.e., their components are: $\mathbf{r}_{\pi_{\bm{\theta}}}[s]=\sum_{a\in\mathcal{A}}\sum_{s^{{}^{\prime}}\in\mathcal{S}}\pi_{\bm{\theta}}(a|s)r(s^{\prime}|s,a)=:R_{\pi_{\bm{\theta}}}(s),~{}s\in\mathcal{S}.$
---|---|---
$\mathbf{v}_{\pi_{\bm{\theta}}},~{}V_{\pi_{\bm{\theta}}}(s),$ | : |  $\mathbf{v}_{\pi_{\bm{\theta}}}\in\mathbb{R}^{|\mathcal{S}|}$ is the vector that stores all the state value functions, and its components are: $\mathbf{v}_{\pi_{\bm{\theta}}}[s]=V_{\pi_{\bm{\theta}}}(s),~{}s\in\mathcal{S}.$
$\rho(\cdot),\bm{\rho}$ | : |  $\rho(s)$: the initial state distribution of state $s$; $\bm{\rho}\in\mathbb{R}^{|\mathcal{S}|}$, and $\bm{\rho}[s]=\rho(s)$.
$\mathbf{P}_{\pi_{\bm{\theta}}}$ | : |  Single-step state transition matrix by executing $\pi_{\bm{\theta}}$.
$\mathbb{P}_{\pi_{\bm{\theta}}}(s^{{}^{\prime}}|s)$ | : |  Single-step state transition probability from $s$ to $s^{{}^{\prime}}$ by executing $\pi_{\bm{\theta}}$, and it is the $(s,s^{{}^{\prime}})$-th component of the matrix $\mathbf{P}_{\pi_{\bm{\theta}}}$, i.e., $\mathbf{P}_{\pi_{\bm{\theta}}}[s,s^{{}^{\prime}}]=\mathbb{P}_{\pi_{\bm{\theta}}}(s^{{}^{\prime}}|s)$.
$\mathbb{P}_{\pi_{\bm{\theta}}}(s_{t}=s^{{}^{\prime}}|s)$ | : |  The probability of visiting the state $s^{{}^{\prime}}$ after $t$ time steps from the state $s$ by executing $\pi_{\bm{\theta}}$, and it is the $(s,s^{{}^{\prime}})$-th component of the matrix $\mathbf{P}_{\pi_{\bm{\theta}}}$, i.e., $\mathbf{P}^{t}_{\pi_{\bm{\theta}}}[s,s^{{}^{\prime}}]=\mathbb{P}_{\pi_{\bm{\theta}}}(s_{t}=s^{{}^{\prime}}|s)$.
$d_{\pi_{\bm{\theta}}}^{s_{0}}(s),~{}d_{\pi_{\bm{\theta}}}^{\rho_{0}}(s)$ | : |  The normalized discounted distribution of the future state $s$ encountered starting at $s_{0}$ by executing $\pi_{\bm{\theta}}$: $d_{\pi_{\bm{\theta}}}^{s_{0}}(s)=:(1-\gamma)\sum_{t=0}^{\infty}\gamma^{t}\mathbb{P}_{\pi_{\bm{\theta}}}(s_{t}=s|s_{0}).$ Since $s_{0}\sim\rho(\cdot)$, we define $d_{\pi_{\bm{\theta}}}^{\rho_{0}}(s)=:\mathbb{E}_{s_{0}\sim\rho(\cdot)}[d_{\pi_{\bm{\theta}}}^{s_{0}}(s)]$.
$\mathbf{d}_{\pi_{\bm{\theta}}}^{\rho_{0}}$ | : |  It stores all the normalized discounted state distributions $d_{\pi_{\bm{\theta}}}^{\rho_{0}}(s)$, $\in\mathcal{S}$, i.e., $\mathbf{d}_{\pi_{\bm{\theta}}}^{\rho_{0}}\in\mathbb{R}^{|\mathcal{S}|}$, and its components are: $\mathbf{d}_{\pi_{\bm{\theta}}}^{\rho_{0}}[s]=d_{\pi_{\bm{\theta}}}^{\rho_{0}}(s).$

####  A.2.2 Extend them to $\lambda$-version.

$\mathbf{P}^{(\lambda)}_{\pi_{\bm{\theta}}}$ | : |  $\mathbf{P}^{(\lambda)}_{\pi_{\bm{\theta}}}=(1-\gamma\lambda)\sum_{{t}=0}^{\infty}(\gamma\lambda)^{{t}}\mathbf{P}^{{t}+1}_{\pi_{\bm{\theta}}}.$
---|---|---
$\mathbb{P}_{\pi_{\bm{\theta}}}^{(\lambda)}(s^{{}^{\prime}}|s)$ | : |  $\mathbb{P}_{\pi_{\bm{\theta}}}^{(\lambda)}(s^{{}^{\prime}}|s)=:\mathbf{P}^{(\lambda)}_{\pi_{\bm{\theta}}}[s,s^{{}^{\prime}}]=(1-\gamma\lambda)\sum_{{t}=0}^{\infty}(\gamma\lambda)^{{t}}\mathbb{P}_{\pi_{\bm{\theta}}}(s_{t+1}=s^{{}^{\prime}}|s)$.
$\mathbf{r}^{(\lambda)}_{\pi_{\bm{\theta}}},~{}R^{(\lambda)}_{\pi_{\bm{\theta}}}(s)$ | : |  $\mathbf{r}^{(\lambda)}_{\pi_{\bm{\theta}}}=\sum_{{t}=0}^{\infty}(\gamma\lambda\mathbf{P}_{\pi_{\bm{\theta}}})^{{t}}\mathbf{r}_{\pi_{\bm{\theta}}};~{}R^{(\lambda)}_{\pi_{\bm{\theta}}}(s)=:\mathbf{r}^{(\lambda)}_{\pi_{\bm{\theta}}}[s].$
$\tilde{\gamma}$ | : |  $\tilde{\gamma}=\dfrac{\gamma(1-\lambda)}{1-\gamma\lambda}$.
$d_{\pi_{\bm{\theta}}}^{s_{0},\lambda}(s)$ | : |  $d_{\pi_{\bm{\theta}}}^{s_{0},\lambda}(s)=(1-\tilde{\gamma})\sum_{t=0}^{\infty}\tilde{\gamma}^{t}\mathbb{P}^{(\lambda)}_{\pi_{\bm{\theta}}}(s_{t}=s|s_{0})$.
$d_{\pi_{\bm{\theta}}}^{\lambda}(s),~{}\mathbf{d}_{\pi_{\bm{\theta}}}^{\lambda}$ | : |  $d_{\pi_{\bm{\theta}}}^{\lambda}(s)=\mathbb{E}_{s_{0}\sim\rho_{0}(\cdot)}\left[d_{\pi_{\bm{\theta}}}^{s_{0},\lambda}(s)\right],~{}\mathbf{d}_{\pi_{\bm{\theta}}}^{\lambda}[s]=d_{\pi_{\bm{\theta}}}^{\lambda}(s)$.

####  A.2.3  TD error w.r.t. any function $\varphi(\cdot)$.

$\delta_{t}^{\varphi}$ | : |  $\delta_{t}^{\varphi}=r(s_{t+1}|s_{t},a_{t})+\gamma\varphi(s_{t+1})-\varphi(s_{t}).$
---|---|---
$\delta^{\varphi}_{\pi_{\bm{\theta}},t}(s)$ | : |  $\delta^{\varphi}_{\pi_{\bm{\theta}},t}(s)=\mathbb{E}_{s_{t}\sim\mathbb{P}_{\pi_{\bm{\theta}}}(\cdot|s),a_{t}\sim{\pi_{\bm{\theta}}}(\cdot|s_{t}),s_{t+1}\sim\mathbb{P}(\cdot|s_{t},a_{t})}\left[\delta_{t}^{\varphi}\right]$.
$\bm{\delta}^{\varphi}_{\pi_{\bm{\theta}},t}$ | : |  $\bm{\delta}^{\varphi}_{\pi_{\bm{\theta}},t}[s]={{\delta}}^{\varphi}_{\pi_{\bm{\theta}},t}(s).$
$\Delta_{t}^{\varphi}(\pi_{\bm{\theta}},\pi_{{\bm{\theta}}^{{}^{\prime}}},s)$ | : |  $\mathbb{E}_{s_{t}\sim\mathbb{P}_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}(\cdot|s),a_{t}\sim{\pi_{{\bm{\theta}}^{{}^{\prime}}}}(\cdot|s_{t}),s_{t+1}\sim\mathbb{P}(\cdot|s_{t},a_{t})}\left[\left(\dfrac{\pi_{\bm{\theta}}(a_{t}|s_{t})}{\pi_{{\bm{\theta}}^{{}^{\prime}}}(a_{t}|s_{t})}-1\right)\delta_{t}^{\varphi}\right]$.
$\bm{\Delta}_{t}^{\varphi}(\pi_{\bm{\theta}},\pi_{{\bm{\theta}}^{{}^{\prime}}})$ | : |  $\bm{\Delta}_{t}^{\varphi}(\pi_{\bm{\theta}},\pi_{{\bm{\theta}}^{{}^{\prime}}})[s]=\Delta_{t}^{\varphi}(\pi_{\bm{\theta}},\pi_{{\bm{\theta}}^{{}^{\prime}}},s)$.

##  Appendix B Additional Discussion about Related Work

This section reviews three typical safe reinforcement learning algorithms: CPO
[Achiam et al., 2017], PCPO [Yang et al., 2020] and FOCOPS [Zhang et al.,
2020]. Those algorithms also use new surrogate functions to replace the
objective and constraints, which resembles the proposed CUP algorithm. The
goal is to present the contribution of our work.

###  B.1 CPO [Achiam et al., 2017]

For a given policy $\pi_{{\bm{\theta}}_{k}}$, CPO updates new policy
$\pi_{{\bm{\theta}}_{k+1}}$ as follows:

$\displaystyle\pi_{{\bm{\theta}}_{k+1}}=\arg\max_{\pi_{{\bm{\theta}}}\in\Pi_{{\bm{\theta}}}}~{}~{}~{}~{}\mathbb{E}_{s\sim
d^{\rho_{0}}_{\pi_{{\bm{\theta}}_{k}}}(\cdot),a\sim\pi_{{\bm{\theta}}}(\cdot|s)}\left[A_{\pi_{{\bm{\theta}}_{k}}}(s,a)\right]$
(24)
$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}\text{s.t.}~{}~{}J^{c}(\pi_{{\bm{\theta}}_{k}})+\frac{1}{1-\gamma}\mathbb{E}_{s\sim
d^{\rho_{0}}_{\pi_{{\bm{\theta}}_{k}}}(\cdot),a\sim\pi_{{\bm{\theta}}}(\cdot|s)}\left[A^{c}_{\pi_{{\bm{\theta}}_{k}}}(s,a)\right]\leq
b,$ (25)
$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}\bar{D}_{\mathrm{KL}}(\pi_{{\bm{\theta}}},\pi_{{\bm{\theta}}_{k}})=\mathbb{E}_{s\sim
d^{\rho_{0}}_{\pi_{{\bm{\theta}}_{k}}}(\cdot)}[\mathrm{KL}(\pi_{{\bm{\theta}}},\pi_{{\bm{\theta}}_{k}})[s]]\leq\delta.$
(26)

It is impractical to solve the problem (24) directly due to the computational
cost. [Achiam et al., 2017] suggest to find some convex approximations to
replace the term $A_{\pi_{{\bm{\theta}}_{k}}}(s,a)$ and
$\bar{D}_{\mathrm{KL}}(\pi_{{\bm{\theta}}},\pi_{{\bm{\theta}}_{k}})$
Eq.(24)-(26).

Concretely, according to (5), Achiam et al. [2017] suggest to use first-order
Taylor expansion of $J(\pi_{\bm{\theta}})$ to replace the objective (24) as
follows,

$\displaystyle\frac{1}{1-\gamma}\mathbb{E}_{s\sim
d_{\pi_{{\bm{\theta}}_{k}}}^{\rho_{0}}(\cdot),a\sim\pi_{{\bm{\theta}}_{k}}(\cdot|s)}\left[\dfrac{\pi_{{\bm{\theta}}}(a|s)}{\pi_{{\bm{\theta}}_{k}}(a|s)}A_{\pi_{{\bm{\theta}}_{k}}}(s,a)\right]=J(\pi_{{\bm{\theta}}})-J(\pi_{{\bm{\theta}}_{k}})\approx({\bm{\theta}}-{\bm{\theta}}_{k})^{\top}\nabla_{{\bm{\theta}}}J(\pi_{\bm{\theta}}).$

Similarly, Achiam et al. [2017] use the following approximations to turn the
constrained policy optimization (24)-(26) to be a convex problem,

$\displaystyle\frac{1}{1-\gamma}\mathbb{E}_{s\sim
d_{\pi_{{\bm{\theta}}_{k}}}^{\rho_{0}}(\cdot),a\sim\pi_{{\bm{\theta}}_{k}}(\cdot|s)}$
$\displaystyle\left[\frac{\pi_{{\bm{\theta}}}(a|s)}{\pi_{{\bm{\theta}}_{k}}(a|s)}A^{c}_{\pi_{{\bm{\theta}}_{k}}}(s,a)\right]\approx({\bm{\theta}}-{\bm{\theta}}_{k})^{\top}\nabla_{{\bm{\theta}}}J^{c}(\pi_{\bm{\theta}}),$
(27)
$\displaystyle\bar{D}_{\mathrm{KL}}(\pi_{{\bm{\theta}}},\pi_{{\bm{\theta}}_{k}})$
$\displaystyle\approx({\bm{\theta}}-{\bm{\theta}}_{k})^{\top}\mathbf{H}({\bm{\theta}}-{\bm{\theta}}_{k}),$
(28)

where $\mathbf{H}$ is Hessian matrix of
$\bar{D}_{\mathrm{KL}}(\pi_{{\bm{\theta}}},\pi_{{\bm{\theta}}_{k}})$, i.e.,

$\mathbf{H}[i,j]=:\dfrac{\partial^{2}}{\partial{\bm{\theta}}_{i}\partial{\bm{\theta}}_{j}}\mathbb{E}_{s\sim
d^{\rho_{0}}_{\pi_{{\bm{\theta}}_{k}}}(\cdot)}\left[\mathrm{KL}(\pi_{{\bm{\theta}}},\pi_{{\bm{\theta}}_{k}})[s]\right],$

Eq.(28) is the second-oder approximation of (26).

Let $\lambda_{\star},\nu_{\star}$ is the dual solution of the following
problem

$\lambda_{\star},\nu_{\star}=\arg\max_{\lambda\geq 0,\nu\geq
0}\left\\{\dfrac{-1}{2\lambda}\left(\mathbf{g}^{\top}\mathbf{H}^{-1}\mathbf{g}-2\nu
r+sv^{2}\right)+\nu c-\dfrac{\lambda\delta}{2}\right\\};$

where $\mathbf{g}=\nabla_{\bm{\theta}}\mathbb{E}_{s\sim
d^{\rho_{0}}_{\pi_{{\bm{\theta}}_{k}}}(\cdot),a\sim\pi_{{\bm{\theta}}}(\cdot|s)}\left[A_{\pi_{{\bm{\theta}}_{k}}}(s,a)\right]$,
$\mathbf{a}=\nabla_{\bm{\theta}}\mathbb{E}_{s\sim
d^{\rho_{0}}_{\pi_{{\bm{\theta}}_{k}}}(\cdot),a\sim\pi_{{\bm{\theta}}}(\cdot|s)}\left[A^{c}_{\pi_{{\bm{\theta}}_{k}}}(s,a)\right]$,
$r=\mathbf{g}^{\top}\mathbf{H}\mathbf{a},s=\mathbf{a}^{\top}\mathbf{H}^{-1}\mathbf{a}$,
and $c=J^{c}(\pi_{\bm{\theta}_{k}})-b$.

Finally, CPO updates parameters according to conjugate gradient as follows: if
approximation to CPO is feasible:

$\displaystyle\bm{\theta}_{k+1}=\bm{\theta}_{k}+\frac{1}{\lambda_{\star}}\mathbf{H}^{-1}(\mathbf{g}-\nu_{\star}\mathbf{a}),$

else,

$\bm{\theta}_{k+1}=\bm{\theta}_{k}-\sqrt{\dfrac{2\delta}{\mathbf{a}^{\top}\mathbf{H}^{-1}\mathbf{a}}}\mathbf{H}^{-1}\mathbf{a}.$

###  B.2 PCPO [Yang et al., 2020]

Projection-Based Constrained Policy Optimization (PCPO) is an iterative method
for optimizing policies in a two-step process: the first step performs a local
reward improvement update, while the second step reconciles any constraint
violation by projecting the policy back onto the constraint set.

Reward Improvement:

$\displaystyle\pi_{\bm{\theta}_{k+\frac{1}{2}}}=\arg\max_{\pi_{{\bm{\theta}}}\in\Pi_{{\bm{\theta}}}}\mathbb{E}_{s\sim
d^{\rho_{0}}_{\pi_{{\bm{\theta}}_{k}}}(\cdot),a\sim\pi_{{\bm{\theta}}}(\cdot|s)}\left[A_{\pi_{{\bm{\theta}}_{k}}}(s,a)\right],$
$\displaystyle\text{
s.t.}\bar{D}_{\mathrm{KL}}(\pi_{{\bm{\theta}}},\pi_{{\bm{\theta}}_{k}})=\mathbb{E}_{s\sim
d^{\rho_{0}}_{\pi_{{\bm{\theta}}_{k}}}(\cdot)}[\mathrm{KL}(\pi_{{\bm{\theta}}},\pi_{{\bm{\theta}}_{k}})[s]]\leq\delta;$

Projection:

$\displaystyle\pi_{{\bm{\theta}}_{k+1}}=\arg\min_{\pi_{{\bm{\theta}}}\in\Pi_{{\bm{\theta}}}}~{}D\left(\pi_{{\bm{\theta}}},\pi_{{\bm{\theta}}_{k+\frac{1}{2}}}\right),$
$\displaystyle\text{s.t.}~{}J^{c}(\pi_{{\bm{\theta}}_{k}})$
$\displaystyle+\dfrac{1}{1-\gamma}\mathbb{E}_{s\sim
d^{\rho_{0}}_{\pi_{{\bm{\theta}}_{k}}}(\cdot),a\sim\pi_{{\bm{\theta}}}(\cdot|s)}\left[A^{c}_{\pi_{{\bm{\theta}}_{k}}}(s,a)\right]\leq
b.$

Then, Yang et al. [2020] follows CPO [Achiam et al., 2017] uses convex
approximation to original problem, and calculate the update rule as follows,

$\bm{\theta}_{k+1}=\bm{\theta}_{k}-\sqrt{\dfrac{2\delta}{\mathbf{g}^{\top}\mathbf{H}^{-1}\mathbf{g}}}\mathbf{H}^{-1}\mathbf{g}-\max\left(0,\dfrac{\sqrt{\dfrac{2\delta}{\mathbf{g}^{\top}\mathbf{H}^{-1}\mathbf{g}}}\mathbf{a}^{\top}\mathbf{H}^{-1}\mathbf{g}+c}{\mathbf{a}^{\top}\mathbf{L}^{-1}\mathbf{a}}\right)\mathbf{L}^{-1}\mathbf{a},$

where $\mathbf{L}=\mathbf{I}$ if $D$ is $\ell_{2}$-norm, and
$\mathbf{L}=\mathbf{H}$ if $D$ is KL-divergence.

###  B.3 FOCOPS [Zhang et al., 2020]

Zhang et al. [2020] propose the First Order Constrained Optimization in Policy
Space (FOCOPS) that is a two-step approach. We present it as follows.

Step1: Finding the optimal update policy. Firstly, for a given policy
$\pi_{\bm{\theta}k}$, we find an optimal update policy $\pi^{\star}$ by
solving the optimization problem (24)-(26) in the non-parameterized policy
space.

$\displaystyle\pi^{\star}=\arg\max_{\pi\in\Pi}~{}~{}~{}~{}\mathbb{E}_{s\sim
d^{\rho_{0}}_{\pi_{{\bm{\theta}}_{k}}}(\cdot),a\sim\pi(\cdot|s)}\left[A_{\pi_{{\bm{\theta}}_{k}}}(s,a)\right]$
(29)
$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}\text{s.t.}~{}~{}J^{c}(\pi_{{\bm{\theta}}_{k}})+\frac{1}{1-\gamma}\mathbb{E}_{s\sim
d^{\rho_{0}}_{\pi_{{\bm{\theta}}_{k}}}(\cdot),a\sim\pi(\cdot|s)}\left[A^{c}_{\pi_{{\bm{\theta}}_{k}}}(s,a)\right]\leq
b,$ (30)
$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}\bar{D}_{\mathrm{KL}}(\pi_{{\bm{\theta}}},\pi_{{\bm{\theta}}_{k}})=\mathbb{E}_{s\sim
d^{\rho_{0}}_{\pi_{{\bm{\theta}}_{k}}}(\cdot)}[\mathrm{KL}(\pi,\pi_{{\bm{\theta}}_{k}})[s]]\leq\delta.$
(31)

If $\pi_{\bm{\theta}_{k}}$ is feasible, then the optimal policy for (29)-(31)
takes the following form:

$\displaystyle\pi^{\star}(a|s)=\dfrac{\pi_{\bm{\theta}_{k}}(a|s)}{Z_{\lambda,\nu}(s)}\exp\left(\dfrac{1}{\lambda}\left(A_{\pi_{\bm{\theta}_{k}}}(s,a)-\nu
A^{c}_{\pi_{\bm{\theta}_{k}}}(s,a)\right)\right),$ (32)

where $Z_{\lambda,\nu}(s)$ is the partition function which ensures (32) is a
valid probability distribution, $\lambda$ and $\nu$ are solutions to the
optimization problem:

$\min_{\lambda,\nu\geq 0}\lambda\nu+\nu\tilde{b}+\lambda\mathbb{E}_{s\sim
d^{\rho_{0}}_{\pi_{{\bm{\theta}}_{k}}}(\cdot),a\sim\pi^{\star}(\cdot|s)}\left[Z_{\lambda,\nu}(s)\right],$

the term $\tilde{b}=(1-\gamma)(b-J^{c}(\pi_{\bm{\theta}_{k}}))$.

Step 2: Projection Then, we project the policy found in the previous step back
into the parameterized policy space $\Pi_{\bm{\theta}}$ by solving for the
closest policy $\pi_{\bm{\theta}}\in\Pi_{\bm{\theta}}$ to $\pi^{\star}$ in
order to obtain $\pi_{\bm{\theta}_{k+1}}$:

$\bm{\theta}_{k+1}=\arg\min_{\bm{\theta}}\mathbb{E}_{s\sim
d^{\rho_{0}}_{\pi_{{\bm{\theta}}_{k}}}(\cdot)}[\mathrm{KL}(\pi_{{\bm{\theta}}},\pi^{\star})[s]].$

Table 2: Comparison of some safe reinforcement algorithms. Algorithm |  Optimization problem |  Implementation |  Remark
---|---|---|---
CPO [Achiam et al., 2017] |  $\pi_{\bm{\theta}_{k+1}}=\arg\max_{\pi_{{\bm{\theta}}}\in\Pi_{{\bm{\theta}}}}\mathbb{E}_{s\sim d^{\rho_{0}}_{\pi_{{\bm{\theta}}_{k}}}(\cdot),a\sim\pi_{{\bm{\theta}}}(\cdot|s)}\left[A_{\pi_{{\bm{\theta}}_{k}}}(s,a)\right]$,
s.t. $J^{c}(\pi_{{\bm{\theta}}_{k}})+\mathbb{E}_{s\sim
d^{\rho_{0}}_{\pi_{{\bm{\theta}}_{k}}}(\cdot),a\sim\pi_{{\bm{\theta}}}(\cdot|s)}\left[A^{c}_{\pi_{{\bm{\theta}}_{k}}}(s,a)\right]\leq
b$,
$\bar{D}_{\mathrm{KL}}(\pi_{{\bm{\theta}}},\pi_{{\bm{\theta}}_{k}})=\mathbb{E}_{s\sim d^{\rho_{0}}_{\pi_{{\bm{\theta}}_{k}}}(\cdot)}[\mathrm{KL}(\pi_{{\bm{\theta}}},\pi_{{\bm{\theta}}_{k}})[s]]\leq\delta$. |  $\bm{\theta}_{k+1}=\arg\max_{\bm{\theta}}~{}\mathbf{g}^{\top}(\bm{\theta}-\bm{\theta}_{k})$,
s.t. $c+\mathbf{b}^{\top}(\bm{\theta}-\bm{\theta}_{k})\leq 0$,
$\dfrac{1}{2}(\bm{\theta}-\bm{\theta}_{k})^{\top}\mathbf{H}(\bm{\theta}-\bm{\theta}_{k})\leq\delta$. |  Convex Implementation
PCPO [Yang et al., 2020] |  Reward Improvement $\pi_{\bm{\theta}_{k+\frac{1}{2}}}=\arg\max_{\pi_{{\bm{\theta}}}\in\Pi_{{\bm{\theta}}}}\mathbb{E}_{s\sim d^{\rho_{0}}_{\pi_{{\bm{\theta}}_{k}}}(\cdot),a\sim\pi_{{\bm{\theta}}}(\cdot|s)}\left[A_{\pi_{{\bm{\theta}}_{k}}}(s,a)\right]$,
s.t.
$\bar{D}_{\mathrm{KL}}(\pi_{{\bm{\theta}}},\pi_{{\bm{\theta}}_{k}})=\mathbb{E}_{s\sim
d^{\rho_{0}}_{\pi_{{\bm{\theta}}_{k}}}(\cdot)}[\mathrm{KL}(\pi_{{\bm{\theta}}},\pi_{{\bm{\theta}}_{k}})[s]]\leq\delta$;
Projection
$\pi_{{\bm{\theta}}_{k+1}}=\arg\min_{\pi_{{\bm{\theta}}}\in\Pi_{{\bm{\theta}}}}~{}D\left(\pi_{{\bm{\theta}}},\pi_{{\bm{\theta}}_{k+\frac{1}{2}}}\right)$,
s.t. $J^{c}(\pi_{{\bm{\theta}}_{k}})+\dfrac{1}{1-\gamma}\mathbb{E}_{s\sim d^{\rho_{0}}_{\pi_{{\bm{\theta}}_{k}}}(\cdot),a\sim\pi_{{\bm{\theta}}}(\cdot|s)}\left[A^{c}_{\pi_{{\bm{\theta}}_{k}}}(s,a)\right]\leq b$. |  Reward Improvement
$\bm{\theta}_{k+\frac{1}{2}}=\arg\max_{\bm{\theta}}~{}\mathbf{g}^{\top}(\bm{\theta}-\bm{\theta}_{k})$,
s.t.$\dfrac{1}{2}(\bm{\theta}-\bm{\theta}_{k})^{\top}\mathbf{H}(\bm{\theta}-\bm{\theta}_{k})\leq\delta$;
Projection
${{\bm{\theta}}_{k+1}}=\arg\min_{\bm{\theta}}\dfrac{1}{2}(\bm{\theta}-\bm{\theta}_{k})^{\top}\mathbf{L}(\bm{\theta}-\bm{\theta}_{k})$,
s.t. $c+\mathbf{b}^{\top}(\bm{\theta}-\bm{\theta}_{k})\leq 0$. |  Convex Implementation
FOCOPS [Zhang et al., 2020] |  Optimal update policy
$\pi^{\star}=\arg\max_{\pi\in\Pi}\mathbb{E}_{s\sim
d^{\rho_{0}}_{\pi_{{\bm{\theta}}_{k}}}(\cdot),a\sim\pi(\cdot|s)}\left[A_{\pi_{{\bm{\theta}}_{k}}}(s,a)\right]$,
s.t. $J^{c}(\pi_{{\bm{\theta}}_{k}})+\mathbb{E}_{s\sim
d^{\rho_{0}}_{\pi_{{\bm{\theta}}_{k}}}(\cdot),a\sim\pi(\cdot|s)}\left[A^{c}_{\pi_{{\bm{\theta}}_{k}}}(s,a)\right]\leq
b$,
$\bar{D}_{\mathrm{KL}}(\pi_{{\bm{\theta}}},\pi_{{\bm{\theta}}_{k}})=\mathbb{E}_{s\sim
d^{\rho_{0}}_{\pi_{{\bm{\theta}}_{k}}}(\cdot)}[\mathrm{KL}(\pi,\pi_{{\bm{\theta}}_{k}})[s]]\leq\delta$;
Projection
$\pi_{{\bm{\theta}}_{k+1}}=\arg\min_{\pi_{{\bm{\theta}}}\in\Pi_{{\bm{\theta}}}}~{}\mathbb{E}_{s\sim d^{\rho_{0}}_{\pi_{{\bm{\theta}}_{k}}}(\cdot)}[\mathrm{KL}(\pi_{{\bm{\theta}}},\pi^{\star})[s]]$. |  Optimal update policy

$\pi^{\star}(a|s)=\frac{\pi_{\bm{\theta}_{k}}(a|s)}{Z_{\lambda,\nu}(s)}\exp\left(\frac{1}{\lambda}\left(A_{\pi_{\bm{\theta}_{k}}}(s,a)-\nu
A^{c}_{\pi_{\bm{\theta}_{k}}}(s,a)\right)\right)$;

Projection
$\bm{\theta}_{k+1}=\arg\min_{\bm{\theta}}\mathbb{E}_{s\sim d^{\rho_{0}}_{\pi_{{\bm{\theta}}_{k}}}(\cdot)}[\mathrm{KL}(\pi_{{\bm{\theta}}},\pi^{\star})[s]].$ |  Non-Convex Implementation
CUP (Our Work) |  Policy Improvement $\displaystyle\pi_{{\bm{\theta}}_{k+\frac{1}{2}}}=\arg\max_{\pi_{{\bm{\theta}}}\in\Pi_{{\bm{\theta}}}}\bigg{\\{}\mathbb{E}_{s\sim{d}_{\pi_{\bm{\theta}_{k}}}^{\lambda}(\cdot),a\sim\pi_{\bm{\theta}}(\cdot|s)}\left[A^{\mathrm{GAE}(\gamma,\lambda)}_{{\pi_{\bm{\theta}_{k}}}}(s,a)\right]$ $\displaystyle-\alpha_{k}\sqrt{\mathbb{E}_{s\sim{d}_{{\pi_{\bm{\theta}_{k}}}}^{\lambda}(\cdot)}\left[\mathrm{KL}(\pi_{\bm{\theta}_{k}},\pi_{\bm{\theta}})[s]\right]}\bigg{\\}},$ Projection $\displaystyle\pi_{{\bm{\theta}}_{k+1}}=\arg\min_{\pi_{{\bm{\theta}}}\in\Pi_{{\bm{\theta}}}}~{}D\Big{(}\pi_{{\bm{\theta}}},\pi_{{\bm{\theta}}_{k+\frac{1}{2}}}\Big{)},~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}$ $\displaystyle\text{s.t.}J^{c}(\pi_{{\bm{\theta}}_{k}})+\dfrac{1}{1-\tilde{\gamma}}\mathbb{E}_{s\sim{d}_{\pi_{\bm{\theta}_{k}}}^{\lambda}(\cdot),a\sim\pi_{\bm{\theta}}(\cdot|s)}\left[A^{\mathrm{GAE}(\gamma,\lambda)}_{{\pi_{\bm{\theta}_{k}}},C}(s,a)\right]$ $\displaystyle+\beta_{k}\sqrt{\mathbb{E}_{s\sim{d}_{{\pi_{\bm{\theta}_{k}}}}^{\lambda}(\cdot)}\left[\mathrm{KL}(\pi_{\bm{\theta}_{k}},\pi_{\bm{\theta}})[s]\right]}\leq b.$ |  Policy Improvement
$\displaystyle{\bm{\theta}}_{k+\frac{1}{2}}=\arg\max_{{\bm{\theta}}}\Bigg{\\{}\frac{1}{T}\sum_{t=1}^{T}\frac{\pi_{\bm{\theta}}(a_{t}|s_{t})}{{\pi_{\bm{\theta}_{k}}}(a_{t}|s_{t})}\hat{A}_{t}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}$
$\displaystyle-\alpha\sqrt{\frac{1}{T}\sum_{t=1}^{T}\mathrm{KL}(\pi_{\bm{\theta}_{k}}(\cdot|s_{t}),\pi_{{\bm{\theta}}}(\cdot|s_{t}))}\Bigg{\\}};$
Projection
$\displaystyle{\bm{\theta}}_{k+1}=\arg\min_{{\bm{\theta}}}\dfrac{1}{T}\sum_{t=1}^{T}\bigg{\\{}\mathrm{KL}\left({\pi_{\bm{\theta}_{k+\frac{1}{2}}}}(\cdot|s_{t}),\pi_{{\bm{\theta}}}(\cdot|s_{t})\right)$ $\displaystyle+\nu_{k}\dfrac{1-\gamma\lambda}{1-\gamma}\dfrac{\pi_{\bm{\theta}}(a_{t}|s_{t})}{\pi_{{\bm{\theta}}_{k}}(a_{t}|s_{t})}\hat{A}^{C}_{t}\bigg{\\}}.$ |  Non-Convex Implementation

##  Appendix C Constrained Update Projection Algorithm

###  C.1 Practical Implementation of Performance Improvement

####  C.1.1 Sample-based Performance Improvement

Let the trajectory $\\{(s_{t},a_{t},r_{t+1},c_{t+1})\\}_{t=1}^{T}$ be sampled
according to $\pi_{\bm{\theta}_{k}}$, then we denote the empirical KL-
divergence with respect to $\pi_{\bm{\theta}}$ and
$\pi_{{\bm{\theta}}^{{}^{\prime}}}$ as follows,

$\hat{D}_{\mathtt{KL}}(\pi_{\bm{\theta}},\pi_{{\bm{\theta}}^{{}^{\prime}}})=\dfrac{1}{T}\sum_{t=1}^{T}\mathtt{KL}(\pi_{\bm{\theta}}(a_{t}|s_{t}),\pi_{{\bm{\theta}}^{{}^{\prime}}}(a_{t}|s_{t})).$

We defined the following
$\hat{\mathcal{L}}_{\text{R}}(\pi_{\bm{\theta}},\pi_{{\bm{\theta}}_{k}})$,

$\displaystyle\hat{\mathcal{L}}_{\text{R}}(\pi_{\bm{\theta}},\pi_{{\bm{\theta}}_{k}})$
$\displaystyle=\dfrac{1}{T}\sum_{t=1}^{T}\dfrac{\pi_{\bm{\theta}}(a_{t}|s_{t})}{\pi_{{\bm{\theta}}_{k}}(a_{t}|s_{t})}\hat{A}_{t}-\alpha_{k}\sqrt{\hat{D}_{\mathtt{KL}}(\pi_{{\bm{\theta}}_{k}},\pi_{{\bm{\theta}}})},$
(33)

where $\hat{A}_{t}$ is an estimator of
$A^{\mathtt{GAE}(\gamma,\lambda)}_{\pi_{{\bm{\theta}}_{k}}}(s,a)$. The term
$\hat{\mathcal{L}}_{\text{R}}(\pi_{\bm{\theta}},\pi_{{\bm{\theta}}_{k}})$ (33)
is an estimator of the next expectation that appears in (14)

$\mathbb{E}_{s\sim{d}_{\pi_{\bm{\theta}_{k}}}^{\lambda}(\cdot),~{}a\sim\pi_{\bm{\theta}_{k}}(\cdot|s)}\left[\frac{\pi_{\bm{\theta}}(a|s)}{\pi_{{\bm{\theta}}_{k}}(a|s)}A^{\mathtt{GAE}(\gamma,\lambda)}_{{\pi_{\bm{\theta}_{k}}}}(s,a)\right]-\alpha_{k}\sqrt{\mathbb{E}_{s\sim{d}_{{\pi_{\bm{\theta}_{k}}}}^{\lambda}(\cdot)}\left[\mathtt{KL}(\pi_{\bm{\theta}_{k}},\pi_{\bm{\theta}})[s]\right]}.$

Then we implement the performance improvement as follows,

$\displaystyle\pi_{{\bm{\theta}}_{k+\frac{1}{2}}}$
$\displaystyle=\arg\max_{\pi_{\bm{\theta}}\in\Pi_{\theta}}\left\\{\hat{\mathcal{L}}_{\text{R}}(\pi_{\bm{\theta}},\pi_{{\bm{\theta}}_{k}})\right\\}.$
(34)

####  C.1.2 Clipped Surrogate Objective

How can the implementation (34) take the biggest possible improvement step on
a policy using the data we currently have, without stepping so far that we
accidentally cause performance collapse? Now, we present a clip implementation
for policy improvement, which is very efficient in practice.

Instead of the previous policy improvement (14), according to PPO Schulman et
al. [2017], we update the policy as follows,

$\displaystyle\pi_{{\bm{\theta}}_{k+\frac{1}{2}}}$
$\displaystyle=\arg\max_{\pi_{{\bm{\theta}}}\in\Pi_{{\bm{\theta}}}}\left\\{\mathbb{E}_{s\sim{d}_{\pi_{\bm{\theta}_{k}}}^{\lambda}(\cdot),~{}a\sim\pi_{\bm{\theta}}(\cdot|s)}\left[\mathcal{L}_{\text{clip}}\left(s,a,\pi_{\bm{\theta}},\pi_{\bm{\theta}_{k}},\epsilon\right)\right]\right\\},$

where the the objective $\mathcal{L}_{\text{clip}}$ is defined as follows,

$\displaystyle\mathcal{L}_{\text{clip}}\left(s,a,\pi_{\bm{\theta}},\pi_{\bm{\theta}_{k}},\epsilon\right)=$
$\displaystyle\min\left\\{\dfrac{\pi_{\bm{\theta}}(a|s)}{\pi_{{\bm{\theta}}_{k}}(a|s)}A^{\mathtt{GAE}(\gamma,\lambda)}_{{\pi_{\bm{\theta}_{k}}}}(s,a),~{}\text{clip}\left(\dfrac{\pi_{\bm{\theta}}(a|s)}{\pi_{{\bm{\theta}}_{k}}(a|s)},1-\epsilon,1+\epsilon\right)A^{\mathtt{GAE}(\gamma,\lambda)}_{{\pi_{\bm{\theta}_{k}}}}(s,a)\right\\},$
(35)

$\epsilon$ is a hyperparameter which roughly says how far away the policy
$\pi_{{\bm{\theta}}_{k+\frac{1}{2}}}$ is allowed to go from the current policy
$\pi_{{\bm{\theta}}_{k}}$. The objective
$\mathcal{L}_{\text{clip}}\left(s,a,\pi_{\bm{\theta}},\pi_{\bm{\theta}_{k}},\epsilon\right)$
is complex, we present the insights of this clip mechanism Schulman et al.
[2017] to make CUP learn stably.

Positive GAE:
$A^{\mathtt{GAE}(\gamma,\lambda)}_{{\pi_{\bm{\theta}_{k}}}}(s,a)>0$. Firstly,
we consider the positive advantage, which implies the objective
$\mathcal{L}_{\text{clip}}\left(s,a,\pi_{\bm{\theta}},\pi_{\bm{\theta}_{k}},\epsilon\right)$
reduces to

$\displaystyle\mathcal{L}_{\text{clip}}\left(s,a,\pi_{\bm{\theta}},\pi_{\bm{\theta}_{k}},\epsilon\right)=\min\left\\{\dfrac{\pi_{\bm{\theta}}(a|s)}{\pi_{{\bm{\theta}}_{k}}(a|s)},1+\epsilon\right\\}A^{\mathtt{GAE}(\gamma,\lambda)}_{{\pi_{\bm{\theta}_{k}}}}(s,a).$
(36)

Since $A^{\mathtt{GAE}(\gamma,\lambda)}_{{\pi_{\bm{\theta}_{k}}}}(s,a)>0$, to
improve the performance, we need to increase $\pi_{\bm{\theta}}$. The
$\min\\{\cdot\\}$ operator determines the quantization how much the CUP
improves. If the policy improves too much such that

$\pi_{\bm{\theta}}(a|s)>(1+\epsilon)\pi_{\bm{\theta}_{k}}(a|s),$

The $\min\\{\cdot\\}$ operator hit the objective with a ceiling of
$(1+\epsilon)A^{\mathtt{GAE}(\gamma,\lambda)}_{{\pi_{\bm{\theta}_{k}}}}(s,a).$
The clip technique requires CUP learns a policy
$\pi_{{\bm{\theta}}_{k+\frac{1}{2}}}$ does not benefit by going far away from
the current policy $\pi_{{\bm{\theta}}_{k}}$.

Negative GAE:
$A^{\mathtt{GAE}(\gamma,\lambda)}_{{\pi_{\bm{\theta}_{k}}}}(s,a)<0$. Let us
consider the negative advantage, which implies the objective
$\mathcal{L}_{\text{clip}}\left(s,a,\pi_{\bm{\theta}},\pi_{\bm{\theta}_{k}},\epsilon\right)$
reduces to

$\displaystyle\mathcal{L}_{\text{clip}}\left(s,a,\pi_{\bm{\theta}},\pi_{\bm{\theta}_{k}},\epsilon\right)=\max\left\\{\dfrac{\pi_{\bm{\theta}}(a|s)}{\pi_{{\bm{\theta}}_{k}}(a|s)},1-\epsilon\right\\}A^{\mathtt{GAE}(\gamma,\lambda)}_{{\pi_{\bm{\theta}_{k}}}}(s,a).$
(37)

Since $A^{\mathtt{GAE}(\gamma,\lambda)}_{{\pi_{\bm{\theta}_{k}}}}(s,a)<0$, to
improve the performance, we need to decrease the policy
$\pi_{\bm{\theta}}(a|s)$. The $\max\\{\cdot\\}$ operator determines the
quantization how much the CUP improves. If the policy decrease too much such
that

$\pi_{\bm{\theta}}(a|s)<(1-\epsilon)\pi_{\bm{\theta}_{k}}(a|s),$

The $\max\\{\cdot\\}$ operator hit the objective with a ceiling of
$(1-\epsilon)A^{\mathtt{GAE}(\gamma,\lambda)}_{{\pi_{\bm{\theta}_{k}}}}(s,a).$
Thus, similar to the positive GAE the clip technique requires CUP learns a
policy $\pi_{{\bm{\theta}}_{k+\frac{1}{2}}}$ does not benefit by going far
away from the current policy $\pi_{{\bm{\theta}}_{k}}$.

####  C.1.3 Learning from Sampling

To short the expression, we introduce a function $g(\epsilon,A)$ as follows,

$\displaystyle g(\epsilon,A)=\begin{cases}(1+\epsilon)A~{}~{}A\geq 0\\\
(1+\epsilon)A~{}~{}A<0.\end{cases}$

Then we rewrite the objective (35) as follows,

$\displaystyle\mathcal{L}_{\text{clip}}\left(s,a,\pi_{\bm{\theta}},\pi_{\bm{\theta}_{k}},\epsilon\right)=\min\left\\{\dfrac{\pi_{\bm{\theta}}(a|s)}{\pi_{{\bm{\theta}}_{k}}(a|s)}A^{\mathtt{GAE}(\gamma,\lambda)}_{{\pi_{\bm{\theta}_{k}}}}(s,a),g\left(\epsilon,A^{\mathtt{GAE}(\gamma,\lambda)}_{{\pi_{\bm{\theta}_{k}}}}(s,a)\right)\right\\}.$
(38)

Recall the trajectory $\\{(s_{t},a_{t},r_{t+1},c_{t+1})\\}_{t=1}^{T}$ be
sampled according to $\pi_{\bm{\theta}_{k}}$, we defined the following
$\hat{\mathcal{L}}_{\text{clip}}(\pi_{\bm{\theta}},\pi_{{\bm{\theta}}_{k}})$,

$\displaystyle\hat{\mathcal{L}}_{\text{clip}}(\pi_{\bm{\theta}},\pi_{{\bm{\theta}}_{k}},\epsilon)$
$\displaystyle=\min\left\\{\dfrac{1}{T}\sum_{t=1}^{T}\dfrac{\pi_{\bm{\theta}}(a_{t}|s_{t})}{\pi_{{\bm{\theta}}_{k}}(a_{t}|s_{t})}\hat{A}_{t}-g\left(\epsilon,\dfrac{1}{T}\sum_{t=1}^{T}\hat{A}_{t}\right)\right\\},$
(39)

where $\hat{A}_{t}$ is an estimator of
$A^{\mathtt{GAE}(\gamma,\lambda)}_{\pi_{{\bm{\theta}}_{k}}}(s,a)$. The term
$\hat{\mathcal{L}}_{\text{clip}}(\pi_{\bm{\theta}},\pi_{{\bm{\theta}}_{k}},\epsilon)$
(39) is an estimator of the next expectation that appears in (38).

Then we implement the performance improvement as follows,

$\displaystyle\pi_{{\bm{\theta}}_{k+\frac{1}{2}}}$
$\displaystyle=\arg\max_{\pi_{\bm{\theta}}\in\Pi_{\theta}}\left\\{\hat{\mathcal{L}}_{\text{clip}}(\pi_{\bm{\theta}},\pi_{{\bm{\theta}}_{k}},\epsilon)\right\\},$

i.e., we obtain the parameter ${\bm{\theta}}_{k+\frac{1}{2}}$ according to

$\displaystyle{\bm{\theta}}_{k+\frac{1}{2}}$
$\displaystyle={\bm{\theta}}_{k}+\eta_{1}\dfrac{\partial}{\partial{\bm{\theta}}}\hat{\mathcal{L}}_{\text{clip}}(\pi_{\bm{\theta}},\pi_{{\bm{\theta}}_{k}},\epsilon)\Big{|}_{\bm{\theta}=\bm{\theta}_{k}},$

where $\eta_{1}$ is step-size.

###  C.2 Practical Implementation of Projection

Recall (15), we introduce the new surrogate function with respected to cost
function as follows,

$C_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}(\pi_{\bm{\theta}},\beta)=J^{c}(\pi_{{\bm{\theta}}^{{}^{\prime}}})+\dfrac{1}{1-\tilde{\gamma}}\mathbb{E}_{s\sim{d}_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}^{\lambda}(\cdot),a\sim\pi_{\bm{\theta}}(\cdot|s)}\left[A^{\mathtt{GAE}(\gamma,\lambda)}_{\pi_{{\bm{\theta}}^{{}^{\prime}}},C}(s,a)+\beta\sqrt{\mathbb{E}_{s\sim{d}_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}^{\lambda}(\cdot)}\left[\mathtt{KL}(\pi_{{\bm{\theta}}^{{}^{\prime}}},\pi_{\bm{\theta}})[s]\right]}\right],$

where $\beta$ is adaptive to the term
$\frac{\sqrt{2}\tilde{\gamma}\left(\gamma\lambda(|\mathcal{S}|-1)+1\right)\epsilon^{V}_{\pi_{\bm{\theta}}}(\pi_{{\bm{\theta}}^{{}^{\prime}}})}{(1-\gamma\lambda)}$.
Now, we rewrite the projection step (15) as follows,

$\displaystyle\pi_{{\bm{\theta}}_{k+1}}=$
$\displaystyle\arg\min_{\pi_{{\bm{\theta}}}\in\Pi_{{\bm{\theta}}}}~{}D\left(\pi_{{\bm{\theta}}},\pi_{{\bm{\theta}}_{k+\frac{1}{2}}}\right),~{}~{}\text{s.t.}~{}C_{\pi_{\bm{\theta}_{k}}}(\pi_{\bm{\theta}},\beta)\leq
b.$ (40)

We update the projection step (15) by replacing the distance function
$D(\cdot,\cdot)$ by KL-divergence, and we solve the constraint problem (15) by
the primal-dual approach.

######  Theorem 4.

The constrained problem (40) is equivalent to the following primal-dual
problem:

$\displaystyle\max_{\nu\geq
0}\min_{\pi_{\bm{\theta}}\in\Pi_{\bm{\theta}}}\left\\{D\left(\pi_{{\bm{\theta}}},\pi_{{\bm{\theta}}_{k+\frac{1}{2}}}\right)+\nu\left(C_{\pi_{\bm{\theta}_{k}}}(\pi_{\bm{\theta}},\beta)-b\right)\right\\}.$

###### Proof.

This result is a direct application of [Boyd and Vandenberghe, 2004, Chapter
5.9], and we also present it in D.1. Firstly, we notice if
$D\left(\cdot,\pi_{{\bm{\theta}}_{k+\frac{1}{2}}}\right)$ is KL divergence or
$\ell_{2}$-norm, then the constrained problem (40) is a convex problem 111It
is worth noting that
$\min_{\pi_{{\bm{\theta}}}\in\Pi_{{\bm{\theta}}}}~{}D\left(\pi_{{\bm{\theta}}},\pi_{{\bm{\theta}}_{k+\frac{1}{2}}}\right)$
is a convex problem, while
$\min_{\bm{\theta}\in\mathbb{R}^{p}}~{}D\left(\pi_{{\bm{\theta}}},\pi_{{\bm{\theta}}_{k+\frac{1}{2}}}\right)$
can be a non-convex problem.. In fact, for a given policy
$\pi_{{\bm{\theta}}_{k+\frac{1}{2}}}$,
$D\left(\cdot,\pi_{{\bm{\theta}}_{k+\frac{1}{2}}}\right)$ is convex over the
policy $\Pi_{\bm{\theta}}$, and
$C_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}(\cdot,\beta)$ is also convex over the
policy $\Pi_{\bm{\theta}}$. Additionally, Slater’s condition alway holds since
$C_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}(\pi_{{\bm{\theta}}^{{}^{\prime}}},\beta)=0$.
∎

According to Theorem 4, we turn the projection step (40) as the following
unconstrained problem,

$\displaystyle\max_{\nu\geq
0}\min_{\pi_{\bm{\theta}}\in\Pi_{\bm{\theta}}}\left\\{D\left(\pi_{{\bm{\theta}}},\pi_{{\bm{\theta}}_{k+\frac{1}{2}}}\right)+\nu\left(C_{\pi_{\bm{\theta}_{k}}}(\pi_{\bm{\theta}},\beta)-b\right)\right\\}.$
(41)

In our implementation, we use KL-divergence as the distance $D(\cdot,\cdot)$
to measure the difference between two policies, then

$\displaystyle
D\left(\pi_{{\bm{\theta}}},\pi_{{\bm{\theta}}_{k+\frac{1}{2}}}\right)=\mathbb{E}_{s\sim{d}_{{\pi_{\bm{\theta}_{k}}}}^{\lambda}(\cdot)}\left[\mathtt{KL}\left(\pi_{\bm{\theta}_{k+\frac{1}{2}}},\pi_{\bm{\theta}}\right)[s]\right],$
(42)

which implies we can rewrite the problem (41) as follows,

$\displaystyle\max_{\nu\geq
0}\min_{\pi_{\bm{\theta}}}\left\\{\mathbb{E}_{s\sim{d}_{{\pi_{\bm{\theta}_{k}}}}^{\lambda}(\cdot)}\left[\mathtt{KL}\left(\pi_{\bm{\theta}_{k+\frac{1}{2}}},\pi_{\bm{\theta}}\right)[s]\right]+\nu\left(C_{\pi_{\bm{\theta}_{k}}}(\pi_{\bm{\theta}},\beta)-b\right)\right\\}.$
(43)

Furthermore, we update the projection step as follows,

$\displaystyle(\pi_{{\bm{\theta}}_{k+1}},\nu_{k+1})=\arg\min_{\pi_{\bm{\theta}}\in\Pi_{\bm{\theta}}}\max_{\nu\geq
0}\left\\{\hat{\mathcal{L}}_{\text{c}}\left(\pi_{\bm{\theta}},\pi_{{\bm{\theta}}_{k}},{\bm{\theta}}_{k+\frac{1}{2}},\nu\right)\right\\},$

where

$\displaystyle\hat{\mathcal{L}}_{\text{c}}\left(\pi_{\bm{\theta}},\pi_{{\bm{\theta}}_{k}},{\bm{\theta}}_{k+\frac{1}{2}},\nu\right)=\hat{D}_{\mathtt{KL}}(\pi_{{\bm{\theta}}_{k+\frac{1}{2}}},\pi_{{\bm{\theta}}})+\nu\hat{C}(\pi_{\bm{\theta}},\pi_{{\bm{\theta}}_{k}}),$
$\displaystyle\hat{C}(\pi_{\bm{\theta}},\pi_{{\bm{\theta}}_{k}})$
$\displaystyle=\hat{J}^{C}+\frac{1}{1-\tilde{\gamma}}\cdot\frac{1}{T}\sum_{t=1}^{T}\frac{\pi_{\bm{\theta}}(a_{t}|s_{t})}{\pi_{{\bm{\theta}}_{k}}(a_{t}|s_{t})}\hat{A}^{C}_{t}+\beta_{k}\sqrt{\hat{D}_{\mathtt{KL}}(\pi_{{\bm{\theta}}_{k}},\pi_{{\bm{\theta}}})}-b,$

$\hat{J}^{C}$and $\hat{A}^{C}_{t}$ are estimators for cost-return and cost-
advantage.

######  Remark 3 (Track for Learning $\nu$).

Particularly, after some simple algebra, we obtain the derivation of
$\hat{\mathcal{L}}_{\text{c}}(\cdot)$ with respect to $\nu$ as follows,

$\displaystyle\dfrac{\partial\hat{\mathcal{L}}_{\text{c}}\left(\pi_{\bm{\theta}},\pi_{{\bm{\theta}}_{k}},{\bm{\theta}}_{k+\frac{1}{2}},\nu\right)}{\partial\nu}=J^{c}(\pi_{{\bm{\theta}}_{k}})+\dfrac{1}{1-\tilde{\gamma}}\mathbb{E}_{s\sim{d}_{\pi_{\bm{\theta}_{k}}}^{\lambda}(\cdot),a\sim\pi_{\bm{\theta}}(\cdot|s)}\left[A^{\mathtt{GAE}(\gamma,\lambda)}_{{\pi_{\bm{\theta}_{k}}},C}(s,a)\right]-b.$
(44)

But recall (14) is a minimization-maximization iteration, i.e., we require to
minimize the distance
$\mathbb{E}_{s\sim{d}_{\pi_{\bm{\theta}_{k}}}^{\lambda}(\cdot)}\mathrm{KL}\left(\pi_{{\bm{\theta}}},\pi_{{\bm{\theta}}_{k}}\right)[s]$,
which implies $\pi_{\bm{\theta}}$ is close to $\pi_{\bm{\theta}_{k}}$. Thus it
is reasonable to consider

$\mathbb{E}_{s\sim{d}_{\pi_{\bm{\theta}_{k}}}^{\lambda}(\cdot),a\sim\pi_{\bm{\theta}}(\cdot|s)}\left[A^{\mathtt{GAE}(\gamma,\lambda)}_{{\pi_{\bm{\theta}_{k}}},C}(s,a)\right]\approx
0.$

Thus, in practice, we update $\nu$ following a simple way

$\nu\leftarrow\left\\{\nu+\eta(J^{c}(\pi_{{\bm{\theta}}_{k}})-b)\right\\}_{+}.$

Finally, we obtain the parameters $({\bm{\theta}}_{k+1},\nu_{k+1})$ as
follows,

$\displaystyle\bm{\theta}_{k+1}$
$\displaystyle\leftarrow\bm{\theta}_{k}-\eta_{2}\dfrac{\partial}{\partial\bm{\theta}}\hat{\mathcal{L}}_{\text{c}}\left(\pi_{\bm{\theta}},\pi_{{\bm{\theta}}_{k}},{\bm{\theta}}_{k+\frac{1}{2}},\nu\right)\Big{|}_{\bm{\theta}=\bm{\theta}_{k},\nu=\nu_{k}},$
(45) $\displaystyle\nu_{k+1}$
$\displaystyle\leftarrow\left\\{\nu_{k}+\eta_{2}\dfrac{\partial}{\partial\nu}\hat{\mathcal{L}}_{\text{c}}\left(\pi_{\bm{\theta}},\pi_{{\bm{\theta}}_{k}},{\bm{\theta}}_{k+\frac{1}{2}},\nu\right)\Big{|}_{\bm{\theta}=\bm{\theta}_{k},\nu=\nu_{k}}\right\\}_{+},$
(46)

where $\\{\cdot\\}_{+}$ denotes the positive part, i.e., if $x\leq 0$,
$\\{x\\}_{+}=0$, else $\\{x\\}_{+}=x$. We have shown all the details of the
implementation in Algorithm 1.

Algorithm 1 Constrained Update Projection (CUP)

Initialize: policy network parameters ${\bm{\theta}}_{0}$; value network
parameter $\bm{\omega}_{0}$; cost value function parameter $\bm{\nu}_{0}$,
step-size $\nu_{0}$;

Hyper-parameters: trajectory horizon $T$; discount rate $\gamma$; episode
number $M,N$, mini-batch size $B$, positive constant $\alpha,\eta$;

for $k=0,1,2,\ldots$ do

Collect batch data of $M$ episodes of horizon $T$ in
$\cup_{i=1}^{M}\cup_{t=0}^{T}\left\\{(s_{i,t},a_{i,t},r_{i,t+1},c_{i,t+1})\right\\}$
according to current policy $\pi_{{\bm{\theta}}_{k}}$;

Estimate $c$-return by discount averaging on each episode:
$\hat{J}_{i}^{C}=\sum_{t=0}^{T}\gamma^{t}c_{i,t+1};$

Compute TD errors $\cup_{i=1}^{M}\cup_{t=0}^{T}\\{\delta_{i,t}\\}$, cost TD
errors $\cup_{i=1}^{M}\cup_{t=0}^{T}\\{\delta^{C}_{i,t}\\}$:
$\delta_{i,t}=r_{i,t}+\gamma
V_{\bm{\omega}_{k}}(s_{i,t})-V_{\bm{\omega}_{k}}(s_{i,t-1}),~{}\delta^{C}_{i,t}=c_{i,t}+\gamma
V^{C}_{\bm{\nu}_{k}}(s_{i,t})-V^{C}_{\bm{\nu}_{k}}(s_{i,t-1});$

Compute GAE:
$\cup_{i=1}^{M}\cup_{t=0}^{T}\\{\hat{A}_{i,t},\hat{A}^{C}_{i,t}\\}$:
$\hat{A}_{i,t}=\sum_{j=t}^{T}(\gamma\lambda)^{j-t}\delta_{i,j},~{}\hat{A}^{C}_{i,t}=\sum_{j=t}^{T}(\gamma\lambda)^{j-t}\delta^{C}_{i,j};$

Compute target function for value function and cost value function as follows,
$V^{\text{target}}_{i,t}=\hat{A}_{i,t}+V_{\bm{\omega}_{k}}(s_{i,t}),~{}~{}V^{\text{target},C}_{i,t}=\hat{A}_{i,t}^{C}+V^{C}_{\bm{\nu}_{k}}(s_{i,t});$

Store data:
$\mathcal{D}_{k}=\cup_{i=1}^{M}\cup_{t=0}^{T}\left\\{(a_{i,t},s_{i,t},\hat{A}_{i,t},\hat{A}^{C}_{i,t},V^{\text{target}}_{i,t},V^{\text{target},C}_{i,t})\right\\}$;

$\pi_{\text{old}}\leftarrow\pi_{\bm{\theta}_{k}}$; Policy Improvement

for $i=0,1,2,\ldots,M$ do

${\bm{\theta}}_{k+\frac{1}{2}}=\arg\max_{{\bm{\theta}}}\left\\{\frac{1}{T}\sum_{t=1}^{T}\frac{\pi_{\bm{\theta}}(a_{i,t}|s_{i,t})}{\pi_{\text{old}}(a_{i,t}|s_{i,t})}\hat{A}_{i,t}-g\left(\epsilon,\dfrac{1}{T}\sum_{t=1}^{T}\hat{A}_{i,t}\right)\right\\};$

end for

$\pi_{\text{old}}\leftarrow\pi_{\bm{\theta}_{k+\frac{1}{2}}}$; Projection

$\nu_{k+1}=(\nu_{k}+\eta(\hat{J}_{i}^{C}-b))_{+}$;

for $i=0,1,2,\ldots,M$ do

$\displaystyle{\bm{\theta}}_{k+1}$
$\displaystyle=\arg\min_{{\bm{\theta}}}\dfrac{1}{T}\sum_{t=1}^{T}\left\\{\mathrm{KL}(\pi_{{\bm{\theta}}_{\text{old}}}(\cdot|s_{i,t}),\pi_{{\bm{\theta}}}(\cdot|s_{i,t}))+\nu_{k}\dfrac{1-\gamma\lambda}{1-\gamma}\dfrac{\pi_{\bm{\theta}}(a_{i,t}|s_{i,t})}{\pi_{{\bm{\theta}}_{k}}(a_{i,t}|s_{i,t})}\hat{A}^{C}_{i,t}\right\\};$

end for

for each mini-batch
$\\{(a_{j},s_{j},\hat{A}_{j},\hat{A}^{C}_{j},V^{\text{target}}_{j},V^{\text{target},C}_{j})\\}$
of size $B$ from $\mathcal{D}_{k}$ do

$\bm{\omega}_{k+1}=\arg\min_{\bm{\omega}}\sum_{j=1}^{B}\left(V_{\bm{\omega}}(s_{j})-V^{\text{target}}_{j}\right)^{2},\bm{\nu}_{k+1}=\arg\min_{\bm{\nu}}\sum_{j=1}^{B}\left(V^{c}_{\bm{\nu}}(s_{j})-V^{\text{target},C}_{j}\right)^{2};$

end for

end for

##  Appendix D Preliminaries

In this section, we introduce some new notations and results about convex
optimization, state distribution, policy optimization and $\lambda$-returns.

###  D.1 Strong Duality via Slater’s Condition

We consider a convex optimization problem:

$\displaystyle p_{\star}$ $\displaystyle=\min_{x}f_{0}(x),$ (47)
$\displaystyle\mathrm{s.t.}~{}f_{i}(x)$ $\displaystyle\leq
0,~{}i=1,2,\cdots,m,$ (48) $\displaystyle h_{i}(x)$
$\displaystyle=0,~{}i=1,2,\cdots,p,$ (49)

where the functions $f_{0},f_{1},\cdots,f_{m}$ are convex, and
$h_{1},\cdots,h_{p}$ are affine. We denote by $\mathcal{D}$ the domain of the
problem (which is the intersection of the domains of all the functions
involved), and by $\mathcal{X}\subset\mathcal{D}$ its feasible set.

To the problem we associate the Lagrangian
$\mathcal{L}:\mathbb{R}^{n}\times\mathbb{R}^{m}\times\mathbb{R}^{p}\rightarrow\mathbb{R}$,
with values

$\displaystyle\mathcal{L}(x,\lambda,\nu)=f_{0}+\sum_{i=1}^{m}\lambda_{i}f_{i}(x)+\sum_{i=1}^{p}\nu_{i}h_{i}(x).$
(50)

The dual function is
$g:\mathbb{R}^{m}\times\mathbb{R}^{p}\rightarrow\mathbb{R}$, with values

$\displaystyle g(\lambda,\nu)=\min_{x}\mathcal{L}(x,\lambda,\nu).$ (51)

The associated dual problem is

$\displaystyle d_{\star}=\max_{\lambda\succeq 0,\nu}g(\lambda,\nu).$ (52)

Slater’s condition. We say that the problem satisfies Slater’s condition if it
is strictly feasible, that is:

$\displaystyle\exists
x_{0}~{}\in\mathcal{D}:f_{i}(x_{0})<0,i=1,\cdots,m,~{}h_{i}(x_{0})=0,i=1,\cdots,p.$
(53)

######  Theorem 5 (Strong duality via Slater condition).

If the primal problem (8.1) is convex, and satisfies the weak Slater’s
condition, then strong duality holds, that is, $p_{\star}=d_{\star}$.

We omit the proof of Theorem 5, for more discussions, please refer to [Boyd
and Vandenberghe, 2004, Chapter 5.9].

###  D.2 State Distribution

We use
$\mathbf{P}_{\pi_{\bm{\theta}}}\in\mathbb{R}^{|\mathcal{S}|\times|\mathcal{S}|}$
to denote the state transition matrix by executing $\pi_{\bm{\theta}}$, and
their components are:

$\mathbf{P}_{\pi_{\bm{\theta}}}[s,s^{\prime}]=\sum_{a\in\mathcal{A}}\pi_{\bm{\theta}}(a|s)\mathbb{P}(s^{\prime}|s,a)=:\mathbb{P}_{\pi_{\bm{\theta}}}(s^{{}^{\prime}}|s),~{}~{}s,s^{{}^{\prime}}\in\mathcal{S},$

which denotes one-step state transformation probability from $s$ to
$s^{{}^{\prime}}$.

We use $\mathbb{P}_{\pi_{\bm{\theta}}}(s_{t}=s|s_{0})$ to denote the
probability of visiting $s$ after $t$ time steps from the initial state
$s_{0}$ by executing $\pi_{\bm{\theta}}$. Particularly, we notice if $t=0$,
$s_{t}\neq s_{0}$, then $\mathbb{P}_{\pi_{\bm{\theta}}}(s_{t}=s|s_{0})=0$,
i.e.,

$\displaystyle\mathbb{P}_{\pi_{\bm{\theta}}}(s_{t}=s|s_{0})=0,~{}~{}t=0~{}\text{and}~{}s\neq
s_{0}.$ (54)

Then for any initial state $s_{0}\sim\rho(\cdot)$, the following holds,

$\displaystyle\mathbb{P}_{{\pi_{\bm{\theta}}}}(s_{t}=s|s_{0})=$
$\displaystyle\sum_{s^{{}^{\prime}}\in\mathcal{S}}\mathbb{P}_{{\pi_{\bm{\theta}}}}(s_{t}=s|s_{t-1}=s^{{}^{\prime}})\mathbb{P}_{{\pi_{\bm{\theta}}}}(s_{t-1}=s^{{}^{\prime}}|s_{0}).$
(55)

Recall $d_{\pi_{\bm{\theta}}}^{s_{0}}(s)$ denotes the normalized discounted
distribution of the future state $s$ encountered starting at $s_{0}$ by
executing $\pi_{\bm{\theta}}$,

$d_{\pi_{\bm{\theta}}}^{s_{0}}(s)=(1-\gamma)\sum_{t=0}^{\infty}\gamma^{t}\mathbb{P}_{\pi_{\bm{\theta}}}(s_{t}=s|s_{0}).$

Furthermore, since $s_{0}\sim\rho_{0}(\cdot)$, we define

$d_{\pi_{\bm{\theta}}}^{\rho_{0}}(s)=\mathbb{E}_{s_{0}\sim\rho_{0}(\cdot)}[d_{\pi_{\bm{\theta}}}^{s_{0}}(s)]=\int_{s_{0}\in\mathcal{S}}\rho_{0}(s_{0})d^{s_{0}}_{\pi_{\bm{\theta}}}(s)\text{d}s_{0}$

as the discounted state visitation distribution over the initial distribution
$\rho_{0}(\cdot)$. We use
$\mathbf{d}_{\pi_{\bm{\theta}}}^{\rho_{0}}\in\mathbb{R}^{|\mathcal{S}|}$ to
store all the normalized discounted state distributions, and its components
are:

$\mathbf{d}_{\pi_{\bm{\theta}}}^{\rho_{0}}[s]=d_{\pi_{\bm{\theta}}}^{\rho_{0}}(s),~{}~{}s\in\mathcal{S}.$

We use $\bm{\rho}_{0}\in\mathbb{R}^{|\mathcal{S}|}$ to denote initial state
distribution vector, and their components are:

$\bm{\rho}_{0}[s]=\rho_{0}(s),~{}~{}s\in\mathcal{S}.$

Then, we rewrite $\mathbf{d}_{\pi_{\bm{\theta}}}^{\rho_{0}}$ as the following
matrix version,

$\displaystyle\mathbf{d}_{\pi_{\bm{\theta}}}^{\rho_{0}}=(1-\gamma)\sum_{t=0}^{\infty}(\gamma\mathbf{P}_{\pi_{\bm{\theta}}})^{t}\bm{\rho}_{0}=(1-\gamma)(\mathbf{I}-\gamma\mathbf{P}_{\pi_{\bm{\theta}}})^{-1}\bm{\rho}_{0}.$
(56)

###  D.3 Objective of MDP

Recall $\tau=\\{s_{t},a_{t},r_{t+1}\\}_{t\geq 0}\sim{\pi_{\bm{\theta}}}$,
according to $\tau$, we define the expected return
$J({\pi_{\bm{\theta}}}|s_{0})$ as follows,

$\displaystyle J({\pi_{\bm{\theta}}}|s_{0})=$
$\displaystyle\mathbb{E}_{\tau\sim\pi_{\bm{\theta}}}[R(\tau)]=\dfrac{1}{1-\gamma}\mathbb{E}_{s\sim
d_{\pi_{\bm{\theta}}}^{s_{0}}(\cdot),a\sim\pi_{\bm{\theta}}(\cdot|s),s^{{}^{\prime}}\sim\mathbb{P}(\cdot|s,a)}\left[r(s^{{}^{\prime}}|s,a)\right],$
(57)

where $R(\tau)=\sum_{t\geq 0}\gamma^{t}r_{t+1}$, and the notation
$J({\pi_{\bm{\theta}}}|s_{0})$ is “conditional” on $s_{0}$ is to emphasize the
trajectory $\tau$ starting from $s_{0}$.

Since $s_{0}\sim\rho_{0}(\cdot)$, we define the objective of MDP as follows,

$\displaystyle J(\pi_{\bm{\theta}})=\dfrac{1}{1-\gamma}\mathbb{E}_{s\sim
d_{\pi_{\bm{\theta}}}^{\rho_{0}}(\cdot),a\sim\pi_{\bm{\theta}}(\cdot|s),s^{{}^{\prime}}\sim\mathbb{P}(\cdot|s,a)}\left[r(s^{{}^{\prime}}|s,a)\right].$
(58)

The goal of reinforcement learning is to solve the following optimization
problem:

$\displaystyle\bm{\theta}_{\star}=\arg\max_{\bm{\theta}\in\mathbb{R}^{p}}J(\pi_{\bm{\theta}}).$
(59)

###  D.4 $\lambda$-Return

Let $\mathcal{B}_{\pi_{\bm{\theta}}}$ be the _Bellman operator_ :

$\displaystyle\mathcal{B}_{\pi_{\bm{\theta}}}:\mathbb{R}^{|\mathcal{S}|}\rightarrow\mathbb{R}^{|\mathcal{S}|},~{}~{}~{}~{}v\mapsto\mathbf{r}_{\pi_{\bm{\theta}}}+\gamma\mathbf{P}_{\pi_{\bm{\theta}}}v,$
(60)

where $\mathbf{r}_{\pi_{\bm{\theta}}}\in\mathbb{R}^{|\mathcal{S}|}$ is the
expected reward according to $\pi_{\bm{\theta}}$, i.e., their components are:

$\mathbf{r}_{\pi_{\bm{\theta}}}[s]=\sum_{a\in\mathcal{A}}\sum_{s^{{}^{\prime}}\in\mathcal{S}}\pi_{\bm{\theta}}(a|s)r(s^{\prime}|s,a)=:R_{\pi_{\bm{\theta}}}(s),~{}~{}s\in\mathcal{S}.$

Let $\mathbf{v}_{\pi_{\bm{\theta}}}\in\mathbb{R}^{|\mathcal{S}|}$ be a vector
that stores all the state value functions, and its components are:

$\mathbf{v}_{\pi_{\bm{\theta}}}[s]=V_{\pi_{\bm{\theta}}}(s),~{}~{}s\in\mathcal{S}.$

Then, according to Bellman operator (60), we rewrite Bellman equation
[Bellman, 1957] as the following matrix version:

$\displaystyle\mathcal{B}_{\pi_{\bm{\theta}}}\mathbf{v}_{\pi_{\bm{\theta}}}=\mathbf{v}_{\pi_{\bm{\theta}}}.$
(61)

Furthermore, we define $\lambda$-_Bellman operator_
$\mathcal{B}^{\lambda}_{\pi_{\bm{\theta}}}$ as follows,

$\mathcal{B}^{\lambda}_{\pi_{\bm{\theta}}}=(1-\lambda)\sum_{t=0}^{\infty}\lambda^{t}(\mathcal{B}_{\pi_{\bm{\theta}}})^{{t}+1},$

which implies

$\displaystyle\mathcal{B}^{\lambda}_{\pi_{\bm{\theta}}}:\mathbb{R}^{|\mathcal{S}|}\rightarrow\mathbb{R}^{|\mathcal{S}|},~{}~{}~{}~{}v\mapsto\mathbf{r}^{(\lambda)}_{\pi_{\bm{\theta}}}+\tilde{\gamma}\mathbf{P}^{(\lambda)}_{\pi_{\bm{\theta}}}v,$
(62)

where

$\displaystyle\mathbf{P}^{(\lambda)}_{\pi_{\bm{\theta}}}=(1-\gamma\lambda)\sum_{{t}=0}^{\infty}(\gamma\lambda)^{{t}}\mathbf{P}^{{t}+1}_{\pi_{\bm{\theta}}},~{}~{}\mathbf{r}^{(\lambda)}_{\pi_{\bm{\theta}}}=\sum_{{t}=0}^{\infty}(\gamma\lambda\mathbf{P}_{\pi_{\bm{\theta}}})^{{t}}\mathbf{r}_{\pi_{\bm{\theta}}},~{}~{}\tilde{\gamma}=\dfrac{\gamma(1-\lambda)}{1-\gamma\lambda}.$
(63)

Let

$\displaystyle\mathbb{P}_{\pi_{\bm{\theta}}}^{(\lambda)}(s^{{}^{\prime}}|s)=\mathbf{P}^{(\lambda)}_{\pi_{\bm{\theta}}}[s,s^{{}^{\prime}}]=:(1-\gamma\lambda)\sum_{{t}=0}^{\infty}(\gamma\lambda)^{{t}}\left(\mathbf{P}^{{t}+1}_{\pi_{\bm{\theta}}}[s,s^{{}^{\prime}}]\right),$
(64)

where $\mathbf{P}^{{t}+1}_{\pi_{\bm{\theta}}}[s,s^{{}^{\prime}}]$ is the
$(s,s^{{}^{\prime}})$-th component of matrix
$\mathbf{P}^{{t}+1}_{\pi_{\bm{\theta}}}$, which is the probability of visiting
$s^{{}^{\prime}}$ after $t+1$ time steps from the state $s$ by executing
$\pi_{\bm{\theta}}$, i.e.,

$\displaystyle\mathbf{P}^{{t}+1}_{\pi_{\bm{\theta}}}[s,s^{{}^{\prime}}]=\mathbb{P}_{\pi_{\bm{\theta}}}(s_{t+1}=s^{{}^{\prime}}|s).$
(65)

Thus, we rewrite
$\mathbb{P}_{\pi_{\bm{\theta}}}^{(\lambda)}(s^{{}^{\prime}}|s)$ (64) as
follows

$\displaystyle\mathbb{P}_{\pi_{\bm{\theta}}}^{(\lambda)}(s^{{}^{\prime}}|s)=(1-\gamma\lambda)\sum_{{t}=0}^{\infty}(\gamma\lambda)^{{t}}\mathbb{P}_{\pi_{\bm{\theta}}}(s_{t+1}=s^{{}^{\prime}}|s),~{}~{}s\in\mathcal{S}.$
(66)

######  Remark 4.

Furthermore, recall the following visitation sequence
$\tau=\\{s_{t},a_{t},r_{t+1}\\}_{t\geq 0}$ induced by $\pi_{\bm{\theta}}$, it
is similar to the probability
$\mathbb{P}_{{\pi_{\bm{\theta}}}}(s_{t}=s^{{}^{\prime}}|s_{0})$, we introduce
$\mathbb{P}^{(\lambda)}_{{\pi_{\bm{\theta}}}}(s_{t}=s^{{}^{\prime}}|s_{0})$ as
the probability of transition from state $s$ to state $s^{{}^{\prime}}$after
$t$ time steps under the dynamic transformation matrix
$\mathbf{P}^{(\lambda)}_{\pi_{\bm{\theta}}}$. Then, the following equity holds

$\displaystyle\mathbb{P}_{{\pi_{\bm{\theta}}}}^{(\lambda)}(s_{t}=s|s_{0})=$
$\displaystyle\sum_{s^{{}^{\prime}}\in\mathcal{S}}\mathbb{P}_{{\pi_{\bm{\theta}}}}^{(\lambda)}(s_{t}=s|s_{t-1}=s^{{}^{\prime}})\mathbb{P}_{{\pi_{\bm{\theta}}}}^{(\lambda)}(s_{t-1}=s^{{}^{\prime}}|s_{0}).$
(67)

Similarly, let

$\displaystyle
R^{(\lambda)}_{\pi_{\bm{\theta}}}(s)=:\mathbf{r}^{(\lambda)}_{\pi_{\bm{\theta}}}[s]=$
$\displaystyle\sum_{{t}=0}^{\infty}(\gamma\lambda\mathbf{P}_{\pi_{\bm{\theta}}})^{{t}}\mathbf{r}_{\pi_{\bm{\theta}}}[s]=\sum_{{t}=0}^{\infty}(\gamma\lambda)^{t}\left(\sum_{s^{{}^{\prime}}\in\mathcal{S}}\mathbb{P}_{\pi_{\bm{\theta}}}(s_{t}=s^{{}^{\prime}}|s)R_{\pi_{\bm{\theta}}}(s^{{}^{\prime}})\right)$
$\displaystyle=$
$\displaystyle\sum_{{t}=0}^{\infty}\sum_{s^{{}^{\prime}}\in\mathcal{S}}(\gamma\lambda)^{t}\mathbb{P}_{\pi_{\bm{\theta}}}(s_{t}=s^{{}^{\prime}}|s)R_{\pi_{\bm{\theta}}}(s^{{}^{\prime}}).$
(68)

It is similar to normalized discounted distribution
$d_{\pi_{\bm{\theta}}}^{\rho_{0}}(s)$, we introduce $\lambda$-return version
of discounted state distribution $d_{\pi_{\bm{\theta}}}^{\lambda}(s)$ as
follows: $\forall s\in\mathcal{S}$,

$\displaystyle d_{\pi_{\bm{\theta}}}^{s_{0},\lambda}(s)$
$\displaystyle=(1-\tilde{\gamma})\sum_{t=0}^{\infty}\tilde{\gamma}^{t}\mathbb{P}^{(\lambda)}_{\pi_{\bm{\theta}}}(s_{t}=s|s_{0}),$
(69) $\displaystyle d_{\pi_{\bm{\theta}}}^{\lambda}(s)$
$\displaystyle=\mathbb{E}_{s_{0}\sim\rho_{0}(\cdot)}\left[d_{\pi_{\bm{\theta}}}^{s_{0},\lambda}(s)\right],$
(70) $\displaystyle\mathbf{d}_{\pi_{\bm{\theta}}}^{\lambda}[s]$
$\displaystyle=d_{\pi_{\bm{\theta}}}^{\lambda}(s),$ (71)

where $\mathbb{P}^{(\lambda)}_{\pi_{\bm{\theta}}}(s_{t}=s|s_{0})$ is the
$(s_{0},s)$-th component of the matrix
$\left(\mathbf{P}^{(\lambda)}_{\pi_{\bm{\theta}}}\right)^{t}$, i.e.,

$\mathbb{P}^{(\lambda)}_{\pi_{\bm{\theta}}}(s_{t}=s|s_{0})=:\left(\mathbf{P}^{(\lambda)}_{\pi_{\bm{\theta}}}\right)^{t}[s_{0},s].$

Similarly,
$\mathbb{P}^{(\lambda)}_{\pi_{\bm{\theta}}}(s_{t}=s^{{}^{\prime}}|s)$ is the
$(s,s^{{}^{\prime}})$-th component of the matrix
$\left(\mathbf{P}^{(\lambda)}_{\pi_{\bm{\theta}}}\right)^{t}$, i.e.,

$\mathbb{P}^{(\lambda)}_{\pi_{\bm{\theta}}}(s_{t}=s^{{}^{\prime}}|s)=:\left(\mathbf{P}^{(\lambda)}_{\pi_{\bm{\theta}}}\right)^{t}[s,s^{{}^{\prime}}].$

Finally, we rewrite $\mathbf{d}_{\pi_{\bm{\theta}}}^{\rho_{0},\lambda}$ as the
following matrix version,

$\displaystyle\mathbf{d}_{\pi_{\bm{\theta}}}^{\lambda}=(1-\tilde{\gamma})\sum_{t=0}^{\infty}\left(\gamma\mathbf{P}^{(\lambda)}_{\pi_{\bm{\theta}}}\right)^{t}\bm{\rho}_{0}=(1-\tilde{\gamma})\left(\mathbf{I}-\tilde{\gamma}\mathbf{P}^{(\lambda)}_{\pi_{\bm{\theta}}}\right)^{-1}\bm{\rho}_{0}.$
(72)

######  Remark 5 ($\lambda$-Return Version of Bellman Equation).

According to Bellman equation (61), $\mathbf{v}_{\pi_{\bm{\theta}}}$ is fixed
point of $\lambda$-operator $\mathcal{B}^{\lambda}_{\pi_{\bm{\theta}}}$, i.e.,

$\displaystyle\mathbf{v}_{\pi_{\bm{\theta}}}=\mathbf{r}^{(\lambda)}_{\pi_{\bm{\theta}}}+{\tilde{\gamma}}\mathbf{P}^{(\lambda)}_{\pi_{\bm{\theta}}}\mathbf{v}_{\pi_{\bm{\theta}}}.$
(73)

Recall $\tau=\\{s_{t},a_{t},r_{t+1}\\}_{t\geq 0}\sim\pi_{\bm{\theta}}$,
according to (73), the value function of initial state $s_{0}$ is

$\displaystyle V_{\pi_{\bm{\theta}}}(s_{0})$
$\displaystyle=\mathbf{v}_{\pi_{\bm{\theta}}}[s_{0}]=\mathbf{r}^{(\lambda)}_{\pi_{\bm{\theta}}}[s_{0}]+\tilde{\gamma}\mathbf{P}^{(\lambda)}_{\pi_{\bm{\theta}}}\mathbf{v}_{\pi_{\bm{\theta}}}[s_{0}]$
$\displaystyle=R^{(\lambda)}_{\pi_{\bm{\theta}}}(s_{0})+{\tilde{\gamma}}\sum_{s^{{}^{\prime}}\in\mathcal{S}}\mathbb{P}_{\pi_{\bm{\theta}}}^{(\lambda)}(s_{1}=s^{{}^{\prime}}|s_{0})V_{\pi_{\bm{\theta}}}(s^{{}^{\prime}}).$
(74)

We unroll the expression of (74) repeatedly, then we have

$\displaystyle V_{{\pi_{\bm{\theta}}}}(s_{0})$ $\displaystyle=$
$\displaystyle{R}^{(\lambda)}_{\pi_{\bm{\theta}}}(s_{0})+{\tilde{\gamma}}\sum_{s^{{}^{\prime}}\in\mathcal{S}}\mathbb{P}_{{\pi_{\bm{\theta}}}}^{(\lambda)}(s_{1}=s^{{}^{\prime}}|s_{0})\underbrace{\left({R}^{(\lambda)}_{\pi_{\bm{\theta}}}(s^{{}^{\prime}})+{\tilde{\gamma}}\sum_{s^{{}^{\prime\prime}}\in\mathcal{S}}\mathbb{P}_{{\pi_{\bm{\theta}}}}^{(\lambda)}(s_{2}=s^{{}^{\prime\prime}}|s_{1}=s^{{}^{\prime}})V_{{\pi_{\bm{\theta}}}}(s^{{}^{\prime\prime}})\right)}_{=V_{{\pi_{\bm{\theta}}}}(s^{{}^{\prime}})}$
$\displaystyle=$
$\displaystyle{R}^{(\lambda)}_{\pi_{\bm{\theta}}}(s_{0})+{\tilde{\gamma}}\sum_{s^{{}^{\prime}}\in\mathcal{S}}\mathbb{P}_{{\pi_{\bm{\theta}}}}^{(\lambda)}(s_{1}=s^{{}^{\prime}}|s_{0}){R}^{(\lambda)}_{\pi_{\bm{\theta}}}(s^{{}^{\prime}})$
$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}+{\tilde{\gamma}}^{2}\sum_{s^{{}^{\prime\prime}}\in\mathcal{S}}\underbrace{\left(\sum_{s^{{}^{\prime}}\in\mathcal{S}}\mathbb{P}_{{\pi_{\bm{\theta}}}}^{(\lambda)}(s_{1}=s^{{}^{\prime}}|s_{0})\mathbb{P}_{{\pi_{\bm{\theta}}}}^{(\lambda)}(s_{2}=s^{{}^{\prime\prime}}|s_{1}=s^{{}^{\prime}})\right)}_{\overset{(\ref{pro-
pi-t-
step})}{=}:\mathbb{P}^{(\lambda)}_{{\pi_{\bm{\theta}}}}\left(s_{2}=s^{{}^{\prime\prime}}|s_{0}\right)}V_{{\pi_{\bm{\theta}}}}(s^{{}^{\prime\prime}})$
$\displaystyle=$
$\displaystyle{R}^{(\lambda)}_{\pi_{\bm{\theta}}}(s_{0})+{\tilde{\gamma}}\sum_{s\in\mathcal{S}}\mathbb{P}_{{\pi_{\bm{\theta}}}}^{(\lambda)}(s_{1}=s|s_{0}){R}^{(\lambda)}_{\pi_{\bm{\theta}}}(s)+{\tilde{\gamma}}^{2}\sum_{s\in\mathcal{S}}\mathbb{P}_{{\pi_{\bm{\theta}}}}^{(\lambda)}(s_{2}=s|s_{0})V_{{\pi_{\bm{\theta}}}}(s)$
$\displaystyle=$
$\displaystyle{R}^{(\lambda)}_{\pi_{\bm{\theta}}}(s_{0})+{\tilde{\gamma}}\sum_{s\in\mathcal{S}}\mathbb{P}_{{\pi_{\bm{\theta}}}}^{(\lambda)}(s_{1}=s|s_{0}){R}^{(\lambda)}_{\pi_{\bm{\theta}}}(s)$
$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}+{\tilde{\gamma}}^{2}\sum_{s\in\mathcal{S}}\mathbb{P}_{{\pi_{\bm{\theta}}}}^{(\lambda)}(s_{2}=s|s_{0})\left({R}^{(\lambda)}_{\pi_{\bm{\theta}}}(s)+{\tilde{\gamma}}\sum_{s^{{}^{\prime}}\in\mathcal{S}}\mathbb{P}_{{\pi_{\bm{\theta}}}}^{(\lambda)}(s_{3}=s^{{}^{\prime}}|s_{2}=s)V_{{\pi_{\bm{\theta}}}}(s^{{}^{\prime}})\right)$
$\displaystyle=$
$\displaystyle{R}^{(\lambda)}_{\pi_{\bm{\theta}}}(s_{0})+{\tilde{\gamma}}\sum_{s\in\mathcal{S}}\mathbb{P}_{{\pi_{\bm{\theta}}}}^{(\lambda)}(s_{1}=s|s_{0}){R}^{(\lambda)}_{\pi_{\bm{\theta}}}(s)+{\tilde{\gamma}}^{2}\sum_{s\in\mathcal{S}}\mathbb{P}_{{\pi_{\bm{\theta}}}}^{(\lambda)}(s_{2}=s|s_{0}){R}^{(\lambda)}_{\pi_{\bm{\theta}}}(s)$
$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}+{\tilde{\gamma}}^{3}\sum_{s^{{}^{\prime}}\in\mathcal{S}}\underbrace{\left(\sum_{s\in\mathcal{S}}\mathbb{P}_{{\pi_{\bm{\theta}}}}^{(\lambda)}(s_{2}=s|s_{0})\mathbb{P}_{{\pi_{\bm{\theta}}}}^{(\lambda)}(s_{3}=s^{{}^{\prime}}|s_{2}=s)\right)}_{=\mathbb{P}_{{\pi_{\bm{\theta}}}}^{(\lambda)}(s_{3}=s^{{}^{\prime}}|s_{0})}V_{{\pi_{\bm{\theta}}}}(s^{{}^{\prime}})$
$\displaystyle=$
$\displaystyle{R}^{(\lambda)}(s_{0})+{\tilde{\gamma}}\sum_{s\in\mathcal{S}}\mathbb{P}_{{\pi_{\bm{\theta}}}}^{(\lambda)}(s_{1}=s|s_{0}){R}^{(\lambda)}_{\pi_{\bm{\theta}}}(s)+{\tilde{\gamma}}^{2}\sum_{s\in\mathcal{S}}\mathbb{P}_{{\pi_{\bm{\theta}}}}^{(\lambda)}(s_{2}=s|s_{0}){R}^{(\lambda)}_{\pi_{\bm{\theta}}}(s)$
$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}+{\tilde{\gamma}}^{3}\sum_{s\in\mathcal{S}}\mathbb{P}^{(\lambda)}_{{\pi_{\bm{\theta}}}}(s_{3}=s|s_{0})V_{{\pi_{\bm{\theta}}}}(s)$
$\displaystyle=$ $\displaystyle\cdots$ $\displaystyle=$
$\displaystyle\sum_{s\in\mathcal{S}}\sum_{t=0}^{\infty}{\tilde{\gamma}}^{t}\mathbb{P}_{{\pi_{\bm{\theta}}}}^{(\lambda)}(s_{t}=s|s_{0}){R}^{(\lambda)}_{\pi_{\bm{\theta}}}(s)\overset{(\ref{lambda-
dis-state-
distribution})}{=}\dfrac{1}{1-{\tilde{\gamma}}}\sum_{s\in\mathcal{S}}d^{s_{0},\lambda}_{\pi_{\bm{\theta}}}(s){R}^{(\lambda)}_{\pi_{\bm{\theta}}}(s).$
(75)

According to (57) and (75), we have

$\displaystyle J({\pi_{\bm{\theta}}})=$
$\displaystyle\sum_{s_{0}\in\mathcal{S}}\rho_{0}(s_{0})V_{\pi_{\bm{\theta}}}(s_{0})\overset{(\ref{re-
bellman-
eq-01})}{=}\dfrac{1}{1-{\tilde{\gamma}}}\sum_{s_{0}\in\mathcal{S}}\rho_{0}(s_{0})\sum_{s\in\mathcal{S}}d^{s_{0},\lambda}_{\pi_{\bm{\theta}}}(s)R^{(\lambda)}_{\pi_{\bm{\theta}}}(s)$
$\displaystyle=$
$\displaystyle\dfrac{1}{1-{\tilde{\gamma}}}\sum_{s\in\mathcal{S}}\underbrace{\left(\sum_{s_{0}\in\mathcal{S}}\rho_{0}(s_{0})d^{s_{0},\lambda}_{\pi_{\bm{\theta}}}(s)\right)}_{=d^{\lambda}_{\pi_{\bm{\theta}}}(s)}R^{(\lambda)}_{\pi_{\bm{\theta}}}(s)$
$\displaystyle=$
$\displaystyle\dfrac{1}{1-{\tilde{\gamma}}}\sum_{s\in\mathcal{S}}d^{\lambda}_{\pi_{\bm{\theta}}}(s)R^{(\lambda)}_{\pi_{\bm{\theta}}}(s)=\dfrac{1}{1-{\tilde{\gamma}}}\mathbb{E}_{s\sim
d^{\lambda}_{\pi_{\bm{\theta}}}(\cdot)}\left[R^{(\lambda)}_{\pi_{\bm{\theta}}}(s)\right].$
(76)

Finally, we summarize above results in the following Lemma 1.

######  Lemma 1.

The objective $J(\pi_{\bm{\theta}})$ (58) can be rewritten as the following
version:

$J({\pi_{\bm{\theta}}})=\dfrac{1}{1-{\tilde{\gamma}}}\sum_{s\in\mathcal{S}}d^{\lambda}_{\pi_{\bm{\theta}}}(s)R^{(\lambda)}_{\pi_{\bm{\theta}}}(s)=\dfrac{1}{1-{\tilde{\gamma}}}\mathbb{E}_{s\sim
d^{\lambda}_{\pi_{\bm{\theta}}}(\cdot)}\left[R^{(\lambda)}_{\pi_{\bm{\theta}}}(s)\right].$

##  Appendix E Proof of Theorem 1

We need the following Proposition 4 to prove Theorem 1, which illustrates an
identity for the objective function of policy optimization.

######  Proposition 4.

For any function $\varphi(\cdot):\mathcal{S}\rightarrow\mathbb{R}$, for any
policy $\pi_{\bm{\theta}}$, for any trajectory satisfies
$\tau=\\{s_{t},a_{t},r_{t+1}\\}_{t\geq 0}\sim{\pi_{\bm{\theta}}}$, let

$\displaystyle\delta_{t}^{\varphi}$
$\displaystyle=r(s_{t+1}|s_{t},a_{t})+\gamma\varphi(s_{t+1})-\varphi(s_{t}),$
$\displaystyle\delta^{\varphi}_{\pi_{\bm{\theta}},t}(s)$
$\displaystyle=\mathbb{E}_{s_{t}\sim\mathbb{P}_{\pi_{\bm{\theta}}}(\cdot|s),a_{t}\sim{\pi_{\bm{\theta}}}(\cdot|s_{t}),s_{t+1}\sim\mathbb{P}(\cdot|s_{t},a_{t})}\left[\delta_{t}^{\varphi}\right],$

then, the objective $J(\pi_{\bm{\theta}})$ (76) can be rewritten as the
following version:

$\displaystyle J(\pi_{\bm{\theta}})=$
$\displaystyle\mathbb{E}_{s_{0}\sim\rho_{0}(\cdot)}[\varphi(s_{0})]+\dfrac{1}{1-\tilde{\gamma}}\sum_{s\in\mathcal{S}}d^{\lambda}_{\pi_{\bm{\theta}}}(s)\left(\sum_{t=0}^{\infty}\gamma^{t}\lambda^{t}\delta^{\varphi}_{\pi_{\bm{\theta}},t}(s)\right)$
(77) $\displaystyle=$
$\displaystyle\mathbb{E}_{s_{0}\sim\rho_{0}(\cdot)}[\varphi(s_{0})]+\dfrac{1}{1-\tilde{\gamma}}\mathbb{E}_{s\sim
d^{\lambda}_{\pi_{\bm{\theta}}}(\cdot)}\left[\sum_{t=0}^{\infty}\gamma^{t}\lambda^{t}\delta^{\varphi}_{\pi_{\bm{\theta}},t}(s)\right].$

We present the proof of of Proposition 4 at the end of this section, see
Section E.2.

We introduce a vector
$\bm{\delta}^{\varphi}_{\pi_{\bm{\theta}},t}\in\mathbb{R}^{|\mathcal{S}|}$ and
its components are: for any $s\in\mathcal{S}$

$\displaystyle\bm{\delta}^{\varphi}_{\pi_{\bm{\theta}},t}[s]={{\delta}}^{\varphi}_{\pi_{\bm{\theta}},t}(s).$
(78)

Then, we rewrite the objective as the following vector version

$\displaystyle
J(\pi_{\bm{\theta}})=\mathbb{E}_{s_{0}\sim\rho_{0}(\cdot)}[\varphi(s_{0})]+\dfrac{1}{1-\tilde{\gamma}}\sum_{t=0}^{\infty}\gamma^{t}\lambda^{t}\langle\mathbf{d}_{\pi_{\bm{\theta}}}^{\lambda},\bm{\delta}^{\varphi}_{\pi_{\bm{\theta}},t}\rangle,$
(79)

where $\langle\cdot,\cdot\rangle$ denotes inner production between two
vectors.

###  E.1 Proof of Theorem 1

Theorem 1 (Generalized Policy Performance Difference) _For any function
$\varphi(\cdot):\mathcal{S}\rightarrow\mathbb{R}$, for two arbitrary policy
$\pi_{\bm{\theta}}$ and $\pi_{{\bm{\theta}}^{{}^{\prime}}}$, for any
$p,q\in[1,\infty)$ such that $\frac{1}{p}+\frac{1}{q}=1$, The following bound
holds:_

$\displaystyle\dfrac{1}{1-\tilde{\gamma}}\sum_{t=0}^{\infty}\gamma^{t}\lambda^{t}M^{\varphi,-}_{p,q,t}(\pi_{\bm{\theta}},\pi_{{\bm{\theta}}^{{}^{\prime}}})\leq
J(\pi_{\bm{\theta}})-J(\pi_{{\bm{\theta}}^{{}^{\prime}}})\leq\dfrac{1}{1-\tilde{\gamma}}\sum_{t=0}^{\infty}\gamma^{t}\lambda^{t}M^{\varphi,+}_{p,q,t}(\pi_{\bm{\theta}},\pi_{{\bm{\theta}}^{{}^{\prime}}}),$
(80)

_where the terms $M^{\varphi,-}_{p,q,t}$ and $M^{\varphi,+}_{p,q,t}$ are
defined in (96)-(97). _

###### Proof.

(of Theorem 1)

We consider two arbitrary policies $\pi_{\bm{\theta}}$ and
$\pi_{{\bm{\theta}}^{{}^{\prime}}}$ with different parameters $\bm{\theta}$
and $\bm{\theta}^{{}^{\prime}}$, let

$\displaystyle
D_{t}^{\varphi,(\lambda)}(\pi_{\bm{\theta}},\pi_{{\bm{\theta}}^{{}^{\prime}}})=:\langle\mathbf{d}_{\pi_{\bm{\theta}}}^{\lambda},\bm{\delta}^{\varphi}_{\pi_{\bm{\theta}},t}\rangle-\langle\mathbf{d}_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}^{\lambda},\bm{\delta}^{\varphi}_{\pi_{{\bm{\theta}}^{{}^{\prime}}},t}\rangle.$
(81)

According to (79), we obtain performance difference as follows,

$\displaystyle J(\pi_{\bm{\theta}})-J(\pi_{{\bm{\theta}}^{{}^{\prime}}})=$
$\displaystyle\dfrac{1}{1-\tilde{\gamma}}\sum_{t=0}^{\infty}\gamma^{t}\lambda^{t}\left(\langle\mathbf{d}_{\pi_{\bm{\theta}}}^{\lambda},\bm{\delta}^{\varphi}_{\pi_{\bm{\theta}},t}\rangle-\langle\mathbf{d}_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}^{\lambda},\bm{\delta}^{\varphi}_{\pi_{{\bm{\theta}}^{{}^{\prime}}},t}\rangle\right)$
$\displaystyle=$
$\displaystyle\dfrac{1}{1-\tilde{\gamma}}\sum_{t=0}^{\infty}\gamma^{t}\lambda^{t}D_{t}^{\varphi,(\lambda)}(\pi_{\bm{\theta}},\pi_{{\bm{\theta}}^{{}^{\prime}}}),$
(82)

which requires us to consider the boundedness of the difference
$D_{t}^{\varphi,(\lambda)}(\pi_{\bm{\theta}},\pi_{{\bm{\theta}}^{{}^{\prime}}})$
(81) .

Step 1: Bound the term
$D_{t}^{\varphi,(\lambda)}(\pi_{\bm{\theta}},\pi_{{\bm{\theta}}^{{}^{\prime}}})$
(81).

We rewrite the first term of (81) as follows,

$\displaystyle\langle\mathbf{d}_{\pi_{\bm{\theta}}}^{\lambda},{\bm{\delta}}^{\varphi}_{\pi_{\bm{\theta}},t}\rangle=\langle\mathbf{d}_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}^{\lambda},{\bm{\delta}}^{\varphi}_{\pi_{\bm{\theta}},t}\rangle+\langle\mathbf{d}_{\pi_{\bm{\theta}}}^{\lambda}-\mathbf{d}_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}^{\lambda},{\bm{\delta}}^{\varphi}_{\pi_{\bm{\theta}},t}\rangle,$
(83)

which is bounded by applying Hölder’s inequality to the term
$\langle\mathbf{d}_{\pi_{\bm{\theta}}}^{\lambda}-\mathbf{d}_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}^{\lambda},{\bm{\delta}}^{\varphi}_{\pi_{\bm{\theta}},t}\rangle$,
we rewrite (83) as follows,

$\displaystyle\langle\mathbf{d}_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}^{\lambda},{\bm{\delta}}^{\varphi}_{\pi_{\bm{\theta}},t}\rangle-\|\mathbf{d}_{\pi_{\bm{\theta}}}^{\lambda}-\mathbf{d}_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}^{\lambda}\|_{p}\|{\bm{\delta}}^{\varphi}_{\pi_{\bm{\theta}},t}\|_{q}$
$\displaystyle\leq$
$\displaystyle\langle\mathbf{d}_{\pi_{\bm{\theta}}}^{\lambda},{\bm{\delta}}^{\varphi}_{\pi_{\bm{\theta}},t}\rangle\leq\langle\mathbf{d}_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}^{\lambda},{\bm{\delta}}^{\varphi}_{\pi_{\bm{\theta}},t}\rangle+\|\mathbf{d}_{\pi_{\bm{\theta}}}^{\lambda}-\mathbf{d}_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}^{\lambda}\|_{p}\|{\bm{\delta}}^{\varphi}_{\pi_{\bm{\theta}},t}\|_{q},$
(84)

where $p,q\in[1,\infty)$ and $\frac{1}{p}+\frac{1}{q}=1$. Let

$\epsilon^{\varphi,(\lambda)}_{p,q,t}(\pi_{\bm{\theta}},\pi_{{\bm{\theta}}^{{}^{\prime}}})=:\|\mathbf{d}_{\pi_{\bm{\theta}}}^{\lambda}-\mathbf{d}_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}^{\lambda}\|_{p}\|{\bm{\delta}}^{\varphi}_{\pi_{\bm{\theta}},t}\|_{q},$

then we rewrite Eq.(84) as follows,

$\displaystyle\langle\mathbf{d}_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}^{\lambda},{\bm{\delta}}^{\varphi}_{\pi_{\bm{\theta}},t}\rangle-\epsilon^{\varphi,(\lambda)}_{p,q,t}(\pi_{\bm{\theta}},\pi_{{\bm{\theta}}^{{}^{\prime}}})\leq\langle\mathbf{d}_{\pi_{\bm{\theta}}}^{\lambda},{\bm{\delta}}^{\varphi}_{\pi_{\bm{\theta}},t}\rangle\leq\langle\mathbf{d}_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}^{\lambda},{\bm{\delta}}^{\varphi}_{\pi_{\bm{\theta}},t}\rangle+\epsilon^{\varphi,(\lambda)}_{p,q,t}(\pi_{\bm{\theta}},\pi_{{\bm{\theta}}^{{}^{\prime}}}).$
(85)

Let

$\displaystyle
M_{t}^{\varphi}(\pi_{\bm{\theta}},\pi_{{\bm{\theta}}^{{}^{\prime}}})=:\underbrace{\langle\mathbf{d}_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}^{\lambda},{\bm{\delta}}^{\varphi}_{\pi_{\bm{\theta}},t}\rangle}_{\text{Term-I}}-\underbrace{\langle\mathbf{d}_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}^{\lambda},\bm{\delta}^{\varphi}_{\pi_{{\bm{\theta}}^{{}^{\prime}}},t}\rangle}_{\text{Term-
II}},$ (86)

combining the (81) and (85), we achieve the boundedness of
$D_{t}^{\varphi}(\pi_{\bm{\theta}},\pi_{{\bm{\theta}}^{{}^{\prime}}})$ as
follows

$\displaystyle
M_{t}^{\varphi}(\pi_{\bm{\theta}},\pi_{{\bm{\theta}}^{{}^{\prime}}})-\epsilon^{\varphi,(\lambda)}_{p,q,t}(\pi_{\bm{\theta}},\pi_{{\bm{\theta}}^{{}^{\prime}}})\leq
D_{t}^{\varphi}(\pi_{\bm{\theta}},\pi_{{\bm{\theta}}^{{}^{\prime}}})\leq