2\gamma H\cdot\sum_{i=1}^{d_{\rm
s}}\sum_{k=1}^{\underline{k}_{i}}[c^{k}_{h}]_{i}\leq 4d_{\rm s}\gamma H.$
(E.17)

Here, the first inequality uses Lemma F.6, which provides an upper bound
$2\gamma H$ for each $[b^{k}_{h}]_{i}$. Recall that $[b^{k}_{h}]_{i}$ is
defined in (E.13). Also, the second inequality uses the fact

$\displaystyle\sum_{k=1}^{\underline{k}_{i}}[c^{k}_{h}]_{i}=[c^{\underline{k}_{i}}_{h}]_{i}+\sum_{k=1}^{\underline{k}_{i}-1}[c^{k}_{h}]_{i}\leq
1+1\leq 2,$

which is by the definition of $\underline{k}_{i}$ in (E.15) and the fact
$[c^{\underline{k}_{i}}_{h}]_{i}\leq 1$ since
$c^{\underline{k}_{i}}_{h}\in\Delta([d_{\rm s}])$. In the sequel, we
characterize the second summation term on the right-hand side of (E.16). For
any $i\in[d_{\rm s}]$ and $k\geq\underline{k}_{i}+1$, we have

$\displaystyle[b^{k}_{h}]_{i}\cdot[c^{k}_{h}]_{i}$
$\displaystyle\leq\mathbb{E}_{\theta^{*},\overline{\pi}_{k}}[e^{k}_{h+1}(\bm{s}_{h})]\cdot\frac{[b^{k}_{h}]_{i}\cdot[c^{k}_{h}]_{i}}{[b^{k}_{h}]_{i}\cdot[\overline{c}^{k}_{h}]_{i}}$
(E.18)
$\displaystyle=\bigl{(}k\cdot\mathbb{E}_{\theta^{*},\overline{\pi}_{k}}[e^{k}_{h+1}(\bm{s}_{h})]\bigr{)}\cdot\frac{[c^{k}_{h}]_{i}}{\sum_{j=0}^{k-1}[c^{j}_{h}]_{i}}$
$\displaystyle\leq\bigl{(}\max_{j\in[K]}\ell\cdot\mathbb{E}_{\theta^{*},\overline{\pi}_{\ell}}[e^{\ell}_{h+1}(\bm{s}_{h})]\bigr{)}\cdot\frac{[c^{k}_{h}]_{i}}{\sum_{j=1}^{k-1}[c^{j}_{h}]_{i}},$

where the first inequality is by (E.14) and the second inequality uses the
fact $[c^{j}_{h}]_{0}\geq 0$. Note that for any $(i,k)$ specified above, we
have

$\displaystyle\frac{[c^{k}_{h}]_{i}}{\sum_{j=0}^{k-1}[c^{j}_{h}]_{i}}\in[0,1]$

since it holds that $[c^{k}_{h}]_{i}\in[0,1]$ and
$\sum_{j=0}^{k-1}[c^{j}_{h}]_{i}\geq 1$ by the definition of
$\underline{k}_{i}$. Then, by applying the inequality $x\leq 2\log(1+x)$ for
any $x\in[0,1]$, we have

$\displaystyle\frac{[c^{k}_{h}]_{i}}{\sum_{j=1}^{k-1}[c^{j}_{h}]_{i}}\leq
2\log\Bigl{(}1+\frac{[c^{k}_{h}]_{i}}{\sum_{j=1}^{k-1}[c^{j}_{h}]_{i}}\Bigr{)}=2\log\sum_{j=1}^{k}[c^{j}_{h}]_{i}-2\log\sum_{j=1}^{k-1}[c^{j}_{h}]_{i}$
(E.19)

Combining (E.18) and (E.19), we obtain

$\displaystyle\sum_{i=1}^{d_{\rm
s}}\sum_{k=\underline{k}_{i}+1}^{K}[b^{k}_{h}]_{i}\cdot[c^{k}_{h}]_{i}$
$\displaystyle\leq\bigl{(}\max_{\ell\in[K]}\ell\cdot\mathbb{E}_{\theta^{*},\overline{\pi}_{\ell}}[e^{\ell}_{h+1}(\bm{s}_{h})]\bigr{)}\cdot\sum_{i=1}^{d_{\rm
s}}\sum_{k=\underline{k}_{i}+1}^{K}\bigl{(}2\log\sum_{j=1}^{k}[c^{j}_{h}]_{i}-2\log\sum_{j=1}^{k-1}[c^{j}_{h}]_{i}\bigr{)}$
$\displaystyle=2\bigl{(}\max_{\ell\in[K]}\ell\cdot\mathbb{E}_{\theta^{*},\overline{\pi}_{\ell}}[e^{\ell}_{h+1}(\bm{s}_{h})]\bigr{)}\cdot\sum_{i=1}^{d_{\rm
s}}\bigl{(}\log\sum_{j=1}^{K}[c^{j}_{h}]_{i}-\log\sum_{j=1}^{\underline{k}_{i}}[c^{j}_{h}]_{i}\bigr{)}$
$\displaystyle\leq
2\bigl{(}\max_{\ell\in[K]}\ell\cdot\mathbb{E}_{\theta^{*},\overline{\pi}_{\ell}}[e^{\ell}_{h+1}(\bm{s}_{h})]\bigr{)}\cdot
d_{\rm s}\cdot\log K.$ (E.20)

Plugging (E.17) and (E.3) into the right-hand side of (E.16), we obtain

$\displaystyle\sum_{k=1}^{K}\mathbb{E}_{\theta^{*},\pi_{k}}[e^{k}_{h+1}(\bm{s}_{h})]\leq
4d_{\rm s}\gamma
H+2\bigl{(}\max_{\ell\in[K]}\ell\cdot\mathbb{E}_{\theta^{*},\overline{\pi}_{\ell}}[e^{\ell}_{h+1}(\bm{s}_{h})]\bigr{)}\cdot
d_{\rm s}\cdot\log K,$

which concludes the proof of Lemma 4.4. ∎

##  Appendix F Auxiliary Lemmas

In this section, we present (the proofs for) the auxiliary lemmas invoked in
previous sections.

###  F.1 Proof of Lemma E.1

###### Proof.

To see that $\widehat{\rho}$ defined in (E.4) is the projection, we consider
the minimization problem

$\displaystyle\min_{\rho^{\prime}\in{\rm linspan}(\\{\phi_{i}\\}_{i=1}^{d_{\rm
o}})}\|\mathbb{K}\rho^{\prime}-\mathbb{K}\rho\|_{\mathcal{H}}^{2}$ (F.1)

for any $\rho\in\Delta(\mathcal{O}^{3})$. Note that the objective can be
written as

$\displaystyle\|\mathbb{K}\rho^{\prime}-\mathbb{K}\rho\|_{\mathcal{H}}^{2}$
$\displaystyle\quad=\langle\mathbb{K}\rho^{\prime},\mathbb{K}\rho^{\prime}\rangle_{\mathcal{H}}-2\cdot\langle\mathbb{K}\rho^{\prime},\mathbb{K}\rho\rangle_{\mathcal{H}}+\langle\mathbb{K}\rho,\mathbb{K}\rho^{\prime}\rangle_{\mathcal{H}}$
$\displaystyle\quad=\mathbb{E}_{X\sim\rho^{\prime},Y\sim\rho^{\prime}}[{\mathcal{K}}(X,Y)]-2\cdot\mathbb{E}_{X\sim\rho^{\prime},Y\sim\rho}[{\mathcal{K}}(X,Y)]+\mathbb{E}_{X\sim\rho,Y\sim\rho}[{\mathcal{K}}(X,Y)].$
(F.2)

Since we have $\rho^{\prime}\in{\rm linspan}(\\{\phi_{i}\\}_{i=1}^{d_{\rm
o}})$, there exists $w=(w_{1},\ldots,w_{d_{\rm
o}})^{\top}\in\mathbb{R}^{d_{\rm o}}$ such that

$\displaystyle\rho^{\prime}(x)=\sum_{j\in[d_{\rm
o}]}w_{j}\cdot\phi_{j}(x),\quad\text{for any $x\in\mathcal{O}^{3}$.}$

By the above form of $\rho^{\prime}$ and the definition of the matrix $G$ in
(3.17), we can further rewrite the right-hand side of (F.1) to obtain

$\displaystyle\|\mathbb{K}\rho^{\prime}-\mathbb{K}\rho\|_{\mathcal{H}}^{2}=w^{\top}Gw-2\cdot\sum_{i=1}^{d_{\rm
o}}w_{i}\cdot\mathbb{E}_{X\sim\phi_{i},Y\sim\rho}[{\mathcal{K}}(X,Y)]+\mathbb{E}_{X\sim\rho,Y\sim\rho}[{\mathcal{K}}(X,Y)]$
(F.3)

Plugging (F.3) into (F.1) and solving the obtained quadratic programming
problem, we see that $\widehat{\rho}$ defined in (E.4) is the projection of
$\rho$.

By the definition of $\mathbb{S}$ in (3.18), we have

$\displaystyle\mathbb{E}_{X\sim\rho}[(\mathbb{S}f)(X)]=\sum_{i,j\in[d_{\rm
o}]}[G^{-1}]_{i,j}\cdot\mathbb{E}_{X\sim\rho,Y\sim\phi_{i},Y^{\prime}\sim\phi_{j}}\bigl{[}{\mathcal{K}}(X,Y)\cdot
f(Y^{\prime})\bigr{]},$ (F.4)

where $X,Y,Y^{\prime}$ are independent variables in $\mathcal{O}^{3}$. By
reorganizing terms in the summation, we can further write the right-hand side
of (F.4) as

$\displaystyle\sum_{i,j\in[d_{\rm o}]}[G^{-1}]_{i,j}\cdot\mathbb{E}_{X\sim
p,Y\sim\phi_{i},Y^{\prime}\sim\phi_{j}}\bigl{[}{\mathcal{K}}(X,Y)\cdot
f(Y^{\prime})\bigr{]}$ $\displaystyle\quad=\sum_{j\in[d_{\rm
o}]}\mathbb{E}_{Y^{\prime}\sim\phi_{j}}[f(Y^{\prime})]\cdot\sum_{i\in[d_{\rm
o}]}[G^{-1}]_{i,j}\cdot\mathbb{E}_{X\sim p,Y\sim\phi_{i}}[{\mathcal{K}}(X,Y)]$
$\displaystyle\quad=\int_{\mathcal{O}}f(x)\cdot\sum_{j\in[d_{\rm
o}]}\phi_{j}(x)\cdot\sum_{i\in[d_{\rm o}]}[G^{-1}]_{i,j}\cdot\mathbb{E}_{X\sim
p,Y\sim\phi_{i}}[{\mathcal{K}}(X,Y)]{\,\mathrm{d}}x,$

