$\mathcal{M}^{\prime}:=\left\\{M_{\sigma}:\sigma\in\Sigma\right\\}$

Recall that by eq. D.18, that it is enough to find a lower bound on

$\inf_{\hat{M}}\sup_{M\in\mathcal{M}^{\prime}}\mathbb{P}\left({\left\|M-\hat{M}\right\|_{\infty}>\varepsilon}\right).$

By applying Tsybakov’s reduction method [54, Theorem 2.5] to our problem, we
obtain the following lower bound,

$\inf_{\hat{M}}\sup_{M\in\mathcal{M}^{\prime}}\mathbb{P}\left({\left\|M-\hat{M}\right\|_{\infty}>\varepsilon}\right)\geq\frac{1}{2}\left(1-\cfrac{2^{2-\frac{d}{16}}\sum_{\boldsymbol{\sigma}\in\Sigma}\mathcal{D}_{\boldsymbol{\sigma},m}}{\log{2^{\frac{d}{16}}}}\right),$
(D.21)

where $\mathcal{D}_{\boldsymbol{\sigma},m}$ is the KL-divergence between
$M_{0}$ and $M_{\sigma}$ (for some $\sigma\in\Sigma$), both viewed as
distributions over sequences of length $m$. Recall the following chain rule
for KL-divergence from [59, Lemma 6.2 ]

$\mathcal{D}_{\boldsymbol{\sigma},m}\leq
p_{\star}m\mathcal{D_{\boldsymbol{\sigma}}},$

where $\mathcal{D_{\boldsymbol{\sigma}}}$ is the KL-divergence between
$\boldsymbol{\eta}(\sigma)$ and
$\left(\frac{1-p_{\star}}{d},\dots,\frac{1-p_{\star}}{d},p_{\star}\right)$. A
direct computation of $\mathcal{D_{\boldsymbol{\sigma}}}$ yields

$\displaystyle\mathcal{D_{\boldsymbol{\sigma}}}$
$\displaystyle=\sum_{i=1}^{\frac{d}{2}}\left(\frac{1-p_{\star}+16\sigma_{i}\varepsilon}{d}\log\left(\frac{\frac{1-p_{\star}+16\sigma_{i}\varepsilon}{d}}{\frac{1-p_{\star}}{d}}\right)+\frac{1-p_{\star}-16\sigma_{i}\varepsilon}{d}\log\left(\frac{\frac{1-p_{\star}-16\sigma_{i}\varepsilon}{d}}{\frac{1-p_{\star}}{d}}\right)\right)$
$\displaystyle=\frac{d}{2}\left(\frac{1-p_{\star}+16\varepsilon}{d}\log\left(\frac{1-p_{\star}+16\varepsilon}{1-p_{\star}}\right)+\frac{1-p_{\star}-16\varepsilon}{d}\log\left(\frac{1-p_{\star}-16\varepsilon}{1-p_{\star}}\right)\right).$

Denoting $1-p_{\star}$ by $A$ and $16\varepsilon$ by $B$ allows us to rewrite
the previous equation as

$\displaystyle\mathcal{D_{\boldsymbol{\sigma}}}=\frac{1}{2}\left((A+B)\log\left(1+\frac{B}{A}\right)+(A-B)\log\left(1-\frac{B}{A}\right)\right).$

Observe that $B=16\varepsilon<\frac{1}{2}$ and
$A=1-p_{\star}>1-\frac{1}{d+1}>\frac{1}{2}$. This implies that
$\frac{B}{A}<1$. Since $\log\left(1+x\right)\leq x$ whenever $x>-1$, it
follows that

$\displaystyle\mathcal{D_{\boldsymbol{\sigma}}}$
$\displaystyle\leq\frac{1}{2}(A+B)\frac{B}{A}-(A-B)\frac{B}{A}=\frac{B^{2}}{A}=\frac{256\varepsilon^{2}}{1-p_{\star}}\leq
512\varepsilon^{2}.$

Substituting this value in section D.3, and further substituting in that value
into eq. D.21, we obtain

$\displaystyle\inf_{\hat{M}}\sup_{M\in\mathcal{M}^{\prime}}\mathbb{P}\left({\left\|M-\hat{M}\right\|_{\infty}>\varepsilon}\right)$
$\displaystyle\geq\frac{1}{2}\left(1-\cfrac{2^{2-\frac{d}{16}}\sum_{\boldsymbol{\sigma}\in\Sigma}512p_{\star}m\varepsilon^{2}}{\log{2^{\frac{d}{16}}}}\right)$
$\displaystyle=\frac{1}{2}\left(1-\cfrac{2^{2-\frac{d}{16}}|\Sigma|512p_{\star}m\varepsilon^{2}}{\log{2^{\frac{d}{16}}}}\right).$

Recall that our choice of $\Sigma$ satisfies $|\Sigma|=2^{\frac{d}{16}}$.
Thus,

$\displaystyle\frac{1}{2}\left(1-\cfrac{2^{2-\frac{d}{16}}|\Sigma|512p_{\star}m\varepsilon^{2}}{\log{2^{\frac{d}{16}}}}\right)=\frac{1}{2}\left(1-\cfrac{32768p_{\star}m\varepsilon^{2}}{d\log{2}}\right).$

Therefore, whenever
$m\leq\frac{d(1-2\delta)\log{2}}{32768p_{\star}\varepsilon^{2}}$,

$\displaystyle\inf_{\hat{\mathbb{M}}}\sup_{(\mathbb{M},P)\in\mathcal{M}^{\prime}}\mathbb{P}\left({\left\|\hat{\mathbb{M}}-\mathbb{M}\right\|_{\infty}^{*}>\varepsilon}\right)>\delta.$

To complete the proof, we need to relate the quantities $d$ and $p_{*}$ to the
expected return time $T$ of the process. From the statement of the theorem, we
need to show that there exists an universal constant $c_{1}$ such that $T$
satisfies

$T\leq c_{1}\frac{d}{p_{\star}},$

where $T$ is the return time as defined in 2. It is easily verifiable that for
any $\sigma\in\left\\{-1,1\right\\}^{d/2}$ the vector

$\left(\frac{(1-p_{\star})^{2}+\left(1-p_{\star}+16\sigma_{1}\varepsilon\right)p_{\star}}{d},\dots,\frac{(1-p_{\star})^{2}+\left(1-p_{\star}-16\sigma_{d/2}\varepsilon\right)p_{\star}}{d},p_{\star}\right)$

represents the stationary distribution corresponding to the transition
probability Matrix $M_{\sigma}$ as defined in D.19. We know from Kac’s theorem
[38, Theorem 10.2.2] that the expected return time to any state is the inverse
of its stationary probability. It follows from section D.3 that the expected
return times are

$\left(\frac{d}{(1-p_{\star})^{2}+\left(1-p_{\star}+16\sigma_{1}\varepsilon\right)p_{\star}},\dots,\frac{d}{(1-p_{\star})^{2}+\left(1-p_{\star}-16\sigma_{d/2}\varepsilon\right)p_{\star}},\frac{1}{p_{\star}}\right).$

Since
$\frac{d}{(1-p_{\star})^{2}+\left(1-p_{\star}+16\sigma_{1}\varepsilon\right)p_{\star}}\leq\frac{d}{(1-p_{\star})^{2}}$
for any value of $\sigma_{1}\in\left\\{1,-1\right\\}$ it follows that

$\displaystyle\max\left\\{\frac{d}{(1-p_{\star})^{2}+\left(1-p_{\star}+16\sigma_{1}\varepsilon\right)p_{\star}},\dots,\frac{d}{(1-p_{\star})^{2}+\left(1-p_{\star}-16\sigma_{d/2}\varepsilon\right)p_{\star}},\frac{1}{p_{\star}}\right\\}$
$\displaystyle\
\leq\max\left\\{\frac{d}{(1-p_{\star})^{2}},\frac{1}{p_{\star}}\right\\}.$

Since $p_{\star}<1/(d+1)$, it follows that

$\max\left\\{\frac{d}{(1-p_{\star})^{2}},\frac{1}{p_{\star}}\right\\}<\frac{d}{p_{\star}}.$

Therefore, setting $c_{1}=1$, it follows that whenever,
$m\leq\frac{T(1-2\delta)\log{2}}{32768\varepsilon^{2}}$,

$\displaystyle\inf_{\hat{\mathbb{M}}}\sup_{(\mathbb{M},P)\in\mathcal{M}^{\prime}}\mathbb{P}\left({\left\|\hat{\mathbb{M}}-\mathbb{M}\right\|_{\infty}^{*}>\varepsilon}\right)>\delta.$

This completes the proof of the first part.

#### Part 2 $\left(m<\left\\{2\
\mathbb{C}_{T,\delta}\left(\log\mathbb{C}_{T,\delta}\right)^{2},2\
\mathbb{C}_{\zeta,\delta}\left(\log\mathbb{C}_{\zeta,\delta}\right)^{2}\right\\}\right)$:

##### Case I: $m<2\
\mathbb{C}_{T,\delta}\left(\log\mathbb{C}_{T,\delta}\right)^{2}$.

In this part, we prove that there exists a subclass
$\mathcal{M}^{\prime}\subset\mathcal{M}_{\chi,\mathbb{I}}$ and an universal
constant $c>0$ for which $\mathcal{R}_{m}\geq 1/(2+2\pi^{2})$ whenever

$m<c\left(1+\mathbb{C}+\mathbb{C}_{\theta}\right)^{2}\max\left\\{{T}^{2},\frac{1}{\left(1-\max\\{\zeta_{1},1-\zeta_{2}\\}\right)^{2}}\right\\}.$

For an MDP with $d$ states and $k$ transition matrices, define the random
variable $\mathbb{T}$ to be the first time all of the states $1,\dots,d/3$
were visited in all of the $k$ transition matrices. That is,

$\mathbb{T}=\min\left\\{n\geq
0:\bigcap_{s\in\left\\{1,\dots,d/3\right\\},l\in\\{1,\dots,k\\}}\left\\{\bigcup_{k=0}^{n}\left\\{X_{k}=s,a_{k}=l\right\\}\right\\}\neq\emptyset\right\\}.$

Then, we can further lower bound $\mathcal{R}_{m}$ as

$\begin{split}\mathcal{R}_{m}&\geq\inf_{\hat{\mathbb{M}}}\sup_{(\mathbb{M},P)\in\mathcal{M}^{\prime}}\mathbb{P}\left({\left\|\hat{\mathbb{M}}-\mathbb{M}\right\|_{\infty}^{*}>\varepsilon}\,|\,\mathbb{T}>m\right)\mathbb{P}\left({\mathbb{T}>m}\right).\end{split}$

Our next objective is to produce a subclass $\mathcal{M}^{\prime}$. Define
$P^{(0)}$ to be the sequences of probability mass function on controls as in
eq. B.1. Let $\mathbb{H}_{\iota}$ be the set of all $k+1$ tuples
$(M_{\iota,\xi^{(1)}}^{(1)},\dots,M_{\iota,\xi^{(k)}}^{(k)})$ where
$M_{\iota,\xi^{(1)}}^{(1)},\dots,M_{\iota,\xi^{(k)}}^{(k)}$ are matrices as
defined in eq. B.2. To be precise,

$\mathbb{H}_{\iota}:=\left\\{\left\\{M_{\iota,\xi^{(l)}}^{(l)}:l\in\left\\{1,\dots,k\right\\}\right\\}:(\xi^{(1)},\dots,\xi^{(k)})\in\left\\{0,1\right\\}^{d/3\times
k}\right\\}.$

Set $\mathcal{M}^{\prime}=\mathbb{H}_{\iota}\times\left\\{P^{(0)}\right\\}$.
As a consequence, we get the following lemma.

######  Lemma 27.

Let $\mathbb{T}$ be the time to visit the state-control pairs
$\left\\{(1,1),\dots,(d/3,1),(2,1),\dots,(d/3,k)\right\\}$ of an MDP belonging
to class $\mathbb{H}_{\iota}\times\left\\{P^{(0)}\right\\}$ as defined in
section D.3. If $n<\frac{dk}{6\iota}\log\left(\frac{dk}{3}\right)$, then

$\mathbb{P}(\mathbb{T}>n)\geq\frac{1}{1+\pi^{2}}.$

Substituting it in the lower bound to $\mathcal{R}_{m}$ gives

$\displaystyle\mathcal{R}_{m}$
$\displaystyle\geq\inf_{\hat{\mathbb{M}}}\sup_{(\mathbb{M},P)\in\mathbb{H}_{\iota}\times\\{P^{(0)}\\}}\mathbb{P}\left({\left\|\hat{\mathbb{M}}-\mathbb{M}\right\|_{\infty}^{*}>\varepsilon}\,|\,\mathbb{T}>m\right)\mathbb{P}\left({\mathbb{T}>m}\right).$

An application of Lemma 27 and Proposition 25 implies that whenever
$m\leq\mathbb{C}_{\tau}\rho_{\star}T^{2}\log T$ for some universal constant
$\mathbb{C}_{\tau}$

$\mathbb{P}\left({\mathbb{T}>m}\right)\geq\frac{1}{1+\pi^{2}}.$

Consequently, we get,

$\begin{split}\mathcal{R}_{m}&\geq\frac{1}{1+\pi^{2}}\inf_{\hat{\mathbb{M}}}\sup_{(\mathbb{M},P)\in\mathbb{H}_{\iota}\times\left\\{P^{(0)}\right\\}}\mathbb{P}\left({\left\|\hat{\mathbb{M}}-\mathbb{M}\right\|_{\infty}^{*}>\varepsilon}\,|\,\mathbb{T}>m\right).\end{split}$

Next, let $l_{0}$ be any control. By definition of
$\left\|\cdot\right\|_{\infty}^{*}$, it holds that

$\left\|\hat{\mathbb{M}}-\mathbb{M}\right\|_{\infty}^{*}\geq\left\|\hat{M}^{(l_{0})}-M_{\iota,\xi^{(l_{0})}}^{(l_{0})}\right\|_{\infty},$

We recall from the construction in eq. B.2 that $\iota$ is known. Therefore,
to correctly estimate the transition matrix
$M_{\iota,\xi^{(l_{0})}}^{(l_{0})}$ we only need to correctly estimate
$\xi^{(l_{0})}$. Combining these facts we get,

$\displaystyle\inf_{\hat{\mathbb{M}}}\sup_{(\mathbb{M},P)\in\mathbb{H}_{\iota}\times\left\\{P^{(0)}\right\\}}\mathbb{P}\left({\left\|\hat{\mathbb{M}}-\mathbb{M}\right\|_{\infty}^{*}>\varepsilon}\,|\,\mathbb{T}>m\right)$
$\displaystyle\
\geq\inf_{\hat{M}^{(l_{0})}}\sup_{\xi^{(l_{0})}\in\left\\{0,1\right\\}^{(d/3)}}\mathbb{P}\left({\left\|\hat{M}^{(l_{0})}-M_{\iota,\xi^{(l_{0})}}^{(l_{0})}\right\|_{\infty}>\varepsilon}\,|\,\mathbb{T}>m\right).$

We note that whenever
$\xi_{1}^{(l_{0})}\neq\xi_{2}^{(l_{0})}\in\left\\{0,1\right\\}^{d/3}$, we have
$\left\|M_{\iota,\xi_{1}^{(l_{0})}}^{(l_{0})}-M_{\iota,\xi_{2}^{(l_{0})}}^{(l_{0})}\right\|_{\infty}=2\varepsilon.$
For any estimate $\hat{M}^{(l_{0})}$ define
$\xi^{\star}=\mathop{\mathrm{argmin}}_{\xi}\left\|\hat{M}^{(l_{0})}-M_{\iota,\xi}^{(l_{0})}\right\|_{\infty}.$
Then for $\xi^{(l_{0})}\neq\xi^{\star}$ we have

$2\varepsilon=\left\|M_{\iota,\xi^{(l_{0})}}^{(l_{0})}-M_{\iota,\xi^{\star}}^{(l_{0})}\right\|_{\infty}\leq\left\|M_{\iota,\xi^{(l_{0})}}^{(l_{0})}-\hat{M}^{(l_{0})}\right\|_{\infty}+\left\|\hat{M}^{(l_{0})}-M_{\iota,\xi^{\star}}^{(l_{0})}\right\|_{\infty}\leq
2\left\|M_{\iota,\xi^{(l_{0})}}^{(l_{0})}-\hat{M}^{(l_{0})}\right\|_{\infty}.$

