# CUP: A Conservative Update Policy Algorithm for Safe Reinforcement Learning
111L.Yang do partial work of this submission when studying at Zhejiang
University, and L.Yang now is with Peking University.

Long Yang  School of Artificial Intelligence, Peking University, Beijing,
China  College of Computer Science and Technology, Zhejiang University, China
Jiaming Ji  College of Computer Science and Technology, Zhejiang University,
China  Juntao Dai  College of Computer Science and Technology, Zhejiang
University, China  Linrui Zhang  Tsinghua University,Beijing,China  Yu Zhang
Netease Games AI Lab, HangZhou, China  Pengfei Li  College of Computer Science
and Technology, Zhejiang University, China  Gang Pan  College of Computer
Science and Technology, Zhejiang University, China

###### Abstract

Safe reinforcement learning (RL) is still very challenging since it requires
the agent to consider both return maximization and safe exploration. In this
paper, we propose CUP, a Conservative Update Policy algorithm with a
theoretical safety guarantee. We derive the CUP based on the new proposed
performance bounds and surrogate functions. Although using bounds as surrogate
functions to design safe RL algorithms have appeared in some existing works,
we develop them at least three aspects: (i) We provide a rigorous theoretical
analysis to extend the surrogate functions to generalized advantage estimator
(GAE). GAE significantly reduces variance empirically while maintaining a
tolerable level of bias, which is an efficient step for us to design CUP; (ii)
The proposed bounds are tighter than existing works, i.e., using the proposed
bounds as surrogate functions are better local approximations to the objective
and safety constraints. (iii) The proposed CUP provides a non-convex
implementation via first-order optimizers, which does not depend on any convex
approximation. Finally, extensive experiments show the effectiveness of CUP
where the agent satisfies safe constraints. We have opened the source code of
CUP at https://github.com/RL-boxes/Safe-RL.

##  1 Introduction

Reinforcement learning (RL) [Sutton and Barto, 1998] has achieved significant
successes in many fields [Mnih et al., 2015, Silver et al., 2017, OpenAI,
2019, Afsar et al., 2021],Dota [OpenAI, 2019], robotics [Deisenroth et al.,
2013], playing Go [Silver et al., 2016, Silver et al., 2017], recommendation
system [Afsar et al., 2021], and Starcraft [Vinyals et al., 2019]. 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., 2020b, 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., 2020b, 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 Fisher information matrix, which causes their algorithms to
require a costly computation for each update when solving high-dimensional RL
problems.

###  1.1 Our Main Work

To address above problems, we propose the _conservative update policy_ (CUP)
algorithm with a theoretical safety guarantee. We derive the CUP bases on new
surrogate functions, 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 3.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 bound to replace objective or constraints has
appeared in some existing works (e.g., [Kakade and Langford, 2002, Schulman et
al., 2015, Achiam et al., 2017]), Theorem 3.1 improves their bounds at least
two aspects: (i) Firstly, our rigorous theoretical analysis extends the bound
w.r.t. generalized advantage estimator (GAE) [Schulman et al., 2016]. GAE
significantly reduces variance while maintains a tolerable level of bias,
which is one of the critical steps for us to design efficient algorithms in
the later section. Although [Zhang et al., 2020, Kang et al., 2021] have
applied GAE to solve safe RL problems, their approaches are empirical and lack
a theoretical analysis w.r.t. GAE. Thus, our result provides a theory to
illustrate the effectiveness of the work [Zhang et al., 2020, Kang et al.,
2021]. (ii) Our new bounds in refine classic difference bounds. For example,
our bounds are more compact than [Achiam et al., 2017], i,e., using our new
bounds as surrogate functions are better local approximations to the objective
and constraints. Besides, the surrogate functions w.r.t. our new bounds are
more accessible to be estimated from the samples than the approaches appears
in [Kakade and Langford, 2002, Schulman et al., 2015]), for more discussions,
please see Remark 3.1.

In Section 4, we provide the necessary details of the proposed CUP. The CUP
contains two steps: it performs a policy improvement at first, then it
projects the policy back onto the safe region to reconcile the constraint
violation. Theorem 4.1 shows a lower bound on policy improvement and an upper
bound on constraint violation for CPU at each update. Notably, the result in
Theorem 4.1 shows the bound of CUP is more compact than state-of-the-art safe
RL algorithms: CPO [Achiam et al., 2017, Proposition 1-2], PCPO [Yang et al.,
2020b, Theorem 1] and FOCOPS [Zhang et al., 2020], which provides a partial
explanation for why CUP is so good in practice. For more discussions, please
refer to Remark 4.1. Finally, we provide a practical implementation of sample-
based CUP. Such an implementation allows us to use deep neural networks to
train a model. Mainly, CUP does not depend on any convex approximation for
objective and constraints, and it optimizes the objective according to the
first-order optimizer. 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}$ 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,
$\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}})$:

$\displaystyle J(\pi_{\bm{\theta}})=\operatorname{\mathbb{E}}_{s\sim
d^{\rho_{0}}_{\pi_{\bm{\theta}}}(\cdot)}[V_{\pi_{\bm{\theta}}}(s)].$ (1)

###  2.1 Policy Gradient and 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 $\nabla J(\pi_{\bm{\theta}})$. The work [Schulman et
al., 2016] summarize several different related expressions for the policy
gradient:

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

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 (GAE)
$\hat{A}^{\text{GAE}(\gamma,\lambda)}_{t}(s_{t},a_{t})$ to replace $\Psi_{t}$:
for any $\lambda\in[0,1]$,

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

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}})=\operatorname{\mathbb{E}}_{\pi_{\bm{\theta}}}\left[\sum_{t=0}^{\infty}\gamma^{t}c_{i}(s_{t},a_{t})\right]$,
the feasible policy set $\Pi_{\mathcal{C}}$ is defined as:

$\Pi_{\mathcal{C}}=\bigcap_{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 safe RL is to search the optimal policy $\pi_{\star}$ s.t.

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

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 w.r.t. auxiliary cost function $c$:

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

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 certain surrogate functions w.r.t. the objective and
cost function, which are theoretical foundations for us to design efficient
algorithms to improve policy performance and satisfy constraints.
Additionally, those bounds refine or extend some existing works (e.g., [Kakade
and Langford, 2002, Schulman et al., 2015, Achiam et al., 2017]) to GAE case
that significantly reduces variance while maintains a tolerable level of bias,
which is one of the key steps for us to propose efficient algorithms in the
later section.

Before we present our new bounds, let us revisit a classic result about policy
performance difference from [Kakade and Langford, 2002], i.e., the next
Eq.(6),

$\displaystyle
J(\pi_{{\bm{\theta}}})-J(\pi_{{\bm{\theta}}^{{}^{\prime}}})=(1-\gamma)^{-1}\operatorname{\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)

Eq.(6) 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 (6), we rewrite
the policy optimization (4) as follows

$\displaystyle\pi_{\star}=\arg\max_{\pi_{\bm{\theta}}\in\Pi_{\mathcal{C}}}\operatorname{\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].$
(7)

However, Eq.(6) or (7) 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, our new bound refines the result (6), which provide the
sights for surrogate functions to solve safe RL problem (4). For more
discussions about the difference between our new bound and Eq.(6), see Remark
3.1.

###  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 w.r.t. $\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)$: $\forall
s\in\mathcal{S}$,

$\displaystyle\delta^{\varphi}_{\pi_{\bm{\theta}},t}(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}}{\operatorname{\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}}{\operatorname{\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 corresponding 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).$

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)$:

$\displaystyle{d}_{\pi_{\bm{\theta}}}^{\lambda}(s)$
$\displaystyle=\operatorname{\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]$
$\displaystyle=\dfrac{1-\gamma}{1-\gamma\lambda}\operatorname{\mathbb{E}}_{s_{0}\sim\rho_{0}(\cdot)}\left[\sum_{t=0}^{\infty}\left(\dfrac{\gamma(1-\lambda)}{1-\gamma\lambda}\right)^{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}=\prod_{i=1}^{t}\mathbf{P}^{(\lambda)}_{\pi_{\bm{\theta}}}=\underbrace{\mathbf{P}^{(\lambda)}_{\pi_{\bm{\theta}}}\cdot\mathbf{P}^{(\lambda)}_{\pi_{\bm{\theta}}}\cdots\mathbf{P}^{(\lambda)}_{\pi_{\bm{\theta}}}}_{t~{}~{}\text{times}}.$

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 3.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}\operatorname{\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 w.r.t. 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 _tight_ , 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}}\operatorname{\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 F.1 (see Appendix F), 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{1}{1-\tilde{\gamma}}\cdot\dfrac{\gamma(1-\lambda)\epsilon^{\varphi}_{\pi_{\bm{\theta}},t}}{\left|1-2\gamma\lambda|\mathcal{S}||\mathcal{A}|\right|}\operatorname{\mathbb{E}}_{s\sim
d_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}^{\lambda}(\cdot)}\left[2D_{\text{TV}}(\pi_{{\bm{\theta}}^{{}^{\prime}}},\pi_{\bm{\theta}})[s]\right],$

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

