M_{t}^{\varphi}(\pi_{\bm{\theta}},\pi_{{\bm{\theta}}^{{}^{\prime}}})+\epsilon^{\varphi,(\lambda)}_{p,q,t}(\pi_{\bm{\theta}},\pi_{{\bm{\theta}}^{{}^{\prime}}}).$
(87)

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

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

$\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)=\mathbb{E}_{s\sim
d_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}^{\lambda}(\cdot)}\left[{{\delta}}^{\varphi}_{\pi_{\bm{\theta}},t}(s)\right]$
(88) $\displaystyle\overset{(\ref{revist-td-ex-error})}{=}$
$\displaystyle\mathbb{E}_{s\sim
d_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}^{\lambda}(\cdot)}\left[\mathbb{E}_{s_{t}\sim\mathbb{P}_{\pi_{\bm{\theta}}}(\cdot|s)}[\delta^{\varphi}_{\pi_{\bm{\theta}}}(s_{t})]\right].$
(89)

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

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

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

According to (88), (90), we rewrite the term
$\langle\mathbf{d}_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}^{\lambda},{\bm{\delta}}^{\varphi}_{\pi_{\bm{\theta}},t}\rangle$
in Eq.(86) 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}}{\mathbb{E}}\left[\dfrac{\pi_{\bm{\theta}}(a_{t}|s_{t})}{\pi_{{\bm{\theta}}^{{}^{\prime}}}(a_{t}|s_{t})}\delta_{t}^{\varphi}\right]\right).$
(91)

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

$\displaystyle\text{Term-II}~{}(\ref{def:l-t})$
$\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}}{\mathbb{E}}\left[\delta_{t}^{\varphi}\right]\right).$
(92)

Finally, take the results (91) and (92) to (86), 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}}})$ (86) 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}}{\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).$
(93)

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}}{\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],$
(94)

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$
(93) as follows,

$\displaystyle
M_{t}^{\varphi}(\pi_{\bm{\theta}},\pi_{{\bm{\theta}}^{{}^{\prime}}})=$
$\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{diff-01})}{=}$
$\displaystyle\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 (87), 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}}}).$
(95)

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}}})$
(96) $\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}}{\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\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}}{\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}}})$
(97) $\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}}{\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\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}}{\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 (82) and (95), 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,}}.$
(98)

∎

###  E.2 Proof of Proposition 4

###### Proof.

(of Proposition 4).

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

We rewrite the discounted distribution
$\mathbf{d}_{\pi_{\bm{\theta}}}^{\lambda}$ (72) 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}.$
(99)

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 (99), 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=\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.$
(100)

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

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

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

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

We express the third term
$\langle{\tilde{\gamma}}\mathbf{P}^{(\lambda)}_{\pi_{\bm{\theta}}}\mathbf{d}_{\pi_{\bm{\theta}}}^{\lambda},\bm{\phi}\rangle$
of (100) 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}}).$
(103)

According to Lemma 1, put the results (76) and (100) 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)+\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\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),$
(104)

where the last equation holds since we unfold (100) according to (101)-(103).

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.(104).

Then, we unfold the second term of (104) 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)$
(105) $\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).$
(106)

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

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

We consider the first term $R^{(\lambda)}_{\pi_{\bm{\theta}}}(s)$ of (105) 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}).$
(108)

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 (105) 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)$
(109) $\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)$
(110) $\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}})}$
(111) $\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),$
(112)

where the equation from Eq.(111) to Eq.(112) holds since: according to (54),
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 (108) and (112) to (107), 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}\Bigg{(}\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}})}$
$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}-\sum_{s_{t}\in\mathcal{S}}\mathbb{P}_{\pi_{\bm{\theta}}}(s_{t}|s)\varphi(s_{t})\Bigg{)}$
(113) $\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})\right.$
$\displaystyle\left.~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}-\sum_{s_{t}\in\mathcal{S}}\mathbb{P}_{\pi_{\bm{\theta}}}(s_{t}|s)\varphi(s_{t})\right)$
(114) $\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)$
(115) $\displaystyle=$
$\displaystyle\sum_{{t}=0}^{\infty}(\gamma\lambda)^{t}\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],$
(116)

the equation from Eq.(112) to Eq.(113) 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.(113) to Eq.(114) 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 (115) 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)\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=\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 (104) and (116), we have

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

This concludes the proof of Proposition 4. ∎

###  E.3 Proposition 3

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

We obtain

$\displaystyle\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\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}\mathbb{E}_{s\sim{d}_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}^{\lambda}(\cdot)}\left[\text{KL}(\pi_{{\bm{\theta}}^{{}^{\prime}}},\pi_{\bm{\theta}})[s]\right]},$
(118)

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 (118), we
obtain the next Proposition 3.

Proposition 3. _All the bounds in ( 11) and (13) hold if we make the following
substitution:_

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

##  Appendix F Lemma 2

In this section, we show Lemma 2 that presents an upper bound to the
difference between two $\lambda$-version of normalized discounted
distribution. Before we present our main results, we review the norms induced
by $p$-norms for matrix.

###  F.1 Norms Induced by $p$-norms for Matrix

If the $p$-norm for vectors $(1\leq p\leq\infty)$ is used for both spaces
$\mathbb{R}^{n}$ and $\mathbb{R}^{m}$, then the corresponding operator norm
is:

${\displaystyle\|\mathbf{A}\|_{p}=\sup_{\mathbf{x}\neq\bm{0}}{\frac{\|\mathbf{A}\mathbf{x}\|_{p}}{\|\mathbf{x}\|_{p}}}.}$

These induced norms are different from the "entry-wise" $p$-norms and the
_Schatten_ $p$-norms for matrices treated below, which are also usually
denoted by ${\displaystyle\|\mathbf{A}\|_{p}.}$

In the special cases of $p=1$ and $p=\infty$, the induced matrix norms can be
computed or estimated by

${\displaystyle\|\mathbf{A}\|_{1}=\max_{1\leq j\leq
n}\sum_{i=1}^{m}|a_{ij}|,}$

which is simply the maximum absolute column sum of the matrix;

${\displaystyle\|\mathbf{A}\|_{\infty}=\max_{1\leq i\leq
m}\sum_{j=1}^{n}|a_{ij}|,}$

which is simply the maximum absolute row sum of the matrix. Thus, the
following equation holds

$\displaystyle\|\mathbf{A}^{\top}\|_{\infty}=\|\mathbf{A}\|_{1}.$ (119)

###  F.2 Lemma 2

######  Lemma 2.

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,

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

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

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

###### Proof.

(of Lemma 2). Recall Eq.(72), we know,

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

To short the expression, we introduce some additional notations as follows.

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

Then, after some simple algebra, 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}.$
(121)

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

Grouping all the results from (120)-(122), recall (72),

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

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

Applying (124), 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}.$
(125)

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

Thus, recall $\tilde{\gamma}=\dfrac{\gamma(1-\lambda)}{1-\gamma\lambda}$, we
obtain

$\displaystyle\|\mathbf{d}_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}^{\lambda}-\mathbf{d}_{\pi_{\bm{\theta}}}^{\lambda}\|_{1}\leq$
$\displaystyle\tilde{\gamma}\|\mathbf{G}_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}\|_{1}\|\mathbf{D}\mathbf{d}_{\pi_{\bm{\theta}}}^{\lambda}\|_{1}\leq\dfrac{\tilde{\gamma}}{1-\tilde{\gamma}}\|\mathbf{D}\mathbf{d}_{\pi_{\bm{\theta}}}^{\lambda}\|_{1}$
(127) $\displaystyle\leq$
$\displaystyle\dfrac{1}{1-\tilde{\gamma}}\cdot\dfrac{\tilde{\gamma}\left(\gamma\lambda(|\mathcal{S}|-1)+1\right)}{1-\gamma\lambda}\mathbb{E}_{s\sim
d_{\pi_{\bm{\theta}}}^{\lambda}(\cdot)}\left[2D_{\mathrm{TV}}(\pi_{{\bm{\theta}}^{{}^{\prime}}},\pi_{\bm{\theta}})[s]\right],$
(128)

where the last equation holds due to Lemma 3, this concludes the proof of
Lemma 2 . ∎

######  Lemma 3.

The term $\|\mathbf{D}\mathbf{d}_{\pi_{\bm{\theta}}}^{\lambda}\|_{1}$ is
bounded as follows,

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

###### Proof.

Now, we analyze $\|\mathbf{D}\mathbf{d}_{\pi_{\bm{\theta}}}^{\lambda}\|_{1}$
as follows,

