1-\alpha\quad\forall\alpha\in(0,1).$ (80)

The desired result in (42) then follows from (80) by noting that for every
$z=(\mathbf{d},\mathbf{i},a)\in\mathcal{Z}$ and $k\in\mathbb{N}$, we have
$N(\tau_{k}(z),\mathbf{d},\mathbf{i},a)=k$, and therefore

$\bigg{\\{}\tau_{k}(z)\leq\lambda_{\alpha}(\bm{\theta})\,k^{4}\bigg{\\}}=\bigg{\\{}N(\tau_{k}(z),\mathbf{d},\mathbf{i},a)\geq\left(\frac{\tau_{k}(z)}{\lambda_{\alpha}(\bm{\theta})}\right)^{1/4}\bigg{\\}}.$

We now proceed to prove (80). Fix $\alpha\in(0,1)$. Let
$g:\mathbb{N}\to\mathbb{N}$ be a strictly increasing function with $g(0)=0$
and $g(k)\geq k$ for all $k\in\mathbb{N}$. Let

$\mathcal{H}=\bigg{\\{}\forall z\in\mathcal{Z},~{}\forall
k\in\mathbb{N},~{}\tau_{k}(z)\leq g(k)\bigg{\\}}.$ (81)

We shall prove below that

$\mathbb{P}_{\bm{\theta}}(\overline{\mathcal{H}})\leq
K\,S_{R}\,\sum_{k=1}^{\infty}\
\prod_{j=0}^{\left\lfloor\frac{g(k)-g(k-1)-1}{m_{\bm{\theta}}+2}\right\rfloor-1}\left[1-\sigma_{\bm{\theta}}\prod_{l=1}^{m_{\bm{\theta}}+2}\varepsilon_{g(k-1)+(m_{\bm{\theta}}+2)\cdot
j+l}\right],$ (82)

where $\overline{\mathcal{H}}$ denotes the complement of $\mathcal{H}$, the
constant $m_{\bm{\theta}}$ is as defined in (71) and $\sigma_{\bm{\theta}}$ is
a constant that depends only on $\bm{\theta}$; see Lemma F.2 below for a
formal definition of $\sigma_{\bm{\theta}}$. We then tune $\varepsilon_{n}$
and $g$ suitably so that the right-hand side of (82) equals $\alpha$. Note
that

$\displaystyle\overline{\mathcal{H}}$
$\displaystyle=\bigcup_{z\in\mathcal{Z}}\
\bigcup_{k=1}^{\infty}\bigg{\\{}\tau_{k}(z)>g(k)\bigg{\\}}$
$\displaystyle=\bigcup_{z\in\mathcal{Z}}\
\bigcup_{k=1}^{\infty}\bigg{\\{}\tau_{k}(z)>g(k)\text{ and }\forall j\leq
k-1,~{}\tau_{j}(z)\leq g(j)\bigg{\\}},$ (83)

whence it follows from an application of the union bound that

$\displaystyle\mathbb{P}_{\bm{\theta}}(\overline{\mathcal{H}})\leq\sum_{z\in\mathcal{Z}}\bigg{[}\mathbb{P}_{\bm{\theta}}(\tau_{1}(z)>g(1))+\sum_{k=2}^{\infty}\mathbb{P}_{\bm{\theta}}\bigg{(}\tau_{k}(z)>g(k)\text{
and }\forall j\leq k-1,~{}\tau_{j}(z)\leq g(j)\bigg{)}\bigg{]}$
$\displaystyle\leq\sum_{z\in\mathcal{Z}}\bigg{[}\mathbb{P}_{\bm{\theta}}(\tau_{1}(z)>g(1))+\sum_{k=2}^{\infty}\mathbb{P}_{\bm{\theta}}\bigg{(}\tau_{k}(z)>g(k),~{}\tau_{k-1}(z)\leq
g(k-1)\bigg{)}\bigg{]}$
$\displaystyle\leq\sum_{z\in\mathcal{Z}}\bigg{[}\mathbb{P}_{\bm{\theta}}(\tau_{1}(z)>g(1))+\sum_{k=2}^{\infty}\mathbb{P}_{\bm{\theta}}\bigg{(}\tau_{k}(z)-\tau_{k-1}(z)>g(k)-g(k-1),~{}\tau_{k-1}(z)\leq
g(k-1)\bigg{)}\bigg{]}$
$\displaystyle\leq\sum_{z\in\mathcal{Z}}\bigg{[}\mathbb{P}_{\bm{\theta}}(\tau_{1}(z)>g(1))+\sum_{k=2}^{\infty}\
\sum_{n=1}^{g(k-1)}\mathbb{P}_{\bm{\theta}}\bigg{(}\tau_{k}(z)-\tau_{k-1}(z)>g(k)-g(k-1)\mid\tau_{k-1}(z)=n\bigg{)}\,\mathbb{P}_{\bm{\theta}}(\tau_{k-1}(z)=n)\bigg{]}$
$\displaystyle=\sum_{z\in\mathcal{Z}}\bigg{[}a_{1}(z)+\sum_{k=2}^{\infty}\
\sum_{n=1}^{g(k-1)}a_{k,n}(z)\,\mathbb{P}_{\bm{\theta}}(\tau_{k-1}(z)=n)\bigg{]},$
(84)

where

$\displaystyle a_{1}(z)$
$\displaystyle\coloneqq\mathbb{P}_{\bm{\theta}}(\tau_{1}(z)>g(1)),$ (85)
$\displaystyle a_{k,n}(z)$
$\displaystyle\coloneqq\mathbb{P}_{\bm{\theta}}\bigg{(}\tau_{k}(z)-\tau_{k-1}(z)>g(k)-g(k-1)\mid\tau_{k-1}(z)=n\bigg{)}.$
(86)

We now upper bound $\alpha_{k,n}(z)$ for each $z\in\mathcal{Z}$ and
$k\in\mathbb{N}$.

Upper bounding $\alpha_{k,n}(z)$: Fix $z\in\mathcal{Z}$ and $k\in\mathbb{N}$.
In order to upper bound $\alpha_{k,n}(z)$, we write the transition kernel
$Q_{\bm{\theta},\pi_{n}}$ for any $n$ as follows:

$Q_{\bm{\theta},\pi_{n}}=\begin{pmatrix}A_{n}(z)&[Q_{\bm{\theta},\pi_{n}}(z|z^{\prime}):z^{\prime}\neq
z]^{\top}\\\ [Q_{\bm{\theta},\pi_{n}}(z^{\prime}|z):z^{\prime}\neq
z]^{\top}&Q_{\bm{\theta},\pi_{n}}(z|z)\end{pmatrix}.$ (87)

In writing (87), we assume without loss of generality that the last row and
last column of $Q_{\bm{\theta},\pi_{n}}$ correspond to state $z$. Given
$z^{\prime}\neq z$, let $\mathbf{q}_{n}(z^{\prime},\neg
z)\coloneqq[Q_{\bm{\theta},\pi_{n}}(z^{\prime\prime}|z^{\prime}):z^{\prime\prime}\neq
z]^{\top}$. Then, for all $N\in\mathbb{N}$, it follows that

$\mathbb{P}_{\bm{\theta}}(\tau_{k}(z)-\tau_{k-1}(z)>N\mid\tau_{k-1}(z)=n)=\mathbf{q}_{n}(z,\neg
z)\cdot\prod_{l=n+1}^{n+N-1}A_{l}(z)\cdot\mathbf{1}.$ (88)

In (88), $\mathbf{1}$ denotes the all-ones vector.

We now note the following result of interest. We continue with the above proof
after the proof of the below result.

######  Lemma F.2.

Let $Q_{\bm{\theta},\pi_{n}}$ be as expressed in (87). Let

$\displaystyle\sigma_{\bm{\theta},1}$
$\displaystyle\coloneqq\min\\{Q_{\bm{\theta},\pi^{\text{\rm
unif}}}(z^{\prime}|z):z,z^{\prime}\in\mathcal{Z},~{}Q_{\bm{\theta},\pi^{\text{\rm
unif}}}(z^{\prime}|z)>0\\},$ (89) $\displaystyle\sigma_{\bm{\theta},2}$
$\displaystyle\coloneqq\min\\{Q_{\bm{\theta},\pi^{\text{\rm
unif}}}^{r}(z^{\prime}|z):z,z^{\prime}\in\mathcal{Z},~{}r\in\\{1,\ldots,m_{\bm{\theta}}+1\\},~{}Q_{\bm{\theta},\pi^{\text{\rm
unif}}}^{r}(z^{\prime}|z)>0\\}.$ (90)

where $m_{\bm{\theta}}$ is as defined in (71). Further, let
$\sigma_{\bm{\theta}}\coloneqq\sigma_{\bm{\theta},1}\,\sigma_{\bm{\theta},2}$.
Then,

$\bigg{\|}\prod_{l=n+1}^{n+m_{\bm{\theta}}+2}A_{l}(z)\bigg{\|}_{\infty}\leq
1-\sigma_{\bm{\theta}}\,\prod_{l=n+1}^{n+m_{\bm{\theta}}+2}\varepsilon_{l}\
,\qquad\forall n\in\mathbb{N}.$ (91)

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

Let $\mathcal{Z}=\mathbb{S}_{R}\times[K]$, with cardinality
$|\mathcal{Z}|=K\,S_{R}$, be enumerated as
$\mathcal{Z}=\\{1,\ldots,K\,S_{R}-1,z\\}$, where $z\in\mathcal{Z}$ corresponds
to the last row and last column in the expression for
$Q_{\bm{\theta},\pi_{n}}$ in (87). In particular, we note that $A_{n}(z)$ in
(87) is a matrix whose rows and columns are indexed by the elements from
$\\{1,\ldots,K\,S_{R}-1\\}$. Given $n_{1},n_{2}\in\mathbb{N}$, let

$r_{z^{\prime}}(n_{1},n_{2})\coloneqq\sum_{z^{\prime\prime}=1}^{K\,S_{R}-1}\left(\prod_{l=n_{1}+1}^{n_{2}}A_{l}(z)\right)(z^{\prime\prime}|z^{\prime})$
(92)

denote the sum of elements of the matrix $\prod_{l=n_{1}+1}^{n_{2}}A_{l}(z)$
corresponding to the row indexed by $z^{\prime}$. We will now prove that

$r_{z^{\prime}}(n,n+m_{\bm{\theta}}+2)\leq
1-\sigma_{\bm{\theta}}\prod_{l=n+1}^{n+m_{\bm{\theta}}+2}\varepsilon_{l}\quad\forall
z^{\prime}\in\\{1,\ldots,K\,S_{R}-1\\},~{}~{}\forall n\in\mathbb{N}.$ (93)

The desired result in (91) then follows from (93) by noting that

$\bigg{\|}\prod_{l=n+1}^{n+m_{\bm{\theta}}+2}A_{l}(z)\bigg{\|}_{\infty}=\max\bigg{\\{}r_{z^{\prime}}(n,n+m_{\bm{\theta}}+2):z^{\prime}\in\\{1,\ldots,K\,S_{R}-1\\}\bigg{\\}}.$

Fix an arbitrary $z^{*}\in\mathcal{Z}$ such that
$Q_{\bm{\theta},\pi^{\text{\rm unif}}}(z|z^{*})\geq\sigma_{\bm{\theta},1}$;
such a $z^{*}$ is guaranteed to exist because the MDP
$\mathcal{M}_{\bm{\theta},R}$ is communicating (Lemma 3.2). Then, for all
$n\in\mathbb{N}$,

$\displaystyle r_{z^{*}}(n,n+1)$
$\displaystyle=\sum_{z^{\prime\prime}=1}^{K\,S_{R}-1}\bigg{(}A_{n+1}(z)\bigg{)}(z^{\prime\prime}|z^{*})$
$\displaystyle=1-Q_{\bm{\theta},\pi_{n+1}}(z|z^{*})$ $\displaystyle\leq
1-\varepsilon_{n+1}\,Q_{\bm{\theta},\pi^{\text{\rm unif}}}(z|z^{*})$
$\displaystyle\leq 1-\sigma_{\bm{\theta},1}\,\varepsilon_{n+1}.$ (94)

Similarly, for any $n_{1},n_{2}\in\mathbb{N}$, we have

$\displaystyle r_{z^{*}}(n_{1},n_{1}+n_{2})$
$\displaystyle=\sum_{z^{\prime\prime}=1}^{K\,S_{R}-1}\left(\prod_{l=n_{1}+1}^{n_{1}+n_{2}}A_{l}(z)\right)(z^{\prime\prime}|z^{*})$
$\displaystyle=\sum_{z^{\prime\prime}=1}^{K\,S_{R}-1}\
\sum_{z^{{}^{\prime\prime\prime}}=1}^{K\,S_{R}-1}\left(\prod_{l=n_{1}+1}^{n_{1}+n_{2}-1}A_{l}(z)\right)(z^{\prime\prime\prime}|z^{*})\cdot\bigg{(}A_{n_{1}+n_{2}}(z)\bigg{)}(z^{\prime\prime}|z^{\prime\prime\prime})$
$\displaystyle=\sum_{z^{{}^{\prime\prime\prime}}=1}^{K\,S_{R}-1}\left(\prod_{l=n_{1}+1}^{n_{1}+n_{2}-1}A_{l}(z)\right)(z^{\prime\prime\prime}|z^{*})\cdot\left[\sum_{z^{\prime\prime}=1}^{K\,S_{R}-1}\bigg{(}A_{n_{1}+n_{2}}(z)\bigg{)}(z^{\prime\prime}|z^{\prime\prime\prime})\right]$
$\displaystyle=\sum_{z^{{}^{\prime\prime\prime}}=1}^{K\,S_{R}-1}\left(\prod_{l=n_{1}+1}^{n_{1}+n_{2}-1}A_{l}(z)\right)(z^{\prime\prime\prime}|z^{*})\cdot
r_{z^{\prime\prime\prime}}(n_{1}+n_{2}-1,n_{1}+n_{2})$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}\sum_{z^{{}^{\prime\prime\prime}}=1}^{K\,S_{R}-1}\left(\prod_{l=n_{1}+1}^{n_{1}+n_{2}-1}A_{l}(z)\right)(z^{\prime\prime\prime}|z^{*})$
$\displaystyle=r_{z^{*}}(n_{1},n_{1}+n_{2}-1)$ $\displaystyle\vdots$
$\displaystyle=r_{z^{*}}(n_{1},n_{1}+1)$ $\displaystyle\leq
1-\sigma_{\bm{\theta},1}\,\varepsilon_{n_{1}+1},$ (95)

where $(a)$ above follows from the fact that
$r_{z^{\prime\prime\prime}}(n_{1}+n_{2}-1,n_{1}+n_{2})\leq 1$ for all
$z^{\prime\prime\prime}\in\mathcal{Z}$, and the last line above follows from
(94). Along similar lines as above, we note that for all
$z^{\prime}\in\mathcal{Z}$ and $n_{1}\in\\{1,\ldots,m_{\bm{\theta}}+1\\}$,

$\displaystyle r_{z^{\prime}}(n,n+m_{\bm{\theta}}+2)$
$\displaystyle=\sum_{z^{\prime\prime}=1}^{K\,S_{R}-1}\left(\prod_{l=n+1}^{n+m_{\bm{\theta}}+2}A_{l}(z)\right)(z^{\prime\prime}|z^{\prime})$
$\displaystyle=\sum_{z^{\prime\prime}=1}^{K\,S_{R}-1}\
\sum_{z^{{}^{\prime\prime\prime}}=1}^{K\,S_{R}-1}\left(\prod_{l=n+1}^{n+n_{1}}A_{l}(z)\right)(z^{\prime\prime\prime}|z^{\prime})\cdot\left(\prod_{l=n+n_{1}+1}^{n+m_{\bm{\theta}}+2}A_{l}(z)\right)(z^{\prime\prime}|z^{\prime\prime\prime})$
$\displaystyle=\sum_{z^{{}^{\prime\prime\prime}}=1}^{K\,S_{R}-1}\left(\prod_{l=n+1}^{n+n_{1}}A_{l}(z)\right)(z^{\prime\prime\prime}|z^{\prime})\cdot\left[\sum_{z^{\prime\prime}=1}^{K\,S_{R}-1}\left(\prod_{l=n+n_{1}+1}^{n+m_{\bm{\theta}}+2}A_{l}(z)\right)(z^{\prime\prime}|z^{\prime\prime\prime})\right]$
$\displaystyle=\sum_{z^{{}^{\prime\prime\prime}}=1}^{K\,S_{R}-1}\left(\prod_{l=n+1}^{n+n_{1}}A_{l}(z)\right)(z^{\prime\prime\prime}|z^{\prime})\cdot
r_{z^{\prime\prime\prime}}(n+n_{1},n+m_{\bm{\theta}}+2)$
$\displaystyle\leq\left(\prod_{l=n+1}^{n+n_{1}}A_{l}(z)\right)(z^{*}|z^{\prime})\cdot
r_{z^{*}}(n+n_{1},n+m_{\bm{\theta}}+2)+\sum_{z^{\prime\prime\prime}\neq
z^{*}}\left(\prod_{l=n+1}^{n+n_{1}}A_{l}(z)\right)(z^{\prime\prime\prime}|z^{\prime})$
$\displaystyle\leq(1-\sigma_{\bm{\theta},1}\,\varepsilon_{n+n_{1}+1})\left(\prod_{l=n+1}^{n+n_{1}}A_{l}(z)\right)(z^{*}|z^{\prime})+1-\left(\prod_{l=n+1}^{n+n_{1}}A_{l}(z)\right)(z^{*}|z^{\prime})$
$\displaystyle=1-\sigma_{\bm{\theta},1}\,\varepsilon_{n+n_{1}+1}\,\left(\prod_{l=n+1}^{n+n_{1}}A_{l}(z)\right)(z^{*}|z^{\prime})$
$\displaystyle\leq
1-\sigma_{\bm{\theta},1}\,\varepsilon_{n+m_{\bm{\theta}}+2}\,\left(\prod_{l=n+1}^{n+n_{1}}A_{l}(z)\right)(z^{*}|z^{\prime}),$
(96)

where the last line follows from the fact that $\varepsilon_{n}$ is a
decreasing sequence. By virtue of the fact that the MDP
$\mathcal{M}_{\bm{\theta},R}$ is communicating, there exists
$r=r(z^{\prime},z^{*})$ such that $Q_{\bm{\theta},\pi^{\text{\rm
unif}}}^{r}(z^{*}|z^{\prime})\geq\sigma_{\bm{\theta},2}>0$. Here, $r\leq
m_{\bm{\theta}}+1$; for a formal justification of this, see Section F.1. Using
the preceding fact and setting $n_{1}=r$ in (96), we get

$\displaystyle\left(\prod_{l=n+1}^{n+r}A_{l}(z)\right)(z^{*}|z^{\prime})$
$\displaystyle\geq\left(\prod_{l=n+1}^{n+r}\varepsilon_{l}\,Q_{\bm{\theta},\pi^{\text{\rm
unif}}}\right)(z^{*}|z^{\prime})$
$\displaystyle=\left(\prod_{l=n+1}^{n+r}\varepsilon_{l}\right)\cdot
Q_{\bm{\theta},\pi^{\text{\rm unif}}}^{r}(z^{*}|z^{\prime})$
$\displaystyle\geq\left(\prod_{l=n+1}^{n+r}\varepsilon_{l}\right)\cdot\sigma_{\bm{\theta},2}.$
(97)

Combining (96) and (97), we get