$2D_{\text{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 3.1 implies a lower bound of performance difference, which
illustrates the worse case of approximation error, we present it in
Proposition 3.2.

######  Proposition 3.2 (Worse case approximation error).

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 the following bound holds

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

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}\operatorname{\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\gamma\epsilon^{V}_{\pi_{\bm{\theta}}}(\pi_{{\bm{\theta}}^{{}^{\prime}}})D_{\text{TV}}(\pi_{{\bm{\theta}}^{{}^{\prime}}},\pi_{\bm{\theta}})[s]\right].$
(12)

Let us review [Achiam et al., 2017, Corollary 1], which shows

$\displaystyle
J(\pi_{\bm{\theta}})-J(\pi_{{\bm{\theta}}^{{}^{\prime}}})\geq\frac{1}{1-\gamma}\operatorname{\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\frac{\gamma\epsilon^{V}_{\pi_{\bm{\theta}}}(\pi_{{\bm{\theta}}^{{}^{\prime}}})}{1-\gamma}D_{\text{TV}}(\pi_{{\bm{\theta}}^{{}^{\prime}}},\pi_{\bm{\theta}})[s]\right].$
(13)

Comparing (12) to (13), our new bound (12) is slightly tighter than the bound
shown by the work [Achiam et al., 2017], concretely, our result improves the
bound (13) by a factor $\dfrac{1}{1-\gamma}$. The bound (13) has been used as
a surrogate function for
$J(\pi_{\bm{\theta}})-J(\pi_{{\bm{\theta}}^{{}^{\prime}}})$, and this idea has
been developed as _constrained policy optimization_ by extensive works (e.g.,
[Koller et al., 2018, Zhang et al., 2020, Yang et al., 2020a, Yang et al.,
2020b, Zanger et al., 2021]). Since the refined bound (11) contains GAE
technique that significantly reduces variance while maintains a tolerable
level of bias [Schulman et al., 2016], which implies using the bound (11) as a
surrogate function could improve performance potentially.

######  Remark 3.1 (Comparison with [Kakade and Langford, 2002]).

The result (11) develops the classic performance difference (6) at least two
aspects. Firstly, the bound (11) extends from the advantage
$A_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}$ (6) to GAE function
$A_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}^{\emph{GAE}(\gamma,\lambda)}$.
Secondly, the following term in Eq.(11):

$\displaystyle\dfrac{1}{1-\tilde{\gamma}}\operatorname{\mathbb{E}}_{s\sim{d}_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}^{\lambda}(\cdot),a\sim\pi_{\bm{\theta}}(\cdot|s)}\left[A^{\emph{GAE}(\gamma,\lambda)}_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}(s,a)\right]$
(14)

is an approximation for the difference
$J(\pi_{\bm{\theta}})-J(\pi_{{\bm{\theta}}^{{}^{\prime}}})$, while Eq.(6)
shows an identity for difference
$J(\pi_{\bm{\theta}})-J(\pi_{{\bm{\theta}}^{{}^{\prime}}})$. It seems that
Eq.(6) is a natural objective for return maximization, however, Eq.(6) is very
intractable for sampling-based policy optimization since Eq.(6) requires the
data comes from a the policy $\pi_{\bm{\theta}}$ that needed to be learned.
The approximation (14) solves this problem by the expectation over the state
distribution $d_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}^{\lambda}(\cdot)$ w.r.t.
policy $\pi_{{\bm{\theta}}^{{}^{\prime}}}$ and action distribution of another
policy $\pi_{\bm{\theta}}$. Thus, bound (11) provides a tractable objective
for sample-based optimization.

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

######  Proposition 3.3.

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 the following bound holds

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

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

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

$\displaystyle\operatorname{\mathbb{E}}_{s\sim{d}_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}^{\lambda}(\cdot)}\left[D_{\text{TV}}(\pi_{{\bm{\theta}}^{{}^{\prime}}},\pi_{\bm{\theta}})[s]\right]\leq$
$\displaystyle\operatorname{\mathbb{E}}_{s\sim{d}_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}^{\lambda}(\cdot)}\left[\sqrt{\frac{1}{2}\text{KL}(\pi_{{\bm{\theta}}^{{}^{\prime}}},\pi_{\bm{\theta}})[s]}\right]\leq\sqrt{\frac{1}{2}\operatorname{\mathbb{E}}_{s\sim{d}_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}^{\lambda}(\cdot)}\left[\text{KL}(\pi_{{\bm{\theta}}^{{}^{\prime}}},\pi_{\bm{\theta}})[s]\right]},$
(16)

where $\text{KL}(\cdot,\cdot)$ is KL-divergence, and

$\text{KL}(\pi_{{\bm{\theta}}^{{}^{\prime}}},\pi_{\bm{\theta}})[s]=\text{KL}(\pi_{{\bm{\theta}}^{{}^{\prime}}}(\cdot|s),\pi_{\bm{\theta}}(\cdot|s));$

the first inequality follows Pinsker’s inequality [Csiszár and Körner, 2011]
and the second inequality follows Jensen’s inequality. According to (16), we
obtain the next Proposition 3.4.

######  Proposition 3.4.

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

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

##  4 CUP: Conservative Update Policy

According to the bounds in Proposition 3.2-3.4, we develop new surrogate
functions to replace the objective and constraints. Inspired by two recent
works [Yang et al., 2020b, Zhang et al., 2020], we propose the CUP
(conservative update policy) algorithm that is a two-step approach contains
_performance improvement_ and _projection_. Theorem 4.1 shows the proposed CUP
guarantees the policy improvement and safe constraints.

###  4.1 Methodology

Step 1: Performance Improvement.

According to Proposition 3.2 and Proposition 3.4, for an appropriate
coefficient $\alpha_{k}$, we update policy as follows,

$\displaystyle\pi_{{\bm{\theta}}_{k+\frac{1}{2}}}$
$\displaystyle=\arg\max_{\pi_{{\bm{\theta}}}\in\Pi_{{\bm{\theta}}}}\left\\{\operatorname{\mathbb{E}}_{s\sim{d}_{\pi_{\bm{\theta}_{k}}}^{\lambda}(\cdot),a\sim\pi_{\bm{\theta}}(\cdot|s)}[A^{\text{GAE}(\gamma,\lambda)}_{{\pi_{\bm{\theta}_{k}}}}(s,a)]-\alpha_{k}\sqrt{\operatorname{\mathbb{E}}_{s\sim{d}_{{\pi_{\bm{\theta}_{k}}}}^{\lambda}(\cdot)}\left[\text{KL}(\pi_{\bm{\theta}_{k}},\pi_{\bm{\theta}})[s]\right]}\right\\}$
(17)
$\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}}{\operatorname{\mathbb{E}}}\left[\frac{\pi_{\bm{\theta}}(a|s)}{\pi_{{\bm{\theta}}_{k}}(a|s)}A^{\text{GAE}(\gamma,\lambda)}_{{\pi_{\bm{\theta}_{k}}}}(s,a)\right]-\alpha_{k}\sqrt{\operatorname{\mathbb{E}}_{s\sim{d}_{{\pi_{\bm{\theta}_{k}}}}^{\lambda}(\cdot)}\left[\text{KL}(\pi_{\bm{\theta}_{k}},\pi_{\bm{\theta}})[s]\right]}\right\\}.$
(18)

We replace (17) with an importance sampling with respect to
$\pi_{\bm{\theta}_{k}}$ to obtain the expectation (18), and all the remains is
to replace the expectation (18) by sample averages according to the
trajectories collected by $\pi_{\bm{\theta}_{k}}$.

Step 2: Projection.

According to Proposition 3.3 and Proposition 3.4, for an appropriate
coefficient $\beta_{k}$, we project the policy
$\pi_{{\bm{\theta}}_{k+\frac{1}{2}}}$ onto the safe constraint set.
Concretely, we use a measure $D(\cdot,\cdot)$ (e.g., KL divergence or
$\ell_{2}$-norm) to minimize distance between
$\pi_{{\bm{\theta}}_{k+\frac{1}{2}}}$ and $\pi_{\bm{\theta}}$, and require the
new policy satisfies the safe constraint:

$\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),$
(19)
$\displaystyle\text{s.t.}~{}J^{c}(\pi_{{\bm{\theta}}_{k}})+\dfrac{1}{1-\tilde{\gamma}}\operatorname{\mathbb{E}}_{s\sim{d}_{\pi_{\bm{\theta}_{k}}}^{\lambda}(\cdot),a\sim\pi_{\bm{\theta}}(\cdot|s)}\left[A^{\text{GAE}(\gamma,\lambda)}_{{\pi_{\bm{\theta}_{k}}},C}(s,a)\right]+\beta_{k}\sqrt{\operatorname{\mathbb{E}}_{s\sim{d}_{{\pi_{\bm{\theta}_{k}}}}^{\lambda}(\cdot)}\left[\text{KL}(\pi_{\bm{\theta}_{k}},\pi_{\bm{\theta}})[s]\right]}\leq
b.$

Until now, the particular choice of surrogate function is heuristically
motivated, we show the policy and safe constraint guarantee of the proposed
CUP in Theorem 4.1, and its proof shown in Appendix G.

######  Theorem 4.1.

Let
$\chi_{k}=\operatorname{\mathbb{E}}_{s\sim{d}_{{\pi_{\bm{\theta}_{k}}}}^{\lambda}(\cdot)}\left[\emph{KL}\left(\pi_{\bm{\theta}_{k}},\pi_{\bm{\theta}_{k+\frac{1}{2}}}\right)[s]\right]$,
if $\pi_{\bm{\theta}_{k}}$ and $\pi_{\bm{\theta}_{k+1}}$ are related to
(18)-(19), 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-\frac{\gamma(1-\lambda)\alpha_{k}\sqrt{2\chi_{k}}\epsilon^{V}_{\pi_{\bm{\theta}}}(\pi_{{\bm{\theta}}^{{}^{\prime}}})}{(1-\gamma)\left|1-2\gamma\lambda|\mathcal{S}||\mathcal{A}|\right|},J^{c}(\pi_{\bm{\theta}_{k+1}})\leq
b+\frac{\gamma(1-\lambda)\beta_{k}\sqrt{2\chi_{k}}\epsilon^{C}_{\pi_{\bm{\theta}}}(\pi_{{\bm{\theta}}^{{}^{\prime}}})}{(1-\gamma)\left|1-2\gamma\lambda|\mathcal{S}||\mathcal{A}|\right|}.$

######  Remark 4.1.

Let $\lambda\rightarrow 0$, according to Theorem 4.1, the performance and cost
constraint of CUP satisfies

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

The bounds of CUP in (20) achieves at
$\mathcal{O}(\frac{\alpha_{k}\gamma}{1-\gamma})$ or
$\mathcal{O}(\frac{\beta_{k}\gamma}{1-\gamma})$, which is more tight than the
bounds of CPO [Achiam et al., 2017, Proposition 1-2], PCPO [Yang et al.,
2020b, Theorem 1] and FOCOPS [Zhang et al., 2020] where their bounds achieve
at $\mathcal{O}(\frac{\gamma}{(1-\gamma)^{2}})$.

Practical Implementation

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

We denote the empirical KL-divergence w.r.t $\pi_{\bm{\theta}}$ and
$\pi_{{\bm{\theta}}^{{}^{\prime}}}$ as follows,

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

Let $\\{(s_{t},a_{t},r_{t+1},c_{t+1})\\}_{t=1}^{T}\sim\pi_{\bm{\theta}_{k}}$,
we update performance improvement (18) step 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\\}$
$\displaystyle\hat{\mathcal{L}}_{\text{R}}(\pi_{\bm{\theta}},\pi_{{\bm{\theta}}_{k}})$
$\displaystyle=\frac{1}{T}\sum_{t=1}^{N}\dfrac{\pi_{\bm{\theta}}(a_{t}|s_{t})}{\pi_{{\bm{\theta}}_{k}}(a_{t}|s_{t})}\hat{A}_{t}-\alpha_{k}\sqrt{\hat{D}_{\text{KL}}(\pi_{{\bm{\theta}}_{k}},\pi_{{\bm{\theta}}})},$

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

Then we update projection step by replacing the distance function $D$ by KL-
divergence, and we solve the constraint problem (19) 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{\mathcal{L}}_{\text{c}}\left(\pi_{\bm{\theta}},\pi_{{\bm{\theta}}_{k}},{\bm{\theta}}_{k+\frac{1}{2}}\right)\right\\}$
$\displaystyle\hat{\mathcal{L}}_{\text{c}}\left(\pi_{\bm{\theta}},\pi_{{\bm{\theta}}_{k}},{\bm{\theta}}_{k+\frac{1}{2}}\right)=\hat{D}_{\text{KL}}(\pi_{{\bm{\theta}}_{k+\frac{1}{2}}},\pi_{{\bm{\theta}}})+\nu\hat{C}(\pi_{\bm{\theta}},\pi_{{\bm{\theta}}_{k}}),$

where the empirical constraint function

$\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}_{\text{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 correspondingly.

Due to the limitation of space, we have presented all the details for the
implementation of CUP in Appendix B and Algorithm 1.

##  5 Related Work

This section reviews some typical ways to solve safe reinforcement learning:
local policy search, Lagrangian approach, and constrained policy optimization
(CPO). We mainly focus on CPO since those algorithms also use surrogate
functions to replace the objective and constraints, which resembles the
proposed CUP. We provide more comparisons and discussion in Appendix C and
Table 2.

Local Policy Search and Lagrangian Approach. A direct way to solve CMDP (4) 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,$
(21)

where $\delta$ is a positive scalar, $D(\cdot,\cdot)$ is some distance
measure. For practice, the local policy search (21) 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, when updating policy according to samples, local policy search (21)
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, Yang et al., 2021a]. Thus, local policy search (21) looks simple,
but it is impractical for high-dimension policy optimization.

The standard way to solve CMDP (4) is Lagrangian approach [Chow et al., 2017]
that is also known as primal-dual policy optimization [Chen et al., 2021]:

$\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\\}.$
(22)

Although extensive canonical algorithms are proposed to solve problem (22),
e.g., [Liang et al., 2018, Tessler et al., 2019, Paternain et al., 2019, Le et
al., 2019, Russel et al., 2020, Xu et al., 2020, Satija et al., 2020, Chen et
al., 2021], the policy updated by Lagrangian approach may be infeasible w.r.t.
CMDP (4). 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, CPO [Achiam et al., 2017]
suggests 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}}$:

$\displaystyle\pi_{{\bm{\theta}}_{k+1}}=\arg\max_{\pi_{{\bm{\theta}}}\in\Pi_{{\bm{\theta}}}}~{}~{}~{}~{}\operatorname{\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]$
(23)
$\displaystyle\text{s.t.}~{}~{}J^{c}(\pi_{{\bm{\theta}}_{k}})+\frac{1}{1-\gamma}\operatorname{\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,$ (24)
$\displaystyle\bar{D}_{\text{KL}}(\pi_{{\bm{\theta}}},\pi_{{\bm{\theta}}_{k}})=\operatorname{\mathbb{E}}_{s\sim
d^{\rho_{0}}_{\pi_{{\bm{\theta}}_{k}}}(\cdot)}[\text{KL}(\pi_{{\bm{\theta}}},\pi_{{\bm{\theta}}_{k}})[s]]\leq\delta.$
(25)

Existing recent works (e.g., [Achiam et al., 2017, Vuong et al., 2019, Yang et
al., 2020b, 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}})$
Eq.(23)-(25). Concretely, according to (6), [Achiam et al., 2017] suggest to
use first-order Taylor expansion to replace (23)-(24), use second-oder
approximation to replace (25). Such first-order and second-order
approximations turn a non-convex problem (23)-(25) 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 (23)-(25) 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.
Later, [Yang et al., 2020b] propose projected-based constrained policy
optimization (PCPO) that also uses second-order approximation, which also
results in an expensive computation.

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.

Figure 1: Performance for CPO, PPO-L, TRPO-L, FOCOPS and CUP over 10 seeds.
The first row shows the learning curves of objective return, and the second
row shows the curves of constraint return. The x-axis is training iteration.
CUP quickly stabilizes the constraint return around the limit value while
converging the objective return to higher values faster.

Environment CPO TRPO-L PPO-L FOCOPS CUP Ant-v3 Return $1030.17\pm 8.15$
$480.86\pm 161.05$ $1012.02\pm 17.26$ $1662.53\pm 17.40$
$\boldsymbol{1743.66\pm 40.5}$ (103.12) 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}$ $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$ $1687.72\pm 24.38$
$\boldsymbol{2025.56\pm 122.35}$ (82.75) 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}$
${\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$
$35.58\pm 5.68$ $28.15\pm 4.30$ $\boldsymbol{33.38\pm 0.54}$ (24.52)
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>4.16}$ $23.31\pm 0.052$ Humanoid-v0 Return $326.95\pm 16.00$ $307.71\pm 24.71$
$322.11\pm 25.54$ $542.5\pm 4.76$ $\boldsymbol{1066.83\pm 266.12}$ (20.14)
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}$ $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$ $713.04\pm 9.25$
$\boldsymbol{768.65\pm 63.70}$ (50.00) 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$ $47.73\pm 0.64$ $48.23\pm 0.65$

