$\displaystyle=\langle\mathbf{d}_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}^{\lambda},\bm{\delta}^{\varphi}_{\pi_{{\bm{\theta}}^{{}^{\prime}}},t}\rangle$
$\displaystyle=\sum_{s\in\mathcal{S}}d_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}^{\lambda}(s){\delta}^{\varphi}_{\pi_{{\bm{\theta}}^{{}^{\prime}}},t}(s)=\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[\delta_{t}^{\varphi}\right]\right).$
(83)

Finally, take the results (82) and (83) to (77), we obtain the difference
between
$\langle\mathbf{d}_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}^{\lambda},{\bm{\delta}}^{\varphi}_{\pi_{\bm{\theta}},t}\rangle$
and
$\langle\mathbf{d}_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}^{\lambda},\bm{\delta}^{\varphi}_{\pi_{{\bm{\theta}}^{{}^{\prime}}},t}\rangle$,
i.e., we achieve a identity for
$M_{t}^{\varphi}(\pi_{\bm{\theta}},\pi_{{\bm{\theta}}^{{}^{\prime}}})$ (77) as
follows,

$\displaystyle
M_{t}^{\varphi}(\pi_{\bm{\theta}},\pi_{{\bm{\theta}}^{{}^{\prime}}})\overset{(\ref{def:l-t})}{=}$
$\displaystyle\langle\mathbf{d}_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}^{\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$
$\displaystyle\overset{(\ref{app-ex-td-01},(\ref{app-ex-td-02})}{=}$
$\displaystyle\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[\left(\dfrac{\pi_{\bm{\theta}}(a_{t}|s_{t})}{\pi_{{\bm{\theta}}^{{}^{\prime}}}(a_{t}|s_{t})}-1\right)\delta_{t}^{\varphi}\right]\right).$
(84)

To simplify expression, we introduce a notation as follows,

$\displaystyle\Delta_{t}^{\varphi}(\pi_{\bm{\theta}},\pi_{{\bm{\theta}}^{{}^{\prime}}},s)$
$\displaystyle=:\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],$
(85)

and we use a vector
$\bm{\Delta}_{t}^{\varphi}(\pi_{\bm{\theta}},\pi_{{\bm{\theta}}^{{}^{\prime}}})\in\mathbb{R}^{|\mathcal{S}|}$
to store all the values
$\\{\Delta_{t}^{\varphi}(\pi_{\bm{\theta}},\pi_{{\bm{\theta}}^{{}^{\prime}}},s)\\}_{s\in\mathcal{S}}$:

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

Then we rewrite
$\langle\mathbf{d}_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}^{\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$
(84) as follows,

$\displaystyle
M_{t}^{\varphi}(\pi_{\bm{\theta}},\pi_{{\bm{\theta}}^{{}^{\prime}}})=\langle\mathbf{d}_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}^{\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\overset{(\ref{diff-01})}{=}\sum_{s\in\mathcal{S}}d_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}^{\lambda}(s)\Delta_{t}^{\varphi}(\pi_{\bm{\theta}},\pi_{{\bm{\theta}}^{{}^{\prime}}},s)=\langle\mathbf{d}_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}^{\lambda},\bm{\Delta}_{t}^{\varphi}(\pi_{\bm{\theta}},\pi_{{\bm{\theta}}^{{}^{\prime}}})\rangle.$

Step 3: Bound on $J(\pi_{\bm{\theta}})-J(\pi_{{\bm{\theta}}^{{}^{\prime}}})$.

Recall (78), taking above result in it, we obtain

$\displaystyle\langle\mathbf{d}_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}^{\lambda},\bm{\Delta}_{t}^{\varphi}(\pi_{\bm{\theta}},\pi_{{\bm{\theta}}^{{}^{\prime}}})\rangle-\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\langle\mathbf{d}_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}^{\lambda},\bm{\Delta}_{t}^{\varphi}(\pi_{\bm{\theta}},\pi_{{\bm{\theta}}^{{}^{\prime}}})\rangle+\epsilon^{\varphi,(\lambda)}_{p,q,t}(\pi_{\bm{\theta}},\pi_{{\bm{\theta}}^{{}^{\prime}}}).$
(86)

Finally, let

$\displaystyle
M^{\varphi,-}_{p,q,t}(\pi_{\bm{\theta}},\pi_{{\bm{\theta}}^{{}^{\prime}}})=\langle\mathbf{d}_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}^{\lambda},\bm{\Delta}_{t}^{\varphi}(\pi_{\bm{\theta}},\pi_{{\bm{\theta}}^{{}^{\prime}}})\rangle-\epsilon^{\varphi,(\lambda)}_{p,q,t}(\pi_{\bm{\theta}},\pi_{{\bm{\theta}}^{{}^{\prime}}})$
(87) $\displaystyle=$
$\displaystyle\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[\left(\dfrac{\pi_{\bm{\theta}}(a_{t}|s_{t})}{\pi_{{\bm{\theta}}^{{}^{\prime}}}(a_{t}|s_{t})}-1\right)\delta_{t}^{\varphi}\right]\right)-\|\mathbf{d}_{\pi_{\bm{\theta}}}^{\lambda}-\mathbf{d}_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}^{\lambda}\|_{p}\|{\bm{\delta}}^{\varphi}_{\pi_{\bm{\theta}},t}\|_{q}$
$\displaystyle=$
$\displaystyle\operatorname{\mathbb{E}}_{s\sim{d}_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}^{\lambda}(\cdot)}\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[\left(\dfrac{\pi_{\bm{\theta}}(a_{t}|s_{t})}{\pi_{{\bm{\theta}}^{{}^{\prime}}}(a_{t}|s_{t})}-1\right)\delta_{t}^{\varphi}\right]\right]-\|\mathbf{d}_{\pi_{\bm{\theta}}}^{\lambda}-\mathbf{d}_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}^{\lambda}\|_{p}\|{\bm{\delta}}^{\varphi}_{\pi_{\bm{\theta}},t}\|_{q}.$

and

$\displaystyle
M^{\varphi,+}_{p,q,t}(\pi_{\bm{\theta}},\pi_{{\bm{\theta}}^{{}^{\prime}}})=\langle\mathbf{d}_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}^{\lambda},\bm{\Delta}_{t}^{\varphi}(\pi_{\bm{\theta}},\pi_{{\bm{\theta}}^{{}^{\prime}}})\rangle+\epsilon^{\varphi,(\lambda)}_{p,q,t}(\pi_{\bm{\theta}},\pi_{{\bm{\theta}}^{{}^{\prime}}})$
(88) $\displaystyle=$
$\displaystyle\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[\left(\dfrac{\pi_{\bm{\theta}}(a_{t}|s_{t})}{\pi_{{\bm{\theta}}^{{}^{\prime}}}(a_{t}|s_{t})}-1\right)\delta_{t}^{\varphi}\right]\right)+\|\mathbf{d}_{\pi_{\bm{\theta}}}^{\lambda}-\mathbf{d}_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}^{\lambda}\|_{p}\|{\bm{\delta}}^{\varphi}_{\pi_{\bm{\theta}},t}\|_{q}$
$\displaystyle=$
$\displaystyle\operatorname{\mathbb{E}}_{s\sim{d}_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}^{\lambda}(\cdot)}\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[\left(\dfrac{\pi_{\bm{\theta}}(a_{t}|s_{t})}{\pi_{{\bm{\theta}}^{{}^{\prime}}}(a_{t}|s_{t})}-1\right)\delta_{t}^{\varphi}\right]\right]+\|\mathbf{d}_{\pi_{\bm{\theta}}}^{\lambda}-\mathbf{d}_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}^{\lambda}\|_{p}\|{\bm{\delta}}^{\varphi}_{\pi_{\bm{\theta}},t}\|_{q}.$