$\displaystyle r_{z^{\prime}}(n,n+m_{\bm{\theta}}+2)$ $\displaystyle\leq
1-\sigma_{\bm{\theta},1}\,\sigma_{\bm{\theta},2}\,\varepsilon_{n+m_{\bm{\theta}}+2}\,\prod_{l=n+1}^{n+r}\,\varepsilon_{l}$
$\displaystyle\leq
1-\sigma_{\bm{\theta}}\,\varepsilon_{n+m_{\bm{\theta}}+2}\prod_{l=n+1}^{n+m_{\bm{\theta}}+1}\,\varepsilon_{l}$
$\displaystyle=1-\sigma_{\bm{\theta}}\prod_{l=n+1}^{n+m_{\bm{\theta}}+2}\,\varepsilon_{l},$
(98)

where the penultimate line follows from using $r\leq m_{\bm{\theta}}+1$. ∎

Plugging $N=g(k)-g(k-1)$ in (88), and using Lemma F.2, we have for all $k\geq
2$ that

$\displaystyle\alpha_{k,n}(z)$
$\displaystyle=\mathbb{P}_{\bm{\theta}}\bigg{(}\tau_{k}(z)-\tau_{k-1}(z)>g(k)-g(k-1)\mid\tau_{k-1}(z)=n\bigg{)}$
$\displaystyle=\mathbf{q}_{n}(z,\neg
z)\cdot\prod_{l=n+1}^{n+g(k)-g(k-1)-1}A_{l}(z)\cdot\mathbf{1}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}\bigg{\|}\prod_{l=n+1}^{n+g(k)-g(k-1)-1}A_{l}(z)\bigg{\|}_{\infty}$
$\displaystyle\leq\bigg{\|}\prod_{l=(m_{\bm{\theta}}+2)\left\lfloor\frac{g(k)-g(k-1)-1}{m_{\bm{\theta}}+2}\right\rfloor+1}^{g(k)-g(k-1)-1}A_{n+l}(z)\bigg{\|}_{\infty}\times\prod_{j=0}^{\left\lfloor\frac{g(k)-g(k-1)-1}{m_{\bm{\theta}}+2}\right\rfloor-1}\
\bigg{\|}\prod_{l=1}^{m_{\bm{\theta}}+2}A_{n+(m_{\bm{\theta}}+2)j+l}(z)\bigg{\|}_{\infty}$
$\displaystyle\leq\prod_{j=0}^{\left\lfloor\frac{g(k)-g(k-1)-1}{m_{\bm{\theta}}+2}\right\rfloor-1}\bigg{[}1-\sigma_{\bm{\theta}}\prod_{l=1}^{m_{\bm{\theta}}+2}\varepsilon_{n+(m_{\bm{\theta}}+2)j+l}\bigg{]}$
$\displaystyle\leq\prod_{j=0}^{\left\lfloor\frac{g(k)-g(k-1)-1}{m_{\bm{\theta}}+2}\right\rfloor-1}\bigg{[}1-\sigma_{\bm{\theta}}\prod_{l=1}^{m_{\bm{\theta}}+2}\varepsilon_{g(k-1)+(m_{\bm{\theta}}+2)j+l}\bigg{]},$
(99)

where $(a)$ above follows by noting that $\|\mathbf{q}_{n}(z,\neg z)\|_{1}\leq
1$, and the last line follows from noting that $n=\tau_{k-1}(z)\leq k-1\leq
g(k-1)$ and that $\varepsilon_{n}$ is decreasing in $n$. Going forward, let

$b_{k}\coloneqq\prod_{j=0}^{\left\lfloor\frac{g(k)-g(k-1)-1}{m_{\bm{\theta}}+2}\right\rfloor-1}\bigg{[}1-\sigma_{\bm{\theta}}\prod_{l=1}^{m_{\bm{\theta}}+2}\varepsilon_{g(k-1)+(m_{\bm{\theta}}+2)j+l}\bigg{]},\quad
k\geq 2.$ (100)

Along similar lines as above, it can be shown that

$\displaystyle a_{1}(z)$
$\displaystyle=\mathbb{P}_{\bm{\theta}}(\tau_{1}(z)>g(1))$
$\displaystyle\leq\prod_{j=0}^{\left\lfloor\frac{g(1)-g(0)-1}{m_{\bm{\theta}}+2}\right\rfloor-1}\bigg{[}1-\sigma_{\bm{\theta}}\prod_{l=1}^{m_{\bm{\theta}}+2}\varepsilon_{g(0)+(m_{\bm{\theta}}+2)j+l}\bigg{]},$
(101)

where in writing the last line, we use $g(0)=0$. Let $b_{1}$ denote the right-
hand side of (101).

As the last step in the proof, we tune $g$ and $\\{\varepsilon_{n}:n\geq 1\\}$
so that $\sum_{k=1}^{\infty}b_{k}\leq\alpha$.

Tuning $g$ and $\\{\varepsilon_{n}:n\geq 1\\}$: Noting that $\varepsilon_{n}$
is a decreasing sequence, we have

$\displaystyle b_{k}$
$\displaystyle=\prod_{j=0}^{\left\lfloor\frac{g(k)-g(k-1)-1}{m_{\bm{\theta}}+2}\right\rfloor-1}\bigg{[}1-\sigma_{\bm{\theta}}\prod_{l=1}^{m_{\bm{\theta}}+2}\varepsilon_{g(k-1)+(m_{\bm{\theta}}+2)j+l}\bigg{]}$
$\displaystyle\leq\prod_{j=0}^{\left\lfloor\frac{g(k)-g(k-1)-1}{m_{\bm{\theta}}+2}\right\rfloor-1}\left[1-\sigma_{\bm{\theta}}(\varepsilon_{g(k-1)+(m_{\bm{\theta}}+2)j+m_{\bm{\theta}}+2})^{m_{\bm{\theta}}+2}\right]$
$\displaystyle\leq\left[1-\sigma_{\bm{\theta}}(\varepsilon_{g(k)})^{m_{\bm{\theta}}+2}\right]^{\left\lfloor\frac{g(k)-g(k-1)-1}{m_{\bm{\theta}}+2}\right\rfloor}$
$\displaystyle\leq\left[1-\sigma_{\bm{\theta}}(\varepsilon_{g(k)})^{1+S_{R}}\right]^{\left\lfloor\frac{g(k)-g(k-1)-1}{1+S_{R}}\right\rfloor},$
(102)

where the last line follows from noting that $m_{\bm{\theta}}\leq S_{R}-1$.
For $g(k)=\lambda k^{4}$ where $\lambda\in\mathbb{N}$, and
$\varepsilon_{n}=n^{-\frac{1}{2(1+S_{R})}}$, we get

$\left\lfloor\frac{g(k)-g(k-1)-1}{1+S_{R}}\right\rfloor\geq\frac{\lambda\,k^{3}}{1+S_{R}},\quad(\varepsilon_{g(k)})^{1+S_{R}}=\frac{1}{k^{2}\sqrt{\lambda}}.$
(103)

Therefore, it follows that for all $k\geq 1$,

$\displaystyle b_{k}$
$\displaystyle\leq\left[1-\frac{\sigma_{\bm{\theta}}}{k^{2}\sqrt{\lambda}}\right]^{\frac{\lambda
k^{3}}{1+S_{R}}}$ $\displaystyle\leq\exp\left(-\frac{\lambda
k^{3}\,\sigma_{\bm{\theta}}}{(1+S_{R})\,k^{2}\sqrt{\lambda}}\right)$
$\displaystyle=\exp\left(-\frac{k\,\sigma_{\bm{\theta}}\,\sqrt{\lambda}}{1+S_{R}}\right).$
(104)

Using (104) in (82), we get

$\displaystyle\mathbb{P}_{\bm{\theta}}(\overline{\mathcal{H}})$
$\displaystyle\leq K\,S_{R}\,\sum_{k=1}^{\infty}b_{k}$ $\displaystyle\leq
K\,S_{R}\,\sum_{k=1}^{\infty}\exp\left(-\frac{k\,\sigma_{\bm{\theta}}\,\sqrt{\lambda}}{1+S_{R}}\right)$
$\displaystyle=\frac{K\,S_{R}\,\exp\left(-\frac{\sqrt{\lambda}\,\sigma_{\bm{\theta}}}{1+S_{R}}\right)}{1-\exp\left(-\frac{\sqrt{\lambda}\,\sigma_{\bm{\theta}}}{1+S_{R}}\right)}.$
(105)

Let $h(\lambda)$ denote the quantity on the right-hand side of (105). Then,
setting

$\lambda=\lambda_{\alpha}(\bm{\theta})=\frac{(1+S_{R})^{2}}{\sigma_{\bm{\theta}}^{2}}\log^{2}\left(1+\frac{K\,S_{R}}{\alpha}\right),$

we get $h(\lambda_{\alpha}(\bm{\theta}))=\alpha$. This completes the proof.

##  Appendix G Proof of Lemma 6.2

###### Proof.

Let

$M_{n}=\begin{pmatrix}\mathbf{1}_{\\{A_{0}=1\\}}\ \mathbf{1}_{\\{A_{0}=2\\}}\
\cdots\ \mathbf{1}_{\\{A_{0}=K\\}}\\\ \mathbf{1}_{\\{A_{1}=1\\}}\
\mathbf{1}_{\\{A_{1}=2\\}}\ \cdots\ \mathbf{1}_{\\{A_{1}=K\\}}\\\ \vdots\\\
\mathbf{1}_{\\{A_{n}=1\\}}\ \mathbf{1}_{\\{A_{n}=2\\}}\ \cdots\
\mathbf{1}_{\\{A_{n}=K\\}}\\\ \end{pmatrix},\quad
E_{n}^{1}=\begin{pmatrix}f(\bar{X}_{0})\\\ f(\bar{X}_{1})\\\ \vdots\\\
f(\bar{X}_{n})\end{pmatrix},\quad
E_{n}^{2}=\begin{pmatrix}\eta_{\theta_{1}}\\\ \eta_{\theta_{2}}\\\ \vdots\\\
\eta_{\theta_{K}}\end{pmatrix}.$ (106)

Then, we have

$\displaystyle M_{n}^{\top}M_{n}$ $\displaystyle={\rm
diag}(N_{1}(n),\ldots,N_{K}(n)),$ (107)

where ${\rm diag}(\cdot)$ refers to the operator that converts an ordered set
of elements into a diagonal matrix. Note that

$\displaystyle\widehat{\eta}_{a}(n)-\eta_{\theta_{a}}$
$\displaystyle=\frac{1}{N_{a}(n)}\sum_{t=0}^{n}\mathbf{1}_{\\{A_{t}=a\\}}\,(f(\bar{X}_{t})-\eta_{\theta_{a}})$
$\displaystyle=\frac{1}{N_{a}(n)}\,(M_{n}^{\top}E_{n}^{1}-M_{n}^{\top}M_{n}E_{n}^{2})_{a}$
$\displaystyle=\frac{1}{N_{a}(n)}\,(M_{n}^{\top}E_{n})_{a},$ (108)

where $E_{n}\coloneqq E_{n}^{1}-M_{n}E_{n}^{2}$. Consider the event

$\mathcal{E}\coloneqq\bigg{\\{}\forall(\mathbf{d},\mathbf{i},a)\in\mathbb{V},\quad\forall
n\geq K,\quad
N(n,\mathbf{d},\mathbf{i},a)\geq\left\lceil\frac{n}{\lambda_{\alpha}(\bm{\theta})}\right\rceil^{1/4}-1\bigg{\\}},$
(109)

where $\lambda_{\alpha}(\bm{\theta})$ and $\mathbb{V}$ are as defined in Lemma
6.1. Under $\mathcal{E}$, we note that for all $a\in[K]$,

$\displaystyle N_{a}(n)$
$\displaystyle=\sum_{(\mathbf{d},\mathbf{i})\in\mathbb{V}_{R,a}}N(n,\mathbf{d},\mathbf{i},a)$
$\displaystyle=\sum_{(\mathbf{d},\mathbf{i})\in\mathbb{S}_{R}}N(n,\mathbf{d},\mathbf{i},a)$
$\displaystyle\geq
S_{R}\left(\frac{n^{1/4}}{\lambda_{\alpha}(\bm{\theta})^{1/4}}-1\right)$
$\displaystyle\geq c\,n^{1/4}\qquad\forall n\geq n_{0},$ (110)

where $n_{0}$ and $c$ are defined as

$n_{0}\coloneqq\inf\left\\{n\geq K:n^{1/4}\geq
2\lambda_{\alpha}(\bm{\theta})^{1/4}\right\\},\quad
c\coloneqq\frac{S_{R}}{2\lambda_{\alpha}(\bm{\theta})^{1/4}}.$ (111)

Eq. (110) implies that $M_{n}^{\top}M_{n}$ is invertible for all $n\geq n_{0}$
under $\mathcal{E}$, in which case it follows from (108) that

$\widehat{\bm{\eta}}(n)-\bm{\eta}=(M_{n}^{\top}M_{n})^{-1}M_{n}^{\top}E_{n}\quad\forall
n\geq n_{0},$ (112)

where $\bm{\eta}\coloneqq[\eta_{\theta_{a}}:a\in[K]]^{\top}$. We then note
that under $\mathcal{E}$,

$\displaystyle\|\widehat{\bm{\eta}}(n)-\bm{\eta}\|_{2}$
$\displaystyle=\|(M_{n}^{\top}M_{n})^{-1}(M_{n}^{\top}E_{n})\|_{2}$
$\displaystyle=\sqrt{(M_{n}^{\top}E_{n})^{\top}\,(M_{n}^{\top}M_{n})^{-1}\,((M_{n}^{\top}M_{n})^{-1})^{\top}\,(M_{n}^{\top}E_{n})}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}\frac{1}{\sqrt{\min_{a}N_{a}(n)}}\,\sqrt{(M_{n}^{\top}E_{n})^{\top}\,(M_{n}^{\top}M_{n})^{-1}\,(M_{n}^{\top}E_{n})}$
$\displaystyle\leq\frac{1}{\sqrt{c}\,n^{1/8}}\sqrt{(M_{n}^{\top}E_{n})^{\top}\,(M_{n}^{\top}M_{n})^{-1}\,(M_{n}^{\top}E_{n})}$
(113)

for all $n\geq n_{0}$, where $||\cdot||_{2}$ denotes vector $2$-norm, and
$(a)$ follows by noting that each entry of
$((M_{n}^{\top}M_{n})^{-1})^{\top}={\rm
diag}\left(N_{1}(n)^{-1},\ldots,N_{K}(n)^{-1}\right)$ may be upper bounded by
$\frac{1}{\min_{a}N_{a}(n)}$. Because

$N_{a}(n)+c\,n^{1/4}<2N_{a}(n)\quad\forall n\geq n_{0},\ \forall a\in[K],$

we have
$2(M_{n}^{\top}M_{n}+c\,n^{1/4}I_{K})^{-1}\succ(M_{n}^{\top}M_{n})^{-1}$ for
all $n\geq n_{0}$, where the notation $A\succ M$ means that $A-M$ is positive
definite, and $I_{K}$ denotes the $K\times K$ identity matrix. Thus, it
follows that under $\mathcal{E}$,

$\displaystyle\|\widehat{\bm{\eta}}(n)-\bm{\eta}\|_{2}$
$\displaystyle<\frac{\sqrt{2}}{\sqrt{c}\,n^{1/8}}\sqrt{(M_{n}^{\top}E_{n})^{\top}\,(M_{n}^{\top}M_{n}+c\,n^{1/4}I_{K})^{-1}\,(M_{n}^{\top}E_{n})}\quad\forall\,n\geq
n_{0}.$ (114)

Introducing the shorthand notation $\|x\|_{A}=\sqrt{x^{\top}Ax}$ for any
positive definite matrix $A$, we show below that under $\mathcal{E}$,

$\|M_{n}^{\top}E_{n}\|_{(M_{n}^{\top}M_{n}+c\,n^{1/4}I_{K})^{-1}}=o(n^{\beta})\quad\forall\beta\in(0,1/8).$

Fix $\beta\in(0,1/8)$ arbitrarily. In order to show that
$\|M_{n}^{\top}E_{n}\|_{(M_{n}^{\top}M_{n}+c\,n^{\alpha}I_{K})^{-1}}=o(n^{\beta})$
under $\mathcal{E}$, we invoke the following result from [20].

######  Proposition G.1.

([20, Proposition 4]) Let $\\{\mathcal{F}_{n}:n\geq 0\\}$ be a filtration. Let
$\\{\mathbf{\eta}_{n}:n\geq 0\\}$ be a real-valued stochastic process with
zero mean and adapted to $\\{\mathcal{F}_{n}\\}$ (i.e., $\eta_{n}$ is
$\mathcal{F}_{n}$-measurable for all $n\geq 0$). Furthermore, suppose that
$\mathbb{E}[\exp(x\eta_{n})|\mathcal{F}_{n}]\leq\exp(-x^{2}\sigma^{2}/2)$ for
all $x\in\mathbb{R}$ and $n\geq 0$. Let $(\mathbf{a}_{n}:n\geq 0)$ be an
$\mathbb{R}^{d}$-valued process adapted to $\\{\mathcal{F}_{t}\\}$. Let $U$ be
a positive definite matrix. Then, for all $\delta>0$,

$P\left(\|Q_{n}^{\top}R_{n}\|^{2}_{(Q_{n}^{\top}Q_{n}+U)^{-1}}>2\sigma^{2}\,\log\left(\frac{\sqrt{{\rm
det}((Q_{n}^{\top}Q_{n}+U)U^{-1})}}{\delta}\right)\right)\leq\delta,$ (115)

where $Q_{n}=[\mathbf{a}_{0}\ \mathbf{a}_{1}\ \cdots\mathbf{a}_{n}]^{\top}$
and $R_{n}=[\mathbf{\eta}_{0}\ \mathbf{\eta}_{1}\
\cdots\mathbf{\eta}_{n}]^{\top}$.

Applying Proposition G.1 with the filtration in (9), $d=K$,
$U=c\,n^{1/4}I_{K}$,

$\mathbf{a}_{t}=[\mathbf{1}_{\\{A_{t}=1\\}}\ \mathbf{1}_{\\{A_{t}=2\\}}\
\cdots\
\mathbf{1}_{\\{A_{t}=K\\}}]^{\top},\quad\eta_{t}=f(\bar{X}_{t})-\sum_{a=1}^{K}\mathbf{1}_{\\{A_{t}=a\\}}\,\eta_{\theta_{a}},\quad
0\leq t\leq n,$

and $\sigma^{2}=2\,M_{f}$ (noting that $|\eta_{t}|\leq
M_{f}+\max_{a}\eta_{\theta_{a}}\leq 2\,M_{f}$ a.s. for all $t$, where
$M_{f}=\max_{i\in\mathcal{S}}f(i)$), we get that for all $\delta>0$,

$\displaystyle\mathbb{P}_{\bm{\theta}}^{\mathcal{E}}\bigg{(}\frac{1}{n^{\beta}}\|M_{n}^{\top}E_{n}\|_{(M_{n}^{\top}M_{n}+c\,n^{1/4})^{-1}}>\frac{\sqrt{2\,M_{f}}}{n^{\beta}}\,\sqrt{\log\left(\frac{\sqrt{{\rm
det}((M_{n}^{\top}M_{n}+c\,n^{1/4}I_{K})(c\,n^{1/4}I_{K})^{-1})}}{\delta}\right)}\bigg{)}\leq\delta,$
(116)

where
$\mathbb{P}_{\bm{\theta}}^{\mathcal{E}}(\cdot)=\mathbb{P}_{\bm{\theta}}(\cdot\;|\;\mathcal{E})$.
Noting that under $\mathcal{E}$,