Therefore,
$\left\\{l_{0}:\xi^{\star}\neq\xi^{(l_{0})}\right\\}\subset\left\\{l_{0}:\left\|M_{\iota,\xi^{(l_{0})}}^{(l_{0})}-\hat{M}^{(l_{0})}\right\|_{\infty}\geq\varepsilon\right\\}$
and $\mathcal{R}_{m}$ can be further lower bounded by

$\displaystyle\mathcal{R}_{m}$
$\displaystyle\geq\frac{1}{1+\pi^{2}}\inf_{\hat{M}^{(l_{0})}}\max_{\xi^{(l_{0})}\in\left\\{0,1\right\\}^{d/3}}\mathbb{P}\left(\xi^{\star}\neq\xi^{(l_{0})}\,|\,\mathbb{T}>m\right)$
$\displaystyle=\frac{1}{1+\pi^{2}}\inf_{\hat{\xi}}\max_{\xi^{(l_{0})}\in\left\\{0,1\right\\}^{d/3}}\mathbb{P}\left({\hat{\xi}\neq\xi^{(l_{0})}\,|\,\mathbb{T}>m}\right),$

where $\hat{\xi}$ any estimate of $\xi^{*}$
$(X_{0},a_{0},\dots,X_{m},a_{m})\mapsto\\{0,1\\}^{d/3}$. We now observe that
that the events $\left\\{N_{s}^{(l_{0})}=0\text{ for some
}l_{0}\in\mathbb{I}\text{ and some }s\in\chi\right\\}$ and
$\left\\{\mathbb{T}>m\right\\}$ are equivalent. Therefore,

$\displaystyle\mathbb{P}\left({\hat{\xi}\neq\xi^{(l_{0})}\,|\,\mathbb{T}>m}\right)=\mathbb{P}\left({\hat{\xi}\neq\xi^{(l_{0})}\,|\,N_{s}^{(l_{0})}=0}\right).$

When $N_{s}^{(l_{0})}=0$, the estimate $\hat{\xi}$ is equivalent to choosing
uniformly over all possible $\xi^{(l_{0})}$. Since there are $2^{d/3}$ many
possible choices for $\xi^{(l_{0})}$, the probability of choosing incorrectly
is $1-1/2^{d/3}$. We get as a consequence that,

$\displaystyle\inf_{\hat{\xi}}\max_{\xi^{(l_{0})}\in\left\\{0,1\right\\}^{d/3}}\mathbb{P}\left({\hat{\xi}\neq\xi^{(l_{0})}\,|\,\mathbb{T}>m}\right)\geq
1-\frac{1}{2^{d/3}}>\frac{1}{2}.$

In conclusion, whenever $m\leq\mathbb{C}_{\tau}T\log T$,

$\inf_{\hat{\mathbb{M}}}\sup_{(\mathbb{M},P)\in\mathcal{M}_{\chi,\mathbb{I}}}\mathbb{P}\left({\left\|\hat{\mathbb{M}}-\mathbb{M}\right\|_{\infty}^{*}>\varepsilon}\right)\geq\frac{1}{2}.$

##### Case II: $m<2\
\mathbb{C}_{\zeta,\delta}\left(\log\mathbb{C}_{\zeta,\delta}\right)^{2}$.

For the final case, we must now show that for our chosen class of MDP’s,
${1}/\left(1-\max\\{\zeta_{1},1-\zeta_{2}\\}\right)^{2}$ must lie in a fixed
interval for appropriate choices of $\zeta_{1}$ and $\zeta_{2}$. Recall that
by Proposition 25 $\zeta_{1}=\zeta_{2}=\iota$, which is a known constant. The
rest of the argument follows.

Next, recall from Proposition 25 that $\mathbb{C}_{\star}$ and
$\mathbb{C}_{\theta,\star}$ are independent of $d$ and $k$. Since $\iota$ is a
known constant, this implies that $\mathbb{C}_{pel}$ is an universal constant.
This completes the proof. ∎

###  D.4 Proof of Theorem 4

###### Proof.

The proof proceeds by using known perturbation equalities of matrices. Observe
the following variation of the Woodbury matrix identity from eq. 2.3 [58]

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

where $A$ and $B$ are matrices of appropriate dimension. Let
$\left\|\cdot\right\|_{op}$ be the operator norm on $d\times d$ matrices as
defined in Section 4.2 [70]. Using the facts that operator norm is sub-
multiplicative and
$\left\|\cdot\right\|_{\infty}\leq\left\|\cdot\right\|_{op}\leq\sqrt{d}\left\|\cdot\right\|_{\infty}$,
we have that

$\displaystyle\left\|B^{-1}-A^{-1}\right\|_{\infty}\leq\left\|B^{-1}-A^{-1}\right\|_{op}=\left|A^{-1}(A-B)B^{-1}\right\|_{op}$
$\displaystyle\leq\left\|A^{-1}\right\|_{op}\left\|B^{-1}\right\|_{op}\left\|A-B\right\|_{op}$
$\displaystyle\leq\left\|A^{-1}\right\|_{op}\left\|B^{-1}\right\|_{op}\sqrt{d}\left\|A-B\right\|_{\infty}.$

Substitute $A=\left(I-\alpha_{dis}\hat{M}\right)$,
$B=\left(I-\alpha_{dis}M\right)$. It is well known that the eigenvalues of
stochastic matrices lie between $[-1,1]$. As a consequence, the eigenvalues of
$A$ and $B$ are at least $1-\alpha_{dis}$ and therefore,
$\left\|A^{-1}\right\|_{op},\left\|B^{-1}\right\|_{op}\leq\left(1-\alpha_{dis}\right)^{-1}$.
Therefore,

$\displaystyle\left\|B^{-1}-A^{-1}\right\|_{\infty}\leq(1-\alpha_{dis})^{2}\sqrt{d}\left\|A-B\right\|_{\infty}.$

Next, observe that,

$\displaystyle\left\|V-\hat{V}\right\|_{\infty}$
$\displaystyle=\left\|\left(\left(I-\alpha_{dis}\hat{M}\right)^{-1}-\left(I-\alpha_{dis}M\right)^{-1}\right)g\right\|_{\infty}$
$\displaystyle\leq\left\|\left(\left(I-\alpha_{dis}\hat{M}\right)^{-1}-\left(I-\alpha_{dis}M\right)^{-1}\right)\right\|_{\infty}\left\|g\right\|_{1}$
$\displaystyle\leq(1-\alpha_{dis})^{-2}\sqrt{d}\left\|\left(\left(I-\alpha_{dis}\hat{M}\right)-\left(I-\alpha_{dis}M\right)\right)\right\|_{\infty}\left\|g\right\|_{1}$
$\displaystyle\leq\frac{\alpha_{dis}}{(1-\alpha_{dis})^{2}}\sqrt{d}\left\|\hat{M}-M\right\|_{\infty}\left\|g\right\|_{1}.$

It follows from theorem 1 that,

$\displaystyle\mathbb{P}\left(\left\|V-\hat{V}\right\|_{\infty}>\varepsilon\right)\leq$
$\displaystyle\mathbb{P}\left(\frac{\alpha_{dis}}{(1-\alpha_{dis})^{2}}\sqrt{d}\left\|\hat{M}-M\right\|_{\infty}\left\|g\right\|_{1}>\varepsilon\right)$
$\displaystyle=\mathbb{P}\left(\left\|\hat{M}-M\right\|_{\infty}>\frac{(1-\alpha_{dis})^{2}}{\left\|g\right\|_{1}\sqrt{d}\alpha_{dis}}\varepsilon\right)$
$\displaystyle\leq\delta$

whenever

$m>c\;\max\left\\{\frac{T_{\alpha}}{\varepsilon^{2}}\log\left(\frac{dkT_{\alpha}}{\varepsilon^{2}\delta}\right),\mathbb{C}_{\theta}^{2}\max\left\\{{T}^{2},\frac{1}{\left(1-\max\\{\zeta_{1},1-\zeta_{2}\\}\right)^{2}}\right\\}\log\left(\frac{dk}{\delta}\right)\right\\}$

∎

##  Appendix E Proofs of Applications

###  E.1 Proof of Proposition 10

###### Proof.

The proof proceeds by verifying Assumptions 1, 2, 5, and 6.

Assumption 1: To verify Assumption 1, we recall that $P_{s}^{(l)}>0$ and
$P_{min}=\min_{s,l}P_{s}^{(l)}$. Since the minimisation is over finitely many
positive quantities, it must follow that $P_{min}>0$. For any
$l_{0}\in\mathbb{I}$, it follows that

$P_{s}^{(l_{0})}=1-\sum_{l\neq l_{0}}P_{s}^{(l)}<1-(k-1)P_{min}.$

Recall that to satisfy 1, it is enough to produce sets $\mathcal{S}_{i}$ such
that

$\zeta_{2}<\mathbb{P}\left((X_{i},a_{i})\in\mathcal{S}_{i}\right)<\zeta_{1}$

for some probabilities $\zeta_{2}$ and $\zeta_{1}$. We observe by setting
$\mathcal{S}_{i}=\arg\sup$ that
$\mathbb{P}\left((X_{i},a_{i})\in\mathcal{S}_{i}\right)=\mathbb{P}\left(a_{i}=1\right)$.
It then follows,

$P_{min}<\mathbb{P}\left((X_{i},a_{i})\in\mathcal{S}_{i}\right)<1-(k-1)P_{min}.$

and Assumption 1 is satisfied for $\zeta_{2}=P_{min}$ and
$\zeta_{1}=1-(k-1)P_{min}$.

Assumption 2: Next, we proceed to the verification of Assumption 2. As
discussed in eq. 4.1, we only need to show that for some $T>0$,

$\sup_{s,l}\mathrm{E}[\tau^{(1)}_{s,l}|X_{0},a_{0}]<T\text{ almost
everywhere.}$

Recall from Proposition 9 that $(X_{i},a_{i})$ is a time homogenous uniformly
ergodic Markov chain. It follows from KAC’s theorem [38, Theorem 10.2.2] that
for any positive integer $i$,

$\mathrm{E}[\tau^{(i)}_{s,l}]=\frac{1}{\pi_{s,l}^{(x,a)}}.$

Setting $T=\sup_{s,l}{1}/{\pi_{s,l}^{(x,a)}}$ then completes the verification
of Assumption 2.

Assumption 5: Next, we verify that an MDP with stationary controls satisfy
Assumption 5. Recall from section 4.2 the definition of stationary controls.

$\mathcal{L}\left(a_{i}|X_{i}=s_{i},\mathcal{H}_{0}^{i-1}=\hbar_{0}^{i-1}\right)=\mathcal{L}\left(a_{i}|X_{i}=s_{i}\right)=\mathcal{L}\left(a_{1}|X_{1}=s_{i}\right).$

Which consequently implies that

$\displaystyle\mathcal{L}\left(a_{p}|X_{p}=s_{p},\mathcal{H}_{i+j}^{p-1}=\hbar_{i+j}^{p-1},\mathcal{H}_{0}^{i}=\hbar_{0}^{i}\right)-\mathcal{L}\left(a_{p}|X_{p}=s_{p},\mathcal{H}_{i+j}^{p-1}=\hbar_{i+j}^{p-1}\right)$
$\displaystyle\
=\mathcal{L}\left(a_{1}|X_{1}=s_{i}\right)-\mathcal{L}\left(a_{1}|X_{1}=s_{i}\right)$
$\displaystyle\ =0.$

Therefore $\gamma_{p,j,i}=0$ and setting $\mathbb{C}=0$ completes the
verification of 5.

Assumption 6: Next, we verify that a MDP with stationary controls satisfy
Assumption 6. It follows from [38, Theorem 16.0.2 ] that any aperiodic time
homogenous Markov chain on a finite state space with a single communicating
class is uniformly ergodic. [39, Theorem 3.4 ] establishes the equivalence of
weak and uniform ergodicity for time homogenous Markov chains with the ergodic
coefficient between $0$ and $1$. This completes the verification of Assumption
6.

Lastly, let $(s_{0},l_{0}):=\arg\sup_{s,l}1/\pi_{s,l}$ and observe that if
$D_{0}=\pi$, then

$\mathbb{P}\left((X_{i},a_{i})=(s_{0},l_{0})\right)=\frac{1}{\pi_{s_{0},l_{0}}}=\frac{1}{T}=\zeta_{1}=\zeta_{2}.$

This completes the proof. ∎

###  E.2 Proof of Proposition 11

###### Proof.

The proof proceeds by verifying Assumptions 1, 2, 5, and 6.

Assumption 1: Set $\mathcal{S}_{i}=(1,\mathbb{I})$ and observe that

$\displaystyle\mathbb{P}\left((X_{i},a_{i})\in\mathcal{S}_{i}\right)$
$\displaystyle=\mathbb{P}\left(X_{i}=1\right)$
$\displaystyle=\mathbb{E}\left[\mathbb{P}\left(X_{i}=1|X_{i-1},a_{i-1}\right)\right]$
$\displaystyle=\mathbb{E}[M_{X_{i-1},1}^{(a_{i-1})}].$

We observe that

$M_{min}\leq\mathbb{P}\left(\mathcal{S}_{i}\right)\leq M_{max}.$

Thus, setting $\zeta_{1}$ as $M_{min}$ and $\zeta_{2}$ as $M_{max}$, completes
the verification of 1.

Assumption 2: A consequence of Section 4.3 is that for each $l\in\mathbb{I}$,
the transition matrix $M^{(l)}$ is visited at least $\lfloor
n/\mathbb{T}\rfloor$ times for any time interval of length $n$. For some time
point $i$ let $a_{i}=l$.

For any integer $p>i$, $(I2)$ implies

$\displaystyle\mathbb{P}\left(\tau_{s,l}^{(i)}>p\right)$
$\displaystyle=\mathbb{P}\left(\left\\{X_{j}\neq s\bigcup a_{j}\neq
l\right\\}\forall j\in\\{i+1\dots,p+i\\}|X_{i}=s,a_{i}=l\right)$
$\displaystyle\leq\left(1-M_{min}\right)^{\lfloor\frac{p}{\mathbb{T}}\rfloor}$
$\displaystyle\leq\left(1-M_{min}\right)^{\frac{p}{\mathbb{T}}-1}.$

Thus,

$\mathbb{E}[\tau_{s,l}^{(i)}]=\sum_{p\geq
1}\mathbb{P}\left(\tau_{s,l}^{(i)}>p\right)\leq\frac{1}{\left(1-M_{min}\right)^{\frac{1}{\mathbb{T}}-1}\left(1-\left(1-M_{min}\right)^{\frac{1}{\mathbb{T}}}\right)}.$

This completes the verification of 2.

Assumption 5 : Recall that $a_{i}$ is a deterministic sequence of indices. It
follows that,

$\displaystyle\gamma_{p,j,i}$
$\displaystyle=\sup_{s_{p},\hbar_{i+j}^{p-1},\hbar_{0}^{i}}\left\|\mathcal{L}\left(a_{p}|X_{p}=s_{p},\mathcal{H}_{i+j}^{p-1}=\hbar_{i+j}^{p-1},\mathcal{H}_{0}^{i}=\hbar_{0}^{i}\right)-\mathcal{L}\left(a_{p}|X_{p}=s_{p},\mathcal{H}_{i+j}^{p-1}=\hbar_{i+j}^{p-1}\right)\right\|_{TV}$
$\displaystyle=0.$

Hence,

$\sup_{1\leq i\leq m}\sum_{j=i}^{m}\sum_{p=i+j+1}^{m}\gamma_{p,j,i}=0,$

and 5 is verified with $\mathbb{C}=0$.

Assumption 6 : Observe from the definition of $\bar{\theta}_{i,j}$ in eq. 4.3
that,