According to (73) and (86), we achieve the boundedness of performance
difference between two arbitrary policies $\pi_{\bm{\theta}}$ and
$\pi_{{\bm{\theta}}^{{}^{\prime}}}$:

$\displaystyle\underbrace{\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}}})}_{=:L^{\varphi,-}_{p,q,}}\leq
J(\pi_{\bm{\theta}})-J(\pi_{{\bm{\theta}}^{{}^{\prime}}})\leq\underbrace{\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}}})}_{=:L^{\varphi,+}_{p,q,}}.$
(89)

∎

###  E.2 Proof of Proposition E.1

###### Proof.

Step 1: Rewrite the objective $J(\pi_{\bm{\theta}})$ in Eq.(67).

We rewrite the discounted distribution
$\mathbf{d}_{\pi_{\bm{\theta}}}^{\lambda}$ (63) as follows,

$\displaystyle\bm{\rho}_{0}-\dfrac{1}{1-{\tilde{\gamma}}}\mathbf{d}_{\pi_{\bm{\theta}}}^{\lambda}+\dfrac{{\tilde{\gamma}}}{1-{\tilde{\gamma}}}\mathbf{P}^{(\lambda)}_{\pi_{\bm{\theta}}}\mathbf{d}_{\pi_{\bm{\theta}}}^{\lambda}=\bm{0}.$
(90)

Let $\varphi(\cdot)$ be a real number function defined on the state space
$\mathcal{S}$, i.e., $\varphi:\mathcal{S}\rightarrow\mathbb{R}$. Then we
define a vector function $\bm{\phi}(\cdot)\in\mathbb{R}^{|\mathcal{S}|}$ to
collect all the values $\\{\varphi(s)\\}_{s\in\mathcal{S}}$, and its
components are

$\bm{\phi}[s]=\varphi(s),~{}~{}s\in\mathcal{S}.$

Now, we take the inner product between the vector $\bm{\phi}$ and (90), we
have

$\displaystyle 0=$
$\displaystyle\langle\bm{\rho}_{0}-\dfrac{1}{1-{\tilde{\gamma}}}\mathbf{d}_{\pi_{\bm{\theta}}}^{\lambda}+\dfrac{{\tilde{\gamma}}}{1-{\tilde{\gamma}}}\mathbf{P}^{(\lambda)}_{\pi_{\bm{\theta}}}\mathbf{d}_{\pi_{\bm{\theta}}}^{\lambda},\bm{\phi}\rangle$
$\displaystyle=$
$\displaystyle\langle\bm{\rho}_{0},\bm{\phi}\rangle-\dfrac{1}{1-{\tilde{\gamma}}}\langle\mathbf{d}_{\pi_{\bm{\theta}}}^{\lambda},\bm{\phi}\rangle+\dfrac{{\tilde{\gamma}}}{1-{\tilde{\gamma}}}\langle\mathbf{P}^{(\lambda)}_{\pi_{\bm{\theta}}}\mathbf{d}_{\pi_{\bm{\theta}}}^{\lambda},\bm{\phi}\rangle.$
(91)

We express the first term $\langle\bm{\rho}_{0},\bm{\phi}\rangle$ of (91) as
follows,

$\displaystyle\langle\bm{\rho}_{0},\bm{\phi}\rangle=\sum_{s\in\mathcal{S}}\rho_{0}(s)\varphi(s)=\operatorname{\mathbb{E}}_{s\sim\rho_{0}(\cdot)}[\varphi(s)].$
(92)

We express the second term
$\langle\mathbf{d}_{\pi_{\bm{\theta}}}^{\lambda},\bm{\phi}\rangle$ of (91) as
follows,

$\displaystyle-\dfrac{1}{1-{\tilde{\gamma}}}\langle\mathbf{d}_{\pi_{\bm{\theta}}}^{\lambda},\bm{\phi}\rangle$
$\displaystyle=-\dfrac{1}{1-{\tilde{\gamma}}}\sum_{s\in\mathcal{S}}d_{\pi_{\bm{\theta}}}^{\lambda}(s)\varphi(s)$
$\displaystyle=-\dfrac{1}{1-{\tilde{\gamma}}}\operatorname{\mathbb{E}}_{s\sim
d_{\pi_{\bm{\theta}}}^{\lambda}(\cdot)}[\varphi(s)].$ (93)

We express the third term
$\langle{\tilde{\gamma}}\mathbf{P}^{(\lambda)}_{\pi_{\bm{\theta}}}\mathbf{d}_{\pi_{\bm{\theta}}}^{\lambda},\bm{\phi}\rangle$
of (91) as follows,

$\displaystyle\dfrac{{\tilde{\gamma}}}{1-{\tilde{\gamma}}}\langle\mathbf{P}^{(\lambda)}_{\pi_{\bm{\theta}}}\mathbf{d}_{\pi_{\bm{\theta}}}^{\lambda},\bm{\phi}\rangle=$
$\displaystyle\dfrac{{\tilde{\gamma}}}{1-{\tilde{\gamma}}}\sum_{s^{{}^{\prime}}\in\mathcal{S}}\left(\mathbf{P}^{(\lambda)}_{\pi_{\bm{\theta}}}\mathbf{d}_{\pi_{\bm{\theta}}}^{\lambda}\right)[s^{{}^{\prime}}]\varphi(s^{{}^{\prime}})$
$\displaystyle=$
$\displaystyle\dfrac{{\tilde{\gamma}}}{1-{\tilde{\gamma}}}\sum_{s^{{}^{\prime}}\in\mathcal{S}}\left(\sum_{s\in\mathcal{S}}\mathbb{P}_{\pi_{\bm{\theta}}}^{(\lambda)}(s^{{}^{\prime}}|s)d_{\pi_{\bm{\theta}}}^{\lambda}(s)\right)\varphi(s^{{}^{\prime}}).$
(94)

According to Lemma D.1, put the results (67) and (91) together, we have

$\displaystyle J(\pi_{\bm{\theta}})\overset{(\ref{lam-return-
objective}),(\ref{state-distribution-inner-initial-vec})}{=}$
$\displaystyle\dfrac{1}{1-{\tilde{\gamma}}}\sum_{s\in\mathcal{S}}d^{\lambda}_{\pi_{\bm{\theta}}}(s)R^{(\lambda)}_{\pi_{\bm{\theta}}}(s)+\left\langle\bm{\rho}_{0}-\dfrac{1}{1-{\tilde{\gamma}}}\mathbf{d}_{\pi_{\bm{\theta}}}^{\lambda}+\dfrac{{\tilde{\gamma}}}{1-{\tilde{\gamma}}}\mathbf{P}^{(\lambda)}_{\pi_{\bm{\theta}}}\mathbf{d}_{\pi_{\bm{\theta}}}^{\lambda},\bm{\phi}\right\rangle$
$\displaystyle=$
$\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(R^{(\lambda)}_{\pi_{\bm{\theta}}}(s)+{\tilde{\gamma}}\sum_{s^{{}^{\prime}}\in\mathcal{S}}\mathbb{P}_{\pi_{\bm{\theta}}}^{(\lambda)}(s^{{}^{\prime}}|s)\varphi(s^{{}^{\prime}})-\varphi(s)\right),$
(95)

where the last equation holds since we unfold (91) according to (92)-(94).

Step 2: Rewrite the term
$\left(R^{(\lambda)}_{\pi_{\bm{\theta}}}(s)+{\tilde{\gamma}}\sum_{s^{{}^{\prime}}\in\mathcal{S}}\mathbb{P}_{\pi_{\bm{\theta}}}^{(\lambda)}(s^{{}^{\prime}}|s)\varphi(s^{{}^{\prime}})-\varphi(s)\right)$
in Eq.(95).