combining which with the definition of $\widehat{\rho}$ in (E.4), we conclude
the proof of Lemma E.1. ∎

###  F.2 Proof of Lemma E.2

###### Proof.

For any $(k,h,a,a^{\prime})\in[K]\times[2,\ldots,H]\times\mathcal{A}^{2}$, let
$w^{k}_{h,a,a^{\prime}}\in\mathbb{R}^{d_{\rm o}}$ be the vector such that

$\displaystyle\rho^{\overline{\pi}_{k}}_{h,a,a^{\prime}}(o_{h-1},o_{h},o_{h+1})=\sum_{j\in[d_{\rm
o}]}\phi_{i}(o_{h-1},o_{h},o_{h+1})\cdot[w^{k}_{h,a,a^{\prime}}]_{j},$ (F.5)

for any $o_{h-1},o_{h},o_{h+1}\in\mathcal{O}$, where
$\\{\phi_{i}\\}_{i=1}^{d_{\rm o}}$ are distribution functions defined in
Assumption 2.1 and the existence of $w^{k}_{h,a,a^{\prime}}$ is guaranteed by
the assumption therein. Also, recall that we define
$\widehat{w}^{k}_{h,a,a^{\prime}}\in\mathbb{R}^{d_{\rm o}}$ in (E.5) and we
have

$\displaystyle\widehat{\rho}^{k}_{h,a,a^{\prime}}(o_{h-1},o_{h},o_{h+1})=\sum_{j\in[d_{\rm
o}]}\phi_{j}(o_{h-1},o_{h},o_{h+1})\cdot[\widehat{w}^{k}_{h,a,a^{\prime}}]_{j}.$
(F.6)

For notational simplicity, we denote $\phi=(\phi_{1},\ldots,\phi_{d_{\rm o}})$
and write $\rho^{k}_{h,a,a^{\prime}}$ in short for
$\rho^{\overline{\pi}_{k}}_{h,a,a^{\prime}}$. Then, we can rewrite (F.5) and
(F.6) as

$\displaystyle\rho^{k}_{h,a,a^{\prime}}(\cdot)=\phi(\cdot)^{\top}w^{k}_{h,a,a^{\prime}},\quad\widehat{\rho}^{k}_{h,a,a^{\prime}}(\cdot)=\phi(\cdot)^{\top}\widehat{w}^{k}_{h,a,a^{\prime}}.$

Following the above definitions, we have

$\displaystyle\|\widehat{\rho}^{k}_{h,a,a^{\prime}}-\rho^{k}_{h,a,a^{\prime}}\|_{1}$
(F.7)
$\displaystyle\quad=\int_{\mathcal{O}^{3}}|\phi(o_{h-1},o_{h},o_{h+1})^{\top}(\widehat{w}^{k}_{h,a,a^{\prime}}-w^{k}_{h,a,a^{\prime}})|{\,\mathrm{d}}o_{h-1}{\,\mathrm{d}}o_{h}{\,\mathrm{d}}o_{h+1}$
$\displaystyle\quad\leq\int_{\mathcal{O}^{3}}\|\phi(o_{h-1},o_{h},o_{h+1})\|_{2}\cdot\|\widehat{w}^{k}_{h,a,a^{\prime}}-w^{k}_{h,a,a^{\prime}}\|_{2}{\,\mathrm{d}}o_{h-1}{\,\mathrm{d}}o_{h}{\,\mathrm{d}}o_{h+1}$
$\displaystyle\quad\leq d_{\rm
o}\cdot\|\widehat{w}^{k}_{h,a,a^{\prime}}-w^{k}_{h,a,a^{\prime}}\|_{2},$

where the first inequality is by the Cauchy-Schwarz inequality and the last
inequality uses

$\displaystyle\int_{\mathcal{O}^{3}}\|\phi(o_{h-1},o_{h},o_{h+1})\|_{2}{\,\mathrm{d}}o_{h-1}{\,\mathrm{d}}o_{h}{\,\mathrm{d}}o_{h+1}$
$\displaystyle\quad\leq\int_{\mathcal{O}^{3}}\|\phi(o_{h-1},o_{h},o_{h+1})\|_{1}{\,\mathrm{d}}o_{h-1}{\,\mathrm{d}}o_{h}{\,\mathrm{d}}o_{h+1}$
$\displaystyle\quad=\sum_{j=1}^{d_{\rm
o}}\int_{\mathcal{O}^{3}}\phi_{j}(o_{h-1},o_{h},o_{h+1}){\,\mathrm{d}}o_{h-1}{\,\mathrm{d}}o_{h}{\,\mathrm{d}}o_{h+1}=d_{\rm
o},$

as $\\{\phi_{i}\\}_{i=1}^{d_{\rm o}}$ are distribution functions over
$\mathcal{O}^{3}$. Thus, to upper bound
$\|\widehat{\rho}^{k}_{h,a,a^{\prime}}-\rho^{k}_{h,a,a^{\prime}}\|_{1}$, it
suffices to upper bound
$\|\widehat{w}^{k}_{h,a,a^{\prime}}-w^{k}_{h,a,a^{\prime}}\|_{2}$.

To this end, we define the vector $U^{k}_{h,a,a^{\prime}}\in\mathbb{R}^{d_{\rm
o}}$ by

$\displaystyle[U^{k}_{h,a,a^{\prime}}]_{i}=\mathbb{E}_{X\sim\phi_{i},Y\sim\widehat{{\mathcal{D}}}^{k}_{h,a,a^{\prime}}}[{\mathcal{K}}(X,Y)],$
(F.8)

where $\widehat{{\mathcal{D}}}^{k}_{h,a,a^{\prime}}$ is the empirical
distribution over $\mathcal{O}^{3}$ induced by the dataset
${\mathcal{D}}^{k}_{h,a,a^{\prime}}$. Then, we can rewrite the definition of
$\widehat{w}^{k}_{h,a,a^{\prime}}$ in (E.5) as

$\displaystyle\widehat{w}^{k}_{h,a,a^{\prime}}=G^{-1}U^{k}_{h,a,a^{\prime}},$

where the matrix $G\in\mathbb{R}^{d_{\rm o}\times d_{\rm o}}$ is defined in
(3.17). Then, we can write

$\displaystyle\|\widehat{w}^{k}_{h,a,a^{\prime}}-w^{k}_{h,a,a^{\prime}}\|_{2}=\|G^{-1}U^{k}_{h,a,a^{\prime}}-G^{-1}Gw^{k}_{h,a,a^{\prime}}\|_{2}\leq
1/\alpha\cdot\|U^{k}_{h,a,a^{\prime}}-Gw^{k}_{h,a,a^{\prime}}\|_{2}.$ (F.9)

Moreover, by the definition of $G$ in (3.17), we have

$\displaystyle[Gw^{k}_{h,a,a^{\prime}}]_{i}$ $\displaystyle=\sum_{j\in[d_{\rm
o}]}[G]_{i,j}\cdot[w^{k}_{h,a,a^{\prime}}]_{j}$ (F.10)
$\displaystyle=\sum_{j\in[d_{\rm
o}]}\mathbb{E}_{X\sim\phi_{i},Y\sim\phi_{j}}[{\mathcal{K}}(X,Y)]\cdot[w^{k}_{h,a,a^{\prime}}]_{j}$
$\displaystyle=\int_{\mathcal{O}^{3}\times\mathcal{O}^{3}}\phi_{i}(x)\cdot{\mathcal{K}}(x,y)\cdot\sum_{j\in[d_{\rm
o}]}\phi_{j}(y)\cdot[w^{k}_{h,a,a^{\prime}}]_{j}{\,\mathrm{d}}x{\,\mathrm{d}}y,$

By the definition of $w^{k}_{h,a,a^{\prime}}$ in (F.5), we can write (F.10) as

$\displaystyle[Gw^{k}_{h,a,a^{\prime}}]_{i}=\int_{\mathcal{O}^{3}\times\mathcal{O}^{3}}\phi_{i}(x)\cdot{\mathcal{K}}(x,y)\cdot\rho^{k}_{h,a,a^{\prime}}(y){\,\mathrm{d}}x{\,\mathrm{d}}y=\mathbb{E}_{X\sim\phi_{i},Y\sim\rho^{k}_{h,a,a^{\prime}}}[{\mathcal{K}}(X,Y)]$
(F.11)

Using the notation of the RKHS $\mathcal{H}$, we can further rewrite (F.8) and
(F.11) as

$\displaystyle[U^{k}_{h,a,a^{\prime}}]_{i}=\langle\mathbb{K}\phi_{i},\mathbb{K}\widehat{{\mathcal{D}}}^{k}_{h,a,a^{\prime}}\rangle_{\mathcal{H}},\quad[Gw^{k}_{h,a,a^{\prime}}]_{i}=\langle\mathbb{K}\phi_{i},\mathbb{K}\rho^{k}_{h,a,a^{\prime}}\rangle_{\mathcal{H}}.$

Recall that $\mathbb{K}$ is defined in (3.16). Therefore, using the Cauchy-
Schwarz inequality for the inner product in $\mathcal{H}$, we have

$\displaystyle\|U^{k}_{h,a,a^{\prime}}-Gw^{k}_{h,a,a^{\prime}}\|^{2}_{2}$
$\displaystyle=\sum_{i\in[d_{\rm
o}]}\bigl{(}\langle\mathbb{K}\phi_{i},\mathbb{K}\widehat{{\mathcal{D}}}^{k}_{h,a,a^{\prime}}-\mathbb{K}\rho^{k}_{h,a,a^{\prime}}\rangle_{\mathcal{H}}\bigr{)}^{2}$
(F.12) $\displaystyle\leq\sum_{i\in[d_{\rm
o}]}\|\mathbb{K}\phi_{i}\|^{2}_{\mathcal{H}}\cdot\|\mathbb{K}\widehat{{\mathcal{D}}}^{k}_{h,a,a^{\prime}}-\mathbb{K}\rho^{k}_{h,a,a^{\prime}}\|^{2}_{\mathcal{H}}.$