$\displaystyle{\rm
det}((M_{n}^{\top}M_{n}+c\,n^{1/4}I_{K})(c\,n^{1/4}I_{K})^{-1})$
$\displaystyle=\prod_{a=1}^{K}\frac{N_{a}(n)+c\,n^{1/4}}{c\,n^{1/4}}$
$\displaystyle\leq\prod_{a=1}^{K}\frac{n+1+c\,n^{1/4}}{c\,n^{1/4}}$
$\displaystyle=\left(\frac{n^{3/4}}{c}+1+\frac{1}{c\,n^{1/4}}\right)^{K}$
$\displaystyle\leq\left(\frac{2n^{3/4}}{c}\right)^{K}$ (117)

for all $n\geq n_{1}$, where

$n_{1}\coloneqq\inf\left\\{n\geq
n_{0}:1+\frac{1}{c\,n^{1/4}}\leq\frac{n^{3/4}}{c}\right\\}.$ (118)

We then have

$\displaystyle\mathbb{P}_{\bm{\theta}}^{\mathcal{E}}\left(\frac{1}{n^{\beta}}\|M_{n}^{\top}E_{n}\|_{(M_{n}^{\top}M_{n}+c\,n^{1/4}I_{K})^{-1}}>\frac{\sqrt{2\,M_{f}}}{n^{\beta}}\sqrt{\log\left(\frac{2^{K/2}\,n^{3K/8}}{c^{K/2}\,\delta}\right)}\right)\leq\delta\quad\forall
n\geq n_{1}.$ (119)

Equivalently, for all $\xi>0$, we have

$\mathbb{P}_{\bm{\theta}}^{\mathcal{E}}\left(\frac{1}{n^{\beta}}\|M_{n}^{\top}E_{n}\|_{(M_{n}^{\top}M_{n}+c\,n^{1/4}I_{K})^{-1}}>\xi\right)\leq\frac{2^{K/2}\,n^{3K/8}}{c^{K/2}}\
\exp\left(-\frac{\xi^{2}\,n^{2\beta}}{2\,M_{f}}\right)\quad\forall n\geq
n_{1}.$ (120)

Using (120) in (114), we get that for any $\xi>0$,

$\mathbb{P}_{\bm{\theta}}^{\mathcal{E}}(\|\widehat{\bm{\eta}}(n)-\bm{\eta}\|>\xi)\leq\frac{2^{K/2}\,n^{3K/8}}{c^{K/2}}\
\exp\left(-\frac{c\,\xi^{2}\,n^{1/4}}{2(2\,M_{f})}\right)\quad\forall n\geq
n_{1}.$ (121)

Finally, fixing $N\geq K$ and applying (121) to the event
$\mathcal{E}=\mathcal{E}_{N}$, where $\mathcal{E}_{N}$ is as defined in (205),
and denoting the constants $n_{0}$, $c$, and $n_{1}$ more explicitly as
$n_{0}(N)$, $c_{N}$, and $n_{1}(N)$777We assume, without loss of generality,
that $N^{5}\geq\max\\{n_{0}(N),n_{1}(N)\\}$. If this is not true, we may
replace $N^{5},N^{6}$ by $N^{b},N^{b+1}$ respectively, where $b$ is any
integer satisfying $N^{b}\geq\max\\{n_{0}(N),n_{1}(N)\\}$. respectively, we
get

$\displaystyle\mathbb{P}_{\bm{\theta}}(\overline{C_{N}^{2}(\xi)})$
$\displaystyle\leq\mathbb{P}_{\bm{\theta}}(\overline{\mathcal{E}_{N}})+\mathbb{P}_{\bm{\theta}}(\overline{C_{N}^{2}(\xi)}\cap\mathcal{E}_{N})$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}\frac{1}{N^{2}}+\sum_{n=N^{5}}^{N^{6}}\mathbb{P}_{\bm{\theta}}^{\mathcal{E}_{N}}(\|\widehat{\bm{\eta}}(n)-\bm{\eta}\|>\xi)$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\leq}}\frac{1}{N^{2}}+\sum_{n=N^{5}}^{N^{6}}\frac{2^{K/2}\,n^{3K/8}}{c_{N}^{K/2}}\
\exp\left(-\frac{c_{N}\,\xi^{2}\,n^{1/4}}{2(2\,M_{f})}\right)$
$\displaystyle\stackrel{{\scriptstyle(c)}}{{\leq}}\frac{1}{N^{2}}+\frac{2^{K/2+2}\,K^{K/4}}{\sigma_{\bm{\theta}}^{K/4}}\,\sum_{n=N^{5}}^{N^{6}}n^{3K/8}\,N\,\exp\left(-\frac{\sqrt{\sigma_{\bm{\theta}}}\,\xi^{2}\,n^{1/4}}{8\,\sqrt{K}\,(2\,M_{f})\,N}\right)$
$\displaystyle\stackrel{{\scriptstyle(d)}}{{\leq}}\frac{1}{N^{2}}+\frac{2^{K/2+2}\,K^{K/4}}{\sigma_{\bm{\theta}}^{K/4}}\,N^{9K/4+1}\,\exp\left(-\frac{\sqrt{\sigma_{\bm{\theta}}}\,\xi^{2}\,N^{1/4}}{8\,\sqrt{K}\,(2\,M_{f})}\right)(N^{6}-N^{5}+1)$
$\displaystyle\leq\frac{1}{N^{2}}+\frac{2^{K/2+2}\,K^{K/4}}{\sigma_{\bm{\theta}}^{K/4}}\,N^{9K/4+7}\,\exp\left(-\frac{\sqrt{\sigma_{\bm{\theta}}}\,\xi^{2}\,N^{1/4}}{8\,\sqrt{K}\,(2\,M_{f})}\right),$
(122)

where

  * •

$(a)$ follows from noting that
$\mathbb{P}_{\bm{\theta}}(\overline{\mathcal{E}_{N}})\leq 1/N^{2}$ (applying
Lemma 6.1 with $\alpha=1/N^{2}$).

  * •

$(b)$ follows from (121) (with $c$ and $n_{1}$ replaced by $c_{N}$ and
$n_{1}(N)$ respectively).

  * •

$(c)$ follows by noting that

$\displaystyle c_{N}$
$\displaystyle=\frac{S_{R}}{2\,\lambda_{\bm{\theta}}(N)^{1/4}}$
$\displaystyle=\frac{S_{R}\sqrt{\sigma_{\bm{\theta}}}}{2\,\sqrt{1+S_{R}}\,\sqrt{\log(1+KS_{R}\,N^{2})}}$
$\displaystyle\geq\frac{S_{R}\sqrt{\sigma_{\bm{\theta}}}}{2\,\sqrt{1+S_{R}}\,\sqrt{KS_{R}\,N^{2}}}$
$\displaystyle=\frac{\sqrt{S_{R}\,\sigma_{\bm{\theta}}}}{2\,N\,\sqrt{K(1+S_{R})}}$
$\displaystyle\geq\frac{\sqrt{\sigma_{\bm{\theta}}}}{2\,N\sqrt{2K}}$
$\displaystyle\geq\frac{\sqrt{\sigma_{\bm{\theta}}}}{4\,N\,\sqrt{K}},$

where the penultimate line above follows from using $1+S_{R}\leq 2\,S_{R}$.

  * •

$(d)$ follows by noting that $n^{3K/8}<(N^{6})^{3K/8}=N^{9K/4}$ and
$n^{1/4}\geq N^{5/4}$ for $n\in\\{N^{5},\ldots,N^{6}\\}$.

This completes the proof. ∎

##  Appendix H Proof of Lemma 6.3

Before we begin the proof, we note the following results of interest.

######  Lemma H.1.

[41, Theorem 2] Let $Q_{1}$ (resp. $Q_{2}$) be the transition kernel of a
Markov chain with stationary distribution $\omega_{1}$ (resp. $\omega_{2}$).
Let $Z_{1}\coloneqq(I-Q_{1}+\mathbf{1}\omega_{1}^{\top})^{-1}$, where $I$ is
the identity matrix (of the same dimension as $Q_{1}$ and $Q_{2}$), and
$\mathbf{1}$ denotes the all-ones vector. Then,

$\omega_{2}^{\top}-\omega_{1}^{\top}=\omega_{2}^{\top}[Q_{2}-Q_{1}]\,Z_{1},\quad\|\omega_{2}-\omega_{1}\|_{1}\leq\|Z_{1}\|_{\infty}\,\|Q_{2}-Q_{1}\|_{\infty}.$
(123)

######  Lemma H.2.

[32, Lemma 23] Let $Q_{\bm{\theta,\pi}}$ be the transition kernel of MDP
$\mathcal{M}_{\bm{\theta},R}$ under policy $\pi$. Let
$\omega_{\bm{\theta},\pi}$ denote the stationary distribution of
$Q_{\bm{\theta,\pi}}$, and let

$\|Q_{\bm{\theta},\pi}^{n}-\mathbf{1}\omega_{\bm{\theta},\pi}^{\top}\|_{\infty}\leq
C_{\pi}\,\rho_{\pi}^{n}\quad\forall n\in\mathbb{N}.$ (124)

Then, for any bounded function $g$ on $\mathcal{Z}=\mathbb{S}_{R}\times[K]$,
the function

$\widehat{g}_{\pi}(z)=\sum_{n=0}^{\infty}\
\sum_{z^{\prime}\in\mathcal{Z}}Q_{\bm{\theta},\pi}^{n}(z^{\prime}|z)\,\bigg{(}g(z^{\prime})-\langle\omega_{\bm{\theta},\pi},g\rangle\bigg{)},\quad
z\in\mathcal{Z},$ (125)

is well-defined and satisfies the so-called Poisson equation

$\widehat{g}_{\pi}(z)-\sum_{z^{\prime}\in\mathcal{Z}}Q_{\bm{\theta},\pi}(z^{\prime}|z)\,\widehat{g}_{\pi}(z^{\prime})=g(z)-\langle\omega_{\bm{\theta},\pi},g\rangle\quad\forall
z\in\mathcal{Z}.$ (126)

Furthermore,

$\|\widehat{g}_{\pi}\|_{\infty}\leq L_{\pi}\,\|g\|_{\infty},$ (127)

where $L_{\pi}\coloneqq\dfrac{C_{\pi}}{1-\rho_{\pi}}$, and for any pair of
policies $\pi,\pi^{\prime}$,

$\max_{z\in\mathcal{Z}}\bigg{\lvert}\sum_{z^{\prime}\in\mathcal{Z}}Q_{\bm{\theta},\pi}(z^{\prime}|z)\,\widehat{g}_{\pi}(z^{\prime})-\sum_{z^{\prime}\in\mathcal{Z}}Q_{\bm{\theta},\pi^{\prime}}(z^{\prime}|z)\,\widehat{g}_{\pi^{\prime}}(z^{\prime})\bigg{\rvert}\leq
L_{\pi}\,\|g\|_{\infty}\bigg{[}\|\omega_{\bm{\theta},\pi}-\omega_{\bm{\theta},\pi^{\prime}}\|_{1}+L_{\pi}\,\|Q_{\bm{\theta},\pi}-Q_{\bm{\theta},\pi^{\prime}}\|_{\infty}\bigg{]}.$
(128)

###### Proof of Lemma 6.3.

We now begin the proof of Lemma 6.3. Let us fix
$z=(\mathbf{d},\mathbf{i},a)\in\mathbb{S}_{R}\times[K]$. Let

$\displaystyle D_{\bm{\theta},\nu}^{n}$
$\displaystyle\coloneqq\frac{N(n,\mathbf{d},\mathbf{i},a)}{n-K+1}-\omega_{\bm{\theta},\nu}^{\star}(\mathbf{d},\mathbf{i},a)$
$\displaystyle=\frac{1}{n-K+1}\sum_{t=K}^{n}\mathbf{1}_{\\{\mathbf{d}(t)=\mathbf{d},\mathbf{i}(t)=\mathbf{i},A_{t}=a\\}}-\omega_{\bm{\theta},\nu}^{\star}(\mathbf{d},\mathbf{i},a)$
$\displaystyle=\frac{\sum\limits_{t=K}^{\sqrt{N}}[\mathbf{1}_{\\{\mathbf{d}(t)=\mathbf{d},\mathbf{i}(t)=\mathbf{i},A_{t}=a\\}}-\omega_{\bm{\theta},\nu}^{\star}(\mathbf{d},\mathbf{i},a)]}{n-K+1}+\frac{\sum\limits_{t=\sqrt{N}+1}^{n}[\mathbf{1}_{\\{\mathbf{d}(t)=\mathbf{d},\mathbf{i}(t)=\mathbf{i},A_{t}=a\\}}-\omega_{\bm{\theta},\nu}^{\star}(\mathbf{d},\mathbf{i},a)]}{n-K+1}$
$\displaystyle=\underbrace{\frac{\sum\limits_{t=K}^{\sqrt{N}}[\mathbf{1}_{\\{\mathbf{d}(t)=\mathbf{d},\mathbf{i}(t)=\mathbf{i},A_{t}=a\\}}-\omega_{\bm{\theta},\nu}^{\star}(\mathbf{d},\mathbf{i},a)]}{n-K+1}}_{D_{\bm{\theta},\nu}^{n}(1)}+\underbrace{\frac{\sum\limits_{t=\sqrt{N}+1}^{n}[\mathbf{1}_{\\{\mathbf{d}(t)=\mathbf{d},\mathbf{i}(t)=\mathbf{i},A_{t}=a\\}}-\omega_{\bm{\theta},t-1}^{\star}(\mathbf{d},\mathbf{i},a)]}{n-K+1}}_{D_{\bm{\theta},\nu}^{n}(2)}$
$\displaystyle\hskip
142.26378pt+\underbrace{\frac{\sum\limits_{t=\sqrt{N}+1}^{n}[\omega_{\bm{\theta},t-1}^{\star}(\mathbf{d},\mathbf{i},a)-\omega_{\bm{\theta},\nu}^{\star}(\mathbf{d},\mathbf{i},a)]}{n-K+1}}_{D_{\bm{\theta},\nu}^{n}(3)},$
(129)

where for each $t\geq\sqrt{N}+1$, the quantity
$\omega_{\bm{\theta},t-1}^{\star}$ denotes the stationary distribution of the
kernel $Q_{\bm{\theta},\pi}$ under the policy
$\pi=\pi_{t-1}=\varepsilon_{t-1}\,\pi^{\text{\rm
unif}}+(1-\varepsilon_{t-1})\,\pi_{\widehat{\bm{\theta}}(t-2)}^{\eta}$
obtained by using a fixed
$\nu_{t-2}^{\star}\in\mathcal{W}^{\star}(\widehat{\bm{\theta}}(t-2))$ in
(34)); such a policy is indeed ergodic thanks to Lemma 3.3. We now upper bound
each of the terms in (129) individually. First, note that for all $n\geq
N^{3/4}$ and for all $N\geq(1/\xi)^{4}$, we have

$\displaystyle|D_{\bm{\theta},\nu}^{n}(1)|$
$\displaystyle\leq\frac{\sqrt{N}-K+1}{n-K+1}$
$\displaystyle\leq\frac{\sqrt{N}}{n}$ $\displaystyle\leq\frac{1}{\sqrt{N}}$
$\displaystyle\leq\xi.$ (130)

Next, we note using Lemma H.1 that

$\displaystyle|D_{\bm{\theta},\nu}^{n}(3)|$
$\displaystyle\leq\frac{\sum\limits_{t=\sqrt{N}+1}^{n}\bigg{\lvert}\omega_{\bm{\theta},t-1}^{\star}(\mathbf{d},\mathbf{i},a)-\omega_{\bm{\theta},\nu}^{\star}(\mathbf{d},\mathbf{i},a)\bigg{\rvert}}{n-K+1}$
$\displaystyle\leq\frac{\sum\limits_{t=\sqrt{N}+1}^{n}\|\omega_{\bm{\theta},t-1}^{\star}-\omega_{\bm{\theta},\nu}^{\star}\|_{1}}{n-K+1}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}\kappa_{\bm{\theta},\nu}\,\frac{\sum\limits_{t=\sqrt{N}+1}^{n}\|Q_{\bm{\theta},\pi_{t-1}}-Q_{\bm{\theta},\pi_{\bm{\theta}}^{\eta}(\nu)}\|_{\infty}}{n-K+1}$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{=}}\kappa_{\bm{\theta},\nu}\,\frac{\sum\limits_{t=\sqrt{N}+1}^{n}\|\varepsilon_{t-1}\,Q_{\bm{\theta},\pi^{\text{\rm
unif}}}+(1-\varepsilon_{t-1})\,Q_{\bm{\theta},\pi_{\widehat{\bm{\theta}}(t-2)}^{\eta}}-Q_{\bm{\theta},\pi_{\bm{\theta}}^{\eta}(\nu)}\|_{\infty}}{n-K+1}$
$\displaystyle\stackrel{{\scriptstyle(c)}}{{\leq}}\kappa_{\bm{\theta},\nu}\,\frac{\sum\limits_{t=\sqrt{N}+1}^{n}\varepsilon_{t-1}+\|Q_{\bm{\theta},\pi_{\widehat{\bm{\theta}}(t-2)}^{\eta}}-Q_{\bm{\theta},\pi_{\bm{\theta}}^{\eta}(\nu)}\|_{\infty}}{n-K+1}$
$\displaystyle\stackrel{{\scriptstyle(d)}}{{\leq}}\kappa_{\bm{\theta},\nu}\,\frac{\sum\limits_{t=\sqrt{N}+1}^{n}\varepsilon_{t-1}+\|\pi_{\widehat{\bm{\theta}}(t-2)}^{\eta}-\pi_{\bm{\theta}}^{\eta}(\nu)\|_{\infty}}{n-K+1},$
(131)

where
$\kappa_{\bm{\theta},\nu}=\|(I+Q_{\bm{\theta},\pi_{\bm{\theta}}^{\eta}(\nu)}+\mathbf{1}\,(\omega_{\bm{\theta},\nu}^{\star})^{\top})^{-1}\|_{\infty}$,
$(a)$ above follows from Lemma 6.3 with $\pi_{\bm{\theta}}^{\eta}(\nu)$
denoting the quantity in (34) with (i) $\widehat{\bm{\theta}}(n)$ replaced by
$\bm{\theta}$, and (ii) $\nu_{n}^{\star}$ replaced by $\nu$, $(b)$ above
follows from the definition of the transition kernel
$Q_{\bm{\theta},\pi_{t-1}}$, $(c)$ above follows from the observation that

$\displaystyle\varepsilon_{t-1}\,Q_{\bm{\theta},\pi^{\text{\rm
unif}}}+(1-\varepsilon_{t-1})\,Q_{\bm{\theta},\pi_{\widehat{\bm{\theta}}(t-2)}^{\eta}}$
$\displaystyle\leq\varepsilon_{t-1}+Q_{\bm{\theta},\pi_{\widehat{\bm{\theta}}(t-2)}^{\eta}},$
(132)

and $(d)$ above follows from the observation that

$\displaystyle\|Q_{\bm{\theta},\pi_{\widehat{\bm{\theta}}(t-2)}^{\eta}}-Q_{\bm{\theta},\pi_{\bm{\theta}}^{\eta}(\nu)}\|_{\infty}$
$\displaystyle=\|Q_{\bm{\theta},R}\,[\pi_{\widehat{\bm{\theta}}(t-2)}^{\eta}-\pi_{\bm{\theta}}^{\eta}(\nu)]\|_{\infty}$
$\displaystyle\leq\|\pi_{\widehat{\bm{\theta}}(t-2)}^{\eta}-\pi_{\bm{\theta}}^{\eta}(\nu)\|_{\infty},$