$\displaystyle\bar{\theta}_{i,j}=\sup_{l,l^{\prime},s_{1},s_{2}}\left\|\mathcal{L}\left(X_{j}|X_{i}=s_{1},a_{i}=l\right)-\mathcal{L}\left(X_{j}|X_{i}=s_{2},a_{i}=l^{\prime}\right)\right\|_{TV}.$

Observe from the definition of an inhomogenous Markov chains that

$\displaystyle\sup_{s_{1},s_{2}}\left\|\mathcal{L}\left(X_{j}|X_{i}=s_{1},a_{i}=l_{1}\right)-\mathcal{L}\left(X_{j}|X_{i}=s_{2},a_{i}=l_{2}\right)\right\|_{TV}$
$\displaystyle=\sup_{s_{1},s_{2}}\left\|\mathcal{L}\left(X_{j}|X_{i}=s_{1},(a_{j-1},\dots,a_{i})=(l_{j-1},\dots,l_{i})\right)-\mathcal{L}\left(X_{j}|X_{i}=s_{2},(a_{j-1},\dots,a_{i})=(l_{j-1},\dots,l_{i})\right)\right\|_{TV},$

where the last line follows since all the controls are deterministic. Since
all of the transition matrices are positive, an application of [60, Theorem 1
] implies that, there exists an integer $C$ for which,

$\bar{\theta}_{i,j}\leq e^{-C(j-i)}.$

Since $e^{-C(j-i)}<e^{-(j-i)}$ for any integer $C$, it consequently implies
that,

$\sup_{i\geq
1}\sum_{j>i}\bar{\theta}_{i,j}\leq\frac{e^{-1}}{1-e^{-1}}\leq\frac{1}{1-e^{-1}}.$

This completes the proof. ∎

###  E.3 Proof of Propopsition 13

###### Proof.

The proof proceeds by verifying Assumptions 1, 2, 5, and 6. Assumptions 1 and
5 are verified similarly to that in the proof of Proposition 11. 2 is verified
by Lemma 12. Finally, 6 follows from Lemma 21 by setting $\chi_{0}=\chi$. ∎

###  E.4 Proof of Proposition 14

###### Proof.

The proof proceeds by verifying Assumptions 1, 2, 5, and 6.
Assumption 1:  1 is verified similarly to that in the proof of Proposition 11.
Assumption 2 : Our objective is to provide an upper bound for $\sup_{i\geq
0}\mathbb{E}[\tau_{s,l}^{(i)}]$. We prove only when $i=0$. All other cases
follow similarly. To compute the expectation, it is sufficient to bound from
above the survival function $\mathbb{P}\left(\tau_{s,l}^{(0)}>p\right)$ for
all $p\geq 1$. When $p\in\left\\{1,\dots,H-1\right\\}$, we trivially upper
bound this probability by $1$. When $p=H$, writing the expression for
$\mathbb{P}\left(\tau_{s,l}^{(0)}>H\right)$ we get

$\displaystyle\mathbb{P}\left(\left\\{X_{j}\neq s\bigcup a_{i}\neq
l\right\\}\forall j\in\\{1\dots,H\\}|X_{0}=s,a_{0}=l\right)$ $\displaystyle\
=\mathbb{P}\left(\left\\{X_{H}\neq s\bigcup a_{H}\neq l\right\\}\right)$
$\displaystyle(E1)$ $\displaystyle\quad\times\mathbb{P}\left(\left\\{X_{j}\neq
s\bigcup a_{i}\neq l\right\\}\forall
j\in\\{1\dots,H-1\\}|X_{0}=s,a_{0}=l\right)$
$\displaystyle\leq\left(1-\frac{1}{dk}\right).$ $\displaystyle(E2)$

$(E1)$ follows from section 4.5 since for all $j\neq H$, $X_{H},a_{H}$ is
independent of $(X_{j},a_{j})$. $(E2)$ follows by substituting the appropriate
probability in $\mathbb{P}\left(\left\\{X_{H}\neq s\bigcup a_{H}\neq
l\right\\}\right)$ and trivially upper bounding
$\mathbb{P}\left(\left\\{X_{j}\neq s\bigcup a_{i}\neq l\right\\}\forall
j\in\\{1\dots,H-1\\}|X_{0}=s,a_{0}=l\right)$ by $1$. We can proceed similarly
for $p\in\\{H+1,\dots,2H-1\\}$. For $p=2H$ we can similarly decompose
$\mathbb{P}\left(\tau_{s,l}^{(i)}>2H\right)$ as,

$\displaystyle\mathbb{P}\left(\tau_{s,l}^{(i)}>2H\right)$
$\displaystyle=\mathbb{P}\left(\left\\{X_{2H}\neq s\bigcup a_{2H}\neq
l\right\\}\right)$ $\displaystyle\quad\times\mathbb{P}\left(\left\\{X_{H}\neq
s\bigcup a_{H}\neq l\right\\}\right)$
$\displaystyle\quad\times\mathbb{P}\left(\left\\{X_{j}\neq s\bigcup a_{i}\neq
l\right\\}\forall
j\in\\{1\dots,2H-1\\}\backslash\\{H\\}|X_{0}=s,a_{0}=l\right)$
$\displaystyle\leq\left(1-\frac{1}{dk}\right)^{2}.$

Proceeding similarly, we bound from above
$\mathbb{P}\left(\tau_{s,l}^{(0)}>p\right)$ for each $p$. Substituting these
bounds in the expression for $\mathbb{E}[\tau_{s,l}^{(0)}]$ we get

$\displaystyle\mathbb{E}[\tau_{s,l}^{(0)}]$
$\displaystyle=\sum_{p=1}^{H-1}\mathbb{P}\left(\tau_{s,l}^{(0)}>p\right)+\sum_{p=H}^{2H-1}\mathbb{P}\left(\tau_{s,l}^{(0)}>p\right)+\dots$
$\displaystyle\leq
H-1+\left(1-\frac{1}{dk}\right)H+\left(1-\frac{1}{dk}\right)^{2}H+\dots$
$\displaystyle=\left(H+\left(1-\frac{1}{dk}\right)H+\left(1-\frac{1}{dk}\right)^{2}H+\dots\right)-1$
$\displaystyle=dkH-1.$

This completes the verification of 2.
Assumption 5 : To verify 5 let $(p,i,j)$ be any triplet in $\mathbb{N}^{3}$
such that $j>i$. We first consider the case when $j\leq i+H$. Observe from
section 4.5 that whenever $p>i+j+H$,

$\displaystyle\mathcal{L}\left(a_{p}|X_{p}=s_{p},\mathcal{H}_{i+j}^{p-1}=\hbar_{i+j}^{p-1},\mathcal{H}_{0}^{i}=\hbar_{0}^{i}\right)-\mathcal{L}\left(a_{p}|X_{p}=s_{p},\mathcal{H}_{i+j}^{p-1}=\hbar_{i+j}^{p-1}\right)$
(E.2) $\displaystyle\
=\mathcal{L}\left(a_{p}|X_{p}=s_{p},\mathcal{H}_{H^{(p)}}^{p-1}=\hbar_{H^{(p)}}^{p-1}\right)-\mathcal{L}\left(a_{p}|X_{p}=s_{p},\mathcal{H}_{H^{(p)}}^{p-1}=\hbar_{H^{(p)}}^{p-1}\right)$
$\displaystyle\ =0.$

Whenever $p\leq i+j+H$, it follows trivially that

$\displaystyle-1\leq\mathcal{L}\left(a_{p}|X_{p}=s_{p},\mathcal{H}_{i+j}^{p-1}=\hbar_{i+j}^{p-1},\mathcal{H}_{0}^{i}=\hbar_{0}^{i}\right)-\mathcal{L}\left(a_{p}|X_{p}=s_{p},\mathcal{H}_{i+j}^{p-1}=\hbar_{i+j}^{p-1}\right)\leq
1.$

Now we consider the case when $j>i+H$. Using the law of iterated expectations
we get

$\displaystyle\mathcal{L}\left(a_{p}|X_{p}=s_{p},\mathcal{H}_{i+j}^{p-1}=\hbar_{i+j}^{p-1},\mathcal{H}_{0}^{i}=\hbar_{0}^{i}\right)$
$\displaystyle=\mathbb{E}\left[\mathcal{L}\left(a_{p}|X_{p}=s_{p},\mathcal{H}_{i+j}^{p-1}=\hbar_{i+j}^{p-1},\mathcal{H}_{H^{(i+j)}}^{i+j-1},\mathcal{H}_{0}^{i}=\hbar_{0}^{i}\right)\right]$
$\displaystyle=\mathbb{E}\left[\mathcal{L}\left(a_{p}|X_{p}=s_{p},\mathcal{H}_{i+j}^{p-1}=\hbar_{i+j}^{p-1},\mathcal{H}_{H^{(i+j)}}^{i+j-1}\right)\right],$
(E.3)

where the second equality follows from section 4.5. Substituting this
expression in eq. E.2 we get for all $j>i+H$

$\displaystyle\mathcal{L}\left(a_{p}|X_{p}=s_{p},\mathcal{H}_{i+j}^{p-1}=\hbar_{i+j}^{p-1},\mathcal{H}_{0}^{i}=\hbar_{0}^{i}\right)-\mathcal{L}\left(a_{p}|X_{p}=s_{p},\mathcal{H}_{i+j}^{p-1}=\hbar_{i+j}^{p-1}\right)$
$\displaystyle\
=\mathbb{E}\left[\mathcal{L}\left(a_{p}|X_{p}=s_{p},\mathcal{H}_{i+j}^{p-1}=\hbar_{i+j}^{p-1},\mathcal{H}_{H^{(i+j)}}^{i+j-1}\right)\right]-\mathbb{E}\left[\mathcal{L}\left(a_{p}|X_{p}=s_{p},\mathcal{H}_{i+j}^{p-1}=\hbar_{i+j}^{p-1},\mathcal{H}_{H^{(i+j)}}^{i+j-1}\right)\right]$
$\displaystyle\ =0.$

Substituting the previous upper bounds into the expression for
$\gamma_{p,j,i}$, we get that

$\displaystyle\sum_{j=1}^{m}\sum_{p=i+j+1}^{m}\gamma_{p,j,i}$
$\displaystyle=\sum_{j=1}^{i+H}\sum_{p=i+j+1}^{i+j+H}\gamma_{p,j,i}+\sum_{j=1}^{i+H}\sum_{p=i+j+H+1}^{m}\gamma_{p,j,i}+\sum_{j={H^{(p)}}}^{m}\sum_{p=i+j+1}^{m}\gamma_{p,j,i}$
$\displaystyle=\sum_{j=1}^{i+H}\sum_{p=i+j+1}^{i+j+H}\gamma_{p,j,i}$
$\displaystyle<H^{2}.$

This completes the verification of 5.

Assumption 6: Applying law of iterated expectation and decomposing
$\mathcal{L}\left(X_{j}|X_{i}=s_{1},a_{i}=l_{1}\right)$ similar to eq. E.3, we
obtain that whenever $j>i+H$ $\bar{\theta}_{i,j}=1$. It follows that
$\sum_{j>i}\bar{\theta}_{i,j}<H$. This completes the verification of 6. ∎

##  Appendix F Proofs of Propositions and Lemmas

###  F.1 Proof of Lemma 1

###### Proof.

The upper bound follows easily by adding and subtracting
$\mathbb{P}\left((X_{m},a_{m},\dots,X_{j},a_{j})\in\mathbb{T}\right)$, and
using triangle inequality. To prove the lower bound, let
$(\hbar_{0}^{i})^{\prime}\in(\chi\times\mathbb{I})^{(i+1)}$. We can write

$\displaystyle\left|\mathbb{P}\left((X_{m},a_{m},\dots,X_{j},a_{j})\in\mathbb{T}|\mathcal{H}_{0}^{i}=\hbar_{0}^{i}\right)-\mathbb{P}\left((X_{m},a_{m},\dots,X_{j},a_{j})\in\mathbb{T}\right)\right|$
$\displaystyle\
=\Bigg{|}\sum_{(\hbar_{0}^{i})^{\prime}\in(\chi\times\mathbb{I})^{(i+1)}}(\mathbb{P}\left((X_{m},a_{m},\dots,X_{j},a_{j})\in\mathbb{T}|\mathcal{H}_{0}^{i}=\hbar_{0}^{i}\right)$
$\displaystyle\quad\quad-\mathbb{P}\left((X_{m},a_{m},\dots,X_{j},a_{j})\in\mathbb{T}|\mathcal{H}_{0}^{i}=(\hbar_{0}^{i})^{\prime}\right))\mathbb{P}(\mathcal{H}_{0}^{i}=(\hbar_{0}^{i})^{\prime})\Bigg{|}$
$\displaystyle\
\leq\sum_{(\hbar_{0}^{i})^{\prime}\in(\chi\times\mathbb{I})^{(i+1)}}\Bigg{|}\mathbb{P}\left((X_{m},a_{m},\dots,X_{j},a_{j})\in\mathbb{T}|\mathcal{H}_{0}^{i}=\hbar_{0}^{i}\right)$
$\displaystyle\quad-\mathbb{P}\left((X_{m},a_{m},\dots,X_{j},a_{j})\in\mathbb{T}|\mathcal{H}_{0}^{i}=(\hbar_{0}^{i})^{\prime}\right)\Bigg{|}\mathbb{P}(\mathcal{H}_{0}^{i}=(\hbar_{0}^{i})^{\prime})$
$\displaystyle\
\leq\bar{\eta}_{i,j}\sum_{(\hbar_{0}^{i})^{\prime}\in(\chi\times\mathbb{I})^{(i+1)}}\mathbb{P}(\mathcal{H}_{0}^{i}=(\hbar_{0}^{i})^{\prime})$
$\displaystyle\ =\bar{\eta}_{i,j}.$

The first inequality follows using the triangle inequality, and the second
inequality follows from equation 2.1. This completes the proof.

∎

###  F.2 Proof of Proposition 3

###### Proof.

The analysis of the proposition term is done via the sampling scheme
introduced in Section C. To begin, use the sampling scheme to get
$\\{\tilde{X}_{0},\tilde{a}_{0},\dots,\tilde{X}_{m},\tilde{a}_{m}\\}$. We
construct the estimators
$\tilde{N}_{s}^{(l)}:=\sum_{i}\mathbbm{1}[\tilde{X_{i}}=s,\tilde{a}_{i}=l]\text{
and
}\tilde{N}_{s,t}^{(l)}:=\sum_{i}\mathbbm{1}[\tilde{X_{i}}=s,\tilde{X}_{i+1}=t,\tilde{a}_{i}=l]$.
Consequently, we define
$\tilde{M}_{s,t}^{(l)}:=\frac{\tilde{N}_{s,t}^{(l)}}{\tilde{N}_{s}^{(l)}}$ and
$\tilde{M}^{(l)}(s,\cdot):=\left(\tilde{M}_{s,1}^{(l)},\tilde{M}_{s,2}^{(l)},\dots,\tilde{M}_{s,d}^{(l)}\right)$.
We observe that
$(\hat{M}^{(l)}(s,\cdot),N_{s}^{(l)})\overset{d}{=}(\tilde{M}^{(l)}(s,\cdot),\tilde{N}_{s}^{(l)})$
by construction we have,

$\displaystyle\mathbb{P}\Bigg{(}\bigg{\|}\hat{M}^{(l)}(s,\cdot)-{M}^{(l)}(s,\cdot)\bigg{\|}_{1}>\varepsilon,N_{s}^{(l)}=n\Bigg{)}$
$\displaystyle=\mathbb{P}\Bigg{(}\bigg{\|}\tilde{M}^{(l)}(s,\cdot)-{M}^{(l)}(s,\cdot)\bigg{\|}_{1}>\varepsilon,\tilde{N}_{s}^{(l)}=n\Bigg{)}$
(F.1)

Next, we observe that given $\tilde{N}_{s}^{(l)}=n\leq m$, and for any
$t\in\chi$, one can reduce $\tilde{M}_{s,t}^{(l)}$ into sum of independent
random variables. Recall from Appendix C that
$\tilde{X}_{i+1}=X_{\tilde{X_{i}},\tilde{N}_{\tilde{X_{i}}}^{(i,\tilde{a}_{i})}+1}^{(\tilde{a}_{i})}$.
Therefore, we can write