$\displaystyle\|\mathbf{D}\mathbf{d}_{\pi_{\bm{\theta}}}^{\lambda}\|_{1}=\sum_{s\in\mathcal{S}}\left|\sum_{s^{{}^{\prime}}\in\mathcal{S}}\mathbf{D}(s^{{}^{\prime}}|s)d_{\pi_{\bm{\theta}}}^{\lambda}(s)\right|\overset{(\ref{lam-
pro-
value-02})}{=}\sum_{s\in\mathcal{S}}\left|\sum_{s^{{}^{\prime}}\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\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),$

which implies that to bound
$\|\mathbf{D}\mathbf{d}_{\pi_{\bm{\theta}}}^{\lambda}\|_{1}$, we need to bound
the following difference

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

Step 1: Rewrite
$\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).$

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})$
(129) $\displaystyle=$
$\displaystyle\sum_{s_{1}\in\mathcal{S}}\mathbb{P}_{{\pi_{\bm{\theta}}}}(s_{t+1}=s^{{}^{\prime}}|s_{1})\left(\sum_{a\in\mathcal{A}}\pi_{\bm{\theta}}(a|s_{0})\mathbb{P}(s_{1}|s_{0},a)\right).$
(130)

Similarly,

$\displaystyle\mathbb{P}_{{\pi_{{\bm{\theta}}^{{}^{\prime}}}}}(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}}^{{}^{\prime}}}}}(s_{t+1}=s^{{}^{\prime}}|s_{1})\mathbb{P}_{{\pi_{{\bm{\theta}}^{{}^{\prime}}}}}(s_{1}|s_{0})$
(131) $\displaystyle=$
$\displaystyle\sum_{s_{1}\in\mathcal{S}}\mathbb{P}_{{\pi_{{\bm{\theta}}^{{}^{\prime}}}}}(s_{t+1}=s^{{}^{\prime}}|s_{1})\left(\sum_{a\in\mathcal{A}}\pi_{{\bm{\theta}}^{{}^{\prime}}}(a|s_{0})\mathbb{P}(s_{1}|s_{0},a)\right).$
(132)

Firstly, we consider the following term

$\displaystyle\sum_{{t}=0}^{\infty}(\gamma\lambda)^{{t}}\sum_{s^{{}^{\prime}}\in\mathcal{S}}$
$\displaystyle\mathbb{P}_{\pi_{\bm{\theta}}}(s_{t+1}=s^{{}^{\prime}}|s)=\sum_{{t}=0}^{\infty}(\gamma\lambda)^{{t}}\sum_{s^{{}^{\prime}}\in\mathcal{S}}\sum_{s_{1}\in\mathcal{S}}\mathbb{P}_{{\pi_{\bm{\theta}}}}(s_{t+1}=s^{{}^{\prime}}|s_{1})\left(\sum_{a\in\mathcal{A}}\pi_{\bm{\theta}}(a|s)\mathbb{P}(s_{1}|s,a)\right)$
$\displaystyle=$
$\displaystyle\sum_{{t}=0}^{\infty}(\gamma\lambda)^{{t}}\sum_{s^{{}^{\prime}}\in\mathcal{S}}\sum_{s_{1}\in\mathcal{S}}\mathbf{P}^{t}_{{\pi_{\bm{\theta}}}}[s_{1},s^{{}^{\prime}}]\left(\sum_{a\in\mathcal{A}}\pi_{\bm{\theta}}(a|s)\mathbb{P}(s_{1}|s,a)\right)$
$\displaystyle=$
$\displaystyle\sum_{s^{{}^{\prime}}\in\mathcal{S}}\sum_{s_{1}\in\mathcal{S}}\left(\sum_{{t}=0}^{\infty}(\gamma\lambda\mathbf{P}_{{\pi_{\bm{\theta}}}})^{t}\right)[s_{1},s^{{}^{\prime}}]\left(\sum_{a\in\mathcal{A}}\pi_{\bm{\theta}}(a|s)\mathbb{P}(s_{1}|s,a)\right)$
$\displaystyle=$
$\displaystyle\sum_{s^{{}^{\prime}}\in\mathcal{S}}\sum_{s_{1}\in\mathcal{S}}\left(\mathbf{I}-\gamma\lambda\mathbf{P}_{{\pi_{\bm{\theta}}}}\right)^{-1}[s_{1},s^{{}^{\prime}}]\left(\sum_{a\in\mathcal{A}}\pi_{\bm{\theta}}(a|s)\mathbb{P}(s_{1}|s,a)\right).$
(133)

To short expression, we introduce a new notation as follows,

$\displaystyle\mathbf{F}_{\pi_{\bm{\theta}}}=\left(\mathbf{I}-\gamma\lambda\mathbf{P}_{{\pi_{\bm{\theta}}}}\right)^{-1}.$
(134)

Then, we rewrite (133) as follows,

$\displaystyle\sum_{{t}=0}^{\infty}(\gamma\lambda)^{{t}}\sum_{s^{{}^{\prime}}\in\mathcal{S}}\mathbb{P}_{\pi_{\bm{\theta}}}(s_{t+1}=s^{{}^{\prime}}|s)=\sum_{s^{{}^{\prime}}\in\mathcal{S}}\sum_{s_{1}\in\mathcal{S}}\mathbf{F}_{\pi_{\bm{\theta}}}[s_{1},s^{{}^{\prime}}]\left(\sum_{a\in\mathcal{A}}\pi_{\bm{\theta}}(a|s)\mathbb{P}(s_{1}|s,a)\right).$
(135)

Furthermore, according to (135), we obtain

$\displaystyle\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)$
$\displaystyle=$
$\displaystyle\sum_{s^{{}^{\prime}}\in\mathcal{S}}\sum_{s_{1}\in\mathcal{S}}\mathbf{F}_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}[s_{1},s^{{}^{\prime}}]\left(\sum_{a\in\mathcal{A}}\pi_{{\bm{\theta}}^{{}^{\prime}}}(a|s)\mathbb{P}(s_{1}|s,a)\right)-\sum_{s^{{}^{\prime}}\in\mathcal{S}}\sum_{s_{1}\in\mathcal{S}}\mathbf{F}_{\pi_{\bm{\theta}}}[s_{1},s^{{}^{\prime}}]\left(\sum_{a\in\mathcal{A}}\pi_{\bm{\theta}}(a|s)\mathbb{P}(s_{1}|s,a)\right)$
$\displaystyle=$
$\displaystyle\sum_{s^{{}^{\prime}}\in\mathcal{S}}\sum_{s_{1}\in\mathcal{S}}\mathbf{F}_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}[s_{1},s^{{}^{\prime}}]\left(\sum_{a\in\mathcal{A}}\pi_{{\bm{\theta}}^{{}^{\prime}}}(a|s)\mathbb{P}(s_{1}|s,a)\right)-\sum_{s^{{}^{\prime}}\in\mathcal{S}}\sum_{s_{1}\in\mathcal{S}}\mathbf{F}_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}[s_{1},s^{{}^{\prime}}]\left(\sum_{a\in\mathcal{A}}\pi_{\bm{\theta}}(a|s)\mathbb{P}(s_{1}|s,a)\right)$
$\displaystyle~{}~{}~{}~{}+\sum_{s^{{}^{\prime}}\in\mathcal{S}}\sum_{s_{1}\in\mathcal{S}}\mathbf{F}_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}[s_{1},s^{{}^{\prime}}]\left(\sum_{a\in\mathcal{A}}\pi_{\bm{\theta}}(a|s)\mathbb{P}(s_{1}|s,a)\right)-\sum_{s^{{}^{\prime}}\in\mathcal{S}}\sum_{s_{1}\in\mathcal{S}}\mathbf{F}_{\pi_{\bm{\theta}}}[s_{1},s^{{}^{\prime}}]\left(\sum_{a\in\mathcal{A}}\pi_{\bm{\theta}}(a|s)\mathbb{P}(s_{1}|s,a)\right)$
$\displaystyle=$
$\displaystyle\sum_{s^{{}^{\prime}}\in\mathcal{S}}\sum_{s_{1}\in\mathcal{S}}\mathbf{F}_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}[s_{1},s^{{}^{\prime}}]\left(\sum_{a\in\mathcal{A}}\Big{(}\pi_{{\bm{\theta}}^{{}^{\prime}}}(a|s)-\pi_{\bm{\theta}}(a|s)\Big{)}\mathbb{P}(s_{1}|s,a)\right)$
(136)
$\displaystyle~{}~{}~{}~{}+\sum_{s^{{}^{\prime}}\in\mathcal{S}}\sum_{s_{1}\in\mathcal{S}}\Big{(}\mathbf{F}_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}[s_{1},s^{{}^{\prime}}]-\mathbf{F}_{\pi_{\bm{\theta}}}[s_{1},s^{{}^{\prime}}]\Big{)}\left(\sum_{a\in\mathcal{A}}\pi_{\bm{\theta}}(a|s)\mathbb{P}(s_{1}|s,a)\right),$
(137)

which implies that to bound the following difference

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

we need to bound (136) and (137).

Step 2: Bound the difference (137).