Since ${\mathcal{K}}$ is uniformly bounded by 1 as specified in Assumption
3.4, we have

$\displaystyle\|\mathbb{K}\phi_{i}\|_{\mathcal{H}}^{2}=\mathbb{E}_{X\sim\phi_{i},Y\sim\phi_{i}}[{\mathcal{K}}(X,Y)]\leq
1.$ (F.13)

In the sequel, we characterize
$\|\mathbb{K}\widehat{{\mathcal{D}}}^{k}_{h,a,a^{\prime}}-\mathbb{K}\rho^{k}_{h,a,a^{\prime}}\|_{\mathcal{H}}$
on the right-hand side of (F.12) for any fixed
$(h,a,a^{\prime})\in\\{2,\ldots,H\\}\times\mathcal{A}^{2}$. For notational
simplicity, we denote by $Y_{j}$ the data point that is added to
${\mathcal{D}}_{h,a,a^{\prime}}$ in the $j$-th iteration of Algorithm 1. In
other words, we have

$\displaystyle{\mathcal{D}}^{k}_{h,a,a^{\prime}}=\\{Y_{1},\ldots,Y_{k}\\},\quad\text{for
any $k\in[K]$.}$

Then, the random function process $\\{\mathcal{M}_{j}\\}_{j\geq 1}$ defined by

$\displaystyle\mathcal{M}_{j}(\cdot)=(1/k)\cdot\Bigl{(}\sum_{i=1}^{\min\\{j,k\\}}{\mathcal{K}}(Y_{i},\cdot)-\sum_{i=1}^{\min\\{j,k\\}}(\mathbb{K}\rho^{\pi_{i-1}}_{h,a,a^{\prime}})(\cdot)\Bigr{)}$
(F.14)

is a martingale in $\mathcal{H}$ adapted to the data filtration
$\\{\mathcal{U}_{j}\\}_{j\geq 0}$ of Algorithm 1. In detail, for any
$j\in[K]$, we have that $\mathcal{U}_{j}$ contains the information of all data
collected in the first $j$ iterations of Algorithm 1. Note that the data point
$Y_{j}$ follows from the distribution $\rho^{\pi_{j-1}}_{h,a,a^{\prime}}$
conditioning on $\mathcal{U}_{j-1}$. Therefore, we have

$\displaystyle\mathbb{E}[{\mathcal{K}}(Y_{j},x)-(\mathbb{K}\rho^{\pi_{j-1}}_{h,a,a^{\prime}})(x)\,|\,\mathcal{U}_{j-1}]=\mathbb{E}[{\mathcal{K}}(Y_{j},x)\,|\,\mathcal{U}_{j-1}]-\mathbb{E}_{Y\sim\rho^{\pi_{j-1}}_{h,a,a^{\prime}}}[{\mathcal{K}}(Y,x)]=0,$

for any fixed $x\in\mathcal{O}^{3}$, which implies that
$\\{\mathcal{M}_{j}\\}_{j\geq 1}$ defined above is a martingale. Moreover, we
have that the total quadratic variation of $\\{\mathcal{M}_{j}\\}_{j\geq 1}$
is upper bounded by

$\displaystyle\sum_{i=1}^{k}(1/k^{2})\cdot\|{\mathcal{K}}(Y_{i},\cdot)-(\mathbb{K}\rho^{\pi_{i}}_{h,a,a^{\prime}})(\cdot)\|^{2}_{\mathcal{H}}\leq\sum_{i=1}^{k}(1/k^{2})\cdot
4=4/k,$

where the inequality uses the fact

$\displaystyle\|{\mathcal{K}}(Y_{i},\cdot)-(\mathbb{K}\rho^{\pi_{i}}_{h,a,a^{\prime}})(\cdot)\|^{2}_{\mathcal{H}}$
$\displaystyle\quad={\mathcal{K}}(Y_{i},Y_{i})+\mathbb{E}_{Y\sim\rho^{\pi_{i}}_{h,a,a^{\prime}},Y^{\prime}\sim\rho^{\pi_{i}}_{h,a,a^{\prime}}}[{\mathcal{K}}(Y,Y^{\prime})]-2\cdot\mathbb{E}_{Y\sim\rho^{\pi_{i}}_{h,a,a^{\prime}}}[{\mathcal{K}}(Y_{i},Y)]\leq
4$

following the same argument of (F.13). Then, invoking Lemma F.7 with

$\displaystyle
c^{2}=4/k\quad\text{and}\quad\varepsilon=\sqrt{8\log(2KHA^{2}/\delta)}\cdot
k^{-1/2}$

for any $\delta>0$, with probability at least $1-\delta/(KHA^{2})$, it holds
that

$\displaystyle\|\mathcal{M}_{k}\|_{\mathcal{H}}=\|\mathbb{K}\widehat{{\mathcal{D}}}^{k}_{h,a,a^{\prime}}-\mathbb{K}\rho^{k}_{h,a,a^{\prime}}\|_{\mathcal{H}}\leq\sqrt{8\log(2KHA^{2}/\delta)}\cdot
k^{-1/2}.$ (F.15)

Here, the equality uses the definition of
$\rho^{k}_{h,a,a^{\prime}}=\rho^{\overline{\pi}_{k}}_{h,a,a^{\prime}}$. Recall
that $\overline{\pi}_{k}$ is the mixing policy that uniformly selects a policy
from $\\{\pi_{0},\ldots,\pi_{k-1}\\}$ at random, which implies

$\displaystyle\rho^{k}_{h,a,a^{\prime}}=\frac{1}{k}\sum_{i=0}^{k-1}\rho^{\pi_{i}}_{h,a,a^{\prime}}\quad\text{and}\quad\mathbb{K}\rho^{k}_{h,a,a^{\prime}}=\frac{1}{k}\sum_{i=0}^{k-1}\mathbb{K}\rho^{\pi_{i}}_{h,a,a^{\prime}}.$

Then, by further applying the union bound, we have that, with probability at
least $1-\delta$, the inequality in (F.15) holds for any
$(k,h,a,a^{\prime})\in[K]\times\\{2,\ldots,H\\}\times\mathcal{A}^{2}$.
Combining such an upper bound with (F.9), (F.12) and (F.13), we have

$\displaystyle\|\widehat{w}^{k}_{h,a,a^{\prime}}-w^{k}_{h,a,a^{\prime}}\|_{2}\leq
d^{1/2}_{\rm o}/\alpha\cdot\sqrt{8\log(2KHA^{2}/\delta)}\cdot k^{-1/2}.$
(F.16)

Combining (F.7) and (F.16), we know that, for any $\delta>0$, we have

$\displaystyle\|\widehat{\rho}^{k}_{h,a,a^{\prime}}-\rho^{k}_{h,a,a^{\prime}}\|_{1}\leq
d_{\rm o}^{3/2}/\alpha\cdot\sqrt{8\log(2KHA^{2}/\delta)}\cdot k^{-1/2},$

for any $(k,h,a,a^{\prime})\in[K]\times\\{2,\ldots,H\\}\times\mathcal{A}^{2}$,
with probability at least $1-\delta$. Therefore, we conclude the proof of
Lemma E.2. ∎

###  F.3 Proof of Lemma E.3

###### Proof.

By the definition of $\mathbb{V}^{\theta}_{h,a}$ in (E.6), we have

$\displaystyle\mathbb{E}_{X\sim
p}[(\mathbb{F}^{\theta}_{h,a}f)(X)]=\int_{\mathcal{O}^{3}}f(x)\cdot(\mathbb{V}^{\theta}_{h,a}\rho)(x){\,\mathrm{d}}x.$
(F.17)

for any $f\in L^{\infty}(\mathcal{O}^{3})$ and
$\rho\in\Delta(\mathcal{O}^{3})$. By combining (F.17) and Lemma C.1, we have

$\displaystyle\int_{\mathcal{O}^{3}}f(x)\cdot(\mathbb{V}^{\theta}_{h,a}\rho^{\theta,\pi}_{h,a,a^{\prime}}-\rho^{\theta,\pi}_{h,a,a^{\prime}})(x){\,\mathrm{d}}x,$

for any $f\in L^{\infty}(\mathcal{O}^{3})$, which implies

$\displaystyle\|\mathbb{V}^{\theta}_{h,a}\rho^{\theta,\pi}_{h,a,a^{\prime}}-\rho^{\theta,\pi}_{h,a,a^{\prime}}\|_{1}=0.$

For any $\rho\in L^{1}(\mathcal{O}^{3})$ such that $\|\rho\|_{1}=1$, we have

$\displaystyle\|\mathbb{V}^{\theta}_{h,a}\rho\|_{1}$
$\displaystyle=\int_{\mathcal{O}^{3}}\Bigl{|}\int_{\mathcal{O}^{2}}{\mathcal{B}}^{\theta}_{h,a}(o_{h},\widetilde{o}_{h},\widetilde{o}_{h+1})\cdot\rho(o_{h-1},o_{h},o_{h+1}){\,\mathrm{d}}o_{h}{\,\mathrm{d}}o_{h+1}\Bigr{|}{\,\mathrm{d}}o_{h-1}{\,\mathrm{d}}{\widetilde{o}}_{h}{\,\mathrm{d}}{\widetilde{o}}_{h+1}$
(F.18)
$\displaystyle\leq\int_{{\mathcal{S}}\times\mathcal{O}^{5}}p_{\theta}(\widetilde{\bm{o}}_{h}=\widetilde{o}_{h},\widetilde{\bm{o}}_{h+1}=\widetilde{o}_{h+1}\,|\,\widetilde{\bm{s}}_{h}=\widetilde{s}_{h},\widetilde{\bm{a}}_{h}=a)\cdot|\mathcal{Z}^{\theta}_{h}(\widetilde{s}_{h},o_{h})|$
$\displaystyle\quad\qquad\qquad\qquad\qquad\cdot|\rho(o_{h-1},o_{h},o_{h+1})|{\,\mathrm{d}}\widetilde{s}_{h}{\,\mathrm{d}}o_{h}{\,\mathrm{d}}o_{h+1}{\,\mathrm{d}}o_{h-1}{\,\mathrm{d}}{\widetilde{o}}_{h}{\,\mathrm{d}}{\widetilde{o}}_{h+1}$
$\displaystyle=\int_{{\mathcal{S}}\times\mathcal{O}^{3}}|\mathcal{Z}^{\theta}_{h}(\widetilde{s}_{h},o_{h})|\cdot|\rho(o_{h-1},o_{h},o_{h+1})|{\,\mathrm{d}}\widetilde{s}_{h}{\,\mathrm{d}}o_{h}{\,\mathrm{d}}o_{h+1}{\,\mathrm{d}}o_{h-1},$