$\displaystyle\tilde{M}_{s,t}^{(l)}$
$\displaystyle=\frac{1}{n}\sum_{i=1}^{m}\mathbbm{1}\left[\tilde{X_{i}}=s,X_{\tilde{X_{i}},\tilde{N}_{\tilde{X_{i}}}^{(i,\tilde{a}_{i})}+1}^{(\tilde{a}_{i})}=t,\tilde{a}_{i}=l\right]$
$\displaystyle=\frac{1}{n}\sum_{i=1}^{n}\mathbbm{1}[X_{s,i}^{(l)}=t].$ (F.2)

Let $\tilde{M}_{n}^{(l)}(s,\cdot)$ be defined as the $d$ dimensional vector
whose $t$-th coordinate is
$\frac{1}{n}\sum_{i=1}^{n}\mathbbm{1}[X_{s,i}^{(l)}=t]$. Therefore,

$\displaystyle\mathbb{P}\left(\left\|\tilde{M}^{(l)}(s,\cdot)-{M}^{(l)}(s,\cdot)\right\|_{1}>\varepsilon,\tilde{N}_{s}^{(l)}=n\right)$
$\displaystyle=\mathbb{P}\left(\sum_{t\in\chi}\left|\tilde{M}_{s,t}^{(l)}-M_{s,t}^{(l)}\right|>\varepsilon,\tilde{N}_{s}^{(l)}=n\right)$
$\displaystyle=\mathbb{P}\left(\left\|\tilde{M}_{n}^{(l)}(s,\cdot)-{M}^{(l)}(s,\cdot)\right\|_{1}>\varepsilon,\tilde{N}_{s}^{(l)}=n\right)$
$\displaystyle\leq\mathbb{P}\left(\left\|\tilde{M}_{n}^{(l)}(s,\cdot)-{M}^{(l)}(s,\cdot)\right\|_{1}>\varepsilon\right),$
(F.3)

We obtain the following facts as a consequence of equations F.2 and F.3.

First, $\sum_{i=1}^{n}\mathbbm{1}[X_{s,i}^{(l)}=t]$ is a sum of independent
Bernoulli random variables and
$\mathbb{E}[n\tilde{M}_{n}^{(l)}(s,\cdot)]=n{M}^{(l)}(s,\cdot)$. Furthermore,

$\mathrm{Var}\left(\sum_{i=1}^{n}\mathbbm{1}[X_{s,i}^{(l)}=t]\right)=n{M}_{s,t}^{(l)}(1-{M}_{s,t}^{(l)})\leq
n{M}_{s,t}^{(l)}.$

Second, the mean absolute deviation satisfies

$\displaystyle\mathbb{E}\left[\lVert\tilde{M}_{n}^{(l)}(s,\cdot)-{M}^{(l)}(s,\cdot)\rVert_{1}\right]$
$\displaystyle=\sum_{t\in\chi}\mathbb{E}\left[\left|\sum_{i=1}^{n}\frac{1}{n}\mathbbm{1}[X_{s,i}^{(l)}=t]-{M}_{s,t}^{(l)}\right|\right]$
$\displaystyle\leq\sum_{t\in\chi}\sqrt{\mathrm{Var}\left(\frac{1}{n}\sum_{i=1}^{n}\mathbbm{1}[X_{s,i}^{(l)}=t]\right)}$
$\displaystyle\leq\frac{\sum_{t\in\chi}\sqrt{M_{s,t}^{(l)}}}{\sqrt{n}}$
$\displaystyle\leq\sqrt{\frac{d}{n}},$ (F.4)

where the first and the last inequalities follows by Cauchy-Schwarz
inequality.

Let $\Phi$ be a function such that

$\Phi(X_{s,1}^{(l)},\dots,X_{s,n}^{(l)})=\begin{bmatrix}\frac{1}{n}\sum_{i=1}^{n}\mathbbm{1}[X_{s,i}^{(l)}=1]\\\
\vdots\\\
\frac{1}{n}\sum_{i=1}^{n}\mathbbm{1}[X_{s,i}^{(l)}=d]\end{bmatrix}-\begin{bmatrix}M_{s,1}^{(l)}\\\
\vdots\\\ M_{s,d}^{(l)}\end{bmatrix}.$

For a fixed $j\in\left\\{1,\dots,n\right\\}$, let
$(X_{s,1}^{(l)},\dots,X_{s,j}^{(l)},\dots,X_{s,n}^{(l)})$ and
$(X_{s,1}^{(l)},\dots,\left(X_{s,j}^{(l)}\right)^{\prime},\dots,X_{s,n}^{(l)})$
be two random vectors which differ only in the $j$-th coordinate. Thus,
$X_{s,j}^{(l)}=t_{1}$ and $\left(X_{s,j}^{(l)}\right)^{\prime}=t_{2}$, with
$t_{1}\neq t_{2}$ . As a consequence, all but the $t_{1}$ and $t_{2}$-th
coordinates of the vector

$\Phi(X_{s,1}^{(l)},\dots,X_{s,j}^{(l)},\dots,X_{s,n}^{(l)})-\Phi\left(X_{s,1}^{(l)},\dots,\left(X_{s,j}^{(l)}\right)^{\prime},\dots,X_{s,n}^{(l)}\right)$

are $0$, while the $t_{1}$-th and $t_{2}$-th coordinates are $\frac{1}{n}$ and
$-\frac{1}{n}$ respectively. Thus,

$\left\|\Phi(X_{s,1}^{(l)},\dots,X_{s,j}^{(l)},\dots,X_{s,n}^{(l)})-\Phi\left(X_{s,1}^{(l)},\dots,\left(X_{s,j}^{(l)}\right)^{\prime},\dots,X_{s,n}^{(l)}\right)\right\|_{1}\leq\frac{2}{n}.$

The reverse triangle inequality gives us,

$\displaystyle\left|\left\|\Phi(X_{s,1}^{(l)},\dots,X_{s,j}^{(l)},\dots,X_{s,n}^{(l)})\right\|_{1}-\left\|\Phi\left(X_{s,1}^{(l)},\dots,\left(X_{s,j}^{(l)}\right)^{\prime},\dots,X_{s,n}^{(l)}\right)\right\|_{1}\right|$
$\displaystyle\quad\leq\left\|\Phi(X_{s,1}^{(l)},\dots,X_{s,j}^{(l)},\dots,X_{s,n}^{(l)})-\Phi\left(X_{s,1}^{(l)},\dots,\left(X_{s,j}^{(l)}\right)^{\prime},\dots,X_{s,n}^{(l)}\right)\right\|_{1}$
$\displaystyle\quad\leq\frac{2}{n}.$

We can now apply McDiarmid’s inequality [44, Equation 1.3] to the probability
in eq. F.3, which, combined with the previous facts implies,

$\displaystyle\mathbb{P}\Bigg{(}\bigg{\|}\hat{M}^{(l)}(s,\cdot)-{M}^{(l)}(s,\cdot)\bigg{\|}_{1}>\varepsilon,N_{s}^{(l)}=n\Bigg{)}$
$\displaystyle\leq\mathbb{P}\Bigg{(}\bigg{\|}\tilde{M}_{n}^{(l)}(s,\cdot)-{M}^{(l)}(s,\cdot)\bigg{\|}_{1}>\varepsilon\Bigg{)}$
$\displaystyle\leq\exp\left(-\frac{n}{2}\max\left\\{0,\varepsilon-\sqrt{\frac{d}{n}}\right\\}^{2}\right).$

Now it follows from eq. D.5,

$\displaystyle\sum_{n=n_{low,s}}^{n_{high,s}}\mathbb{P}\left(\left\|\hat{M}^{(l)}(s,\cdot)-{M}^{(l)}(s,\cdot)\right\|_{1}>\varepsilon,N_{s}^{(l)}=n\right)$
$\displaystyle\quad\leq\sum_{n=n_{low,s}}^{n_{high,s}}\exp\left(-\frac{n}{2}\max\left\\{0,\varepsilon-\sqrt{\frac{d}{n}}\right\\}^{2}\right)$
$\displaystyle\quad\leq\sum_{n=n_{low,s}}^{n_{high,s}}\exp\left({-\frac{n_{low,s}}{2}\max\left\\{0,\varepsilon-\sqrt{\frac{d}{n_{high,s}}}\right\\}^{2}}\right).$

Since the term in the exponent does not depend upon $n$, it can be taken out
of the summation. This yields the following upper bound,

$\displaystyle\left(n_{high,s}-n_{low,s}\right)\exp\left({-\frac{n_{low,s}}{2}\max\left\\{0,\varepsilon-\sqrt{\frac{d}{n_{high,s}}}\right\\}^{2}}\right)$
$\displaystyle\leq
m\exp\left({-\frac{n_{low,s}}{2}\max\left\\{0,\varepsilon-\sqrt{\frac{d}{n_{high,s}}}\right\\}^{2}}\right)\leavevmode\nobreak\
$ (F.5)

This completes the analysis. ∎

###  F.3 Proof of Lemma 4

To find the upper bound, observe that,

$\displaystyle\mathbb{E}[N_{s}^{(l)}]=\sum_{i=1}^{m}\mathbb{E}\left[\mathbbm{1}[X_{i}=s,a_{i}=l]\right]$
$\displaystyle=\sum_{i=1}^{m}\mathbb{P}\left(X_{i}=s,a_{i}=l\right).$

From Assumption 1 it follows that if $(s,l)\in\mathcal{S}_{i}$ then,
$\mathbb{P}\left(X_{i}=s,a_{i}=l\right)\leq\zeta_{1}$. Furthermore, if
$(s,l)\notin\mathcal{S}_{i}$, then $(s,l)\in\mathcal{S}_{i}^{c}$, where
$\mathcal{S}_{i}^{c}$ is the complement of the set $\mathcal{S}_{i}$. In that
case,

$\displaystyle\mathbb{P}\left(X_{i}=s,a_{i}=l\right)$
$\displaystyle\leq\mathbb{P}\left((X_{i},a_{i})\in\mathcal{S}_{i}^{c}\right)$
$\displaystyle=1-\mathbb{P}\left((X_{i},a_{i})\in\mathcal{S}_{i}\right)$
$\displaystyle\leq 1-\zeta_{2}.$

Thus, we have proved that
$\mathbb{P}\left(X_{i}=s,a_{i}=l\right)\leq\max\left\\{\zeta_{1},1-\zeta_{2}\right\\}$.
It follows as a consequence that,

$\displaystyle\mathbb{E}[N_{s}^{(l)}]$
$\displaystyle=\sum_{i=1}^{m}\mathbb{P}\left(X_{i}=s,a_{i}=l\right)$
$\displaystyle\leq m\max\left\\{\zeta_{1},1-\zeta_{2}\right\\}.$

For the lower bound, define the random variable $\\{Z_{s,l}^{(p)}\\}$ and the
filtration $\mathcal{F}_{p}^{\prime}$ as,

$\displaystyle Z_{s,l}^{(0)}:=0$ $\displaystyle
Z_{s,l}^{(p)}:=\frac{\sum_{i=1}^{p}\tau_{s,l}^{(i)}}{T}-p$
$\displaystyle\mathcal{F}_{p}^{\prime}:=\mathcal{F}_{\sum_{i=1}^{p}\tau_{s,l}^{(i)}}.$

Observe that

$\displaystyle\mathbb{E}[Z_{s,l}^{(p)}|\mathcal{F}_{p-1}^{\prime}]$
$\displaystyle=\frac{\mathbb{E}[\sum_{i=1}^{p}\tau_{s,l}^{(i)}|\mathcal{F}_{p-1}^{\prime}]}{T}-p$
$\displaystyle=\frac{\mathbb{E}[\sum_{i=1}^{p-1}\tau_{s,l}^{(i)}|\mathcal{F}_{p-1}^{\prime}]}{T}-(p-1)+\frac{\mathbb{E}[\tau_{s,l}^{(p)}|\mathcal{F}_{p-1}^{\prime}]}{T}-1$
$\displaystyle\leq\mathbb{E}[{Z_{s,l}^{(p-1)}}|\mathcal{F}_{p-1}^{\prime}]+\frac{T}{T}-1$
$\displaystyle=Z_{s,l}^{(p-1)},$

where the last inequality follow from Assumption 2 and the last equality
follow from the fact that $Z_{s,l}^{(p-1)}$ is $\mathcal{F}_{p-1}^{\prime}$
measurable. It follows that, $\\{Z_{s,l}^{(p)}\\}$ is a supermartingale. Now,
define

$N:=\min\\{n:\sum_{i=1}^{p}\tau_{s,l}^{(i)}>m\\}.$

It can be seen easily that $N$ is a valid stopping time. Moreover, since the
return times $\tau_{s,l}^{(i)}\geq 1$ almost everywhere, it easily follows
that $\mathbb{P}(N\leq m+1)=1$. Therefore, it follows from Doob’s Optional
Stopping Theorem for supermartingales [20, Theorem 7.1, page 495] that,

$\displaystyle\mathbb{E}[Z_{N}]\leq\mathbb{E}[Z_{0}].$

Since $Z_{0}=0$, we can write

$\displaystyle\mathbb{E}\left[\frac{\sum_{i=1}^{N}\tau_{s,l}^{(i)}}{T}-N\right]$
$\displaystyle\leq 0.$ This in turn implies
$\displaystyle\mathbb{E}\left[\frac{\sum_{i=1}^{N}\tau_{s,l}^{(i)}}{T}\right]$
$\displaystyle\leq\mathbb{E}[N].$

Next, we observe that $N_{s}^{(l)}$ can be written as

$N_{s}^{(l)}=\max\\{n:\sum_{i=1}^{n}\tau_{s,l}^{(i)}\leq m\\}.$

In other words, $N_{s}^{(l)}=N+1$ almost everywhere. It follows that,

$\displaystyle\mathbb{E}\left[\frac{\sum_{i=1}^{N}\tau_{s,l}^{(i)}}{T}\right]$
$\displaystyle\leq\mathbb{E}[N_{s}^{(l)}]+1.$ This in turn implies
$\displaystyle\mathbb{E}\left[\frac{\sum_{i=1}^{N}\tau_{s,l}^{(i)}}{T}\right]-1$
$\displaystyle\leq\mathbb{E}[N_{s}^{(l)}].$

Finally, observe that by the definition of $N$,
$\sum_{i=1}^{N}\tau_{s,l}^{(i)}>m$ almost everywhere. Therefore,

$\displaystyle\frac{m}{T}-1$ $\displaystyle<\mathbb{E}[N_{s}^{(l)}].$

Finally, if $m\geq 2T$

$\frac{m}{T}-1\geq\frac{m}{2T}.$

This completes the proof of the lower bound and consequently proves our lemma.

###  F.4 Proof of Proposition 6

###### Proof.

For ease of notation, we drop $s$, and $l$, and denote
$\mathbbm{1}[X_{i}=s,a_{i}=l]$ by $I_{i}$. Our first step is to prove that for
any integer $i$,

$\displaystyle\left(\mathrm{Var}(I_{i})+2\sum_{j\geq
i}|\mathrm{Cov}(I_{i},I_{j})|\right)\leq 4\mathbb{C}_{\Delta}\rho_{s}^{(l)}.$

By an application of Lemma 2, observe that

$\displaystyle|\mathrm{Cov}(I_{i},I_{j})|$
$\displaystyle\leq\bar{\eta}_{i,j}\mathbb{E}|I_{j}-\mathbb{E}[I_{j}]|\mathrm{ess}\sup|I_{i}|$
$\displaystyle\leq\bar{\eta}_{i,j}\mathbb{E}|I_{j}-\mathbb{E}[I_{j}]|$
$\displaystyle=\bar{\eta}_{i,j}\left(\mathbb{P}\left(I_{j}=1\right)\left(1-\mathbb{P}\left(I_{j}=1\right)\right)+\left|0-\mathbb{P}\left(I_{j}=1\right)\right|\left(1-\mathbb{P}\left(I_{j}=1\right)\right)\right)$
$\displaystyle=2\bar{\eta}_{i,j}\mathbb{P}\left(I_{j}=1\right)\left(1-\mathbb{P}\left(I_{j}=1\right)\right)$
$\displaystyle\leq 2\bar{\eta}_{i,j}\mathbb{P}\left(I_{j}=1\right)$
$\displaystyle\leq 2\bar{\eta}_{i,j}\rho_{s}^{(l)}.$