Due to the simple fact: for any inverse matrices $\mathbf{A}$ and
$\mathbf{B}$, then the following identity holds

$\mathbf{A}^{-1}-\mathbf{B}^{-1}=\mathbf{A}^{-1}(\mathbf{B}-\mathbf{A})\mathbf{B}^{-1},$

we rewrite the difference
$\mathbf{F}_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}-\mathbf{F}_{\pi_{\bm{\theta}}}$
as follows,

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

Then, we rewrite (137) as the following matrix version

$\displaystyle\sum_{s^{{}^{\prime}}\in\mathcal{S}}\sum_{s_{1}\in\mathcal{S}}\Big{(}\mathbf{F}_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}[s_{1},s^{{}^{\prime}}]-\mathbf{F}_{\pi_{\bm{\theta}}}[s_{1},s^{{}^{\prime}}]\Big{)}\left(\sum_{a\in\mathcal{A}}\pi_{\bm{\theta}}(a|s)\mathbb{P}(s_{1}|s,a)\right)$
$\displaystyle=$
$\displaystyle\sum_{s^{{}^{\prime\prime}}\in\mathcal{S}}\sum_{s^{{}^{\prime}}\in\mathcal{S}}\Big{(}\mathbf{F}_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}[s^{{}^{\prime}},s^{{}^{\prime\prime}}]-\mathbf{F}_{\pi_{\bm{\theta}}}[s^{{}^{\prime}},s^{{}^{\prime\prime}}]\Big{)}\left(\sum_{a\in\mathcal{A}}\pi_{\bm{\theta}}(a|s)\mathbb{P}(s^{{}^{\prime}}|s,a)\right)=\left\|\left(\mathbf{F}^{\top}_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}-\mathbf{F}^{\top}_{\pi_{\bm{\theta}}}\right)\mathbf{p}_{\pi_{\bm{\theta}}}(s)\right\|_{1},$

where $\mathbf{p}_{\pi_{\bm{\theta}}}(s)\in\mathbb{R}^{|\mathcal{S}|}$, and

$\mathbf{p}_{\pi_{\bm{\theta}}}(s)=\left(\mathbb{P}_{\pi_{\bm{\theta}}}(s_{1}|s),\mathbb{P}_{\pi_{\bm{\theta}}}(s_{2}|s),\cdots,\mathbb{P}_{\pi_{\bm{\theta}}}\left(s_{|\mathcal{S}|}|s\right)\right)^{\top}.$

According to (119), we obtain

$\displaystyle\left\|\left(\mathbf{F}^{\top}_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}-\mathbf{F}^{\top}_{\pi_{\bm{\theta}}}\right)\mathbf{p}_{\pi_{\bm{\theta}}}(s)\right\|_{1}=\left\|\mathbf{p}^{\top}_{\pi_{\bm{\theta}}}(s)\left(\mathbf{F}_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}-\mathbf{F}_{\pi_{\bm{\theta}}}\right)\right\|_{\infty}$
$\displaystyle=$
$\displaystyle\gamma\lambda\left\|\mathbf{p}^{\top}_{\pi_{\bm{\theta}}}(s)\left(\mathbf{I}-\gamma\lambda\mathbf{P}_{{\pi_{{\bm{\theta}}^{{}^{\prime}}}}}\right)^{-1}\left(\mathbf{P}_{{\pi_{{\bm{\theta}}^{{}^{\prime}}}}}-\mathbf{P}_{{\pi_{\bm{\theta}}}}\right)\left(\mathbf{I}-\gamma\lambda\mathbf{P}_{{\pi_{\bm{\theta}}}}\right)^{-1}\right\|_{\infty}$
$\displaystyle=$
$\displaystyle\dfrac{\gamma\lambda}{1-\gamma\lambda}\Bigg{\|}\underbrace{\mathbf{p}^{\top}_{\pi_{\bm{\theta}}}(s)(1-\gamma\lambda)\left(\mathbf{I}-\gamma\lambda\mathbf{P}_{{\pi_{{\bm{\theta}}^{{}^{\prime}}}}}\right)^{-1}}_{\mathbf{f}^{\top}_{s}}\left(\mathbf{P}_{{\pi_{{\bm{\theta}}^{{}^{\prime}}}}}-\mathbf{P}_{{\pi_{\bm{\theta}}}}\right)\left(\mathbf{I}-\gamma\lambda\mathbf{P}_{{\pi_{\bm{\theta}}}}\right)^{-1}\Bigg{\|}_{\infty}$
(138) $\displaystyle\leq$
$\displaystyle\dfrac{\gamma\lambda}{1-\gamma\lambda}\left\|\mathbf{f}^{\top}_{s}\left(\mathbf{P}_{{\pi_{{\bm{\theta}}^{{}^{\prime}}}}}-\mathbf{P}_{{\pi_{\bm{\theta}}}}\right)\right\|_{\infty}\left\|\left(\mathbf{I}-\gamma\lambda\mathbf{P}_{{\pi_{\bm{\theta}}}}\right)^{-1}\right\|_{\infty}$
$\displaystyle=$
$\displaystyle\dfrac{\gamma\lambda}{(1-\gamma\lambda)^{2}}\left\|\mathbf{f}^{\top}_{s}\left(\mathbf{P}_{{\pi_{{\bm{\theta}}^{{}^{\prime}}}}}-\mathbf{P}_{{\pi_{\bm{\theta}}}}\right)\right\|_{\infty}$
(139) $\displaystyle=$
$\displaystyle\dfrac{2\gamma\lambda}{(1-\gamma\lambda)^{2}}\sum_{s\in\mathcal{S}}D_{\mathrm{TV}}(\pi_{{\bm{\theta}}^{{}^{\prime}}},\pi_{\bm{\theta}})[s],$
(140)

where in Eq.(138), we introduce a notation
$\mathbf{f}^{\top}_{s}\in\mathbb{R}^{|\mathcal{S}|}$ as follows,

$\mathbf{f}^{\top}_{s}=:\mathbf{p}^{\top}_{\pi_{\bm{\theta}}}(s)(1-\gamma\lambda)\left(\mathbf{I}-\gamma\lambda\mathbf{P}_{{\pi_{{\bm{\theta}}^{{}^{\prime}}}}}\right)^{-1};$

Eq.(139) holds since:

$\left\|\left(\mathbf{I}-\gamma\lambda\mathbf{P}_{{\pi_{\bm{\theta}}}}\right)^{-1}\right\|_{\infty}=\dfrac{1}{1-\gamma\lambda};$

Eq.(140) holds since:

$\displaystyle\left\|\mathbf{f}^{\top}\left(\mathbf{P}_{{\pi_{{\bm{\theta}}^{{}^{\prime}}}}}-\mathbf{P}_{{\pi_{\bm{\theta}}}}\right)\right\|_{\infty}$
$\displaystyle=\sum_{s\in\mathcal{S}}\sum_{s^{{}^{\prime}}\in\mathcal{S}}\mathbf{f}_{s}[s^{{}^{\prime}}]\left|\mathbb{P}_{{\pi_{{\bm{\theta}}^{{}^{\prime}}}}}(s^{{}^{\prime}}|s)-\mathbb{P}_{{\pi_{\bm{\theta}}}}(s^{{}^{\prime}}|s)\right|$
$\displaystyle=\sum_{s\in\mathcal{S}}\sum_{s^{{}^{\prime}}\in\mathcal{S}}\mathbf{f}_{s}[s^{{}^{\prime}}]\left|\sum_{a\in\mathcal{A}}\mathbb{P}(s^{{}^{\prime}}|s,a)\left(\pi_{{\bm{\theta}}^{{}^{\prime}}}(a|s)-\pi_{\bm{\theta}}(a|s)\right)\right|$
$\displaystyle\leq\sum_{s\in\mathcal{S}}\sum_{s^{{}^{\prime}}\in\mathcal{S}}\mathbf{f}_{s}[s^{{}^{\prime}}]\sum_{a\in\mathcal{A}}\left|\pi_{{\bm{\theta}}^{{}^{\prime}}}(a|s)-\pi_{\bm{\theta}}(a|s)\right|$
$\displaystyle=\sum_{s\in\mathcal{S}}\sum_{a\in\mathcal{A}}\left|\pi_{{\bm{\theta}}^{{}^{\prime}}}(a|s)-\pi_{\bm{\theta}}(a|s)\right|,$

where the last equation holds due to the following fact

$\sum_{s^{{}^{\prime}}\in\mathcal{S}}\mathbf{f}_{s}[s^{{}^{\prime}}]=\sum_{s^{{}^{\prime}}\in\mathcal{S}}\mathbf{p}^{\top}_{\pi_{\bm{\theta}}}(s)(1-\gamma\lambda)\left(\mathbf{I}-\gamma\lambda\mathbf{P}_{{\pi_{{\bm{\theta}}^{{}^{\prime}}}}}\right)^{-1}[s^{{}^{\prime}}]=1.$