Then, we unfold the second term of (95) as follows,

$\displaystyle
R^{(\lambda)}_{\pi_{\bm{\theta}}}(s)+{\tilde{\gamma}}\sum_{s^{{}^{\prime}}\in\mathcal{S}}\mathbb{P}_{\pi_{\bm{\theta}}}^{(\lambda)}(s^{{}^{\prime}}|s)\varphi(s^{{}^{\prime}})-\varphi(s)$
(96) $\displaystyle\overset{(\ref{lam-pro-value-02}),(\ref{lam-pro-
value-03})}{=}$
$\displaystyle\sum_{{t}=0}^{\infty}({{\gamma}}\lambda\mathbf{P}_{\pi_{\bm{\theta}}})^{{t}}\mathbf{r}_{\pi_{\bm{\theta}}}[s]+{\tilde{\gamma}}(1-\gamma\lambda)\sum_{s^{{}^{\prime}}\in\mathcal{S}}\sum_{{t}=0}^{\infty}({{\gamma}}\lambda)^{{t}}\left(\mathbf{P}^{{t}+1}_{\pi_{\bm{\theta}}}[s,s^{{}^{\prime}}]\right)\varphi(s^{{}^{\prime}})-\varphi(s)$
$\displaystyle\overset{(\ref{def:matrix-p-lam-return})}{=}$
$\displaystyle\sum_{{t}=0}^{\infty}({{\gamma}}\lambda\mathbf{P}_{\pi_{\bm{\theta}}})^{{t}}\mathbf{r}_{\pi_{\bm{\theta}}}[s]+{{\gamma}}(1-\lambda)\sum_{s^{{}^{\prime}}\in\mathcal{S}}\sum_{{t}=0}^{\infty}({{\gamma}}\lambda)^{{t}}\mathbb{P}_{\pi_{\bm{\theta}}}(s_{t+1}=s^{{}^{\prime}}|s)\varphi(s^{{}^{\prime}})-\varphi(s).$
(97)

Recall the terms
$\mathbf{P}^{(\lambda)}_{\pi_{\bm{\theta}}},~{}\mathbf{r}^{(\lambda)}_{\pi_{\bm{\theta}}}[s]$
defined in (54)-(59),

$\displaystyle
R^{(\lambda)}_{\pi_{\bm{\theta}}}(s)+\gamma(1-\lambda)\sum_{s^{{}^{\prime}}\in\mathcal{S}}\mathbb{P}_{\pi_{\bm{\theta}}}^{(\lambda)}(s^{{}^{\prime}}|s)\varphi(s^{{}^{\prime}})-\varphi(s)$
(98)

We consider the first term $R^{(\lambda)}_{\pi_{\bm{\theta}}}(s)$ of (96) as
follows,

$\displaystyle R^{(\lambda)}_{\pi_{\bm{\theta}}}(s)\overset{(\ref{def:matrix-
p-lam-return})-(\ref{lam-pro-
value-03})}{=}\mathbf{r}^{(\lambda)}_{\pi_{\bm{\theta}}}[s]=\sum_{{t}=0}^{\infty}(\gamma\lambda)^{t}\mathbf{P}_{\pi_{\bm{\theta}}}^{{t}}\mathbf{r}_{\pi_{\bm{\theta}}}[s]=\sum_{{t}=0}^{\infty}\sum_{s_{t}\in\mathcal{S}}(\gamma\lambda)^{t}\mathbb{P}_{\pi_{\bm{\theta}}}(s_{t}|s)R_{\pi_{\bm{\theta}}}(s_{t}).$
(99)

We consider the second term
$\tilde{\gamma}\sum_{s\in\mathcal{S}}\mathbb{P}_{\pi_{\bm{\theta}}}^{(\lambda)}(s^{{}^{\prime}}|s)\varphi(s)-\varphi(s)$
of (96) as follows,

$\displaystyle\tilde{\gamma}\sum_{s^{{}^{\prime}}\in\mathcal{S}}\mathbb{P}_{\pi_{\bm{\theta}}}^{(\lambda)}(s^{{}^{\prime}}|s)\varphi(s^{{}^{\prime}})-\varphi(s)$
$\displaystyle\overset{(\ref{lam-pro-value-02})}{=}$
$\displaystyle\tilde{\gamma}(1-\gamma\lambda)\sum_{s^{{}^{\prime}}\in\mathcal{S}}\sum_{{t}=0}^{\infty}(\gamma\lambda)^{{t}}\mathbb{P}_{\pi_{\bm{\theta}}}(s_{t+1}=s^{{}^{\prime}}|s)\varphi(s^{{}^{\prime}})-\varphi(s)$
(100) $\displaystyle\overset{(\ref{def:matrix-p-lam-return})}{=}$
$\displaystyle\gamma(1-\lambda)\sum_{s^{{}^{\prime}}\in\mathcal{S}}\sum_{{t}=0}^{\infty}(\gamma\lambda)^{{t}}\mathbb{P}_{\pi_{\bm{\theta}}}(s_{t+1}=s^{{}^{\prime}}|s)\varphi(s^{{}^{\prime}})-\varphi(s)$
(101) $\displaystyle=$
$\displaystyle\gamma\sum_{s^{{}^{\prime}}\in\mathcal{S}}\sum_{{t}=0}^{\infty}(\gamma\lambda)^{{t}}\mathbb{P}_{\pi_{\bm{\theta}}}(s_{t+1}=s^{{}^{\prime}}|s)\varphi(s^{{}^{\prime}})-\sum_{s^{{}^{\prime}}\in\mathcal{S}}\underbrace{\left(\sum_{{t}=0}^{\infty}(\gamma\lambda)^{{t}+1}\mathbb{P}_{\pi_{\bm{\theta}}}(s_{t+1}=s^{{}^{\prime}}|s)\varphi(s^{{}^{\prime}})\right)}_{=\sum_{{t}=1}^{\infty}(\gamma\lambda)^{{t}}\mathbb{P}_{\pi_{\bm{\theta}}}(s_{t}=s^{{}^{\prime}}|s)\varphi(s^{{}^{\prime}})}-\varphi(s)$
$\displaystyle=$
$\displaystyle\gamma\sum_{s^{{}^{\prime}}\in\mathcal{S}}\sum_{{t}=0}^{\infty}(\gamma\lambda)^{{t}}\mathbb{P}_{\pi_{\bm{\theta}}}(s_{t+1}=s^{{}^{\prime}}|s)\varphi(s^{{}^{\prime}})-\underbrace{\left(\sum_{s^{{}^{\prime}}\in\mathcal{S}}\sum_{{t}=1}^{\infty}(\gamma\lambda)^{{t}}\mathbb{P}_{\pi_{\bm{\theta}}}(s_{t}=s^{{}^{\prime}}|s)\varphi(s^{{}^{\prime}})+\varphi(s)\right)}_{=\sum_{s^{{}^{\prime}}\in\mathcal{S}}\sum_{{t}=0}^{\infty}(\gamma\lambda)^{{t}}\mathbb{P}_{\pi_{\bm{\theta}}}(s_{t}=s^{{}^{\prime}}|s)\varphi(s^{{}^{\prime}})}$
(102) $\displaystyle=$
$\displaystyle\gamma\sum_{s^{{}^{\prime}}\in\mathcal{S}}\sum_{{t}=0}^{\infty}(\gamma\lambda)^{{t}}\mathbb{P}_{\pi_{\bm{\theta}}}(s_{t+1}=s^{{}^{\prime}}|s)\varphi(s^{{}^{\prime}})-\sum_{s_{t}\in\mathcal{S}}\sum_{{t}=0}^{\infty}(\gamma\lambda)^{{t}}\mathbb{P}_{\pi_{\bm{\theta}}}(s_{t}|s)\varphi(s),$
(103)