Moreover,

$\mathrm{Var}(I_{i})=\mathbb{P}\left(I_{j}=1\right)\left(1-\mathbb{P}\left(I_{j}=1\right)\right)\leq\mathbb{P}\left(I_{j}=1\right)\leq
4\rho_{s}^{(l)}.$

Combining these facts we get,

$\displaystyle\left(\mathrm{Var}(I_{i})+2\sum_{j\geq
i}|\mathrm{Cov}(I_{i},I_{j})|\right)$ $\displaystyle\leq 4\left(1+\sum_{j\geq
i}\bar{\eta}_{i,j}\right)\rho_{s}^{(l)}$ $\displaystyle\leq
4\mathbb{C}_{\Delta}\rho_{s}^{(l)},$

where the final line follows from Assumption 4. Next, we observe that,

$\displaystyle\mathbb{P}(N_{s}^{(l)}\notin[n_{low,s},n_{high,s}])$
$\displaystyle=\mathbb{P}(N_{s}^{(l)}-\mathbb{E}[N_{s}^{(l)}]<n_{low,s}-\mathbb{E}[N_{s}^{(l)}])$
$\displaystyle\quad+\mathbb{P}(N_{s}^{(l)}-\mathbb{E}[N_{s}^{(l)}]>n_{high,s}-\mathbb{E}[N_{s}^{(l)}]).$
(F.6)

The rest of the proof follows from an application of Lemma 18 and eq. F.6.
Since $4\mathbb{C}_{\Delta}\rho_{s}^{(l)}$ is independent of $i$, our proof is
complete. ∎

###  F.5 Proof of Lemma 7

###### Proof.

Recall from Lemma 16 the definition of $\lVert\Delta_{m}\rVert$.

$\|\Delta_{m}\|:=\underset{1\leq i\leq
m}{\max}(1+\bar{\eta}_{i,i+1}+\bar{\eta}_{i,i+2}+\dots\bar{\eta}_{i,m}),$

where,

$\displaystyle\bar{\eta}_{i,j}:=\underset{\mathbb{T},s_{1},s_{2},l_{1},l_{2},\hbar_{0}^{i-1}}{\sup}\eta_{i,j},$

and,

$\displaystyle\eta_{i,j}$
$\displaystyle:=\left|\mathbb{P}\left((X_{m},a_{m},\dots,X_{j},a_{j})\in\mathbb{T}|X_{i}=s_{1},a_{i}=l_{1},\mathcal{H}_{0}^{i-1}=\hbar_{0}^{i-1}\right)\right.$
$\displaystyle\left.\qquad\qquad-\mathbb{P}\left((X_{m},a_{m},\dots,X_{j},a_{j})\in\mathbb{T}|X_{i}=s_{2},a_{i}=l_{2},\mathcal{H}_{0}^{i-1}=\hbar_{0}^{i-1}\right)\right|.$

For any fixed $s_{1},s_{2}\in\chi$, $a_{1},a_{2}\in\mathbb{I}$, and
$\hbar_{0}^{i-1}\in(\chi\times\mathbb{I})^{i}$, define the total variation
distance $\eta_{i,j}^{(m)}$ as,

$\displaystyle\eta_{i,j}^{(m)}$
$\displaystyle:=\|\mathcal{L}\left((X_{m},a_{m},\dots,X_{j},a_{j})|X_{i}=s_{1},a_{i}=l_{1},\mathcal{H}_{1}^{i-1}=\hbar_{0}^{i-1}\right)$
$\displaystyle\qquad-\mathcal{L}\left((X_{m},a_{m},\dots,X_{j},a_{j})|X_{i}=s_{2},a_{i}=l_{2},\mathcal{H}_{1}^{i-1}=\hbar_{0}^{i-1}\right)\|_{TV}.$

We note that for each fixed $m$, $\bar{\eta}_{i,j}$ can be recovered from the
corresponding $\eta_{i,j}^{(m)}$ as

$\bar{\eta}_{i,j}=\sup_{s_{1},s_{2},l_{1},l_{2},\hbar_{0}^{i-1}}\eta_{i,j}^{(m)}.$

Thus is is enough to find an upper bound for $\eta_{i,j}^{(m)}$. For the sake
of simplicity, consider the case when $m=2$. Then,

$\displaystyle\eta_{1,2}^{(2)}$
$\displaystyle=\bigg{\|}\mathcal{L}\left((X_{2},a_{2})|X_{1}=s_{1},a_{1}=l_{1},X_{0}=s_{0},a_{0}=l_{0}\right)$
$\displaystyle\qquad-\mathcal{L}\left((X_{2},a_{2})|X_{1}=s_{2},a_{1}=l_{2},X_{0}=s_{0},a_{0}=l_{0}\right)\bigg{\|}_{TV}.$

Use Lemma 19 by substituting $X=a_{2}$, $Y=X_{2}$ and
$Z=(X_{1},a_{1},X_{0},a_{0})$ with $z_{1}$ and $z_{2}$ defined accordingly.
This reduces the $\eta$ mixing coefficient into a sum of the $\gamma$ mixing
coefficients and $\theta$ mixing coefficients. To be precise,

$\displaystyle\eta_{1,2}^{(2)}$
$\displaystyle\leq\sup_{s^{\prime\prime}}\|\mathcal{L}\left(a_{2}|X_{2}=s^{\prime\prime},X_{1}=s_{1},a_{1}=l_{1},X_{0}=s_{0},a_{0}=l_{0}\right)$
(F.8)
$\displaystyle\qquad-\mathcal{L}\left(a_{2}|X_{2}=s^{\prime\prime},X_{1}=s_{2},a_{1}=l_{2},X_{0}=s_{0},a_{0}=l_{0}\right)\|_{TV}$
$\displaystyle+\|\mathcal{L}\left(X_{2}\in\mathbb{T}_{2}|X_{1}=s_{1},a_{1}=l_{1},X_{0}=s_{0},a_{0}=l_{0}\right)$
$\displaystyle\qquad-\mathcal{L}\left(X_{2}\in\mathbb{T}_{2}|X_{1}=s_{2},a_{1}=l_{2},X_{0}=s_{0},a_{0}=l_{0}\right)\|_{TV}.$

We can decompose the first term in eq. F.8 as,

$\displaystyle\sup_{s^{\prime\prime}}\|\mathcal{L}\left(a_{2}|X_{2}=s^{\prime\prime},X_{1}=s_{1},a_{1}=l_{1},X_{0}=s_{0},a_{0}=l_{0}\right)$
$\displaystyle\qquad-\mathcal{L}\left(a_{2}|X_{2}=s^{\prime\prime},X_{1}=s_{2},a_{1}=l_{2},X_{0}=s_{0},a_{0}=l_{0}\right)\|_{TV}$
$\displaystyle\
\leq\sup_{s^{\prime\prime}}\|\mathcal{L}\left(a_{2}|X_{2}=s^{\prime\prime}X_{1}=s_{1},a_{1}=l_{1},X_{0}=s_{0},a_{0}=l_{0}\right)-\mathcal{L}\left(a_{2}|X_{2}=s^{\prime\prime}\right)\|_{TV}$
$\displaystyle\qquad+\sup_{s^{\prime\prime}}\|\mathcal{L}\left(a_{2}|X_{2}=s^{\prime\prime},X_{1}=s_{2},a_{1}=l_{2},X_{0}=s_{0},a_{0}=l_{0}\right)-\mathcal{L}\left(a_{2}|X_{2}=s^{\prime\prime}\right)\|_{TV}$
$\displaystyle\ \leq 2\gamma_{2,1,1},$ (F.9)

where the last step follows from taking supremum over
$s_{1},l_{1},s_{2},l_{2},s_{0}$,and $a_{0}$ on both sides of the inequality.
It follows that, when $m=2$,

$\bar{\eta}_{1,2}\leq\gamma_{2,1,1}+\bar{\theta}_{1,2}.$

We now establish the following recursion,

$\eta_{i,j}^{(m+1)}\leq\eta_{i,j}^{(m)}+2\gamma_{m+1,j,i}.$

Fix an arbitrary $m\geq 3$ and fix $i,j\in{1,2,\dots,m}$ such that $i<j$ and
decompose $\eta_{i,j}^{(m+1)}$ using Lemma 19 by taking $X=(X_{m+1},a_{m+1})$,
and defining $Y$ and $Z$ accordingly to get,