where the inequality is by the definition of ${\mathcal{B}}^{\theta}_{h,a}$ in
(3.6). Combining (F.18) with (C.15) from the proof of Lemma C.1, we have

$\displaystyle\|\mathbb{V}^{\theta}_{h,a}\rho\|_{1}\leq\int_{\times\mathcal{O}^{3}}\gamma\cdot|\rho(o_{h-1},o_{h},o_{h+1})|{\,\mathrm{d}}o_{h}{\,\mathrm{d}}o_{h+1}{\,\mathrm{d}}o_{h-1}=\gamma,$

which implies $\|\mathbb{V}^{\theta}_{h,a}\|_{1\rightarrow 1}\leq\gamma$.

Therefore, we conclude the proof of Lemma E.3. ∎

###  F.4 Property of the Bridge Operator

######  Lemma F.1 (Bridge Property).

Recall that we denote by $\sigma_{h-1}$ the event

$\displaystyle{\overline{\bm{\tau}}}_{h-1}={\overline{\tau}}_{h-1},\quad\bm{a}_{h-1}=a_{h-1}.$

For any
$(h,\theta,{\overline{\tau}}_{h-1},a_{h-1})\in[H]\times\Theta\times\overline{\Gamma}_{h-1}\times\mathcal{A}$,
we have

$\displaystyle\mathbb{E}_{\theta}[\mathcal{Z}^{\theta}_{h}(\widetilde{s}_{h},\bm{o}_{h})\,|\,\sigma_{h-1}]=p_{\theta}(\widetilde{\bm{s}}_{h}=\widetilde{s}_{h}\,|\,\sigma_{h-1}).$

###### Proof.

By the tower property of the expectation and the Markov property of the POMDP,
we have

$\displaystyle\mathbb{E}_{\theta}[\mathcal{Z}^{\theta}_{h}(\widetilde{s}_{h},\bm{o}_{h})\,|\,\sigma_{h-1}]=\mathbb{E}_{\theta}\bigl{[}\mathbb{E}_{\theta}[\mathcal{Z}^{\theta}_{h}(\widetilde{s}_{h},\bm{o}_{h})\,|\,\bm{s}_{h-1},\bm{a}_{h-1}=a_{h-1}]\,\big{|}\,\sigma_{h-1}\bigr{]}.$
(F.19)

Note that, for any $s_{h-1}\in{\mathcal{S}}$, we have

$\displaystyle\mathbb{E}_{\theta}[\mathcal{Z}^{\theta}_{h}(\widetilde{s}_{h},\bm{o}_{h})\,|\,\bm{s}_{h-1}=s_{h-1},\bm{a}_{h-1}=a_{h-1}]$
(F.20)
$\displaystyle\quad=\int_{\mathcal{O}}\mathcal{Z}^{\theta}_{h}(\widetilde{s}_{h},o_{h})\cdot
p_{\theta}(\bm{o}_{h}=o_{h}\,|\,\bm{s}_{h-1}=s_{h-1},\bm{a}_{h-1}=a_{h-1}){\,\mathrm{d}}o_{h}$
$\displaystyle\quad=\int_{\mathcal{O}\times{\mathcal{S}}}\mathcal{Z}^{\theta}_{h}(\widetilde{s}_{h},o_{h})\cdot\mathcal{E}^{\theta}_{h}(o_{h}\,|\,s_{h})\cdot
p_{\theta}(\bm{s}_{h}=s_{h}\,|\,\bm{s}_{h-1}=s_{h-1},\bm{a}_{h-1}=a_{h-1}){\,\mathrm{d}}s_{h}{\,\mathrm{d}}o_{h}.$

We define the function $f:{\mathcal{S}}\rightarrow\mathbb{R}$ by

$\displaystyle
f(s_{h})=p_{\theta}(\bm{s}_{h}=s_{h}\,|\,\bm{s}_{h-1}=s_{h-1},\bm{a}_{h-1}=a_{h-1}),\quad\text{for
any $s_{h}\in{\mathcal{S}}$.}$

Then, we have $f\in\mathcal{F}_{\rm s}$ and we can write the right-hand side
of (F.20) as

$\displaystyle(\mathbb{Z}^{\theta}_{h}\mathbb{O}^{\theta}_{h}f)(\widetilde{s}_{h})=f(\widetilde{s}_{h})=p_{\theta}(\bm{s}_{h}=\widetilde{s}_{h}\,|\,\bm{s}_{h-1}=s_{h-1},\bm{a}_{h-1}=a_{h-1})$

following Assumptions 2.1 and 2.2. In other words, we have

$\displaystyle\mathbb{E}_{\theta}[\mathcal{Z}^{\theta}_{h}(\widetilde{s}_{h},\bm{o}_{h})\,|\,\bm{s}_{h-1}=s_{h-1},\bm{a}_{h-1}=a_{h-1}]$
(F.21)
$\displaystyle\quad=p_{\theta}(\bm{s}_{h}=\widetilde{s}_{h}\,|\,\bm{s}_{h-1}=s_{h-1},\bm{a}_{h-1}=a_{h-1}).$

Combining (F.19) and (F.21) and using the Markov property of the POMDP, we
obtain

$\displaystyle\mathbb{E}_{\theta}[\mathcal{Z}^{\theta}_{h}(\widetilde{s}_{h},\bm{o}_{h})\,|\,\sigma_{h-1}]$
$\displaystyle\quad=\int_{\mathcal{S}}p_{\theta}(\bm{s}_{h}=\widetilde{s}_{h}\,|\,\bm{s}_{h-1}=s_{h-1},\bm{a}_{h-1}=a_{h-1})\cdot
p_{\theta}(\bm{s}_{h-1}=s_{h-1}\,|\,\sigma_{h-1}){\,\mathrm{d}}s_{h-1}$
$\displaystyle\quad=\int_{\mathcal{S}}p_{\theta}(\bm{s}_{h}=\widetilde{s}_{h}\,|\,\bm{s}_{h-1}=s_{h-1},\sigma_{h-1})\cdot
p_{\theta}(\bm{s}_{h-1}=s_{h-1}\,|\,\sigma_{h-1}){\,\mathrm{d}}s_{h-1}$
$\displaystyle\quad=p_{\theta}(\bm{s}_{h}=\widetilde{s}_{h}\,|\,\sigma_{h-1}),$

which concludes the proof of lemma F.1. ∎

The following lemma is a variant of Lemma 3.1, which adds the state
information to the expectation condition.

######  Lemma F.2 (Variant of Lemma 3.1).

For any
$(h,\theta,\pi,s_{h-1},\overline{\tau}_{h-1},a_{h-1})\in[H]\times\Theta\times\Pi\times{\mathcal{S}}\times\overline{\Gamma}_{h-1}\times\mathcal{A}$
and $f\in L^{\infty}(\overline{\Gamma}_{h+1})$, we have

$\displaystyle\mathbb{E}_{\theta}[({\mathbb{B}}^{\theta,\pi}_{h}f)({\overline{\bm{\tau}}}_{h})-f({\overline{\bm{\tau}}}_{h+1})\,|\,\bm{s}_{h-1}=s_{h-1},\sigma_{h-1}]=0.$

###### Proof.

The proof is very similar to the proof of Lemma 3.1. Following the notation in
Lemma 3.1, by the definition of ${\mathbb{B}}^{\theta,\pi}_{h}$ in (3.4), we
have

$\displaystyle\mathbb{E}_{\theta}[({\mathbb{B}}^{\theta,\pi}_{h}f)({\overline{\bm{\tau}}}_{h})\,|\,\bm{s}_{h-1}=s_{h-1},\sigma_{h-1}]$
(F.22)
$\displaystyle\quad=\int_{{\mathcal{S}}\times\mathcal{O}^{3}}f\bigl{(}{\overline{\tau}}_{h}^{\dagger},\pi(\tau_{h}^{\dagger}),{\widetilde{o}}_{h+1}\bigr{)}\cdot
p_{\theta}\bigl{(}\bm{o}_{h}=\widetilde{o}_{h},\bm{o}_{h+1}=\widetilde{o}_{h+1}\,|\,\bm{s}_{h}=\widetilde{s}_{h},\bm{a}_{h}=\pi(\tau_{h}^{\dagger})\bigr{)}$
$\displaystyle\quad\qquad\qquad\qquad\cdot\mathcal{Z}^{\theta}_{h}(\widetilde{s}_{h},o_{h})\cdot
p_{\theta}(\bm{o}_{h}=o_{h}\,|\,\bm{s}_{h-1}=s_{h-1},\sigma_{h-1}){\,\mathrm{d}}o_{h}{\,\mathrm{d}}{\widetilde{o}}_{h}{\,\mathrm{d}}{\widetilde{o}}_{h+1}{\,\mathrm{d}}\widetilde{s}_{h}.$

Here, by (F.20)-(F.21) in the proof of Lemma F.1, we have

$\displaystyle\int_{\mathcal{O}}\mathcal{Z}^{\theta}_{h}(\widetilde{s}_{h},o_{h})\cdot
p_{\theta}(\bm{o}_{h}=o_{h}\,|\,\bm{s}_{h-1}=s_{h-1},\sigma_{h-1}){\,\mathrm{d}}o_{h}$
$\displaystyle\quad=\int_{\mathcal{O}}\mathcal{Z}^{\theta}_{h}(\widetilde{s}_{h},o_{h})\cdot
p_{\theta}(\bm{o}_{h}=o_{h}\,|\,\bm{s}_{h-1}=s_{h-1},\bm{a}_{h-1}=a_{h-1}){\,\mathrm{d}}o_{h}$
$\displaystyle\quad=p_{\theta}(\bm{s}_{h}=\widetilde{s}_{h}\,|\,\bm{s}_{h-1}=s_{h-1},\bm{a}_{h-1}=a_{h-1})$
$\displaystyle\quad=p_{\theta}(\bm{s}_{h}=\widetilde{s}_{h}\,|\,\bm{s}_{h-1}=s_{h-1},\sigma_{h-1}).$

Thus, we can rewrite (F.22) as