Table 1: Average results for CPO, PPO-L, TRPO-L, FOCOPS and CUP over 10 seeds
after 500 iterations. The agent interacts with the environment 5000 times per
iteration. Constraint limit are in brackets under the environment names.

##  6 Experiment

In this section, we verify the effectiveness and stability of CUP in terms of
policy improvement while satisfying safety. We aim to answer the following
three issues:

(I). Does CUP satisfy the safety constraints in different environments? For
the same environment with different cost limit, Does CUP also performs well?

(II). How does CUP compare to the state-of-the-art safe RL algorithms? Does
CUP achieve higher rewards under the constraint of cost threshold?

(III). Does CUP play a sensibility during the hyper-parameters (e.g., step-
size $\nu$, the coefficient $\alpha$ with respect KL-divergence) tuning
processing?

Environments: 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].

Figure 2: Cost constraint with respect to hyper-parameter $\nu$ (defined in
Projection step).

Baseline Algorithms: Baselines includes CPO[Achiam et al., 2017], 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 [bertsekas1997nonlinear], which
applies adaptive penalty coefficients to satisfy the constraint.

###  6.1 Evaluation CUP and Comparison Analysis

We have shown the Learning curves for CUP, and other baselines in Figure 1,
and Table 1 summarizes the performance of all algorithms. We find that CUP and
FOCOPS successfully enforce the constraints in all experiments. In most cases,
the traces of their constraint almost coincide with the dashed black line of
the limit. By contrast, the others frequently suffer from over or under the
correction. Although it seems that being below the limit also satisfies the
constraint, this usually results in a poor return. The initial policy is not
guaranteed to be feasible, such as in the Swimmer-v3 environment. We observed
that CUP brings the policy back to the feasible range faster than other
baselines. From Table 1, we know although PPO-L achieves a reward of $35.58\pm
5.68$ outperforms CUP in Swimmer-v3, PPO-L obtain a cost with $54.91\pm 3.93$
that violates the cost limit of $24.52$ significantly, which implies PPO-L
learns a dangerous policy under this setting.

On the other hand, Figure 1 shows that CUP generally gains higher returns than
different baselines while enforcing the cost constraint.

In contrast, after equal iterations, CUP has a greater speed of stabilizing
the constraint return around to the limit value and is quicker to find
feasible policies to gain a more significant objective return.

###  6.2 Sensitivity Analysis for Hyper-Parameters Tuning

Hyper-parameters tuning is necessary to achieve efficient and stable policy
improvement and enforce constraints. Now, we investigate the performance with
respect to the parameters: $\nu$, step-size $\alpha$, and cost limit $b$. In
Figure 2-4, after exploring the influence of hyper-parameters introduced by
CUP methods under different experimental settings, we discover that the
performance of CUP is robust to hyper-parameters tuning.

We have visualized the changes of cost constraint with respect to $\nu$ over
different MuJoCo in Figure 2. From Figure 2 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 on
the Humanoid environment. 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 result shown in Figure 2 is
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 learning a safe
policy.

Furthermore, we investigate the influence of reward performance and cost
constraint with respect to the penalty factor $\alpha$, see Figure 3. Results
show that the performance of CUP is still very stable for different settings
of $\alpha$, where we run $\alpha$ among $\\{0.1,0.15,0.2,0.25,0.3\\}$.
Additionally, 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, we compare different cost limit $b$ to verify the sensitiveness of
CUP. We have shown the results in Figure 4. 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\\}$. As illustrated in Figure 4. we
demonstrate that the CUP algorithm continuously improves the policy under the
constrain. This experiment implies CUP is robust to different cost limit
settings, and CUP is scalable to various safe RL tasks.

Figure 3: Performance with respect to penalty factor $\alpha$. Figure 4:
Performance with respect to cost limit.

##  7 Conclusion

This paper proposes the CUP algorithm with a theoretical safety guarantee. We
derive the CUP based on some new proposed surrogate functions with respect to
objective and constraints, and the practical implementation of CUP does not
depend on any convex approximation. Extensive experiments on continuous
control tasks show the effectiveness of CUP where the agent satisfies safe
constraints.