where the equation from Eq.(102) to Eq.(103) holds since: according to (45),
we use the following identity

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

Furthermore, take the result (99) and (103) to (98), we have

$\displaystyle
R^{(\lambda)}_{\pi_{\bm{\theta}}}(s)+\tilde{\gamma}\sum_{s^{{}^{\prime}}\in\mathcal{S}}\mathbb{P}_{\pi_{\bm{\theta}}}^{(\lambda)}(s^{{}^{\prime}}|s)\varphi(s^{{}^{\prime}})-\varphi(s)$
$\displaystyle=$
$\displaystyle\sum_{{t}=0}^{\infty}(\gamma\lambda)^{t}\left(\sum_{s_{t}\in\mathcal{S}}\mathbb{P}_{\pi_{\bm{\theta}}}(s_{t}|s)R_{\pi_{\bm{\theta}}}(s_{t})+\gamma\sum_{s^{{}^{\prime}}\in\mathcal{S}}\underbrace{\mathbb{P}_{\pi_{\bm{\theta}}}(s_{t+1}=s^{{}^{\prime}}|s)\varphi(s^{{}^{\prime}})}_{\overset{(\ref{pro-
pi-t-step-
app})}{=}\sum_{s_{t}\in\mathcal{S}}\mathbb{P}_{\pi_{\bm{\theta}}}(s_{t+1}=s^{{}^{\prime}}|s_{t})\mathbb{P}_{\pi_{\bm{\theta}}}(s_{t}|s)\varphi(s^{{}^{\prime}})}-\sum_{s_{t}\in\mathcal{S}}\mathbb{P}_{\pi_{\bm{\theta}}}(s_{t}|s)\varphi(s_{t})\right)$
(104) $\displaystyle=$
$\displaystyle\sum_{{t}=0}^{\infty}(\gamma\lambda)^{t}\left(\sum_{s_{t}\in\mathcal{S}}\mathbb{P}_{\pi_{\bm{\theta}}}(s_{t}|s)R_{\pi_{\bm{\theta}}}(s_{t})+\gamma\sum_{s_{t}\in\mathcal{S}}\mathbb{P}_{\pi_{\bm{\theta}}}(s_{t}|s)\sum_{s_{t+1}\in\mathcal{S}}\mathbb{P}_{\pi_{\bm{\theta}}}(s_{t+1}|s_{t})\varphi(s_{t+1})-\sum_{s_{t}\in\mathcal{S}}\mathbb{P}_{\pi_{\bm{\theta}}}(s_{t}|s)\varphi(s_{t})\right)$
(105) $\displaystyle=$
$\displaystyle\sum_{{t}=0}^{\infty}(\gamma\lambda)^{t}\sum_{s_{t}\in\mathcal{S}}\mathbb{P}_{\pi_{\bm{\theta}}}(s_{t}|s)\left(\underbrace{\sum_{a_{t}\in\mathcal{A}}{\pi_{\bm{\theta}}}(a_{t}|s_{t})\sum_{s_{t+1}\in\mathcal{S}}\mathbb{P}(s_{t+1}|s_{t},a_{t})r(s_{t+1}|s_{t},a_{t})}_{=R_{\pi_{\bm{\theta}}}(s_{t})}\right.$
$\displaystyle\left.~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}+\gamma\underbrace{\sum_{a_{t}\in\mathcal{A}}{\pi_{\bm{\theta}}}(a_{t}|s_{t})\sum_{s_{t+1}\in\mathcal{S}}\mathbb{P}(s_{t+1}|s_{t},a_{t})}_{=\mathbb{P}_{\pi_{\bm{\theta}}}(s_{t+1}|s_{t})}\varphi(s_{t+1})-\varphi(s_{t})\right)$
$\displaystyle=$
$\displaystyle\sum_{{t}=0}^{\infty}(\gamma\lambda)^{t}\sum_{s_{t}\in\mathcal{S}}\mathbb{P}_{\pi_{\bm{\theta}}}(s_{t}|s)\sum_{a_{t}\in\mathcal{A}}{\pi_{\bm{\theta}}}(a_{t}|s_{t})\sum_{s_{t+1}\in\mathcal{S}}\mathbb{P}(s_{t+1}|s_{t},a_{t})\left(r(s_{t+1}|s_{t},a_{t})+\gamma\varphi(s_{t+1})-\varphi(s_{t})\right)$
(106) $\displaystyle=$
$\displaystyle\sum_{{t}=0}^{\infty}(\gamma\lambda)^{t}\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[r(s_{t+1}|s_{t},a_{t})+\gamma\varphi(s_{t+1})-\varphi(s_{t})\right],$
(107)

the equation from Eq.(103) to Eq.(104) holds since:

$\mathbb{P}_{\pi_{\bm{\theta}}}(s_{t+1}|s)\overset{(\ref{pro-pi-t-step-
app})}{=}\sum_{s_{t}\in\mathcal{S}}\mathbb{P}_{\pi_{\bm{\theta}}}(s_{t+1}|s_{t})\mathbb{P}_{\pi_{\bm{\theta}}}(s_{t}|s);$

the equation from Eq.(104) to Eq.(105) holds since we use the Markov property
of the definition of MDP: for each time $t\in\mathbb{N}$,

$\mathbb{P}_{\pi_{\bm{\theta}}}(s_{t+1}=s^{{}^{\prime}}|s_{t}=s)=\mathbb{P}_{\pi_{\bm{\theta}}}(s^{{}^{\prime}}|s);$

the equation (106) the following identity:

$\sum_{a_{t}\in\mathcal{A}}{\pi_{\bm{\theta}}}(a_{t}|s_{t})=1,~{}~{}~{}~{}\sum_{s_{t+1}\in\mathcal{S}}\mathbb{P}(s_{t+1}|s_{t},a_{t})=1,$

then

$\varphi(s_{t})=\sum_{a_{t}\in\mathcal{A}}{\pi_{\bm{\theta}}}(a_{t}|s_{t})\sum_{s_{t+1}\in\mathcal{S}}\mathbb{P}(s_{t+1}|s_{t},a_{t})\varphi(s_{t}).$

Step 3: Put all the result together.

Finally, 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],$

combining the results (95) and (107), we have

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

This concludes the proof of Proposition E.1. ∎

##  Appendix F Lemma F.1

######  Lemma F.1.

Let
$\|\bm{\Pi}_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}-\bm{\Pi}_{\pi_{\bm{\theta}}}\|_{1,1}$
denote as the $L_{1,1}$-norm for the difference between two policy space
$\\{\pi_{\bm{\theta}}(a|s)\\}_{(s,a)\in\mathcal{S}\times\mathcal{A}}$,
$\\{\pi_{{\bm{\theta}}^{{}^{\prime}}}(a|s)\\}_{(s,a)\in\mathcal{S}\times\mathcal{A}}$,
i.e.,

$\displaystyle\|\bm{\Pi}_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}-\bm{\Pi}_{\pi_{\bm{\theta}}}\|_{1,1}=:\sum_{s\in\mathcal{S}}\sum_{a\in\mathcal{A}}\left|{{\pi_{{\bm{\theta}}^{{}^{\prime}}}}}(a|s)-{{\pi_{\bm{\theta}}}}(a|s)\right|.$
(109)

The divergence between discounted future state visitation distributions,
$\|\mathbf{d}_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}^{\lambda}-\mathbf{d}_{\pi_{\bm{\theta}}}^{\lambda}\|_{1}$,
is bounded as follows,