where the last line above is an artefact of $\|Q_{\bm{\theta},R}\|\leq 1$.
Thanks to Lemma 6.1, we have $\bm{\theta}(n)\to\bm{\theta}$ almost surely as
$n\to\infty$. We then note that by virtue of the upper-hemicontinuity of the
map $\bm{\lambda}\to\mathcal{W}^{\star}(\bm{\lambda})$, there exists
$N_{1}=N_{1}(\xi)>0$ and $\rho(\xi)>0$ such that for all $N\geq N_{1}$ and for
all $t\geq\sqrt{N}+1$, we have

$\displaystyle\|\pi_{\widehat{\bm{\theta}}(t-2)}^{\eta}-\pi_{\bm{\theta}}^{\eta}(\nu)\|_{\infty}$
$\displaystyle=\bigg{\|}\frac{\eta\,\nu_{\widehat{\bm{\theta}}(t-2)}^{\text{\rm
unif}}(\mathbf{d},\mathbf{i},a)+(1-\eta)\,\nu_{t-2}^{\star}(\mathbf{d},\mathbf{i},a)}{\eta\,\mu_{\widehat{\bm{\theta}}(t-2)}^{\text{\rm
unif}}(\mathbf{d},\mathbf{i})+(1-\eta)\,\sum_{a^{\prime}=1}^{K}\nu_{t-2}^{\star}(\mathbf{d},\mathbf{i},a^{\prime})}-\frac{\eta\,\nu_{{\bm{\theta}}}^{\text{\rm
unif}}(\mathbf{d},\mathbf{i},a)+(1-\eta)\,\nu(\mathbf{d},\mathbf{i},a)}{\eta\,\mu_{{\bm{\theta}}}^{\text{\rm
unif}}(\mathbf{d},\mathbf{i})+(1-\eta)\,\sum_{a^{\prime}=1}^{K}\nu(\mathbf{d},\mathbf{i},a^{\prime})}\bigg{\|}$
$\displaystyle\leq\rho(\xi).$ (133)

Using (133) in (131), we get

$|D_{\bm{\theta},\nu}^{n}(3)|\leq\kappa_{\bm{\theta},\nu}\,\rho(\xi)\quad\forall
n\geq\sqrt{N}+1,~{}\forall N\geq N_{1}(\xi).$ (134)

Lastly, in order to bound $D_{\bm{\theta},\nu}^{n}(2)$, we use the function
$\widehat{g}_{t-1}=\widehat{g}_{\pi_{t-1}}$, the solution to the Poisson
equation in (126) with $g(z)=\mathbf{1}_{\\{(\mathbf{d},\mathbf{i},a)\\}}(z)$.
From Lemma H.2, we know that $\widehat{g}_{t-1}$ exists, and using the
shorthand notation $z_{t}=(\mathbf{d}(t),\mathbf{i}(t),A_{t})$, we may express
$D_{\bm{\theta},\nu}^{n}(2)$ as

$\displaystyle D_{\bm{\theta},\nu}^{n}(2)$
$\displaystyle=\frac{\sum\limits_{t=\sqrt{N}+1}^{n}[\widehat{g}_{t-1}(z_{t})-Q_{\bm{\theta},\pi_{t-1}}\,\widehat{g}_{t-1}(z_{t})]}{n-K+1}$
$\displaystyle=D_{\bm{\theta},\nu}^{n}(2,1)+D_{\bm{\theta},\nu}^{n}(2,2)+D_{\bm{\theta},\nu}^{n}(2,3),$
(135)

where

$\displaystyle D_{\bm{\theta},\nu}^{n}(2,1)$
$\displaystyle\coloneqq\frac{\sum\limits_{t=\sqrt{N}+1}^{n}[\widehat{g}_{t-1}(z_{t})-Q_{\bm{\theta},\pi_{t-1}}\,\widehat{g}_{t-1}(z_{t-1})]}{n-K+1},$
(136) $\displaystyle D_{\bm{\theta},\nu}^{n}(2,2)$
$\displaystyle\coloneqq\frac{\sum\limits_{t=\sqrt{N}+1}^{n}[Q_{\bm{\theta},\pi_{t}}\,\widehat{g}_{t}(z_{t})-Q_{\bm{\theta},\pi_{t-1}}\,\widehat{g}_{t-1}(z_{t})]}{n-K+1},$
(137) $\displaystyle D_{\bm{\theta},\nu}^{n}(2,3)$
$\displaystyle\coloneqq\dfrac{Q_{\bm{\theta},\pi_{\sqrt{N}}}\,\widehat{g}_{\sqrt{N}}(z_{\sqrt{N}})-Q_{\bm{\theta},\pi_{n}}\,\widehat{g}_{n}(z_{n})}{n-K+1},$
(138)

Bounding $D_{\bm{\theta},\nu}^{n}(2,1)$: To bound (136), we note that
$G_{n}=(n-K+1)\,D_{\bm{\theta},\nu}^{n}(2,1)$ is a martingale. Furthermore, by
Lemma H.2, we have

$\displaystyle|G_{n}-G_{n-1}|$
$\displaystyle=\bigg{\lvert}\widehat{g}_{n-1}(z_{n})-Q_{\bm{\theta},\pi_{n-1}}\,\widehat{g}_{n-1}(z_{n-1})\bigg{\rvert}$
$\displaystyle\leq 2\,\|\widehat{g}_{n-1}\|_{\infty}$ $\displaystyle\leq
2\,\frac{C_{n-1}}{1-\rho_{n-1}},$ (139)

where $C_{n-1}$ and $\rho_{n-1}$ are constants as defined in Lemma L.2. For
all for all $n\geq\sqrt{N}+1$ and for all
$N\geq\max\\{N_{1}(\xi)+1,(1/\xi)^{4(1+S_{R})}\\}$, where $N_{1}(\xi)$ is as
defined above, we note that

$\displaystyle\varepsilon_{n-1}=(n-1)^{-\frac{1}{2(1+S_{R})}}\leq
N^{-\frac{1}{4(1+S_{R})}}\leq\xi,$ (140)
$\displaystyle\|\pi_{\widehat{\bm{\theta}}(n-2)}^{\eta}-\pi_{\bm{\theta}}^{\eta}(\nu)\|_{\infty}\leq\rho(\xi),$
(141)
$\displaystyle\|\omega_{\bm{\theta},n-1}^{\star}-\omega_{\bm{\theta},\nu}^{\star}\|_{1}\leq\varepsilon_{n-1}+\|\pi_{\widehat{\bm{\theta}}(n-2)}^{\eta}-\pi_{\bm{\theta}}^{\eta}(\nu)\|_{\infty}\|\leq
2\,\xi.$ (142)

Therefore, we have

$\displaystyle\frac{C_{n-1}}{1-\rho_{n-1}}$
$\displaystyle=\frac{2/\bar{\sigma}(\varepsilon_{n-1},\pi_{\widehat{\bm{\theta}}(n-2)}^{\eta},\omega_{\bm{\theta},n-1}^{\star})}{1-\bar{\sigma}(\varepsilon_{n-1},\pi_{\widehat{\bm{\theta}}(n-2)}^{\eta},\omega_{\bm{\theta},n-1}^{\star})}$
$\displaystyle\leq
L_{\xi}\coloneqq\max_{\begin{subarray}{c}\varepsilon:|\varepsilon|\leq\xi\\\
\pi:\|\pi-\pi_{\bm{\theta}}^{\eta}(\nu)\|_{\infty}\leq\rho(\xi)\\\
\omega:\|\omega-\omega_{\bm{\theta},\nu}^{\star}\|_{1}\leq
2\,\xi\end{subarray}}\frac{2/\bar{\sigma}(\varepsilon,\pi,\omega)}{1-\bar{\sigma}(\varepsilon,\pi,\omega)}.$
(143)

In (143), $\bar{\sigma}$ is as defined in (196). Using (139), (143), and the
Azuma-Hoeffding inequality for bounded martingale sequences, we get

$\displaystyle\mathbb{P}_{\bm{\theta}}\bigg{(}|D_{\bm{\theta},\nu}^{n}(2,1)|\geq
2\,L_{\xi}\,\xi\bigg{)}$
$\displaystyle=\mathbb{P}_{\bm{\theta}}\bigg{(}|G_{n}|\geq(n-K+1)\,2\,L_{\xi}\,\xi\bigg{)}$
$\displaystyle=O\bigg{(}\exp(-n\,\xi^{2})\bigg{)}\quad\forall
n\geq\sqrt{N}+1,~{}\forall N\geq\max\\{N_{1}(\xi),(1/\xi)^{4(1+S_{R})}\\}.$
(144)

Bounding $D_{\bm{\theta},\nu}^{n}(2,2)$: Writing $L_{t}=C_{t}/(1-\rho_{t})$
for all $t$, we note from Lemma H.2 that

$\displaystyle|D_{\bm{\theta},\nu}^{n}(2,2)|$
$\displaystyle=\frac{\sum\limits_{t=\sqrt{N}+1}^{n}L_{t}\bigg{[}\|\omega_{\bm{\theta},t}^{\star}-\omega_{\bm{\theta},t-1}^{\star}\|_{1}+L_{t-1}\,\|Q_{\bm{\theta},\pi_{t}}-Q_{\bm{\theta},\pi_{t-1}}\|_{\infty}\bigg{]}}{n-K+1}$
$\displaystyle\leq\frac{\sum\limits_{t=\sqrt{N}+1}^{n}L_{\xi}\bigg{[}\|\omega_{\bm{\theta},t}^{\star}-\omega_{\bm{\theta},\nu}^{\star}\|_{1}+\|\omega_{\bm{\theta},t-1}^{\star}-\omega_{\bm{\theta},\nu}^{\star}\|_{1}+L_{\xi}\,\|Q_{\bm{\theta},\pi_{t}}-Q_{\bm{\theta},\pi_{t-1}}\|_{\infty}\bigg{]}}{n-K+1}.$
(145)

We then note that

$\displaystyle\|Q_{\bm{\theta},\pi_{t}}-Q_{\bm{\theta},\pi_{t-1}}\|_{\infty}$
$\displaystyle\leq\|Q_{\bm{\theta},\pi_{t}}-Q_{\bm{\theta},\pi_{\bm{\theta}}^{\eta}(\nu)}\|+\|Q_{\bm{\theta},\pi_{t-1}}-Q_{\bm{\theta},\pi_{\bm{\theta}}^{\eta}(\nu)}\|$
$\displaystyle\leq\varepsilon_{t-1}+\varepsilon_{t}+\|\pi_{\widehat{\bm{\theta}}(t-1)}^{\eta}-\pi_{\bm{\theta}}^{\eta}(\nu)\|_{\infty}+\|\pi_{\widehat{\bm{\theta}}(t-2)}^{\eta}-\pi_{\bm{\theta}}^{\eta}(\nu)\|_{\infty}$
$\displaystyle\leq 2\,\varepsilon_{t}+2\,\xi\quad\forall t\geq N_{1}(\xi)+1$
$\displaystyle\leq 2\,t^{-\frac{1}{2(1+S_{R})}}+2\,\xi\quad\forall t\geq
N_{1}(\xi)+1$ $\displaystyle\leq 4\xi\quad\forall
t\geq\max\\{N_{1}(\xi)+1,(1/\xi)^{2(1+S_{R})}\\},$ (146)

where the second line follows from (132), and the third line follows from
using $\varepsilon_{t-1}>\varepsilon_{t}$. Plugging (146) in (145), we get

$\displaystyle|D_{\bm{\theta},\nu}^{n}(2,2)|$
$\displaystyle\leq\frac{\sum\limits_{t=\sqrt{N}+1}^{n}L_{\xi}\bigg{[}\|\omega_{\bm{\theta},t}^{\star}-\omega_{\bm{\theta},\nu}^{\star}\|_{1}+\|\omega_{\bm{\theta},t-1}^{\star}-\omega_{\bm{\theta},\nu}^{\star}\|_{1}+4\,L_{\xi}\,\xi\bigg{]}}{n-K+1}$
$\displaystyle\leq
L_{\xi}\bigg{[}2\,\kappa_{\bm{\theta},\nu}\,\rho(\xi)+4\,L_{\xi}\,\xi\bigg{]},$
(147)

where the last line above follows from using the chain of inequalities in
(131) along with (132) and (133).

Bounding $D_{\bm{\theta},\nu}^{n}(2,3)$: To bound (138), we note that

$\displaystyle|D_{\bm{\theta},\nu}^{n}(2,3)|$
$\displaystyle\leq\bigg{\lvert}\dfrac{Q_{\bm{\theta},\pi_{\sqrt{N}}}\,\widehat{g}_{\sqrt{N}}(z_{\sqrt{N}})-Q_{\bm{\theta},\pi_{n}}\,\widehat{g}_{n}(z_{n})}{n-K+1}\bigg{\rvert}$
$\displaystyle\leq\dfrac{\|\widehat{g}_{\sqrt{N}}\|_{\infty}+\|\widehat{g}_{\sqrt{n}}\|_{\infty}}{n-K+1}$
$\displaystyle\leq\frac{L_{\sqrt{N}}+L_{\sqrt{n}}}{n-K+1}$
$\displaystyle\leq\frac{2\,L_{\xi}}{n-K+1}$ $\displaystyle\leq
2\,L_{\xi}\,\xi\quad\forall n\geq 1/\xi+K-1,$ (148)

where the second line above follows from using
$\|Q_{\bm{\theta},\pi_{\sqrt{N}}}\|_{\infty}\leq 1$,
$\|Q_{\bm{\theta},\pi_{\sqrt{n}}}\|_{\infty}\leq 1$, and the second line above
follows from Lemma H.2.

Combining all of the results above, we get for every
$(\mathbf{d},\mathbf{i},a)\in\mathbb{S}_{R}\times[K]$,

$\displaystyle\mathbb{P}_{\bm{\theta}}\left(\left\lvert\frac{N(n,\mathbf{d},\mathbf{i},a)}{n-K+1}-\omega_{\bm{\theta},\nu}^{\star}(\mathbf{d},\mathbf{i},a)\right\rvert>K_{\xi}(\bm{\theta},\nu)\,\xi\right)=O\bigg{(}\exp\left(-n\xi^{2}\right)\bigg{)},$
(149)

where $K_{\xi}(\bm{\theta},\nu)\coloneqq
1+\kappa_{\bm{\theta},\nu}\,\frac{\rho(\xi)}{\xi}+4\,L_{\xi}+L_{\xi}\bigg{[}2\,\kappa_{\bm{\theta},\nu}\,\frac{\rho(\xi)}{\xi}+4\,L_{\xi}\bigg{]}$.
Noting that

$\lim_{\xi\downarrow
0}L_{\xi}=\frac{2/\bar{\sigma}(0,\pi_{\bm{\theta}}(\nu),\omega_{\bm{\theta},\nu}^{\star})}{1-\bar{\sigma}(0,\pi_{\bm{\theta}}(\nu),\omega_{\bm{\theta},\nu}^{\star})}<+\infty,\quad\lim_{\xi\downarrow
0}\frac{\rho(\xi)}{\xi}=0,$

we get $\limsup_{\xi\downarrow 0}K_{\xi}(\bm{\theta},\nu)<+\infty$. The final
result in (46) follows from (149) via union bound. ∎

##  Appendix I Proof of Proposition 6.4

Our proof is inspired by the proof of Lemma 15 in [32], which in turn is
inspired by the proof of Proposition 1 in [42] that is based on the idea of
constructing mixture martingales. Note that

$\displaystyle\mathbb{P}_{\bm{\theta}}(\tau<\infty,\
\eta_{\widehat{a}}<\eta_{a^{\star}(\bm{\theta})})$
$\displaystyle=\mathbb{P}_{\bm{\theta}}(\exists n\geq K:\tau_{\pi}=n,\
\eta_{\widehat{a}}<\eta_{a^{\star}(\bm{\theta})})$
$\displaystyle\leq\mathbb{P}_{\bm{\theta}}(\exists n\geq
K:Z(n)\geq\zeta(n,\delta),\ \eta_{\widehat{a}}<\eta_{a^{\star}(\bm{\theta})})$
$\displaystyle=\mathbb{P}_{\bm{\theta}}\left(\exists n\geq
K:\inf_{\bm{\lambda}\in\textsc{Alt}(\widehat{\bm{\theta}}(n)}\sum_{(\mathbf{d},\mathbf{i})\in\mathbb{S}_{R}}\
\sum_{a=1}^{K}N(n,\mathbf{d},\mathbf{i},a)\,D_{\text{\rm
KL}}(\widehat{Q}_{n}(\cdot\mid\mathbf{d},\mathbf{i},a)\|Q_{\bm{\lambda},R}(\cdot\mid\mathbf{d},\mathbf{i},a))\geq\zeta(n,\delta),\
\eta_{\widehat{a}}<\eta_{a^{\star}(\bm{\theta})}\right)$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}\mathbb{P}_{\bm{\theta}}\left(\exists
n\geq K:\sum_{(\mathbf{d},\mathbf{i})\in\mathbb{S}_{R}}\
\sum_{a=1}^{K}N(n,\mathbf{d},\mathbf{i},a)\,D_{\text{\rm
KL}}(\widehat{Q}_{n}(\cdot\mid\mathbf{d},\mathbf{i},a)\|Q_{\bm{\theta},R}(\cdot\mid\mathbf{d},\mathbf{i},a))\geq\zeta(n,\delta),\
\eta_{\widehat{a}}<\eta_{a^{\star}(\bm{\theta})}\right)$
$\displaystyle\leq\mathbb{P}_{\bm{\theta}}\left(\exists n\geq
K:\sum_{(\mathbf{d},\mathbf{i})\in\mathbb{S}_{R}}\
\sum_{a=1}^{K}N(n,\mathbf{d},\mathbf{i},a)\,D_{\text{\rm
KL}}(\widehat{Q}_{n}(\cdot\mid\mathbf{d},\mathbf{i},a)\|Q_{\bm{\theta},R}(\cdot\mid\mathbf{d},\mathbf{i},a))\geq\zeta(n,\delta)\right),$
(150)

where $(a)$ above follows by noting that
$\bm{\theta}\in\textsc{Alt}(\widehat{\bm{\theta}}(n))$ under the event
$\\{\eta_{\widehat{a}}<\eta_{a^{\star}(\bm{\theta})}\\}$. Below, we construct
a martingale $\\{M_{n}\\}_{n=K}^{\infty}$ such that for all $n\geq K$,

$\displaystyle M_{n}$
$\displaystyle\geq\exp\bigg{(}\sum_{(\mathbf{d},\mathbf{i})\in\mathbb{S}_{R}}\
\sum_{a=1}^{K}N(n,\mathbf{d},\mathbf{i},a)\,D_{\text{\rm
KL}}(\widehat{Q}_{n}(\cdot\mid\mathbf{d},\mathbf{i},a)\|Q_{\bm{\theta},R}(\cdot\mid\mathbf{d},\mathbf{i},a))$
$\displaystyle\hskip
113.81102pt-(S_{R}-1)\,\sum_{(\mathbf{d},\mathbf{i})\in\mathbb{S}_{R}}\
\sum_{a=1}^{K}\,\log\left(e\left[1+\frac{N(n,\mathbf{d},\mathbf{i},a)}{S_{R}-1}\right]\right)\bigg{)}\quad\text{almost
surely}.$ (151)

Then, using Doob’s maximal inequality, we argue that

$\mathbb{P}_{\bm{\theta}}(\exists n\geq K:M_{n}>1/\delta)\leq\delta,$ (152)

which straightforwardly proves the desired result.

Preliminary notations:

We start with some notations. Given $\bm{\gamma}\in\mathbb{R}^{S_{R}-1}$ and a
probability distribution $\bm{p}=(p_{1},\ldots,p_{S_{R}})$ on
$\mathbb{S}_{R}$, let