## References

  * [Achiam et al., 2017] Achiam, J., Held, D., Tamar, A., and Abbeel, P. (2017).  Constrained policy optimization.  In Proceedings of International Conference on Machine Learning (ICML), volume 70, pages 22–31.
  * [Afsar et al., 2021] Afsar, M. M., Crump, T., and Far, B. (2021).  Reinforcement learning based recommender systems: A survey.  arXiv preprint arXiv:2101.06286.
  * [Altman, 1999] Altman, E. (1999).  Constrained Markov decision processes.  CRC Press.
  * [Bellman, 1957] Bellman, R. (1957).  A markovian decision process.  Journal of mathematics and mechanics, 6(5):679–684.
  * [Bharadhwaj et al., 2021] Bharadhwaj, H., Kumar, A., Rhinehart, N., Levine, S., Shkurti, F., and Garg, A. (2021).  Conservative safety critics for exploration.  In International Conference on Learning Representations (ICLR).
  * [Bisi et al., 2020] Bisi, L., Sabbioni, L., Vittori, E., Papini, M., and Restelli, M. (2020).  Risk-averse trust region optimization for reward-volatility reduction.  In Bessiere, C., editor, Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI-20, pages 4583–4589.
  * [Brockman et al., 2016] Brockman, G., Cheung, V., Pettersson, L., Schneider, J., Schulman, J., Tang, J., and Zaremba, W. (2016).  Openai gym.  arXiv preprint arXiv:1606.01540.
  * [Chen et al., 2021] Chen, Y., Dong, J., and Wang, Z. (2021).  A primal-dual approach to constrained markov decision processes.  arXiv preprint arXiv:2101.10895.
  * [Chow et al., 2017] Chow, Y., Ghavamzadeh, M., Janson, L., and Pavone, M. (2017).  Risk-constrained reinforcement learning with percentile risk criteria.  The Journal of Machine Learning Research, 18(1):6070–6120.
  * [Chow et al., 2018] Chow, Y., Nachum, O., Duenez-Guzman, E., and Ghavamzadeh, M. (2018).  A lyapunov-based approach to safe reinforcement learning.  In Advances in Neural Information Processing Systems (NeurIPS).
  * [Csiszár and Körner, 2011] Csiszár, I. and Körner, J. (2011).  Information theory: coding theorems for discrete memoryless systems.  Cambridge University Press.
  * [Deisenroth et al., 2013] Deisenroth, M. P., Neumann, G., and Peters, J. (2013).  A survey on policy search for robotics.  Foundations and Trends® in Machine Learning.
  * [Duan et al., 2016] Duan, Y., Chen, X., Houthooft, R., Schulman, J., and Abbeel, P. (2016).  Benchmarking deep reinforcement learning for continuous control.  In International Conference on Machine Learning (ICML), pages 1329–1338.
  * [Greensmith et al., 2004] Greensmith, E., Bartlett, P. L., and Baxter, J. (2004).  Variance reduction techniques for gradient estimates in reinforcement learning.  Journal of Machine Learning Research (JMLR), 5(Nov):1471–1530.
  * [Han et al., 2020] Han, M., Tian, Yuanand Zhang, L., Wang, J., and Pan, W. (2020).  Reinforcement learning control of constrained dynamic systems with uniformly ultimate boundedness stability guarantee.  arXiv preprint arXiv:2011.06882.
  * [Kakade and Langford, 2002] Kakade, S. and Langford, J. (2002).  Approximately optimal approximate reinforcement learning.  In Proceedings of International Conference on Machine Learning (ICML), volume 2, pages 267–274.
  * [Kang et al., 2021] Kang, B., Mannor, S., and Feng, J. (2021).  Learning safe policies with cost-sensitive advantage estimation.  https://openreview.net/forum?id=uVnhiRaW3J.
  * [Koller et al., 2018] Koller, T., Berkenkamp, F., Turchetta, M., and Krause, A. (2018).  Learning-based model predictive control for safe exploration.  In Conference on Decision and Control (CDC), pages 6059–6066. IEEE.
  * [Le et al., 2019] Le, H., Voloshin, C., and Yue, Y. (2019).  Batch policy learning under constraints.  In International Conference on Machine Learning (ICML), pages 3703–3712.
  * [Liang et al., 2018] Liang, Q., Que, F., and Modiano, E. (2018).  Accelerated primal-dual policy optimization for safe reinforcement learning.  arXiv preprint arXiv:1802.06480.
  * [Mnih et al., 2015] Mnih, V., Kavukcuoglu, K., Silver, D., Rusu, A. A., Veness, J., Bellemare, M. G., Graves, A., Riedmiller, M., Fidjeland, A. K., Ostrovski, G., et al. (2015).  Human-level control through deep reinforcement learning.  Nature, 518(7540):529.
  * [OpenAI, 2019] OpenAI (2019).  Openai five defeats dota 2 world champions.  https://openai.com/blog/openai-five-defeats-dota-2-world-champions/.
  * [Paternain et al., 2019] Paternain, S., Chamon, L. F., Calvo-Fullana, M., and Ribeiro, A. (2019).  Constrained reinforcement learning has zero duality gap.  In Advances in Neural Information Processing Systems (NeurIPS).
  * [Peters and Schaal, 2008] Peters, J. and Schaal, S. (2008).  Reinforcement learning of motor skills with policy gradients.  Neural Netw, 21(4):682–697.
  * [Pirotta et al., 2013] Pirotta, M., Restelli, M., Pecorino, A., and Calandriello, D. (2013).  Safe policy iteration.  In International Conference on Machine Learning (ICML), pages 307–315.
  * [Puterman, 2014] Puterman, M. L. (2014).  Markov decision processes: discrete stochastic dynamic programming.  John Wiley & Sons.
  * [Ray et al., 2019] Ray, A., Achiam, J., and Amodei, D. (2019).  Benchmarking Safe Exploration in Deep Reinforcement Learning.
  * [Russel et al., 2020] Russel, R. H., Benosman, M., and Van Baar, J. (2020).  Robust constrained-mdps: Soft-constrained robust policy optimization under model uncertainty.  arXiv preprint arXiv:2010.04870.
  * [Satija et al., 2020] Satija, H., Amortila, P., and Pineau, J. (2020).  Constrained markov decision processes via backward value functions.  In International Conference on Machine Learning (ICML), pages 8502–8511.
  * [Schulman et al., 2015] Schulman, J., Levine, S., Abbeel, P., Jordan, M., and Moritz, P. (2015).  Trust region policy optimization.  In International Conference on Machine Learning (ICML), pages 1889–1897.
  * [Schulman et al., 2016] Schulman, J., Moritz, P., Levine, S., Jordan, M., and Abbeel, P. (2016).  High-dimensional continuous control using generalized advantage estimation.  International Conference on Learning Representations (ICLR).
  * [Schulman et al., 2017] Schulman, J., Wolski, F., Dhariwal, P., Radford, A., and Klimov, O. (2017).  Proximal policy optimization algorithms.  arXiv preprint arXiv:1707.06347.
  * [Silver et al., 2016] Silver, D., Huang, A., Maddison, C. J., Guez, A., Sifre, L., Van Den Driessche, G., Schrittwieser, J., Antonoglou, I., Panneershelvam, V., Lanctot, M., et al. (2016).  Mastering the game of go with deep neural networks and tree search.  nature, 529(7587):484.
  * [Silver et al., 2017] Silver, D., Schrittwieser, J., Simonyan, K., Antonoglou, I., Huang, A., Guez, A., Hubert, T., Baker, L., Lai, M., Bolton, A., et al. (2017).  Mastering the game of go without human knowledge.  Nature, 550(7676):354.
  * [Süli and Mayers, 2003] Süli, E. and Mayers, D. F. (2003).  An introduction to numerical analysis.  Cambridge university press.
  * [Sutton and Barto, 1998] Sutton, R. S. and Barto, A. G. (1998).  Reinforcement learning: An introduction.  MIT press.
  * [Sutton et al., 2000] Sutton, R. S., McAllester, D. A., Singh, S. P., and Mansour, Y. (2000).  Policy gradient methods for reinforcement learning with function approximation.  In Advances in Neural Information Processing Systems (NeurIPS), pages 1057–1063.
  * [Tessler et al., 2019] Tessler, C., Mankowitz, D. J., and Mannor, S. (2019).  Reward constrained policy optimization.  International Conference on Learning Representation (ICLR).
  * [Todorov et al., 2012] Todorov, E., Erez, T., and Tassa, Y. (2012).  Mujoco: A physics engine for model-based control.  In 2012 IEEE/RSJ International Conference on Intelligent Robots and Systems, pages 5026–5033. IEEE.
  * [Vinyals et al., 2019] Vinyals, O., Babuschkin, I., Chung, J., Mathieu, M., Jaderberg, M., Czarnecki, W. M., Dudzik, A., Huang, A., Georgiev, P., Powell, R., et al. (2019).  Alphastar: Mastering the real-time strategy game starcraft ii.  DeepMind blog, 2.
  * [Vuong et al., 2019] Vuong, Q., Zhang, Y., and Ross, K. W. (2019).  Supervised policy update for deep reinforcement learning.  In International Conference on Learning Representation (ICLR).
  * [Watkins, 1989] Watkins, C. J. C. H. (1989).  Learning from delayed rewards.
  * [Williams, 1992] Williams, R. J. (1992).  Simple statistical gradient-following algorithms for connectionist reinforcement learning.  Machine learning, 8(3-4):229–256.
  * [Wu et al., 2018] Wu, C., Rajeswaran, A., Duan, Y., Kumar, V., Bayen, A. M., Kakade, S., Mordatch, I., and Abbeel, P. (2018).  Variance reduction for policy gradient with action-dependent factorized baselines.  International Conference on Learning Representation (ICLR).
  * [Xu et al., 2020] Xu, T., Liang, Y., and Lan, G. (2020).  A primal approach to constrained policy optimization: Global optimality and finite-time analysis.  arXiv preprint arXiv:2011.05869.
  * [Yang et al., 2018] Yang, L., Shi, M., Zheng, Q., Meng, W., and Pan, G. (2018).  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.
  * [Yang et al., 2021a] Yang, L., Zheng, G., Zhang, Y., Zheng, Q., Li, P., and Pan, G. (2021a).  On convergence of gradient expected sarsa ($\lambda$).  In AAAI.
  * [Yang et al., 2021b] Yang, L., Zheng, Q., and Pan, G. (2021b).  Sample complexity of policy gradient finding second-order stationary points.  In AAAI.
  * [Yang et al., 2020a] Yang, T.-Y., Rosca, J., Narasimhan, K., and Ramadge, P. J. (2020a).  Accelerating safe reinforcement learning with constraint-mismatched policies.  arXiv preprint arXiv:2006.11645.
  * [Yang et al., 2020b] Yang, T.-Y., Rosca, J., Narasimhan, K., and Ramadge, P. J. (2020b).  Projection-based constrained policy optimization.  In International Conference on Learning Representation (ICLR).
  * [Zanger et al., 2021] Zanger, M. A., Daaboul, K., and Zöllner, J. M. (2021).  Safe continuous control with constrained model-based policy optimization.  arXiv preprint arXiv:2104.06922.
  * [Zhang et al., 2020] Zhang, Y., Vuong, Q., and Ross, K. (2020).  First order constrained optimization in policy space.  In Advances in Neural Information Processing Systems (NeurIPS), volume 33.

##  Appendix A Key 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.3 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$ 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)=:\operatorname{\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.4 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)=\operatorname{\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.5  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)=\operatorname{\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)$ | : |  $\operatorname{\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 Practical Implementation of CUP

Algorithm 1 Conservative Update Policy (CUP)

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

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

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

4: 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}}$;

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

6: 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});$

7: 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};$

8: 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});$

9: 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\\}$;

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

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

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

13: end for

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

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

16:
$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\nu_{i,k+1}=\left\\{\nu_{i,k}+\eta(\hat{J}_{i}^{C}-b)\right\\}_{+}$
$\displaystyle{\bm{\theta}}_{k+1}$
$\displaystyle=\arg\min_{{\bm{\theta}}}\dfrac{1}{T}\sum_{t=1}^{T}\left\\{\text{KL}(\pi_{{\bm{\theta}}_{\text{old}}}(\cdot|s_{i,t}),\pi_{{\bm{\theta}}}(\cdot|s_{i,t}))+\nu_{i,k+1}\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\\};$

17: end for

18: 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

19:
$\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};$

20: end for

21: end for

In this section, we present the practical implementation of CUP.

###  B.1 Step 1: Policy Improvement

Objective of Policy Improvement.

For the first step w.r.t. policy improvement (17),