$\|\mathbf{d}_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}^{\lambda}-\mathbf{d}_{\pi_{\bm{\theta}}}^{\lambda}\|_{1}\leq\dfrac{(1-\gamma\lambda)^{2}}{(1-\gamma)\left(1-\gamma\lambda\|\bm{\Pi}_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}-\bm{\Pi}_{\pi_{\bm{\theta}}}\|_{1,1}\right)}\operatorname{\mathbb{E}}_{s\sim
d_{\pi_{\bm{\theta}}}^{\lambda}(\cdot)}\Big{[}2D_{\emph{TV}}(\pi_{{\bm{\theta}}^{{}^{\prime}}},\pi_{\bm{\theta}})[s]\Big{]}$

and

$\|\mathbf{d}_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}^{\lambda}-\mathbf{d}_{\pi_{\bm{\theta}}}^{\lambda}\|_{1}\leq\dfrac{(1-\gamma\lambda)^{2}}{(1-\gamma)\left(1-\gamma\lambda\|\bm{\Pi}_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}-\bm{\Pi}_{\pi_{\bm{\theta}}}\|_{1,1}\right)}\operatorname{\mathbb{E}}_{s\sim
d_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}^{\lambda}(\cdot)}\Big{[}2D_{\emph{TV}}(\pi_{{\bm{\theta}}^{{}^{\prime}}},\pi_{\bm{\theta}})[s]\Big{]},$

where

$2D_{\emph{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|.$

Furthermore, we achieve the boundedness of
$\|\mathbf{d}_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}^{\lambda}-\mathbf{d}_{\pi_{\bm{\theta}}}^{\lambda}\|_{1}$
as follows,

$\displaystyle\|\mathbf{d}_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}^{\lambda}-\mathbf{d}_{\pi_{\bm{\theta}}}^{\lambda}\|_{1}\leq\dfrac{1}{1-\tilde{\gamma}}\cdot\dfrac{1-\gamma\lambda}{\left|1-2\gamma\lambda|\mathcal{S}||\mathcal{A}|\right|}\operatorname{\mathbb{E}}_{s\sim
d_{\pi_{\bm{\theta}}}^{\lambda}(\cdot)}\Big{[}2D_{\emph{TV}}(\pi_{{\bm{\theta}}^{{}^{\prime}}},\pi_{\bm{\theta}})[s]\Big{]},$
$\displaystyle\|\mathbf{d}_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}^{\lambda}-\mathbf{d}_{\pi_{\bm{\theta}}}^{\lambda}\|_{1}\leq\dfrac{1}{1-\tilde{\gamma}}\cdot\dfrac{1-\gamma\lambda}{\left|1-2\gamma\lambda|\mathcal{S}||\mathcal{A}|\right|}\operatorname{\mathbb{E}}_{s\sim
d_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}^{\lambda}(\cdot)}\Big{[}2D_{\emph{TV}}(\pi_{{\bm{\theta}}^{{}^{\prime}}},\pi_{\bm{\theta}})[s]\Big{]}.$

###### Proof.

Recall Eq.(63), let

$\displaystyle\mathbf{G}_{\pi_{\bm{\theta}}}=\left(\mathbf{I}-\tilde{\gamma}\mathbf{P}^{(\lambda)}_{\pi_{\bm{\theta}}}\right)^{-1},~{}~{}\mathbf{G}_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}=\left(\mathbf{I}-\tilde{\gamma}\mathbf{P}^{(\lambda)}_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}\right)^{-1},~{}~{}\mathbf{D}=\mathbf{P}^{(\lambda)}_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}-\mathbf{P}^{(\lambda)}_{\pi_{\bm{\theta}}}.$
(110)

Then, the following holds

$\displaystyle\mathbf{G}_{\pi_{\bm{\theta}}}^{-1}-\mathbf{G}_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}^{-1}=\left(\mathbf{I}-\tilde{\gamma}\mathbf{P}^{(\lambda)}_{\pi_{\bm{\theta}}}\right)-\left(\mathbf{I}-\tilde{\gamma}\mathbf{P}^{(\lambda)}_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}\right)=\tilde{\gamma}\mathbf{D}.$
(111)

Furthermore, by left-multiplying by $\mathbf{G}_{\pi_{\bm{\theta}}}$ and
right-multiplying by $\mathbf{G}_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}$, we
achieve

$\displaystyle\mathbf{G}_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}-\mathbf{G}_{\pi_{\bm{\theta}}}=\tilde{\gamma}\mathbf{G}_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}\mathbf{D}\mathbf{G}_{\pi_{\bm{\theta}}}.$
(112)

Grouping all the results from (110)-(112), recall (63),

$\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}=(1-\tilde{\gamma})\mathbf{G}_{\pi_{\bm{\theta}}}\bm{\rho}_{0},$
(113)

then we have

$\displaystyle\mathbf{d}_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}^{\lambda}-\mathbf{d}_{\pi_{\bm{\theta}}}^{\lambda}=$
$\displaystyle(1-\tilde{\gamma})\left(\mathbf{G}_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}-\mathbf{G}_{\pi_{\bm{\theta}}}\right)\bm{\rho}_{0}$
$\displaystyle\overset{(\ref{app-g-03})}{=}$
$\displaystyle(1-\tilde{\gamma})\tilde{\gamma}\mathbf{G}_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}\mathbf{D}\mathbf{G}_{\pi_{\bm{\theta}}}\bm{\rho}_{0}$
$\displaystyle\overset{(\ref{matrixversion-lambda-dis-state-
distribution-001})}{=}$
$\displaystyle\tilde{\gamma}\mathbf{G}_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}\mathbf{D}\mathbf{d}_{\pi_{\bm{\theta}}}^{\lambda}.$
(114)

Applying (114), we have

$\displaystyle\|\mathbf{d}_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}^{\lambda}-\mathbf{d}_{\pi_{\bm{\theta}}}^{\lambda}\|_{1}\overset{(\ref{app-
error-
gap-01})}{\leq}\tilde{\gamma}\|\mathbf{G}_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}\|_{1}\|\mathbf{D}\mathbf{d}_{\pi_{\bm{\theta}}}^{\lambda}\|_{1}.$
(115)

Firstly, we bound the term
$\|\mathbf{G}_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}\|_{1}$ as follows,

$\displaystyle\|\mathbf{G}_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}\|_{1}=\left\|\left(\mathbf{I}-\tilde{\gamma}\mathbf{P}^{(\lambda)}_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}\right)^{-1}\right\|_{1}\leq\sum_{t=0}^{\infty}\tilde{\gamma}^{t}\left\|\mathbf{P}^{(\lambda)}_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}\right\|_{1}=\dfrac{1}{1-\tilde{\gamma}}=\dfrac{1-\gamma\lambda}{1-\gamma}.$
(116)

Now, we analyze the second term as follows,

$\displaystyle\|\mathbf{D}\mathbf{d}_{\pi_{\bm{\theta}}}^{\lambda}\|_{1}$
$\displaystyle=$
$\displaystyle\sum_{s^{{}^{\prime}}\in\mathcal{S}}\left|\sum_{s\in\mathcal{S}}\mathbf{D}(s^{{}^{\prime}}|s)d_{\pi_{\bm{\theta}}}^{\lambda}(s)\right|$
$\displaystyle\overset{(\ref{lam-pro-value-02})}{=}$
$\displaystyle\sum_{s^{{}^{\prime}}\in\mathcal{S}}\left|\sum_{s\in\mathcal{S}}\left(\mathbb{P}_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}^{(\lambda)}(s^{{}^{\prime}}|s)-\mathbb{P}_{\pi_{\bm{\theta}}}^{(\lambda)}(s^{{}^{\prime}}|s)\right)\right|d_{\pi_{\bm{\theta}}}^{\lambda}(s)$
$\displaystyle\overset{(\ref{lam-pro-value-02})}{=}$
$\displaystyle\sum_{s^{{}^{\prime}}\in\mathcal{S}}\left|(1-\gamma\lambda)\sum_{{t}=0}^{\infty}(\gamma\lambda)^{{t}}\sum_{s\in\mathcal{S}}\left(\mathbb{P}_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}(s_{t+1}=s^{{}^{\prime}}|s)-\mathbb{P}_{\pi_{\bm{\theta}}}(s_{t+1}=s^{{}^{\prime}}|s)\right)\right|d_{\pi_{\bm{\theta}}}^{\lambda}(s)$
$\displaystyle\leq$
$\displaystyle\sum_{s\in\mathcal{S}}\left((1-\gamma\lambda)\sum_{{t}=0}^{\infty}(\gamma\lambda)^{{t}}\sum_{s^{{}^{\prime}}\in\mathcal{S}}\left|\mathbb{P}_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}(s_{t+1}=s^{{}^{\prime}}|s)-\mathbb{P}_{\pi_{\bm{\theta}}}(s_{t+1}=s^{{}^{\prime}}|s)\right|\right)d_{\pi_{\bm{\theta}}}^{\lambda}(s).$
(117)