$\displaystyle\mathbb{E}_{\theta}[({\mathbb{B}}^{\theta,\pi}_{h}f)({\overline{\bm{\tau}}}_{h})\,|\,\bm{s}_{h-1}=s_{h-1},\sigma_{h-1}]$
(F.23)
$\displaystyle\quad=\int_{{\mathcal{S}}\times\mathcal{O}^{2}}f\bigl{(}{\overline{\tau}}_{h}^{\dagger},\pi(\tau_{h}^{\dagger}),{\widetilde{o}}_{h+1}\bigr{)}\cdot
p_{\theta}\bigl{(}\bm{o}_{h}=\widetilde{o}_{h},\bm{o}_{h+1}=\widetilde{o}_{h+1}\,|\,\bm{s}_{h}=\widetilde{s}_{h},\bm{a}_{h}=\pi({\overline{\tau}}_{h}^{\dagger})\bigr{)}$
$\displaystyle\quad\qquad\qquad\qquad\cdot
p(\bm{s}_{h}=\widetilde{s}_{h}\,|\,\bm{s}_{h-1}=s_{h-1},\sigma_{h-1}){\,\mathrm{d}}{\widetilde{o}}_{h}{\,\mathrm{d}}{\widetilde{o}}_{h+1}{\,\mathrm{d}}\widetilde{s}_{h}$
$\displaystyle\quad=\int_{\mathcal{O}^{2}}f\bigl{(}{\overline{\tau}}_{h}^{\dagger},\pi(\tau_{h}^{\dagger}),{\widetilde{o}}_{h+1}\bigr{)}\cdot
p_{\theta,\pi}(\bm{o}_{h}=\widetilde{o}_{h},\bm{o}_{h+1}=\widetilde{o}_{h+1}\,|\,\bm{s}_{h-1}=s_{h-1},\sigma_{h-1}){\,\mathrm{d}}{\widetilde{o}}_{h}{\,\mathrm{d}}{\widetilde{o}}_{h+1}.$

where the second equality uses the independence between
$(\bm{o}_{h},\bm{o}_{h+1})$ and $\bm{\tau}_{h-1}$ conditioning on
$(\bm{s}_{h},\bm{a}_{h})$. Replacing the notations ${\widetilde{o}}_{h}$ and
${\widetilde{o}}_{h+1}$ of the integral variables on the right-hand side of
(F.23) by $o_{h}$ and $o_{h+1}$, respectively, we obtain

$\displaystyle\mathbb{E}_{\theta}[({\mathbb{B}}^{\theta,\pi}_{h}f)({\overline{\bm{\tau}}}_{h})\,|\,\bm{s}_{h-1}=s_{h-1},\sigma_{h-1}]$
(F.24)
$\displaystyle\quad=\int_{\mathcal{O}^{2}}f\bigl{(}{\overline{\tau}}_{h},\pi(\tau_{h}),o_{h+1}\bigr{)}\cdot
p_{\theta,\pi}(\bm{o}_{h}=o_{h},\bm{o}_{h+1}=o_{h+1}\,|\,\bm{s}_{h-1}=s_{h-1},\sigma_{h-1}){\,\mathrm{d}}o_{h}{\,\mathrm{d}}o_{h+1}$
$\displaystyle\quad=\mathbb{E}_{\theta,\pi}[f({\overline{\bm{\tau}}}_{h+1})\,|\,\bm{s}_{h-1}=s_{h-1},\sigma_{h-1}],$

where we denote
${\overline{\tau}}_{h}=({\overline{\tau}}_{h-1},a_{h-1},o_{h})$ and
$\tau_{h}=(\tau_{h-1},o_{h})$. Therefore, we conclude the proof of Lemma F.2.
∎

###  F.5 Properties of the Value Functions

######  Lemma F.3.

For any
$(h,\pi,\theta,{\overline{\tau}}_{h})\in[H]\times\Pi\times\Theta\times\overline{\Gamma}_{h}$,
it holds that

$\displaystyle
V^{\theta,\pi}_{h}({\overline{\tau}}_{h})=\int_{\mathcal{S}}\mathbb{E}_{\theta,\pi}\Bigl{[}\sum_{i=1}^{H}\bm{r}_{i}\,\Big{|}\,\bm{s}_{h}=s_{h},{\overline{\bm{\tau}}}_{h-1}={\overline{\tau}}_{h-1},\bm{a}_{h-1}=a_{h-1}\Bigr{]}\cdot\mathcal{Z}^{\theta}_{h}(s_{h},o_{h}){\,\mathrm{d}}s_{h}.$
(F.25)

Here, we denote
${\overline{\tau}}_{h}=({\overline{\tau}}_{h-1},a_{h-1},o_{h})$ following the
definition in (2.3).

###### Proof.

We prove the lemma by induction over $h\in[H]$. When $h=H$, by the definition
of the value function in (3.10) and the definition of
${\mathbb{B}}^{\theta,\pi}_{H}$ in (3.4), we have

$\displaystyle V^{\theta,\pi}_{H}({\overline{\tau}}_{H})$
$\displaystyle=({\mathbb{B}}^{\theta,\pi}_{H}R)({\overline{\tau}}_{H})$ (F.26)
$\displaystyle=\int_{\mathcal{O}^{2}}\Bigl{(}r\bigl{(}{\widetilde{o}}_{H},\pi(\tau^{\dagger}_{H})\bigr{)}+\sum_{i=1}^{H-1}r(o_{h},a_{h})\Bigr{)}\cdot{\mathcal{B}}^{\theta}_{h,\pi(\tau^{\dagger}_{H})}(o_{H},{\widetilde{o}}_{H},{\widetilde{o}}_{H+1}){\,\mathrm{d}}{\widetilde{o}}_{H}{\,\mathrm{d}}{\widetilde{o}}_{H+1}$
$\displaystyle=\int_{\mathcal{O}}\Bigl{(}r\bigl{(}{\widetilde{o}}_{H},\pi(\tau^{\dagger}_{H})\bigr{)}+\sum_{i=1}^{H-1}r(o_{h},a_{h})\Bigr{)}\cdot\Bigl{(}\int_{\mathcal{O}}{\mathcal{B}}^{\theta}_{h,\pi(\tau^{\dagger}_{H})}(o_{H},{\widetilde{o}}_{H},{\widetilde{o}}_{H+1}){\,\mathrm{d}}{\widetilde{o}}_{H+1}\Bigr{)}{\,\mathrm{d}}{\widetilde{o}}_{H}.$

Recall that $\tau^{\dagger}_{H}$ is the tail-mirrored observation history
defined in (3.5). Note that, by the definition of
$\\{{\mathcal{B}}^{\theta}_{H,a}\\}_{a\in\mathcal{A}}$ in (3.6), we have

$\displaystyle\int_{\mathcal{O}}{\mathcal{B}}^{\theta}_{h,\pi(\tau^{\dagger}_{H})}(o_{H},{\widetilde{o}}_{H},{\widetilde{o}}_{H+1}){\,\mathrm{d}}{\widetilde{o}}_{H+1}$
(F.27)
$\displaystyle\quad=\int_{{\mathcal{S}}\times\mathcal{O}}p_{\theta}(\widetilde{\bm{o}}_{H}=\widetilde{o}_{H},\widetilde{\bm{o}}_{H+1}={\widetilde{o}}_{H+1}\,|\,\widetilde{\bm{s}}_{H}=s_{H},\widetilde{\bm{a}}_{H}=a)\cdot\mathcal{Z}^{\theta}_{H}(s_{H},o_{H}){\,\mathrm{d}}s_{H}{\,\mathrm{d}}{\widetilde{o}}_{H+1}$
$\displaystyle\quad=\int_{{\mathcal{S}}}p_{\theta}(\bm{o}_{h}=\widetilde{o}_{H}\,|\,\bm{s}_{H}=s_{H},\bm{a}_{H}=a)\cdot\mathcal{Z}^{\theta}_{H}(s_{H},o_{H}){\,\mathrm{d}}s_{H},$

where we use the fact that $\widetilde{\bm{s}}_{H}$, $\widetilde{\bm{a}}_{H}$,
$\widetilde{\bm{o}}_{H}$, and $\widetilde{\bm{o}}_{H+1}$ in (3.6) have the
same distribution of $\bm{s}_{H}$, $\bm{a}_{H}$, $\bm{o}_{H}$, and
$\bm{o}_{H+1}$. Combining (F.26) and (F.27), we have that (F.25) holds for
$h=H$.

Assume that (F.25) holds when $h=j+1$ for some fixed $j\leq H-1$. Then, by the
definition of the value function in (3.10), we have

$\displaystyle V^{\theta,\pi}_{j}({\overline{\tau}}_{j})$
$\displaystyle=({\mathbb{B}}^{\theta,\pi}_{j}V^{\theta,\pi}_{j+1})({\overline{\tau}}_{j}),\quad\text{for
any ${\overline{\tau}}_{j}\in\overline{\Gamma}_{j}$.}$

Applying the induction assumption and definition of
${\mathbb{B}}^{\theta,\pi}_{j}$ in (3.4), we obtain

$\displaystyle({\mathbb{B}}^{\theta,\pi}_{j}V^{\theta,\pi}_{j+1})({\overline{\tau}}_{j})$
$\displaystyle=\int_{{\mathcal{S}}\times\mathcal{O}^{2}}\mathbb{E}_{\theta,\pi}\Bigl{[}\sum_{i=1}^{H}\bm{r}_{i}\,\Big{|}\,\bm{s}_{j+1}=s_{j+1},{\overline{\bm{\tau}}}_{j}={\overline{\tau}}^{\dagger}_{j},\bm{a}_{j}=\pi(\tau^{\dagger}_{j})\Bigr{]}\cdot\mathcal{Z}^{\theta}_{h}(s_{j+1},{\widetilde{o}}_{j+1})$
$\displaystyle\qquad\qquad\qquad\qquad\cdot{\mathcal{B}}^{\theta}_{j,\pi(\tau^{\dagger}_{j})}(o_{j},{\widetilde{o}}_{j},{\widetilde{o}}_{j+1}){\,\mathrm{d}}s_{j+1}{\,\mathrm{d}}{\widetilde{o}}_{j}{\,\mathrm{d}}{\widetilde{o}}_{j+1}.$
(F.28)

