$s_{\scriptscriptstyle\mathcal{O}}$ (blue circles) are exit states. Subscripts
$\rightarrow,\downarrow,\leftarrow$ indicate directions respectively for
$\mathopen{}\mathclose{{}\left(\ell\mathopen{}\mathclose{{}\left(u}\right),\langle
u,v_{2}\rangle}\right)$,$\mathopen{}\mathclose{{}\left(\ell\mathopen{}\mathclose{{}\left(u}\right),\langle
u,v_{3}\rangle}\right)$, and
$\mathopen{}\mathclose{{}\left(\ell\mathopen{}\mathclose{{}\left(u}\right),\langle
u,v_{4}\rangle}\right)$. $B=\left\\{s_{B}\right\\}$ (red circle) and
$T=\left\\{v_{3}\right\\}$ (green square) are a bad state and the final goal,
respectively.

The sufficiency directly follows from Theorem 5.1 and the fact that a
deterministic stationary policy is sufficient to maximize constrained
reachability and discounted objectives in MDPs [48, 11] (in particular in
$\mathcal{M}_{\mathrm{\Pi}}$). Now we show that memory of at least size
$\left|V\right|$ is necessary. Take the hierarchical model of Fig. 5. Graph
vertices are depicted by squares, while states are depicted by circles. States
of the form $s_{\scriptscriptstyle\mathcal{O}}$ (blue) are exit states. We
further write $\rightarrow,\downarrow,\leftarrow$ respectively for
$\mathopen{}\mathclose{{}\left(\ell\mathopen{}\mathclose{{}\left(u}\right),\langle
u,v_{2}\rangle}\right)$,$\mathopen{}\mathclose{{}\left(\ell\mathopen{}\mathclose{{}\left(u}\right),\langle
u,v_{3}\rangle}\right)$, and
$\mathopen{}\mathclose{{}\left(\ell\mathopen{}\mathclose{{}\left(u}\right),\langle
u,v_{4}\rangle}\right)$, and we choose $B=\left\\{s_{B}\right\\}$ (red state)
and $T=\left\\{v_{3}\right\\}$ (green square). A stationary planner
$\tau\colon V\to E$ clearly fails here. Indeed, $\tau$ should choose $\langle
u,v_{4}\rangle$ to follow $\pi_{\leftarrow}$ when entering $u$ from $v_{1}$,
$\langle u,v_{3}\rangle$ to follow $\pi_{\downarrow}$ from $v_{2}$, and
$\langle u,v_{2}\rangle$ to follow $\pi_{\leftarrow}$ from $v_{4}$. So, $\tau$
must remember the vertex from which the room is entered.

######  Proof (of Theorem 5.2)

Given any MDP
$\mathcal{M}=\langle\mathcal{S},\mathcal{A},\mathbf{P},\mathbf{I}\rangle$, we
start by recalling the definition of the value function of any reach-avoid
objective of the form $\mathbb{O}(T,B)$ with $T,B\subseteq\mathcal{S}$ for a
discount factor $\gamma\in\mathopen{(}0,1\mathclose{)}$ and a policy $\pi$:

$val\mathopen{}\mathclose{{}\left(\pi,\mathbb{O},\gamma}\right)=\text{{E}}_{\rho\sim\mathbb{P}^{\mathcal{M}}_{\pi}}\left[\sup_{i\geq
0}\gamma^{i}\mathds{1}\left\\{{s_{i}\in{T}}\right\\}\mathds{1}\left\\{{\rho\in\mathbb{O}}\right\\}\right],$
(8)

where $s_{i}$ denotes the $i^{\text{th}}$ state of $\rho$. Intuitively, this
corresponds to the expected value of the discount scaled to the time step of
_the first visit of the set $T$_, ensuring that the set of bad states $B$ is
not encountered before this first visit.

First, notice that the reach-avoid property can be merely reduced to a simple
reachability property by making absorbing the states of $B$ [11]. Precisely,
write $\mathcal{M}^{\nobreak\hskip
0.45502pt\scaleto{\rotatebox[origin={c}]{90.0}{$\circlearrowright$}}{1.4ex}B}$
for the MDP $\mathcal{M}$ where we make all states from $B$ absorbing, i.e.,
where $\mathbf{P}$ is modified so that
$\mathbf{P}\mathopen{}\mathclose{{}\left(s\mid s,a}\right)=1$ for any $s\in B$
and $a\in\mathcal{A}$. Then, one can get rid of the indicator
$\mathds{1}\left\\{{\rho\in\mathbb{O}}\right\\}$ in Eq. 8 by considering
infinite paths of $\mathcal{M}^{\nobreak\hskip
0.45502pt\scaleto{\rotatebox[origin={c}]{90.0}{$\circlearrowright$}}{1.4ex}B}$:

$\displaystyle val\mathopen{}\mathclose{{}\left(\pi,\mathbb{O},\gamma}\right)$
$\displaystyle=\text{{E}}_{\rho\sim\mathbb{P}^{\mathcal{M}}_{\pi}}\left[\sup_{i\geq
0}\gamma^{i}\mathds{1}\left\\{{s_{i}\in{T}}\right\\}\mathds{1}\left\\{{\rho\in\mathbb{O}}\right\\}\right]$
$\displaystyle=\text{{E}}_{\rho\sim\mathbb{P}^{\mathcal{M}^{\nobreak\hskip
0.32501pt\scaleto{\rotatebox[origin={c}]{90.0}{$\circlearrowright$}}{1.4ex}B}}_{\pi}}\left[\sup_{i\geq
0}\gamma^{i}\mathds{1}\left\\{{s_{i}\in{T}}\right\\}\right].$

Second, define

$\textit{Paths}^{\,\textit{fin}}_{\Diamond
T}=\left\\{\rho=s_{0},s_{1},\dots,s_{i}\mid s_{i}\in T\text{ and }s_{j}\not\in
T\text{ for all }j<t\right\\}$

as the set of finite paths that end up in $T$, with $T$ being visited for the
first time. Then, on can get rid of the supremum of Eq. 8 follows:

$\displaystyle val\mathopen{}\mathclose{{}\left(\pi,\mathbb{O},\gamma}\right)$
$\displaystyle=\text{{E}}_{\rho\sim\mathbb{P}^{\mathcal{M}^{\nobreak\hskip
0.32501pt\scaleto{\rotatebox[origin={c}]{90.0}{$\circlearrowright$}}{1.4ex}B}}_{\pi}}\left[\sup_{i\geq
0}\gamma^{i}\mathds{1}\left\\{{s_{i}\in{T}}\right\\}\right]$
$\displaystyle=\text{{E}}_{\rho\sim\mathbb{P}^{\mathcal{M}^{\nobreak\hskip
0.32501pt\scaleto{\rotatebox[origin={c}]{90.0}{$\circlearrowright$}}{1.4ex}B}}_{\pi}}\left[\sum_{t=0}^{\infty}\gamma^{t}\cdot\mathds{1}\left\\{{\textit{pref}\,\mathopen{}\mathclose{{}\left(\rho,t}\right)\in\textit{Paths}^{\,\textit{fin}}_{\Diamond
T}}\right\\}\right],$ (9)

where
$\textit{pref}\,\mathopen{}\mathclose{{}\left(\rho,t}\right)=s_{0},s_{1},\dots,s_{t}$
yields the prefix of $\rho=s_{0},s_{1},\dots$ which ends up in the
$t^{\text{th}}$ state $s_{t}$. The attentive reader may have noticed that the
resulting expectation can be seen as the expectation of a discounted
cumulative reward signal (or a _discounted return_ , for short), where a
reward of one is incurred when visiting $T$ _for the first time_. Taking it a
step further, define the reward function

$\mathit{rew}\mathopen{}\mathclose{{}\left(s,a,s^{\prime}}\right)=\begin{cases}{1-\gamma}&\text{if
}s\in T,\text{ and}\\\ 0&\text{otherwise}.\end{cases}$

Then, the value function can be re-written as

$\displaystyle val\mathopen{}\mathclose{{}\left(\pi,\mathbb{O},\gamma}\right)$
$\displaystyle=\text{{E}}_{\rho\sim\mathbb{P}^{\mathcal{M}^{\nobreak\hskip
0.32501pt\scaleto{\rotatebox[origin={c}]{90.0}{$\circlearrowright$}}{1.4ex}B}}_{\pi}}\left[\sum_{t=0}^{\infty}\gamma^{t}\cdot\mathds{1}\left\\{{\textit{pref}\,\mathopen{}\mathclose{{}\left(\rho,t}\right)\in\textit{Paths}^{\,\textit{fin}}_{\Diamond
T}}\right\\}\right]$
$\displaystyle=\text{{E}}_{\rho\sim\mathbb{P}^{\mathcal{M}^{\nobreak\hskip
0.32501pt\scaleto{\rotatebox[origin={c}]{90.0}{$\circlearrowright$}}{1.4ex}T\cup
B}}_{\pi}}\left[\sum_{t=0}^{\infty}\gamma^{t}\cdot r_{t}\right].$

For any state $s\in T$, notice that since $T$ is absorbing in
$\mathcal{M}^{\nobreak\hskip
0.45502pt\scaleto{\rotatebox[origin={c}]{90.0}{$\circlearrowright$}}{1.4ex}T\cup
B}$,

$\displaystyle
val_{s}\mathopen{}\mathclose{{}\left(\pi,\mathbb{O},\gamma}\right)$
$\displaystyle=1.$ (10)

It is folklore that the discounted return is the solution of the Bellman’s
equation
$val_{s}\mathopen{}\mathclose{{}\left(\pi,\mathbb{O},\gamma}\right)=\gamma\text{{E}}_{s^{\prime}\sim\mathbf{P}\mathopen{}\mathclose{{}\left({\cdotp}\mid
s,a}\right)}\,\left[\mathit{rew}\mathopen{}\mathclose{{}\left(s,a,s^{\prime}}\right)\cdot
val_{s^{\prime}}\mathopen{}\mathclose{{}\left(\pi,\mathbb{O},\gamma}\right)\right]$
for any $s\in\mathcal{S}$ [48]. In particular, considering the reach-avoid
objective $\mathbb{O}$, we have by Eq. 10

$val_{s}\mathopen{}\mathclose{{}\left(\pi,\mathbb{O},\gamma}\right)=\begin{cases}\gamma\text{{E}}_{s^{\prime}\sim\mathbf{P}\mathopen{}\mathclose{{}\left({\cdotp}\mid
s,a}\right)}\,\left[val_{s^{\prime}}\mathopen{}\mathclose{{}\left(\pi,\mathbb{O},\gamma}\right)\right]&\text{if
}s\notin T\cup B,\\\ 1&\text{if }s\in T,\text{ and}\\\ 0&\text{otherwise, when
}s\in B.\end{cases}$

Now, let us consider the values of the MDP plan $\mathcal{M}_{\mathrm{\Pi}}$
for the reach-avoid objective
$\mathbb{O}\mathopen{}\mathclose{{}\left(\mathbf{T},\mathbf{B}}\right)$ where
$\mathbf{T}=\left\\{\langle s,v,u\rangle\mid v\in T\right\\}$ and
$\mathbf{B}=\left\\{\langle s,v,u\rangle\mid s\not\in
B_{\ell\mathopen{}\mathclose{{}\left(v}\right)}\right\\}$ for the high-level
objective $\Diamond T$ and set of low-level objectives
$\left\\{\mathbb{O}_{R}^{d}\colon R\in\mathcal{R},d\in D_{R}\right\\}$ so that
$B_{R}$ is the set of states to avoid in room $R$. Fix a
$\left|V\right|$-memory hierarchical controller
$\pi=\langle\tau,\mathrm{\Pi}\rangle$ in for hierarchical model $\mathcal{H}$
(which is compliant with $\mathcal{M}_{\mathrm{\Pi}}$, see Thm. 5.1 and the
related proof). We take a close look to the value of each state in
$\mathcal{M}_{\mathrm{\Pi}}$ by following the same structure as we used for
the definition of $\mathcal{M}_{\mathrm{\Pi}}$ (cf. Sect. 5.1). For the sake
of presentation, given any pair of vertices $v,u\in V$, we may note $\langle
s_{\text{reset}},v,u\rangle$ to refer to the (unified, cf. Assumption 2) reset
state $s_{\text{reset}}\in\mathcal{S}_{\mathrm{\Pi}}$. Given a state $\langle
s,v,u\rangle\in\mathcal{S}_{\mathrm{\Pi}}$ with direction $d=\langle
v,u\rangle$,

  1. (i)

if $s$ is not an exit state, i.e., if
$s\not\in\mathcal{O}_{\ell\mathopen{}\mathclose{{}\left(v}\right)}$, then