.

Before we provide a further analyze (117), we need to bound
$|\mathbb{P}_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}(s_{t+1}=s^{{}^{\prime}}|s)-\mathbb{P}_{\pi_{\bm{\theta}}}(s_{t+1}=s^{{}^{\prime}}|s)|$.
Let $s_{0}=s$, then

$\displaystyle\mathbb{P}_{{\pi_{\bm{\theta}}}}(s_{t+1}=s^{{}^{\prime}}|s)\overset{\ref{pro-
pi-t-step-app}}{=}$
$\displaystyle\sum_{s_{1}\in\mathcal{S}}\mathbb{P}_{{\pi_{\bm{\theta}}}}(s_{t+1}=s^{{}^{\prime}}|s_{1})\mathbb{P}_{{\pi_{\bm{\theta}}}}(s_{1}|s_{0})$
$\displaystyle=$
$\displaystyle\sum_{s_{1}\in\mathcal{S}}\sum_{s_{2}\in\mathcal{S}}\mathbb{P}_{{\pi_{\bm{\theta}}}}(s_{t+1}=s^{{}^{\prime}}|s_{2})\mathbb{P}_{{\pi_{\bm{\theta}}}}(s_{2}|s_{1})\mathbb{P}_{{\pi_{\bm{\theta}}}}(s_{1}|s_{0})$
$\displaystyle=$ $\displaystyle\cdots$ $\displaystyle=$
$\displaystyle\sum_{s_{1}\in\mathcal{S}}\sum_{s_{2}\in\mathcal{S}}\cdots\sum_{s_{t}\in\mathcal{S}}\left(\prod_{i=1}^{t+1}\mathbb{P}_{{\pi_{\bm{\theta}}}}(s_{i}|s_{i-1})\right)$
$\displaystyle=$
$\displaystyle\sum_{s_{1}\in\mathcal{S}}\sum_{s_{2}\in\mathcal{S}}\cdots\sum_{s_{t}\in\mathcal{S}}\left(\prod_{i=1}^{t+1}\left(\sum_{a_{i}\in\mathcal{A}}\mathbb{P}(s_{i}|s_{i-1},a_{i}){{\pi_{\bm{\theta}}}}(a_{i}|s_{i-1})\right)\right).$
(118)

Similarly, we have

$\displaystyle\mathbb{P}_{{\pi_{{\bm{\theta}}^{{}^{\prime}}}}}(s_{t+1}=s^{{}^{\prime}}|s)=$
$\displaystyle\sum_{s_{1}\in\mathcal{S}}\sum_{s_{2}\in\mathcal{S}}\cdots\sum_{s_{t}\in\mathcal{S}}\left(\prod_{i=1}^{t+1}\left(\sum_{a_{i}\in\mathcal{A}}\mathbb{P}(s_{i}|s_{i-1},a_{i}){{\pi_{{\bm{\theta}}^{{}^{\prime}}}}}(a_{i}|s_{i-1})\right)\right).$
(119)

Then, according to the results (118)-(119), let $s_{0}=s$, the following holds

$\displaystyle\sum_{s^{{}^{\prime}}\in\mathcal{S}}|\mathbb{P}_{{\pi_{{\bm{\theta}}^{{}^{\prime}}}}}(s_{t+1}=s^{{}^{\prime}}|s)-\mathbb{P}_{{\pi_{\bm{\theta}}}}(s_{t+1}=s^{{}^{\prime}}|s)|$
$\displaystyle=$
$\displaystyle\sum_{s^{{}^{\prime}}\in\mathcal{S}}\left|\sum_{s_{1}\in\mathcal{S}}\sum_{s_{2}\in\mathcal{S}}\cdots\sum_{s_{t}\in\mathcal{S}}\left(\prod_{i=1}^{t+1}\left(\sum_{a_{i}\in\mathcal{A}}\mathbb{P}(s_{i}|s_{i-1},a_{i})\left({{\pi_{{\bm{\theta}}^{{}^{\prime}}}}}(a_{i}|s_{i-1})-{{\pi_{\bm{\theta}}}}(a_{i}|s_{i-1})\right)\right)\right)\right|$
$\displaystyle\leq$
$\displaystyle\sum_{s_{1}\in\mathcal{S}}\sum_{s_{2}\in\mathcal{S}}\cdots\sum_{s_{t}\in\mathcal{S}}\left(\prod_{i=1}^{t+1}\sum_{a_{i}\in\mathcal{A}}\left|{{\pi_{{\bm{\theta}}^{{}^{\prime}}}}}(a_{i}|s_{i-1})-{{\pi_{\bm{\theta}}}}(a_{i}|s_{i-1})\right|\right)$
$\displaystyle=$
$\displaystyle\sum_{s_{1}\in\mathcal{S}}\sum_{s_{2}\in\mathcal{S}}\cdots\sum_{s_{t}\in\mathcal{S}}\left(\prod_{i=2}^{t+1}\sum_{a_{i}\in\mathcal{A}}\left|{{\pi_{{\bm{\theta}}^{{}^{\prime}}}}}(a_{i}|s_{i-1})-{{\pi_{\bm{\theta}}}}(a_{i}|s_{i-1})\right|\right)\cdot\left(\sum_{a_{1}\in\mathcal{A}}\left|{{\pi_{{\bm{\theta}}^{{}^{\prime}}}}}(a_{1}|s_{0})-{{\pi_{\bm{\theta}}}}(a_{1}|s_{0})\right|\right)$
$\displaystyle=$
$\displaystyle\prod_{i=2}^{t+1}\left(\sum_{s_{i-1}\in\mathcal{S}}\sum_{a_{i}\in\mathcal{A}}\left|{{\pi_{{\bm{\theta}}^{{}^{\prime}}}}}(a_{i}|s_{i-1})-{{\pi_{\bm{\theta}}}}(a_{i}|s_{i-1})\right|\right)\cdot\left(\sum_{a_{1}\in\mathcal{A}}\left|{{\pi_{{\bm{\theta}}^{{}^{\prime}}}}}(a_{1}|s_{0})-{{\pi_{\bm{\theta}}}}(a_{1}|s_{0})\right|\right)$
$\displaystyle=$
$\displaystyle\left(\underbrace{\sum_{s\in\mathcal{S}}\sum_{a\in\mathcal{A}}\left|{{\pi_{{\bm{\theta}}^{{}^{\prime}}}}}(a|s)-{{\pi_{\bm{\theta}}}}(a|s)\right|}_{=:\left\|\bm{\Pi}_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}-\bm{\Pi}_{\pi_{\bm{\theta}}}\right\|_{1,1}}\right)^{t}\cdot\left(\sum_{a\in\mathcal{A}}\left|{{\pi_{{\bm{\theta}}^{{}^{\prime}}}}}(a|s)-{{\pi_{\bm{\theta}}}}(a|s)\right|\right).$
(120)