Thus, the difference (137) is bounded as follows,

$\displaystyle\sum_{s^{{}^{\prime}}\in\mathcal{S}}\sum_{s_{1}\in\mathcal{S}}\Big{(}\mathbf{F}_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}[s_{1},s^{{}^{\prime}}]-\mathbf{F}_{\pi_{\bm{\theta}}}[s_{1},s^{{}^{\prime}}]\Big{)}\left(\sum_{a\in\mathcal{A}}\pi_{\bm{\theta}}(a|s)\mathbb{P}(s_{1}|s,a)\right)\leq\dfrac{2\gamma\lambda}{(1-\gamma\lambda)^{2}}\sum_{s\in\mathcal{S}}D_{\mathrm{TV}}(\pi_{{\bm{\theta}}^{{}^{\prime}}},\pi_{\bm{\theta}})[s].$

Step 3: Bound the difference (136).

We turn to consider (136):

$\displaystyle\sum_{s^{{}^{\prime}}\in\mathcal{S}}\sum_{s_{1}\in\mathcal{S}}\mathbf{F}_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}[s_{1},s^{{}^{\prime}}]\left(\sum_{a\in\mathcal{A}}\Big{(}\pi_{{\bm{\theta}}^{{}^{\prime}}}(a|s)-\pi_{\bm{\theta}}(a|s)\Big{)}\mathbb{P}(s_{1}|s,a)\right)$
$\displaystyle=$
$\displaystyle\sum_{s^{{}^{\prime\prime}}\in\mathcal{S}}\sum_{s^{{}^{\prime}}\in\mathcal{S}}\mathbf{F}_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}[s^{{}^{\prime}},s^{{}^{\prime\prime}}]\left(\sum_{a\in\mathcal{A}}\Big{(}\pi_{{\bm{\theta}}^{{}^{\prime}}}(a|s)-\pi_{\bm{\theta}}(a|s)\Big{)}\mathbb{P}(s^{{}^{\prime}}|s,a)\right)$
$\displaystyle=$
$\displaystyle\left\|\mathbf{F}^{\top}_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}(\mathbf{p}_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}(s)-\mathbf{p}_{\pi_{\bm{\theta}}}(s))\right\|_{1}$
$\displaystyle\leq$
$\displaystyle\left\|\mathbf{F}^{\top}_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}\right\|_{1}\left\|\mathbf{p}_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}(s)-\mathbf{p}_{\pi_{\bm{\theta}}}(s)\right\|_{1}$
$\displaystyle=$
$\displaystyle\left\|\mathbf{p}_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}(s)-\mathbf{p}_{\pi_{\bm{\theta}}}(s)\right\|_{1}\leq\dfrac{2}{1-\gamma\lambda}D_{\mathrm{TV}}(\pi_{{\bm{\theta}}^{{}^{\prime}}},\pi_{\bm{\theta}})[s],$
(141)

where the last Eq.(141) holds since:

$\left\|\mathbf{F}^{\top}_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}\right\|_{1}=\dfrac{1}{1-\gamma\lambda},$

and

$\displaystyle\left\|\mathbf{p}_{\pi_{{\bm{\theta}}^{{}^{\prime}}}}(s)-\mathbf{p}_{\pi_{\bm{\theta}}}(s)\right\|_{1}$
$\displaystyle=\sum_{s^{{}^{\prime}}\in\mathcal{S}}\left|\mathbb{P}_{{\pi_{{\bm{\theta}}^{{}^{\prime}}}}}(s^{{}^{\prime}}|s)-\mathbb{P}_{{\pi_{\bm{\theta}}}}(s^{{}^{\prime}}|s)\right|$
$\displaystyle=\sum_{s^{{}^{\prime}}\in\mathcal{S}}\left|\sum_{a\in\mathcal{A}}\mathbb{P}(s^{{}^{\prime}}|s,a)\left(\pi_{{\bm{\theta}}^{{}^{\prime}}}(a|s)-\pi_{\bm{\theta}}(a|s)\right)\right|$
$\displaystyle\leq\sum_{a\in\mathcal{A}}\sum_{s^{{}^{\prime}}\in\mathcal{S}}\mathbb{P}(s^{{}^{\prime}}|s,a)\left|\pi_{{\bm{\theta}}^{{}^{\prime}}}(a|s)-\pi_{\bm{\theta}}(a|s)\right|$
$\displaystyle=\sum_{a\in\mathcal{A}}\left|\pi_{{\bm{\theta}}^{{}^{\prime}}}(a|s)-\pi_{\bm{\theta}}(a|s)\right|=2D_{\mathrm{TV}}(\pi_{{\bm{\theta}}^{{}^{\prime}}},\pi_{\bm{\theta}})[s].$

Step 4: Put all the result together.

Finally, according to (136), (137), (140), and (141), we obtain

$\displaystyle\|\mathbf{D}\mathbf{d}_{\pi_{\bm{\theta}}}^{\lambda}\|_{1}=$
$\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)$
$\displaystyle\leq$
$\displaystyle\sum_{s\in\mathcal{S}}d_{\pi_{\bm{\theta}}}^{\lambda}(s)\left[\dfrac{2\gamma\lambda}{1-\gamma\lambda}\sum_{s\in\mathcal{S}}D_{\mathrm{TV}}(\pi_{{\bm{\theta}}^{{}^{\prime}}},\pi_{\bm{\theta}})[s]+2D_{\mathrm{TV}}(\pi_{{\bm{\theta}}^{{}^{\prime}}},\pi_{\bm{\theta}})[s]\right]$
$\displaystyle=$
$\displaystyle\sum_{s\in\mathcal{S}}d_{\pi_{\bm{\theta}}}^{\lambda}(s)\left[\dfrac{2\gamma\lambda|\mathcal{S}|}{1-\gamma\lambda}D_{\mathrm{TV}}(\pi_{{\bm{\theta}}^{{}^{\prime}}},\pi_{\bm{\theta}})[s]+2D_{\mathrm{TV}}(\pi_{{\bm{\theta}}^{{}^{\prime}}},\pi_{\bm{\theta}})[s]\right]$
$\displaystyle=$
$\displaystyle\dfrac{\gamma\lambda(|\mathcal{S}|-1)+1}{1-\gamma\lambda}\mathbb{E}_{s\sim
d_{\pi_{\bm{\theta}}}^{\lambda}(\cdot)}\left[2D_{\mathrm{TV}}(\pi_{{\bm{\theta}}^{{}^{\prime}}},\pi_{\bm{\theta}})[s]\right].$

This concludes the result of Lemma 3. ∎

##  Appendix G Proof of Theorem 2

Before we present the main result, we define some notations.

$\displaystyle\chi_{k}=$
$\displaystyle\mathbb{E}_{s\sim{d}_{{\pi_{\bm{\theta}_{k}}}}^{\lambda}(\cdot)}\left[\mathtt{KL}\left(\pi_{\bm{\theta}_{k}},\pi_{\bm{\theta}_{k+\frac{1}{2}}}\right)[s]\right],$
(142) $\displaystyle\iota=$
$\displaystyle\dfrac{\tilde{\gamma}\left(\gamma\lambda(|\mathcal{S}|-1)+1\right)}{(1-\tilde{\gamma})(1-\gamma\lambda)}.$
(143)

###### Proof.

(of Theorem 2)

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

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

implies

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

Furthermore, according to Proposition 1 and Proposition 3, we have

$\displaystyle J(\pi_{\bm{\theta}_{k+1}})-J(\pi_{\bm{\theta}_{k}})$
$\displaystyle\geq$
$\displaystyle\dfrac{1}{1-\tilde{\gamma}}\mathbb{E}_{s\sim{d}_{\pi_{\bm{\theta}_{k}}}^{\lambda}(\cdot),a\sim\pi_{\bm{\theta}_{k+1}}(\cdot|s)}\left[A^{\mathtt{GAE}(\gamma,\lambda)}_{\pi_{\bm{\theta}_{k}}}(s,a)-\iota\epsilon^{V}_{\pi_{\bm{\theta}_{k+1}}}(\pi_{\bm{\theta}_{k}})D_{\text{TV}}(\pi_{\bm{\theta}_{k}},\pi_{\bm{\theta}_{k+1}})[s]\right]$
$\displaystyle\geq$
$\displaystyle\dfrac{1}{1-\tilde{\gamma}}\mathbb{E}_{s\sim{d}_{\pi_{\bm{\theta}_{k}}}^{\lambda}(\cdot),a\sim\pi_{\bm{\theta}_{k+1}}(\cdot|s)}\left[-\iota\alpha_{k}\epsilon^{V}_{\pi_{\bm{\theta}_{k+1}}}(\pi_{\bm{\theta}_{k}})\sqrt{\dfrac{1}{2}\mathrm{KL}(\pi_{\bm{\theta}_{k}},\pi_{\bm{\theta}_{k+1}})[s]}\right]$
$\displaystyle\geq$
$\displaystyle-\dfrac{\iota}{1-\tilde{\gamma}}\alpha_{k}\sqrt{2\chi_{k}}\epsilon^{V}_{\pi_{\bm{\theta}_{k+1}}}(\pi_{\bm{\theta}_{k}}).$

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