$\displaystyle\pi_{{\bm{\theta}}_{k+\frac{1}{2}}}=$
$\displaystyle\arg\max_{\pi_{{\bm{\theta}}}\in\Pi_{{\bm{\theta}}}}\left\\{\operatorname{\mathbb{E}}_{s\sim{d}_{\pi_{\bm{\theta}_{k}}}^{\lambda}(\cdot),a\sim\pi_{\bm{\theta}}(\cdot|s)}\left[A^{\text{GAE}(\gamma,\lambda)}_{{\pi_{\bm{\theta}_{k}}}}(s,a)\right]-\alpha_{k}\sqrt{\operatorname{\mathbb{E}}_{s\sim{d}_{{\pi_{\bm{\theta}_{k}}}}^{\lambda}(\cdot)}\left[\text{KL}(\pi_{\bm{\theta}_{k}},\pi_{\bm{\theta}})[s]\right]}\right\\},$

according to

$\displaystyle\operatorname{\mathbb{E}}_{s\sim{d}_{\pi_{\bm{\theta}_{k}}}^{\lambda}(\cdot),a\sim\pi_{\bm{\theta}}(\cdot|s)}\left[A^{\text{GAE}(\gamma,\lambda)}_{{\pi_{\bm{\theta}_{k}}}}(s,a)\right]=\operatorname{\mathbb{E}}_{s\sim
d_{\pi_{{\bm{\theta}}_{k}}}^{\lambda}(\cdot),a\sim\pi_{{\bm{\theta}}_{k}}(\cdot|s)}\left[\dfrac{\pi_{{\bm{\theta}}}(a|s)}{\pi_{{\bm{\theta}}_{k}}(a|s)}A^{\text{GAE}(\gamma,\lambda)}_{\pi_{{\bm{\theta}}_{k}}}(s,a)\right],$
(26)

which implies Eq.(18):

$\displaystyle\pi_{{\bm{\theta}}_{k+\frac{1}{2}}}=$
$\displaystyle\arg\max_{\pi_{{\bm{\theta}}}\in\Pi_{{\bm{\theta}}}}\left\\{\operatorname{\mathbb{E}}_{s\sim
d_{\pi_{{\bm{\theta}}_{k}}}^{\lambda}(\cdot),a\sim\pi_{{\bm{\theta}}_{k}}(\cdot|s)}\left[\dfrac{\pi_{{\bm{\theta}}}(a|s)}{\pi_{{\bm{\theta}}_{k}}(a|s)}A^{\text{GAE}(\gamma,\lambda)}_{\pi_{{\bm{\theta}}_{k}}}(s,a)\right]-\alpha_{k}\sqrt{\operatorname{\mathbb{E}}_{s\sim{d}_{{\pi_{\bm{\theta}_{k}}}}^{\lambda}(\cdot)}\left[\text{KL}(\pi_{\bm{\theta}_{k}},\pi_{\bm{\theta}})[s]\right]}\right\\}.$
(27)

We replace (17) with an importance sampling with respect to
$\pi_{\bm{\theta}_{k}}$ to obtain the expectation (27), and all the remains is
to replace the expectation (27) by sample averages according to the
trajectories collected by $\pi_{\bm{\theta}_{k}}$.

Learning from Samples.

For each trajectories (with size $M$) sampled from

$\bigcup_{i=1}^{M}\bigcup_{t=0}^{T}\left\\{(s_{i,t},a_{i,t},r_{i,t+1},c_{i,t+1})\right\\}\sim\pi_{{\bm{\theta}}_{k}},$

we learn the parameter $\bm{\theta}_{k+\frac{1}{2}}$ as follows: for each
$i=1,2,\cdots,M$,

$\displaystyle{\bm{\theta}}_{k+\frac{1}{2}}=\arg\max_{{\bm{\theta}}}\left\\{\dfrac{1}{T}\sum_{t=1}^{T}\frac{\pi_{\bm{\theta}}(a_{i,t}|s_{i,t})}{{\pi_{\bm{\theta}_{k}}}(a_{i,t}|s_{i,t})}\hat{A}_{i,t}-\alpha\sqrt{\dfrac{1}{T}\sum_{t=1}^{T}\text{KL}(\pi_{\bm{\theta}_{k}}(\cdot|s_{i,t}),\pi_{{\bm{\theta}}}(\cdot|s_{i,t}))}\right\\},$
(28)

which can be solved via the first order optimizer, where the following three
terms

$\hat{A}_{i,t},~{}~{}\dfrac{1}{T}\sum_{t=1}^{T}\frac{\pi_{\bm{\theta}}(a_{i,t}|s_{i,t})}{{\pi_{\bm{\theta}_{k}}}(a_{i,t}|s_{i,t})}\hat{A}_{i,t},~{}~{}\dfrac{1}{T}\sum_{t=1}^{T}\text{KL}(\pi_{\bm{\theta}_{k}}(\cdot|s_{i,t}),\pi_{{\bm{\theta}}}(\cdot|s_{i,t}))$