Taking the result (120) to (117), we have

$\displaystyle\|\mathbf{D}\mathbf{d}_{\pi_{\bm{\theta}}}^{\lambda}\|_{1}\leq$
$\displaystyle(1-\gamma\lambda)\sum_{{t}=0}^{\infty}(\gamma\lambda)^{{t}}\left\|\bm{\Pi}_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}-\bm{\Pi}_{\pi_{\bm{\theta}}}\right\|^{t}_{1,1}\sum_{s\in\mathcal{S}}\underbrace{\sum_{a\in\mathcal{A}}\left|{{\pi_{{\bm{\theta}}^{{}^{\prime}}}}}(a|s)-{{\pi_{\bm{\theta}}}}(a|s)\right|}_{=:2D_{\text{TV}}(\pi_{{\bm{\theta}}^{{}^{\prime}}},\pi_{\bm{\theta}})[s]}d_{\pi_{\bm{\theta}}}^{\lambda}(s)$
$\displaystyle=$
$\displaystyle(1-\gamma\lambda)\sum_{{t}=0}^{\infty}(\gamma\lambda)^{{t}}\|\bm{\Pi}_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}-\bm{\Pi}_{\pi_{\bm{\theta}}}\|^{t}_{1,1}\operatorname{\mathbb{E}}_{s\sim
d_{\pi_{\bm{\theta}}}^{\lambda}(\cdot)}\Big{[}2D_{\text{TV}}(\pi_{{\bm{\theta}}^{{}^{\prime}}},\pi_{\bm{\theta}})[s]\Big{]}$
$\displaystyle=$
$\displaystyle\dfrac{1-\gamma\lambda}{1-\gamma\lambda\|\bm{\Pi}_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}-\bm{\Pi}_{\pi_{\bm{\theta}}}\|_{1,1}}\operatorname{\mathbb{E}}_{s\sim
d_{\pi_{\bm{\theta}}}^{\lambda}(\cdot)}\Big{[}2D_{\text{TV}}(\pi_{{\bm{\theta}}^{{}^{\prime}}},\pi_{\bm{\theta}})[s]\Big{]}.$
(121)

Finally, according to (115), (116) and (121), we have

$\displaystyle\|\mathbf{d}_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}^{\lambda}-\mathbf{d}_{\pi_{\bm{\theta}}}^{\lambda}\|_{1}\leq\dfrac{\tilde{\gamma}}{1-\tilde{\gamma}}\cdot\dfrac{\gamma(1-\lambda)}{1-\gamma\lambda\|\bm{\Pi}_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}-\bm{\Pi}_{\pi_{\bm{\theta}}}\|_{1,1}}\operatorname{\mathbb{E}}_{s\sim
d_{\pi_{\bm{\theta}}}^{\lambda}(\cdot)}\Big{[}2D_{\text{TV}}(\pi_{{\bm{\theta}}^{{}^{\prime}}},\pi_{\bm{\theta}})[s]\Big{]}.$
(122)

Recall (109), we have

$\displaystyle\|\bm{\Pi}_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}-\bm{\Pi}_{\pi_{\bm{\theta}}}\|_{1,1}=\sum_{s\in\mathcal{S}}\sum_{a\in\mathcal{A}}\left|{{\pi_{{\bm{\theta}}^{{}^{\prime}}}}}(a|s)-{{\pi_{\bm{\theta}}}}(a|s)\right|\leq
2|\mathcal{S}||\mathcal{A}|.$ (123)

Then, we achieve the boundedness of
$\|\bm{\Pi}_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}-\bm{\Pi}_{\pi_{\bm{\theta}}}\|_{1,1}$
as follows,

$\displaystyle\|\mathbf{d}_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}^{\lambda}-\mathbf{d}_{\pi_{\bm{\theta}}}^{\lambda}\|_{1}\leq\dfrac{\tilde{\gamma}}{1-\tilde{\gamma}}\cdot\dfrac{1-\gamma\lambda}{\left|1-2\gamma\lambda|\mathcal{S}||\mathcal{A}|\right|}\operatorname{\mathbb{E}}_{s\sim
d_{\pi_{\bm{\theta}}}^{\lambda}(\cdot)}\Big{[}2D_{\text{TV}}(\pi_{{\bm{\theta}}^{{}^{\prime}}},\pi_{\bm{\theta}})[s]\Big{]}.$
(124)

Similarly, we obtain

$\displaystyle\|\mathbf{d}_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}^{\lambda}-\mathbf{d}_{\pi_{\bm{\theta}}}^{\lambda}\|_{1}\leq\dfrac{1}{1-\tilde{\gamma}}\cdot\dfrac{1-\gamma\lambda}{\left|1-2\gamma\lambda|\mathcal{S}||\mathcal{A}|\right|}\operatorname{\mathbb{E}}_{s\sim
d_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}^{\lambda}(\cdot)}\Big{[}2D_{\emph{TV}}(\pi_{{\bm{\theta}}^{{}^{\prime}}},\pi_{\bm{\theta}})[s]\Big{]}.$

∎

##  Appendix G Proof of Theorem 4.1

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_

$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|}.$

###### Proof.

(of Theorem 4.1)

According to Bregman divergence, if policy $\pi_{\bm{\theta}_{k}}$ is
feasible, policy $\pi_{\bm{\theta}_{k+1}}$ is generated according to (19),
then the following

$\text{KL}\left(\pi_{\bm{\theta}_{k}},\pi_{\bm{\theta}_{k+\frac{1}{2}}}\right)\geq\text{KL}\left(\pi_{\bm{\theta}_{k}},\pi_{\bm{\theta}_{k+1}}\right)+\text{KL}\left(\pi_{\bm{\theta}_{k+1}},\pi_{\bm{\theta}_{k+\frac{1}{2}}}\right)$

implies

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

According to the asymptotically symmetry of KL divergence if we update the
policy within a local region, then, we have

$\chi_{k}\geq\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}_{k}}\right)[s]\right]\geq\operatorname{\mathbb{E}}_{s\sim{d}_{{\pi_{\bm{\theta}_{k}}}}^{\lambda}(\cdot)}\left[\text{KL}\left(\pi_{\bm{\theta}_{k+1}},\pi_{\bm{\theta}_{k}}\right)[s]\right].$

Furthermore, according to Proposition 3.2 and Proposition 3.4, we have

$\displaystyle J(\pi_{\bm{\theta}_{k+1}})-J(\pi_{\bm{\theta}_{k}})$
$\displaystyle\geq$
$\displaystyle\frac{1}{1-\tilde{\gamma}}\operatorname{\mathbb{E}}_{s\sim{d}_{\pi_{\bm{\theta}_{k}}}^{\lambda}(\cdot),a\sim\pi_{\bm{\theta}_{k+1}}(\cdot|s)}\left[A^{\text{GAE}(\gamma,\lambda)}_{\pi_{\bm{\theta}_{k}}}(s,a)-\frac{2\gamma(1-\lambda)\epsilon^{V}_{\pi_{\bm{\theta}_{k+1}}}(\pi_{\bm{\theta}_{k}})}{(1-\gamma\lambda)\left|1-2\gamma\lambda|\mathcal{S}||\mathcal{A}|\right|}D_{\text{TV}}(\pi_{\bm{\theta}_{k}},\pi_{\bm{\theta}_{k+1}})[s]\right]$
$\displaystyle\geq$
$\displaystyle\frac{1}{1-\tilde{\gamma}}\operatorname{\mathbb{E}}_{s\sim{d}_{\pi_{\bm{\theta}_{k}}}^{\lambda}(\cdot),a\sim\pi_{\bm{\theta}_{k+1}}(\cdot|s)}\left[-\frac{2\gamma(1-\lambda)\alpha_{k}\epsilon^{V}_{\pi_{\bm{\theta}_{k+1}}}(\pi_{\bm{\theta}_{k}})}{(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}_{k}}}^{\lambda}(\cdot)}\left[\text{KL}(\pi_{\bm{\theta}_{k}},\pi_{\bm{\theta}_{k+1}})[s]\right]}\right]$
$\displaystyle\geq$
$\displaystyle\frac{1}{1-\tilde{\gamma}}\operatorname{\mathbb{E}}_{s\sim{d}_{\pi_{\bm{\theta}_{k}}}^{\lambda}(\cdot),a\sim\pi_{\bm{\theta}_{k+1}}(\cdot|s)}\left[-\frac{\gamma(1-\lambda)\alpha_{k}\sqrt{2\chi_{k}}\epsilon^{V}_{\pi_{\bm{\theta}_{k+1}}}(\pi_{\bm{\theta}_{k}})}{(1-\gamma\lambda)\left|1-2\gamma\lambda|\mathcal{S}||\mathcal{A}|\right|}\right].$