$\displaystyle
J^{c}(\pi_{{\bm{\theta}}_{k}})+\dfrac{1}{1-\tilde{\gamma}}\mathbb{E}_{s\sim{d}_{\pi_{\bm{\theta}_{k}}}^{\lambda}(\cdot),a\sim\pi_{\bm{\theta}_{k+1}}(\cdot|s)}\left[A^{\mathtt{GAE}(\gamma,\lambda)}_{{\pi_{\bm{\theta}_{k}}},C}(s,a)\right]+\beta_{k}\sqrt{\mathbb{E}_{s\sim{d}_{{\pi_{\bm{\theta}_{k}}}}^{\lambda}(\cdot)}\left[\mathrm{KL}(\pi_{\bm{\theta}_{k}},\pi_{\bm{\theta}_{k+1}})[s]\right]}\leq
b,$ (144)

and

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

Combining (144)- (146), we have

$\displaystyle J^{c}(\pi_{\bm{\theta}_{k+1}})-J^{c}(\pi_{\bm{\theta}_{k}})$
(146) $\displaystyle\leq$ $\displaystyle
b+\frac{1}{1-\tilde{\gamma}}\mathbb{E}_{s\sim{d}_{\pi_{\bm{\theta}_{k}}}^{\lambda}(\cdot),a\sim\pi_{\bm{\theta}_{k+1}}(\cdot|s)}\left[\iota\beta_{k}\epsilon^{C}_{\pi_{\bm{\theta}_{k+1}}}\sqrt{\dfrac{1}{2}\mathbb{E}_{s\sim{d}_{\pi_{\bm{\theta}_{k}}}^{\lambda}(\cdot)}\left[\mathrm{KL}(\pi_{\bm{\theta}_{k}},\pi_{\bm{\theta}_{k+1}})[s]\right]}\right]$
$\displaystyle\leq$ $\displaystyle
b+\frac{1}{1-\tilde{\gamma}}\mathbb{E}_{s\sim{d}_{\pi_{\bm{\theta}_{k}}}^{\lambda}(\cdot),a\sim\pi_{\bm{\theta}_{k+1}}(\cdot|s)}\left[\iota\beta_{k}\sqrt{2\chi_{k}}\epsilon^{C}_{\pi_{\bm{\theta}_{k+1}}}\right].$
(147)

∎

##  Appendix H Experiments

The Python code for our implementation of CUP is provided along with this
submission in the supplementary material.

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 the open-source
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 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.

###  H.2 Environment

####  H.2.1 Environment 1: Robots with Speed Limit.

We consider two tasks from MuJoCo [Brockman et al., 2016]: Walker2d-v3 and
Hopper-v3, where the setting of cost follows [Zhang et al., 2020]. For agents
move on a two-dimensional plane, the cost is calculated as follows,

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

for agents move 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.2 Environment 2: Circle.

The Circle Environment follows [Achiam et al., 2017], and we use open-source
implementation of the circle environments from
https://github.com/ymzhang01/mujoco-circle. According to Zhang et al. [2020],
those experiments were implemented in OpenAI Gym [Brockman et al., 2016] while
the circle tasks in Achiam et al. [2017] were implemented in rllab [Duan et
al., 2016]. We also excluded the Point agent from the original experiments
since it is not a valid agent in OpenAI Gym. The first two dimensions in the
state space are the $(x,y)$ coordinates of the center mass of the agent, hence
the state space for both agents has two extra dimensions compared to the
standard Ant-v0 and Humanoid-v0 environments from OpenAI Gym.

Now, we present some necessary details of this environment taken from [Zhang
et al., 2020].

Figure 4: 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$ (figure and caption
taken from [Achiam et al., 2017; Zhang et al., 2020]).

In the circle tasks, the goal is for an agent to move along the circumference
of a circle while remaining within a safety region smaller than the radius of
the circle. The exact geometry of the task is shown in Figure 4. The reward
and cost functions are defined as:

$\displaystyle
R(s)=\dfrac{-yv_{x}+xv_{y}}{1+|\sqrt{x^{2}+y^{2}}-r|},~{}~{}C(s)=\mathbb{I}(|x|>x_{\lim}),$

where $x,y$ are the positions of the agent on the plane, $v_{x},v_{y}$ are the
velocities of the agent along the $x$ and $y$ directions, $r$ is the radius of
the circle, and $x_{\lim}$ specifies the range of the safety region. The
radius is set to $r=10$ for both Ant and Humanoid while $x_{\lim}$ is set to 3
and 2.5 for Ant and Humanoid respectively. Note that these settings are
identical to those of the circle task in Achiam et al. [2017]; Zhang et al.
[2020].

###  H.3 Safety Gym

In Safety Gym environments, the agent perceives the world through a robot’s
sensors and interacts with the world through its actuators [Ray et al., 2019].
In this section, we consider two robots: Point and Car, where the presentation
of those safety environments are taken from [Ray et al., 2019], for more
details, please refer to [Ray et al., 2019, Page 8–10]. In this section, we
experiment with the Safety Gym environment-builder two tasks: Goal, Button.

(a) Point

(b) Car

Figure 5:  Fig (a): a 2D robot that can turn and move; Fig (b): a wheeled
robot with a differential drive control, in “Button”, the objective is to
press the highlighted button (visually indicated with a faint gray cylinder),
where figures and caption taken from Safety Gym [Ray et al., 2019].

(a) Goal

(b) Button

Figure 6:  Fig (a): In “Goal,” the objective is to move the robot inside the
green goal area; Fig (b): In “Button”, the objective is to press the
highlighted button (visually indicated with a faint gray cylinder), where
figures and caption are taken from Safety Gym [Ray et al., 2019].

####  H.3.1 Safety Gym Robots

We consider two robots: Point and Car. All actions for all robots are
continuous and linearly scaled to $[-1,+1]$, which is typical for 3D robot-
based RL environments and (anecdotally) improves learning with neural nets.
Modulo scaling, the action parameterization is based on a mix of hand-tuning
and MuJoCo actuator defaults, and we caution that it is not clear if these
choices are optimal. Some safe exploration techniques are action-layer
interventions, like projecting to the closest predicted safe action [Dalal et
al., 2018], and these methods can be sensitive to action parameterization. As
a result, action parameterization may merit more careful consideration than is
usually given. Future work on action space design might be to find action
parameterizations that respect physical measures we care about—for example, an
action space where a fixed distance corresponds to a fixed amount of energy.

Point: A robot constrained to the 2D plane, with one actuator for turning and
another for moving forward/backward. This factored control scheme makes the
robot particularly easy to control for navigation. Point has a small square in
front that makes it easier to visually determine the robot’s direction and
helps the point push a box element that appears in one of our tasks.

Car: The car is a slightly more complex robot that has two independently-
driven parallel wheels and a free-rolling rear wheel. The car is not fixed to
the 2D plane but mostly resides in it. For this robot, both are turning and
moving forward/backward require coordinating both of the actuators. It is
similar in design to simple robots used in education.

####  H.3.2  Tasks

Tasks in Safety Gym are mutually exclusive, and an individual environment can
only use a single task. Reward functions are configurable, allowing rewards to
be either sparse (rewards only obtained on task completion) or dense (rewards
have helpful, hand-crafted shaping terms). Task details are shown as follows.

Goal: Move the robot to a series of goal positions. When a goal is achieved,
the goal location is randomly reset to someplace new, while keeping the rest
of the layout the same. The sparse reward component is attained on achieving a
goal position (robot enters the goal circle). The dense reward component gives
a bonus for moving towards the goal (shown in Figure 5).

Button: Press a series of goal buttons. Several immobile “buttons” are
scattered throughout the environment, and the agent should navigate to and
press (contact) the currently-highlighted button, which is the goal button.
After the agent presses the correct button, the environment will select and
highlight a new goal button, keeping everything else fixed. The sparse reward
component is attained on pressing the current goal button. The dense reward
component gives a bonus for moving towards the current goal button. We show a
visualization in Figure 6).