$\langle\bm{\gamma},\bm{p}\rangle\coloneqq
p_{S_{R}}+\sum_{s=1}^{S_{R}-1}p_{s}\,\lambda_{s},\quad\phi_{\bm{p}}(\bm{\gamma})\coloneqq\log\left(p_{S_{R}}+\sum_{s=1}^{S_{R}-1}p_{s}\,e^{\lambda_{s}}\right).$
(153)

Given $(\mathbf{d},\mathbf{i},a)\in\mathbb{S}_{R}$, let
$\phi_{\bm{\theta},\mathbf{d},\mathbf{i},a}(\bm{\gamma})=\phi_{Q_{\bm{\theta},R}(\cdot\mid\mathbf{d},\mathbf{i},a)}(\bm{\gamma})$.
Define $N(K-1,\mathbf{d},\mathbf{i},a)=0$ for all
$(\mathbf{d},\mathbf{i},a)\in\mathbb{S}_{R}\times[K]$.

Construction of a martingale for each state-action:

Fix $(\mathbf{d},\mathbf{i},a)\in\mathbb{S}_{R}\times[K]$ and
$\bm{\gamma}\in\mathbb{R}^{S_{R}-1}$. Let

$M_{n}^{\bm{\gamma}}(\mathbf{d},\mathbf{i},a)\coloneqq\exp\left(N(n,\mathbf{d},\mathbf{i},a)\,\left[\langle\bm{\gamma},\widehat{Q}_{n}(\cdot\mid\mathbf{d},\mathbf{i},a)\rangle-\phi_{\bm{\theta},\mathbf{d},\mathbf{i},a}(\bm{\gamma})\right]\right),\quad
n\geq K-1,$ (154)

where $\widehat{Q}_{n}$ is as defined in (37). Then,
$\\{M_{n}^{\bm{\gamma}}(\mathbf{d},\mathbf{i},a)\\}_{n=K-1}^{\infty}$ is a
martingale with respect to the filtration defined in (9). Indeed, using the
shorthand notation $z_{n}=(\mathbf{d}(n),\mathbf{i}(n),A_{n})$, we note that
almost surely,

$\displaystyle\mathbb{E}_{\bm{\theta}}[M_{n}^{\bm{\gamma}}(\mathbf{d},\mathbf{i},a)|\mathcal{F}_{n-1},z_{n}=(\mathbf{d},\mathbf{i},a)]$
(155)
$\displaystyle=\mathbb{E}_{\bm{\theta}}\left[\exp\left(N(n,\mathbf{d},\mathbf{i},a)\,\left[\langle\bm{\gamma},\widehat{Q}_{n}(\cdot\mid\mathbf{d},\mathbf{i},a)\rangle-\phi_{\bm{\theta},\mathbf{d},\mathbf{i},a}(\bm{\gamma})\right]\right)\bigg{|}\mathcal{F}_{n-1},z_{n}=(\mathbf{d},\mathbf{i},a)\right]$
$\displaystyle=\mathbb{E}_{\bm{X}\sim
Q_{\bm{\theta},R}(\cdot\mid\mathbf{d},\mathbf{i},a)}\bigg{[}\exp\bigg{(}(N(n-1,\mathbf{d},\mathbf{i},a)+1)\,\bigg{[}\left\langle\bm{\gamma},\frac{N(n-1,\mathbf{d},\mathbf{i},a)\,\widehat{Q}_{n-1}(\cdot\mid\mathbf{d},\mathbf{i},a)+\bm{X}}{N(n-1,\mathbf{d},\mathbf{i},a)+1}\right\rangle$
$\displaystyle\hskip
341.43306pt-\phi_{\bm{\theta},\mathbf{d},\mathbf{i},a}(\bm{\gamma})\bigg{]}\bigg{)}\bigg{|}\mathcal{F}_{n-1}\bigg{]}$
$\displaystyle=\mathbb{E}_{\bm{X}\sim
Q_{\bm{\theta},R}(\cdot\mid\mathbf{d},\mathbf{i},a)}\left[M_{n-1}^{\bm{\gamma}}(\mathbf{d},\mathbf{i},a)\exp\left(\langle\bm{\gamma},\bm{X}\rangle-\phi_{\mathbf{d},\mathbf{i},a}(\bm{\gamma})\right)\bigg{|}\mathcal{F}_{n-1}\right]$
$\displaystyle=M_{n-1}^{\bm{\gamma}}(\mathbf{d},\mathbf{i},a).$ (156)

In the above set of equalities,
$\bm{X}=[\mathbf{1}_{\\{\mathbf{d}(n+1)=\mathbf{d}^{\prime},\mathbf{i}(n+1)=\mathbf{i}^{\prime}\\}}:(\mathbf{d}^{\prime},\mathbf{i}^{\prime})\in\mathbb{S}_{R}]^{\top}$,
and the last line follows by noting that

$\log\mathbb{E}_{\bm{X}\sim
Q_{\bm{\theta},R}(\cdot\mid\mathbf{d},\mathbf{i},a)}[\exp(\langle\bm{\gamma},\bm{X}\rangle)]=\phi_{\mathbf{d},\mathbf{i},a}(\bm{\gamma}).$
(157)

When $z_{n}\neq(\mathbf{d},\mathbf{i},a)$, we have
$N(n,\mathbf{d},\mathbf{i},a)=N(n-1,\mathbf{d},\mathbf{i},a)$ and
$\widehat{Q}_{n}(\cdot\mid\mathbf{d},\mathbf{i},a)=\widehat{Q}_{n-1}(\cdot\mid\mathbf{d},\mathbf{i},a)$,
and therefore
$\mathbb{E}_{\bm{\theta}}[M_{n}^{\bm{\gamma}}(\mathbf{d},\mathbf{i},a)M_{n}\mid\mathcal{F}_{n-1},z_{n}\neq(\mathbf{d},\mathbf{i},a)]=M_{n-1}^{\bm{\gamma}}(\mathbf{d},\mathbf{i},a)$
holds trivially.

Construction of a mixture martingale:

For each $(\mathbf{d},\mathbf{i},a)\in\mathbb{S}_{R}\times[K]$, we now
construct a mixture of the martingales
$\\{M_{n}^{\bm{\gamma}}(\mathbf{d},\mathbf{i},a)\\}_{n=K-1}^{\infty}$ as
follows. For any $\bm{\gamma}\in\mathbb{R}^{S_{R}-1}$ and probability
distribution $\bm{p}$ on $\mathbb{S}_{R}$, let
$\\{\bm{p}^{\bm{\gamma}}:\bm{\gamma}\in\mathbb{R}^{S_{R}-1}\\}$ denote the
exponential family generated by $\bm{p}$ with the corresponding parameters
defined by $\bm{\gamma}$, i.e., for any $s\in\mathbb{S}_{R}$, the $s$-th
component $p_{s}^{\bm{\gamma}}$ of $\bm{p}^{\bm{\gamma}}$ is given by

$p_{s}^{\bm{\gamma}}=\frac{p_{s}\,e^{\gamma_{s}}}{p_{S_{R}}+\sum_{s=1}^{S_{R}-1}p_{s}\,e^{\gamma_{s}}},$
(158)

where $\gamma_{S_{R}}=0$ by convention. Then, it follows that for any fixed
probability distribution $\bm{p}$ on $\mathbb{S}_{R}$, the mapping in (158)
defines a bijection between $\mathbb{R}^{S_{R}-1}$ and the space of
probability distributions on $\mathbb{S}_{R}$. Given any probability
distribution $p$ on $\mathbb{S}_{R}$, let $\bm{\gamma}_{\bm{p}}$ denote the
value of $\bm{\gamma}\in\mathbb{R}^{m-1}$ such that
$\bm{p}^{\bm{\gamma}_{\bm{p}}}=\bm{p}$. For later use, we record the below
result from [42] specialized to our setting.

######  Lemma I.1.

[42, Lemma 3] For any two probability distributions $\bm{p},\bm{p}^{\prime}$
on $\mathbb{S}_{R}$ and $\bm{\gamma}\in\mathbb{R}^{S_{R}-1}$,

$\langle\bm{\gamma},\bm{p}^{\prime}\rangle-\phi_{\bm{p}}(\bm{\gamma})=D_{\text{\rm
KL}}(\bm{p}^{\prime}\|\bm{p})-D_{\text{\rm
KL}}(\bm{p}^{\prime}\|\bm{p}^{\bm{\gamma}}),$ (159)

where $p^{\bm{\gamma}}$ denotes the member of the exponential family generated
by $\bm{p}$ with parameters given by $\bm{\gamma}$, defined via (158).

Consider the following mixture of martingales obtained by choosing $\bm{p}$
according to the Dirichlet distribution $\mathcal{D}(1,\ldots,1)$ on the
simplex of dimension $S_{R}-1$:

$M_{n}(\mathbf{d},\mathbf{i},a)=\int
M_{n}^{\bm{\gamma}_{\bm{p}}}(\mathbf{d},\mathbf{i},a)\,\frac{\prod_{s=1}^{S_{R}}p_{s}}{(\prod_{s=1}^{S_{R}}\Gamma(1))/\Gamma(S_{R})}\,\mathrm{d}p_{1}\cdots\mathrm{d}p_{S_{R}},\quad
n\geq K-1.$ (160)

Clearly, because a convex combination of martingales is a martingale, the
mixture in (160) defines a martingale. Also, in (160), $\Gamma(\cdot)$ denotes
the Gamma function with the property that $\Gamma(k)=(k-1)!$ for all
$k\in\mathbb{N}$.

An almost sure lower bound on $M_{n}(\mathbf{d},\mathbf{i},a)$:

We note that for each $(\mathbf{d},\mathbf{i},a)\in\mathbb{S}_{R}\times[K]$,
almost surely,

$\displaystyle M_{n}(\mathbf{d},\mathbf{i},a)$
$\displaystyle=\int\exp\left(N(n,\mathbf{d},\mathbf{i},a)\,\left[\langle\bm{\gamma}_{\bm{p}},\widehat{Q}_{n}(\cdot\mid\mathbf{d},\mathbf{i},a)\rangle-\phi_{\bm{\theta},\mathbf{d},\mathbf{i},a}(\bm{\gamma})\right]\right)\,\frac{\prod_{s=1}^{S_{R}}p_{s}}{(\prod_{s=1}^{S_{R}}\Gamma(1))/\Gamma(S_{R})}\,\mathrm{d}p_{1}\cdots\mathrm{d}p_{S_{R}}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}\int\exp\left(N(n,\mathbf{d},\mathbf{i},a)\,\left[D_{\text{\rm
KL}}(\widehat{Q}_{n}(\cdot\mid\mathbf{d},\mathbf{i},a)\|Q_{\bm{\theta},R}(\cdot\mid\mathbf{d},\mathbf{i},a))-D_{\text{\rm
KL}}(\widehat{Q}_{n}(\cdot\mid\mathbf{d},\mathbf{i},a)\|\bm{p})\right]\right)\,(S_{R}-1)!\,\mathrm{d}p_{1}\cdots\mathrm{d}p_{S_{R}}$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{=}}\exp\left(N(n,\mathbf{d},\mathbf{i},a)\,\left[D_{\text{\rm
KL}}(\widehat{Q}_{n}(\cdot\mid\mathbf{d},\mathbf{i},a)\|Q_{\bm{\theta},R}(\cdot\mid\mathbf{d},\mathbf{i},a))+H(\widehat{Q}_{n}(\cdot\mid\mathbf{d},\mathbf{i},a))\right]\right)$
$\displaystyle\hskip
199.16928pt\cdot(S_{R}-1)!\cdot\int\prod_{s\in\mathbb{S}_{R}}p_{s}^{1+N(n,\mathbf{d},\mathbf{i},a)\,\widehat{Q}_{n}(s|\mathbf{d},\mathbf{i},a)}\mathrm{d}p_{1}\cdots\mathrm{d}p_{S_{R}}$
$\displaystyle\stackrel{{\scriptstyle(c)}}{{=}}\exp\left(N(n,\mathbf{d},\mathbf{i},a)\,\left[D_{\text{\rm
KL}}(\widehat{Q}_{n}(\cdot\mid\mathbf{d},\mathbf{i},a)\|Q_{\bm{\theta},R}(\cdot\mid\mathbf{d},\mathbf{i},a))+H(\widehat{Q}_{n}(\cdot\mid\mathbf{d},\mathbf{i},a))\right]\right)$
$\displaystyle\hskip
199.16928pt\cdot\frac{1}{\binom{N(n,\mathbf{d},\mathbf{i},a)}{N(n,\mathbf{d},\mathbf{i},a)\,\widehat{Q}_{n}(\cdot\mid\mathbf{d},\mathbf{i},a)}}\cdot\frac{1}{\binom{N(n,\mathbf{d},\mathbf{i},a)+S_{R}-1}{S_{R}-1}},$
(161)

where in the above set of equalities, $(a)$ follows from the application of
Lemma I.1 to $\bm{p}=Q_{\bm{\theta},R}(\cdot\mid\mathbf{d},\mathbf{i},a)$,
$\bm{\gamma}=\bm{\gamma}_{\bm{p}}$, and
$\bm{p}^{\prime}=\widehat{Q}_{n}(\cdot\mid\mathbf{d},\mathbf{i},a)$,
$H(\cdot)$ in $(b)$ denotes the Shannon entropy of the argument probability
distribution, and in $(c)$, the notation $\binom{N}{\bm{x}}$ for any integer
$N\in\mathbb{N}$ and a vector $\bm{x}=[x_{1},\ldots,x_{N}]$ with
$\sum_{i=1}^{N}x_{i}=N$ denotes the quantity

$\binom{N}{\bm{x}}=\frac{N!}{\prod_{i=1}^{N}x_{i}!},$

whereas for any two integers $N,m\in\mathbb{N}$ such that $N>m$, the notation
$\binom{N}{m}$ denotes the quantity

$\binom{N}{m}=\frac{N!}{m!\times(N-m)!}.$

We now use the below result to upper bound the binomial coefficients appearing
in (161).

######  Lemma I.2.

[43, Theorem 11.1.3] For any integers $N,m\in\mathbb{N}$ such that $N>m$ and a
non-negative vector $\bm{x}=[x_{1},\ldots,x_{N}]$ such that
$\sum_{i=1}^{N}x_{i}=N$,

$\binom{N}{\bm{x}}=\frac{N!}{\prod_{i=1}^{N}x_{i}!}\leq\exp\left(N\,H(\bm{x}/N)\right),\quad\binom{N}{m}\leq\exp\left(N\,H(m/N)\right),$
(162)

where $H(\bm{x}/N)$ denotes the Shannon entropy of the discrete probability
distribution $\bm{x}/N\coloneqq[x_{1}/N,\ldots,x_{N}/N]$, and $H(m/N)$ denotes
the Shannon entropy of the Bernoulli distribution with mean $m/N$.

Using Lemma I.2 to upper bound the binomial coefficients in (161), and
simplifying the resulting expression, we get

$\displaystyle M_{n}(\mathbf{d},\mathbf{i},a)$
$\displaystyle\geq\exp\bigg{(}N(n,\mathbf{d},\mathbf{i},a)\,D_{\text{\rm
KL}}(\widehat{Q}_{n}(\cdot\mid\mathbf{d},\mathbf{i},a)\|Q_{\bm{\theta},R}(\cdot\mid\mathbf{d},\mathbf{i},a))$
$\displaystyle\hskip
142.26378pt-(N(n,\mathbf{d},\mathbf{i},a)+S_{R}-1)H((S_{R}-1)/(N(n,\mathbf{d},\mathbf{i},a)+S_{R}-1))\bigg{)}$
(163)

almost surely for every $(\mathbf{d},\mathbf{i},a)\in\mathbb{S}_{R}\times[K]$.

A product martingale and proof completion:

Taking product over all $(\mathbf{d},\mathbf{i},a)\in\mathbb{S}_{R}\times[K]$
in (163), we have almost surely

$\displaystyle M_{n}$
$\displaystyle\coloneqq\prod_{(\mathbf{d},\mathbf{i},a)\in\mathbb{S}_{R}\times[K]}M_{n}(\mathbf{d},\mathbf{i},a)$
$\displaystyle\geq\exp\bigg{(}\sum_{(\mathbf{d},\mathbf{i},a)\in\mathbb{S}_{R}\times[K]}N(n,\mathbf{d},\mathbf{i},a)\,D_{\text{\rm
KL}}(\widehat{Q}_{n}(\cdot\mid\mathbf{d},\mathbf{i},a)\|Q_{\bm{\theta},R}(\cdot\mid\mathbf{d},\mathbf{i},a))$
$\displaystyle\hskip
85.35826pt-\sum_{(\mathbf{d},\mathbf{i},a)\in\mathbb{S}_{R}\times[K]}(N(n,\mathbf{d},\mathbf{i},a)+S_{R}-1)H((S_{R}-1)/(N(n,\mathbf{d},\mathbf{i},a)+S_{R}-1))\bigg{)}.$
(164)

We now prove that $\\{M_{n}\\}_{n=K-1}^{\infty}$ is a martingale and note that
for each $(\mathbf{d},\mathbf{i},a)\in\mathbb{S}_{R}\times[K]$,

$\displaystyle(N(n,\mathbf{d},\mathbf{i},a)+S_{R}-1)H((S_{R}-1)/(N(n,\mathbf{d},\mathbf{i},a)+S_{R}-1))$
$\displaystyle=(S_{R}-1)\,\log\left(1+\frac{N(n,\mathbf{d},\mathbf{i},a)}{S_{R}-1}\right)+N(n,\mathbf{d},\mathbf{i},a)\,\log\left(1+\frac{S_{R}-1}{N(n,\mathbf{d},\mathbf{i},a)}\right)$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}(S_{R}-1)\,\log\left(1+\frac{N(n,\mathbf{d},\mathbf{i},a)}{S_{R}-1}\right)+(S_{R}-1)$
$\displaystyle=(S_{R}-1)\,\log\left(e\left[1+\frac{N(n,\mathbf{d},\mathbf{i},a)}{S_{R}-1}\right]\right),$
(165)

where $(a)$ above follows from the inequality $\log(1+x)\leq x$. The fact that
$\\{M_{n}\\}_{n=K-1}^{\infty}$ is a martingale (with respect to the filtration
in (9)) follows by noting that for any
$(\mathbf{d},\mathbf{i},a)\in\mathbb{S}_{R}\times[K]$, using the shorthand
notation $z_{n}=(\mathbf{d}(n),\mathbf{i}(n),A_{n})$, we have

$\displaystyle\mathbb{E}_{\bm{\theta}}[M_{n}\mid\mathcal{F}_{n-1},z_{n}=(\mathbf{d},\mathbf{i},a)]$
$\displaystyle=\mathbb{E}_{\bm{\theta}}\bigg{[}M_{n}(\mathbf{d},\mathbf{i},a)\times\prod_{(\mathbf{d}^{\prime},\mathbf{i}^{\prime},a^{\prime})\neq(\mathbf{d},\mathbf{i},a)}M_{n}(\mathbf{d}^{\prime},\mathbf{i}^{\prime},a^{\prime})~{}\bigg{|}~{}\mathcal{F}_{n-1},\
z_{n}=(\mathbf{d},\mathbf{i},a)\bigg{]}$
$\displaystyle=\mathbb{E}_{\bm{\theta}}\bigg{[}M_{n}(\mathbf{d},\mathbf{i},a)\times\prod_{(\mathbf{d}^{\prime},\mathbf{i}^{\prime},a^{\prime})\neq(\mathbf{d},\mathbf{i},a)}M_{n-1}(\mathbf{d}^{\prime},\mathbf{i}^{\prime},a^{\prime})~{}\bigg{|}~{}\mathcal{F}_{n-1}\bigg{]}$
$\displaystyle=\mathbb{E}_{\bm{\theta}}\bigg{[}M_{n}(\mathbf{d},\mathbf{i},a)\mid\mathcal{F}_{n-1}\bigg{]}\times\prod_{(\mathbf{d}^{\prime},\mathbf{i}^{\prime},a^{\prime})\neq(\mathbf{d},\mathbf{i},a)}M_{n-1}(\mathbf{d}^{\prime},\mathbf{i}^{\prime},a^{\prime})$
$\displaystyle=M_{n-1}(\mathbf{d},\mathbf{i},a)\times\prod_{(\mathbf{d}^{\prime},\mathbf{i}^{\prime},a^{\prime})\neq(\mathbf{d},\mathbf{i},a)}M_{n-1}(\mathbf{d}^{\prime},\mathbf{i}^{\prime},a^{\prime})$
$\displaystyle=M_{n-1},$ (166)