$\displaystyle val_{\langle
s,v,u\rangle}\mathopen{}\mathclose{{}\left(\pi,\mathbb{O},\gamma}\right)$
$\displaystyle=$ $\displaystyle\gamma\text{{E}}_{\langle
s^{\prime},v,u\rangle\sim\mathbf{P}_{\mathrm{\Pi}}\mathopen{}\mathclose{{}\left({\cdotp}\mid\langle
s,v,u\rangle,*}\right)}\,\left[val_{\langle
s^{\prime},v,u\rangle}\mathopen{}\mathclose{{}\left(\pi,\mathbb{O},\gamma}\right)\right]$
(by Eq. 6) $\displaystyle=$
$\displaystyle\gamma\sum_{s^{\prime}\in\mathcal{S}_{\ell\mathopen{}\mathclose{{}\left(v}\right)}}\mathbf{P}_{\mathrm{\Pi}}\mathopen{}\mathclose{{}\left(\langle
s^{\prime},v,u\rangle\mid\langle s,v,u\rangle,*}\right)\cdot val_{\langle
s^{\prime},v,u\rangle}\mathopen{}\mathclose{{}\left(\pi,\mathbb{O},\gamma}\right)$
$\displaystyle=$
$\displaystyle\gamma\sum_{s^{\prime}\in\mathcal{S}_{\ell\mathopen{}\mathclose{{}\left(v}\right)}}\sum_{a\in\mathcal{A}_{\ell\mathopen{}\mathclose{{}\left(v}\right)}}\mkern
1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern
1.5mu_{\ell\mathopen{}\mathclose{{}\left(v}\right),d}\mathopen{}\mathclose{{}\left(a\mid
s}\right)\cdot\mathbf{P}_{\ell\mathopen{}\mathclose{{}\left(v}\right)}\mathopen{}\mathclose{{}\left(s^{\prime}\mid
s,a}\right)\cdot val_{\langle
s^{\prime},v,u\rangle}\mathopen{}\mathclose{{}\left(\pi,\mathbb{O},\gamma}\right);$

  2. (ii)

if $s$ is an exit state in the direction $d$, i.e.,
$s\in\mathcal{O}_{\ell\mathopen{}\mathclose{{}\left(u}\right)}\mathopen{}\mathclose{{}\left(d}\right)$,
given the direction chosen by the planner
$d^{\prime}=\tau\mathopen{}\mathclose{{}\left(v,u}\right)=\langle u,t\rangle$
for some neihbor $t\in N\mathopen{}\mathclose{{}\left(u}\right)$, we have

$\displaystyle val_{\langle
s,v,u\rangle}\mathopen{}\mathclose{{}\left(\pi,\mathbb{O},\gamma}\right)$
$\displaystyle=$ $\displaystyle\gamma\text{{E}}_{\langle
s^{\prime},u,t\rangle\sim\mathbf{P}_{\mathrm{\Pi}}\mathopen{}\mathclose{{}\left({\cdotp}\mid\langle
s,v,u\rangle}\right)}\,\left[val_{\langle
s^{\prime},u,t\rangle}\mathopen{}\mathclose{{}\left(\pi,\mathbb{O},\gamma}\right)\right]$
$\displaystyle=$
$\displaystyle\gamma\text{{E}}_{s^{\prime}\sim\mathcal{I}_{\ell\mathopen{}\mathclose{{}\left(u}\right)}\mathopen{}\mathclose{{}\left({\cdotp}\mid
d}\right)}\,\left[val_{\langle
s^{\prime},u,t\rangle}\mathopen{}\mathclose{{}\left(\pi,\mathbb{O},\gamma}\right)\right]$
(by Eq. 7) $\displaystyle=$
$\displaystyle\gamma\sum_{s^{\prime}\in\mathcal{S}_{\ell\mathopen{}\mathclose{{}\left(u}\right)}}\mathcal{I}_{\ell\mathopen{}\mathclose{{}\left(u}\right)}\mathopen{}\mathclose{{}\left(s^{\prime}\mid
d}\right)\cdot{val_{\langle
s^{\prime},u,t\rangle}\mathopen{}\mathclose{{}\left(\pi,\mathbb{O},\gamma}\right)};$
(11)

  3. (iii)

if $v$ is the target, i.e., $v\in T$,
$val_{s}\mathopen{}\mathclose{{}\left(\pi,\mathbb{O},\gamma}\right)=1$; and

  4. (iv)

otherwise, when $s$ is a bad state, i.e., $s\in
B_{\ell\mathopen{}\mathclose{{}\left(v}\right)}$,
$val_{s}\mathopen{}\mathclose{{}\left(\pi,\mathbb{O},\gamma}\right)=0$.

Take $R=\ell\mathopen{}\mathclose{{}\left(v}\right)$. By (i) and (ii), when
$s$ is not an exit state, i.e.,
$s\not\in\mathcal{O}_{\ell\mathopen{}\mathclose{{}\left(v}\right)}\mathopen{}\mathclose{{}\left(d}\right)$,
we have

$\displaystyle val_{\langle
s,v,u\rangle}\mathopen{}\mathclose{{}\left(\pi,\mathbb{O},\gamma}\right)=\sum_{s_{0},s_{1},\dots,s_{i}\in\textit{Path}^{\,\textit{fin}}_{{\mathbb{O}_{R}^{d}}}}\gamma^{i}\mathbb{P}^{R_{s}}_{\mkern
1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern
1.5mu_{R,d}}\mathopen{}\mathclose{{}\left(s_{0},s_{1},\dots,s_{i}}\right)\cdot
val_{\langle
s_{i},v,u\rangle}\mathopen{}\mathclose{{}\left(\pi,\mathbb{O},\gamma}\right),$

so that

$\textit{Path}^{\,\textit{fin}}_{\mathbb{O}_{R}^{d}}=\textit{Path}^{\,\textit{fin}}_{\Diamond\mathcal{O}_{R}\mathopen{}\mathclose{{}\left(d}\right)}\setminus\left\\{\rho=s_{0},s_{1},\dots,s_{n}\mid\exists
1\leq i\leq n,\,s_{i}\in B_{R}\right\\},$

where we denote by $R_{s}$ the room $R$ where we change the initial
distribution by the Dirac
$\mathbf{I}_{R}\mathopen{}\mathclose{{}\left(s_{0}}\right)=\mathds{1}\left\\{{s_{0}=s}\right\\}$,
and $\mathbb{P}^{R_{s}}_{\mkern
1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu_{R,d}}$ is the
distribution over paths of $R$ which start in state $s$ which is induced by
the choices of the low-level latent policy $\mkern
1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu_{R,d}$.

Following Eq. 11, notice that $val_{\langle
s_{\text{exit}},v,u\rangle}\mathopen{}\mathclose{{}\left(\pi,\mathbb{O},\gamma}\right)=val_{\langle
s^{\prime}_{\text{exit}},v,u\rangle}\mathopen{}\mathclose{{}\left(\pi,\mathbb{O},\gamma}\right)$
for any
$s_{\text{exit}},s^{\prime}_{\text{exit}}\in\mathcal{O}_{R}\mathopen{}\mathclose{{}\left(d}\right)$:
the probability of going to the next room
$R^{\prime}=\ell\mathopen{}\mathclose{{}\left(u}\right)$ from an exit state of
the current room $R$ only depends on the entrance function
$\mathcal{I}_{R^{\prime}}$ and is independent from the exact exit state which
allowed to leave the current room $R$. Therefore, we further denote by
$val_{\langle{\cdotp},v,u\rangle}\mathopen{}\mathclose{{}\left(\pi,\mathbb{O},\gamma}\right)$
the value of any exit state of $R$ in direction $d$, i.e.,
$val_{\langle{\cdotp},v,u\rangle}\mathopen{}\mathclose{{}\left(\pi,\mathbb{O},\gamma}\right)=val_{\langle
s_{\text{exit}},v,u\rangle}\mathopen{}\mathclose{{}\left(\pi,\mathbb{O},\gamma}\right)$
for all
$s_{\text{exit}}\in\mathcal{O}_{R}\mathopen{}\mathclose{{}\left(d}\right)$.
Then, we have

$\displaystyle val_{\langle
s,v,u\rangle}\mathopen{}\mathclose{{}\left(\pi,\mathbb{O},\gamma}\right)$
$\displaystyle=$
$\displaystyle\sum_{s_{0},s_{1},\dots,s_{i}\in\textit{Path}^{\,\textit{fin}}_{\mathbb{O}_{d}^{R}}}\gamma^{i}\mathbb{P}^{R_{s}}_{\mkern
1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern
1.5mu_{R,d}}\mathopen{}\mathclose{{}\left(s_{0},s_{1},\dots,s_{i}}\right)\cdot
val_{\langle
s_{i},v,u\rangle}\mathopen{}\mathclose{{}\left(\pi,\mathbb{O},\gamma}\right)$
$\displaystyle=$
$\displaystyle\sum_{s_{0},s_{1},\dots,s_{i}\in\textit{Path}^{\,\textit{fin}}_{\mathbb{O}_{R}^{d}}}\gamma^{i}\mathbb{P}^{R_{s}}_{\mkern
1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern
1.5mu_{R,d}}\mathopen{}\mathclose{{}\left(s_{0},s_{1},\dots,s_{i}}\right)\cdot
val_{\langle{\cdotp},v,u\rangle}\mathopen{}\mathclose{{}\left(\pi,\mathbb{O},\gamma}\right)$
$\displaystyle=$ $\displaystyle
val_{\langle{\cdotp},v,u\rangle}\mathopen{}\mathclose{{}\left(\pi,\mathbb{O},\gamma}\right)\cdot\sum_{s_{0},s_{1},\dots,s_{i}\in\textit{Path}^{\,\textit{fin}}_{\mathbb{O}_{R}^{d}}}\gamma^{i}\mathbb{P}^{R_{s}}_{\mkern
1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern
1.5mu_{R,d}}\mathopen{}\mathclose{{}\left(s_{0},s_{1},\dots,s_{i}}\right)$
$\displaystyle=$ $\displaystyle
val_{\langle{\cdotp},v,u\rangle}\mathopen{}\mathclose{{}\left(\pi,\mathbb{O},\gamma}\right)\cdot
val_{s}\mathopen{}\mathclose{{}\left(\mkern
1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern
1.5mu_{d,R},\gamma,\mathbb{O}_{R}^{d}}\right),$ (by Eq. 9)

where $val_{s}\mathopen{}\mathclose{{}\left(\mkern
1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern
1.5mu_{R,d},\gamma,\mathbb{O}_{R}^{d}}\right)$ denotes the value of the reach-
avoid objective
$\mathbb{O}_{R}^{d}=\mathbb{O}\mathopen{}\mathclose{{}\left(\mathcal{O}_{R}\mathopen{}\mathclose{{}\left(d}\right),B_{R}}\right)$
in the room $R$ from state $s\in R$. Henceforth, for the sake of readability,
we write $val_{s}(\mathbb{O}_{R}^{d})$ for
$val_{s}\mathopen{}\mathclose{{}\left(\mkern
1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern
1.5mu_{R,d},\gamma,\mathbb{O}_{R}^{d}}\right)$. Then,

$\displaystyle
val_{\langle{\cdotp},v,u\rangle}\mathopen{}\mathclose{{}\left(\pi,\mathbb{O},\gamma}\right)$
$\displaystyle=$
$\displaystyle\gamma{\sum_{s^{\prime}\in\mathcal{S}_{\ell\mathopen{}\mathclose{{}\left(u}\right)}}\mathcal{I}_{\ell\mathopen{}\mathclose{{}\left(u}\right)}\mathopen{}\mathclose{{}\left(s^{\prime}\mid
d=\langle v,u\rangle}\right)\cdot val_{\langle
s^{\prime},\tau\mathopen{}\mathclose{{}\left(v,u}\right)\rangle}\mathopen{}\mathclose{{}\left(\pi,\mathbb{O},\gamma}\right)}$
$\displaystyle=$
$\displaystyle\gamma{\sum_{s^{\prime}\in\mathcal{S}_{\ell\mathopen{}\mathclose{{}\left(u}\right)}}\mathcal{I}_{\ell\mathopen{}\mathclose{{}\left(u}\right)}\mathopen{}\mathclose{{}\left(s^{\prime}\mid
d=\langle v,u\rangle}\right)\cdot
val_{s^{\prime}}\mathopen{}\mathclose{{}\left(\mathbb{O}_{\ell\mathopen{}\mathclose{{}\left(u}\right)}^{\tau\mathopen{}\mathclose{{}\left(v,u}\right)}}\right)\cdot
val_{\langle{\cdotp},\tau\mathopen{}\mathclose{{}\left(v,u}\right)\rangle}\mathopen{}\mathclose{{}\left(\pi,\mathbb{O},\gamma}\right)}.$

Finally, by construction of $\mathcal{M}_{\mathrm{\Pi}}^{\mathcal{G}}$, we
have for any pair of vertices $\langle v,u\rangle\in E$ that

$val^{\mathcal{M}_{\mathrm{\Pi}}}_{\langle{\cdotp},v,u\rangle}\mathopen{}\mathclose{{}\left(\pi,\mathbb{O},\gamma}\right)=val^{\mathcal{M}_{\mathrm{\Pi}}^{\mathcal{G}}}_{\langle
v,u\rangle}\mathopen{}\mathclose{{}\left(\pi,\Diamond T,\gamma}\right),$

which yields the result.

######  Proof (of Theorem 5.3)