Environment CPO TRPO-L PPO-L FOCOPS CUP Safexp-PointGoal1-v0 Return $21.29\pm
3.49$ $19.23\pm 1.45$ $16.17\pm 5.89$ $12.46\pm 1.49$ $\bm{23.74\pm 0.12}$
Cost limit (25.0) Constraint $39.00\pm 5.19$ $28.20\pm 5.21$ $21.82\pm 6.31$
$34.67\pm 2.62$ $24.74\pm 0.91$ Safexp-PointButton1-v0 Return $17.69\pm 1.22$
$5.39\pm 1.02$ $4.74\pm 2.73$ $8.36\pm 0.34$ $\bm{19.52\pm 1.38}$ Cost limit
(25.0) Constraint $69.61\pm 8.29$ $25.15\pm 4.88$ $30.37\pm 7.58$ $18.56\pm
1.31$ $26.67\pm 1.84$ Safexp-CarGoal1-v0 Return $\bm{33.00\pm 0.00}$ $17.78\pm
2.34$ $19.93\pm 1.13$ $17.73\pm 3.50$ $27.41\pm 1.80$ Cost limit 25.0)
Constraint $30.50\pm 1.44$ $23.00\pm 4.11$ $29.64\pm 4.79$ $25.50\pm 1.43$
$30.81\pm 1.60$ Safexp-CarButton1-v0 Return $5.80\pm 1.06$ $0.48\pm 0.15$
$0.41\pm 0.13$ $9.47\pm 1.67$ $\bm{12.12\pm 1.91}$ Cost limit (25.0)
Constraint $93.88\pm 13.90$ $23.17\pm 9.76$ $16.23\pm 15.55$ $19.60\pm 1.52$
$29.41\pm 0.40$

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

Figure 7: Performance with respect to penalty factor $\epsilon$ appears in
Algorithm 1.

###  H.4 Discussions

Results of Figure 7 show that the performance of CUP is still very stable for
different settings of $\epsilon$. Additionally, the constraint value of CUP
also still fluctuates around the target value. The different value achieved by
CUP in different setting $\epsilon$ is affected by the simulated environment
and constraint thresholds, which are easy to control

The results of Table 4 show that the proposed CUP significantly outperforms
all the baseline algorithms except on the Safexp-CarGoal1-v0 task. Notably, on
the Safexp-PointButton1-v0 task, CUP achieve $21.27\pm 1.42$ within the safety
region, while the best baseline algorithm is CPO that only obtains a reward of
$17.69\pm 1.22$ but it violates the cost limit $25$ more than a value of 44.
This result is consistent with the result of Figure 2. Besides, from Table 4,
we know although CPO achieves a reward of $33\pm 00$ significantly outperforms
the proposed CUP in Safexp-CarGoal1-v0, CPO needs a cost $30.50\pm 1.44$
higher than CUP.


11institutetext: Research Institute for Signals, Systems and Computational
Intelligence, sinc(i)
(CONICET, Universidad Nacional del Litoral)
Santa Fe, Argentina

# Unsupervised bias discovery
in medical image segmentation

Nicolás Gaggion  Rodrigo Echeveste  Lucas Mansilla  Diego H. Milone  Enzo
Ferrante

###### Abstract

It has recently been shown that deep learning models for anatomical
segmentation in medical images can exhibit biases against certain sub-
populations defined in terms of protected attributes like sex or ethnicity. In
this context, auditing fairness of deep segmentation models becomes crucial.
However, such audit process generally requires access to ground-truth
segmentation masks for the target population, which may not always be
available, especially when going from development to deployment. Here we
propose a new method to anticipate model biases in biomedical image
segmentation in the absence of ground-truth annotations. Our unsupervised bias
discovery method leverages the reverse classification accuracy framework to
estimate segmentation quality. Through numerical experiments in synthetic and
realistic scenarios we show how our method is able to successfully anticipate
fairness issues in the absence of ground-truth labels, constituting a novel
and valuable tool in this field.

###### Keywords:

unsupervised bias discovery fairness medical image segmentation reverse
classification accuracy

##  1 Introduction

An ever growing body of work has shown that machine learning systems can be
systematically biased against certain sub-populations based on attributes like
race or gender in a variety of settings [17]. When it comes to machine
learning systems analyzing health data, this topic becomes extremely relevant,
particularly in medical image computing (MIC) tasks like computed assisted
diagnosis [12] or anatomical segmentation [16]. It is hence vital to audit the
models considering fairness metrics to assess potential disparate performance
of various types among subgroups [13]. A usual way to detect such fairness
issues consists in employing the standard group fairness framework to audit
bias in machine learning models. This framework usually requires access to a
dataset of images with two important pieces of information: the demographic
attributes used to define the groups of analysis, and the ground truth labels
for the task of interest. However, in many situations, we may not have access
to them. Medical images, for example, may lack the necessary metadata due to
privacy concerns. Moreover, obtaining expert label annotations for extensive
image databases can be a time-consuming and costly endeavor, significantly
limiting the availability of these annotations. More importantly, in real life
scenarios, we may be interested in auditing existing deployed systems in a new
target population for which we do not have ground-truth labels to ensure these
models are still fair. To tackle these issues, here we propose an unsupervised
bias discovery (UBD) method, which to our knowledge is the first one
specifically designed for biomedical image segmentation.

The term UBD refers to the process of identifying and uncovering biases in a
machine learning system without using ground-truth labels or demographic
information. Two primary UBD scenarios can be considered. The first one, when
we have access to ground-truth (such as classification labels or anatomical
masks for image segmentation) but lack knowledge about the specific sub-
population metadata for sub-group analysis. Methods addressing this issue have
been recently proposed in fairness literature for machine learning [10, 11].
The second scenario, of main interest to us, appears when we possess
demographic attributes at an individual level to construct pre-defined
analysis groups (e.g. gender, sex, age, ethnicity) but lack ground-truth
annotations for the target population. Here we focus in this last case, i.e.
performing UBD in the absence of ground-truth to anticipate fairness issues in
unseen subjects, particularly in the context of medical image segmentation.
Given recent research indicating how fairness properties may not transfer
under distribution shifts in healthcare [19], understanding how to anticipate
fairness issues in new populations with unforeseen distribution shifts,
especially when ground-truth labels are unavailable, becomes of paramount
importance.

##  2 Related work

Anatomical segmentation is a fundamental task in medical image analysis, with
applications ranging from computational anatomy studies and patient follow-up,
to radiotherapy planning [6, 3]. Several methods have been proposed in the
literature to estimate segmentation performance in the absence of ground-truth
annotations, usually in the context of automatic quality control pipelines.
Some of these methods leverage the concept of predictive uncertainty [4, 3]
under the hypothesis that highly uncertain predictions will correlate with
erroneous pixels. However, these methods heavily rely on the quality of the
uncertainty estimates provided by the segmentation model. In [5], the authors
proposed an alternative learning-based approach where a convolutional neural
network (CNN) is trained to predict the Dice-Sørensen coefficient (or DSC, a
commonly used metric for segmentation quality) from pairs of images with the
corresponding predicted segmentation. This approach is agnostic to the
segmentation model, but it does require to train an extra CNN to predict the
DSC score. Here we build on top of a different approach introduced by
Valindria et al [21], entitled reverse classification accuracy (RCA). This
method proposes to construct a reverse classifier, using only one test image
and its predicted segmentation as pseudo ground truth. Subsequently, this
classifier is assessed on a reference dataset containing available
segmentations, and its performance is used as a proxy of the quality of the
predicted segmentation. Different variants of RCA were originally proposed,
including atlas-forest, CNN-based RCA and atlas-based label propagation RCA
via classic image registration. Here we implement our own deep learning
variant of atlas-based label propagation RCA, which has shown to be fast and
reliable in previous work [14, 15] (see details in Section 3), and use it to
perform UBD.

#### Contributions:

To the best of our knowledge, this is the first study to explore unsupervised
bias discovery in biomedical image segmentation. To this end, we propose a
deep learning variant of atlas-based label propagation RCA and demonstrate its
capacity to reveal hidden biases in segmentation models that exhibit disparate
performance across specific sub-populations. The proposed method is applied to
the task of chest X-ray anatomical segmentation, revealing sex biases in
situations where ground-truth masks are unavailable. This is fundamentally
important when implementing anatomical segmentation systems in real and
dynamic clinical scenarios, as it may help to monitor that fairness is
maintained when models are deployed into production.

##  3 Unsupervised bias discovery via reverse classification accuracy

Figure 1: Outline of the RCA framework (based on [21]). The DSC-score for the
predicted segmentation $S_{I}$ (for which we do not have ground-truth) is
estimated by registering image $I$ to the top-$k$ similar images from the
reference database, and computing the DSC-score of the propagated labels with
respect to the corresponding segmentation masks. The mean DSC computed for the
$k$ reference masks is then used as a DSC estimate of the predicted
segmentation $S_{I}$.

Let us briefly start by describing the atlas based label-propagation RCA
framework [21] adopted in our work to estimate individual DSC coefficients per
image. The process starts with an image $I$ and its corresponding predicted
segmentation $S_{I}$ for which quality needs to be assessed (see Figure 1). We
will refer to this image as the atlas. Additionally, there is a reference
database containing images $J_{i}$ with known ground-truth segmentation masks
$S^{GT}_{J_{i}}$.