where the third line follows by noting that conditioned on
$\mathcal{F}_{n-1}$, the random variable $M_{n}(\mathbf{d},\mathbf{i},a)$ is
independent of
$\\{M_{n-1}(\mathbf{d}^{\prime},\mathbf{i}^{\prime},a^{\prime}):(\mathbf{d}^{\prime},\mathbf{i}^{\prime},a^{\prime})\neq(\mathbf{d},\mathbf{i},a)\\}$.
Applying $\mathbb{E}_{\bm{\theta}}[\cdot]$ on either side of (166) and using
the tower property of conditional expectations, we have

$\displaystyle\mathbb{E}_{\bm{\theta}}[M_{n}]=\mathbb{E}_{\bm{\theta}}[\mathbb{E}_{\bm{\theta}}[M_{n}\mid\mathcal{F}_{n-1},z_{n}]\mid\mathcal{F}_{n-1}]=M_{n-1}.$
(167)

Noting that
$\mathbb{E}_{\bm{\theta}}[M_{n}]=\mathbb{E}_{\bm{\theta}}[M_{K-1}]=1$ for all
$n\geq K-1$, and using Doob’s maximal inequality, we get

$\mathbb{P}_{\bm{\theta}}\left(\exists n\geq
K-1:M_{n}>\frac{1}{\delta}\right)\leq\delta\,\mathbb{E}_{\bm{\theta}}[M_{K-1}]=\delta.$
(168)

Clearly, (168) implies (152), thus proving the desired result.

##  Appendix J Proof of Proposition 6.5

Fix $\delta\in(0,1)$ and $\eta\in(0,1)$. Fix an arbitrary
$\nu\in\mathcal{W}^{\star}(\bm{\theta})$, and let
$\omega_{\bm{\theta},\nu}^{\star}$ be as defined in Lemma 6.3. Consider the
event

$\mathcal{E}=\left\\{\lim_{n\to\infty}\max_{(\mathbf{d},\mathbf{i},a)}\bigg{\lvert}\frac{N(n,\mathbf{d},\mathbf{i},a)}{n-K+1}-\omega_{\bm{\theta},\nu}^{\star}(\mathbf{d},\mathbf{i},a)\bigg{\rvert}=0,\quad\lim_{n\to\infty}\|\bm{\eta}(n)-\bm{\eta}\|_{\infty}=0\right\\}.$
(169)

Thanks to Lemma 6.2, Lemma 6.3, and the Borel–Cantelli lemma, we have
$\mathbb{P}_{\bm{\theta}}(\mathcal{E})=1$ under the non-stopping version of
$\pi^{\textsc{Rstl-Dtrack}}$ (with the same parameters as $\pi^{\textsc{Rstl-
Dtrack}}$). Fix $\omega\in\mathcal{E}$ and $\gamma>0$ arbitrarily. Then, there
exists $N_{\gamma}(\omega)\in\mathbb{N}$ independent of $\delta$ such that the
following hold for all $n\geq N_{\gamma}(\omega)$:

$\displaystyle\frac{Z(n,\omega)}{n}$
$\displaystyle\geq(1-\gamma)(\eta\,T_{\text{\rm
unif}}^{\star}(\bm{\theta})+(1-\eta)\,T_{R}^{\star}(\bm{\theta})),$ (170)
$\displaystyle\zeta(n,\delta)$
$\displaystyle\leq\log\left(\frac{1}{\delta}\right)+\gamma\,(\eta\,T_{\text{\rm
unif}}^{\star}(\bm{\theta})+(1-\eta)\,T_{R}^{\star}(\bm{\theta}))\,n.$ (171)

The inequality in (171) follows by noting that
$\zeta(n,\delta)=\log(1/\delta)+O(\log(n))=\log(1/\delta)+o(n)$. We then have

$\displaystyle\tau(\omega)$ $\displaystyle=\inf\\{n\geq
K:Z(n,\omega)\geq\zeta(n,\delta)\\}$ $\displaystyle\leq\inf\\{n\geq
N_{\gamma}(\omega):Z(n,\omega)\geq\zeta(n,\delta)\\}$
$\displaystyle\leq\inf\left\\{n\geq
N_{\gamma}(\omega):n\,(1-\gamma)(\eta\,T_{\text{\rm
unif}}^{\star}(\bm{\theta})+(1-\eta)\,T_{R}^{\star}(\bm{\theta}))\geq\log\left(\frac{1}{\delta}\right)+\gamma\,(\eta\,T_{\text{\rm
unif}}^{\star}(\bm{\theta})+(1-\eta)\,T_{R}^{\star}(\bm{\theta}))\,n\right\\}$
$\displaystyle\leq\inf\left\\{n\geq
N_{\gamma}(\omega):n\,(1-2\gamma)(\eta\,T_{\text{\rm
unif}}^{\star}(\bm{\theta})+(1-\eta)\,T_{R}^{\star}(\bm{\theta}))\geq\log\left(\frac{1}{\delta}\right)\right\\}$
$\displaystyle=\max\left\\{N_{\gamma}(\omega),\quad\inf\left\\{n\geq
1:n\,(1-2\gamma)(\eta\,T_{\text{\rm
unif}}^{\star}(\bm{\theta})+(1-\eta)\,T_{R}^{\star}(\bm{\theta}))\geq\log\left(\frac{1}{\delta}\right)\right\\}\right\\}$
$\displaystyle\leq\max\left\\{N_{\gamma}(\omega),\quad\left\lceil\frac{\log(1/\delta)}{(1-2\gamma)(\eta\,T_{\text{\rm
unif}}^{\star}(\bm{\theta})+(1-\eta)\,T_{R}^{\star}(\bm{\theta}))}\right\rceil\right\\}$
$\displaystyle\leq\max\left\\{N_{\gamma}(\omega),\quad
1+\frac{\log(1/\delta)}{(1-2\gamma)(\eta\,T_{\text{\rm
unif}}^{\star}(\bm{\theta})+(1-\eta)\,T_{R}^{\star}(\bm{\theta}))}\right\\}$
(172)

for all $\omega\in\mathcal{E}$, where in writing the last line above, we use
the relation $\lceil x\rceil<1+x$. Thus, it follows from (172) that
$\mathbb{P}_{\bm{\theta}}(\tau<+\infty)=1$ under $\pi^{\textsc{Rstl-Dtrack}}$,
which in turn implies from (49) that $\pi^{\textsc{Rstl-
Dtrack}}\in\Pi_{R}(\delta)$. Also, dividing both sides of (172) by
$\log(1/\delta)$, letting $\delta\downarrow 0$ and noting that
$N_{\gamma}(\omega)$ does not depend on $\delta$, we get

$\limsup_{\delta\downarrow
0}\frac{\tau(\omega)}{\log(1/\delta)}\leq\frac{1}{(1-2\gamma)(\eta\,T_{\text{\rm
unif}}^{\star}(\bm{\theta})+(1-\eta)\,T_{R}^{\star}(\bm{\theta}))}\quad\forall\omega\in\mathcal{E}.$
(173)

Noting that the right-hand side of (173) holds for all $\gamma>0$, we arrive
at (50) by taking limits as $\gamma\downarrow 0$.

##  Appendix K Proof of Proposition 6.6

Notations: We first introduce some notations. Let $\|\cdot\|_{1}$,
$\|\cdot\|_{2}$, and $\|\cdot\|_{\infty}$ denote the vector $1$-norm,
$2$-norm, and sup-norm operators respectively. Further, for matrices
$Q,Q^{\prime}$ of identical dimensions, let

$\|Q-Q^{\prime}\|_{\infty}\coloneqq\max_{(\mathbf{d},\mathbf{i},a)}\|Q(\cdot\mid\mathbf{d},\mathbf{i},a)-Q^{\prime}(\cdot\mid\mathbf{d},\mathbf{i},a)\|_{1}.$

For all $n\geq K$, let
$\bm{N}(n)\coloneqq[N(n,\mathbf{d},\mathbf{i},a):(\mathbf{d},\mathbf{i},a)\in\mathbb{S}_{R}\times[K]]^{\top}$.
Let $\widehat{\mathcal{M}}_{n}$ denote the MDP with transition kernel
$\widehat{Q}_{n}$ defined in (37), and for any $\bm{\theta}\in\Theta^{K}$, let
$\|\widehat{\mathcal{M}}_{n}-\mathcal{M}_{\bm{\theta},R}\|_{\infty}$ be as
defined in (202). Given $\bm{\theta}\in\Theta^{K}$, let
$\bm{\eta}_{\bm{\theta}}\coloneqq[\eta_{\theta_{a}}:a\in[K]]^{\top}$. Also,
let $\widehat{\bm{\eta}}(n)=[\widehat{\eta}_{a}(n):a\in[K]]^{\top}$,
$\widehat{\theta}_{a}(n)=\dot{A}^{-1}(\widehat{\eta}_{a})$ for all $a\in[K]$,
and $\widehat{\bm{\theta}}(n)=[\widehat{\theta}_{a}(n):a\in[K]]^{\top}$. For
any $\bm{\theta}\in\Theta^{K}$ and $\nu\in\mathcal{W}^{\star}(\bm{\theta})$,
let
$\omega_{\bm{\theta},\nu}^{\star}=[\omega_{\bm{\theta},\nu}^{\star}(\mathbf{d},\mathbf{i},a):(\mathbf{d},\mathbf{i},a)\in\mathbb{S}_{R}\times[K]]^{\top}$
be as defined in Lemma 6.3. Let

$\psi^{\prime}(\bm{\theta}^{\prime},\nu^{\prime},Q^{\prime})\coloneqq\inf_{\bm{\lambda}\in\textsc{Alt}(\bm{\theta}^{\prime})}\
\sum_{(\mathbf{d},\mathbf{i})\in\mathbb{S}_{R}}\
\sum_{a=1}^{K}\nu^{\prime}(\mathbf{d},\mathbf{i},a)\,D_{\text{\rm
KL}}(Q^{\prime}(\cdot\mid\mathbf{d},\mathbf{i},a)\|Q_{\bm{\lambda},R}(\cdot\mid\mathbf{d},\mathbf{i},a)).$
(174)

###### Proof of Proposition 6.6.

Fix $\bm{\theta}\in\Theta^{K}$, $\eta\in(0,1)$,
$\nu\in\mathcal{W}^{\star}(\bm{\theta})$, and $\delta\in(0,1)$. Assume that
$\bm{\theta}$ is the underlying instance. Fix an arbitrary $\xi>0$. From Lemma
I.1, we know that the mapping
$\bm{\theta}^{\prime}\mapsto\bm{\eta}_{\bm{\theta}^{\prime}}$ is continuous.
Hence, there exists $\varepsilon=\varepsilon(\xi)\leq\xi$ such that

$\|\bm{\theta}-\bm{\theta}^{\prime}\|_{2}<\varepsilon\implies\|\bm{\eta}_{\bm{\theta}}-\bm{\eta}_{\bm{\theta}^{\prime}}\|_{2}<\xi.$
(175)

Given $N\geq K$, let888We assume, without loss of generality, that $N^{3/4}$
is an integer.

$C_{N}^{3}(\xi)\coloneqq\bigcap_{n=N^{5}}^{N^{6}}\bigg{\\{}\bigg{\|}\frac{\bm{N}(n)}{n-K+1}-\omega_{\bm{\theta},\nu}^{\star}\bigg{\|}_{\infty}\leq
K_{\xi}(\bm{\theta},\nu)\,\xi\bigg{\\}},$ (176)

where $K_{\xi}(\bm{\theta},\nu)$ are as defined in Lemma 6.3. Let
$C_{N}^{1}(\xi)$ and $C_{N}^{2}(\xi)$ be as defined in (203) and (44)
respectively. Let

$\psi^{\star}(\bm{\theta},\omega_{\bm{\theta},\nu}^{\star},\xi)\coloneqq\inf_{\begin{subarray}{c}\bm{\theta}^{\prime}:\|\bm{\theta}^{\prime}-\bm{\theta}\|_{2}\leq\varepsilon\\\
\nu^{\prime}:\|\nu^{\prime}-\omega_{\bm{\theta},\nu}^{\star}\|_{\infty}\leq
K_{\xi}\,\xi\\\
Q^{\prime}:\|Q-Q_{\bm{\theta},R}\|_{\infty}\leq\xi\end{subarray}}\psi^{\prime}(\theta^{\prime},\nu^{\prime},Q^{\prime}),$
(177)

Notice that as a consequence of (41), the following convergences hold almost
surely:

$\|\widehat{\bm{\eta}}(n)-\bm{\eta}\|_{2}\to
0,\quad\|\widehat{\bm{\theta}}(n)-\bm{\theta}\|_{2}\to
0,\quad\|\widehat{\mathcal{M}}_{n}-\mathcal{M}_{\bm{\theta},R}\|_{\infty}\to
0.$ (178)

Therefore, there exists $N_{1}=N_{1}(\xi)\geq K$ such that for all $N\geq
N_{1}$, the following hold:

$\displaystyle\|\widehat{\bm{\theta}}(n)-\bm{\theta}\|_{2}$
$\displaystyle\leq\varepsilon,\qquad N^{5}\leq n\leq N^{6},$ (179)
$\displaystyle\|\widehat{\bm{\eta}}(n)-\bm{\eta}\|_{2}$
$\displaystyle\leq\xi,\qquad N^{5}\leq n\leq N^{6},$ (180)
$\displaystyle\|\widehat{\mathcal{M}}_{n}-\mathcal{M}_{\bm{\theta},R}\|_{\infty}$
$\displaystyle\leq\xi,\qquad N^{5}\leq n\leq N^{6},$ (181)
$\displaystyle\psi\left(\widehat{\bm{\theta}}(n),\frac{\bm{N}(n)}{n-K+1}\right)$
$\displaystyle\geq\psi^{\star}(\bm{\theta},\omega_{\bm{\theta},\nu}^{\star},\xi),\qquad
N^{5}\leq n\leq N^{6}.$ (182)

Furthermore, it follows from Lemma L.3 and Lemma 6.2 that
$\mathbb{E}_{\bm{\theta}}[N_{1}(\xi)]<+\infty$ (this is simply an artefact of
the probability term $\mathbb{P}_{\bm{\theta}}(N_{1}>n)$ decaying
exponentially in $n$). Hence, it follows that for all $N\geq N_{1}$, the event
$C_{N}^{3}(\xi)$ holds with high probability, conditioned on $C_{N}^{1}(\xi)$.
Furthermore, noting that $N_{a}(n,\mathbf{d},\mathbf{i},a)\leq n+1$ and
therefore $\zeta(n,\delta)=\log(1/\delta)+O(\log n)$, it follows that there
exists $N_{2}=N_{2}(\xi)\geq K$ such that

$\zeta(n,\delta)\leq\log\left(\frac{1}{\delta}\right)+\xi\,\psi^{\star}(\bm{\theta},\omega_{\bm{\theta},\nu}^{\star},\xi)\,n\qquad\forall
n\geq N_{2}.$ (183)

Let $N_{3}=N_{3}(\xi,\delta)$ be defined as

$N_{3}(\xi,\delta)=\inf\left\\{n\geq
K:n-K+1\geq\frac{1}{(1-\xi)\,\psi^{\star}(\bm{\theta},\omega_{\bm{\theta},\nu}^{\star},\xi)}\,\log\left(\frac{1}{\delta}\right)\right\\}.$
(184)

Then, for all $N\geq\max\\{N_{1},N_{2},N_{3}\\}$, it follows that conditional
on $C_{N}^{1}(\xi)\cap C_{N}^{2}(\xi)\cap C_{N}^{3}(\xi)$,

$\displaystyle Z(N)$
$\displaystyle=\inf_{\bm{\lambda}\in\textsc{Alt}(\bm{\theta}(N))}\sum_{(\mathbf{d},\mathbf{i})\in\mathbb{S}_{R}}\
\sum_{a=1}^{K}N(N,\mathbf{d},\mathbf{i},a)\,D_{\text{\rm
KL}}(\widehat{Q}_{N}(\cdot\mid\mathbf{d},\mathbf{i},a)\|Q_{\bm{\lambda},R}(\cdot\mid\mathbf{d},\mathbf{i},a))$
$\displaystyle\geq(N-K+1)\,\psi^{\star}(\bm{\theta},\omega_{\bm{\theta},\nu}^{\star},\xi)$
$\displaystyle\geq(N-K+1)\,\xi\,\psi^{\star}(\bm{\theta},\omega_{\bm{\theta},\nu}^{\star},\xi)+\log\left(\frac{1}{\delta}\right)$
$\displaystyle\geq\zeta(N,\delta),$

thereby proving that

$C_{N}^{1}(\xi)\cap C_{N}^{2}(\xi)\cap C_{N}^{3}(\xi)\subset\\{\tau\leq
N\\}\qquad\forall N\geq\max\\{N_{1}(\xi),N_{2}(\xi),N_{3}(\xi,\delta)\\}.$
(185)

Noting that $N_{1}(\xi)$ is a random variable, while
$N_{2}(\xi),N_{3}(\xi,\delta)$ are deterministic constants, for any $n\geq K$,
we have

$\displaystyle\mathbb{E}_{\bm{\theta}}[\tau\,\mathbf{1}_{\\{N_{1}(\xi)=n\\}}]$
$\displaystyle=\sum_{N=1}^{\infty}\mathbb{P}_{\bm{\theta}}(\tau>N,\,N_{1}(\xi)=n)$
$\displaystyle\leq\max\\{n,N_{2}(\xi),N_{3}(\xi,\delta)\\}+\sum_{N=\max\\{n,N_{2},N_{3}\\}+1}^{\infty}\mathbb{P}_{\bm{\theta}}(\tau>N)$
$\displaystyle\leq\max\\{n,N_{2}(\xi),N_{3}(\xi,\delta)\\}+\sum_{N=\max\\{N_{1},N_{2},N_{3}\\}+1}^{\infty}\mathbb{P}_{\bm{\theta}}\bigg{(}\overline{C_{N}^{1}(\xi)}\cup\overline{C_{N}^{2}(\xi)}\cup\overline{C_{N}^{3}(\xi)}\bigg{)}$
$\displaystyle\leq\max\\{n,N_{2}(\xi),N_{3}(\xi,\delta)\\}+\sum_{N=\max\\{N_{1},N_{2},N_{3}\\}+1}^{\infty}\bigg{[}\mathbb{P}_{\bm{\theta}}\bigg{(}\overline{C_{N}^{1}(\xi)}\bigg{)}+\mathbb{P}_{\bm{\theta}}\bigg{(}\overline{C_{N}^{2}(\xi)}\bigg{)}+\mathbb{P}_{\bm{\theta}}\bigg{(}\overline{C_{N}^{3}(\xi)}~{}\bigg{|}~{}C_{N}^{2}(\xi)\bigg{)}\bigg{]}$
$\displaystyle\leq\max\\{n,N_{2}(\xi),N_{3}(\xi,\delta)\\}+\sum_{N=1}^{\infty}\bigg{[}\mathbb{P}_{\bm{\theta}}\bigg{(}\overline{C_{N}^{1}(\xi)}\bigg{)}+\mathbb{P}_{\bm{\theta}}\bigg{(}\overline{C_{N}^{2}(\xi)}\bigg{)}+\mathbb{P}_{\bm{\theta}}\bigg{(}\overline{C_{N}^{3}(\xi)}~{}\bigg{|}~{}C_{N}^{2}(\xi)\bigg{)}\bigg{]}$
$\displaystyle\leq
n+N_{2}(\xi)+N_{3}(\xi,\delta)+\sum_{N=1}^{\infty}\bigg{[}\mathbb{P}_{\bm{\theta}}\bigg{(}\overline{C_{N}^{1}(\xi)}\bigg{)}+\mathbb{P}_{\bm{\theta}}\bigg{(}\overline{C_{N}^{2}(\xi)}\bigg{)}+\mathbb{P}_{\bm{\theta}}\bigg{(}\overline{C_{N}^{3}(\xi)}~{}\bigg{|}~{}C_{N}^{2}(\xi)\bigg{)}\bigg{]},$
(186)