$\displaystyle\eta_{i,j}^{(m+1)}$ $\displaystyle\leq\eta_{i,j}^{(m)}$
$\displaystyle\qquad+\|\mathcal{L}(X_{m+1},a_{m+1}|X_{m}=x_{m},a_{m}=l_{m},X_{i}=s_{1},a_{i}=l_{1},\dots)$
$\displaystyle\qquad\qquad-\mathcal{L}(X_{m+1},a_{m+1}|X_{m}=x_{m},a_{m}=l_{m},X_{i}=s_{2},a_{i}=l_{2},\dots\|_{TV}.$

where we have replaced the terms common to both the conditionals by $\dots$
for convenience of notation.

Using Lemma 19 again on the second term by taking $X=a_{m+1}$, $Y=X_{m+1}$,
and $Z$ as all the random variables in the conditional, we get the following
upper bound,

$\displaystyle\eta_{i,j}^{(m+1)}$
$\displaystyle\leq\eta_{i,j}^{(m)}+\sup_{x_{m+1}\in\chi}\|\mathcal{L}(a_{m+1}|X_{m+1}=x_{m+1},X_{m}=x_{m},a_{m}=l_{m},X_{i}=s_{1},a_{i}=l_{1},\dots)$
$\displaystyle\qquad\qquad-\mathcal{L}(a_{m+1}|X_{m+1}=x_{m+1},X_{m}=x_{m},a_{m}=l_{m},X_{i}=s_{2},a_{i}=l_{2},\dots\|_{TV}$
$\displaystyle\qquad+\|\mathcal{L}(X_{m+1}|X_{m}=x_{m},a_{m}=l_{m},X_{i}=s_{1},a_{i}=l_{1},\dots)$
$\displaystyle\qquad\qquad-\mathcal{L}(X_{m+1}|X_{m}=x_{m},a_{m}=l_{m},X_{i}=s_{2},a_{i}=l_{2},\dots\|_{TV}.$
(F.11)

Since $X_{m+1}$ is Markovian conditional on $X_{m}$ and $a_{m}$, the third
term vanishes. Proceeding similarly to eq. F.9, the second term can be upper
bounded by $\gamma_{m+1,j,i}$. This proves the recursion in section F.5.

Applying the recursion multiple times we are left with,

$\eta_{i,j}^{(m)}\leq\sum_{p=i+j+1}^{m}2\gamma_{p,j,i}+\eta_{i,j}^{(j)}.$

Proceeding similarly to eq. F.8, we can decompose $\eta_{i,j}^{(j)}$ to get,

$\eta_{i,j}^{(j)}\leq 2\gamma_{j,i,i}+\bar{\theta}_{i,j}.$

The terms in the right hand side of the previous equation is a constant.
Following the arguments of section F.5, we can now take an appropriate
supremum on the left hand side to recover $\bar{\eta}_{i,j}$. Therefore,

$\bar{\eta}_{i,j}\leq 2\sum_{p=i+j}^{m}\gamma_{p,j,i}+\bar{\theta}_{i,j}.$

By substituting the upper bound into the expression of
$\lVert\Delta_{m}\rVert$, it follows that,

$\lVert\Delta_{m}\rVert\leq\sup_{1\leq i\leq
m}\left\\{1+2\sum_{j>i}\sum_{p=i+j}^{m}\gamma_{p,j,i}+\sum_{j>i}\bar{\theta}_{i,j}\right\\},$

From Assumptions 5 and 6 it now follows that,

$\lVert\Delta_{m}\rVert\leq 1+\mathbb{C}+\mathbb{C}_{\theta},$

which completes the proof. ∎

###  F.6 Proof of Lemma 8

###### Proof.

The proof of this Lemma follows similarly to that of Lemma 7. We begin by
observing from section F.5 that

$\displaystyle\bar{\eta}_{i,j}\leq
2\sum_{p=i+j}^{m}\gamma_{p,j,i}+\bar{\theta}_{i,j}.$

The rest of the proof follows from a direct application of Assumptions 7 and
8. ∎

###  F.7 Proof of Lemma 12

###### Proof.

As before, let $\tau_{s,l}^{(i,\star,j)}$ as the time between the $j-1$-th and
$j$-th visit to control $l$ after visiting state-control pair $s,l$ for the
$i$-th time. Our next step is to represent $\tau_{s,l}^{(i)}$ in terms of
$\tau_{s,l}^{(i,\star,j)}$’s. Observe that

$\displaystyle\tau_{s,l}^{(i+1)}=\begin{cases}\tau_{s,l}^{(i,\star,1)}\ \text{
if
}\left\\{X_{\sum_{p=1}^{i}\tau_{s,l}^{(p)}+\tau_{s,l}^{(i,\star,1)}}=s\right\\}\\\
\tau_{s,l}^{(i,\star,1)}+\tau_{s,l}^{(i,\star,2)}\ \text{ if
}\left\\{X_{\sum_{p=1}^{i}\tau_{s,l}^{(p)}+\tau_{s,l}^{(i,\star,1)}}\neq
s\text{ and }\
X_{\sum_{p=1}^{i}\tau_{s,l}^{(p)}+\tau_{s,l}^{(i,\star,1)}+\tau_{s,l}^{(i,\star,2)}}=s\right\\}\\\
\quad\vdots\qquad\qquad\qquad\vdots\end{cases}$

Informally, $\tau_{s,l}^{(i+1)}$ is: $\tau_{s,l}^{(i,\star,1)}$ if the state
at the corresponding time is $s$; it is
$\tau_{s,l}^{(i,\star,1)}+\tau_{s,l}^{(i,\star,2)}$ if the state was not $s$
after $\tau_{s,l}^{(i,\star,1)}$ time points and $s$ after
$\tau_{s,l}^{(i,\star,1)}+\tau_{s,l}^{(i,\star,2)}$ time points, and so on. In
other words,

$\displaystyle\tau_{s,l}^{(i+1)}$
$\displaystyle=\tau_{s,l}^{(i,\star,1)}\mathbbm{1}\left[X_{\sum_{p=1}^{i}\tau_{s,l}^{(p)}+\tau_{s,l}^{(i,\star,1)}}=s\right]$
$\displaystyle\
+\left(\tau_{s,l}^{(i,\star,1)}+\tau_{s,l}^{(i,\star,2)}\right)\mathbbm{1}\left[X_{\sum_{p=1}^{i}\tau_{s,l}^{(p)}+\tau_{s,l}^{(i,\star,1)}}\neq
s,\
X_{\sum_{p=1}^{i}\tau_{s,l}^{(p)}+\tau_{s,l}^{(i,\star,1)}+\tau_{s,l}^{(i,\star,2)}}=s\right]$
$\displaystyle\ +\dots$ which in turn implies
$\displaystyle\mathbb{E}[\tau_{s,l}^{(i+1)}|\mathcal{F}_{\sum_{p=1}^{i-1}\tau_{s,l}^{(p)}}]$
$\displaystyle\
=\mathbb{E}\left[\tau_{s,l}^{(i,\star,1)}\mathbbm{1}\left[X_{\sum_{p=1}^{i}\tau_{s,l}^{(p)}+\tau_{s,l}^{(i,\star,1)}}=s\right]|\mathcal{F}_{\sum_{p=1}^{i-1}\tau_{s,l}^{(p)}}\right]$
$\displaystyle\quad+\mathbb{E}\left[\left(\tau_{s,l}^{(i,\star,1)}+\tau_{s,l}^{(i,\star,2)}\right)\mathbbm{1}\left[X_{\sum_{p=1}^{i}\tau_{s,l}^{(p)}+\tau_{s,l}^{(i,\star,1)}}\neq
s,\
X_{\sum_{p=1}^{i}\tau_{s,l}^{(p)}+\tau_{s,l}^{(i,\star,1)}+\tau_{s,l}^{(i,\star,2)}}=s\right]|\mathcal{F}_{\sum_{p=1}^{i-1}\tau_{s,l}^{(p)}}\right]$
$\displaystyle\quad+\dots$ $\displaystyle=\text{Term 1}+\text{Term 2}+\dots$
(F.13)

To compute an upper bound to $\mathbb{E}[\tau_{s,l}^{(i)}]$, it is thus
sufficient to individually find an upper bound to each term of the summation
in the right-hand side of the previous equation by a careful bookkeeping of
the conditional expectations.

Term 1: Applying the law of conditional expectation to the first term we get

$\displaystyle\mathbb{E}\left[\tau_{s,l}^{(i,\star,1)}\mathbbm{1}\left[X_{\sum_{p=1}^{i}\tau_{s,l}^{(p)}+\tau_{s,l}^{(i,\star,1)}}=s\right]|\mathcal{F}_{\sum_{p=1}^{i-1}\tau_{s,l}^{(p)}}\right]$
$\displaystyle\
=\mathbb{E}\left[\mathbb{E}\left[\tau_{s,l}^{(i,\star,1)}\mathbbm{1}\left[X_{\sum_{p=1}^{i}\tau_{s,l}^{(p)}+\tau_{s,l}^{(i,\star,1)}}=s\right]\,|\,\tau_{s,l}^{(i,\star,1)}\right]|\mathcal{F}_{\sum_{p=1}^{i-1}\tau_{s,l}^{(p)}}\right]$
$\displaystyle\
=\mathbb{E}\left[\tau_{s,l}^{(i,\star,1)}\mathbb{P}\left(X_{\sum_{p=1}^{i}\tau_{s,l}^{(p)}+\tau_{s,l}^{(i,\star,1)}}=s|\tau_{s,l}^{(i,\star,1)}\right)|\mathcal{F}_{\sum_{p=1}^{i-1}\tau_{s,l}^{(p)}}\right]$
(F.14)

Recall from item 2 our assumption that

$\max_{s,t,l}M_{s,t}^{(l)}=M_{max},\text{ and
}\min_{s,t,l}M_{s,t}^{(l)}=M_{min}$

for two numbers $0<M_{min},M_{max}<1$. It follows that for any time $p$, state
$s$, and history $\hbar_{0}^{p-1}$,

$\displaystyle
M_{min}\leq\mathbb{P}\left(X_{p}=s\,|\,\mathcal{H}_{0}^{p-1}=\hbar_{0}^{p-1}\right)\leq
M_{max},\,\,\text{and }$ $\displaystyle(E1)$
$\displaystyle\mathbb{P}\left(X_{p}\neq
s\,|\,\mathcal{H}_{0}^{p-1}=\hbar_{0}^{p-1}\right)\leq\max\left\\{M_{max},1-M_{min}\right\\}=:M_{opt}.$
$\displaystyle(E2)$

It follows from $(E1)$ that,
$\mathbb{P}\left(X_{\sum_{p=1}^{i}\tau_{s,l}^{(p)}+\tau_{s,l}^{(i,\star,1)}}=s|\tau_{s,l}^{(i,\star,1)}\right)\leq
M_{max}$. Substituting this value in the right hand side of eq. F.14, we get
the following upper bound to Term 1

$\mathbb{E}\left[\tau_{s,l}^{(i,\star,1)}\mathbbm{1}\left[X_{\sum_{p=1}^{i}\tau_{s,l}^{(p)}+\tau_{s,l}^{(i,\star,1)}}=s\right]|\mathcal{F}_{\sum_{p=1}^{i-1}\tau_{s,l}^{(p)}}\right]\leq\mathbb{E}\left[\tau_{s,l}^{(i,\star,1)}M_{max}|\mathcal{F}_{\sum_{p=1}^{i-1}\tau_{s,l}^{(p)}}\right]\leq
T_{\star}M_{max},$

where the last inequality follows from tower property since

$\mathcal{F}_{\sum_{p=1}^{i-1}\tau_{s,l}^{(p)}}\subseteq\mathcal{F}_{\sum_{p=1}^{i-1}\tau_{s,l}^{(p)}+\sum_{p=1}^{j-1}\tau_{s,l}^{(i,\star,p)}}.$

Term 2: For ease of notation, we define

$\mathbb{E}^{*}[\cdot]=\mathbb{E}[\cdot|\mathcal{F}_{\sum_{p=1}^{i-1}\tau_{s,l}^{(p)}}]$

and proceed similarly as before to get

$\displaystyle\mathbb{E}^{*}\left[\left(\tau_{s,l}^{(i,\star,1)}\right)\mathbbm{1}\left[X_{\sum_{p=1}^{i}\tau_{s,l}^{(p)}+\tau_{s,l}^{(i,\star,1)}}\neq
s,\
X_{\sum_{p=1}^{i}\tau_{s,l}^{(p)}+\tau_{s,l}^{(i,\star,1)}+\tau_{s,l}^{(i,\star,2)}}=s\right]\right]$
$\displaystyle=\mathbb{E}^{*}\left[\left(\tau_{s,l}^{(i,\star,1)}\right)\mathbb{P}\left(X_{\sum_{p=1}^{i}\tau_{s,l}^{(p)}+\tau_{s,l}^{(i,\star,1)}}\neq
s,\
X_{\sum_{p=1}^{i}\tau_{s,l}^{(p)}+\tau_{s,l}^{(i,\star,1)}+\tau_{s,l}^{(i,\star,2)}}=s|\tau_{s,l}^{(i,\star,1)},\tau_{s,l}^{(i,\star,2)}\right)\right].$
(F.15)

We decompose
$\mathbb{P}\left(X_{\sum_{p=1}^{i}\tau_{s,l}^{(p)}+\tau_{s,l}^{(i,\star,1)}}\neq
s,\
X_{\sum_{p=1}^{i}\tau_{s,l}^{(p)}+\tau_{s,l}^{(i,\star,1)}+\tau_{s,l}^{(i,\star,2)}}=s|\tau_{s,l}^{(i,\star,1)},\tau_{s,l}^{(i,\star,2)}\right)$
into

$\displaystyle\mathbb{P}\left(X_{\sum_{p=1}^{i}\tau_{s,l}^{(p)}+\tau_{s,l}^{(i,\star,1)}+\tau_{s,l}^{(i,\star,2)}}=s|\tau_{s,l}^{(i,\star,1)},\tau_{s,l}^{(i,\star,2)},X_{\sum_{p=1}^{i}\tau_{s,l}^{(p)}+\tau_{s,l}^{(i,\star,1)}}\neq
s\right)$
$\displaystyle\qquad\qquad\times\mathbb{P}\left(X_{\sum_{p=1}^{i}\tau_{s,l}^{(p)}+\tau_{s,l}^{(i,\star,1)}}\neq
s|\tau_{s,l}^{(i,\star,1)},\tau_{s,l}^{(i,\star,2)}\right)$

We use $(E1)$ to bound the first term from above and $(E2)$ to bound the
second term from above in the previous equation. This gives us,

$\displaystyle\mathbb{P}\left(X_{\sum_{p=1}^{i}\tau_{s,l}^{(p)}+\tau_{s,l}^{(i,\star,1)}}\neq
s,\
X_{\sum_{p=1}^{i}\tau_{s,l}^{(p)}+\tau_{s,l}^{(i,\star,1)}+\tau_{s,l}^{(i,\star,2)}}=s|\tau_{s,l}^{(i,\star,1)},\tau_{s,l}^{(i,\star,2)}\right)$
$\displaystyle\leq M_{max}M_{opt},$

Substituting this value in the right hand side of eq. F.15 we get

$\displaystyle\mathbb{E}^{*}\left[\left(\tau_{s,l}^{(i,\star,1)}\right)\mathbbm{1}\left[X_{\sum_{p=1}^{i}\tau_{s,l}^{(p)}+\tau_{s,l}^{(i,\star,1)}}\neq
s,\
X_{\sum_{p=1}^{i}\tau_{s,l}^{(p)}+\tau_{s,l}^{(i,\star,1)}+\tau_{s,l}^{(i,\star,2)}}=s\right]\right]$
$\displaystyle\leq\mathbb{E}^{*}[\tau_{s,l}^{(i,\star,1)}]M_{max}M_{opt}$
$\displaystyle\leq T_{\star}M_{max}M_{opt},$

where the last inequality follows from an application of tower property. We
similarly have,

$\mathbb{E}^{*}\left[\left(\tau_{s,l}^{(i,\star,2)}\right)\mathbbm{1}\left[X_{\sum_{p=1}^{i}\tau_{s,l}^{(p)}+\tau_{s,l}^{(i,\star,1)}}\neq
s,\
X_{\sum_{p=1}^{i}\tau_{s,l}^{(p)}+\tau_{s,l}^{(i,\star,1)}+\tau_{s,l}^{(i,\star,2)}}=s\right]\right]\leq
T_{\star}M_{max}M_{opt}.$

Thus $2T_{\star}M_{max}M_{opt}$ is an upper bound to Term 2. Proceeding
similarly, we can find an upper bound to each term. Substituting these upper
bounds back into eq. F.13 we get

$\displaystyle\mathbb{E}\left[\tau_{s,l}^{(i)}|\mathcal{F}_{\sum_{p=1}^{i-1}\tau_{s,l}^{(p)}}\right]$
$\displaystyle\leq T_{\star}M_{max}+2T_{\star}M_{max}M_{opt}+\dots$
$\displaystyle=\sum_{j=1}^{\infty}jT_{\star}M_{max}M_{opt}^{j-1}$
$\displaystyle=\frac{T_{\star}M_{max}}{1-M_{opt}}\sum_{j=1}^{\infty}j(1-M_{opt})M_{opt}^{j-1}$
$\displaystyle=\frac{T_{\star}M_{max}}{M_{opt}(1-M_{opt})}.$

∎

###  F.8 Proof of Lemma 15

###### Proof.

That it is a controlled Markov chain is obvious. We only need to verify
ergodicity of $\tilde{\mathfrak{M}}^{(l)}$, and stationarity of controls
$a_{i}$. We first show that $\tilde{\mathfrak{M}}^{(l)}$ is irreducible. Since
$M^{(l)}$ is irreducible and aperiodic, there exists an integer $n_{ap}$ such
that $\left(M^{(l)}\right)^{n_{ap}}$ is a positive stochastic matrix. Observe
that $J\times J=J$, $J\times M^{(l)}=J$. Then,

$\left(\mathfrak{M}^{(l)}\right)^{2}=\mathfrak{M}^{(l)}\times\mathfrak{M}^{(l)}=\begin{bmatrix}(1-\upsilon)^{2}J&(1-\upsilon)\upsilon
J\\\ (1-\upsilon)\upsilon
J&\upsilon^{2}\left(M^{(l)}\right)^{2}\end{bmatrix}.$

Similarly, it can be shown that $\left(\mathfrak{M}^{(l)}\right)^{n_{ap}}$
depends only upon $\upsilon,\left(M^{(l)}\right)^{n_{ap}}$ and $J$. Thus,
$\left(\mathfrak{M}^{(l)}\right)^{n_{ap}}$ is positive and it is irreducible.

$\mathbb{P}(X_{2}=1,\omega_{2}=0|X_{1}=1,\omega_{1}=0)=\frac{1-\upsilon}{d}\mathbb{P}(\omega_{2}=\xi)>0$

Since $\mathbb{P}(\omega_{2}=\xi)=\min\\{\upsilon,1-\upsilon\\}>0$, this
proves that there exists a one-step path of positive probability from $(1,0)$
to $(1,0)$. Thus, state $(1,0)$ is aperiodic. Since the matrix is also
irreducible, all the states are aperiodic, and the transition matrix is
ergodic. Next, we verify the stationarity of the controls $a_{i}$. Let
$\hbar_{0}^{i-1}\in(\chi\times\\{0,1\\}\times\mathbb{I})^{i}$ be any history
and $(s_{i},\xi_{i})\in\chi\times\\{0,1\\}$. Then,

$\displaystyle\mathcal{L}(\tilde{a}_{i}|X_{i}=s_{i},\omega_{i}=\xi_{i},\mathcal{H}_{0}^{i-1}=\hbar_{0}^{i-1})$
$\displaystyle=\begin{cases}\mathcal{L}(a_{i}|X_{i}=s_{i},\omega_{i}=\xi_{i},\mathcal{H}_{0}^{i-1}=\hbar_{0}^{i-1})\text{
if }\xi_{i}=1\\\
\mathcal{L}(D_{i}^{(3)}|X_{i}=s_{i},\omega_{i}=\xi_{i},\mathcal{H}_{0}^{i-1}=\hbar_{0}^{i-1})\text{
if }\xi_{i}=0\\\ \end{cases}.$

However, if $\xi_{i}=1$, then $a_{i}$ is drawn uniformly over $\mathbb{I}$
independent of the history. And if $\xi_{i}=0$, then we draw from
$D_{i}^{(3)}$, which is distributed uniformly over $\mathbb{I}$ independent of
the history. Thus the controls are trivially stationary. This completes the
proof. ∎

###  F.9 Proof of Lemma 17

###### Proof.

As before, for some $i,j$ let $T_{\star}\in\left\\{0,1\right\\}^{m-j}$ and
$\hbar_{\star}\in\left\\{0,1\right\\}^{i+1}$, and denote by
$\left(\mathbbm{1}[X_{i}=s,a_{i}=l],\dots\mathbbm{1}[X_{0}=s,a_{0}=l]\right)$
by $\mathbbm{1}(\mathcal{H}_{0}^{i})$. Define
$\mathcal{S}_{\hbar_{\star}}:=\\{\hbar_{0}^{i}\in(\chi\times\mathbb{I})^{i+1}:\mathbbm{1}(\hbar_{0}^{i})=\hbar_{\star}\\}$.
Next observe that,

$\displaystyle\left|\mathbb{P}\left(\mathbbm{1}[X_{m}=s,a_{m}=l],\dots,\mathbbm{1}[X_{j}=s,a_{j}=l])\in\mathbb{T}_{\star}|\mathbbm{1}\left(\mathcal{H}_{0}^{i}\right)=\hbar_{\star}\right)\right.$
$\displaystyle\qquad\left.-\mathbb{P}\left(\mathbbm{1}[X_{m}=s,a_{m}=l],\dots,\mathbbm{1}[X_{j}=s,a_{j}=l])\in\mathbb{T}_{\star}\right)\right|$
$\displaystyle\leq\sup_{\begin{subarray}{c}\hbar_{0}^{i}\in\mathcal{S}_{\hbar_{\star}}\end{subarray}}\left|\mathbb{P}\left(\mathbbm{1}[X_{m}=s,a_{m}=l],\dots,\mathbbm{1}[X_{j}=s,a_{j}=l])\in\right.\mathbb{T}_{\star}|\mathcal{H}_{0}^{i}=\hbar_{0}^{i}\right)$
$\displaystyle\quad\left.-\mathbb{P}\left(\mathbbm{1}[X_{m}=s,a_{m}=l],\dots,\mathbbm{1}[X_{j}=s,a_{j}=l])\in\mathbb{T}_{\star}\right)\right|$
$\displaystyle\leq\sup_{\begin{subarray}{c}\hbar_{0}^{i}\in(\chi\times\mathbb{I})^{i+1}\end{subarray}}\left|\mathbb{P}\left(\mathbbm{1}[X_{m}=s,a_{m}=l],\dots,\mathbbm{1}[X_{j}=s,a_{j}=l])\in\right.\mathbb{T}_{\star}|\mathcal{H}_{0}^{i}=\hbar_{0}^{i}\right)$
$\displaystyle\quad\left.-\mathbb{P}\left(\mathbbm{1}[X_{m}=s,a_{m}=l],\dots,\mathbbm{1}[X_{j}=s,a_{j}=l])\in\mathbb{T}_{\star}\right)\right|$
$\displaystyle\leq\sup_{\begin{subarray}{c}\mathbb{T},\hbar_{0}^{i-1}\end{subarray}}\left|\mathbb{P}\left((X_{m},a_{m},\dots,X_{j},a_{j})\in\mathbb{T}|\mathcal{H}_{0}^{i}=\hbar_{0}^{i}\right)-\mathbb{P}\left(X_{m},a_{m},\dots,X_{j},a_{j}\in\mathbb{T}\right)\right|,$