are the estimators (according to the $i$-th trajectory
$\\{(s_{i,t},a_{i,t},r_{i,t+1},c_{i,t+1})\\}_{t=0}^{T}\sim\pi_{\bm{\theta}_{k}}$
of the following three expectations correspondingly:

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

###  B.2 Step 2: Projection

Objective of Projection.

Recall Proposition 3.4 with respected to cost

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

and we introduce a new surrogate function with respected to cost function as
follows

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

where $\beta$ is adaptive to
$\frac{2\gamma(1-\lambda)\epsilon^{C}_{\pi_{\bm{\theta}}}(\pi_{{\bm{\theta}}^{{}^{\prime}}})}{(1-\gamma\lambda)\left|1-2\gamma\lambda|\mathcal{S}||\mathcal{A}|\right|}$.

Now, consider the projection step:

$\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.$ (29)

We turn the projection step as the following unconstrained problem:

$\displaystyle\max_{\nu\geq
0}\min_{\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\\}.$
(30)

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

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

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

$\displaystyle\max_{\nu\geq
0}\min_{\pi_{\bm{\theta}}}\left\\{\operatorname{\mathbb{E}}_{s\sim{d}_{{\pi_{\bm{\theta}_{k}}}}^{\lambda}(\cdot)}\left[\text{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\\}.$
(32)

Recall

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

to simplify the problem, we ignore the term
$\beta\sqrt{\operatorname{\mathbb{E}}_{s\sim{d}_{{\pi_{\bm{\theta}_{k}}}}^{\lambda}(\cdot)}\left[\text{KL}(\pi_{\bm{\theta}_{k}},\pi_{\bm{\theta}})[s]\right]}$
in Eq.(33) due to the following two aspects: (i) firstly, $\beta$ is adapted
to the term
$\frac{\gamma(1-\lambda)\epsilon^{C}_{\pi_{\bm{\theta}_{k+1}}}(\pi_{\bm{\theta}_{k}})}{(1-\gamma\lambda)\left|1-2\gamma\lambda|\mathcal{S}||\mathcal{A}|\right|}$,
and for the high-dimensional state space or continuous action space, then
$\beta$ is very small; (ii) secondly, if $D$ is a KL-divergence measure, then
the direction of the policy optimization
$D\left(\pi_{{\bm{\theta}}},\pi_{{\bm{\theta}}_{k+\frac{1}{2}}}\right)$ (31)
is proportional to
$\beta\sqrt{\operatorname{\mathbb{E}}_{s\sim{d}_{{\pi_{\bm{\theta}_{k}}}}^{\lambda}(\cdot)}\left[\text{KL}(\pi_{\bm{\theta}_{k}},\pi_{\bm{\theta}})[s]\right]}$,
thus, in practice, we can only optimize the distance
$D\left(\pi_{{\bm{\theta}}},\pi_{{\bm{\theta}}_{k+\frac{1}{2}}}\right)$.

Above discussions implies that instead of (32), we can consider the problem

$\displaystyle\max_{\nu\geq
0}\min_{\pi_{\bm{\theta}}}\mathcal{L}(\bm{\theta},\nu),$

where

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

Learning from Samples.

Then, according to gradient decent method, we have

$\displaystyle\bm{\theta}\leftarrow\bm{\theta}-\eta\dfrac{\mathcal{L}(\bm{\theta},\nu)}{\partial\bm{\theta}},~{}~{}~{}\nu\leftarrow\left\\{\nu+\eta\dfrac{\mathcal{L}(\bm{\theta},\nu)}{\partial\nu}\right\\}_{+},$
(34)

where $\\{\cdot\\}_{+}$ denote the positive part, i.e., if $x\leq 0$,
$\\{x\\}_{+}=0$, else $\\{x\\}_{+}=x$. Particularly,

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

where the term
$\operatorname{\mathbb{E}}_{s\sim{d}_{\pi_{\bm{\theta}_{k}}}^{\lambda}(\cdot),a\sim\pi_{\bm{\theta}}(\cdot|s)}\left[A^{\text{GAE}(\gamma,\lambda)}_{{\pi_{\bm{\theta}_{k}}},C}(s,a)\right]$
can be estimated following the idea as (26):

$\operatorname{\mathbb{E}}_{s\sim{d}_{\pi_{\bm{\theta}_{k}}}^{\lambda}(\cdot),a\sim\pi_{\bm{\theta}}(\cdot|s)}\left[A^{\text{GAE}(\gamma,\lambda)}_{{\pi_{\bm{\theta}_{k}}},C}(s,a)\right]=\operatorname{\mathbb{E}}_{s\sim
d_{\pi_{{\bm{\theta}}_{k}}}^{\lambda}(\cdot),a\sim\pi_{{\bm{\theta}}_{k}}(\cdot|s)}\left[\dfrac{\pi_{{\bm{\theta}}}(a|s)}{\pi_{{\bm{\theta}}_{k}}(a|s)}A^{\text{GAE}(\gamma,\lambda)}_{\pi_{{\bm{\theta}}_{k}},C}(s,a)\right].$

But recall (18) is a MM-iteration, i.e., we require to minimize
$\operatorname{\mathbb{E}}_{s\sim{d}_{\pi_{\bm{\theta}_{k}}}^{\lambda}(\cdot)}\text{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
$\operatorname{\mathbb{E}}_{s\sim{d}_{\pi_{\bm{\theta}_{k}}}^{\lambda}(\cdot),a\sim\pi_{\bm{\theta}}(\cdot|s)}\left[A^{\text{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, according to (34), for each data sampled from
$\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}}$, we learn the parameter
$\bm{\theta}_{k+1}$ as follows,

$\displaystyle{\bm{\theta}}_{k+1}$
$\displaystyle=\arg\min_{{\bm{\theta}}}\dfrac{1}{T}\sum_{t=1}^{T}\left\\{\text{KL}\left({\pi_{\bm{\theta}_{k+\frac{1}{2}}}}(\cdot|s_{i,t}),\pi_{{\bm{\theta}}}(\cdot|s_{i,t})\right)+\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\\},$

which can be solved via the first-order optimizer.

##  Appendix C Additional Discussion about Related Work

This section reviews three typical safe reinforcement learning algorithms: CPO
[Achiam et al., 2017], PCPO [Yang et al., 2020b] 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.

###  C.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}}}}~{}~{}~{}~{}\operatorname{\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]$
(36)
$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}\text{s.t.}~{}~{}J^{c}(\pi_{{\bm{\theta}}_{k}})+\frac{1}{1-\gamma}\operatorname{\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,$ (37)
$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}\bar{D}_{\text{KL}}(\pi_{{\bm{\theta}}},\pi_{{\bm{\theta}}_{k}})=\operatorname{\mathbb{E}}_{s\sim
d^{\rho_{0}}_{\pi_{{\bm{\theta}}_{k}}}(\cdot)}[\text{KL}(\pi_{{\bm{\theta}}},\pi_{{\bm{\theta}}_{k}})[s]]\leq\delta.$
(38)

It is impractical to solve the problem (23) 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}_{\text{KL}}(\pi_{{\bm{\theta}}},\pi_{{\bm{\theta}}_{k}})$
Eq.(23)-(25).

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

$\displaystyle\frac{1}{1-\gamma}\operatorname{\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 (23)-(25) to be a convex problem,

$\displaystyle\frac{1}{1-\gamma}\operatorname{\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}}),$
(39)
$\displaystyle\bar{D}_{\text{KL}}(\pi_{{\bm{\theta}}},\pi_{{\bm{\theta}}_{k}})$
$\displaystyle\approx({\bm{\theta}}-{\bm{\theta}}_{k})^{\top}\mathbf{H}({\bm{\theta}}-{\bm{\theta}}_{k}),$
(40)

where $\mathbf{H}$ is Hessian matrix of
$\bar{D}_{\text{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}}\operatorname{\mathbb{E}}_{s\sim
d^{\rho_{0}}_{\pi_{{\bm{\theta}}_{k}}}(\cdot)}\left[\text{KL}(\pi_{{\bm{\theta}}},\pi_{{\bm{\theta}}_{k}})[s]\right],$

Eq.(40) is the second-oder approximation of (25).

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}}\operatorname{\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}}\operatorname{\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}.$

###  C.2 PCPO [Yang et al., 2020b]

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}}}}\operatorname{\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}_{\text{KL}}(\pi_{{\bm{\theta}}},\pi_{{\bm{\theta}}_{k}})=\operatorname{\mathbb{E}}_{s\sim
d^{\rho_{0}}_{\pi_{{\bm{\theta}}_{k}}}(\cdot)}[\text{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}\operatorname{\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., 2020b] 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.

###  C.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 (42)-(43) in the non-
parameterized policy space.

$\displaystyle\pi^{\star}=\arg\max_{\pi\in\Pi}~{}~{}~{}~{}\operatorname{\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]$
(41)
$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}\text{s.t.}~{}~{}J^{c}(\pi_{{\bm{\theta}}_{k}})+\frac{1}{1-\gamma}\operatorname{\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,$ (42)
$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}\bar{D}_{\text{KL}}(\pi_{{\bm{\theta}}},\pi_{{\bm{\theta}}_{k}})=\operatorname{\mathbb{E}}_{s\sim
d^{\rho_{0}}_{\pi_{{\bm{\theta}}_{k}}}(\cdot)}[\text{KL}(\pi,\pi_{{\bm{\theta}}_{k}})[s]]\leq\delta.$
(43)

If $\pi_{\bm{\theta}_{k}}$ is feasible, then the optimal policy for (41)-(43)
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),$ (44)

where $Z_{\lambda,\nu}(s)$ is the partition function which ensures (44) 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\operatorname{\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}}\operatorname{\mathbb{E}}_{s\sim
d^{\rho_{0}}_{\pi_{{\bm{\theta}}_{k}}}(\cdot)}[\text{KL}(\pi_{{\bm{\theta}}},\pi^{\star})[s]].$

###  C.4 Comparison to CUP

Comparing to CPO and PCPO, the implementation of CUP does not depend on any
convex approximations. CPO learns its objective with the deep neural network
via the first-order method (see Appendix B).

Concretely, CPO and PCPO 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. Additionally, their approaches
involve the inverse of a high-dimension Fisher information matrix, which
causes their algorithms to require a costly computation for each update when
solving high-dimensional RL problems. While the proposed CUP does not depend
on any convex approximations, it learns the policy via first-order
optimization approaches. Thus, CUP does not involve the inverse of a high-
dimension Fisher information matrix, which implies CUP requires less memory
than CPO and PCPO.

Although FOCOPS is also a non-convex implementation, it heavily depends on the
current best-satisfied policy. It is known that the current best policy may
not be the optimal policy, and FOCOPS requires to project this policy back
into the parametric policy space, which implies FOCOPS reduce the chances for
an agent to explore the environment since it may lose in a locally optimal
solution. While the proposed CUP does not depend on the current optimal
policy, in fact, CUP requires the agent to learn the policy according to (18),
the numerical solution is not the current optimal policy, which helps CUP to
explore the environment.

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}}}}\operatorname{\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}})+\operatorname{\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}_{\text{KL}}(\pi_{{\bm{\theta}}},\pi_{{\bm{\theta}}_{k}})=\operatorname{\mathbb{E}}_{s\sim
d^{\rho_{0}}_{\pi_{{\bm{\theta}}_{k}}}(\cdot)}[\text{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., 2020b] Reward Improvement
$\pi_{\bm{\theta}_{k+\frac{1}{2}}}=\arg\max_{\pi_{{\bm{\theta}}}\in\Pi_{{\bm{\theta}}}}\operatorname{\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}_{\text{KL}}(\pi_{{\bm{\theta}}},\pi_{{\bm{\theta}}_{k}})=\operatorname{\mathbb{E}}_{s\sim
d^{\rho_{0}}_{\pi_{{\bm{\theta}}_{k}}}(\cdot)}[\text{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}\operatorname{\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
$\pi_{{\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}\operatorname{\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}})+\operatorname{\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}_{\text{KL}}(\pi_{{\bm{\theta}}},\pi_{{\bm{\theta}}_{k}})=\operatorname{\mathbb{E}}_{s\sim
d^{\rho_{0}}_{\pi_{{\bm{\theta}}_{k}}}(\cdot)}[\text{KL}(\pi,\pi_{{\bm{\theta}}_{k}})[s]]\leq\delta$;
Projection
$\pi_{{\bm{\theta}}_{k+1}}=\arg\min_{\pi_{{\bm{\theta}}}\in\Pi_{{\bm{\theta}}}}~{}\operatorname{\mathbb{E}}_{s\sim
d^{\rho_{0}}_{\pi_{{\bm{\theta}}_{k}}}(\cdot)}[\text{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}}\operatorname{\mathbb{E}}_{s\sim
d^{\rho_{0}}_{\pi_{{\bm{\theta}}_{k}}}(\cdot)}[\text{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{\\{}\operatorname{\mathbb{E}}_{s\sim{d}_{\pi_{\bm{\theta}_{k}}}^{\lambda}(\cdot),a\sim\pi_{\bm{\theta}}(\cdot|s)}\left[A^{\text{GAE}(\gamma,\lambda)}_{{\pi_{\bm{\theta}_{k}}}}(s,a)\right]$
$\displaystyle-\alpha_{k}\sqrt{\operatorname{\mathbb{E}}_{s\sim{d}_{{\pi_{\bm{\theta}_{k}}}}^{\lambda}(\cdot)}\left[\text{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}}\operatorname{\mathbb{E}}_{s\sim{d}_{\pi_{\bm{\theta}_{k}}}^{\lambda}(\cdot),a\sim\pi_{\bm{\theta}}(\cdot|s)}\left[A^{\text{GAE}(\gamma,\lambda)}_{{\pi_{\bm{\theta}_{k}}},C}(s,a)\right]$
$\displaystyle+\beta_{k}\sqrt{\operatorname{\mathbb{E}}_{s\sim{d}_{{\pi_{\bm{\theta}_{k}}}}^{\lambda}(\cdot)}\left[\text{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}\text{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{\\{}\text{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 D Preliminaries

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

###  D.1 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}.$ (45)

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}).$
(46)

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}.$
(47)

###  D.2 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],$
(48)

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].$
(49)

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}}).$
(50)

###  D.3 Bellman Operator

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,$
(51)

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 (51), 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}}}.$
(52)

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,$
(53)

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}.$
(54)

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),$
(55)

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).$
(56)