For the sake of readability, assume that the reset state in
$\mathcal{S}_{\mathrm{\Pi}}$ is a triplet of the form $\langle
s_{\text{reset}},v_{\text{reset}},v_{0}\rangle$ so that
$\mathcal{O}_{\ell\mathopen{}\mathclose{{}\left(v_{\text{reset}}}\right)}\mathopen{}\mathclose{{}\left(\langle
v_{\text{reset}},v_{0}\rangle}\right)=\left\\{s_{\text{reset}}\right\\}$. We
also may write $\phi\mathopen{}\mathclose{{}\left(\,\overline{\\!{s}}}\right)$
for $\phi_{R}\mathopen{}\mathclose{{}\left(\,\overline{\\!{s}}}\right)$ when
it is clear from the context that $\,\overline{\\!{s}}\in\mathcal{S}_{R}$. We
respectively denote the marginal stationary distribution of states and
directions by
$\xi_{\pi}\mathopen{}\mathclose{{}\left(s}\right)=\text{{E}}_{s^{\prime},v,u\sim\xi_{\pi}}\,\left[\mathds{1}\left\\{{s=s^{\prime}}\right\\}\right]$
and
$\xi_{\pi}\mathopen{}\mathclose{{}\left(d}\right)=\text{{E}}_{s,v,u\sim\xi_{\pi}}\,\left[\mathds{1}\left\\{{d=\langle
v,u\rangle}\right\\}\right]$. Furthermore, Given a direction $d\in E$, we
denote the conditional stationary distribution by

$\displaystyle\xi_{\pi}\mathopen{}\mathclose{{}\left(s,a\mid d}\right)$
$\displaystyle=\text{{E}}_{s^{\prime},v,u\sim\xi_{\pi}}\,\left[\mkern
1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern
1.5mu_{\ell\mathopen{}\mathclose{{}\left(v}\right),d}\mathopen{}\mathclose{{}\left(a\mid\phi\mathopen{}\mathclose{{}\left(s}\right)}\right)\cdot\mathds{1}\left\\{{s=s^{\prime}}\right\\}\mid\left\\{s,v,u\mid\langle
v,u\rangle=d\right\\}\right]$
$\displaystyle=\text{{E}}_{s^{\prime},v,u\sim\xi_{\pi}}\,\left[\mkern
1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern
1.5mu_{\ell\mathopen{}\mathclose{{}\left(v}\right),d}\mathopen{}\mathclose{{}\left(a\mid\phi\mathopen{}\mathclose{{}\left(s}\right)}\right)\cdot\mathds{1}\left\\{{s=s^{\prime}}\right\\}\frac{\mathds{1}\left\\{{d=\langle
v,u\rangle}\right\\}}{\xi_{\pi}\mathopen{}\mathclose{{}\left(v,u}\right)}\right]$

In the following, we also write
$\mathbf{P}\mathopen{}\mathclose{{}\left(s^{\prime}\mid s,a}\right)$ as
shorthand for $\mathbf{P}\mathopen{}\mathclose{{}\left(\langle
s^{\prime},v\rangle\mid\langle s,v\rangle,a}\right)$ (the transition function
of the explicit MDP of $\mathcal{H}$) if and only if
$s,s^{\prime}\in\mathcal{S}_{\ell\mathopen{}\mathclose{{}\left(v}\right)}$ and
$s\not\in\mathcal{O}_{\ell\mathopen{}\mathclose{{}\left(v}\right)}\mathopen{}\mathclose{{}\left(d}\right)$
for some $v\in V$, $d\in\textit{out}\mathopen{}\mathclose{{}\left(v}\right)$.
Then:

$\displaystyle L_{\mathbf{P}}^{\tau,\mathrm{\Pi}}$ $\displaystyle=$
$\displaystyle\ \frac{1}{2}\,\text{{E}}_{\langle
s,v,u\rangle,a\sim\xi_{\pi}}\,\left\|\phi\mathbf{P}_{\mathrm{\Pi}}\mathopen{}\mathclose{{}\left({\cdotp}\mid\langle
s,v,u\rangle,a}\right)-\mkern
1.5mu\overline{\mkern-1.5mu\mathbf{P}\mkern-1.5mu}\mkern
1.5mu_{\mathrm{\Pi}}\mathopen{}\mathclose{{}\left({\cdotp}\mid\langle\phi\mathopen{}\mathclose{{}\left(s}\right),v,u\rangle,a}\right)\right\|_{1}$
$\displaystyle=$ $\displaystyle\
\begin{multlined}\frac{1}{2}\,\text{{E}}_{s,v,u\sim\xi_{\pi}}\,\left[\mathds{1}\left\\{{s\neq
s_{\text{reset}}}\right\\}\,\mathds{1}\left\\{{s\not\in\mathcal{O}_{\ell\mathopen{}\mathclose{{}\left(v}\right)}\mathopen{}\mathclose{{}\left(\langle
v,u\rangle}\right)}\right\\}\right.\\\
\left\|\phi\mathbf{P}_{\mathrm{\Pi}}\mathopen{}\mathclose{{}\left({\cdotp}\mid\langle
s,v,u\rangle,*}\right)-\mkern
1.5mu\overline{\mkern-1.5mu\mathbf{P}\mkern-1.5mu}\mkern
1.5mu_{\mathrm{\Pi}}\mathopen{}\mathclose{{}\left({\cdotp}\mid\langle\phi\mathopen{}\mathclose{{}\left(s}\right),v,u\rangle,*}\right)\right\|_{1}\Bigg{]}\end{multlined}\frac{1}{2}\,\text{{E}}_{s,v,u\sim\xi_{\pi}}\,\left[\mathds{1}\left\\{{s\neq
s_{\text{reset}}}\right\\}\,\mathds{1}\left\\{{s\not\in\mathcal{O}_{\ell\mathopen{}\mathclose{{}\left(v}\right)}\mathopen{}\mathclose{{}\left(\langle
v,u\rangle}\right)}\right\\}\right.\\\
\left\|\phi\mathbf{P}_{\mathrm{\Pi}}\mathopen{}\mathclose{{}\left({\cdotp}\mid\langle
s,v,u\rangle,*}\right)-\mkern
1.5mu\overline{\mkern-1.5mu\mathbf{P}\mkern-1.5mu}\mkern
1.5mu_{\mathrm{\Pi}}\mathopen{}\mathclose{{}\left({\cdotp}\mid\langle\phi\mathopen{}\mathclose{{}\left(s}\right),v,u\rangle,*}\right)\right\|_{1}\Bigg{]}$
$\displaystyle\ \begin{multlined}+\frac{1}{2}\,\text{{E}}_{\langle
s,v,u\rangle,d^{\prime}\sim\xi_{\pi}}\,\Bigg{[}\mathds{1}\left\\{{s\neq
s_{\text{reset}}}\right\\}\,\mathds{1}\left\\{{s\in\mathcal{O}_{\ell\mathopen{}\mathclose{{}\left(v}\right)}\mathopen{}\mathclose{{}\left(\langle
v,u\rangle}\right)}\right\\}\\\
\left\|\phi\mathbf{P}_{\mathrm{\Pi}}\mathopen{}\mathclose{{}\left({\cdotp}\mid\langle
s,v,u\rangle,d^{\prime}}\right)-\mkern
1.5mu\overline{\mkern-1.5mu\mathbf{P}\mkern-1.5mu}\mkern
1.5mu_{\mathrm{\Pi}}\mathopen{}\mathclose{{}\left({\cdotp}\mid\langle\phi\mathopen{}\mathclose{{}\left(s}\right),v,u\rangle,d^{\prime}}\right)\right\|_{1}\Bigg{]}\end{multlined}+\frac{1}{2}\,\text{{E}}_{\langle
s,v,u\rangle,d^{\prime}\sim\xi_{\pi}}\,\Bigg{[}\mathds{1}\left\\{{s\neq
s_{\text{reset}}}\right\\}\,\mathds{1}\left\\{{s\in\mathcal{O}_{\ell\mathopen{}\mathclose{{}\left(v}\right)}\mathopen{}\mathclose{{}\left(\langle
v,u\rangle}\right)}\right\\}\\\
\left\|\phi\mathbf{P}_{\mathrm{\Pi}}\mathopen{}\mathclose{{}\left({\cdotp}\mid\langle
s,v,u\rangle,d^{\prime}}\right)-\mkern
1.5mu\overline{\mkern-1.5mu\mathbf{P}\mkern-1.5mu}\mkern
1.5mu_{\mathrm{\Pi}}\mathopen{}\mathclose{{}\left({\cdotp}\mid\langle\phi\mathopen{}\mathclose{{}\left(s}\right),v,u\rangle,d^{\prime}}\right)\right\|_{1}\Bigg{]}$
$\displaystyle\
+\frac{1}{2}\,\text{{E}}_{s,v,u\sim\xi_{\pi}}\,\left[\mathds{1}\left\\{{s=s_{\text{reset}}}\right\\}\,\left\|\phi\mathbf{P}_{\mathrm{\Pi}}\mathopen{}\mathclose{{}\left({\cdotp}\mid\langle
s,v,u\rangle,*}\right)-\mkern
1.5mu\overline{\mkern-1.5mu\mathbf{P}\mkern-1.5mu}\mkern
1.5mu_{\mathrm{\Pi}}\mathopen{}\mathclose{{}\left({\cdotp}\mid\langle\phi\mathopen{}\mathclose{{}\left(s}\right),v,u\rangle,*}\right)\right\|_{1}\right]$
($\pi$ is proper) $\displaystyle=$ $\displaystyle\
\begin{multlined}\frac{1}{2}\,\text{{E}}_{s,v,u\sim\xi_{\pi}}\,\left[\mathds{1}\left\\{{s\neq
s_{\text{reset}}}\right\\}\,\mathds{1}\left\\{{s\not\in\mathcal{O}_{\ell\mathopen{}\mathclose{{}\left(v}\right)}\mathopen{}\mathclose{{}\left(\langle
v,u\rangle}\right)}\right\\}\right.\\\ \left.\left\|\text{{E}}_{a\sim\mkern
1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern
1.5mu_{\ell\mathopen{}\mathclose{{}\left(v}\right),\langle
v,u\rangle}\mathopen{}\mathclose{{}\left({\cdotp}\mid\phi\mathopen{}\mathclose{{}\left(s}\right)}\right)}\,\bigg{[}\phi\mathbf{P}\mathopen{}\mathclose{{}\left({\cdotp}\mid
s,a}\right)-\mkern 1.5mu\overline{\mkern-1.5mu\mathbf{P}\mkern-1.5mu}\mkern
1.5mu\mathopen{}\mathclose{{}\left({\cdotp}\mid{\phi\mathopen{}\mathclose{{}\left(s}\right),a}}\right)\bigg{]}\right\|_{1}\right]\end{multlined}\frac{1}{2}\,\text{{E}}_{s,v,u\sim\xi_{\pi}}\,\left[\mathds{1}\left\\{{s\neq
s_{\text{reset}}}\right\\}\,\mathds{1}\left\\{{s\not\in\mathcal{O}_{\ell\mathopen{}\mathclose{{}\left(v}\right)}\mathopen{}\mathclose{{}\left(\langle
v,u\rangle}\right)}\right\\}\right.\\\ \left.\left\|\text{{E}}_{a\sim\mkern
1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern
1.5mu_{\ell\mathopen{}\mathclose{{}\left(v}\right),\langle
v,u\rangle}\mathopen{}\mathclose{{}\left({\cdotp}\mid\phi\mathopen{}\mathclose{{}\left(s}\right)}\right)}\,\bigg{[}\phi\mathbf{P}\mathopen{}\mathclose{{}\left({\cdotp}\mid
s,a}\right)-\mkern 1.5mu\overline{\mkern-1.5mu\mathbf{P}\mkern-1.5mu}\mkern
1.5mu\mathopen{}\mathclose{{}\left({\cdotp}\mid{\phi\mathopen{}\mathclose{{}\left(s}\right),a}}\right)\bigg{]}\right\|_{1}\right]$
(by definition of $\mathcal{M}_{\mathrm{\Pi}}$ (i)) $\displaystyle\
\begin{multlined}+\frac{1}{2}\,\text{{E}}_{\langle
s,v,u\rangle,d^{\prime}\sim\xi_{\pi}}\,\Bigg{[}\mathds{1}\left\\{{s\neq
s_{\text{reset}}}\right\\}\,\mathds{1}\left\\{{s\in\mathcal{O}_{\ell\mathopen{}\mathclose{{}\left(v}\right)}\mathopen{}\mathclose{{}\left(\langle
v,u\rangle}\right)}\right\\}\\\
\left\|\phi\mathcal{I}_{\ell\mathopen{}\mathclose{{}\left(u}\right)}\mathopen{}\mathclose{{}\left({\cdotp}\mid\langle
v,u\rangle}\right)-\overline{\mathcal{I}}_{\ell\mathopen{}\mathclose{{}\left(u}\right)}\mathopen{}\mathclose{{}\left({\cdotp}\mid\langle
v,u\rangle}\right)\right\|_{1}\Bigg{]}\end{multlined}+\frac{1}{2}\,\text{{E}}_{\langle
s,v,u\rangle,d^{\prime}\sim\xi_{\pi}}\,\Bigg{[}\mathds{1}\left\\{{s\neq
s_{\text{reset}}}\right\\}\,\mathds{1}\left\\{{s\in\mathcal{O}_{\ell\mathopen{}\mathclose{{}\left(v}\right)}\mathopen{}\mathclose{{}\left(\langle
v,u\rangle}\right)}\right\\}\\\
\left\|\phi\mathcal{I}_{\ell\mathopen{}\mathclose{{}\left(u}\right)}\mathopen{}\mathclose{{}\left({\cdotp}\mid\langle
v,u\rangle}\right)-\overline{\mathcal{I}}_{\ell\mathopen{}\mathclose{{}\left(u}\right)}\mathopen{}\mathclose{{}\left({\cdotp}\mid\langle
v,u\rangle}\right)\right\|_{1}\Bigg{]}$ (by definition of
$\mathcal{M}_{\mathrm{\Pi}}$ (ii)) $\displaystyle\
+\frac{1}{2}\,\text{{E}}_{s,v,u\sim\xi_{\pi}}\,\left[\mathds{1}\left\\{{s=s_{\text{reset}}}\right\\}\,\left\|\phi\mathcal{I}_{\ell\mathopen{}\mathclose{{}\left(v_{0}}\right)}\mathopen{}\mathclose{{}\left({\cdotp}\mid
d_{0}}\right)-\overline{\mathcal{I}}_{\ell\mathopen{}\mathclose{{}\left(v_{0}}\right)}\mathopen{}\mathclose{{}\left({\cdotp}\mid
d_{0}}\right)\right\|_{1}\right]$ (by definition of
$\mathcal{M}_{\mathrm{\Pi}}$ (iii)) $\displaystyle=$ $\displaystyle\
\begin{multlined}\frac{1}{2}\,\text{{E}}_{s,v,u\sim\xi_{\pi}}\,\left[\mathds{1}\left\\{{s\neq
s_{\text{reset}}}\right\\}\,\mathds{1}\left\\{{s\not\in\mathcal{O}_{\ell\mathopen{}\mathclose{{}\left(v}\right)}\mathopen{}\mathclose{{}\left(\langle
v,u\rangle}\right)}\right\\}\right.\\\ \left.\left\|\text{{E}}_{a\sim\mkern
1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern
1.5mu_{\ell\mathopen{}\mathclose{{}\left(v}\right),\langle
v,u\rangle}\mathopen{}\mathclose{{}\left({\cdotp}\mid\phi\mathopen{}\mathclose{{}\left(s}\right)}\right)}\,\bigg{[}\phi\mathbf{P}\mathopen{}\mathclose{{}\left({\cdotp}\mid
s,a}\right)-\mkern 1.5mu\overline{\mkern-1.5mu\mathbf{P}\mkern-1.5mu}\mkern
1.5mu\mathopen{}\mathclose{{}\left({\cdotp}\mid{\phi\mathopen{}\mathclose{{}\left(s}\right),a}}\right)\bigg{]}\right\|_{1}\right]\end{multlined}\frac{1}{2}\,\text{{E}}_{s,v,u\sim\xi_{\pi}}\,\left[\mathds{1}\left\\{{s\neq
s_{\text{reset}}}\right\\}\,\mathds{1}\left\\{{s\not\in\mathcal{O}_{\ell\mathopen{}\mathclose{{}\left(v}\right)}\mathopen{}\mathclose{{}\left(\langle
v,u\rangle}\right)}\right\\}\right.\\\ \left.\left\|\text{{E}}_{a\sim\mkern
1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern
1.5mu_{\ell\mathopen{}\mathclose{{}\left(v}\right),\langle
v,u\rangle}\mathopen{}\mathclose{{}\left({\cdotp}\mid\phi\mathopen{}\mathclose{{}\left(s}\right)}\right)}\,\bigg{[}\phi\mathbf{P}\mathopen{}\mathclose{{}\left({\cdotp}\mid
s,a}\right)-\mkern 1.5mu\overline{\mkern-1.5mu\mathbf{P}\mkern-1.5mu}\mkern
1.5mu\mathopen{}\mathclose{{}\left({\cdotp}\mid{\phi\mathopen{}\mathclose{{}\left(s}\right),a}}\right)\bigg{]}\right\|_{1}\right]$
$\displaystyle\
+\frac{1}{2}\,\text{{E}}_{R,d\sim\xi_{\pi}}\,\left\|\phi\mathcal{I}_{R}\mathopen{}\mathclose{{}\left({\cdotp}\mid
d}\right)-\overline{\mathcal{I}}_{R}\mathopen{}\mathclose{{}\left({\cdotp}\mid
d}\right)\right\|_{1}$ $\displaystyle=$ $\displaystyle\
\begin{multlined}\frac{1}{2}\,\text{{E}}_{s,v,u\sim\xi_{\pi}}\,\left[\mathds{1}\left\\{{s\neq
s_{\text{reset}}}\right\\}\,\mathds{1}\left\\{{s\not\in\mathcal{O}_{\ell\mathopen{}\mathclose{{}\left(v}\right)}\mathopen{}\mathclose{{}\left(\langle
v,u\rangle}\right)}\right\\}\right.\\\ \left.\left\|\text{{E}}_{a\sim\mkern
1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern
1.5mu_{\ell\mathopen{}\mathclose{{}\left(v}\right),\langle
v,u\rangle}\mathopen{}\mathclose{{}\left({\cdotp}\mid\phi\mathopen{}\mathclose{{}\left(s}\right)}\right)}\,\bigg{[}\phi\mathbf{P}\mathopen{}\mathclose{{}\left({\cdotp}\mid
s,a}\right)-\mkern 1.5mu\overline{\mkern-1.5mu\mathbf{P}\mkern-1.5mu}\mkern
1.5mu\mathopen{}\mathclose{{}\left({\cdotp}\mid{\phi\mathopen{}\mathclose{{}\left(s}\right),a}}\right)\bigg{]}\right\|_{1}\right]\end{multlined}\frac{1}{2}\,\text{{E}}_{s,v,u\sim\xi_{\pi}}\,\left[\mathds{1}\left\\{{s\neq
s_{\text{reset}}}\right\\}\,\mathds{1}\left\\{{s\not\in\mathcal{O}_{\ell\mathopen{}\mathclose{{}\left(v}\right)}\mathopen{}\mathclose{{}\left(\langle
v,u\rangle}\right)}\right\\}\right.\\\ \left.\left\|\text{{E}}_{a\sim\mkern
1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern
1.5mu_{\ell\mathopen{}\mathclose{{}\left(v}\right),\langle
v,u\rangle}\mathopen{}\mathclose{{}\left({\cdotp}\mid\phi\mathopen{}\mathclose{{}\left(s}\right)}\right)}\,\bigg{[}\phi\mathbf{P}\mathopen{}\mathclose{{}\left({\cdotp}\mid
s,a}\right)-\mkern 1.5mu\overline{\mkern-1.5mu\mathbf{P}\mkern-1.5mu}\mkern
1.5mu\mathopen{}\mathclose{{}\left({\cdotp}\mid{\phi\mathopen{}\mathclose{{}\left(s}\right),a}}\right)\bigg{]}\right\|_{1}\right]$
$\displaystyle\ +L_{\mathcal{I}}$ $\displaystyle\leq$ $\displaystyle\
\begin{multlined}\frac{1}{2}\,\text{{E}}_{s,v,u\sim\xi_{\pi}}\,\text{{E}}_{a\sim\mkern
1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern
1.5mu_{\ell\mathopen{}\mathclose{{}\left(v}\right),\langle
v,u\rangle}\mathopen{}\mathclose{{}\left({\cdotp}\mid\phi\mathopen{}\mathclose{{}\left(s}\right)}\right)}\,\left[\mathds{1}\left\\{{s\neq
s_{\text{reset}}}\right\\}\,\mathds{1}\left\\{{s\not\in\mathcal{O}_{\ell\mathopen{}\mathclose{{}\left(v}\right)}\mathopen{}\mathclose{{}\left(\langle
v,u\rangle}\right)}\right\\}\right.\\\
\left.\left\|\phi\mathbf{P}\mathopen{}\mathclose{{}\left({\cdotp}\mid
s,a}\right)-\mkern 1.5mu\overline{\mkern-1.5mu\mathbf{P}\mkern-1.5mu}\mkern
1.5mu\mathopen{}\mathclose{{}\left({\cdotp}\mid{\phi\mathopen{}\mathclose{{}\left(s}\right),a}}\right)\right\|_{1}\right]+L_{\mathcal{I}}\end{multlined}\frac{1}{2}\,\text{{E}}_{s,v,u\sim\xi_{\pi}}\,\text{{E}}_{a\sim\mkern
1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern
1.5mu_{\ell\mathopen{}\mathclose{{}\left(v}\right),\langle
v,u\rangle}\mathopen{}\mathclose{{}\left({\cdotp}\mid\phi\mathopen{}\mathclose{{}\left(s}\right)}\right)}\,\left[\mathds{1}\left\\{{s\neq
s_{\text{reset}}}\right\\}\,\mathds{1}\left\\{{s\not\in\mathcal{O}_{\ell\mathopen{}\mathclose{{}\left(v}\right)}\mathopen{}\mathclose{{}\left(\langle
v,u\rangle}\right)}\right\\}\right.\\\
\left.\left\|\phi\mathbf{P}\mathopen{}\mathclose{{}\left({\cdotp}\mid
s,a}\right)-\mkern 1.5mu\overline{\mkern-1.5mu\mathbf{P}\mkern-1.5mu}\mkern
1.5mu\mathopen{}\mathclose{{}\left({\cdotp}\mid{\phi\mathopen{}\mathclose{{}\left(s}\right),a}}\right)\right\|_{1}\right]+L_{\mathcal{I}}$
(Jensen’s inequality) $\displaystyle=$ $\displaystyle\
\begin{multlined}\frac{1}{2}\,\text{{E}}_{d\sim\xi_{\pi}}\,\text{{E}}_{s,a\sim\xi_{\pi}\mathopen{}\mathclose{{}\left({\cdotp}\mid
d}\right)}\,\left[\mathds{1}\left\\{{s\neq
s_{\text{reset}}}\right\\}\,\mathds{1}\left\\{{s\not\in\mathcal{O}_{\ell\mathopen{}\mathclose{{}\left(v}\right)}\mathopen{}\mathclose{{}\left({d}}\right)}\right\\}\right.\\\
\left.\left\|\phi\mathbf{P}\mathopen{}\mathclose{{}\left({\cdotp}\mid
s,a}\right)-\mkern 1.5mu\overline{\mkern-1.5mu\mathbf{P}\mkern-1.5mu}\mkern
1.5mu\mathopen{}\mathclose{{}\left({\cdotp}\mid{\phi\mathopen{}\mathclose{{}\left(s}\right),a}}\right)\right\|_{1}\right]+L_{\mathcal{I}}\end{multlined}\frac{1}{2}\,\text{{E}}_{d\sim\xi_{\pi}}\,\text{{E}}_{s,a\sim\xi_{\pi}\mathopen{}\mathclose{{}\left({\cdotp}\mid
d}\right)}\,\left[\mathds{1}\left\\{{s\neq
s_{\text{reset}}}\right\\}\,\mathds{1}\left\\{{s\not\in\mathcal{O}_{\ell\mathopen{}\mathclose{{}\left(v}\right)}\mathopen{}\mathclose{{}\left({d}}\right)}\right\\}\right.\\\
\left.\left\|\phi\mathbf{P}\mathopen{}\mathclose{{}\left({\cdotp}\mid
s,a}\right)-\mkern 1.5mu\overline{\mkern-1.5mu\mathbf{P}\mkern-1.5mu}\mkern
1.5mu\mathopen{}\mathclose{{}\left({\cdotp}\mid{\phi\mathopen{}\mathclose{{}\left(s}\right),a}}\right)\right\|_{1}\right]+L_{\mathcal{I}}$
($\star$)

Now, let $d=\langle v,u\rangle\in E$ be a _target direction_ for the room
$R=\ell\mathopen{}\mathclose{{}\left(v}\right)$. We consider the room $R$ as
an episodic MDP (cf. Assumption 1) where (i) the initial distribution
corresponds to the expected entrance probabilities in $R$: for any
$s\in\mathcal{S}_{R}$

$\mathbf{I}^{\pi}_{R}\mathopen{}\mathclose{{}\left(s}\right)=\text{{E}}_{\dot{s},\langle\dot{u},\dot{v}\rangle\sim\xi_{\pi}}\,\left[\mathcal{I}_{R}\mathopen{}\mathclose{{}\left(s\mid
d_{0}=\langle\dot{u},\dot{v}\rangle}\right)\mid\dot{s}\in\mathcal{O}_{\ell\mathopen{}\mathclose{{}\left(\dot{u}}\right)}\mathopen{}\mathclose{{}\left(\langle\dot{u},\dot{v}\rangle}\right)\text{
and }\dot{v}=v\right]$

(where $d_{0}$ is the direction from which $R$ is entered); and (ii) the room
is reset when an exit state in direction $d$ is visited: for any
$s,s^{\prime}\in\mathcal{S}_{R}$, $a\in\mathcal{A}_{R}$,