where the first inequality follows because there exists at least one
$\hbar_{0}^{i}$ such that $\mathbbm{1}(\hbar_{0}^{i})=\hbar_{\star}$, and the
last inequality follows naturally by taking inversion of $\mathbbm{1}(\cdot)$
and the appropriate supremum. Now taking an appropriate supremum over
$\mathbb{T}_{\star},\hbar_{\star}$ we get,

$\displaystyle\sup_{\begin{subarray}{c}\mathbb{T}_{\star},\hbar_{\star}\end{subarray}}\left|\mathbb{P}\left(\mathbbm{1}[X_{m}=s,a_{m}=l],\dots,\mathbbm{1}[X_{j}=s,a_{j}=l])\in\mathbb{T}_{\star}|\mathbbm{1}\left(\mathcal{H}_{0}^{i}\right)=\hbar_{\star}\right)\right.$
$\displaystyle\qquad\left.-\mathbb{P}\left(\mathbbm{1}[X_{m}=s,a_{m}=l],\dots,\mathbbm{1}[X_{j}=s,a_{j}=l])\in\mathbb{T}_{\star}\right)\right|$
$\displaystyle\leq\sup_{\begin{subarray}{c}\mathbb{T},\hbar_{0}^{i-1}\end{subarray}}\left|\mathbb{P}\left((X_{m},a_{m},\dots,X_{j},a_{j})\in\mathbb{T}|\mathcal{H}_{0}^{i}=\hbar_{0}^{i}\right)-\mathbb{P}\left(X_{m},a_{m},\dots,X_{j},a_{j}\in\mathbb{T}\right)\right|$
$\displaystyle=\phi_{i,j}.$

This proves our lemma. ∎

###  F.10 Proof of Lemma 19

###### Proof.

Let $\mathcal{X}$ and $\mathcal{Y}$ be two events. Consider the following
term,

$\displaystyle\left|\mathbb{P}(X\in\mathcal{X},Y\in\mathcal{Y}|Z=z_{1})-\mathbb{P}(X\in\mathcal{X},Y\in\mathcal{Y}|Z=z_{2})\right|$
$\displaystyle\
=\left|\sum_{y\in\mathcal{Y}}\left[\mathbb{P}(X\in\mathcal{X},Y=y|Z=z_{1})-\mathbb{P}(X\in\mathcal{X},Y=y|Z=z_{2})\right\\}\right|$
$\displaystyle\
=\left|\sum_{y\in\mathcal{Y}}\left[\mathbb{P}(X\in\mathcal{X}|Y=y,Z=z_{1})\mathbb{P}(Y=y|Z=z_{1})-\mathbb{P}(X\in\mathcal{X}|Y=y,Z=z_{2})\mathbb{P}(Y=y|Z=z_{2})\right\\}\right|$

Adding and subtracting
$\mathbb{P}(X\in\mathcal{X}|Y=y,Z=z_{1})\mathbb{P}(Y=y|Z=z_{2})$ inside the
summation and applying triangle inequality we get,

$\displaystyle\left|\mathbb{P}(X\in\mathcal{X},Y\in\mathcal{Y}|Z=z_{1})-\mathbb{P}(X\in\mathcal{X},Y\in\mathcal{Y}|Z=z_{2})\right|$
$\displaystyle\leq\left|\sum_{y\in\mathcal{Y}}\left[\mathbb{P}(X\in\mathcal{X}|Y=y,Z=z_{1})\mathbb{P}(Y=y|Z=z_{2})-\mathbb{P}(X\in\mathcal{X}|Y=y,Z=z_{2})\mathbb{P}(Y=y|Z=z_{2})\right]\right|$
$\displaystyle\
+\left|\sum_{y\in\mathcal{Y}}\left[\mathbb{P}(X\in\mathcal{X}|Y=y,Z=z_{1})\mathbb{P}(Y=y|Z=z_{2})-\mathbb{P}(X\in\mathcal{X}|Y=y,Z=z_{1})\mathbb{P}(Y=y|Z=z_{1})\right]\right|$
$\displaystyle=\text{TERM 1+TERM 2}$

In the first term in the previous equation, $\mathbb{P}(Y=y|Z=z_{2})$ is
common. So, the first term can be rewritten as,

TERM 1
$\displaystyle=\left|\sum_{y\in\mathcal{Y}}\bigg{(}\left[\mathbb{P}(X\in\mathcal{X}|Y=y,Z=z_{1})-\mathbb{P}(X\in\mathcal{X}|Y=y,Z=z_{2})\right]\times\mathbb{P}(Y=y|Z=z_{2})\bigg{)}\right|$

We take the modulus inside the summation to get,

TERM 1
$\displaystyle\leq\sum_{y\in\mathcal{Y}}\bigg{(}\left|\mathbb{P}(X\in\mathcal{X}|Y=y,Z=z_{1})-\mathbb{P}(X\in\mathcal{X}|Y=y,Z=z_{2})\right|\mathbb{P}(Y=y|Z=z_{2})\bigg{)}$
$\displaystyle\leq\sup_{y_{0}\in\mathcal{Y}}\left|\mathbb{P}(X\in\mathcal{X}|Y=y_{0},Z=z_{1})-\mathbb{P}(X\in\mathcal{X}|Y=y_{0},Z=z_{2})\right|\sum_{y\in\mathcal{Y}}\mathbb{P}(Y=y|Z=z_{2})$
$\displaystyle=\sup_{y_{0}\in\mathcal{Y}}\left|\mathbb{P}(X\in\mathcal{X}|Y=y_{0},Z=z_{1})-\mathbb{P}(X\in\mathcal{X}|Y=y_{0},Z=z_{2})\right|\mathbb{P}(Y=\mathcal{Y}|Z=z_{2})$
$\displaystyle\leq\sup_{y_{0}\in\mathcal{Y}}\left|\mathbb{P}(X\in\mathcal{X}|Y=y_{0},Z=z_{1})-\mathbb{P}(X\in\mathcal{X}|Y=y_{0},Z=z_{2})\right|.$

We upper bound
$\left|\mathbb{P}(X\in\mathcal{X}|Y=y_{0},Z=z_{1})-\mathbb{P}(X\in\mathcal{X}|Y=y_{0},Z=z_{2})\right|$
by its corresponding total variation distance as,

$\sup_{y_{0}\in\mathcal{Y}}\left\|\mathcal{L}(X|Y=y_{0},Z=z_{1})-\mathcal{L}(X|Y=y_{0},Z=z_{2})\right\|_{TV}.$

Since $\mathcal{Y}\subseteq\Omega$ , we can further upper bound the previous
term by

$\displaystyle\sup_{y_{0}\in\Omega}\left\|\mathcal{L}(X|Y=y_{0},Z=z_{1})-\mathcal{L}(X|Y=y_{0},Z=z_{2})\right\|_{TV}.$

This gives us the following upper bound to the first term,

$\displaystyle\text{TERM
1}\leq\sup_{y_{0}\in\Omega}\left\|\mathcal{L}(X|Y=y_{0},Z=z_{1})-\mathcal{L}(X|Y=y_{0},Z=z_{2})\right\|_{TV}.$
(F.16)

Now focusing on the second term, let $\mathcal{Y}_{1}\subseteq\mathcal{Y}$ be
the largest set such that the probability difference
$\mathbb{P}\left(Y=y|Z=z_{1}\right)-\mathbb{P}\left(Y=y|Z=z_{2}\right)>0$ for
any $y\in\mathcal{Y}_{1}$. Let $\mathcal{Y}_{2}$ be the set difference
$\mathcal{Y}\backslash\mathcal{Y}_{1}$. This yields us the following
decomposition of the second term,

TERM 2
$\displaystyle=\left|\sum_{y\in\mathcal{Y}}\mathbb{P}(X\in\mathcal{X}|Y=y,Z=z_{1})\left[\mathbb{P}(Y=y|Z=z_{1})-\mathbb{P}(Y=y|Z=z_{2})\right]\right|$
$\displaystyle=\Bigg{|}\sum_{y\in\mathcal{Y}_{1}}\mathbb{P}(X\in\mathcal{X}|Y=y,Z=z_{1})\left[\mathbb{P}(Y=y|Z=z_{1})-\mathbb{P}(Y=y|Z=z_{2})\right]$
$\displaystyle\
+\sum_{y\in\mathcal{Y}_{2}}\mathbb{P}(X\in\mathcal{X}|Y=y,Z=z_{1})\left[\mathbb{P}(Y=y|Z=z_{1})-\mathbb{P}(Y=y|Z=z_{2})\right]\Bigg{|},$

which can be further upper bounded by,

$\displaystyle\Bigg{|}\left(\sup_{y_{1}\in\mathcal{Y}_{1}}\mathbb{P}(X=\mathcal{X}|Y=y_{1},Z=z_{1})\right)\sum_{y_{1}\in\mathcal{Y}_{1}}\left(\mathbb{P}(Y=y_{1}|Z=z_{1})-\mathbb{P}(Y=y_{1}|Z=z_{2})\right)$
$\displaystyle\
+\left(\inf_{y_{2}\in\mathcal{Y}_{2}}\mathbb{P}(X=\mathcal{X}|Y=y_{2},Z=z_{1})\right)\sum_{y_{2}\in\mathcal{Y}_{2}}\left(\mathbb{P}(Y=y_{2}|Z=z_{1})-\mathbb{P}(Y=y_{2}|Z=z_{2})\right)\Bigg{|}$
$\displaystyle=\Bigg{|}\left(\sup_{y_{1}\in\mathcal{Y}_{1}}\mathbb{P}(X=\mathcal{X}|Y=y_{1},Z=z_{1})\right)\left(\mathbb{P}(Y=\mathcal{Y}_{1}|Z=z_{1})-\mathbb{P}(Y=\mathcal{Y}_{1}|Z=z_{2})\right)$
$\displaystyle\
+\left(\inf_{y_{2}\in\mathcal{Y}_{2}}\mathbb{P}(X=\mathcal{X}|Y=y_{2},Z=z_{1})\right)\left(\mathbb{P}(Y=\mathcal{Y}_{2}|Z=z_{1})-\mathbb{P}(Y=\mathcal{Y}_{2}|Z=z_{2})\right)\Bigg{|}.$
Recall that if $\mathcal{P}_{1}$ and $\mathcal{P}_{2}$ are real numbers with
different signs,
$|\mathcal{P}_{1}+\mathcal{P}_{2}|\leq\max\\{|\mathcal{P}_{1}|,|\mathcal{P}_{2}|\\}$.
Using this fact, we can get the following upper bound to the previous
equation.
$\displaystyle\max\Bigg{\\{}\left|\left(\sup_{y_{1}\in\mathcal{Y}_{1}}\mathbb{P}(X\in\mathcal{X}|Y=y_{1},Z=z_{1})\right)\left(\mathbb{P}(Y\in\mathcal{Y}_{1}|Z=z_{1})-\mathbb{P}(Y\in\mathcal{Y}_{1}|Z=z_{2})\right)\right|,$
$\displaystyle\
\qquad\left|\left(\inf_{y_{2}\in\mathcal{Y}_{2}}\mathbb{P}(X=\mathcal{X}|Y=y_{2},Z=z_{1})\right)\left(\mathbb{P}(Y=\mathcal{Y}_{2}|Z=z_{1})-\mathbb{P}(Y=\mathcal{Y}_{2}|Z=z_{2})\right)\right|\Bigg{\\}}.$

We can upper bound the common probabilities in the previous terms by $1$. This
gives us the following upper bound to the previous term.

$\displaystyle\max\bigg{\\{}\left|\mathbb{P}(Y=\mathcal{Y}_{1}|Z=z_{1})-\mathbb{P}(Y=\mathcal{Y}_{1}|Z=z_{2})\right|,\left|\mathbb{P}(Y=\mathcal{Y}_{2}|Z=z_{1})-\mathbb{P}(Y=\mathcal{Y}_{2}|Z=z_{2})\right|\bigg{\\}},$

Since $\left\|\mathcal{L}(Y|Z=z_{1})-\mathcal{L}(Y|Z=z_{2})\right\|_{TV}$ is
an upper bound to both of the terms inside the maximum, we find the following
upper bound to the second term.

$\displaystyle\text{TERM
2}\leq\left\|\mathcal{L}(Y|Z=z_{1})-\mathcal{L}(Y|Z=z_{2})\right\|_{TV}.$
(F.17)

Combining equations F.16 and F.17 we find

$\displaystyle|\mathbb{P}(X\in\mathcal{X},Y\in\mathcal{Y}|Z=z_{1})$
$\displaystyle-\mathbb{P}(X\in\mathcal{X},Y\in\mathcal{Y}|Z=z_{2})|\leq\left\|\mathcal{L}(Y|Z=z_{1})-\mathcal{L}(Y|Z=z_{2})\right\|_{TV}$
$\displaystyle\
+\sup_{y_{0}\in\Omega}\left\|\mathcal{L}(X|Y=y_{0},Z=z_{1})-\mathcal{L}(X|Y=y_{0},Z=z_{2})\right\|_{TV}.$

Taking supremum over $\mathcal{X}$ and $\mathcal{Y}$,

$\displaystyle\left\|\mathcal{L}(X,Y|Z=z_{1})-\mathcal{L}(X,Y|Z=z_{2})\right\|_{TV}$
$\displaystyle\leq\left\|\mathcal{L}(Y|Z=z_{1})-\mathcal{L}(Y|Z=z_{2})\right\|_{TV}$
$\displaystyle\
+\sup_{y_{0}\in\Omega}\left\|\mathcal{L}(X|Y=y_{0},Z=z_{1})-\mathcal{L}(X|Y=y_{0},Z=z_{2})\right\|_{TV}.$

This completes the proof. ∎

###  F.11 Proof of Lemma 21

###### Proof.

Define the paired process $Y_{i}:=(X_{i},a_{i})$ on the paired state space
$\chi\times\mathbb{I}$. It follows from the definition of $\bar{\theta}_{i,j}$
in eq. 4.3 that,

$\displaystyle\bar{\theta}_{i,j}$
$\displaystyle=\sup_{s_{1},s_{2}\in\chi,l_{1},l_{2}\in\mathbb{I}}\|\mathcal{L}\left(X_{j}|X_{i}=s_{1},a_{i}=l_{1}\right)-\mathcal{L}\left(X_{j}|X_{i}=s_{2},a_{i}=l_{2}\right)\|_{TV}$
$\displaystyle\leq\sup_{s_{1},s_{2}\in\chi,l_{1},l_{2}\in\mathbb{I}}\|\mathcal{L}\left(X_{j},a_{j}|X_{i}=s_{1},a_{i}=l_{1}\right)-\mathcal{L}\left(X_{j},a_{j}|X_{i}=s_{2},a_{i}=l_{2}\right)\|_{TV}$

As seen in section 4.4, $(X_{i},a_{i})$ forms an inhomogenous Markov chain
with the probability of transition from $(s,l)$ to $(t,l^{\prime})$ at time
point $i$ is $M_{s,t}^{(l)}\times P_{t,l^{\prime}}^{(i)}$. It follows from
[21, Theorem 2 ] that

$\displaystyle\sup_{s_{1},s_{2}\in\chi,l_{1},l_{2}\in\mathbb{I}}\|\mathcal{L}\left(X_{j},a_{j}|X_{i}=s_{1},a_{i}=l_{1}\right)-\mathcal{L}\left(X_{j},a_{j}|X_{i}=s_{2},a_{i}=l_{2}\right)\|_{TV}$
$\displaystyle\qquad\leq\prod_{p=i}^{j-1}\left(1-\min_{(s_{1},l_{1}),(s_{2},l_{2})\in\chi\times\mathbb{I}}\sum_{(t,l^{\prime})\in\chi\times\mathbb{I}}\min\left\\{\left(M_{s_{1},t}^{(l_{1})}\times
P_{t,l^{\prime}}^{(i)}\right),\left(M_{s_{2},t}^{(l_{2})}\times
P_{t,l^{\prime}}^{(i)}\right)\right\\}\right).$ (F.18)