Recall that $\tau^{\dagger}_{j}$ and ${\overline{\tau}}^{\dagger}_{j}$ are the
tail-mirrored observation history and full history defined in (3.5),
respectively. Note that, by the definition of
$\\{{\mathcal{B}}^{\theta}_{j,a}\\}_{a\in\mathcal{A}}$ in (3.6), we have

$\displaystyle{\mathcal{B}}^{\theta}_{j,\pi(\tau^{\dagger}_{j})}(o_{j},{\widetilde{o}}_{j},{\widetilde{o}}_{j+1})$
(F.29)
$\displaystyle\quad=\int_{\mathcal{S}}p_{\theta}\bigl{(}\bm{o}_{j}=\widetilde{o}_{j},\bm{o}_{j+1}={\widetilde{o}}_{j+1}\,|\,\bm{s}_{j}=s_{j},\bm{a}_{j}=\pi(\tau^{\dagger}_{j})\bigr{)}\cdot\mathcal{Z}^{\theta}_{j}(s_{j},o_{j}){\,\mathrm{d}}s_{j}$
$\displaystyle\quad=\int_{\mathcal{S}}\mathcal{E}^{\theta}_{h}({\widetilde{o}}_{j}\,|\,s_{j})\cdot
p_{\theta}\bigl{(}\bm{o}_{j+1}={\widetilde{o}}_{j+1}\,|\,\bm{s}_{j}=s_{j},\bm{a}_{j}=\pi(\tau^{\dagger}_{j})\bigr{)}\cdot\mathcal{Z}^{\theta}_{j}(s_{j},o_{j}){\,\mathrm{d}}s_{j}$

Following the same argument in (F.20)-(F.21), we have

$\displaystyle\int_{\mathcal{O}}\mathcal{Z}^{\theta}_{h}(s_{j+1},{\widetilde{o}}_{j+1})\cdot
p_{\theta}\bigl{(}\bm{o}_{j+1}={\widetilde{o}}_{j+1}\,|\,\bm{s}_{j}=s_{j},\bm{a}_{j}=\pi(\tau^{\dagger}_{j})\bigr{)}{\,\mathrm{d}}{\widetilde{o}}_{j+1}$
$\displaystyle\quad=p_{\theta}\bigl{(}\bm{s}_{j+1}=s_{j+1}\,|\,\bm{s}_{j}=s_{j},\bm{a}_{j}=\pi(\tau^{\dagger}_{j})\bigr{)},$

combining which with (F.29), we obtain

$\displaystyle\int_{\mathcal{O}}\mathcal{Z}^{\theta}_{h}(s_{j+1},{\widetilde{o}}_{j+1})\cdot{\mathcal{B}}^{\theta}_{j,\pi(\tau^{\dagger}_{j})}(o_{j},{\widetilde{o}}_{j},{\widetilde{o}}_{j+1}){\,\mathrm{d}}{\widetilde{o}}_{j+1}$
$\displaystyle\quad=\int_{\mathcal{S}}\mathcal{E}^{\theta}_{h}({\widetilde{o}}_{j}\,|\,s_{j})\cdot
p_{\theta}\bigl{(}\bm{s}_{j+1}=s_{j+1}\,|\,\bm{s}_{j}=s_{j},\bm{a}_{j}=\pi(\tau^{\dagger}_{j})\bigr{)}\cdot\mathcal{Z}^{\theta}_{j}(s_{j},o_{j}){\,\mathrm{d}}s_{j}$
$\displaystyle\quad=\int_{\mathcal{S}}p_{\theta}\bigl{(}\bm{o}_{j}={\widetilde{o}}_{j},\bm{s}_{j+1}=s_{j+1}\,|\,\bm{s}_{j}=s_{j},\bm{a}_{j}=\pi(\tau^{\dagger}_{j})\bigr{)}\cdot\mathcal{Z}^{\theta}_{j}(s_{j},o_{j}){\,\mathrm{d}}s_{j}.$
(F.30)

Plugging (F.5) into the right-hand side of (F.5), we obtain

$\displaystyle({\mathbb{B}}^{\theta,\pi}_{j}V^{\theta,\pi}_{j+1})({\overline{\tau}}_{j})$
(F.31)
$\displaystyle\quad=\int_{{\mathcal{S}}^{2}\times\mathcal{O}}\mathbb{E}_{\theta,\pi}\Bigl{[}\sum_{i=1}^{H}\bm{r}_{i}\,\Big{|}\,\bm{s}_{j+1}=s_{j+1},{\overline{\bm{\tau}}}_{j}={\overline{\tau}}^{\dagger}_{j},\bm{a}_{j}=\pi(\tau^{\dagger}_{j})\Bigr{]}$
$\displaystyle\quad\qquad\qquad\cdot
p_{\theta}\bigl{(}\bm{o}_{j}={\widetilde{o}}_{j},\bm{s}_{j+1}=s_{j+1}\,|\,\bm{s}_{j}=s_{j},\bm{a}_{j}=\pi(\tau^{\dagger}_{j})\bigr{)}\cdot\mathcal{Z}^{\theta}_{j}(s_{j},o_{j}){\,\mathrm{d}}s_{j}{\,\mathrm{d}}s_{j+1}{\,\mathrm{d}}{\widetilde{o}}_{j}.$

Using the Markov property of the POMDP, we can simplify the right-hand side of
(F.31) to obtain

$\displaystyle({\mathbb{B}}^{\theta,\pi}_{j}V^{\theta,\pi}_{j+1})({\overline{\tau}}_{j})=\int_{\mathcal{S}}\mathbb{E}_{\theta,\pi}\Bigl{[}\sum_{i=1}^{H}\bm{r}_{i}\,\Big{|}\,\bm{s}_{j}=s_{j},{\overline{\bm{\tau}}}_{j-1}={\overline{\tau}}_{j-1},\bm{a}_{j-1}=a_{j-1}\Bigr{]}\cdot\mathcal{Z}^{\theta}_{j}(s_{j},o_{j}){\,\mathrm{d}}s_{j},$

which implies that (F.25) holds when $h=j$.

Therefore, we conclude the proof of Lemma F.3 by induction. ∎

######  Lemma F.4.

For any
$(h,\theta,{\overline{\tau}}_{h},\pi)\in[H]\times\Theta\times\overline{\Gamma}_{h}\times\Pi$,
we have

$\displaystyle|V^{\theta,\pi}_{h}({\overline{\tau}}_{h})|\leq\gamma H.$

Recall that $\gamma$ is defined in Assumption 2.2.

###### Proof.

By Lemma F.3 and Assumption 2.2, we have

$\displaystyle|V^{\theta,\pi}_{h}({\overline{\tau}}_{h})|$
$\displaystyle=\Bigl{|}\int_{\mathcal{S}}\mathbb{E}_{\theta,\pi}\Bigl{[}\sum_{i=1}^{H}\bm{r}_{i}\,\Big{|}\,\bm{s}_{h}=s_{h},{\overline{\bm{\tau}}}_{h-1}={\overline{\tau}}_{h-1},\bm{a}_{h-1}=a_{h-1}\Bigr{]}\cdot\mathcal{Z}^{\theta}_{h}(s_{h},o_{h}){\,\mathrm{d}}s_{h}\Bigr{|}$
$\displaystyle\leq
H\cdot\int_{\mathcal{S}}|\mathcal{Z}^{\theta}_{h}(s_{h},o_{h})|{\,\mathrm{d}}s_{h}=H\cdot\|{\mathbb{Z}}^{\theta}_{h}\delta_{o_{h}}\|_{1}\leq\gamma
H\cdot\|\delta_{o_{h}}\|_{1}=\gamma H,$

for any
$(h,\theta,{\overline{\tau}}_{h},\pi)\in[H]\times\Theta\times\overline{\Gamma}_{h}\times\Pi$.
Here, $\delta_{o_{h}}$ is the Dirac delta function defined on $\mathcal{O}$,
whose value is zero everywhere except at $o_{h}$, and whose integral over
$\mathcal{O}$ is equal to one. Thus, we conclude the proof of Lemma F.4. ∎

###  F.6 Properties of the State-Dependent Error

######  Lemma F.5.

For any $(k,h)\in[K]\times\\{2,\ldots,H\\}$, we have

$\displaystyle\mathbb{E}_{\theta^{*},\overline{\pi}_{k}}[e^{k}_{h}(\bm{s}_{h})]$
$\displaystyle\leq\gamma^{2}H\cdot\sum_{a,a^{\prime}\in\mathcal{A}}\bigl{\|}\mathbb{V}^{\theta_{k}}_{h,a^{\prime}}\rho^{\overline{\pi}_{k}}_{h,a,a^{\prime}}-\rho^{\overline{\pi}_{k}}_{h,a,a^{\prime}}\bigr{\|}_{1}.$

###### Proof.

By the definition of $e^{k}_{h}$ in (4.5), we have

$\displaystyle
e^{k}_{h}(s_{h-1})=\bigl{|}\mathbb{E}_{\theta^{*},\pi_{k}}[({\mathbb{B}}^{\theta_{k},\pi_{k}}_{h}V^{\theta_{k},\pi_{k}}_{h+1})({\overline{\bm{\tau}}}_{h})-({\mathbb{B}}^{\theta^{*},\pi_{k}}_{h}V^{\theta_{k},\pi_{k}}_{h+1})({\overline{\bm{\tau}}}_{h})\,|\,\bm{s}_{h-1}=s_{h-1}]\bigr{|},$
(F.32)

for any $s_{h-1}\in{\mathcal{S}}$. Note that, by the definition of
${\mathbb{B}}^{\theta,\pi}_{h}$ in (3.4), we have

$\displaystyle\mathbb{E}_{\theta^{*},\pi_{k}}[({\mathbb{B}}^{\theta_{k},\pi_{k}}_{h}V^{\theta_{k},\pi_{k}}_{h+1})({\overline{\bm{\tau}}}_{h})-({\mathbb{B}}^{\theta^{*},\pi_{k}}_{h}V^{\theta_{k},\pi_{k}}_{h+1})({\overline{\bm{\tau}}}_{h})\,|\,\bm{s}_{h-1}=s_{h-1},{\overline{\bm{\tau}}}_{h-1}={\overline{\tau}}_{h-1}]$
(F.33)
$\displaystyle\quad=\int_{\mathcal{O}^{3}}V^{\theta_{k},\pi_{k}}_{h+1}\bigl{(}{\overline{\tau}}^{\dagger}_{h},\pi_{k}(\tau^{\dagger}_{h}),{\widetilde{o}}_{h+1}\bigr{)}\cdot\Delta{\mathcal{B}}^{\theta_{k},\theta^{*}}_{h,\pi_{k}(\tau^{\dagger}_{h})}(o_{h},{\widetilde{o}}_{h},{\widetilde{o}}_{h+1})$
$\displaystyle\quad\qquad\qquad\cdot
p_{\theta^{*}}\bigl{(}\bm{o}_{h}=o_{h}\,\big{|}\,\bm{s}_{h-1}=s_{h-1},\bm{a}_{h-1}=\pi_{k}(\tau_{h-1})\bigr{)}{\,\mathrm{d}}o_{h}{\,\mathrm{d}}{\widetilde{o}}_{h}{\,\mathrm{d}}{\widetilde{o}}_{h+1},$