$\mathbf{P}^{d,\pi}_{R}\mathopen{}\mathclose{{}\left(s^{\prime}\mid\allowbreak
s,a}\right)=\begin{cases}1&\text{if $s^{\prime}=s_{\text{reset}}$ and
$s\in\mathcal{O}_{R}\mathopen{}\mathclose{{}\left(d}\right)$},\\\
\mathbf{I}^{\pi}_{R}\mathopen{}\mathclose{{}\left(s^{\prime}}\right)&\text{if
$s=s_{\text{reset}}$, and}\\\ \mathbf{P}_{R}(s^{\prime}\mid
s,a)&\text{otherwise.}\end{cases}$ (12)

We call the resulting MDP the _individual room_ version of $R$ that we denote
by $R_{d,\pi}$. The stationary distribution of the room $R_{d,\pi}$ for the
low-level policy $\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern
1.5mu_{R,d}$ is $\xi_{\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern
1.5mu_{R,d}}^{R_{d,\pi}}$. Observe that $\xi_{\mkern
1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu_{R,d}}^{R_{d,\pi}}$ is
over $\mathcal{S}_{R}$, which includes the reset state $s_{\text{reset}}$,
while $\xi_{\pi}\mathopen{}\mathclose{{}\left({\cdotp}\mid d}\right)$ is over
the exact same state space but without the reset state (since the reset state
is a special state outside $R$, shared by all the rooms in the hierarchical
model; cf. Assumption 2 and the definition of $\mathcal{M}_{\mathrm{\Pi}}$).

Figure 6: Room $R=\ell\mathopen{}\mathclose{{}\left(v}\right)$ in the
hierarchical model (left) and the same room taken individually (right). Both
distributions $\xi_{\pi}\mathopen{}\mathclose{{}\left({\cdotp}\mid d}\right)$
and $\xi_{\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern
1.5mu_{R,d}}^{R_{d,\pi}}$ correspond to the limiting distributions over
$\mathcal{S}_{R}$ when $\mkern
1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu_{R,d}$ is executed in
$R$. The sole difference remains in the fact that the reset is considered
outside $R$ in the hierarchical model (Assumption 2) while it is considered to
be part of the state space when $R$ is taken individually (Assumption 1).

Furthermore, notice that, modulo this reset state, the two distributions are
the same (see Fig. 6): they both consist of the limiting distribution over
$\mathcal{S}_{R}$ when $\mkern
1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu_{R,d}$ is executed in
$R$. All the transition distributions remain the same, except those of the
exit states: in the hierarchical model $\mathcal{H}$, every state
$s\in\mathcal{O}_{R}\mathopen{}\mathclose{{}\left(d}\right)$ transitions to
$u$ deterministically, while in the individual room $R_{d,\pi}$, they
transition to the reset state deterministically. Still, in both cases, $R$ is
entered and exited with the same probability (respectively from and to
$\mathopen{}\mathclose{{}\left(\mathcal{S}\setminus\mathcal{S}_{R}\times\left\\{v\right\\}}\right)$
in $\mathcal{H}$ and $s_{\text{reset}}$ in the individual room $R_{d,\pi}$).
Therefore, we have:

$\xi_{\pi}\mathopen{}\mathclose{{}\left(s\mid d}\right)=\xi_{\mkern
1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern
1.5mu_{R,d}}^{R_{d,\pi}}\mathopen{}\mathclose{{}\left(s\mid\mathcal{S}_{R}\setminus\left\\{s_{\text{reset}}\right\\}}\right)=\frac{\xi_{\mkern
1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern
1.5mu_{R,d}}^{R_{d,\pi}}\mathopen{}\mathclose{{}\left(s}\right)\mathds{1}\left\\{{s\neq
s_{\text{reset}}}\right\\}}{1-\xi_{\mkern
1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern
1.5mu_{R,d}}^{R_{d,\pi}}\mathopen{}\mathclose{{}\left(s_{\text{reset}}}\right)}.$
(13)

Instead of sampling from $\xi_{\pi}\mathopen{}\mathclose{{}\left(s\mid
d}\right)$ in Eq. $\star$ ‣ 0.C, we would rather like to sample from the
distribution of the individual room $\xi_{\mkern
1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern
1.5mu_{R,d}}^{R_{d,\pi}}\mathopen{}\mathclose{{}\left(s\mid\mathcal{S}_{R}\setminus\left\\{s_{\text{reset}}\right\\}}\right)$.
We have:

$\displaystyle\
\text{{E}}_{s,a\sim\xi_{\pi}\mathopen{}\mathclose{{}\left({\cdotp}\mid
d}\right)}\,\left[\mathds{1}\left\\{{s\neq
s_{\text{reset}}}\right\\}\,\mathds{1}\left\\{{s\not\in\mathcal{O}_{\ell\mathopen{}\mathclose{{}\left(v}\right)}\mathopen{}\mathclose{{}\left({d}}\right)}\right\\}\left\|\phi\mathbf{P}\mathopen{}\mathclose{{}\left({\cdotp}\mid
s,a}\right)-\mkern 1.5mu\overline{\mkern-1.5mu\mathbf{P}\mkern-1.5mu}\mkern
1.5mu\mathopen{}\mathclose{{}\left({\cdotp}\mid{\phi\mathopen{}\mathclose{{}\left(s}\right),a}}\right)\right\|_{1}\right]$
$\displaystyle=$ $\displaystyle\
\begin{multlined}\sum_{s\in\mathcal{S}}\sum_{a\in\mathcal{A}}\left[\xi_{\pi}\mathopen{}\mathclose{{}\left(s\mid
d}\right)\,\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern
1.5mu_{R,{d}}\mathopen{}\mathclose{{}\left(a\mid\phi\mathopen{}\mathclose{{}\left(s}\right)}\right)\,\right.\\\
\left.\mathds{1}\left\\{{s\neq
s_{\text{reset}}}\right\\}\,\mathds{1}\left\\{{s\not\in\mathcal{O}_{\ell\mathopen{}\mathclose{{}\left(v}\right)}\mathopen{}\mathclose{{}\left({d}}\right)}\right\\}\,\left\|\phi\mathbf{P}\mathopen{}\mathclose{{}\left({\cdotp}\mid
s,a}\right)-\mkern 1.5mu\overline{\mkern-1.5mu\mathbf{P}\mkern-1.5mu}\mkern
1.5mu\mathopen{}\mathclose{{}\left({\cdotp}\mid{\phi\mathopen{}\mathclose{{}\left(s}\right),a}}\right)\right\|_{1}\right]\end{multlined}\sum_{s\in\mathcal{S}}\sum_{a\in\mathcal{A}}\left[\xi_{\pi}\mathopen{}\mathclose{{}\left(s\mid
d}\right)\,\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern
1.5mu_{R,{d}}\mathopen{}\mathclose{{}\left(a\mid\phi\mathopen{}\mathclose{{}\left(s}\right)}\right)\,\right.\\\
\left.\mathds{1}\left\\{{s\neq
s_{\text{reset}}}\right\\}\,\mathds{1}\left\\{{s\not\in\mathcal{O}_{\ell\mathopen{}\mathclose{{}\left(v}\right)}\mathopen{}\mathclose{{}\left({d}}\right)}\right\\}\,\left\|\phi\mathbf{P}\mathopen{}\mathclose{{}\left({\cdotp}\mid
s,a}\right)-\mkern 1.5mu\overline{\mkern-1.5mu\mathbf{P}\mkern-1.5mu}\mkern
1.5mu\mathopen{}\mathclose{{}\left({\cdotp}\mid{\phi\mathopen{}\mathclose{{}\left(s}\right),a}}\right)\right\|_{1}\right]$
(16) $\displaystyle=$ $\displaystyle\
\begin{multlined}\sum_{s\in\mathcal{S}}\sum_{a\in\mathcal{A}}\left[\frac{\xi_{\mkern
1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern
1.5mu_{R,d}}^{R_{d,\pi}}\mathopen{}\mathclose{{}\left(s}\right)\mathds{1}\left\\{{s\neq
s_{\text{reset}}}\right\\}}{1-\xi_{\mkern
1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern
1.5mu_{R,d}}^{R_{d,\pi}}\mathopen{}\mathclose{{}\left(s_{\text{reset}}}\right)}\,\mkern
1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern
1.5mu_{R,{d}}\mathopen{}\mathclose{{}\left(a\mid\phi\mathopen{}\mathclose{{}\left(s}\right)}\right)\,\right.\\\
\left.\mathds{1}\left\\{{s\neq
s_{\text{reset}}}\right\\}\,\mathds{1}\left\\{{s\not\in\mathcal{O}_{\ell\mathopen{}\mathclose{{}\left(v}\right)}\mathopen{}\mathclose{{}\left({d}}\right)}\right\\}\,\left\|\phi\mathbf{P}_{R}\mathopen{}\mathclose{{}\left({\cdotp}\mid
s,a}\right)-\mkern 1.5mu\overline{\mkern-1.5mu\mathbf{P}\mkern-1.5mu}\mkern
1.5mu_{R}\mathopen{}\mathclose{{}\left({\cdotp}\mid{\phi\mathopen{}\mathclose{{}\left(s}\right),a}}\right)\right\|_{1}\right]\end{multlined}\sum_{s\in\mathcal{S}}\sum_{a\in\mathcal{A}}\left[\frac{\xi_{\mkern
1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern
1.5mu_{R,d}}^{R_{d,\pi}}\mathopen{}\mathclose{{}\left(s}\right)\mathds{1}\left\\{{s\neq
s_{\text{reset}}}\right\\}}{1-\xi_{\mkern
1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern
1.5mu_{R,d}}^{R_{d,\pi}}\mathopen{}\mathclose{{}\left(s_{\text{reset}}}\right)}\,\mkern
1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern
1.5mu_{R,{d}}\mathopen{}\mathclose{{}\left(a\mid\phi\mathopen{}\mathclose{{}\left(s}\right)}\right)\,\right.\\\
\left.\mathds{1}\left\\{{s\neq
s_{\text{reset}}}\right\\}\,\mathds{1}\left\\{{s\not\in\mathcal{O}_{\ell\mathopen{}\mathclose{{}\left(v}\right)}\mathopen{}\mathclose{{}\left({d}}\right)}\right\\}\,\left\|\phi\mathbf{P}_{R}\mathopen{}\mathclose{{}\left({\cdotp}\mid
s,a}\right)-\mkern 1.5mu\overline{\mkern-1.5mu\mathbf{P}\mkern-1.5mu}\mkern
1.5mu_{R}\mathopen{}\mathclose{{}\left({\cdotp}\mid{\phi\mathopen{}\mathclose{{}\left(s}\right),a}}\right)\right\|_{1}\right]$
(19) $\displaystyle=$ $\displaystyle\ \text{{E}}_{s,a\sim\xi_{\mkern
1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern
1.5mu_{R,d}}^{R_{d,\pi}}}\,\\!\\!\left[\frac{\mathds{1}\left\\{{s\neq
s_{\text{reset}}}\right\\}}{1-\xi_{\mkern
1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern
1.5mu_{R,d}}^{R_{d,\pi}}\mathopen{}\mathclose{{}\left(s_{\text{reset}}}\right)}\mathds{1}\left\\{{s\not\in\mathcal{O}_{\ell\mathopen{}\mathclose{{}\left(v}\right)}\mathopen{}\mathclose{{}\left({d}}\right)}\right\\}\left\|\phi\mathbf{P}_{R}\mathopen{}\mathclose{{}\left({\cdotp}\mid
s,a}\right)-\mkern 1.5mu\overline{\mkern-1.5mu\mathbf{P}\mkern-1.5mu}\mkern
1.5mu_{R}\mathopen{}\mathclose{{}\left({\cdotp}\mid{\phi\mathopen{}\mathclose{{}\left(s}\right),a}}\right)\right\|_{1}\right]$

Notice that we can pass from Eq. (16) to (19) because we only consider states
$s\neq s_{\text{reset}}$ and
$s\not\in\mathcal{O}_{\ell\mathopen{}\mathclose{{}\left(v}\right)}\mathopen{}\mathclose{{}\left(d}\right)$
that are the only ones for which
$\mathbf{P}\mathopen{}\mathclose{{}\left({\cdotp}\mid s,a}\right)$ differs
from $\mathbf{P}_{R}^{d,\pi}\mathopen{}\mathclose{{}\left({\cdotp}\mid
s,a}\right)$ (Eq. 12). Furthermore, in that case, we have
$\mathbf{P}_{R}^{d,\pi}\mathopen{}\mathclose{{}\left({\cdotp}\mid
s,a}\right)=\mathbf{P}_{R}\mathopen{}\mathclose{{}\left({\cdotp}\mid
s,a}\right)$. Then we have:

$\displaystyle\ \text{{E}}_{s,a\sim\xi_{\mkern
1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern
1.5mu_{R,d}}^{R_{d,\pi}}}\,\\!\\!\left[\frac{\mathds{1}\left\\{{s\neq
s_{\text{reset}}}\right\\}}{1-\xi_{\mkern
1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern
1.5mu_{R,d}}^{R_{d,\pi}}\mathopen{}\mathclose{{}\left(s_{\text{reset}}}\right)}\mathds{1}\left\\{{s\not\in\mathcal{O}_{\ell\mathopen{}\mathclose{{}\left(v}\right)}\mathopen{}\mathclose{{}\left({d}}\right)}\right\\}\left\|\phi\mathbf{P}_{R}\mathopen{}\mathclose{{}\left({\cdotp}\mid
s,a}\right)-\mkern 1.5mu\overline{\mkern-1.5mu\mathbf{P}\mkern-1.5mu}\mkern
1.5mu_{R}\mathopen{}\mathclose{{}\left({\cdotp}\mid{\phi\mathopen{}\mathclose{{}\left(s}\right),a}}\right)\right\|_{1}\right]$
$\displaystyle=$ $\displaystyle\ \text{{E}}_{s,a\sim\xi_{\mkern
1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern
1.5mu_{R,d}}^{R_{d,\pi}}}\,\\!\\!\left[\frac{\mathds{1}\left\\{{s\neq
s_{\text{reset}}}\right\\}}{1-\xi_{\mkern
1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern
1.5mu_{R,d}}^{R_{d,\pi}}\mathopen{}\mathclose{{}\left(s_{\text{reset}}}\right)}\left\|\phi\mathbf{P}_{R}^{d}\mathopen{}\mathclose{{}\left({\cdotp}\mid
s,a}\right)-\mkern 1.5mu\overline{\mkern-1.5mu\mathbf{P}\mkern-1.5mu}\mkern
1.5mu_{R}^{d}\mathopen{}\mathclose{{}\left({\cdotp}\mid{\phi\mathopen{}\mathclose{{}\left(s}\right),a}}\right)\right\|_{1}\right]$
(by definition of $\mathbf{P}_{R}^{d}$ and $\mkern
1.5mu\overline{\mkern-1.5mu\mathbf{P}\mkern-1.5mu}\mkern 1.5mu_{R}^{d}$)
$\displaystyle=$ $\displaystyle\ \frac{1}{1-\xi_{\mkern
1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern
1.5mu_{R,d}}^{R_{d,\pi}}\mathopen{}\mathclose{{}\left(s_{\text{reset}}}\right)}\text{{E}}_{s,a\sim\xi_{\mkern
1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern
1.5mu_{R,d}}^{R_{d,\pi}}}\,\left[\mathds{1}\left\\{{s\neq
s_{\text{reset}}}\right\\}\,\left\|\phi\mathbf{P}_{R}^{d}\mathopen{}\mathclose{{}\left({\cdotp}\mid
s,a}\right)-\mkern 1.5mu\overline{\mkern-1.5mu\mathbf{P}\mkern-1.5mu}\mkern
1.5mu_{R}^{d}\mathopen{}\mathclose{{}\left({\cdotp}\mid{\phi\mathopen{}\mathclose{{}\left(s}\right),a}}\right)\right\|_{1}\right]$
$\displaystyle\leq$ $\displaystyle\ \frac{1}{1-\xi_{\mkern
1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern
1.5mu_{R,d}}^{R_{d,\pi}}\mathopen{}\mathclose{{}\left(s_{\text{reset}}}\right)}\text{{E}}_{s,a\sim\xi_{\mkern
1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern
1.5mu_{R,d}}^{R_{d,\pi}}}\,\left\|\phi\mathbf{P}_{R}^{d}\mathopen{}\mathclose{{}\left({\cdotp}\mid
s,a}\right)-\mkern 1.5mu\overline{\mkern-1.5mu\mathbf{P}\mkern-1.5mu}\mkern
1.5mu_{R}^{d}\mathopen{}\mathclose{{}\left({\cdotp}\mid{\phi\mathopen{}\mathclose{{}\left(s}\right),a}}\right)\right\|_{1}$

Assuming that the projection of the BSCC of $\mathcal{M}_{\mathrm{\Pi}}$ under
$\pi$ to $\mathcal{S}_{R}$ is included in the BSCC of $R$ when it operates
under $\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu_{R,d}$,
we have that $\text{supp}\mathopen{}\mathclose{{}\left(\xi_{\mkern
1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern
1.5mu_{R,d}}^{R_{d,\pi}}}\right)\subseteq\text{supp}\mathopen{}\mathclose{{}\left(\xi_{\mkern
1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu_{R,d}}^{R}}\right)$,
where $\xi_{\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern
1.5mu_{R,d}}^{R}$ denotes the stationary distribution of the training room
$R_{d}$ under the latent policy $\mkern
1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu_{R,d}$. Then:

$\displaystyle\ \frac{1}{1-\xi_{\mkern
1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern
1.5mu_{R,d}}^{R_{d,\pi}}\mathopen{}\mathclose{{}\left(s_{\text{reset}}}\right)}\text{{E}}_{s,a\sim\xi_{\mkern
1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern
1.5mu_{R,d}}^{R_{d,\pi}}}\,\left\|\phi\mathbf{P}_{R}^{d}\mathopen{}\mathclose{{}\left({\cdotp}\mid
s,a}\right)-\mkern 1.5mu\overline{\mkern-1.5mu\mathbf{P}\mkern-1.5mu}\mkern
1.5mu_{R}^{d}\mathopen{}\mathclose{{}\left({\cdotp}\mid{\phi\mathopen{}\mathclose{{}\left(s}\right),a}}\right)\right\|_{1}$
$\displaystyle=$ $\displaystyle\ \begin{multlined}\frac{1}{1-\xi_{\mkern
1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern
1.5mu_{R,d}}^{R_{d,\pi}}\mathopen{}\mathclose{{}\left(s_{\text{reset}}}\right)}\sum_{s\in\text{supp}\mathopen{}\mathclose{{}\left(\xi_{\mkern
1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern
1.5mu_{R,d}}^{R_{d,\pi}}}\right)}\sum_{a\in\mathcal{A}_{R}}\left[\xi_{\mkern
1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern
1.5mu_{R,d}}^{R_{d,\pi}}\mathopen{}\mathclose{{}\left(s}\right)\,\mkern
1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern
1.5mu_{R,d}\mathopen{}\mathclose{{}\left(a\mid\phi\mathopen{}\mathclose{{}\left(s}\right)}\right)\right.\\\
\left.\left\|\phi\mathbf{P}_{R}^{d}\mathopen{}\mathclose{{}\left({\cdotp}\mid
s,a}\right)-\mkern 1.5mu\overline{\mkern-1.5mu\mathbf{P}\mkern-1.5mu}\mkern
1.5mu_{R}^{d}\mathopen{}\mathclose{{}\left({\cdotp}\mid{\phi\mathopen{}\mathclose{{}\left(s}\right),a}}\right)\right\|_{1}\right]\end{multlined}\frac{1}{1-\xi_{\mkern
1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern
1.5mu_{R,d}}^{R_{d,\pi}}\mathopen{}\mathclose{{}\left(s_{\text{reset}}}\right)}\sum_{s\in\text{supp}\mathopen{}\mathclose{{}\left(\xi_{\mkern
1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern
1.5mu_{R,d}}^{R_{d,\pi}}}\right)}\sum_{a\in\mathcal{A}_{R}}\left[\xi_{\mkern
1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern
1.5mu_{R,d}}^{R_{d,\pi}}\mathopen{}\mathclose{{}\left(s}\right)\,\mkern
1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern
1.5mu_{R,d}\mathopen{}\mathclose{{}\left(a\mid\phi\mathopen{}\mathclose{{}\left(s}\right)}\right)\right.\\\
\left.\left\|\phi\mathbf{P}_{R}^{d}\mathopen{}\mathclose{{}\left({\cdotp}\mid
s,a}\right)-\mkern 1.5mu\overline{\mkern-1.5mu\mathbf{P}\mkern-1.5mu}\mkern
1.5mu_{R}^{d}\mathopen{}\mathclose{{}\left({\cdotp}\mid{\phi\mathopen{}\mathclose{{}\left(s}\right),a}}\right)\right\|_{1}\right]$
$\displaystyle=$ $\displaystyle\ \begin{multlined}\frac{1}{1-\xi_{\mkern
1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern
1.5mu_{R,d}}^{R_{d,\pi}}\mathopen{}\mathclose{{}\left(s_{\text{reset}}}\right)}\sum_{s\in\text{supp}\mathopen{}\mathclose{{}\left(\xi_{\mkern
1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern
1.5mu_{R,d}}^{R}}\right)}\sum_{a\in\mathcal{A}_{R}}\left[\frac{\xi_{\mkern
1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern
1.5mu_{R,d}}^{R_{d,\pi}}\mathopen{}\mathclose{{}\left(s}\right)}{\xi_{\mkern
1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern
1.5mu_{R,d}}^{R}\mathopen{}\mathclose{{}\left(s}\right)}\,\xi_{\mkern
1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern
1.5mu_{R,d}}^{R}\mathopen{}\mathclose{{}\left(s}\right)\,\mkern
1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern
1.5mu_{R,d}\mathopen{}\mathclose{{}\left(a\mid\phi\mathopen{}\mathclose{{}\left(s}\right)}\right)\right.\\\
\left.\left\|\phi\mathbf{P}_{R}^{d}\mathopen{}\mathclose{{}\left({\cdotp}\mid
s,a}\right)-\mkern 1.5mu\overline{\mkern-1.5mu\mathbf{P}\mkern-1.5mu}\mkern
1.5mu_{R}^{d}\mathopen{}\mathclose{{}\left({\cdotp}\mid{\phi\mathopen{}\mathclose{{}\left(s}\right),a}}\right)\right\|_{1}\right]\end{multlined}\frac{1}{1-\xi_{\mkern
1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern
1.5mu_{R,d}}^{R_{d,\pi}}\mathopen{}\mathclose{{}\left(s_{\text{reset}}}\right)}\sum_{s\in\text{supp}\mathopen{}\mathclose{{}\left(\xi_{\mkern
1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern
1.5mu_{R,d}}^{R}}\right)}\sum_{a\in\mathcal{A}_{R}}\left[\frac{\xi_{\mkern
1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern
1.5mu_{R,d}}^{R_{d,\pi}}\mathopen{}\mathclose{{}\left(s}\right)}{\xi_{\mkern
1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern
1.5mu_{R,d}}^{R}\mathopen{}\mathclose{{}\left(s}\right)}\,\xi_{\mkern
1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern
1.5mu_{R,d}}^{R}\mathopen{}\mathclose{{}\left(s}\right)\,\mkern
1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern
1.5mu_{R,d}\mathopen{}\mathclose{{}\left(a\mid\phi\mathopen{}\mathclose{{}\left(s}\right)}\right)\right.\\\
\left.\left\|\phi\mathbf{P}_{R}^{d}\mathopen{}\mathclose{{}\left({\cdotp}\mid
s,a}\right)-\mkern 1.5mu\overline{\mkern-1.5mu\mathbf{P}\mkern-1.5mu}\mkern
1.5mu_{R}^{d}\mathopen{}\mathclose{{}\left({\cdotp}\mid{\phi\mathopen{}\mathclose{{}\left(s}\right),a}}\right)\right\|_{1}\right]$
$\displaystyle=$ $\displaystyle\ \frac{1}{1-\xi_{\mkern
1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern
1.5mu_{R,d}}^{R_{d,\pi}}\mathopen{}\mathclose{{}\left(s_{\text{reset}}}\right)}\text{{E}}_{s,a\sim\xi_{\mkern
1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern
1.5mu_{R,d}}^{R}}\,\left[\frac{\xi_{\mkern
1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern
1.5mu_{R,d}}^{R_{d,\pi}}\mathopen{}\mathclose{{}\left(s}\right)}{\xi_{\mkern
1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern
1.5mu_{R,d}}^{R}\mathopen{}\mathclose{{}\left(s}\right)}\,\left\|\phi\mathbf{P}_{R}^{d}\mathopen{}\mathclose{{}\left({\cdotp}\mid
s,a}\right)-\mkern 1.5mu\overline{\mkern-1.5mu\mathbf{P}\mkern-1.5mu}\mkern
1.5mu_{R}^{d}\mathopen{}\mathclose{{}\left({\cdotp}\mid{\phi\mathopen{}\mathclose{{}\left(s}\right),a}}\right)\right\|_{1}\right]$
$\displaystyle\leq$ $\displaystyle\ \begin{multlined}\frac{1}{1-\xi_{\mkern
1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern
1.5mu_{R,d}}^{R_{d,\pi}}\mathopen{}\mathclose{{}\left(s_{\text{reset}}}\right)}\text{{E}}_{s,a\sim\xi_{\mkern
1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern
1.5mu_{R,d}}^{R}}\,\left[\max_{s^{\prime}\in\text{supp}\mathopen{}\mathclose{{}\left(\xi_{\mkern
1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern
1.5mu_{R,d}}^{R}}\right)}\mathopen{}\mathclose{{}\left(\frac{\xi_{\mkern
1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern
1.5mu_{R,d}}^{R_{d,\pi}}\mathopen{}\mathclose{{}\left(s^{\prime}}\right)}{\xi_{\mkern
1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern
1.5mu_{R,d}}^{R}\mathopen{}\mathclose{{}\left(s^{\prime}}\right)}}\right)\right.\\\
\left.\left\|\phi\mathbf{P}_{R}^{d}\mathopen{}\mathclose{{}\left({\cdotp}\mid
s,a}\right)-\mkern 1.5mu\overline{\mkern-1.5mu\mathbf{P}\mkern-1.5mu}\mkern
1.5mu_{R}^{d}\mathopen{}\mathclose{{}\left({\cdotp}\mid{\phi\mathopen{}\mathclose{{}\left(s}\right),a}}\right)\right\|_{1}\right]\end{multlined}\frac{1}{1-\xi_{\mkern
1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern
1.5mu_{R,d}}^{R_{d,\pi}}\mathopen{}\mathclose{{}\left(s_{\text{reset}}}\right)}\text{{E}}_{s,a\sim\xi_{\mkern
1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern
1.5mu_{R,d}}^{R}}\,\left[\max_{s^{\prime}\in\text{supp}\mathopen{}\mathclose{{}\left(\xi_{\mkern
1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern
1.5mu_{R,d}}^{R}}\right)}\mathopen{}\mathclose{{}\left(\frac{\xi_{\mkern
1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern
1.5mu_{R,d}}^{R_{d,\pi}}\mathopen{}\mathclose{{}\left(s^{\prime}}\right)}{\xi_{\mkern
1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern
1.5mu_{R,d}}^{R}\mathopen{}\mathclose{{}\left(s^{\prime}}\right)}}\right)\right.\\\
\left.\left\|\phi\mathbf{P}_{R}^{d}\mathopen{}\mathclose{{}\left({\cdotp}\mid
s,a}\right)-\mkern 1.5mu\overline{\mkern-1.5mu\mathbf{P}\mkern-1.5mu}\mkern
1.5mu_{R}^{d}\mathopen{}\mathclose{{}\left({\cdotp}\mid{\phi\mathopen{}\mathclose{{}\left(s}\right),a}}\right)\right\|_{1}\right]$
$\displaystyle=$ $\displaystyle\ \begin{multlined}\frac{1}{1-\xi_{\mkern
1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern
1.5mu_{R,d}}^{R_{d,\pi}}\mathopen{}\mathclose{{}\left(s_{\text{reset}}}\right)}\max_{s\in\text{supp}\mathopen{}\mathclose{{}\left(\xi_{\mkern
1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern
1.5mu_{R,d}}^{R}}\right)}\mathopen{}\mathclose{{}\left(\frac{\xi_{\mkern
1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern
1.5mu_{R,d}}^{R_{d,\pi}}\mathopen{}\mathclose{{}\left(s}\right)}{\xi_{\mkern
1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern
1.5mu_{R,d}}^{R}\mathopen{}\mathclose{{}\left(s}\right)}}\right)\\\
\text{{E}}_{s,a\sim\xi_{\mkern
1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern
1.5mu_{R,d}}^{R}}\,\left[\left\|\phi\mathbf{P}_{R}^{d}\mathopen{}\mathclose{{}\left({\cdotp}\mid
s,a}\right)-\mkern 1.5mu\overline{\mkern-1.5mu\mathbf{P}\mkern-1.5mu}\mkern
1.5mu_{R}^{d}\mathopen{}\mathclose{{}\left({\cdotp}\mid{\phi\mathopen{}\mathclose{{}\left(s}\right),a}}\right)\right\|_{1}\right]\end{multlined}\frac{1}{1-\xi_{\mkern
1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern
1.5mu_{R,d}}^{R_{d,\pi}}\mathopen{}\mathclose{{}\left(s_{\text{reset}}}\right)}\max_{s\in\text{supp}\mathopen{}\mathclose{{}\left(\xi_{\mkern
1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern
1.5mu_{R,d}}^{R}}\right)}\mathopen{}\mathclose{{}\left(\frac{\xi_{\mkern
1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern
1.5mu_{R,d}}^{R_{d,\pi}}\mathopen{}\mathclose{{}\left(s}\right)}{\xi_{\mkern
1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern
1.5mu_{R,d}}^{R}\mathopen{}\mathclose{{}\left(s}\right)}}\right)\\\
\text{{E}}_{s,a\sim\xi_{\mkern
1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern
1.5mu_{R,d}}^{R}}\,\left[\left\|\phi\mathbf{P}_{R}^{d}\mathopen{}\mathclose{{}\left({\cdotp}\mid
s,a}\right)-\mkern 1.5mu\overline{\mkern-1.5mu\mathbf{P}\mkern-1.5mu}\mkern
1.5mu_{R}^{d}\mathopen{}\mathclose{{}\left({\cdotp}\mid{\phi\mathopen{}\mathclose{{}\left(s}\right),a}}\right)\right\|_{1}\right]$
$\displaystyle=$ $\displaystyle\
\max_{s\in\text{supp}\mathopen{}\mathclose{{}\left(\xi_{\mkern
1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern
1.5mu_{R,d}}^{R}}\right)}\mathopen{}\mathclose{{}\left(\frac{\xi_{\mkern
1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern
1.5mu_{R,d}}^{R_{d,\pi}}\mathopen{}\mathclose{{}\left(s}\right)}{\xi_{\mkern
1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern
1.5mu_{R,d}}^{R}\mathopen{}\mathclose{{}\left(s}\right)}}\right)\frac{2L_{\mathbf{P}}^{R,d}}{1-\xi_{\mkern
1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern
1.5mu_{R,d}}^{R_{d,\pi}}\mathopen{}\mathclose{{}\left(s_{\text{reset}}}\right)}$