Similarly, according to Proposition 3.2 and Proposition 3.3, and since policy
$\pi_{\bm{\theta}_{k+1}}$ satisfies

$\displaystyle
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}_{k+1}}(\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}_{k+1}})[s]\right]}\leq
b,$ (125)

and

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

Combining (125)- (127), we have

$\displaystyle J^{c}(\pi_{\bm{\theta}_{k+1}})-J^{c}(\pi_{\bm{\theta}_{k}})$
(127) $\displaystyle\leq$ $\displaystyle
b+\frac{1}{1-\tilde{\gamma}}\operatorname{\mathbb{E}}_{s\sim{d}_{\pi_{\bm{\theta}_{k}}}^{\lambda}(\cdot),a\sim\pi_{\bm{\theta}_{k+1}}(\cdot|s)}\left[\frac{2\gamma(1-\lambda)\beta_{k}\epsilon^{C}_{\pi_{\bm{\theta}_{k+1}}}(\pi_{\bm{\theta}_{k}})}{(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}_{k}}}^{\lambda}(\cdot)}\left[\text{KL}(\pi_{\bm{\theta}_{k}},\pi_{\bm{\theta}_{k+1}})[s]\right]}\right]$
$\displaystyle\leq$ $\displaystyle
b+\frac{1}{1-\tilde{\gamma}}\operatorname{\mathbb{E}}_{s\sim{d}_{\pi_{\bm{\theta}_{k}}}^{\lambda}(\cdot),a\sim\pi_{\bm{\theta}_{k+1}}(\cdot|s)}\left[\frac{\gamma(1-\lambda)\beta_{k}\sqrt{2\chi_{k}}\epsilon^{C}_{\pi_{\bm{\theta}_{k+1}}}(\pi_{\bm{\theta}_{k}})}{(1-\gamma\lambda)\left|1-2\gamma\lambda|\mathcal{S}||\mathcal{A}|\right|}\right].$
(128)

∎

##  Appendix H More Details for Experiments

All experiments were implemented in Pytorch 1.7.0 with CUDA 11.0 and conducted
on an Ubuntu 20.04.2 LTS (GNU/Linux 5.8.0-59-generic x86 64) with 40 CPU cores
(Intel(R) Xeon(R) Silver 4210R CPU @ 2.40GHz), 251G memory and 4 GPU cards
(GeForce RTX 3080). The baseline algorithm FOCOPS based on
https://github.com/ymzhang01/focops, which were offical code library. The
other baseline algorithms include CPO, TRPO-L, PPO-L based on
https://github.com/openai/safety-starter-agents, which published by OpenAI.

###  H.1 Robots with Speed limit

We used the MuJoCo environments provided by OpenAI Gym [Brockman et al., 2016]
for this set of experiments. For agents manuvering on a two-dimensional plane,
the cost is calculated as

$C(s,a)=\sqrt{v_{x}^{2}+v_{y}^{2}}$

For agents moving along a straight line, the cost is calculated as

$C(s,a)=|v_{x}|$

where $v_{x},v_{y}$ are the velocities of the agent in the $x$ and $y$
directions respectively.

###  H.2 Robots with Circle

Figure 5: In the Circle task, reward is maximized by moving along the green
circle. The agent is not allowed to enter the blue regions, so its optimal
constrained path follows the line segments $AD$ and $BC$.

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

$\displaystyle R(s)$
$\displaystyle=\frac{v^{T}[-y,x]}{1+\left|\|[x,y]\|_{2}-d\right|},$
$\displaystyle C(s)$ $\displaystyle=\boldsymbol{1}\left[|x|>x_{lim}\right],$

where $x,y$ are the coordinates in the plane, $v$ is the velocity, and
$d,x_{lim}$ are environmental parameters.

###  H.3 Algorithm Parameters

Hyperparameter | CUP | PPO-L | TRPO-L | CPO | FOCOPS
---|---|---|---|---|---
No. of hidden layers | 2 | 2 | 2 | 2 | 2
No. of hidden nodes | 64 | 64 | 64 | 64 | 64
Activation | $\tanh$ | $\tanh$ | $\tanh$ | $\tanh$ | $\tanh$
Initial log std | -0.5 | -0.5 | -1 | -0.5 | -0.5
Discount for reward $\gamma$ | 0.99 | 0.99 | 0.99 | 0.99 | 0.99
Discount for cost $\gamma_{C}$ | 0.99 | 0.99 | 0.99 | 0.99 | 0.99
Batch size | 5000 | 5000 | 5000 | 5000 | 5000
Minibatch size | 64 | 64 | N/A | N/A | 64
No. of optimization epochs | 10 | 10 | N/A | N/A | 10
Maximum episode length | 1000 | 1000 | 1000 | 1000 | 1000
GAE parameter (reward) | 0.95 | 0.95 | 0.95 | 0.95 | 0.95
GAE parameter (cost) | 0.95 | 0.95 | 0.95 | 0.95 | 0.95
Learning rate for policy | $3\times 10^{-4}$ | $3\times 10^{-4}$ | N/A | N/A | $3\times 10^{-4}$
Learning rate for reward value net | $3\times 10^{-4}$ | $3\times 10^{-4}$ | $3\times 10^{-4}$ | $3\times 10^{-4}$ | $3\times 10^{-4}$
Learning rate for cost value net | $3\times 10^{-4}$ | $3\times 10^{-4}$ | $3\times 10^{-4}$ | $3\times 10^{-4}$ | $3\times 10^{-4}$
Learning rate for $\nu$ | 0.01 | 0.01 | 0.01 | N/A | 0.01
$L2$-regularization coeff. for value net | $10^{-3}$ | $3\times 10^{-3}$ | $3\times 10^{-3}$ | $3\times 10^{-3}$ | $10^{-3}$
Clipping coefficient | N/A | 0.2 | N/A | N/A | N/A
Damping coeff. | N/A | N/A | 0.01 | 0.01 | N/A
Backtracking coeff. | N/A | N/A | 0.8 | 0.8 | N/A
Max backtracking iterations | N/A | N/A | 10 | 10 | N/A
Max conjugate gradient iterations | N/A | N/A | 10 | 10 | N/A
Iterations for training value net | 1 | 1 | 80 | 80 | 1
Temperature $\lambda$ | 1.5 | N/A | N/A | N/A | 1.5
Trust region bound $\delta$ | 0.02 | N/A | 0.01 | 0.01 | 0.02
Initial $\nu$, $\nu_{\max}$ | 0, 2 | 0, 1 | 0, 2 | N/A | 0, 2
Table 3: Hyper-parameters for robots.