for any
$(s_{h-1},{\overline{\tau}}_{h-1})\in{\mathcal{S}}\times\overline{\Gamma}_{h-1}$,
where
${\overline{\tau}}_{h}^{\dagger}=({\overline{\tau}}_{h-1},a_{h-1},\widetilde{o}_{h})$,
$\tau_{h}^{\dagger}=(\tau_{h-1},\widetilde{o}_{h})$, and

$\displaystyle\Delta{\mathcal{B}}^{\theta_{k},\theta^{*}}_{h,\pi_{k}(\tau^{\dagger}_{h})}(o_{h},{\widetilde{o}}_{h},{\widetilde{o}}_{h+1})={\mathcal{B}}^{\theta_{k}}_{h,\pi_{k}(\tau^{\dagger}_{h})}(o_{h},{\widetilde{o}}_{h},{\widetilde{o}}_{h+1})-{\mathcal{B}}^{\theta^{*}}_{h,\pi_{k}(\tau^{\dagger}_{h})}(o_{h},{\widetilde{o}}_{h},{\widetilde{o}}_{h+1}).$
(F.34)

By replacing the actions $\pi_{k}(\tau_{h-1})$ and
$\pi_{k}(\tau^{\dagger}_{h})$ on the right-hand side of (F.33) by all possible
action combinations, we have the inequality

$\displaystyle\bigl{|}\mathbb{E}_{\theta^{*},\pi_{k}}[({\mathbb{B}}^{\theta_{k},\pi_{k}}_{h}V^{\theta_{k},\pi_{k}}_{h+1})({\overline{\bm{\tau}}}_{h})-({\mathbb{B}}^{\theta^{*},\pi_{k}}_{h}V^{\theta_{k},\pi_{k}}_{h+1})({\overline{\bm{\tau}}}_{h})\,|\,\bm{s}_{h-1}=s_{h-1},{\overline{\bm{\tau}}}_{h-1}={\overline{\tau}}_{h-1}]\bigr{|}$
(F.35)
$\displaystyle\quad\leq\sum_{a,a^{\prime}\in\mathcal{A}}\Bigl{|}\int_{\mathcal{O}^{3}}V^{\theta_{k},\pi_{k}}_{h+1}({\overline{\tau}}^{\dagger}_{h},a^{\prime},{\widetilde{o}}_{h+1})\cdot\Delta{\mathcal{B}}^{\theta_{k},\theta^{*}}_{h,a^{\prime}}(o_{h},{\widetilde{o}}_{h},{\widetilde{o}}_{h+1})$
$\displaystyle\quad\qquad\qquad\qquad\quad\cdot
p_{\theta^{*}}\bigl{(}\bm{o}_{h}=o_{h}\,\big{|}\,\bm{s}_{h-1}=s_{h-1},\bm{a}_{h-1}=a\bigr{)}{\,\mathrm{d}}o_{h}{\,\mathrm{d}}{\widetilde{o}}_{h}{\,\mathrm{d}}{\widetilde{o}}_{h+1}\Bigr{|}.$

Invoking Lemma F.4, we can further upper bound the left-hand side of (F.36) as

$\displaystyle\bigl{|}\mathbb{E}_{\theta^{*},\pi_{k}}[({\mathbb{B}}^{\theta_{k},\pi_{k}}_{h}V^{\theta_{k},\pi_{k}}_{h+1})({\overline{\bm{\tau}}}_{h})-({\mathbb{B}}^{\theta^{*},\pi_{k}}_{h}V^{\theta_{k},\pi_{k}}_{h+1})({\overline{\bm{\tau}}}_{h})\,|\,\bm{s}_{h-1}=s_{h-1},{\overline{\bm{\tau}}}_{h-1}={\overline{\tau}}_{h-1}]\bigr{|}$
(F.36)
$\displaystyle\quad\leq\sum_{a,a^{\prime}\in\mathcal{A}}\sup_{({\overline{\tau}}^{\dagger}_{h},{\widetilde{o}}_{h+1})\in\overline{\Gamma}_{h}\times\mathcal{O}}|V^{\theta_{k},\pi_{k}}_{h+1}({\overline{\tau}}^{\dagger}_{h},a^{\prime},{\widetilde{o}}_{h+1})|\cdot\int_{\mathcal{O}^{2}}\Bigl{|}\int_{\mathcal{O}}\Delta{\mathcal{B}}^{\theta_{k},\theta^{*}}_{h,a^{\prime}}(o_{h},{\widetilde{o}}_{h},{\widetilde{o}}_{h+1})$
$\displaystyle\quad\qquad\qquad\qquad\qquad\qquad\quad\cdot
p_{\theta^{*}}(\bm{o}_{h}=o_{h}\,|\,\bm{s}_{h-1}=s_{h-1},\bm{a}_{h-1}=a){\,\mathrm{d}}o_{h}\Bigr{|}{\,\mathrm{d}}{\widetilde{o}}_{h}{\,\mathrm{d}}{\widetilde{o}}_{h+1}$
$\displaystyle\quad\leq\sum_{a,a^{\prime}\in\mathcal{A}}\gamma
H\cdot\int_{\mathcal{O}^{2}}\Bigl{|}\int_{\mathcal{O}}\Delta{\mathcal{B}}^{\theta_{k},\theta^{*}}_{h,a^{\prime}}(o_{h},{\widetilde{o}}_{h},{\widetilde{o}}_{h+1})$
$\displaystyle\quad\qquad\qquad\qquad\qquad\qquad\quad\cdot
p_{\theta^{*}}(\bm{o}_{h}=o_{h}\,|\,\bm{s}_{h-1}=s_{h-1},\bm{a}_{h-1}=a){\,\mathrm{d}}o_{h}\Bigr{|}{\,\mathrm{d}}{\widetilde{o}}_{h}{\,\mathrm{d}}{\widetilde{o}}_{h+1}.$

Combining (F.32) and (F.36), and applying Jensen’s inequality, we obtain

$\displaystyle e^{k}_{h}(s_{h-1})$
$\displaystyle\leq\sum_{a,a^{\prime}\in\mathcal{A}}\gamma
H\cdot\int_{\mathcal{O}^{2}}\Bigl{|}\int_{\mathcal{O}}\Delta{\mathcal{B}}^{\theta_{k},\theta^{*}}_{h,a^{\prime}}(o_{h},{\widetilde{o}}_{h},{\widetilde{o}}_{h+1})$
(F.37) $\displaystyle\quad\qquad\qquad\qquad\qquad\quad\cdot
p_{\theta^{*}}(\bm{o}_{h}=o_{h}\,|\,\bm{s}_{h-1}=s_{h-1},\bm{a}_{h-1}=a){\,\mathrm{d}}o_{h}\Bigr{|}{\,\mathrm{d}}{\widetilde{o}}_{h}{\,\mathrm{d}}{\widetilde{o}}_{h+1},$

for any $s_{h-1}\in{\mathcal{S}}$.

In the sequel, we characterize the expectation of both sides of (F.37) with
respect to the marginal distribution of $\bm{s}_{h-1}$. We define the function
$f:{\mathcal{S}}\rightarrow\mathbb{R}$ by

$\displaystyle
f(s_{h-1})=\int_{\mathcal{O}}\Delta{\mathcal{B}}^{\theta_{k},\theta^{*}}_{h,a^{\prime}}(o_{h},{\widetilde{o}}_{h},{\widetilde{o}}_{h+1})\cdot
p_{\theta^{*},\overline{\pi}_{k}}(\bm{o}_{h}=o_{h},\bm{s}_{h-1}=s_{h-1}\,|\,\bm{a}_{h-1}=a){\,\mathrm{d}}o_{h},$
(F.38)

for any $s_{h-1}\in{\mathcal{S}}$. With $f$ defined above and the inequality
in (F.37), we have

$\displaystyle\mathbb{E}_{\theta^{*},\overline{\pi}_{k}}[e^{k}_{H}(\bm{s}_{h-1})]=\gamma
H\cdot\sum_{a,a^{\prime}\in\mathcal{A}}\int_{\mathcal{O}}\|f\|_{1}{\,\mathrm{d}}{\widetilde{o}}_{h}{\widetilde{o}}_{h+1},$
(F.39)

where we take the expectation of both sides of (F.37) with respect to the
marginal distribution of $\bm{s}_{h-1}$, following the policy
$\overline{\pi}_{k}$. Note that we can write the probability on the right-hand
side of (F.38) as

$\displaystyle
p_{\theta^{*},\overline{\pi}_{k}}(\bm{o}_{h}=o_{h},\bm{s}_{h-1}=s_{h-1}\,\big{|}\,\bm{a}_{h-1}=a)$
$\displaystyle\quad=p_{\theta^{*},\overline{\pi}_{k}}(\bm{s}_{h-1}=s_{h-1}\,|\,\bm{o}_{h}=o_{h},\bm{a}_{h-1}=a)\cdot
p_{\theta^{*},\overline{\pi}_{k}}(\bm{o}_{h}=o_{h}\,|\,\bm{a}_{h-1}=a),$

which implies $f\in\mathcal{F}^{\prime}_{\rm s}\subset{\rm
linspan}(\\{\psi_{i}\\}_{i=1}^{d_{\rm s}})$ following Assumption 2.1. Then, by
further applying Assumption 2.2, we obtain

$\displaystyle\|f\|_{1}=\|{\mathbb{Z}}^{\theta}_{h-1}{\mathbb{O}}^{\theta}_{h-1}f\|_{1}\leq\gamma\cdot\|{\mathbb{O}}^{\theta}_{h-1}f\|_{1}.$
(F.40)

With $f$ defined in (F.38) and ${\mathbb{O}}^{\theta}_{h-1}$ defined in (2.4),
we can write