Non-rigid registration is then applied to align the atlas with the reference
images in the database, deforming it via a deformation field $D_{i}$ to match
their anatomy. Through label propagation, the predicted segmentation mask
under evaluation ($S_{I}$) is transferred to the corresponding target images
by warping it with the resulting deformation fields, providing a candidate
segmentation mask $\hat{S}_{J_{i}}=S_{I}\circ D_{i}$ per reference image
$J_{i}$. Subsequently, we evaluate the quality of the propagated labels
$\hat{S}_{J_{i}}$ by comparing them with the corresponding ground-truth
segmentation masks $S^{GT}_{J_{i}}$ using DSC (or any other metric of
interest). Thus, given an image $I$, the prediction $S_{I}$ and the reference
database $\\{J,S^{GT}_{J}\\}_{k}$, we estimate the quality of $S_{I}$ as the
average:

$DSC^{RCA}(I,S_{i},\\{J,S^{GT}_{J}\\}_{k})=\frac{\sum_{k}DSC(\hat{S}_{J_{k}},S^{GT}_{J_{k}})}{k}$
(1)

The underlying assumption is that if the segmentation quality of the new image
is high, the RCA estimator will have a high performance on the reference
images; conversely, poor segmentation quality will result in lower performance
on the reference images. By aggregating the predictions of the RCA estimator
on those images, one can assess the quality of the segmentation of a new image
without requiring ground truth data. Note that even though RCA stands for
reverse classification accuracy, here there is no actual classifier, as the
process is fully based on image registration. However, we keep the name
following the original publication [21].

Deep registration networks for atlas-based RCA. We propose a variant of the
original atlas-based label propagation RCA framework which employs deep
registration networks and top-$k$ image selection to reduce computational
time. Our method has four main stages:

  1. 1.

First, the top-$k$ images, which are most similar to the atlas, are identified
within our reference database, to avoid registering the atlas with all the
references.

  2. 2.

Subsequently, a deep CNN is employed to learn the affine registration
parameters for every reference image. This network is implemented following a
Siamese architecture, with two CNN encoders whose output are then processed by
2 fully connected layers to produce the affine parameters of a 2D
transformation.

  3. 3.

Then, a dense deformation field is estimated by an anatomically constrained
deformable registration network (ACNN-RegNet) for every reference image which
is finally used to warp the atlas mask (following Ref. [15]).111Code for the
full RCA pipeline based on deep registration networks is publicly available at
https://github.com/ngaggion/UBD_SourceCode.

  4. 4.

Finally, the estimated $DSC^{RCA}$ is computed following Eq. 1, i.e. by
averaging over all estimates. Note that in the original work [21] the maximum
is computed instead of the average of the DSC scores for the reference images.
In our experiments, we found that taking the average was more robust than the
maximum. We believe this difference may be due to the fact that we perform a
top-$k$ selection where only the top-$k$ similar images are chosen, reducing
the chance of having really different images in our reference set.

Unsupervised Bias Discovery. Let us say we have a trained model M which, given
an image $I$, produces a segmentation mask $S_{I}=\mathbf{M}(I)$. The idea is
to audit M for fairness with respect to a demographic attribute A. Following
previous work [16], we will study fairness in terms of the DSC coefficient. In
particular, we consider the difference in terms of DSC between demographic
groups as a measure of bias (the closer to zero, the fairer the model).
However, since we do not have access to segmentation masks for the target
population, we will use the difference in terms of $DSC^{RCA}$ as a proxy for
this performance gap. For example, let us assume $A$ refers to the biological
sex. We then divide our target population according to whether they are male
or female, and analyze the gap between the corresponding $DSC^{RCA}_{A=M}$ and
$DSC^{RCA}_{A=F}$. Note that throughout the experimental section we will use
the signed difference $\Delta DSC^{RCA}=DSC^{RCA}_{A=M}-DSC^{RCA}_{A=F}$ to be
sure that our estimator is capturing the biases in the right direction. In
what follows, we present synthetic and real experiments to validate the
proposed UBD framework.

##  4 Experiments and discussion

We study the task of lung and heart segmentation in x-ray images, and measure
fairness taking sex as the protected attribute. We employed four different
x-ray datasets (comprising a total of 911 images) including JSRT [20],
Montgomery [2], Shenzhen [9], and a minor subset of the Padchest dataset [1]
for which we had access to ground-truth annotations222For JSRT, Montgomery and
Shenzhen we used the original annotations. For PadChest, we used the
annotations released in the Chest X-ray Landmark Database [7] publicly
available at https://github.com/ngaggion/Chest-xray-landmark-dataset.

All experiments were conducted using a UNet model [18] trained via a compound
soft Dice and cross-entropy loss. In an effort to combine heterogeneous
annotations –given that some images contain only lung annotations while others
contain both lung and heart annotations, we adopted the approach outlined in
[8]. Here, each organ is treated as an independent output channel using binary
versions of the loss functions, and gradients are back-propagated on a
specific channel only when annotations for that channel are available.

Figure 2: Synthetic experiment. Heatmaps illustrating the distribution of real
bias as measured by $\Delta DSC$ (1st column) and the estimated $\Delta
DSC^{RCA}$ (2nd column) across all combinations of models for male and female
subjects. The third column shows scatter plots depicting the correlation
between the real $\Delta DSC$ and the estimated $\Delta DSC^{RCA}$ bias. Each
point represents a combination of models for male and female subjects. The
positive correlation indicates that $\Delta DSC^{RCA}$ serves as a valid
estimator of biases in the absence of ground-truth. Top/bottom row shows
results for lung/heart segmentation.

###  4.1 Synthetic experiment: validating RCA for UBD

We start with a synthetic experiment to validate the effectiveness of RCA as a
bias detector. To obtain networks of varying performance levels, we trained
UNet models until convergence, and used 12 different versions from
intermediate saving checkpoints $M_{1\leq i\leq 12}$, one after each epoch
from the 1st to the 11th and a final checkpoint at convergence. Note that
since performance improves over training, in general the performance of model
$M_{i}$ will tend to be higher than that of $M_{j}$ if $i>j$. We used balanced
training and test sets in terms of sex (50% male and 50% female) (80-20%
split). To asses biases the test subset was analyzed in terms of the two sex-
specific subgroups.

We simulated a scenario where the segmentation quality varies based on sex,
with either male or female patients exhibiting superior performance. This was
achieved by selecting pairs of UNet models $(M_{i},M_{j})\forall i,j:1\leq
i,j\leq 12$, and segmenting the male test set with $M_{i}$ and the female set
with $M_{j}$. Note that even though masks are coming from different models, in
this synthetic experiment we consider them to be generated by a single
fictitious model whose fairness we would aim to audit. This led to 144
possible combinations (fictitious models), where the segmentation quality in
the male set was usually higher if $i>j$ and vice-versa. Figure 2 (1st column)
shows the real signed DSC gap for all possible UNet combinations tested on
male ($M_{i}$) and female ($M_{j}$) patients, computed as $\Delta
DSC=DSC_{A=M}-DSC_{A=F}$ (i.e. positive indicates higher segmentation quality
for the male group, and negative for the female group). We then repeated the
experiment but computing $\Delta DSC^{RCA}$, which does not require ground-
truth annotations (see Figure 2, 2nd column). As it can be observed,
$DSC^{RCA}$ is able to recover the same biases, up to a scaling factor. To
better understand this relation, we also depict the real vs. estimated biases
in a scatter plot shown in the 3rd column of Figure 2.

Note that the direction of the bias, i.e., whether the performance is skewed
towards males or females, can be inferred from the sign of the difference;
positive values indicate a male bias and vice versa. We highlight that the
signs of the $\Delta DSC$ and $\Delta DSC^{RCA}$ agree in 90% and 92% for the
lungs and heart, respectively. When excluding cases where the bias was less
than 0.01 (since small gaps may be due to statistical noise), the sign
agreement improved to 96% and 92%. An even greater accuracy, 100% and 96%, was
obtained when all pairs with bias less than 0.02 were excluded, thereby
validating $\Delta DSC^{RCA}$ as a reliable estimator of bias in segmentation
models.

###  4.2 Real experiment: auditing chest x-ray segmentation models for sex
bias

We now proceed to validate $\Delta DSC^{RCA}$ in a more realistic scenario,
auditing the bias of two concrete chest x-ray segmentation models. Data
imbalance in terms of protected attributes in the training set is known to
result in models which are biased in terms of those attributes [12]. We
exploit this fact to produce biased models by training two sets of 5-fold
cross validation UNet models: one using only the male subset of the training
set, and the other on the female subset. These models were then evaluated
separately on the Male and Female partitions of the test set. Here again we
employed an 80-20% split for the complete train and test sets respectively.
Intriguingly, when measuring biases using the available ground-truth
annotations, we discovered that independently of the training set, models tend
to perform better on female patients, with a slightly more pronounced gap when
the model is trained on female patients (Figure 3, left and center column
boxplots).