from which it follows that

$\displaystyle\mathbb{E}_{\bm{\theta}}[\tau]$
$\displaystyle=\sum_{n=1}^{\infty}\mathbb{E}_{\bm{\theta}}[\tau_{\delta}\,\mathbf{1}_{\\{N_{1}(\xi)=n\\}}]$
$\displaystyle\leq\mathbb{E}_{\bm{\theta}}[N_{1}(\xi)]+N_{2}(\xi)+N_{3}(\xi,\delta)+\sum_{N=1}^{\infty}\bigg{[}\mathbb{P}_{\bm{\theta}}\bigg{(}\overline{C_{N}^{1}(\xi)}\bigg{)}+\mathbb{P}_{\bm{\theta}}\bigg{(}\overline{C_{N}^{2}(\xi)}\bigg{)}+\mathbb{P}_{\bm{\theta}}\bigg{(}\overline{C_{N}^{3}(\xi)}~{}\bigg{|}~{}C_{N}^{2}(\xi)\bigg{)}\bigg{]}.$
(187)

From Lemma L.3, Lemma 6.2, and Lemma 6.3, we know that the infinite-summation
term in (187) is finite. Dividing both sides of (187) by $\log(1/\delta)$ and
taking limits as $\delta\downarrow 0$, we get

$\displaystyle\limsup_{\delta\downarrow
0}\frac{\mathbb{E}_{\bm{\theta}}[\tau_{\pi}]}{\log(1/\delta)}$
$\displaystyle\leq\limsup_{\delta\downarrow
0}\frac{N_{3}(\xi,\delta)}{\log(1/\delta)}$
$\displaystyle=\frac{1}{(1-\xi)\,\psi^{\star}(\bm{\theta},\omega_{\bm{\theta},\nu}^{\star},\xi)}.$
(188)

Taking limits as $\xi\downarrow 0$, using the fact that
$\limsup_{\xi\downarrow 0}K_{\xi}(\bm{\theta},\nu)<+\infty$ (cf. Lemma 6.3),
and noting that

$\lim_{\xi\downarrow
0}\psi^{\star}(\bm{\theta},\omega_{\bm{\theta},\nu}^{\star},\xi)=\psi(\omega_{\bm{\theta},\nu}^{\star},\bm{\theta}),$
(189)

where $\psi$ is as defined in (29), we get

$\limsup_{\delta\downarrow
0}\frac{\mathbb{E}_{\bm{\theta}}[\tau_{\pi}]}{\log(1/\delta)}\leq\frac{1}{\psi(\omega_{\bm{\theta},\nu}^{\star},\bm{\theta})}.$
(190)

Noting that

$\omega_{\bm{\theta},\nu}^{\star}=\eta\,\nu_{\bm{\theta}}^{\text{\rm
unif}}+(1-\eta)\,\nu,$

and that

$\displaystyle\psi(\omega_{\bm{\theta},\nu}^{\star},\bm{\theta})$
$\displaystyle=\inf_{\bm{\lambda}\in\textsc{Alt}(\bm{\theta})}\sum_{(\mathbf{d},\mathbf{i})\in\mathbb{S}_{R}}\
\sum_{a=1}^{K}\omega_{\bm{\theta},\nu}^{\star}(\mathbf{d},\mathbf{i},a)\,D_{\text{\rm
KL}}(Q_{\bm{\theta},R}(\cdot\mid\mathbf{d},\mathbf{i},a)\|Q_{\bm{\lambda},R}(\cdot\mid\mathbf{d},\mathbf{i},a))$
$\displaystyle=\inf_{\bm{\lambda}\in\textsc{Alt}(\bm{\theta})}\sum_{(\mathbf{d},\mathbf{i})\in\mathbb{S}_{R}}\
\sum_{a=1}^{K}(\eta\,\nu_{\bm{\theta}}^{\text{\rm
unif}}(\mathbf{d},\mathbf{i},a)+(1-\eta)\,\nu(\mathbf{d},\mathbf{i},a))\,D_{\text{\rm
KL}}(Q_{\bm{\theta},R}(\cdot\mid\mathbf{d},\mathbf{i},a)\|Q_{\bm{\lambda},R}(\cdot\mid\mathbf{d},\mathbf{i},a))$
$\displaystyle\geq\eta\,T_{\text{\rm
unif}}^{\star}(\bm{\theta})+(1-\eta)\,T_{R}^{\star}(\bm{\theta}),$

where $T_{R}^{\star}(\bm{\theta})$ appears because
$\nu\in\mathcal{W}^{\star}(\bm{\theta})$, we get

$\limsup_{\delta\downarrow
0}\frac{\mathbb{E}_{\bm{\theta}}[\tau_{\pi}]}{\log(1/\delta)}\leq\frac{1}{\eta\,T_{\text{\rm
unif}}^{\star}(\bm{\theta})+(1-\eta)\,T_{R}^{\star}(\bm{\theta})}.$ (191)

Finally, taking limits as $\eta\downarrow 0$ in (191) yields (53). ∎

##  Appendix L Technical Results

In this section, we record some technical results of interest. First, we
introduce some notations. Fix $\bm{\theta}\in\Theta^{K}$. For any $n\geq K$,
let $Q_{n}\coloneqq Q_{\bm{\theta},\pi_{n}}$ denote the transition kernel of
the MDP $\mathcal{M}_{\bm{\theta},R}$ under $\pi_{n}$. Along similar lines as
in the proof of Lemma 3.3, it is easy to show that implies that $Q_{n}$ is
ergodic for each $n\geq K$. Let
$\omega_{n}^{\star}=[\omega_{n}^{\star}(\mathbf{d},\mathbf{i},a):(\mathbf{d},\mathbf{i},a)\in\mathbb{S}_{R}\times[K]]^{\top}$
denote the unique stationary distribution of $Q_{n}$. Let
$W_{n}=\mathbf{1}\omega_{n}^{T}$ denote the rank-$1$ matrix each of whose rows
is equal to $\omega_{n}^{T}$. For $r\in\mathbb{N}$, let $Q_{n}^{r}$ denote the
$r$-fold self-product of $Q_{n}$. Let
$\|Q_{n}^{r}-W_{n}\|_{\infty}=\max_{(\mathbf{d},\mathbf{i},a)}\|Q_{n}^{r}(\cdot\mid\mathbf{d},\mathbf{i},a)-W_{n}(\cdot\mid\mathbf{d},\mathbf{i},a)\|_{1}$,
where $\|\cdot\|_{1}$ denotes vector $1$-norm.

Let $\omega_{\bm{\theta}}^{\text{\rm unif}}=[\omega_{\bm{\theta}}^{\text{\rm
unif}}(\mathbf{d},\mathbf{i},a):(\mathbf{d},\mathbf{i},a)\in\mathbb{S}_{R}\times[K]]^{\top}$
denote the unique stationary distribution of the MDP
$\mathcal{M}_{\bm{\theta},R}$ under $\pi^{\text{\rm unif}}$. Let $\mathbb{V}$
be as defined in Lemma 6.1. Thanks to Lemma 3.3, the following quantities are
well-defined:

$\displaystyle r_{\bm{\theta},\text{\rm unif}}$
$\displaystyle\coloneqq\min\left\\{r\in\mathbb{N}:\forall(\mathbf{d},\mathbf{i},a),(\mathbf{d}^{\prime},\mathbf{i}^{\prime},a^{\prime})\in\mathbb{V},\quad
Q_{\bm{\theta},\pi^{\text{\rm
unif}}}^{r}(\mathbf{d}^{\prime},\mathbf{i}^{\prime},a^{\prime}|\mathbf{d},\mathbf{i},a)>0\right\\},$
(192) $\displaystyle\sigma_{\bm{\theta},\text{\rm unif}}$
$\displaystyle\coloneqq\min_{(\mathbf{d},\mathbf{i},a),(\mathbf{d}^{\prime},\mathbf{i}^{\prime},a^{\prime})\in\mathbb{V}}\frac{Q_{\bm{\theta},\pi^{\text{\rm
unif}}}^{r_{\bm{\theta},\text{\rm
unif}}}(\mathbf{d}^{\prime},\mathbf{i}^{\prime},a^{\prime}|\mathbf{d},\mathbf{i},a)}{\omega_{\bm{\theta}}^{\text{\rm
unif}}(\mathbf{d}^{\prime},\mathbf{i}^{\prime},a^{\prime})}.$ (193)

Given a policy
$\pi=[\pi(a|\mathbf{d},\mathbf{i}):(\mathbf{d},\mathbf{i},a)\in\mathbb{S}_{R}\times[K]]^{\top}$,
let
$U_{\pi}\coloneqq\\{(\mathbf{d},\mathbf{i},a):\pi(a|\mathbf{d},\mathbf{i})>0\\}$.
Let $U_{n}\coloneqq U_{\pi_{n}^{\eta}}$, $n\geq K$.

###  L.1 A Bound on $\|Q_{n}^{r}-W_{n}\|_{\infty}$ for $r\in\mathbb{N}$

The below result from [37] gives a bound on the rate of convergence of powers
of an ergodic transition kernel to the stationary distribution.

######  Lemma L.1.

[37, Theorem 4.9] Let $Q$ be an ergodic stochastic matrix on a finite state
space $\mathcal{Z}$ with stationary distribution $\omega$. Let $W$ denote the
rank-$1$ matrix each of whose rows is equal to $\omega^{\top}$. Suppose that
there exists $\sigma>0$ and $r_{0}\in\mathbb{N}$ such that
$Q^{r_{0}}(z,z^{\prime})\geq\sigma\omega(z^{\prime})$ for all
$z,z^{\prime}\in\mathcal{Z}$. Then,

$\|Q^{r}-W\|_{\infty}\leq 2(1-\sigma)^{r/r_{0}-1}\quad\forall r\in\mathbb{N}.$
(194)

We then have the below result for the transition kernel $Q_{n}^{r}$.

######  Lemma L.2.

Fix $\bm{\theta}\in\Theta^{K}$. For any $n\geq K$, let
$\pi_{n}^{\eta}\coloneqq\pi_{\widehat{\bm{\theta}}(n)}^{\eta}$. Let

$\displaystyle\sigma(\varepsilon,\pi,\omega)$
$\displaystyle\coloneqq\left(\varepsilon^{r_{\bm{\theta},\text{\rm
unif}}}+\left((1-\varepsilon)\,K\min_{(\mathbf{d},\mathbf{i},a)\in
U_{\pi}}\pi(a|\mathbf{d},\mathbf{i})\right)^{r_{\bm{\theta},\text{\rm
unif}}}\,\right)\cdot\sigma_{\bm{\theta},\text{\rm
unif}}\cdot\left(\min_{(\mathbf{d},\mathbf{i},a)}\frac{\omega_{\bm{\theta},\text{\rm
unif}}(\mathbf{d},\mathbf{i},a)}{\omega(\mathbf{d},\mathbf{i},a)}\right),$
(195) $\displaystyle\bar{\sigma}(\varepsilon,\pi,\omega)$
$\displaystyle\coloneqq 1-\sigma(\varepsilon,\pi,\omega),.$ (196)

Then, we have

$\|Q_{n}^{r}-W_{n}\|_{\infty}\leq C_{n}\,\rho_{n}^{r}\quad\forall
r\in\mathbb{N},$ (197)

where $C_{n}=2/\bar{\sigma}(\varepsilon_{n},\pi_{n-1}^{\eta},\omega_{n})$ and
$\rho_{n}=\bar{\sigma}(\varepsilon_{n},\pi_{n-1}^{\eta},\omega_{n})^{1/r_{\bm{\theta},\text{\rm
unif}}}$.

###### Proof.

Recall that

$Q_{n}(\mathbf{d}^{\prime},\mathbf{i}^{\prime},a^{\prime}|\mathbf{d},\mathbf{i},a)=\varepsilon_{n}\,Q_{\bm{\theta},\pi^{\text{\rm
unif}}}(\mathbf{d}^{\prime},\mathbf{i}^{\prime},a^{\prime}|\mathbf{d},\mathbf{i},a)+(1-\varepsilon_{n})\,Q_{\bm{\theta},\pi_{n-1}^{\eta}}(\mathbf{d}^{\prime},\mathbf{i}^{\prime},a^{\prime}|\mathbf{d},\mathbf{i},a).$
(198)

We note that for all
$(\mathbf{d},\mathbf{i},a),(\mathbf{d}^{\prime},\mathbf{i}^{\prime},a^{\prime})\in\mathbb{S}_{R}\times[K]$,

$\displaystyle
Q_{\bm{\theta},\pi_{n-1}^{\eta}}(\mathbf{d}^{\prime},\mathbf{i}^{\prime},a^{\prime}|\mathbf{d},\mathbf{i},a)$
$\displaystyle=Q_{\bm{\theta},R}(\mathbf{d}^{\prime},\mathbf{i}^{\prime}|\mathbf{d},\mathbf{i},a)\cdot\pi_{n-1}^{\eta}(a^{\prime}|\mathbf{d}^{\prime},\mathbf{i}^{\prime})$
$\displaystyle=Q_{\bm{\theta},R}(\mathbf{d}^{\prime},\mathbf{i}^{\prime}|\mathbf{d},\mathbf{i},a)\cdot
K\,\pi_{n-1}^{\eta}(a^{\prime}|\mathbf{d}^{\prime},\mathbf{i}^{\prime})\cdot\frac{1}{K}$
$\displaystyle\geq
Q_{\bm{\theta},R}(\mathbf{d}^{\prime},\mathbf{i}^{\prime}|\mathbf{d},\mathbf{i},a)\cdot
K\,\min_{(\mathbf{d},\mathbf{i},a)\in
U_{n-1}}\pi_{n-1}^{\eta}(a|\mathbf{d},\mathbf{i})\cdot\pi^{\text{\rm
unif}}(a^{\prime}|\mathbf{d}^{\prime},\mathbf{i}^{\prime})$
$\displaystyle=K\,\min_{(\mathbf{d},\mathbf{i},a)\in
U_{n-1}}\pi_{n-1}^{\eta}(a|\mathbf{d},\mathbf{i})\cdot
Q_{\bm{\theta},\pi^{\text{\rm
unif}}}(\mathbf{d}^{\prime},\mathbf{i}^{\prime},a^{\prime}|\mathbf{d},\mathbf{i},a),$
(199)

where in writing the inequality above, we make use of the relation

$\pi_{n-1}^{\eta}(a^{\prime}|\mathbf{d}^{\prime},\mathbf{i}^{\prime})\cdot\frac{1}{K}\geq\min_{(\mathbf{d},\mathbf{i},a)\in
U_{n-1}}\pi_{n-1}^{\eta}(a|\mathbf{d},\mathbf{i})\cdot\pi^{\text{\rm
unif}}(a^{\prime}|\mathbf{d}^{\prime},\mathbf{i}^{\prime})\quad\forall(\mathbf{d}^{\prime},\mathbf{i}^{\prime},a^{\prime}).$
(200)

We then note that for all
$(\mathbf{d},\mathbf{i},a),(\mathbf{d}^{\prime},\mathbf{i}^{\prime},a^{\prime})\in\mathbb{V}$,

$\displaystyle Q_{n}^{r_{\bm{\theta},\text{\rm
unif}}}(\mathbf{d}^{\prime},\mathbf{i}^{\prime},a^{\prime}|\mathbf{d},\mathbf{i},a)$
$\displaystyle\geq\varepsilon_{n}^{r_{\bm{\theta}},\text{\rm
unif}}\,Q_{\bm{\theta},\pi^{\text{\rm unif}}}^{r_{\bm{\theta},\text{\rm
unif}}}(\mathbf{d}^{\prime},\mathbf{i}^{\prime},a^{\prime}|\mathbf{d},\mathbf{i},a)+(1-\varepsilon_{n})^{r_{\bm{\theta},\text{\rm
unif}}}\,Q_{\bm{\theta},\pi_{n-1}^{\eta}}^{r_{\bm{\theta},\text{\rm
unif}}}(\mathbf{d}^{\prime},\mathbf{i}^{\prime},a^{\prime}|\mathbf{d},\mathbf{i},a)$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\geq}}\left(\varepsilon_{n}^{r_{\bm{\theta}},\text{\rm
unif}}+\left((1-\varepsilon_{n})\,K\,\min_{(\mathbf{d},\mathbf{i},a)\in
U_{n-1}}\pi_{n-1}^{\eta}(a|\mathbf{d},\mathbf{i})\right)^{r_{\bm{\theta},\text{\rm
unif}}}\,\right)\,Q_{\bm{\theta},\pi^{\text{\rm
unif}}}^{r_{\bm{\theta},\text{\rm
unif}}}(\mathbf{d}^{\prime},\mathbf{i}^{\prime},a^{\prime}|\mathbf{d},\mathbf{i},a)$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\geq}}\left(\varepsilon_{n}^{r_{\bm{\theta}},\text{\rm
unif}}+\left((1-\varepsilon_{n})\,K\,\min_{(\mathbf{d},\mathbf{i},a)\in
U_{n-1}}\pi_{n-1}^{\eta}(a|\mathbf{d},\mathbf{i})\right)^{r_{\bm{\theta},\text{\rm
unif}}}\,\right)\cdot\sigma_{\bm{\theta},\text{\rm
unif}}\cdot\omega_{\bm{\theta},\text{\rm
unif}}(\mathbf{d}^{\prime},\mathbf{i}^{\prime},a^{\prime})$
$\displaystyle=\left(\varepsilon_{n}^{r_{\bm{\theta}},\text{\rm
unif}}+\left((1-\varepsilon_{n})\,K\,\min_{(\mathbf{d},\mathbf{i},a)\in
U_{n-1}}\pi_{n-1}^{\eta}(a|\mathbf{d},\mathbf{i})\right)^{r_{\bm{\theta},\text{\rm
unif}}}\,\right)\cdot\sigma_{\bm{\theta},\text{\rm
unif}}\cdot\frac{\omega_{\bm{\theta},\text{\rm
unif}}(\mathbf{d}^{\prime},\mathbf{i}^{\prime},a^{\prime})}{\omega_{n}^{\star}(\mathbf{d}^{\prime},\mathbf{i}^{\prime},a^{\prime})}\cdot\omega_{n}^{\star}(\mathbf{d}^{\prime},\mathbf{i}^{\prime},a^{\prime})$
$\displaystyle\stackrel{{\scriptstyle(c)}}{{\geq}}\underbrace{\left(\varepsilon_{n}^{r_{\bm{\theta}},\text{\rm
unif}}+\left((1-\varepsilon_{n})\,K\,\min_{(\mathbf{d},\mathbf{i},a)\in
U_{n-1}}\pi_{n-1}^{\eta}(a|\mathbf{d},\mathbf{i})\right)^{r_{\bm{\theta},\text{\rm
unif}}}\,\right)\cdot\sigma_{\bm{\theta},\text{\rm
unif}}\cdot\left(\min_{(\mathbf{d},\mathbf{i},a)\in\mathbb{V}}\frac{\omega_{\bm{\theta},\text{\rm
unif}}(\mathbf{d},\mathbf{i},a)}{\omega_{n}^{\star}(\mathbf{d},\mathbf{i},a)}\right)}_{=\sigma(\varepsilon_{n},\pi_{n-1}^{\eta},\omega_{n}^{\star})}\cdot\,\omega_{n}^{\star}(\mathbf{d}^{\prime},\mathbf{i}^{\prime},a^{\prime})$
$\displaystyle=\sigma(\varepsilon_{n},\pi_{n-1}^{\eta},\omega_{n}^{\star})\cdot\omega_{n}^{\star}(\mathbf{d}^{\prime},\mathbf{i}^{\prime},a^{\prime}),$
(201)