Recall that by hypothesis

$\min_{s\in\chi,l\in\mathbb{I}}M_{s,t}^{(l)}>M_{min},$

for any $t\in\chi_{0}$. This implies that for all $t\in\chi_{0}$,

$\min\left\\{\left(M_{s_{1},t}^{(l_{1})}\times
P_{t,l^{\prime}}^{(i)}\right),\left(M_{s_{2},t}^{(l_{2})}\times
P_{t,l^{\prime}}^{(i)}\right)\right\\}\geq M_{min}P_{t,l^{\prime}}^{(i)}.$

Decomposing the summation over $(t,l)\in\chi\times\mathbb{I}$ in eq. F.18 into
a summation over $(t,l)\in(\chi\backslash\chi_{0})\times\mathbb{I}$ and
$(t,l)\in\chi_{0}\times\mathbb{I}$ and substituting
$M_{min}P_{t,l^{\prime}}^{(i)}$ as the appropriate lower bound we get,

$\displaystyle\sum_{(t,l^{\prime})\in\chi\times\mathbb{I}}$
$\displaystyle\min\left\\{\left(M_{s_{1},t}^{(l_{1})}\times
P_{t,l^{\prime}}^{(i)}\right),\left(M_{s_{2},t}^{(l_{2})}\times
P_{t,l^{\prime}}^{(i)}\right)\right\\}$
$\displaystyle\geq\sum_{t\in\chi\backslash\chi_{0}}\sum_{l^{\prime}\in\mathbb{I}}\min\left\\{\left(M_{s_{1},t}^{(l_{1})}\times
P_{t,l^{\prime}}^{(i)}\right),\left(M_{s_{2},t}^{(l_{2})}\times
P_{t,l^{\prime}}^{(i)}\right)\right\\}+\sum_{(t,l^{\prime})\in\chi_{0}\times\mathbb{I}}M_{min}P_{t,l^{\prime}}^{(i)}$
$\displaystyle\geq\sum_{t\in\chi_{0}}\sum_{l^{\prime}\in\mathbb{I}}M_{min}P_{t,l^{\prime}}^{(i)}$
$\displaystyle=\sum_{t\in\chi_{0}}M_{min}\sum_{l^{\prime}\in\mathbb{I}}P_{t,l^{\prime}}^{(i)}$
$\displaystyle=|\chi_{0}|M_{min}.$

It follows that

$\displaystyle\prod_{p=i}^{j-1}\left(1-\min_{(s_{1},l_{1}),(s_{2},l_{2})\in\chi\times\mathbb{I}}\sum_{(t,l^{\prime})\in\chi\times\mathbb{I}}\min\left\\{\left(M_{s_{1},t}^{(l_{1})}\times
P_{t,l^{\prime}}^{(i)}\right),\left(M_{s_{2},t}^{(l_{2})}\times
P_{t,l^{\prime}}^{(i)}\right)\right\\}\right)$ $\displaystyle\
\leq\prod_{p=i}^{j-1}\left(1-|\chi_{0}|M_{min}\right)$ $\displaystyle\
=\left(1-|\chi_{0}|M_{min}\right)^{j-i-1}.$

Thus we prove that,

$\bar{\theta}_{i,j}\leq\left(1-|\chi_{0}|M_{min}\right)^{j-i-1}.$

Therefore,

$\sum_{j=i+1}^{\infty}\bar{\theta}_{i,j}\leq\frac{1}{1-|\chi_{0}|M_{min}}.$

Since $|\chi_{0}|M_{min}<\sum_{t\in\chi_{0}}M_{s,t}^{(l)}\ $ for any $s$ and
$l$, we observe that $|\chi_{0}|M_{min}<\sum_{t\in\chi_{0}}M_{s,t}^{(l)}\leq
1$. Therefore, $1-|\chi_{0}|M_{min}>0$. Choosing
$\mathbb{C}_{\theta}=1/(1-|\chi_{0}|M_{min})$ now completes the proof. ∎

###  F.12 Proof of Proposition 26

###### Proof.

We prove this fact by induction. Obviously,
$(X_{0},a_{0})\overset{d}{=}(\tilde{X}_{0},\tilde{a_{0}})$. Now, for some
$i\geq 1$, let $\left(X_{0},a_{0},\dots,X_{i},a_{i}\right)$ be identically
distributed to
$\left(\tilde{X}_{0},\tilde{a}_{0},\dots,\tilde{X}_{i},\tilde{a}_{i}\right)$.
Then, for $i+1$, we note that,

$\displaystyle\mathbb{P}\left(\tilde{X}_{i+1}=s_{i+1},\tilde{a}_{i+1}=l_{i+1},\dots,\tilde{X}_{0}=s_{0},\tilde{a}_{0}=l_{0}\right)$
$\displaystyle\
=\mathbb{P}\left(\tilde{a}_{i+1}=l_{i+1}|\tilde{X}_{i+1}=s_{i+1},\dots,\tilde{X}_{0}=s_{0}\right)$
$\displaystyle\quad\times\mathbb{P}\left(\tilde{X}_{i+1}=s_{i+1}|\tilde{X}_{i}=s_{i},\tilde{a}_{i}=l_{i},\dots,\tilde{a}_{0}=l_{0},\tilde{X}_{0}=s_{0}\right)$
$\displaystyle\quad\times\mathbb{P}(\tilde{X}_{i}=s_{i},\tilde{a}_{i}=l_{i},\dots,\tilde{X}_{0}=s_{0},\tilde{a}_{0}=l_{0})$
$\displaystyle\
=\mathbb{P}\left(\alpha_{i}^{(\tilde{X}_{0},\tilde{a_{0}},\dots,\tilde{X}_{i+1})}=l_{i+1}|\tilde{X}_{i+1}=s_{i+1},\dots,\tilde{X}_{0}=s_{0}\right)$
$\displaystyle\quad\times\mathbb{P}\left(X_{\tilde{X_{i}},\tilde{N}_{\tilde{X_{i}}}^{(i,\tilde{a}_{i})}+1}^{(\tilde{a}_{i})}=s_{i+1}|\tilde{X}_{i}=s_{i},\tilde{a}_{i}=l_{i},\dots,\tilde{a}_{0}=l_{0},\tilde{X}_{0}=s_{0}\right)$
$\displaystyle\quad\times\mathbb{P}(\tilde{X}_{i}=s_{i},\tilde{a}_{i}=l_{i},\dots,\tilde{X}_{0}=s_{0},\tilde{a}_{0}=l_{0})$
$\displaystyle\
=\mathbb{P}\left(\alpha_{i}^{(s_{0},l_{0},\dots,s_{i+1})}=l_{i+1}|\tilde{X}_{i+1}=s_{i+1},\dots,\tilde{X}_{0}=s_{0}\right)$
$\displaystyle\quad\times\mathbb{P}\left(X_{s_{i},\tilde{N}_{s_{i}}^{(i,l_{i})}+1}^{(l_{i})}=s_{i+1}|\tilde{X}_{i}=s_{i},\tilde{a}_{i}=l_{i},\dots,\tilde{a}_{0}=l_{0},\tilde{X}_{0}=s_{0}\right)$
$\displaystyle\quad\times\mathbb{P}(\tilde{X}_{i}=s_{i},\tilde{a}_{i}=l_{i},\dots,\tilde{X}_{0}=s_{0},\tilde{a}_{0}=l_{0}),$

where the equalities follow by substituting in the corresponding value of each
quantity. Observe that under the given conditional, such that
$\tilde{N}_{s_{i}}^{(i,l_{i})}+1$ is some fixed integer $n$. Then, the right-
hand side of the previous equation can be further decomposed into,

$\displaystyle\
\mathbb{P}\left(\alpha_{i}^{(s_{0},l_{0},\dots,s_{i+1})}=l_{i+1}|\tilde{X}_{i+1}=s_{i+1},\dots,\tilde{X}_{0}=s_{0}\right)$
$\displaystyle\quad\times\mathbb{P}\left(X_{s_{i},\tilde{N}_{s_{i}}^{(i,l_{i})}+1}^{(l_{i})}=s_{i+1}|\tilde{X}_{i}=s_{i},\tilde{a}_{i}=l_{i},\dots,\tilde{a}_{0}=l_{0},\tilde{X}_{0}=s_{0}\right)$
$\displaystyle\quad\times\mathbb{P}(\tilde{X}_{i}=s_{i},\tilde{a}_{i}=l_{i},\dots,\tilde{X}_{0}=s_{0},\tilde{a}_{0}=l_{0})$
$\displaystyle\
=\mathbb{P}\left(\alpha_{i}^{(s_{0},a_{0},\dots,s_{i+1})}=l_{i+1}|\tilde{X}_{i+1}=s_{i+1},\dots,\tilde{X}_{0}=s_{0}\right)$
$\displaystyle\quad\times\mathbb{P}\left(X_{s_{i},n}^{(l_{i})}=s_{i+1}|\tilde{X}_{i}=s_{i},\tilde{a}_{i}=l_{i},\dots,\tilde{a}_{0}=l_{0},\tilde{X}_{0}=s_{0}\right)$
$\displaystyle\quad\times\mathbb{P}(\tilde{X}_{i}=s_{i},\tilde{a}_{i}=l_{i},\dots,\tilde{X}_{0}=s_{0},\tilde{a}_{0}=l_{0})$
$\displaystyle\
=\mathbb{P}\left(\alpha_{i}^{(s_{0},a_{0},\dots,s_{i+1})}=l_{i+1}\right)\times\mathbb{P}\left(X_{s_{i},n}^{(l_{i})}=s_{i+1}\right)$
$\displaystyle\quad\times\mathbb{P}(\tilde{X}_{i}=s_{i},\tilde{a}_{i}=l_{i},\dots,\tilde{X}_{0}=s_{0},\tilde{a}_{0}=l_{0})$
(F.19) $\displaystyle\
=P_{l}^{(s_{i},l_{i-1},\dots,l_{0},s_{0})}M_{s,t}^{(l_{i})}\times\mathbb{P}(\tilde{X}_{i}=s_{i},\tilde{a}_{i}=l_{i},\dots,\tilde{X}_{0}=s_{0},\tilde{a}_{0}=l_{0})$
$\displaystyle\
=P_{l}^{(s_{i},l_{i-1},\dots,l_{0},s_{0})}M_{s,t}^{(l_{i})}\times\mathbb{P}(X_{i}=s_{i},a_{i}=l_{i},\dots,X_{0}=s_{0},a_{0}=l_{0}),$

where the last equality follows by induction hypothesis. It follows easily
from the last equality that

$\displaystyle\mathbb{P}\left(\tilde{X}_{i+1}=s_{i+1},\tilde{a}_{i+1}=l_{i+1},\dots,\tilde{X}_{0}=s_{0},\tilde{a}_{0}=l_{0}\right)$
$\displaystyle\
=\mathbb{P}\left(X_{i+1}=s_{i+1},a_{i+1}=l_{i+1},\dots,X_{0}=s_{0},a_{0}=l_{0}\right).$

This completes the proof. ∎

###  F.13 Proof of Lemma 27

###### Proof.

We introduce the notation $\chi^{\prime}$ to denote
$\left\\{(1,1),\dots,(d/3,1),(2,1),\dots,(d/3,k)\right\\}$. Observe that
$\mathbb{T}$ can be written as,

$\mathbb{T}:=\sum_{\Upsilon=0}^{dk/3-1}U_{\Upsilon}$

where $U_{\Upsilon}$ is the time spent between the $\Upsilon$-th and the
$\Upsilon+1$-th unique state-control pair visited in $\chi^{\prime}$. Next, we
observe two facts. Firstly, observe that for any element $(t,l^{\prime})$
belonging to $\chi^{\prime}$ we have

$\displaystyle\mathbb{P}\left(X_{i}=t,a_{i}=l^{\prime}|X_{i-1}=s,a_{i-1}=l\right)=\mathbb{P}\left(X_{i}=t,a_{i}=l^{\prime}\right)=\frac{3\iota}{dk}$

independent of any $(s,l)\in\chi\times\mathbb{I}$. Secondly, observe that the
probability of visiting a new state-control pair in $\chi_{\mathbb{I}}$ when
$\Upsilon$ unique states have already been visited is
${3\iota\left({dk}/{3}-\Upsilon\right)}/dk$. Together, these facts imply that

$U_{\Upsilon}\overset{d}{=}X_{\Upsilon}\text{ where }X_{\Upsilon}\sim
Geometric\left(\left(\frac{dk}{3}-\Upsilon\right)\frac{3\iota}{dk}\right).\leavevmode\nobreak\
$

It follows from section F.13 that,

$\displaystyle\mathbb{E}[\mathbb{T}]$
$\displaystyle=\left(\frac{dk}{3\iota}\sum_{\Upsilon=0}^{dk/3-1}\frac{1}{dk/3-\Upsilon}\right)$
where we have dropped the superscript $l$ from $\Upsilon^{(l)}$ for
convenience. Rewriting the previous equation we get,
$\displaystyle\mathbb{E}[\mathbb{T}]$
$\displaystyle=\frac{dk}{3\iota}\sum_{\Upsilon=1}^{dk/3}\frac{1}{\Upsilon}$
$\displaystyle>\frac{dk}{3\iota}\log\left(dk/3+1\right)\leavevmode\nobreak\ .$
(F.22)

where the last inequality follows from the Euler-Maclaurin (see for example,
[1]) approximation of a sum by its integral. We also observe that,

$\displaystyle\mathrm{Var}(U_{\Upsilon})=\frac{d^{2}k^{2}}{9\iota^{2}}\left(\frac{dk}{3}-\Upsilon\right)^{-2}\left[1-\left(\frac{dk}{3}-\Upsilon\right)\frac{3\iota}{dk}\right].$

The term inside the square brackets is a probability, and can be upper bounded
by $1$. Observe that when $\Upsilon\leq dk/3-1$ we can upper bound
$\mathrm{Var}(\mathbb{T})$ as

$\displaystyle\mathrm{Var}(\mathbb{T})$
$\displaystyle\leq\sum_{\Upsilon=0}^{dk/3-1}\frac{d^{2}k^{2}}{9\iota^{2}}\left(\frac{dk}{3}-\Upsilon\right)^{-2}$
$\displaystyle=\sum_{\Upsilon=1}^{dk/3}\frac{d^{2}k^{2}}{9\iota^{2}}\frac{1}{\Upsilon^{2}}$
$\displaystyle<\frac{d^{2}k^{2}}{9\iota^{2}}\frac{\pi^{2}}{6}$
$\displaystyle<\frac{d^{2}k^{2}}{9\iota^{2}}\frac{\pi^{2}}{4}.\leavevmode\nobreak\
$ (F.23)

where the second inequality follows from the fact that $\sum_{\Upsilon\geq
1}1/\Upsilon^{2}=\pi^{2}/6$. Using Cantelli’s inequality [19, Equation 5], we
obtain, for all
$0<\theta<{\mathbb{E}[\mathbb{T}]}/{\sqrt{\mathrm{Var}(\mathbb{T})}}$,

$\mathbb{P}\left(\mathbb{T}>\frac{dk}{3\iota}\log\left(\frac{dk}{3}+1\right)-\theta\frac{dk}{3\iota}\frac{\pi}{2}\right)\geq\frac{\theta^{2}}{1+\theta^{2}}.$

From the equations F.22 and F.23, we get that
${\mathbb{E}[\mathbb{T}]}/\left({\sqrt{\mathrm{Var}(\mathbb{T})}}\right)>\left(\log(dk/3)+1\right)/\pi$.
Substituting $\theta={(\log(dk/3)+1)/\pi}$ we get

$\displaystyle\mathbb{P}\left(\mathbb{T}>\frac{dk}{6\iota}\left(\log\left(\frac{dk}{3}\right)+1\right)\right)\geq\frac{1}{1+\left(\frac{\pi}{\log(dk/3)+1}\right)^{2}}>\frac{1}{1+\pi^{2}}.$

This proves the lemma. ∎