If the initial distributions of the individual $R_{d,\pi}$ and the training
room $R_{d}$ have the same support, then the projection and the BSCCs coincide
since the same set of states is eventually visited under $\mkern
1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu$ from states of
$\text{supp}\mathopen{}\mathclose{{}\left(\mathbf{I}_{R}}\right)=\text{supp}\mathopen{}\mathclose{{}\left(\mathbf{I}_{R}^{\pi}}\right)$.
Furthermore, by [45, Theorem 1], we have

$\displaystyle\ \max_{s\in\text{supp}\mathopen{}\mathclose{{}\left(\xi_{\mkern
1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern
1.5mu_{R,d}}^{R}}\right)}\mathopen{}\mathclose{{}\left(\frac{\xi_{\mkern
1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern
1.5mu_{R,d}}^{R_{d,\pi}}\mathopen{}\mathclose{{}\left(s}\right)}{\xi_{\mkern
1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern
1.5mu_{R,d}}^{R}\mathopen{}\mathclose{{}\left(s}\right)}}\right)$ (20)
$\displaystyle\leq$ $\displaystyle\
\max_{s\in\text{supp}\mathopen{}\mathclose{{}\left(\xi_{\mkern
1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern
1.5mu_{R,d}}^{R}}\right)}\max\left\\{\frac{\xi_{\mkern
1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern
1.5mu_{R,d}}^{R_{d,\pi}}\mathopen{}\mathclose{{}\left(s}\right)}{\xi_{\mkern
1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern
1.5mu_{R,d}}^{R}\mathopen{}\mathclose{{}\left(s}\right)},\frac{\xi_{\mkern
1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern
1.5mu_{R,d}}^{R}\mathopen{}\mathclose{{}\left(s}\right)}{\xi_{\mkern
1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern
1.5mu_{R,d}}^{R_{d,\pi}}\mathopen{}\mathclose{{}\left(s}\right)}\right\\}$
$\displaystyle\leq$ $\displaystyle\
\mathopen{}\mathclose{{}\left(\max_{s\in\text{supp}\mathopen{}\mathclose{{}\left(\mathbf{I}_{R}}\right)}\max\left\\{\frac{\mathbf{I}_{R}^{\pi}\mathopen{}\mathclose{{}\left(s}\right)}{\mathbf{I}_{R}\mathopen{}\mathclose{{}\left(s}\right)},\frac{\mathbf{I}_{R}\mathopen{}\mathclose{{}\left(s}\right)}{\mathbf{I}_{R}^{\pi}\mathopen{}\mathclose{{}\left(s}\right)}\right\\}}\right)^{\left|\mathcal{S}\right|}$
(cf. Eq. 12) $\displaystyle=$ $\displaystyle\ \kappa_{R,d};$ (21)

otherwise, we set $\kappa_{R,d}$ to
$\max_{s\in\text{supp}\mathopen{}\mathclose{{}\left(\xi_{\mkern
1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern
1.5mu_{R,d}}^{R}}\right)}\mathopen{}\mathclose{{}\left(\frac{\xi_{\mkern
1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern
1.5mu_{R,d}}^{R_{d,\pi}}\mathopen{}\mathclose{{}\left(s}\right)}{\xi_{\mkern
1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern
1.5mu_{R,d}}^{R}\mathopen{}\mathclose{{}\left(s}\right)}}\right)$. Moreover,
let $\mathcal{S}_{R,d}=\left\\{\langle
s,v,u\rangle\in\mathcal{S}_{\mathrm{\Pi}}\mid\ell\mathopen{}\mathclose{{}\left(v}\right)=R\text{
and }\langle v,u\rangle=d\right\\}$ and define

$\xi_{\pi}\mathopen{}\mathclose{{}\left(s_{\text{reset}}\mid
R,d}\right)=\text{{E}}_{\langle
s,v,u\rangle,a\sim\xi_{\pi}}\,\left[\mathbf{P}_{\mathrm{\Pi}}\mathopen{}\mathclose{{}\left(s_{\text{reset}}\mid\langle
s,v,u\rangle,a}\right)\mid\mathcal{S}_{R,d}\right].$

Notice that

$\displaystyle\xi_{\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern
1.5mu_{R,d}}^{R_{d,\pi}}\mathopen{}\mathclose{{}\left(s_{\text{reset}}}\right)$
$\displaystyle=\text{{E}}_{\langle
s,v,u\rangle,a\sim\xi_{\pi}}\,\left[\mathbf{P}_{\mathrm{\Pi}}\mathopen{}\mathclose{{}\left(s_{\text{reset}}\mid\langle
s,v,u\rangle,a}\right)+\mathds{1}\left\\{{s\in\mathcal{O}_{R}\mathopen{}\mathclose{{}\left(d}\right)}\right\\}\mid\mathcal{S}_{R,d}\right]$
$\displaystyle=\xi_{\pi}\mathopen{}\mathclose{{}\left(s_{\text{reset}}\mid{R,d}}\right)+\xi_{\pi}\mathopen{}\mathclose{{}\left(\mathcal{O}_{R}\mathopen{}\mathclose{{}\left(d}\right)\times\left\\{d\right\\}\mid\mathcal{S}_{R,d}}\right)$

by definition of $\mathbf{P}_{R}^{d,\pi}$ (cf. Eq. 12 and Fig. 6), the fact
that the probability of exiting the room is equal to the probability of
visiting an exit state, and the fact that resetting the room and visiting an
exit state are disjoint events (when an exit state is visited, it always
transitions to the next room, never to the reset state).

By putting all together, we have