where $(a)$ above follows from an application of (199) for a total of
$r_{\bm{\theta},\text{\rm unif}}$ times in succession, and $(b)$ follows from
(193). Noting that (201) holds for all
$(\mathbf{d},\mathbf{i},a),(\mathbf{d}^{\prime},\mathbf{i}^{\prime},a^{\prime})\in\mathbb{V}$,
a simple application of Lemma L.1 with
$\sigma=\sigma(\varepsilon_{n},\pi_{n-1}^{\eta},\omega_{n}^{\star})$ and
$r_{0}=r_{\bm{\theta},\text{\rm unif}}$ yields the desired result. ∎

###  L.2 Concentration of Empirical Transition Kernel

In this section, we record a result on the concentration of the empirical
transition kernel $\widehat{Q}_{n}$ defined in (37) under a indefinitely
running version of the policy $\pi^{\textsc{Rstl-Dtrack}}$ (i.e., a policy
that does not check for the stopping criterion and runs indefinitely by
selecting arms according to (36)). We begin with some notations. For any
$n\geq K$, let $\widehat{\mathcal{M}}_{n}$ denote the MDP whose state space is
$\mathbb{S}_{R}$, action space is $[K]$, and the transition kernel is
specified by $\widehat{Q}_{n}$. For any $\bm{\theta}\in\Theta^{K}$, let

$\|\widehat{\mathcal{M}}_{n}-\mathcal{M}_{\bm{\theta},R}\|_{\infty}\coloneqq\max_{(\mathbf{d},\mathbf{i},a)}\|\widehat{Q}_{n}(\cdot\mid\mathbf{d},\mathbf{i},a)-Q_{\bm{\theta},R}(\cdot\mid\mathbf{d},\mathbf{i},a)\|_{1},$
(202)

where $\|\cdot\|_{1}$ denotes the vector $1$-norm operator. We then have the
following result.

######  Lemma L.3.

Fix $\bm{\theta}\in\Theta^{K}$ and $\xi>0$. For $N\geq K$, let999We assume,
without loss of generality, that $N^{1/4}$ is an integer.

$C_{N}^{1}(\xi)\coloneqq\bigcap_{n=N^{5}}^{N^{6}}\bigg{\\{}\|\widehat{\mathcal{M}}_{n}-\mathcal{M}_{\bm{\theta},R}\|_{\infty}\leq\xi\bigg{\\}}.$
(203)

Then, there exist constants $B$ and $C$ that depend only on $\xi$ and
$\bm{\theta}$ such that under the indefinite version of $\pi^{\textsc{Rstl-
Dtrack}}$,

$\mathbb{P}_{\bm{\theta}}\bigg{(}\overline{C_{N}^{1}(\xi)}\bigg{)}\leq\frac{1}{N^{2}}+B\,N^{6}\,\exp\left(-\frac{C\,N^{1/4}}{\sqrt{K\,S_{R}}}\right)\quad\forall
N\geq K.$ (204)

###### Proof.

Consider the event

$\mathcal{E}_{N}\coloneqq\bigg{\\{}\forall(\mathbf{d},\mathbf{i},a)\in\mathbb{V},\quad\forall
n\geq K,\quad
N(n,\mathbf{d},\mathbf{i},a)\geq\left\lceil\frac{n}{\lambda_{\bm{\theta}}(N)}\right\rceil^{1/4}-1\bigg{\\}},$
(205)

where
$\lambda_{\bm{\theta}}(N)\coloneqq\frac{(1+S_{R})^{2}}{\sigma_{\bm{\theta}}^{2}}\log^{2}(1+KS_{R}\,N^{2})$,
and $\mathbb{V}$ is as defined in Lemma 6.1. In the definition of
$\lambda_{\bm{\theta}}(N)$, the constant $\sigma_{\bm{\theta}}$ is as defined
in Lemma F.2. From Lemma 6.1, we know that
$\mathbb{P}_{\bm{\theta}}(\mathcal{E}_{N})\geq 1-1/N^{2}$. We thus have

$\displaystyle\mathbb{P}_{\bm{\theta}}(\overline{C_{N}^{1}(\xi)})$
$\displaystyle\leq\mathbb{P}_{\bm{\theta}}(\overline{\mathcal{E}_{N}})+\mathbb{P}_{\bm{\theta}}(\overline{C_{N}^{1}(\xi)}\cap\mathcal{E}_{N})$
$\displaystyle\leq\frac{1}{N^{2}}+\mathbb{P}_{\bm{\theta}}(\overline{C_{N}^{1}(\xi)}\cap\mathcal{E}_{N}).$
(206)

Using the union bound, we have

$\displaystyle\mathbb{P}_{\bm{\theta}}(\overline{C_{N}^{1}(\xi)}\cap\mathcal{E}_{N})$
$\displaystyle\leq\sum_{n=N^{5}}^{N^{6}}\mathbb{P}_{\bm{\theta}}\bigg{(}\exists(\mathbf{d},\mathbf{i},a)\in\mathbb{V}:\|\widehat{Q}_{n}(\cdot\mid\mathbf{d},\mathbf{i},a)-Q_{\bm{\theta},R}(\cdot\mid\mathbf{d},\mathbf{i},a)\|_{1}>\xi,\
\mathcal{E}_{N}\bigg{)}$ $\displaystyle\leq\sum_{n=N^{5}}^{N^{6}}\
\sum_{(\mathbf{d},\mathbf{i},a)\in\mathbb{V}}\mathbb{P}_{\bm{\theta}}\bigg{(}\exists(\mathbf{d}^{\prime},\mathbf{i}^{\prime})\in\mathbb{S}_{R}:|\widehat{Q}_{n}(\mathbf{d}^{\prime},\mathbf{i}^{\prime}|\mathbf{d},\mathbf{i},a)-Q_{\bm{\theta},R}(\mathbf{d}^{\prime},\mathbf{i}^{\prime}|\mathbf{d},\mathbf{i},a)|>\frac{\xi}{S_{R}},\
\mathcal{E}_{N}\bigg{)}$ $\displaystyle\leq\sum_{n=N^{5}}^{N^{6}}\
\sum_{\begin{subarray}{c}(\mathbf{d},\mathbf{i},a)\in\mathbb{V}\\\
(\mathbf{d}^{\prime},\mathbf{i}^{\prime})\in\mathbb{S}_{R}\end{subarray}}\mathbb{P}_{\bm{\theta}}\bigg{(}|\widehat{Q}_{n}(\mathbf{d}^{\prime},\mathbf{i}^{\prime}|\mathbf{d},\mathbf{i},a)-Q_{\bm{\theta},R}(\mathbf{d}^{\prime},\mathbf{i}^{\prime}|\mathbf{d},\mathbf{i},a)|>\frac{\xi}{S_{R}},\
\mathcal{E}_{N}\bigg{)}$ $\displaystyle\leq\sum_{n=N^{5}}^{N^{6}}\
\sum_{\begin{subarray}{c}(\mathbf{d},\mathbf{i},a)\in\mathbb{V}\\\
(\mathbf{d}^{\prime},\mathbf{i}^{\prime})\in\mathbb{S}_{R}\end{subarray}}\mathbb{P}_{\bm{\theta}}\bigg{(}\widehat{Q}_{n}(\mathbf{d}^{\prime},\mathbf{i}^{\prime}|\mathbf{d},\mathbf{i},a)-Q_{\bm{\theta},R}(\mathbf{d}^{\prime},\mathbf{i}^{\prime}|\mathbf{d},\mathbf{i},a)>\frac{\xi}{S_{R}},\
\mathcal{E}_{N}\bigg{)}$ $\displaystyle\hskip
28.45274pt+\sum_{n=N^{5}}^{N^{6}}\
\sum_{\begin{subarray}{c}(\mathbf{d},\mathbf{i},a)\in\mathbb{V}\\\
(\mathbf{d}^{\prime},\mathbf{i}^{\prime})\in\mathbb{S}_{R}\end{subarray}}\mathbb{P}_{\bm{\theta}}\bigg{(}\widehat{Q}_{n}(\mathbf{d}^{\prime},\mathbf{i}^{\prime}|\mathbf{d},\mathbf{i},a)-Q_{\bm{\theta},R}(\mathbf{d}^{\prime},\mathbf{i}^{\prime}|\mathbf{d},\mathbf{i},a)<-\frac{\xi}{S_{R}},\
\mathcal{E}_{N}\bigg{)}.$ (207)

For $x,y\in[0,1]$, let $d(x,y)\coloneqq x\log(x/y)+(1-x)\log((1-x)/(1-y))$.
For all $(\mathbf{d},\mathbf{i},a)\in\mathbb{V}$,
$(\mathbf{d}^{\prime},\mathbf{i}^{\prime})\in\mathbb{S}_{R}$, and $n\geq
N^{5}$, we then have

$\displaystyle\mathbb{P}_{\bm{\theta}}\bigg{(}\widehat{Q}_{n}(\mathbf{d}^{\prime},\mathbf{i}^{\prime}|\mathbf{d},\mathbf{i},a)-Q_{\bm{\theta},R}(\mathbf{d}^{\prime},\mathbf{i}^{\prime}|\mathbf{d},\mathbf{i},a)>\frac{\xi}{S_{R}},\
\mathcal{E}_{N}\bigg{)}$
$\displaystyle\leq\mathbb{P}_{\bm{\theta}}\bigg{(}\widehat{Q}_{n}(\mathbf{d}^{\prime},\mathbf{i}^{\prime}|\mathbf{d},\mathbf{i},a)-Q_{\bm{\theta},R}(\mathbf{d}^{\prime},\mathbf{i}^{\prime}|\mathbf{d},\mathbf{i},a)>\frac{\xi}{S_{R}},\
N(n,\mathbf{d},\mathbf{i},a)\geq\left\lceil\frac{n}{\lambda_{\bm{\theta}}(N)}\right\rceil^{1/4}-1\bigg{)}$
$\displaystyle=\sum_{u=\left\lceil\frac{n}{\lambda_{\bm{\theta}}(N)}\right\rceil^{1/4}-1}^{\infty}\mathbb{P}_{\bm{\theta}}\bigg{(}\widehat{Q}_{n}(\mathbf{d}^{\prime},\mathbf{i}^{\prime}|\mathbf{d},\mathbf{i},a)-Q_{\bm{\theta},R}(\mathbf{d}^{\prime},\mathbf{i}^{\prime}|\mathbf{d},\mathbf{i},a)>\frac{\xi}{S_{R}},\
N(n,\mathbf{d},\mathbf{i},a)=u\bigg{)}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}\sum_{u=\left\lceil\frac{n}{\lambda_{\bm{\theta}}(N)}\right\rceil^{1/4}-1}^{\infty}\exp\left(-u\cdot
d\left(Q_{\bm{\theta},R}(\mathbf{d}^{\prime},\mathbf{i}^{\prime}|\mathbf{d},\mathbf{i},a)+\frac{\xi}{S_{R}},Q_{\bm{\theta},R}(\mathbf{d}^{\prime},\mathbf{i}^{\prime}|\mathbf{d},\mathbf{i},a)\right)\right)$
$\displaystyle\leq\dfrac{\exp\left(-\left(\left\lceil\frac{n}{\lambda_{\bm{\theta}}(N)}\right\rceil^{1/4}-1\right)\cdot
d\left(Q_{\bm{\theta},R}(\mathbf{d}^{\prime},\mathbf{i}^{\prime}|\mathbf{d},\mathbf{i},a)+\frac{\xi}{S_{R}},Q_{\bm{\theta},R}(\mathbf{d}^{\prime},\mathbf{i}^{\prime}|\mathbf{d},\mathbf{i},a)\right)\right)}{1-\exp\left(-d\left(Q_{\bm{\theta},R}(\mathbf{d}^{\prime},\mathbf{i}^{\prime}|\mathbf{d},\mathbf{i},a)+\frac{\xi}{S_{R}},Q_{\bm{\theta},R}(\mathbf{d}^{\prime},\mathbf{i}^{\prime}|\mathbf{d},\mathbf{i},a)\right)\right)}$
$\displaystyle\leq\dfrac{\exp\left(-\left(\frac{N^{5/4}}{\lambda_{\bm{\theta}}(N)^{1/4}}-1\right)\cdot
d\left(Q_{\bm{\theta},R}(\mathbf{d}^{\prime},\mathbf{i}^{\prime}|\mathbf{d},\mathbf{i},a)+\frac{\xi}{S_{R}},Q_{\bm{\theta},R}(\mathbf{d}^{\prime},\mathbf{i}^{\prime}|\mathbf{d},\mathbf{i},a)\right)\right)}{1-\exp\left(-d\left(Q_{\bm{\theta},R}(\mathbf{d}^{\prime},\mathbf{i}^{\prime},|\mathbf{d},\mathbf{i},a)+\frac{\xi}{S_{R}},Q_{\bm{\theta},R}(\mathbf{d}^{\prime},\mathbf{i}^{\prime}|\mathbf{d},\mathbf{i},a)\right)\right)},$
(208)

where $(a)$ above follows from the Chernoff–Hoeffding bound. Along similar
lines as above, we have

$\displaystyle\mathbb{P}_{\bm{\theta}}\bigg{(}\widehat{Q}_{n}(\mathbf{d}^{\prime},\mathbf{i}^{\prime}|\mathbf{d},\mathbf{i},a)-Q_{\bm{\theta},R}(\mathbf{d}^{\prime},\mathbf{i}^{\prime}|\mathbf{d},\mathbf{i},a)<-\frac{\xi}{S_{R}},\
\mathcal{E}_{N}\bigg{)}$
$\displaystyle\leq\dfrac{\exp\left(-\left(\frac{N^{5/4}}{\lambda_{\bm{\theta}}(N)^{1/4}}-1\right)\cdot
d\left(Q_{\bm{\theta},R}(\mathbf{d}^{\prime},\mathbf{i}^{\prime}|\mathbf{d},\mathbf{i},a)-\frac{\xi}{S_{R}},Q_{\bm{\theta},R}(\mathbf{d}^{\prime},\mathbf{i}^{\prime}|\mathbf{d},\mathbf{i},a)\right)\right)}{1-\exp\left(-d\left(Q_{\bm{\theta},R}(\mathbf{d}^{\prime},\mathbf{i}^{\prime}|\mathbf{d},\mathbf{i},a)-\frac{\xi}{S_{R}},Q_{\bm{\theta},R}(\mathbf{d}^{\prime},\mathbf{i}^{\prime},|\mathbf{d},\mathbf{i},a)\right)\right)}.$
(209)

Plugging (208) and (209) into (207), setting

$\displaystyle C$
$\displaystyle\coloneqq\sqrt{\frac{\sigma_{\bm{\theta}}}{1+S_{R}}}\min_{\begin{subarray}{c}(\mathbf{d},\mathbf{i},a)\in\mathbb{V}\\\
(\mathbf{d}^{\prime},\mathbf{i}^{\prime})\in\mathbb{S}_{R}\end{subarray}}\bigg{\\{}d\left(Q_{\bm{\theta},R}(\mathbf{d}^{\prime},\mathbf{i}^{\prime}|\mathbf{d},\mathbf{i},a)-\frac{\xi}{S_{R}},~{}~{}Q_{\bm{\theta},R}(\mathbf{d}^{\prime},\mathbf{i}^{\prime}|\mathbf{d},\mathbf{i},a)\right),$
$\displaystyle\hskip
142.26378ptd\left(Q_{\bm{\theta},R}(\mathbf{d}^{\prime},\mathbf{i}^{\prime}|\mathbf{d},\mathbf{i},a)+\frac{\xi}{S_{R}},~{}~{}Q_{\bm{\theta},R}(\mathbf{d}^{\prime},\mathbf{i}^{\prime}|\mathbf{d},\mathbf{i},a)\right)\bigg{\\}},$
(210) $\displaystyle B$
$\displaystyle\coloneqq\sum_{\begin{subarray}{c}(\mathbf{d},\mathbf{i},a)\in\mathbb{V}\\\
(\mathbf{d}^{\prime},\mathbf{i}^{\prime})\in\mathbb{S}_{R}\end{subarray}}\bigg{[}\dfrac{\exp\left(d\left(Q_{\bm{\theta},R}(\mathbf{d}^{\prime},\mathbf{i}^{\prime}|\mathbf{d},\mathbf{i},a)+\frac{\xi}{S_{R}},~{}~{}Q_{\bm{\theta},R}(\mathbf{d}^{\prime},\mathbf{i}^{\prime}|\mathbf{d},\mathbf{i},a)\right)\right)}{1-\exp\left(-d\left(Q_{\bm{\theta},R}(\mathbf{d}^{\prime},\mathbf{i}^{\prime}|\mathbf{d},\mathbf{i},a)+\frac{\xi}{S_{R}},~{}~{}Q_{\bm{\theta},R}(\mathbf{d}^{\prime},\mathbf{i}^{\prime}|\mathbf{d},\mathbf{i},a)\right)\right)}$
$\displaystyle\hskip
85.35826pt+\dfrac{\exp\left(d\left(Q_{\bm{\theta},R}(\mathbf{d}^{\prime},\mathbf{i}^{\prime}|\mathbf{d},\mathbf{i},a)-\frac{\xi}{S_{R}},~{}~{}Q_{\bm{\theta},R}(\mathbf{d}^{\prime},\mathbf{i}^{\prime}|\mathbf{d},\mathbf{i},a)\right)\right)}{1-\exp\left(-d\left(Q_{\bm{\theta},R}(\mathbf{d}^{\prime},\mathbf{i}^{\prime}|\mathbf{d},\mathbf{i},a)-\frac{\xi}{S_{R}},~{}~{}Q_{\bm{\theta},R}(\mathbf{d}^{\prime},\mathbf{i}^{\prime}|\mathbf{d},\mathbf{i},a)\right)\right)}\bigg{]},$
(211)

and noting that

$\displaystyle\sum_{n=N^{5}}^{N^{6}}\exp\left(-\frac{C\,N^{5/4}}{\sqrt{\log(1+KS_{R}\,N^{2})}}\right)$
$\displaystyle\leq
N^{6}\exp\left(-\,\frac{C\,N^{5/4}}{\sqrt{\log(1+KS_{R}\,N^{2})}}\right)$
$\displaystyle\leq
N^{6}\exp\left(-\,\frac{C\,N^{5/4}}{\sqrt{K\,S_{R}\,N^{2}}}\right)$
$\displaystyle=N^{6}\exp\left(-\,\frac{C\,N^{1/4}}{\sqrt{K\,S_{R}}}\right),$

we arrive at (204). ∎