Thus, we rewrite
$\mathbb{P}_{\pi_{\bm{\theta}}}^{(\lambda)}(s^{{}^{\prime}}|s)$ (55) 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}.$
(57)

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

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}).$
(58)

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}}).$
(59)

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}),$
(60) $\displaystyle d_{\pi_{\bm{\theta}}}^{\lambda}(s)$
$\displaystyle=\operatorname{\mathbb{E}}_{s_{0}\sim\rho_{0}(\cdot)}\left[d_{\pi_{\bm{\theta}}}^{s_{0},\lambda}(s)\right],$
(61) $\displaystyle\mathbf{d}_{\pi_{\bm{\theta}}}^{\lambda}[s]$
$\displaystyle=d_{\pi_{\bm{\theta}}}^{\lambda}(s),$ (62)

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}.$
(63)

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

According to Bellman equation (52), $\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}}}.$
(64)

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

$\displaystyle
V_{\pi_{\bm{\theta}}}(s_{0})=\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}]=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}}).$
(65)

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

$\displaystyle 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})\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).$
(66)

According to (48) and (66), 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}}}\operatorname{\mathbb{E}}_{s\sim
d^{\lambda}_{\pi_{\bm{\theta}}}(\cdot)}\left[R^{(\lambda)}_{\pi_{\bm{\theta}}}(s)\right].$
(67)

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

######  Lemma D.1.

The objective $J(\pi_{\bm{\theta}})$ (49) 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}}}\operatorname{\mathbb{E}}_{s\sim
d^{\lambda}_{\pi_{\bm{\theta}}}(\cdot)}\left[R^{(\lambda)}_{\pi_{\bm{\theta}}}(s)\right].$

##  Appendix E Proof of Theorem 3.1

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

######  Proposition E.1.

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=\operatorname{\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}})$ (67) can be rewritten as the
following version:

$\displaystyle J(\pi_{\bm{\theta}})=$
$\displaystyle\operatorname{\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)$
(68) $\displaystyle=$
$\displaystyle\operatorname{\mathbb{E}}_{s_{0}\sim\rho_{0}(\cdot)}[\varphi(s_{0})]+\dfrac{1}{1-\tilde{\gamma}}\operatorname{\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 E.1 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).$
(69)

Then, we rewrite the objective as the following vector version

$\displaystyle
J(\pi_{\bm{\theta}})=\operatorname{\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,$
(70)

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

###  E.1 Proof of Theorem 3.1

Theorem 3.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}}}),$
(71)

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

###### Proof.

(of Theorem 3.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.$
(72)

According to (70), 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}}}),$
(73)

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

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

We rewrite the first term of (72) as:

$\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,$
(74)

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 (74) as:

$\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}\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+\|\mathbf{d}_{\pi_{\bm{\theta}}}^{\lambda}-\mathbf{d}_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}^{\lambda}\|_{p}\|{\bm{\delta}}^{\varphi}_{\pi_{\bm{\theta}},t}\|_{q},$
(75)

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.(75) 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}}}).$
(76)

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}},$ (77)

combining the (72) and (76), 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
M_{t}^{\varphi}(\pi_{\bm{\theta}},\pi_{{\bm{\theta}}^{{}^{\prime}}})+\epsilon^{\varphi,(\lambda)}_{p,q,t}(\pi_{\bm{\theta}},\pi_{{\bm{\theta}}^{{}^{\prime}}}).$
(78)

Step 2: Analyze the term
$M_{t}^{\varphi}(\pi_{\bm{\theta}},\pi_{{\bm{\theta}}^{{}^{\prime}}})$ (77).

To analyze (78) further, we need to consider the first term appears in
$M_{t}^{\varphi}(\pi_{\bm{\theta}},\pi_{{\bm{\theta}}^{{}^{\prime}}})$ (77):

$\displaystyle\text{Term-I}~{}(\ref{def:l-t})=$
$\displaystyle\langle\mathbf{d}_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}^{\lambda},{\bm{\delta}}^{\varphi}_{\pi_{\bm{\theta}},t}\rangle$
$\displaystyle=$
$\displaystyle\sum_{s\in\mathcal{S}}d_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}^{\lambda}(s){{\delta}}^{\varphi}_{\pi_{\bm{\theta}},t}(s)=\operatorname{\mathbb{E}}_{s\sim
d_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}^{\lambda}(\cdot)}\left[{{\delta}}^{\varphi}_{\pi_{\bm{\theta}},t}(s)\right]$
(79) $\displaystyle\overset{(\ref{revist-td-ex-error})}{=}$
$\displaystyle\operatorname{\mathbb{E}}_{s\sim
d_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}^{\lambda}(\cdot)}\left[\operatorname{\mathbb{E}}_{s_{t}\sim\mathbb{P}_{\pi_{\bm{\theta}}}(\cdot|s)}[\delta^{\varphi}_{\pi_{\bm{\theta}}}(s_{t})]\right].$
(80)

We notice the following relationship

$\displaystyle\delta^{\varphi}_{\pi_{\bm{\theta}},t}(s)=$
$\displaystyle\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}}{\operatorname{\mathbb{E}}}\left[\delta_{t}^{\varphi}\right]=\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}}{\operatorname{\mathbb{E}}}\left[\dfrac{\pi_{\bm{\theta}}(a_{t}|s_{t})}{\pi_{{\bm{\theta}}^{{}^{\prime}}}(a_{t}|s_{t})}\delta_{t}^{\varphi}\right],$
(81)

which holds since we use importance sampling: for any distribution $p(\cdot)$
and $q(\cdot)$, for any random variable function $f(\cdot)$,

$\operatorname{\mathbb{E}}_{x\sim p(x)}[f(x)]=\operatorname{\mathbb{E}}_{x\sim
q(x)}\left[\dfrac{p(x)}{q(x)}f(x)\right].$

According to (79), (81), we rewrite the term
$\langle\mathbf{d}_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}^{\lambda},{\bm{\delta}}^{\varphi}_{\pi_{\bm{\theta}},t}\rangle$
in Eq.(77) as follows,

$\displaystyle\text{Term-I}~{}(\ref{def:l-t})=\langle\mathbf{d}_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}^{\lambda},{\bm{\delta}}^{\varphi}_{\pi_{\bm{\theta}},t}\rangle=\sum_{s\in\mathcal{S}}d_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}^{\lambda}(s)\left(\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}}{\operatorname{\mathbb{E}}}\left[\dfrac{\pi_{\bm{\theta}}(a_{t}|s_{t})}{\pi_{{\bm{\theta}}^{{}^{\prime}}}(a_{t}|s_{t})}\delta_{t}^{\varphi}\right]\right).$
(82)

Now, we consider the second term appears in
$M_{t}^{\varphi}(\pi_{\bm{\theta}},\pi_{{\bm{\theta}}^{{}^{\prime}}})$ (77):

$\displaystyle\text{Term-II}~{}(\ref{def:l-t})$