$\displaystyle\|{\mathbb{O}}^{\theta}_{h-1}f\|_{1}$ (F.41)
$\displaystyle\quad=\int_{\mathcal{O}}\Bigl{|}\int_{\mathcal{O}\times{\mathcal{S}}}\Delta{\mathcal{B}}^{\theta_{k},\theta^{*}}_{h,a^{\prime}}(o_{h},{\widetilde{o}}_{h},{\widetilde{o}}_{h+1})\cdot
p_{\theta^{*},\overline{\pi}_{k}}(\bm{o}_{h}=o_{h},\bm{s}_{h-1}=s_{h-1}\,|\,\bm{a}_{h-1}=a)$
$\displaystyle\quad\qquad\qquad\qquad\qquad\cdot\mathcal{E}^{\theta}_{h-1}(o_{h-1}\,|\,s_{h-1}){\,\mathrm{d}}o_{h}{\,\mathrm{d}}s_{h-1}\Bigr{|}{\,\mathrm{d}}o_{h-1}$
$\displaystyle\quad=\int_{\mathcal{O}}\Bigl{|}\int_{\mathcal{O}}\Delta{\mathcal{B}}^{\theta_{k},\theta^{*}}_{h,a^{\prime}}(o_{h},{\widetilde{o}}_{h},{\widetilde{o}}_{h+1})\cdot
p_{\theta^{*},\overline{\pi}_{k}}(\bm{o}_{h-1}=o_{h-1},\bm{o}_{h}=o_{h}\,|\,\bm{a}_{h-1}=a){\,\mathrm{d}}o_{h}\Bigr{|}{\,\mathrm{d}}o_{h-1}$

Here, we can rewrite the probability on the right-hand side as

$\displaystyle
p_{\theta^{*},\overline{\pi}_{k}}(\bm{o}_{h-1}=o_{h-1},\bm{o}_{h}=o_{h}\,|\,\bm{a}_{h-1}=a)$
$\displaystyle\quad=\int_{\mathcal{O}}p_{\theta^{*},\overline{\pi}_{k}}(\bm{o}_{h-1}=o_{h-1},\bm{o}_{h}=o_{h},\bm{o}_{h+1}=o_{h+1}\,|\,\bm{a}_{h-1}=a,\bm{a}_{h}=a^{\prime}){\,\mathrm{d}}o_{h+1}$
$\displaystyle\quad=\int_{\mathcal{O}}\rho^{\overline{\pi}_{k}}_{h,a,a^{\prime}}(o_{h-1},o_{h},o_{h+1}){\,\mathrm{d}}o_{h+1}.$

Recall that $\Delta{\mathcal{B}}^{\theta_{k},\theta^{*}}_{h,a^{\prime}}$ is
defined in (F.34). Then, by applying the definition of
$\mathbb{V}^{\theta}_{h,a^{\prime}}$ in (E.6) for $\theta=\theta_{k}$ and
$\theta=\theta^{*}$ to the right-hand side of (F.41) and integrating for
${\widetilde{o}}_{h},{\widetilde{o}}_{h+1}$ over $\mathcal{O}^{2}$ for both
sides, we have

$\displaystyle\int_{\mathcal{O}^{3}}\|{\mathbb{O}}^{\theta}_{h-1}f\|_{1}{\,\mathrm{d}}{\widetilde{o}}_{h}{\,\mathrm{d}}{\widetilde{o}}_{h+1}=\|\mathbb{V}^{\theta_{k}}_{h,a^{\prime}}\rho^{\overline{\pi}_{k}}_{h,a,a^{\prime}}-\mathbb{V}^{\theta^{*}}_{h,a^{\prime}}\rho^{\overline{\pi}_{k}}_{h,a,a^{\prime}}\|_{1}=\|\mathbb{V}^{\theta_{k}}_{h,a^{\prime}}\rho^{\overline{\pi}_{k}}_{h,a,a^{\prime}}-\rho^{\overline{\pi}_{k}}_{h,a,a^{\prime}}\|_{1},$
(F.42)

where the second equality is by Lemma E.3. Then, by combining (F.39), (F.40)
and (F.42), we obtain

$\displaystyle\mathbb{E}_{\theta^{*},\overline{\pi}_{k}}[e^{k}_{h}(\bm{s}_{h-1})]$
$\displaystyle\leq\gamma
H\cdot\sum_{a,a^{\prime}\in\mathcal{A}}\int_{\mathcal{O}^{3}}\|f\|_{1}{\,\mathrm{d}}{\widetilde{o}}_{h}{\,\mathrm{d}}{\widetilde{o}}_{h+1}$
$\displaystyle\leq\gamma^{2}H\cdot\sum_{a,a^{\prime}\in\mathcal{A}}\int_{\mathcal{O}^{3}}\|{\mathbb{O}}^{\theta}_{h-1}f\|_{1}{\,\mathrm{d}}{\widetilde{o}}_{h}{\,\mathrm{d}}{\widetilde{o}}_{h+1}$
$\displaystyle=\gamma^{2}H\cdot\sum_{a,a^{\prime}\in\mathcal{A}}\|\mathbb{V}^{\theta_{k}}_{h}\rho^{\overline{\pi}_{k}}_{h,a,a^{\prime}}-\rho^{\overline{\pi}_{k}}_{h,a,a^{\prime}}\|_{1},$

which concludes the proof of Lemma F.5. ∎

######  Lemma F.6.

For any $(k,h)\in[K]\times\\{2,\ldots,H\\}$ and $s_{h-1}\in{\mathcal{S}}$, we
have

$\displaystyle e^{k}_{h}(s_{h-1})\leq 2\gamma H.$

###### Proof.

For any
$(k,h,s_{h-1},{\overline{\tau}}_{h-1},a_{h-1})\in[K]\times\\{2,\ldots,H\\}\times{\mathcal{S}}\times\overline{\Gamma}_{h-1}\times\mathcal{A}$,
we have

$\displaystyle\bigl{|}\mathbb{E}_{\theta^{*}}[({\mathbb{B}}^{\theta_{k},\pi_{k}}_{h}V^{\theta_{k},\pi_{k}}_{h+1})({\overline{\bm{\tau}}}_{h})\,|\,\bm{s}_{h-1}=s_{h-1},{\overline{\bm{\tau}}}_{h-1}={\overline{\tau}}_{h-1},\bm{a}_{h-1}=a_{h-1}]\bigr{|}$
(F.43)
$\displaystyle\quad=\bigl{|}\mathbb{E}_{\theta^{*}}[V^{\theta_{k},\pi_{k}}_{h}({\overline{\bm{\tau}}}_{h})\,|\,\bm{s}_{h-1}=s_{h-1},{\overline{\bm{\tau}}}_{h-1}={\overline{\tau}}_{h-1},\bm{a}_{h-1}=a_{h-1}]\bigr{|}\leq\gamma
H,$

where the equality uses the definition of the value function in (3.10) and the
inequality is by Lemma F.4. Similarly, by Lemma F.2, we have

$\displaystyle\bigl{|}\mathbb{E}_{\theta^{*}}[({\mathbb{B}}^{\theta^{*},\pi_{k}}_{h}V^{\theta_{k},\pi_{k}}_{h+1})({\overline{\bm{\tau}}}_{h})\,|\,\bm{s}_{h-1}=s_{h-1},{\overline{\bm{\tau}}}_{h-1}={\overline{\tau}}_{h-1},\bm{a}_{h-1}=a_{h-1}]\bigr{|}$
(F.44)
$\displaystyle\quad=\bigl{|}\mathbb{E}_{\theta^{*},\pi_{k}}[V^{\theta_{k},\pi_{k}}_{h+1}({\overline{\bm{\tau}}}_{h+1})\,|\,\bm{s}_{h-1}=s_{h-1},{\overline{\bm{\tau}}}_{h-1}={\overline{\tau}}_{h-1},\bm{a}_{h-1}=a_{h-1}]\bigr{|}\leq\gamma
H.$

Combining (F.43) and (F.44), and using the triangle inequality, we have

$\displaystyle\bigl{|}\mathbb{E}_{\theta^{*}}[({\mathbb{B}}^{\theta_{k},\pi_{k}}_{h}V^{\theta_{k},\pi_{k}}_{h+1}-{\mathbb{B}}^{\theta^{*},\pi_{k}}_{h}V^{\theta_{k},\pi_{k}}_{h+1})({\overline{\bm{\tau}}}_{h})\,|\,\bm{s}_{h-1}=s_{h-1},{\overline{\bm{\tau}}}_{h-1}={\overline{\tau}}_{h-1},\bm{a}_{h-1}=a_{h-1}]\bigr{|}\leq
2\gamma H,$

which, by Jensen’s inequality, implies

$\displaystyle
e^{k}_{h}(s_{h-1})=\bigl{|}\mathbb{E}_{\theta^{*},\pi_{k}}[({\mathbb{B}}^{\theta_{k},\pi_{k}}_{h}V^{\theta_{k},\pi_{k}}_{h+1}-{\mathbb{B}}^{\theta^{*},\pi_{k}}_{h}V^{\theta_{k},\pi_{k}}_{h+1})({\overline{\bm{\tau}}}_{h})\,|\,\bm{s}_{h-1}=s_{h-1}]\bigr{|}\leq
2\gamma H.$

Therefore, we conclude the proof of Lemma F.6. ∎

###  F.7 Concentration Inequality

######  Lemma F.7.

Suppose that $\\{\mathcal{M}_{j}\\}_{j\geq 1}$ is a martingale defined on a
Hilbert space $\mathcal{H}$. For any $c>0$, if we have

$\displaystyle\sum_{j=1}^{\infty}\|\mathcal{M}_{j+1}-\mathcal{M}_{j}\|^{2}_{\mathcal{H}}\leq
c^{2},$ (F.45)

then, for any $\varepsilon>0$, it holds that

$\displaystyle{\mathcal{P}}\Bigl{(}\sup_{j\geq
1}\|\mathcal{M}_{j}\|_{\mathcal{H}}\geq\varepsilon\Bigr{)}\leq
2\exp\Bigl{\\{}-\frac{\varepsilon^{2}}{2c^{2}}\Bigr{\\}}.$

###### Proof.

The lemma is a special case of Theorem 3.5 in Pinelis (1994) (see also,
Theorem 3 in Pinelis (1992)), which is a more general result for martingales
in Banach spaces. ∎