$\displaystyle\ L_{\mathbf{P}}^{\tau,\mathrm{\Pi}}$ $\displaystyle\leq$
$\displaystyle\
\begin{multlined}L_{\mathcal{I}}+\frac{1}{2}\,\text{{E}}_{d\sim\xi_{\pi}}\,\text{{E}}_{s,a\sim\xi_{\pi}\mathopen{}\mathclose{{}\left({\cdotp}\mid
d}\right)}\,\left[\mathds{1}\left\\{{s\neq
s_{\text{reset}}}\right\\}\,\mathds{1}\left\\{{s\not\in\mathcal{O}_{\ell\mathopen{}\mathclose{{}\left(v}\right)}\mathopen{}\mathclose{{}\left({d}}\right)}\right\\}\right.\\\
\left.\left\|\phi\mathbf{P}\mathopen{}\mathclose{{}\left({\cdotp}\mid
s,a}\right)-\mkern 1.5mu\overline{\mkern-1.5mu\mathbf{P}\mkern-1.5mu}\mkern
1.5mu\mathopen{}\mathclose{{}\left({\cdotp}\mid{\phi\mathopen{}\mathclose{{}\left(s}\right),a}}\right)\right\|_{1}\right]\end{multlined}L_{\mathcal{I}}+\frac{1}{2}\,\text{{E}}_{d\sim\xi_{\pi}}\,\text{{E}}_{s,a\sim\xi_{\pi}\mathopen{}\mathclose{{}\left({\cdotp}\mid
d}\right)}\,\left[\mathds{1}\left\\{{s\neq
s_{\text{reset}}}\right\\}\,\mathds{1}\left\\{{s\not\in\mathcal{O}_{\ell\mathopen{}\mathclose{{}\left(v}\right)}\mathopen{}\mathclose{{}\left({d}}\right)}\right\\}\right.\\\
\left.\left\|\phi\mathbf{P}\mathopen{}\mathclose{{}\left({\cdotp}\mid
s,a}\right)-\mkern 1.5mu\overline{\mkern-1.5mu\mathbf{P}\mkern-1.5mu}\mkern
1.5mu\mathopen{}\mathclose{{}\left({\cdotp}\mid{\phi\mathopen{}\mathclose{{}\left(s}\right),a}}\right)\right\|_{1}\right]$
$\displaystyle\leq$ $\displaystyle\
L_{\mathcal{I}}+\text{{E}}_{R,d\sim\xi_{\pi}}\,\frac{\kappa_{R,d}L_{\mathbf{P}}^{R,d}}{1-\xi_{\mkern
1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern
1.5mu_{R,d}}^{R_{d,\pi}}\mathopen{}\mathclose{{}\left(s_{\text{reset}}}\right)}$
$\displaystyle=$ $\displaystyle\
L_{\mathcal{I}}+\text{{E}}_{R,d\sim\xi_{\pi}}\,\frac{\kappa_{R,d}L_{\mathbf{P}}^{R,d}}{1-\xi_{\pi}\mathopen{}\mathclose{{}\left(s_{\text{reset}}\mid{R,d}}\right)-\xi_{\pi}\mathopen{}\mathclose{{}\left(\mathcal{O}_{R}\mathopen{}\mathclose{{}\left(d}\right)\times\left\\{d\right\\}\mid\mathcal{S}_{R,d}}\right)}$
$\displaystyle\leq$ $\displaystyle\
\begin{multlined}L_{\mathcal{I}}+\text{{E}}_{R,d\sim\xi_{\pi}}\,\\\
\frac{\max\left\\{{\kappa_{R^{\star},d^{\star}}}\colon
R^{\star}\in\mathcal{R},d^{\star}\in
D_{R^{\star}}\right\\}\,L_{\mathbf{P}}^{R,d}}{1-\max_{R^{\star}\in\mathcal{R},d^{\star}\in
D_{R}}\mathopen{}\mathclose{{}\left(\xi_{\pi}\mathopen{}\mathclose{{}\left(s_{\text{reset}}\mid{R^{\star},d^{\star}}}\right)+\xi_{\pi}\mathopen{}\mathclose{{}\left(\mathcal{O}_{R^{\star}}\mathopen{}\mathclose{{}\left(d^{\star}}\right)\times\left\\{d^{\star}\right\\}\mid\mathcal{S}_{R^{\star},d^{\star}}}\right)}\right)}\end{multlined}L_{\mathcal{I}}+\text{{E}}_{R,d\sim\xi_{\pi}}\,\\\
\frac{\max\left\\{{\kappa_{R^{\star},d^{\star}}}\colon
R^{\star}\in\mathcal{R},d^{\star}\in
D_{R^{\star}}\right\\}\,L_{\mathbf{P}}^{R,d}}{1-\max_{R^{\star}\in\mathcal{R},d^{\star}\in
D_{R}}\mathopen{}\mathclose{{}\left(\xi_{\pi}\mathopen{}\mathclose{{}\left(s_{\text{reset}}\mid{R^{\star},d^{\star}}}\right)+\xi_{\pi}\mathopen{}\mathclose{{}\left(\mathcal{O}_{R^{\star}}\mathopen{}\mathclose{{}\left(d^{\star}}\right)\times\left\\{d^{\star}\right\\}\mid\mathcal{S}_{R^{\star},d^{\star}}}\right)}\right)}$
$\displaystyle\leq$ $\displaystyle\
L_{\mathcal{I}}^{\mathrm{\Pi}}+\frac{\kappa}{\xi_{\text{continue}}^{\min}}\,\text{{E}}_{R,d\sim\xi_{\pi}}\,{L_{\mathbf{P}}^{R,d}}$

where $\kappa=\max\left\\{{\kappa_{R^{\star},d^{\star}}}\colon
R^{\star}\in\mathcal{R},d^{\star}\in D_{R^{\star}}\right\\}$ and

$\xi_{\text{continue}}^{\min}=1-\max_{R\in\mathcal{R},d\in
D_{R}}\mathopen{}\mathclose{{}\left(\xi_{\pi}\mathopen{}\mathclose{{}\left(s_{\text{reset}}\mid{R,d}}\right)+\xi_{\pi}\mathopen{}\mathclose{{}\left(\mathcal{O}_{R}\mathopen{}\mathclose{{}\left(d}\right)\times\left\\{d\right\\}\mid\mathcal{S}_{R,d}}\right)}\right).$
(22)

This concludes the proof.

(a) Goal reached per episode.

(b) Failures (adversaries hit) per episode.

Figure 7: A more detailed version of Fig. 4, where the WAE-DQN performance is
specified per direction.

##  Appendix 0.D Experiments

In this Section, we give additional information on the setting used during our
experiments.

#### Grid world.

Figure 8 represents a $3\times 3$ grid environment where each room is composed
of $20\times 20$ cells.

Figure 8: Environment for $N=9$ rooms of $20\times 20$ cells. The agent is
depicted in yellow (top left), adversaries in red, power-ups as cherries, and
the goal at the bottom right.

#### Hyperparameter search.

To train our WAE-DQN agent, we ran $4$ environments in parallel per training
instance and used a replay buffer of capacity $7.5\cdot 10^{5}$. We performed
a grid search to find the best parameters for our WAE-DQN algorithm. Table 3
presents the range of hyperparameters used. In particular, we found that
prioritized experience replay [50] and a categorical $Q$-network [14] did not
significantly improve the results in our specific environment. We used a batch
size of $128$ for the WAE-MDP.

For synthesizing the high-level controller, we used the hyperparameters that
worked the best for each specific direction. We used the same parameters for
the DQN training instances shown in Fig. 4. Additionally, with Fig. 7 we
provide a more detailed version of the figure, showing the results of each
latent policy for each specific direction.

Table 3: Hyperparameter range used for (WAE-)DQN. Parameters in green worked
best on average. For details about the WAE-MDP parameters, see [18].

Parameter | Value
---|---
Common to DQN and WAE-DQN
Activation | $\left\\{\text{\color[rgb]{0.1953125,0.8046875,0.1953125}\definecolor[named]{pgfstrokecolor}{rgb}{0.1953125,0.8046875,0.1953125}ReLU},\text{\color[rgb]{0.1953125,0.8046875,0.1953125}\definecolor[named]{pgfstrokecolor}{rgb}{0.1953125,0.8046875,0.1953125}leaky ReLu},\text{ELU},{\tanh},\text{sigmoid}\right\\}$
# Hidden layers per network | $\left\\{1,2,{\color[rgb]{0.1953125,0.8046875,0.1953125}\definecolor[named]{pgfstrokecolor}{rgb}{0.1953125,0.8046875,0.1953125}3}\right\\}$
# Neurons per layer | $\left\\{{\color[rgb]{0.1953125,0.8046875,0.1953125}\definecolor[named]{pgfstrokecolor}{rgb}{0.1953125,0.8046875,0.1953125}128},256,{512}\right\\}$
CNN filters ($3$ layers) | $\left\\{{3\to 5\to 7},{3\to 3\to 3}\right\\}$
CNN kernels ($3$ layers) | $\left\\{{32\to 64\to 16},{64\to 32\to 16}\right\\}$
DQN
Use Boltzmann exploration | $\left\\{\text{\color[rgb]{0.1953125,0.8046875,0.1953125}\definecolor[named]{pgfstrokecolor}{rgb}{0.1953125,0.8046875,0.1953125}Yes},\text{No}\right\\}$
Boltzmann temperature | $\left\\{0.25,0.10,{\color[rgb]{0.1953125,0.8046875,0.1953125}\definecolor[named]{pgfstrokecolor}{rgb}{0.1953125,0.8046875,0.1953125}0.75},{\color[rgb]{0.1953125,0.8046875,0.1953125}\definecolor[named]{pgfstrokecolor}{rgb}{0.1953125,0.8046875,0.1953125}1},{\color[rgb]{0.1953125,0.8046875,0.1953125}\definecolor[named]{pgfstrokecolor}{rgb}{0.1953125,0.8046875,0.1953125}10},100\right\\}$
Use $\epsilon$-greedy exploration (decay to $\epsilon=0.1$) | $\left\\{\text{Yes},\text{\color[rgb]{0.1953125,0.8046875,0.1953125}\definecolor[named]{pgfstrokecolor}{rgb}{0.1953125,0.8046875,0.1953125}No}\right\\}$
Target update period | $\left\\{{\color[rgb]{0.1953125,0.8046875,0.1953125}\definecolor[named]{pgfstrokecolor}{rgb}{0.1953125,0.8046875,0.1953125}1},{\color[rgb]{0.1953125,0.8046875,0.1953125}\definecolor[named]{pgfstrokecolor}{rgb}{0.1953125,0.8046875,0.1953125}250},500,1000\right\\}$
Target update scale ($\alpha$ in Algorithm 1) | $\left\\{{\color[rgb]{0.1953125,0.8046875,0.1953125}\definecolor[named]{pgfstrokecolor}{rgb}{0.1953125,0.8046875,0.1953125}10^{-4}},5\cdot 10^{-4},{\color[rgb]{0.1953125,0.8046875,0.1953125}\definecolor[named]{pgfstrokecolor}{rgb}{0.1953125,0.8046875,0.1953125}10^{-3}},5\cdot 10^{-3}\right\\}$
Reward scaling | $\left\\{1,10,25,{\color[rgb]{0.1953125,0.8046875,0.1953125}\definecolor[named]{pgfstrokecolor}{rgb}{0.1953125,0.8046875,0.1953125}100}\right\\}$
Learning rate | $\left\\{{\color[rgb]{0.1953125,0.8046875,0.1953125}\definecolor[named]{pgfstrokecolor}{rgb}{0.1953125,0.8046875,0.1953125}6.25\cdot 10^{-5}},{10}^{-4},2.5\cdot 10^{-4},10^{-3}\right\\}$
Batch size | $\left\\{32,{\color[rgb]{0.1953125,0.8046875,0.1953125}\definecolor[named]{pgfstrokecolor}{rgb}{0.1953125,0.8046875,0.1953125}64},128\right\\}$
Use double $Q$-networks [27] | $\left\\{\text{\color[rgb]{0.1953125,0.8046875,0.1953125}\definecolor[named]{pgfstrokecolor}{rgb}{0.1953125,0.8046875,0.1953125}Yes},\text{No}\right\\}$
WAE-MDP
Latent state size (power of $2$) | $\left\\{12,{\color[rgb]{0.1953125,0.8046875,0.1953125}\definecolor[named]{pgfstrokecolor}{rgb}{0.1953125,0.8046875,0.1953125}13},14,15\right\\}$
State embedding function temperature | $\left\\{{\color[rgb]{0.1953125,0.8046875,0.1953125}\definecolor[named]{pgfstrokecolor}{rgb}{0.1953125,0.8046875,0.1953125}\nicefrac{{1}}{{3}}},\nicefrac{{1}}{{2}},\nicefrac{{2}}{{3}},\nicefrac{{3}}{{4}},0.99\right\\}$
Transition function temperature | $\left\\{{\color[rgb]{0.1953125,0.8046875,0.1953125}\definecolor[named]{pgfstrokecolor}{rgb}{0.1953125,0.8046875,0.1953125}\nicefrac{{1}}{{3}}},\nicefrac{{1}}{{2}},\nicefrac{{2}}{{3}},\nicefrac{{3}}{{4}},0.99\right\\}$
Steady-state regularizer scale factor | $\left\\{10,25,{\color[rgb]{0.1953125,0.8046875,0.1953125}\definecolor[named]{pgfstrokecolor}{rgb}{0.1953125,0.8046875,0.1953125}50},75\right\\}$
Transition regularizer scale factor | $\left\\{10,25,{\color[rgb]{0.1953125,0.8046875,0.1953125}\definecolor[named]{pgfstrokecolor}{rgb}{0.1953125,0.8046875,0.1953125}50},75\right\\}$
Minimizer learning rate | $\left\\{{\color[rgb]{0.1953125,0.8046875,0.1953125}\definecolor[named]{pgfstrokecolor}{rgb}{0.1953125,0.8046875,0.1953125}10^{-4}},5\cdot 10^{-4},{\color[rgb]{0.1953125,0.8046875,0.1953125}\definecolor[named]{pgfstrokecolor}{rgb}{0.1953125,0.8046875,0.1953125}10^{-3}}\right\\}$
Maximizer learning rate | $\left\\{{\color[rgb]{0.1953125,0.8046875,0.1953125}\definecolor[named]{pgfstrokecolor}{rgb}{0.1953125,0.8046875,0.1953125}10^{-4}},5\cdot 10^{-4},10^{-3}\right\\}$
State embedding function learning rate | $\left\\{{\color[rgb]{0.1953125,0.8046875,0.1953125}\definecolor[named]{pgfstrokecolor}{rgb}{0.1953125,0.8046875,0.1953125}10^{-4}},5\cdot 10^{-4},10^{-3}\right\\}$
# critic updates | $\left\\{{\color[rgb]{0.1953125,0.8046875,0.1953125}\definecolor[named]{pgfstrokecolor}{rgb}{0.1953125,0.8046875,0.1953125}5},10,15\right\\}$
State reconstruction function | $\left\\{{\color[rgb]{0.1953125,0.8046875,0.1953125}\definecolor[named]{pgfstrokecolor}{rgb}{0.1953125,0.8046875,0.1953125}L_{2}},\text{binary cross entropy (for $\mathbf{M}$)}\right\\}$

The MADE used to model the latent entrance function was trained on a dataset
of size $25600$, and the training was split into $100$ epochs (i.e., the model
performed $100$ passes through the entire dataset) with a learning rate of
$10^{-3}$. We used a batch size of $32$ or $64$, and two hidden layers, either
with $64$ or $128$ neurons.