Crucially, estimated performance gaps via RCA strongly correlate with true
gaps both for lung and heart segmentation also in this scenario (Figure 3,
right column top and bottom). However, it should be noted that the slope of
the correlation is not exactly one and varies between tasks (cf. Figure 3 top
vs bottom row). This suggests that while $\Delta DSC^{RCA}$ provides reliable
estimates of bias up to a scaling factor, as in the synthetic experiment,
calibration may be necessary to accurately estimate the magnitude of bias when
transitioning from development to deployment scenarios.

Figure 3: Real experiment Boxplots depict the distribution of real bias as
measured by Real $DSC$ (1st column) and the estimated $DSC^{RCA}$ (2nd column)
across all combinations of models trained and tested on male and female
subjects separately. The third column shows scatter plots depicting the
correlation between the real $\Delta DSC$ and the estimated $\Delta DSC^{RCA}$
bias. Each point represents a model. The positive correlation indicates that
$\Delta DSC^{RCA}$ serves as a valid estimator of biases in the absence of
ground-truth. Top/bottom row shows results for lungs/heart segmentation.

##  5 Conclusion

The increasing adoption of automated methods in the context of MIC brings with
it a responsibility to produce models which do not unfairly discriminate in
terms of protected attributes. After development of a model, the reduced
number of expert label annotations in the real-world dataset where the model
is to be deployed may significantly limit the possibility to anticipate
fairness issues. In order to estimate possible biases, here we propose a novel
unsupervised bias discovery for biomedical image segmentation based on the RCA
framework.

To evaluate our framework we employed x-ray datasets where ground truth
annotations were actually available and true biases could hence be obtained. A
first synthetic experiment, where the performance of a model could be easily
manipulated, allowed us to validate our estimated bias score in a controlled
scenario, showing the viability of our method. A second experiment performed
in a more realistic scenario, where models were trained for high performance
but in a data-imbalance setting resulting in biases, confirmed UBD was able to
correctly capture these biases. Overall, these results show that UBD methods
based on RCA could prove extremely helpful to anticipate biases at deployment
in clinical settings where ground truth annotations are not yet available.

##  6 Acknowledgments

This work was supported by Argentina’s National Scientific and Technical
Research Council (CONICET), which covered the salaries of E.F., R.E. and D.M.,
and the fellowships of N.G. and L.M. The authors gratefully acknowledge NVIDIA
Corporation with the donation of the GPUs used for this research, and the
support of Universidad Nacional del Litoral (Grants CAID-PIC-50220140100084LI,
50620190100145LI), ANPCyT (PICT-PRH-2019-00009) and the Google Award for
Inclusion Research (AIR) Program.

## References

  * [1] Bustos, A., Pertusa, A., Salinas, J.M., de la Iglesia-Vayá, M.: Padchest: A large chest x-ray image dataset with multi-label annotated reports. Medical image analysis 66, 101797 (2020)
  * [2] Candemir, S., others.: Lung segmentation in chest radiographs using anatomical atlases with nonrigid registration. IEEE Transactions on Medical Imaging 33(2), 577–590 (2014). https://doi.org/10.1109/TMI.2013.2290491
  * [3] Cubero, L., Serrano, J., Castelli, J., de Crevoisier, R., Acosta, O., J., P.: Exploring uncertainty for clinical acceptability in head and neck deep learning-based oar segmentation. In: IEEE ISBI 2023. IEEE (2023)
  * [4] Czolbe, S., Arnavaz, K., Krause, O., Feragen, A.: Is segmentation uncertainty useful? In: Information Processing in Medical Imaging: 27th International Conference, IPMI 2021, Virtual Event, June 28–June 30, 2021, Proceedings 27. pp. 715–726. Springer (2021)
  * [5] Fournel, J., Bartoli, A., Bendahan, D., Guye, M., Bernard, M., Rauseo, E., Khanji, M.Y., Petersen, S.E., Jacquier, A., Ghattas, B.: Medical image segmentation automatic quality control: A multi-dimensional approach. Medical Image Analysis 74, 102213 (2021)
  * [6] Fu, Y., Lei, Y., Wang, T., Curran, W.J., Liu, T., Yang, X.: A review of deep learning based methods for medical image multi-organ segmentation. Physica Medica 85, 107–122 (2021)
  * [7] Gaggion, N., Mansilla, L., Mosquera, C., Milone, D.H., Ferrante, E.: Improving anatomical plausibility in medical image segmentation via hybrid graph neural networks: applications to chest x-ray analysis. IEEE Transactions on Medical Imaging (2022). https://doi.org/10.1109/tmi.2022.3224660, https://doi.org/10.1109%2Ftmi.2022.3224660
  * [8] Gaggion, N., Vakalopoulou, M., Milone, D.H., Ferrante, E.: Multi-center anatomical segmentation with heterogeneous labels via landmark-based models. In: 20th IEEE International Symposium on Biomedical Imaging (ISBI). IEEE (2023)
  * [9] Jaeger, S.e.a.: Automatic tuberculosis screening using chest radiographs. IEEE Transactions on Medical Imaging 33(2), 233–245 (2014). https://doi.org/10.1109/TMI.2013.2284099
  * [10] Krishnakumar, A., Prabhu, V., Sudhakar, S., Hoffman, J.: Udis: Unsupervised discovery of bias in deep visual recognition models. In: British Machine Vision Conference (BMVC). vol. 1, p. 3 (2021)
  * [11] Lahoti, P., Beutel, A., Chen, J., Lee, K., Prost, F., Thain, N., Wang, X., Chi, E.: Fairness without demographics through adversarially reweighted learning. Advances in neural information processing systems 33, 728–740 (2020)
  * [12] Larrazabal, A.J., Nieto, N., Peterson, V., Milone, D.H., Ferrante, E.: Gender imbalance in medical imaging datasets produces biased classifiers for computer-aided diagnosis. Proceedings of the National Academy of Sciences 117(23), 12592–12594 (2020)
  * [13] Liu, X., Glocker, B., McCradden, M.M., Ghassemi, M., Denniston, A.K., Oakden-Rayner, L.: The medical algorithmic audit. The Lancet Digital Health 4(5), e384–e397 (2022)
  * [14] Mansilla, L., Ferrante, E.: Segmentación multi-atlas de imágenes médicas con selección de atlas inteligente y control de calidad automático. In: XXIV Congreso Argentino de Ciencias de la Computación (La Plata, 2018). (2018)
  * [15] Mansilla, L., Milone, D.H., Ferrante, E.: Learning deformable registration of medical images with anatomical constraints. Neural Networks 124, 269–279 (2020)
  * [16] Puyol-Antón, E., Ruijsink, B., Piechnik, S.K., Neubauer, S., Petersen, S.E., Razavi, R., King, A.P.: Fairness in cardiac mr image analysis: an investigation of bias due to data imbalance in deep learning based segmentation. In: Medical Image Computing and Computer Assisted Intervention–MICCAI 2021: 24th International Conference, Strasbourg, France, September 27–October 1, 2021, Proceedings, Part III 24. pp. 413–423. Springer (2021)
  * [17] Ricci Lara, M.A., Echeveste, R., Ferrante, E.: Addressing fairness in artificial intelligence for medical imaging. nature communications 13(1), 1–6 (2022)
  * [18] Ronneberger, O., Fischer, P., Brox, T.: U-net: Convolutional networks for biomedical image segmentation. In: Medical Image Computing and Computer-Assisted Intervention–MICCAI 2015: 18th International Conference, Munich, Germany, October 5-9, 2015, Proceedings, Part III 18. pp. 234–241. Springer (2015)
  * [19] Schrouff, J., Harris, N., Koyejo, S., Alabdulmohsin, I.M., Schnider, E., Opsahl-Ong, K., Brown, A., Roy, S., Mincu, D., Chen, C., et al.: Diagnosing failures of fairness transfer across distribution shift in real-world medical settings. Advances in Neural Information Processing Systems 35, 19304–19318 (2022)
  * [20] Shiraishi, J., et al.: Development of a digital image database for chest radiographs with and without a lung nodule: receiver operating characteristic analysis of radiologists’ detection of pulmonary nodules. American Journal of Roentgenology 174(1) (2000)
  * [21] Valindria, V.V., Lavdas, I., Bai, W., Kamnitsas, K., Aboagye, E.O., Rockall, A.G., Rueckert, D., Glocker, B.: Reverse classification accuracy: predicting segmentation performance in the absence of ground truth. IEEE transactions on medical imaging 36(8), 1597–1606 (2017)