$\displaystyle\leq\C\frac{|X|_{\mathcal{L}}^{1/2}}{T_{m}}\mathcal{L}(S_{t_{m}},a)^{2}$
$\displaystyle\Bigr{|}{\mathbb{E}}\Bigr{[}\bigr{|}\frac{1}{T_{m}}\sum_{t}r(S_{t},A_{t})-{\mathbb{E}}[R]\bigl{|}^{4}\mathds{1}[\mathcal{B}_{m}]\Big{|}\mathcal{F}_{m},A_{t_{m}}=a\Bigl{]}\Bigl{|}^{1/2}$
$\displaystyle\leq\C\frac{|R|_{\mathcal{L}}^{1/2}}{T_{m}}\mathcal{L}(S_{t_{m}},a)^{2}.$
(90)

The bound for $C$ thus becomes

${\mathbb{E}}[|C|^{2}|\mathcal{F}_{m},A_{t_{m}}=a]\leq\frac{\C}{T_{m}^{2}}\mathcal{L}(S_{t_{m}},a)^{4}.$
(91)

Upper bounding all terms by the largest exponents and adding over the
different actions, we finally obtain

${\mathbb{E}}[|\eta_{m}|^{2}\mathds{1}[\mathcal{B}_{m}]|\mathcal{F}_{m}]\leq\frac{\C}{T_{m}}\sum_{a}\mathcal{L}(S_{t_{m}},a)^{4}\pi(a|S_{t_{m}}),\Theta_{m}\leq\frac{\C}{T_{m}}\mathcal{L}_{4}(S_{t_{m}}).$
(92)

That is it. $\Box$

###  C.4 Proof of Lemma 2

We will again use the notation $t_{m+1}-t_{m}=T_{m}$ and without loss of
generality we will assume that $T_{m}=\ell m^{\sigma/2+\kappa}$ instead of
$\lfloor\ell m^{\sigma/2+\kappa}\rfloor$. This can be assumed since for $m\geq
1$ there exist constants $c_{l},c_{u}>0$ such that $c_{l}\ell
m^{\sigma/2+\kappa}\leq t_{m+1}-t_{m}\geq c_{u}\ell m^{\sigma/2+\kappa}$. The
proof of Lemma 2 follows the same steps as in [13, Proposition 20]. However,
we have to quickly diverge and adapt the estimates to the case that there the
variance of $H_{m}$ depends on the states of a Markov chain. From the
assumptions, it can be shown that there is a unique differentiable orthogonal
projection map
$\mathfrak{p}:V_{\mathfrak{r},\delta}(\theta^{\star})\to\mathcal{M}\cap U$
from $V_{\mathfrak{r},\delta}(\theta^{\star})\cap U$ onto
$V_{\mathfrak{r},\delta}(\theta^{\star})\cap\mathcal{M}\cap U$. The distance
of $\Theta_{m}$ to the set of minima can then be upper bounded by the distance
to the projection
$\mathfrak{p}:V_{\mathfrak{r},\delta}(\theta^{\star})\to\mathcal{M}\cap U$ of
$\Theta_{m-1}$ by

$\displaystyle\mathrm{dist}(\Theta_{m},\mathcal{M}\cap U)^{2}$
$\displaystyle\leq|\Theta_{m}-\mathfrak{p}(\Theta_{m-1})|^{2}$
$\displaystyle\leq|\Theta_{m-1}-\mathfrak{p}(\Theta_{m-1})-\alpha_{m-1}\nabla
J(\Theta_{m-1})+(\alpha_{m-1}\nabla J(\Theta_{m-1})-\alpha_{m-1}H_{m-1})|^{2}$
(93)

After expanding (93) and taking expectations, however, the effect of bias
already appears and we must diverge from the analysis from [13, (44)]
thereafter. In particular, the effect of the bias of $H_{m-1}$ needs to be
handled in the terms

$\mathbb{E}\Bigl{[}2\Bigl{\langle}\Theta_{m-1}-\mathfrak{p}(\Theta_{m-1})-\alpha_{m-1}\nabla
J(\Theta_{m-1}),\alpha_{m-1}\nabla
J(\Theta_{m-1})-\alpha_{m-1}H_{m-1}\Bigr{\rangle}\mathds{1}[\mathcal{B}_{m-1}]\Bigr{]},$
(94)

and

$\displaystyle\mathbb{E}\Bigl{[}\Big{|}\alpha_{m-1}\nabla
J(\Theta_{m-1})-\alpha_{m-1}H_{m-1}\Big{|}^{2}\mathds{1}[\mathcal{B}_{m-1}]\Bigr{]}=(\alpha_{m-1})^{2}\mathbb{E}\Bigl{[}|\eta_{m-1}|^{2}\mathds{1}[\mathcal{B}_{m-1}]\Bigr{]}.$
(95)

We specifically require bounds of these terms without relying on independence
of the iterands.

We focus on (95) first. Recall for $m>0$, that $\mathcal{F}_{m}$ is the sigma
algebra defined in (29). By using the tower property of the conditional
expectation and conditioning on $\mathcal{F}_{m-1}$, from Lemma 1 together
with the fact that $T_{m}<cT_{m-1}$ for some $c>0$, we obtain directly

$\displaystyle\eqref{eqn:Quadratic_term}=(\alpha_{m-1})^{2}\mathbb{E}\Bigl{[}\mathbb{E}\Bigl{[}|\eta_{m-1}|^{2}\mathds{1}[\mathcal{B}_{m-1}]\big{|}\mathcal{F}_{m-1}\Bigr{]}\Bigr{]}$
$\displaystyle\overset{\textnormal{(
Lemma~{}\ref{lem:Bounded_norms_on_the_gradient_estimator}
)}}{\leq}(\alpha_{m-1})^{2}\frac{\C}{T_{m}}\mathbb{E}[\mathcal{L}_{4}(S_{t_{m-1}})^{2}\mathds{1}[\mathcal{B}_{m-1}]].$
(96)

Let us next bound (94). Note that this term does not vanish due to dependence
of the samples conditional on $\mathcal{F}_{m-1}$. In our case, however, we
have a Markov chain trajectory whose kernel will depend on $\Theta_{m-1}$. Let

$Z_{m-1}=\Theta_{m-1}-\mathfrak{p}(\Theta_{m-1})-\alpha_{m-1}\nabla
J(\Theta_{m-1}).$ (97)

We use the law of total expectation again on (94). Note that $Z_{m-1}$ and
$\mathcal{B}_{m-1}$ are $\mathcal{F}_{m-1}$-measurable.

$\displaystyle\eqref{eqn:Cross_term}$ $\displaystyle\leq
2\alpha_{m-1}{\mathbb{E}}\Bigl{[}\bigl{\langle}\mathds{1}[\mathcal{B}_{m-1}]Z_{m-1},{\mathbb{E}}[\eta_{m-1}|\mathcal{F}_{m-1}]\bigr{\rangle}\Bigr{]}$
$\displaystyle\overset{\textnormal{(i)}}{\leq}2\alpha_{m-1}\mathbb{E}\Bigl{[}|Z_{m-1}|^{2}\mathds{1}[\mathcal{B}_{m-1}]\Bigr{]}^{1/2}\mathbb{E}\Bigl{[}|{\mathbb{E}}[\eta_{m-1}\mathds{1}[\mathcal{B}_{m-1}]|\mathcal{F}_{m-1}]|^{2}\Bigr{]}^{1/2}$
$\displaystyle\overset{\textnormal{(ii)}}{\leq}2\alpha_{m-1}\mathbb{E}\Bigl{[}|Z_{m-1}|^{2}\mathds{1}[\mathcal{B}_{m-1}]\Bigr{]}^{1/2}\mathbb{E}\Bigl{[}\mathds{1}[\mathcal{B}_{m-1}]\mathcal{L}_{4}(S_{t_{m-1}})^{2}\Bigr{]}^{1/2}\frac{\C}{T_{m}}$
(98)

where (i) have used Cauchy–Schwartz and (ii) Lemma 1 and the fact that for
some $c>0$, $T_{m}<cT_{m-1}$.

The terms in (96) and (98) containing $\mathcal{L}_{4}(S_{t_{m}})$ can be
upper bounded as follows. From the definition of (32) and since $v\geq 16$, by
a generalized mean inequality and the fact that $\mathcal{L}(s,a)\geq 1$ for
any $(s,a)\in\mathcal{S}\times\mathcal{A}$ we have

$\mathcal{L}_{4}(s)\leq\mathcal{L}_{v}(s)^{4/v}\leq\mathcal{L}_{v}(s)^{1/4}.$
(99)

Now, by Lemma 6, there exists $D>0$ such that for all $m\in\mathbb{N}$

$\mathbb{E}\Bigl{[}\mathds{1}[\mathcal{B}_{m-1}]\mathcal{L}_{4}(S_{t_{m-1}})^{2}\Bigr{]}\leq\mathbb{E}\Bigl{[}\mathds{1}[\mathcal{B}_{m-2}]\mathcal{L}_{4}(S_{t_{m-1}})^{2}\Bigr{]}\overset{\textnormal{(
\ref{eqn:inequality_lyapunov_functions})}}{\leq}\mathbb{E}\Bigl{[}\mathds{1}[\mathcal{B}_{m-2}]\mathcal{L}_{v}(S_{t_{m-1}})\Bigr{]}\leq
D.$ (100)

For the other term in (98), we can use the same bound used in [13, (41)]:
There exists constants $y,c>0$ depending on $J,\theta^{\star}$ and
$\mathfrak{r}_{0}$ such that on the event $\mathcal{B}_{m-1}$ we have

$\displaystyle|Z_{m-1}|^{2}$
$\displaystyle\leq\bigl{(}1-\alpha_{m-1}y\bigr{)}^{2}\mathrm{dist}(\Theta_{m-1},\mathcal{M}\cap
U)^{2}$
$\displaystyle+c\bigl{(}1-\alpha_{m-1}y\bigr{)}\alpha_{m-1}\mathrm{dist}(\Theta_{m-1},\mathcal{M}\cap
U)^{3}$
$\displaystyle+c(\alpha_{m-1})^{2}\mathrm{dist}(\Theta_{m-1},\mathcal{M}\cap
U)^{4}.$ (101)

The bound in (101) characterizes the fact that, close to the manifold of
maximizers, the projection is differentiable and can be approximated by an
orthogonal expansion of $J$ around the manifold of maximizers. The error terms
of this expansion can be bounded depending on the Hessian at
$\mathfrak{p}(\Theta_{m-1})\in\mathcal{M}\cap U$,
$\mathrm{Hess}_{\mathfrak{p}(\Theta_{m-1})}\ J$ . We refer to [13, Proposition
17] for a proof of this fact.

We will now use an induction argument to show the claim of the lemma. We will
namely assume for the time being that for $m-1$ we have

$\mathbb{E}\Bigl{[}(\mathrm{dist}(\Theta_{m-1},\mathcal{M}\cap
U)\wedge\delta)^{2}\mathds{1}[\mathcal{B}_{m-1}]\Bigr{]}\leq\delta^{2}c(\alpha)(m-1)^{-\sigma-\kappa},$
(102)

where $c(\alpha)>0$ is a function of $a$ to be determined. We want to show
(102) for $m$. To do so we will use (101) to bound $Z_{m-1}$. Suppose that
there exists a sequence $\\{b_{l}\\}_{l>0}\subset\mathbb{R}_{+}$ such that we
have

$\mathbb{E}\Bigl{[}|Z_{m-1}|^{2}\mathds{1}[\mathcal{B}_{m-1}]\Bigr{]}\leq
b_{m-1}.$ (103)

Using (103) in (98) yields that for some $\Cl{5}>0$ we have:

$\eqref{eqn:Cross_term}\leq
2(b_{m-1})^{1/2}\alpha_{m-1}D^{1/2}\frac{\Cr{5}}{T_{m}}.$ (104)

From the expansion of (93) and combining the bounds of (101) and (104)
together we obtain

$\displaystyle\mathbb{E}\Bigl{[}\mathrm{dist}(\Theta_{m},\mathcal{M}\cap
U)^{2}\mathds{1}[\mathcal{B}_{m-1}]\Bigr{]}$ $\displaystyle\leq b_{m-1}$
$\displaystyle+2(b_{m-1})^{1/2}\alpha_{m-1}D^{1/2}\frac{\Cr{5}}{T_{m}}$
$\displaystyle+(\alpha_{m-1})^{2}\frac{\C}{T_{m}}D.$ (105)

We show now that from the induction hypothesis, if (102) holds, then we also
have the bound

$b_{m-1}\leq c(\alpha)\delta^{2}m^{-\sigma-\kappa}-\delta^{2}\frac{\alpha
y}{2}c(\alpha)(m-1)^{-\sigma-\kappa}m^{-\sigma}.$ (106)

Indeed, taking expectations in (101) and using the bound (102) yields

$\displaystyle
b_{m-1}\leq\bigl{(}1-\alpha_{m-1}y\bigr{)}^{2}c(\alpha)(m-1)^{-\sigma-\kappa}$
$\displaystyle+c(\alpha)\bigl{(}1-\alpha_{m-1}y\bigr{)}\alpha_{m-1}\delta
c(\alpha)(m-1)^{-\sigma-\kappa}$
$\displaystyle+c(\alpha)(\alpha_{m-1})^{2}\delta^{2}c(\alpha)(m-1)^{-\sigma-\kappa}.$
(107)

Recall that $\alpha_{m-1}=\alpha m^{-\sigma/2-\kappa}$. Adding and subtracting
$c(\alpha)m^{-\sigma-\kappa}$ in (107), we obtain that

$\displaystyle b_{m-1}\leq$ $\displaystyle c(\alpha)m^{-\sigma-\kappa}$
$\displaystyle+c(\alpha)m^{-\sigma}(m-1)^{-\sigma-\kappa}\mathopen{}\mathclose{{}\left(m^{\sigma}-(m-1)^{\sigma+\kappa}m^{-\kappa}-2\alpha
y+\frac{\alpha^{2}y}{m^{\sigma}}+\bigl{(}1-\frac{\alpha
y}{m^{\sigma}}\bigr{)}\alpha\delta+\delta^{2}\frac{\alpha^{2}y^{2}}{m^{\sigma}}}\right)$

Note now that there exists $m_{0}(a)>0$ such that if $m\geq m_{0}(a)$, we have

$m^{\sigma}-(m-1)^{\sigma+\kappa}m^{-\kappa}-\alpha
y+\frac{\alpha^{2}y}{m^{\sigma}}<-\frac{\alpha y}{2}.$ (108)

Indeed, note that the latter equation can be satisfied for $m\geq m_{0}(a)$
since there exists a constant $c>0$ depending on $\sigma$ and $\kappa$ such
that

$\displaystyle m^{\sigma}-(m-1)^{\sigma+\kappa}m^{-\kappa}$ $\displaystyle\leq
m^{-\kappa}(m^{\sigma+\kappa}-(m-1)^{\sigma+\kappa})$ $\displaystyle\leq
m^{-\kappa}(\sigma+\kappa)\max[(m-1)^{\sigma+\kappa-1},m^{\sigma+\kappa-1}]$
$\displaystyle\leq\Cl{6}(\sigma+\kappa)m^{\sigma-1}.$ (109)

In this case we have that

$m_{0}(\alpha)=\Bigl{(}\frac{2\Cr{6}(\sigma+\kappa)}{y\alpha}\Bigr{)}^{1-\sigma}>\frac{c^{\prime}}{\alpha^{1-\sigma}}.$
(110)

Then for $m>m_{0}(\alpha)$, we will have

$\displaystyle b_{m}\leq$ $\displaystyle
c(\alpha)m^{-\sigma-\kappa}+c(\alpha)m^{-\sigma}(m-1)^{-\sigma-\kappa}\mathopen{}\mathclose{{}\left(-\frac{\alpha
y}{2}+\bigl{(}1-\frac{\alpha
y}{m^{\sigma}}\bigr{)}\alpha\delta+\delta^{2}\frac{\alpha^{2}y^{2}}{m^{\sigma}}}\right).$

Choose $\delta\in(0,\delta_{1}(\alpha)]$, where $\delta_{1}(\alpha)$ is a
bound that we will choose appropriately, such that for any $m\geq
m_{0}(\alpha)$ we have

$\bigl{(}1-\frac{\alpha
y}{m^{\sigma}}\bigr{)}\alpha\delta+\delta^{2}\frac{\alpha^{2}y^{2}}{m^{\sigma}}\leq\alpha
y.$ (111)

Thus, from (102) we obtain (106). With (106) with an appropriate choice of
$c(\alpha)$, we can now show (102) for $m$. We will namely choose $c(\alpha)$
as follows

$c(\alpha)=\max\Bigl{(}\frac{c^{\prime}}{\alpha^{(1-\sigma)(\sigma+\kappa)}},\frac{4C^{2}D+4yCD\alpha\ell}{\delta^{2}\ell^{2}y^{2}}\Bigr{)},$
(112)

where recall that $\delta\in(0,\delta_{1}(\alpha)]$ and $\delta_{1}(\alpha)$
were chosen so that (111) holds. Let $L=\ell^{-1}$. Substituting the bound of
(106) into (105) and recalling that $T_{m}=m^{\kappa+\sigma/2}\ell$ yields

$\displaystyle\mathbb{E}\Bigl{[}(\mathrm{dist}(\Theta_{m},\mathcal{M}\cap
U))^{2}\mathds{1}[\mathcal{B}_{m-1}]\Bigr{]}\leq
c(\alpha)\delta^{2}m^{-\sigma-\kappa}-\frac{\alpha
y}{2}c(\alpha)\delta^{2}(m-1)^{-\sigma-\kappa}m^{-\sigma}$
$\displaystyle\phantom{aaaaaaaaaaaaa}+2(c(\alpha)\delta^{2}m^{-\sigma-\kappa}-\frac{\alpha\lambda}{2}c(\alpha)\delta^{2}(m-1)^{-\sigma-\kappa}m^{-\sigma})^{1/2}\alpha
m^{-\sigma}D^{1/2}\frac{\Cr{5}}{T_{m}}+Dm^{-2\sigma}\frac{\alpha^{2}\Cr{5}}{T_{m}}$
$\displaystyle\leq
c(\alpha)\delta^{2}m^{-\sigma-\kappa}+m^{-\sigma}(2\sqrt{c(\alpha)}\delta\Cr{5}aD^{1/2}Lm^{-\sigma-3\kappa/2}+\Cr{5}D\alpha^{2}Lm^{-3\sigma/2-\kappa}-c(\alpha)\delta^{2}\alpha
y(m-1)^{-\sigma-\kappa})$ $\displaystyle\leq
c(\alpha)\delta^{2}m^{-\sigma-\kappa}+m^{-\sigma}(m-1)^{-\sigma-\kappa}(2\sqrt{c(\alpha)}\delta\Cr{5}aD^{1/2}L+\Cr{5}D\alpha^{2}L-c(\alpha)\delta^{2}\alpha
y).$ (113)

By the choice of $c(\alpha)$ in (112), for any $\kappa\geq 0$ we have the
following inequality

$2\sqrt{c(\alpha)}\delta\Cr{6}D^{1/2}L+\Cr{6}DaL-c(\alpha)\delta^{2}y<0.$
(114)

Hence, with this choice of $c(\alpha)$, in (113) the latter term in the right-
hand side is negative for any $m\geq 2$ and the induction step follows if
$m>m_{0}(\alpha)$. That is, we have for some $c>0$ that and when
$m>m_{0}(\alpha)$ that

$\mathbb{E}\Bigl{[}\mathrm{dist}(4\Theta_{m},\mathcal{M}\cap
U)^{2}\mathds{1}[\mathcal{B}_{m-1}]\Bigr{]}\leq
c\max\Bigl{(}\frac{\delta^{2}}{a^{(1-\sigma)(\sigma+\kappa)}},\frac{(1+\alpha\ell)}{\ell^{2}}\Bigr{)}m^{-\sigma-\kappa}.$
(115)

We have left to show that the induction hypothesis holds in (102) for some
$m$. Recall that $m>m_{0}(\alpha)$ is the only restriction we needed on the
starting point for the induction argument to work—$\delta$ was already chosen
depending on $\alpha$ in (111). From the choice

$m_{0}(\alpha)\geq\frac{c^{\prime}}{\alpha^{1-\sigma}},$ (116)

if $m\leq m_{0}(\alpha)$, the following slightly changed version of (102) will
hold; namely

$\mathbb{E}\Bigl{[}(\mathrm{dist}(\Theta_{m},\mathcal{M}\cap
U)^{2}\wedge\delta^{2})\mathds{1}[\mathcal{B}_{m-1}]\Bigr{]}\leq\delta^{2}c(\alpha)m^{-\sigma-\kappa}.$
(117)

Hence, by same arguments conducted with (117) instead of(102), we have shown
by induction that (117) holds for $m>0$.

For convenience, we will further show that there exists a constant $\Cl{7}>0$
such that for all $m>0$ we have

$\mathbb{E}\Bigl{[}(\mathrm{dist}(\Theta_{m},\mathcal{M}\cap
U)^{2}\wedge\delta^{2})\mathds{1}[\mathcal{B}_{m-1}]\Bigr{]}\leq\Cr{7}m^{-\sigma-\kappa}.$
(118)

Fix $\Cr{7}>0$. Choose $\delta_{0}\leq\delta_{1}(\alpha)$ depending on
$\alpha$ small enough and $\ell_{0}>0$ large enough such that for
$\delta\in(0,\delta_{0}]$ and $\ell\in[\ell_{0},\infty)$ we have that

$\displaystyle\frac{c^{\prime}\delta^{2}}{\alpha^{(1-\sigma)(\sigma+\kappa)}}$
$\displaystyle<\Cr{7}$ $\displaystyle\frac{c(1+\alpha\ell)}{\ell^{2}}$
$\displaystyle<\Cr{7},$ (119)

With the conditions in (119), the proof of the lemma follows noting that
$\delta^{2}c(\alpha)=\delta^{2}c(\alpha,\ell)<\Cr{7}$.

###  C.5 Proof of Lemma 3

We will again use the notation that $t_{m+1}-t_{m}=T_{m}$ and without loss of
generality assume that $T_{m}=\ell m^{\sigma/2+\kappa}$ as in Section C.4. The
proof of Lemma 3 also mainly follows the steps of [13]. However, we again need
to take care of the terms that the bias and lack of independence generate in
the analysis.

The bounding starts noting the inequality

$\mathbb{E}\Bigl{[}\max_{1\leq l\leq
m}\bigl{|}\Theta_{l}-\Theta_{0}\bigr{|}\mathds{1}[\mathcal{B}_{l-1}]\Bigr{]}\leq\sum_{l=1}^{m}\mathbb{E}[|\Theta_{l}-\Theta_{l-1}|^{2}\mathds{1}[\mathcal{B}_{l-1}]]^{1/2}.$
(120)

We will show that there exists a constant $c>0$ such that for $l\in[m]$ we
have

$\mathbb{E}[|\Theta_{l+1}-\Theta_{l}|^{2}\mathds{1}[\mathcal{B}_{l}]]^{1/2}\leq
c\alpha\Bigl{(}l^{-3/2\sigma-\kappa/2}+\sqrt{\frac{1}{\ell}}l^{-5\sigma/8-\kappa/2}\Bigr{)},$
(121)

where the exponents of $\sigma$ and $\kappa$ already differ from the result in
[13], and are required to account for the lack of independence and bias.
Following the steps from [13], in the neighborhood
$V_{\mathfrak{r},\delta}(\theta^{\star})$, for each $l\leq m$ there is a
random variable $\epsilon_{l}:\mathcal{B}_{l}\to\mathbb{R}^{n}$ and there
exists a constant $c>0$ such that

$|\epsilon_{l}|<c\mathrm{dist}(\Theta_{l},\mathcal{M}\cap U)^{2}$ (122)

and such that on the event $\mathcal{B}_{l}$ we have

$\nabla
J(\Theta_{l})=\mathrm{Hess}_{\mathfrak{p}(\Theta_{l})}(\Theta_{l}-\mathfrak{p}(\Theta_{l}))+\epsilon_{l}.$
(123)

Recalling the definition of $\eta_{l}$ in (31), we have then the equality

$\Theta_{l+1}=\Theta_{l}-\alpha_{l}\mathrm{Hess}_{\mathfrak{p}(\Theta_{l})}(\Theta_{l}-\mathfrak{p}(\Theta_{l}))-\alpha_{l}\epsilon_{l}+\alpha_{l}\eta_{l}$
(124)

Define

$\tilde{\Theta}_{l}=\Theta_{l}-\alpha_{l}\mathrm{Hess}_{\mathfrak{p}(\Theta_{l})}(\Theta_{l}-\mathfrak{p}(\Theta_{l})).$
(125)

We use the triangle inequality with in (124) separating
$\Theta_{l+1}-\Theta_{l}$ as the summands of $\Theta_{l+1}-\tilde{\Theta}_{l}$
and $\tilde{\Theta}_{l}-\Theta_{l}$.

We estimate first $|\Theta_{l+1}-\tilde{\Theta}_{l}|^{2}$. In our case, after
expanding
$\mathbb{E}[|\Theta_{l+1}-\tilde{\Theta}_{l}|^{2}\mathds{1}[\mathcal{B}_{l}]]$,
we diverge from [13, (58)] and we need to bound

$\alpha_{l}^{2}\mathbb{E}\Bigl{[}\mathds{1}[\mathcal{B}_{l}]\langle\epsilon_{l},\eta_{l}\rangle\Bigr{]}.$
(126)

Similar to the proof of Lemma 2, we can condition on $\mathcal{F}_{l}$ and
using that $\epsilon_{l}$ and $\mathcal{B}_{l}$ are
$\mathcal{F}_{l}$-measurable together with the Cauchy–Schwartz inequality, we
have

$\displaystyle\alpha_{l}^{2}\mathbb{E}\Bigl{[}\mathds{1}[\mathcal{B}_{l}]\bigl{\langle}\epsilon_{l},\eta_{l}\bigr{\rangle}\Bigr{]}$
$\displaystyle\leq\alpha_{l}^{2}\mathbb{E}\Bigl{[}\bigl{\langle}\mathds{1}[\mathcal{B}_{l}]\epsilon_{l},\mathbb{E}\bigl{[}\eta_{l}\mathds{1}[\mathcal{B}_{l}]|\mathcal{F}_{l}\bigr{]}\bigr{\rangle}\Bigr{]}$
$\displaystyle\leq\alpha_{l}^{2}\mathbb{E}\Bigl{[}\mathds{1}[\mathcal{B}_{l}]|\epsilon_{l}|^{2}\Bigr{]}^{1/2}\mathbb{E}\Bigl{[}|\mathbb{E}\bigl{[}\eta_{l}\mathds{1}[\mathcal{B}_{l}]|\mathcal{F}_{l}\bigr{]}|^{2}\Bigr{]}^{1/2}$
(127)

Since $\mathds{1}[\mathcal{B}_{m}]\leq\mathds{1}[\mathcal{B}_{m-1}]$, we can
bound

$\mathbb{E}\Bigl{[}\big{|}\mathbb{E}[\eta_{l}\mathds{1}[\mathcal{B}_{l}]|\mathcal{F}_{l}]\big{|}^{2}\Bigr{]}^{1/2}\overset{\textnormal{(Lemma~{}\ref{lem:Bounded_norms_on_the_gradient_estimator})}}{\leq}\mathbb{E}\Bigl{[}\mathds{1}[\mathcal{B}_{l}]\frac{\C^{2}}{T_{l}^{2}}\mathcal{L}_{v}(S_{t_{l}})\Bigr{]}^{1/2}\overset{\textnormal{(Lemma~{}\ref{lemma:expectation_L_is_bounded})}}{\leq}\frac{\C}{T_{l}}.$
(128)

For the remaining term in (127), recall that on the event $\mathcal{B}_{l}$,
since $\Theta_{l}\in V_{\mathfrak{r},\delta}(\theta^{\star})$, we have that
$\mathrm{dist}(\Theta_{l},\mathcal{M}\cap U)\leq\delta$. Hence, we can bound
for any $l>0$ that

$\displaystyle\mathbb{E}\Bigl{[}\mathds{1}[\mathcal{B}_{l}]|\epsilon_{l}|^{2}\Bigr{]}^{1/2}$
$\displaystyle\overset{\textnormal{(\ref{eqn:proof_lemma6_epsilon})}}{\leq}(\alpha_{l})^{2}{\mathbb{E}}[\mathrm{dist}(\Theta_{l},\mathcal{M}\cap
U)^{4}\mathds{1}[\mathcal{B}_{l}]]^{1/2}\frac{\Cl{8}}{T_{l+1}}$
$\displaystyle\leq(\alpha_{l})^{2}\delta^{2}{\mathbb{E}}[\mathrm{dist}(\Theta_{l},\mathcal{M}\cap
U)^{2}\mathds{1}[\mathcal{B}_{l}]]^{1/2}\frac{\Cr{8}}{T_{l+1}}$
$\displaystyle\leq(\alpha_{l})^{2}\delta^{2}{\mathbb{E}}[\mathrm{dist}(\Theta_{l},\mathcal{M}\cap
U)^{2}\mathds{1}[\mathcal{B}_{l-1}]]^{1/2}\frac{\Cr{8}}{T_{l+1}}$
$\displaystyle\overset{\textnormal{(Lemma~{}\ref{lem:conditional_convergence_in_basin})}}{\leq}(\alpha_{l})^{2}\delta^{2}l^{-\sigma/2-\kappa/2}\frac{\C}{T_{l}}.$
(129)

The estimation of the remaining terms in the expansion of
$\mathbb{E}[|\Theta_{l}-\tilde{\Theta}_{l-1}|^{2}\mathds{1}[\mathcal{B}_{l-1}]]$
can be conducted in the same way as that in [13], to which we refer for the
details to the interested reader. Together with the estimate of (129) that
accounts for the biases we have that

$\displaystyle{\mathbb{E}}[|\Theta_{l}-\tilde{\Theta}_{l-1}|^{2}\mathds{1}[\mathcal{B}_{l}]]$
$\displaystyle\leq\C(\alpha_{l})^{2}\delta^{2}\mathbb{E}\Bigl{[}\mathrm{dist}(\Theta_{l},\mathcal{M}\cap
U)^{2}\mathds{1}[\mathcal{B}_{l}]\Bigr{]}$
$\displaystyle+2\delta\mathbb{E}\Bigl{[}\mathrm{dist}(\Theta_{l},\mathcal{M}\cap
U)^{2}\mathds{1}[\mathcal{B}_{l}]\Bigr{]}^{1/2}\frac{\Cl{9}}{T_{l}}+(\alpha_{l})^{2}\frac{\Cl{9}}{T_{l}}$
$\displaystyle\leq\C(\alpha_{l})^{2}\Bigl{[}\delta^{2}l^{-\sigma-\kappa}+2\delta
l^{-\sigma/2-\kappa/2}\frac{1}{T_{l}}+\frac{1}{T_{l}}\Bigr{]}.$ (130)

Substituting $T_{l}=t_{l+1}-t_{l}=l^{\kappa+\sigma/2}\ell$ and using
$\alpha_{l}<\alpha_{l-1}=\alpha l^{-\sigma}$ into (130) yields the bound

$\displaystyle\mathbb{E}\bigl{[}|\Theta_{l}-\tilde{\Theta}_{l-1}|^{2}\mathds{1}[\mathcal{B}_{l-1}]\bigr{]}$
$\displaystyle\leq\C\frac{\alpha^{2}}{l^{2\sigma}}\Bigl{(}\delta^{2}\frac{1}{l^{\sigma+\kappa}}+2\delta\frac{1}{l^{\sigma+3\kappa/2\ell}}+\frac{1}{l^{\kappa+\sigma/2}}\Bigr{)}$
$\displaystyle\leq\C\frac{\alpha^{2}}{l^{5\sigma/4+\kappa}\ell},$ (131)

where in the last inequality we have taken the term with the highest order.
Using the previous bounds from Lemma 2 we can show that

$\mathbb{E}\bigl{[}|\Theta_{l}-\tilde{\Theta}_{l}|^{2}\mathds{1}[\mathcal{B}_{l}]\bigr{]}\leq\alpha_{l}^{2}\mathbb{E}\bigl{[}\mathrm{dist}(\Theta_{l},\mathcal{M}\cap
U)\mathds{1}[\mathcal{B}_{l}]\bigr{]}\leq\C\frac{a^{2}}{l^{3\sigma+\kappa}},$
(132)

so that using the triangle inequality and combining the bounds of (131) and
(132) we obtain

$\mathbb{E}\bigl{[}|\Theta_{l+1}-\Theta_{l}|^{2}\mathds{1}[\mathcal{B}_{l}]\bigr{]}^{1/2}\leq\Cl{10}\alpha\Bigl{(}l^{-3/2\sigma-\kappa/2}+\sqrt{\ell}^{-1}l^{-5\sigma/8-\kappa/2}\Bigr{)}.$
(133)

Hence, since $\sigma\in(2/3,1)$ adding the bound (133) in (120) yields

$\displaystyle\mathbb{E}\Bigl{[}\max_{1\leq l\leq
m}\bigl{|}\Theta_{l}-\Theta_{0}\bigr{|}\mathds{1}[\mathcal{B}_{l-1}]\Bigr{]}$
$\displaystyle\leq\sum_{l=1}^{m}\Cr{10}\alpha(l^{-3/2\sigma-\kappa/2}+\sqrt{\ell}^{-1}l^{-\sigma-\kappa/2})$
$\displaystyle\leq\C\alpha(m^{1-3/2\sigma-\kappa/2}+\sqrt{\ell}^{-1}m^{1-5\sigma/8-\kappa/2}).$

###  C.6 Proof of Lemma 4

The proof mimicks the proof strategy of [13, Prop. 24], but modifications are
required due to our Markovian assumptions and appearances of biases.
Specifically, we must carefully consider the adverse effects that these biases
could have on the probability that the iterates exit the basin of attraction.
Concretely, our effort will go into firstly proving the following sufficiently
strong analogue of [13, (75)] that is applicable to our problem:

######  Lemma 7.

There exist constants $c_{1},c_{2}>0$ such that

$\mathbb{P}[\mathrm{dist}(\Theta_{m},\mathcal{M}\cap
U)>\delta,\mathcal{B}_{m-1}]\leq\frac{c_{1}\alpha^{2}}{\delta^{2}\ell
m^{2\sigma}}\mathbb{P}[\mathcal{B}_{m-1}]+\frac{c_{2}}{\delta^{4}\ell
m^{\sigma+\kappa}}.$ (134)

The proof of Lemma 7 can be found in Section C.6.1.

Once Lemma 7 has been established, we secondly estimate the combined
probability that any of the iterates escape in directions tangential to the
manifold. The proof of this fact, which is analogous to [13, (78)–(79)], can
be found in Section C.6.2.

######  Lemma 8.

If $\Theta_{0}\in V_{\mathfrak{r}/2,\delta}(\theta^{\star})$, then

$\sum_{l=1}^{m}\mathbb{P}[\mathrm{dist}(\Theta_{l},\mathcal{M}\cap
U)<\delta,\Theta_{l}\notin
V_{\mathfrak{r},\delta}(\theta^{\star}),\mathcal{B}_{l-1}]\leq\mathbb{P}\Bigl{[}\max_{1\leq
l\leq
m}\bigl{|}\Theta_{l}-\Theta_{0}\bigr{|}\mathds{1}[\mathcal{B}_{l-1}]>R/2-2\delta,\Bigr{]}.$
(135)

##### Proof that Lemmas 7 and 8 imply Lemma 4.

First, note that the recursion

$\mathbb{P}[\mathcal{B}_{m}]=\mathbb{P}[\Theta_{m}\in
V_{\mathfrak{r},\delta}(\theta^{\star}),\mathcal{B}_{m-1}]=\mathbb{P}[\mathcal{B}_{m-1}]-\mathbb{P}[\Theta_{m}\notin
V_{\mathfrak{r},\delta}(\theta^{\star}),\mathcal{B}_{m-1}]$ (136)

can be iterated whenever we can control and bound the following probabilities

$\displaystyle\mathbb{P}[\Theta_{m}\notin
V_{\mathfrak{r},\delta}(\theta^{\star}),\mathcal{B}_{m-1}]$
$\displaystyle=\mathbb{P}[\mathrm{dist}(\Theta_{m},\mathcal{M}\cap
U)>\delta,\mathcal{B}_{m-1}]$
$\displaystyle\phantom{=}+\mathbb{P}[\mathrm{dist}(\Theta_{m},\mathcal{M}\cap
U)\leq\delta,\Theta_{m}\notin
V_{\mathfrak{r},\delta}(\theta^{\star}),\mathcal{B}_{m-1}].$ (137)

Using Lemma 7 and induction on (136) and (137), it follows that for some
$c>0$,

$\mathbb{P}[\mathcal{B}_{m}]\geq\prod_{l=1}^{m}\Bigl{(}1-\frac{c\alpha^{2}}{\delta^{2}\ell
l^{2\sigma}}\Bigr{)}_{+}-\sum_{l=1}^{m}\frac{c}{\ell\delta^{4}l^{\sigma+\kappa}}-\sum_{l=1}^{m}\mathbb{P}[\mathrm{dist}(\Theta_{l},\mathcal{M}\cap
U)<\delta,\Theta_{l}\notin
V_{\mathfrak{r},\delta}(\theta^{\star}),\mathcal{B}_{l-1}].$ (138)

We use Lemma 8 together with Lemma 3 and Markov’s inequality to obtain the
bound

$\displaystyle\sum_{l=1}^{m}\mathbb{P}[\mathrm{dist}(\Theta_{l},\mathcal{M}\cap
U)<\delta,\Theta_{l}\notin
V_{\mathfrak{r},\delta}(\theta^{\star}),\mathcal{B}_{l-1}]\leq
c\alpha\frac{(m^{1-3/2\sigma-\kappa/2}+\ell^{-1/2}m^{1-5\sigma/8-\kappa/2})}{(\mathfrak{r}/2-2\delta)_{+}}$
(139)

Thus, substituting (139) in (138), for some $c>0$ we have

$\mathbb{P}[\mathcal{B}_{m}]\geq\prod_{l=1}^{m}\Bigl{(}1-\frac{c\alpha^{2}}{\delta^{2}\ell
l^{2\sigma}}\Bigr{)}_{+}-\sum_{l=1}^{m}\frac{c}{\ell\delta^{4}l^{\sigma+\kappa}}-c\alpha\frac{(m^{1-3/2\sigma-\kappa/2}+\ell^{-1/2}m^{1-5\sigma/8-\kappa/2})}{(\mathfrak{r}/2-2\delta)_{+}}.$
(140)

Note first that since $\sigma\in(2/3,1)$ and $\kappa\geq 0$, if
$\sigma+\kappa\neq 1$, then there exists a constant $\Cl{20}>0$ such that

$\sum_{l=1}^{m}\frac{c}{\ell\delta^{4}l^{\sigma+\kappa}}\leq\Cr{20}m^{1-\sigma-\kappa}$
(141)

Lastly, there also exists a constant $c>0$, $\alpha_{0}>0$, $\delta_{0}$ such
that if $\alpha\in(0,\alpha_{0}]$ and $\delta\in(0,\delta_{0}]$ then there
exists $\ell_{0}>0$ such that if $\ell\in[\ell_{0},\infty)$ then

$\prod_{l=1}^{m}\Bigl{(}1-\frac{c\alpha^{2}}{\delta^{2}\ell
l^{2\sigma}}\Bigr{)}_{+}\geq\exp\Bigl{(}-\frac{c\alpha^{2}}{\delta^{2}\ell}\Bigr{)}$
(142)

Lower bounding (140) using (141) and (142) yields Lemma 4. $\Box$

####  C.6.1 Proof of Lemma 7

We follow first [13, (69)], by fixing $\delta_{1}$ small enough such that
$\delta\in(0,\delta_{1}]$, on the event $\mathcal{B}_{m-1}$ it is shown in
[13] that we have the inequality

$\mathrm{dist}(\Theta_{m},\mathcal{M}\cap
U)\leq\Bigl{(}1-\frac{\lambda\alpha_{m-1}}{2}\Bigr{)}\mathrm{dist}(\Theta_{m-1},\mathcal{M}\cap
U)+\alpha_{m-1}|\eta_{m-1}|.$ (143)

We consider now the event $\\{\mathrm{dist}(\Theta_{m},\mathcal{M}\cap
U)>\delta\\}\cap\mathcal{B}_{m-1}$. This event occurs when in (143), either
$\Theta_{m-1}\in V_{\mathfrak{r},\delta/2}(\theta^{\star})$ and
$|\eta_{m-1}|\geq\alpha_{m-1}\delta/2$, or $\Theta_{m-1}\in
V_{\mathfrak{r},\delta}(\theta^{\star})\backslash
V_{\mathfrak{r},\delta/2}(\theta^{\star})$ and the gradient term can have
smaller size. Mathematically, this translates into the inequality

$\displaystyle\mathbb{P}[\mathrm{dist}(\Theta_{m},\mathcal{M}\cap
U)>\delta,\mathcal{B}_{m-1}]\leq\mathbb{P}\Bigl{[}|\eta_{m-1}|\geq\frac{\delta}{2\alpha_{m-1}},\Theta_{m-1}\in
V_{\mathfrak{r},\delta/2}(\theta^{\star}),\mathcal{B}_{m-2}\Bigr{]}$ (144)
$\displaystyle+\mathbb{P}\Bigl{[}|\eta_{m-1}|\geq\frac{\delta\lambda}{2},\Theta_{m-1}\in
V_{\mathfrak{r},\delta}(\theta^{\star})\backslash
V_{\mathfrak{r},\delta/2}(\theta^{\star}),\mathcal{B}_{m-2}\Bigr{]}=:P_{1}+P_{2}.$

Contrary to what is done in the proof of [13, Prop. 24], we cannot use an
independence property to estimate the probabilities $P_{1}$ and $P_{2}$ in
(144). After all, the Markov chain’s behavior at epoch $m-1$ depends on
$\Theta_{m-1}$.

In order to overcome this issue we will use the characterization of
$\eta_{m-1}$ in Lemma 1. Recall Lemma 1, and note that it implies

$\displaystyle\mathbb{E}\Bigl{[}\mathds{1}[\mathcal{B}_{m-1}]\mathds{1}\Bigl{[}|\eta_{m-1}|\geq\frac{\delta}{2\alpha_{m-1}}\Bigr{]}\Big{|}\mathcal{F}_{m-1}\Bigr{]}=\mathbb{P}\Bigl{[}|\eta_{m-1}|\geq\frac{\delta}{2\alpha_{m-1}},\mathcal{B}_{m-1}\big{|}\mathcal{F}_{m-1}\Bigr{]}$
$\displaystyle\leq\frac{\mathbb{E}[|\eta_{m-1}|^{2}\mathds{1}[\mathcal{B}_{m-1}]\
|\mathcal{F}_{m-1}]}{\frac{\delta^{2}}{4(\alpha_{m-1})^{2}}}\leq\frac{4\Cl{11}(\alpha_{m-1})^{2}\mathcal{L}_{4}(S_{t_{m-1}})}{\delta^{2}T_{m}}$
(145)

since there exist a constant $c>0$ such that $T_{m}<cT_{m-1}$.

##### Bounding $P_{1}$ in (144).

We can write

$\displaystyle P_{1}$
$\displaystyle\overset{\textnormal{(i)}}{=}\mathbb{E}\Bigl{[}\mathds{1}\bigl{[}|\eta_{m-1}|\geq\frac{\delta}{2\alpha_{m-1}}\bigr{]}\mathds{1}[\Theta_{m-1}\in
V_{\mathfrak{r},\delta/2}(\theta^{\star})]\mathds{1}[\mathcal{B}_{m-2}]\mathds{1}[\mathcal{B}_{m-1}]\Bigr{]}$
$\displaystyle=\mathbb{E}\Bigl{[}\mathds{1}[\Theta_{m-1}\in
V_{\mathfrak{r},\delta/2}(\theta^{\star})]\mathds{1}[\mathcal{B}_{m-2}]\mathbb{E}\bigl{[}\mathds{1}[\mathcal{B}_{m-1}]\mathds{1}[|\eta_{m-1}|\geq\frac{\delta}{2\alpha_{m-1}}]|\mathcal{F}_{m-1}\bigr{]}\Bigr{]}$
$\displaystyle\overset{\textnormal{(\ref{eqn:proof_lemma7_1})}}{\leq}\frac{4\Cr{11}(\alpha_{m-1})^{2}}{T_{m}\delta^{2}}\mathbb{E}\Bigl{[}\mathds{1}[\Theta_{m-1}\in
V_{\mathfrak{r},\delta/2}(\theta^{\star})]\mathds{1}[\mathcal{B}_{m-2}]\mathcal{L}_{4}(S_{t_{m-1}})\Bigr{]}$
(146)

where for (i) we have used the fact that $\\{\Theta_{m-1}\in
V_{\mathfrak{r},\delta/2}(\theta^{\star})\\}\cap\mathcal{B}_{m-2}\subset\mathcal{B}_{m-1}$.

We deal now with the remaining term in (146). Differently to the independent
and unbiased case we need to control the bias and use the tail probability
that the Lyapunov function is larger than a certain bound in order to estimate
the deviation probability. This step is the crucial different step compared to
[13], where we have to explicitly use Assumption 4 and 6. Note that a
Cauchy–Schwartz inequality in (146) will not yields an inequality strong
enough. See the remark after the proof for further details.

Before bounding the remaining term in (146), we obtain the necessary
inequalities. Recall from Lemma 6 that since
${\mathbb{E}}[\mathcal{L}_{4}(S_{t_{m-1}})^{4}\mathds{1}[\mathcal{B}_{m-2}]]<{\mathbb{E}}[\mathcal{L}_{v}(S_{t_{m-1}})\mathds{1}[\mathcal{B}_{m-2}]]<D<\infty$,
then by Markov’s inequality we have that there exists $D>0$ such that for any
$m>0$,

$\mathbb{P}[\mathcal{L}(S_{t_{m-1}})>m^{s},\mathcal{B}_{m-2}]\leq
D^{4}m^{-4s}.$ (147)

Note also that under the moment assumptions the following holds

$\displaystyle\mathbb{E}\Bigl{[}\mathcal{L}(S_{t_{m-1}})\mathds{1}[\mathcal{B}_{m-2}]\mathds{1}[\mathcal{L}(S_{t_{m-1}})>m^{s}]\Bigr{]}$
$\displaystyle=\int_{m^{s}}^{\infty}\mathbb{P}[\mathcal{L}(S_{t_{m-1}})>t,\mathcal{B}_{m-2}]\operatorname{d}\\!{t}$
$\displaystyle=\int_{m^{s}}^{\infty}\frac{D^{4}}{t^{4}}\operatorname{d}\\!{t}\leq
D^{4}m^{-3s+1}.$ (148)

We use the (148) to bound (146) as follows

$\displaystyle\mathbb{E}\Bigl{[}\mathds{1}[\Theta_{m-1}\in
V_{\mathfrak{r},\delta/2}(\theta^{\star})]\mathcal{L}_{4}(S_{t_{m-1}})\mathds{1}[\mathcal{B}_{m-2}]\Bigr{]}$
$\displaystyle\leq\mathbb{E}\Bigl{[}\mathds{1}[\Theta_{m-1}\in
V_{\mathfrak{r},\delta/2}(\theta^{\star})]\mathcal{L}_{4}(S_{t_{m-1}})\mathds{1}[\mathcal{B}_{m-2}]\Bigl{(}\mathds{1}[\mathcal{L}_{4}(S_{t_{m-1}})>m^{s}]+\mathds{1}[\mathcal{L}_{4}(S_{t_{m-1}})\leq
m^{s}]\Bigr{)}\Bigr{]}$
$\displaystyle\leq\mathbb{E}\Bigl{[}\mathds{1}[\Theta_{m-1}\in
V_{\mathfrak{r},\delta/2}(\theta^{\star})]m^{s}\mathds{1}[\mathcal{B}_{m-2}]\Bigr{]}+\mathbb{E}\Bigl{[}\mathcal{L}(S_{t_{m-1}})\mathds{1}[\mathcal{B}_{m-2}]\mathds{1}[\mathcal{L}(S_{t_{m-1}})>m^{s}]\Bigr{]}$
$\displaystyle\overset{\textnormal{(\ref{eqn:intereq3})}}{\leq}m^{s}\mathbb{P}[\Theta_{m-1}\in
V_{\mathfrak{r},\delta/2}(\theta^{\star}),\mathcal{B}_{m-2}]+\Cl{12}Dm^{-3s+1}\leq
m^{s}\mathbb{P}[\mathcal{B}_{m-1}]+\Cr{12}Dm^{-3s+1}.$ (149)

Thus, using (149), we can bound $P_{1}$ in (144). Specifically,

$P_{1}\leq\frac{4\C(\alpha_{m-1})^{2}}{T_{m}\delta^{2}}(m^{s}\mathbb{P}[\mathcal{B}_{m-1}]+m^{-3s+1}).$
(150)

This completes our bound for $P_{1}$.

##### Bounding $P_{2}$ in (144).

Repeating the argumentation behind (150), we can show that

$\displaystyle
P_{2}\leq\frac{4\C}{T_{m}\lambda^{2}\delta^{2}}\Bigl{(}m^{s}\mathbb{P}\bigl{[}\Theta_{m-1}\in
V_{\mathfrak{r},\delta}(\theta^{\star})\backslash
V_{\mathfrak{r},\delta/2}(\theta^{\star}),\mathcal{B}_{m-2}\bigr{]}+m^{-3s+1}\Bigr{)}.$
(151)

Using the facts (i) $\\{\Theta_{m-1}\in
V_{\mathfrak{r},\delta}(\theta^{\star})\backslash
V_{\mathfrak{r},\delta/2}(\theta^{\star})\\}\subseteq\\{\mathrm{dist}(\Theta_{m-1},\mathcal{M}\cap
U)\geq\delta/2\\}$, with (ii) an application of Lemma 2 and Markov’s
inequality, reveals that

$\mathbb{P}[\Theta_{m-1}\in V_{\mathfrak{r},\delta}(\theta^{\star})\backslash
V_{\mathfrak{r},\delta/2}(\theta^{\star}),\mathcal{B}_{m-2}]\overset{\textnormal{(i)}}{\leq}\mathbb{P}\Bigl{[}\mathrm{dist}(\Theta_{m-1},\mathcal{M}\cap
U)\geq\frac{\delta}{2},\mathcal{B}_{m-2}\Bigr{]}\overset{\textnormal{(ii)}}{\leq}\frac{4}{\delta^{2}}\C
m^{-\sigma-\kappa}.$ (152)

Applying the bound in (151) to (152) yields

$P_{2}\leq\frac{4\C}{T_{m}\lambda^{2}\delta^{4}}\Bigl{(}m^{s}m^{-\sigma-\kappa}+m^{-3s+1}\Bigr{)}.$
(153)

This completes the bound for $P_{2}$ in (144).

##### A return to (144), and parameter selection.

Let us now combine (149) and (153) and return to bounding the left-hand side
of (144). Specifically, observe that we proved that

$\displaystyle\mathbb{P}[\mathrm{dist}(\Theta_{m},\mathcal{M}\cap
U)>\delta,\mathcal{B}_{m-1}]$
$\displaystyle\leq\frac{4\C(\alpha_{m-1})^{2}}{T_{m}\delta^{2}}\bigl{(}m^{s}\mathbb{P}[\mathcal{B}_{m-1}]+m^{-3s+1}\bigr{)}$
$\displaystyle\phantom{\leq}+\frac{4\C}{T_{m}\delta^{4}}\bigl{(}m^{s-\sigma-\kappa}+m^{-3s+1}\bigr{)}.$
(154)

We now specify $s=\kappa+\sigma/2$ in (154). Without loss of generality we
will again assume that $T_{m}=\ell m^{\sigma/2+\kappa}$ instead of
$\lfloor\ell m^{\sigma/2+\kappa}\rfloor$—there is namely only a constant
changed. By choosing the smallest exponents in $m$ in (154) for all $m>0$ we
have

$\displaystyle\mathbb{P}[\mathrm{dist}(\Theta_{m},\mathcal{M}\cap
U)>\delta,\mathcal{B}_{m-1}]$
$\displaystyle\leq\Cl{15}\frac{a^{2}}{\delta^{2}\ell
m^{2\sigma}}\mathbb{P}[\mathcal{B}_{m-1}]+\frac{\Cr{15}}{\delta^{4}\ell}\bigl{(}m^{-3\sigma-4\kappa+1}+m^{-\sigma-\kappa}\bigr{)}.$
(155)

Since $\sigma\in(2/3,1)$, then $-3\sigma-4\kappa+1<-\sigma-\kappa$ for any
$\kappa\geq 0$. Upper bounding the leading orders in $m$ completes the proof
of Lemma 7. $\Box$

######  Remark.

A Cauchy–Schwartz inequality in (146) would only yield a factor
$\mathbb{P}[\mathcal{B}_{m-1}]^{1/2}>\mathbb{P}[\mathcal{B}_{m-1}]$, which
would not be sufficient. Similarly, we could have used Lemma 6 directly and
obtain a bound on
$\mathbb{E}[\mathds{1}[\mathcal{B}_{m-2}]\mathcal{L}_{4}(S_{t_{m-1}})]$.
However, this would not give an inequality that can be iterated inductively
and is sharp enough. We can directly simplify this term to obtain
$\mathbb{P}(\mathcal{B}_{m-1})$ in the inequality only when
$\mathcal{L}_{4}(S_{t_{m-1}})$ is bounded.

####  C.6.2 Proof of Lemma 8

In [13], it is [13, Lem. 23] that establishes [13, (78)–(79)] directly. Since
[13, Lem. 23] is solely a geometric argument, and does not concern the
stochastic process, it also applies in our Markovian setting. $\Box$

##  Appendix D The compact case

In the case that the set of maxima $\mathcal{M}$ is compact, we can improve
the convergence rate of Theorem 2. We will namely assume the following

######  Assumption 8 (Compactness, Optional).

The open subset $U$ defined in Assumption 7 is such that $\mathcal{M}\cap U$
is compact.

Under the additional Assumption 8, in Section D.1 we show the following

######  Theorem 3 (Compact case).

Suppose that Assumptions 1 to 8 hold, except that (16) is now relaxed to allow
for $\sigma\in(0,1)$ and $\kappa\in[0,\infty)$. For every maximizer
$\theta^{\star}\in\mathcal{M}$, there exist constants $c>0$ and $\alpha_{0}>0$
such that, for every $\alpha\in(0,\alpha_{0}]$, there exists a neighborhood
$V$ of $\theta^{\star}$ such that there exists $\ell_{0}>0$ such that for any
$\ell\in[\ell_{0},\infty)$, $m\in\mathbb{N}_{+}$, and $\epsilon\in(0,1)$,

$\displaystyle\mathbb{P}\mathopen{}\mathclose{{}\left[J(\Theta_{m})<J^{\star}-\epsilon|\Theta_{0}\in
V}\right]$ $\displaystyle\leq
c\mathopen{}\mathclose{{}\left(\epsilon^{-2}m^{-\sigma-\kappa}+\frac{m^{1-\sigma-\kappa}}{\ell}+\frac{\alpha^{2}}{\ell}}\right).$
(156)

The term proportional to $\alpha m^{-\kappa/2}+\alpha
m^{1-\sigma/2-\kappa/2}\ell^{-\frac{1}{2}}$ is not in Theorem 3 compared to
Theorem 2. This term estimates the probability that the iterates escape $V$
along directions almost parallel to those of $\mathcal{M}$. As it turns out,
in the compact case such event cannot occur. The bound in (156) thus holds
when the set of maxima is, for example, a singleton $\mathcal{M}\cap
U=\\{x_{0}\\}$.

With the additional assumption that the reward $r$ is bounded, we immediately
obtain a typical sample complexity bound by optimizing a bound over
$\epsilon$.

######  Corollary 1 (Sample Complexity, Compact case).

Under the same assumptions and setting as in Theorem 3, assume moreover that
there exists some $b>0$ such that $|r(s,a)|<b$ for any
$(s,a)\in\mathcal{S}\times\mathcal{A}$. Then we have

$\displaystyle{\mathbb{E}}[J^{\star}-J(\Theta_{m})|\Theta_{0}\in V]$
$\displaystyle\leq
3\Bigl{(}\frac{cb}{2}\Bigr{)}^{\frac{1}{3}}m^{-\frac{(\sigma+\kappa)}{3}}+2bc\frac{m^{1-(\sigma+\kappa)}+\alpha^{2}}{\ell}.$

###### Proof.

Optimizing the following bound over $\epsilon>0$,

${\mathbb{E}}[J^{\star}-J(\Theta_{m})|\Theta_{0}\in
V]\leq\mathbb{P}\mathopen{}\mathclose{{}\left[J(\Theta_{m})<J^{\star}-\epsilon|\Theta_{0}\in
V}\right]2b+\epsilon,$ (157)

immediately yields the result by using the bound in (156). ∎

###  D.1 Proof of Theorem 3

The proof is the same as with Theorem 2, but we can omit the last term in (62)
by showing that we can choose $\mathfrak{r}$ arbitrarily large. The argument
is as follows. If the manifold $\mathcal{M}\cap U$ is compact, it can be
covered by a finite number $k$ of local tubular neighborhoods
$V_{i}=V_{\mathfrak{r}_{i},\delta_{i}}(\theta_{i})$ where
$\theta_{i}\in\mathcal{M}\cap U$ and $\mathcal{M}\cap
U\subset\cup_{i\in[k]}V_{i}$. Choose $\delta=\min_{i\in[k]}\delta_{i}$. Then,
any $\theta\in U$ such that $\mathrm{dist}(\theta,\mathcal{M}\cap U)<\delta$
will satisfy that $\mathfrak{p}(\theta)\in\mathcal{M}\cap U$, where
$\mathfrak{p}$ is the unique local orthogonal projection on $\mathcal{M}\cap
U$ from (27). Now, from compactness, for any $\theta^{\star}\in\mathcal{M}\cap
U$ there exists $\tilde{\mathfrak{r}}>0$ such that $\mathcal{M}\cap U\subset
B_{\tilde{\mathfrak{r}}}(\theta^{\star})$. For any
$\mathfrak{r}\geq\tilde{\mathfrak{r}}$ we thus have that
$V_{\mathfrak{r},\delta}(\theta^{\star})=V_{\tilde{\mathfrak{r}},\delta}(\theta^{\star})$
is a tubular neighborhood containing $\mathcal{M}\cap U$. Then, we can choose
$\mathfrak{r}$ arbitrarily large and conclude that the last term in the bound
for the probability in Theorem 2 vanishes if $\mathcal{M}\cap U$ is a compact
manifold. More details on tubular neighborhoods and their existence for
embedded manifolds can be found in [20].

##  Appendix E Proof of Proposition 1

We consider the following setting. Let $D<1$. We consider
$\theta\in\mathbb{R}$ and a function $f$ such that in
$\mathbb{R}\backslash[-D,D]$ satisfies $f(\theta)=0$ and in $[-D/2,D/2]$
satisfies

$f(\theta)=1-\theta^{2}.$ (158)

In $[-D,-D/2]\cup[D/2,D]$, we define $f$ such that it is smoothly and
monotonically interpolated between $[-D/2,D/2]$ and
$\mathbb{R}\backslash[-D,D]$.

We let $H_{m}$ be such that $H_{m}=0$ in $\mathbb{R}\backslash[-D,D]$. Hence,
the set $\mathbb{R}\backslash[-D,D]$ is an absorbing set that is 1-suboptimal.
In $[-D/2,D/2]$, we will consider $\eta_{m}=\nabla f(\Theta_{m})-H_{m}$ to be
a random variable that, conditional on $\mathcal{F}_{m}$, is unbiased and has
a second moment for all $m$ but is heavy tailed. In particular, for $\beta>0$,
we define $\eta_{m}$ such that there exists $c>0$ such that for any $m$, we
have

$\mathbb{P}[|\eta_{m}|>s|\mathcal{F}_{m}]\geq\frac{c}{s^{2+\beta}T_{m}}\quad\text{for}\quad
s>D.$ (159)

Note that this constraint on $\eta_{m}$ is compatible with the finite second
moment condition from (22). If moreover $\alpha\leq 1$ and
$\sqrt{\epsilon}<2D$, under the previous conditions we can bound

$\displaystyle\mathbb{P}\mathopen{}\mathclose{{}\left[f(\Theta_{m})<f^{\star}-\epsilon|\Theta_{0}\in
V}\right]$
$\displaystyle\overset{\textnormal{(i)}}{\geq}\mathbb{P}\mathopen{}\mathclose{{}\left[f(\Theta_{m})<f^{\star}-\epsilon|\Theta_{0}=\theta^{\min}}\right]$
$\displaystyle=\mathbb{P}\mathopen{}\mathclose{{}\left[|\Theta_{m}|>\sqrt{\epsilon}|\Theta_{0}=\theta^{\min}}\right]$
$\displaystyle\overset{\textnormal{(ii)}}{\geq}\mathbb{P}\mathopen{}\mathclose{{}\left[\sup_{l\leq
m}|\Theta_{l}|>2D|\Theta_{0}=\theta^{\min}}\right]$
$\displaystyle\geq\mathbb{P}\mathopen{}\mathclose{{}\left[|\Theta_{1}|>2D|\Theta_{0}=\theta^{\min}}\right]$
$\displaystyle=\mathbb{P}\mathopen{}\mathclose{{}\left[|\theta^{\min}+\alpha_{1}\eta_{1}|>2D|\Theta_{0}=\theta_{0}}\right]$
$\displaystyle\overset{\textnormal{(iii)}}{\geq}\mathbb{P}\mathopen{}\mathclose{{}\left[\alpha_{1}|\eta_{1}|>D|\Theta_{0}}\right]$
$\displaystyle\overset{\textnormal{(\ref{eqn:Proof_lower_bound_1})}}{\geq}c\frac{\alpha_{1}^{2+\beta}}{D^{2+\beta}T_{1}}$
$\displaystyle\geq c\frac{\alpha^{2+\beta}}{D^{2+\beta}\ell},$ (160)

where (i) we have used that for any $V=[-\delta,\delta]$ with $\delta<D$,

$\displaystyle\mathbb{P}\mathopen{}\mathclose{{}\left[f(\Theta_{m})<f^{\star}-\epsilon|\Theta_{0}\in
V}\right]$ $\displaystyle=\int_{\theta\in
V}\mathbb{P}\mathopen{}\mathclose{{}\left[f(\Theta_{m})<f^{\star}-\epsilon|\Theta_{0}=\theta}\right]d\mathbb{P}\mathopen{}\mathclose{{}\left[\Theta_{0}=\theta|\Theta_{0}\in
V}\right]$ $\displaystyle\geq\min_{\theta\in
V}\mathbb{P}\mathopen{}\mathclose{{}\left[f(\Theta_{m})<f^{\star}-\epsilon|\Theta_{0}=\theta}\right]$
$\displaystyle\geq\mathbb{P}\mathopen{}\mathclose{{}\left[f(\Theta_{m})<f^{\star}-\epsilon|\Theta_{0}=\theta^{\min}}\right]$
(161)

for some $\theta^{\min}\in V$. In (ii), we have used the fact that from the
definition of $f$, we have the inclusion of events $\\{\sup_{l\leq
m}|\Theta_{l}|>2D\\}\in\\{|\Theta_{m}|>2D\\}$, since the set
$\mathbb{R}\backslash[-D,D]$ is absorbent for the process
$\\{\Theta_{t}\\}_{t\geq 0}$. In (iii), we have used that $\theta^{\min}$
belongs at least to $[-D,D]$, since otherwise it cannot be the minimum as
defined in (161). To guarantee that $\epsilon\in(0,1)$ we may choose $D=1/2$,
for example.

##  Appendix F Proof of Proposition 2

To prove the proposition we will show that for almost all $\tilde{\pi}$ in the
Lebesgue measure of the class of policies defined in (5), the function
$J_{\tilde{\pi}}(\theta)$ is Morse. Morse functions are smooth functions $f$
such that every critical point of $f$ is nondegenerate, that is, for any $x$
such that $\nabla_{x}f=0$ we have that $\mathrm{Hess}_{x}f$ is nonsingular.
Hence, all critical points are isolated. If the function
$J_{\tilde{\pi}}(\theta)$ is Morse and furthermore satisfies that
$J_{\tilde{\pi}}(\theta)\to-\infty$ as $|\theta|\to\infty$, it will then have
bounded isolated maxima.

We show first that for almost all $\tilde{\pi}$, the function
$J_{\tilde{\pi}}(\theta)$ is a Morse function. To do so, we will implicitly
use the fact that Morse functions are dense and form an open subset in the
space of smooth functions [25].

We introduce first notation. For a finite dimensional smooth manifold $M$, we
denote by $T_{x}M$ and $T^{*}_{x}M$ the tangent and cotangent spaces at $x\in
M$, respectively. When $M=\mathbb{R}^{u}$, for $f:\mathbb{R}^{u}\to\mathbb{R}$
we will denote the (covariant) derivative and gradient of $f$ at $x$ by
$d_{x}f\in T^{*}_{x}M$ and $\nabla_{x}f\in T_{x}M$, respectively. In local
coordinates $(w_{1},\ldots,w_{u})$, we have namely

$\displaystyle d_{x}f$ $\displaystyle=\sum_{i=1}^{u}\frac{\partial
f(x)}{\partial w_{i}}dw_{i}$ $\displaystyle\nabla_{x}f$
$\displaystyle=\sum_{i=1}^{u}\frac{\partial f(x)}{\partial
w_{i}}\frac{d}{dw_{i}},$ (162)

where $dw_{i}(\frac{d}{dw_{i}})=\mathds{1}[i=j]$. In this notation and since
$M=\mathbb{R}^{u}$, we have then

$d_{x}(df)=\sum_{i=1}^{u}d_{x}\Bigl{(}\frac{\partial f(x)}{\partial
w_{i}}dw_{i}\Bigr{)}=\sum_{i=1}^{u}\sum_{j=1}^{u}\frac{\partial^{2}f(x)}{\partial
w_{j}\partial w_{i}}dw_{j}\otimes dw_{i}=\mathrm{Hess}_{x}f\in
T^{*}_{x}M\otimes T^{*}_{x}M.$ (163)

We require the following lemmas and definitions.

######  Definition 1.

Let $M$ and $N$ be two manifolds and let $B$ be a submanifold of $N$. We say a
smooth map $f:M\to N$ is transversal to $B$ if for every point $x\in M$ such
that $f(x)\in B$ we have

$d_{x}f(T_{x}M)+T_{f(x)}B=T_{f(x)}N.$ (164)

We will use the following result that has is its core an application of Sard’s
theorem that states that in a map between smooth manifolds, the set of
critical points has measure zero in the image.

######  Lemma 9 (Parametric transversality theorem [16]).

Let $Z,M$ and $N$ be smooth manifolds and let $B$ be a smooth submanifold of
$N$. Let $F:Z\times M\to N$ be a smooth submersion, that is, the differential
map is surjective everywhere. If $F$ is transversal to $B$, then for almost
every $z\in Z$, the map

$F_{z}(m)=F(z,m)$ (165)

is transversal to $B$.

When appropriate, we will make explicit the dependence of $v\in T^{*}_{x}M$ on
$x$ by writing $(x,v)\in T^{*}_{x}M$. We can now show the following,

######  Lemma 10.

Let $M=\mathbb{R}^{u}$ and let $f:M\to\mathbb{R}$ be a smooth map. Consider
the map $\tilde{f}:M\to T^{*}M$ given for $x\in M$ by

$\tilde{f}(x)=(x,d_{x}f)\in T^{*}_{x}M.$ (166)

Let $B\subset T^{*}M$ be the zero section submanifold, that is, $B(x)=(x,0)\in
T^{*}_{x}M$ for every $x$. Then $x$ is a nondegenerate critical point of $f$
if and only if $\tilde{f}$ is transversal to $B$ at $x$ and $\nabla_{x}f=0$.

###### Proof.

$x$ is a critical nondegenerate point if and only if $\nabla_{x}f=0$ and
$\mathrm{Hess}_{x}f\in T^{*}_{x}M\otimes T^{*}_{x}M$ is nonsingular. For any
$\nu\in T_{x}M$, we have then that

$d_{x}\tilde{f}(\nu)=(\nu,\mathrm{Hess}_{x}f(\nu))$ (167)

By definition, $\tilde{f}$ is transversal to $B$ if and only if for every
$x\in M$,

$\displaystyle d_{x}\tilde{f}(T_{x}M)+T_{x}M\oplus 0$
$\displaystyle=(Id\oplus\mathrm{Hess}_{x}(f))(T_{x}M)+T_{x}M\oplus 0$
$\displaystyle=T_{x}M\oplus\mathrm{Hess}_{x}f(T_{x}M)$
$\displaystyle=T_{x}M\oplus T^{*}_{x}M,$ (168)

which is true if and only if $\mathrm{Hess}_{x}f$ is nonsingular. ∎

From the last two lemmas it follows that by adding an appropriate perturbation
to a function, the perturbed function is nondegenerate. This result is well-
known in the literature in the context of genericity of Morse functions and
can be generalized to general smooth manifolds; see [16].

######  Lemma 11.

Let $M=\mathbb{R}^{u}$. Let $f:M\to\mathbb{R}$ and $g_{i}:M\to\mathbb{R}$ for
$i\in[l]$ be smooth functions such that for every $x\in M$,
$\mathrm{span}(\\{d_{x}g_{i}\\}_{i=1}^{l})=T^{*}_{x}M$. Then for almost every
$z=(z_{1},\ldots,z_{l})\in\mathbb{R}^{u}$ we have that

$f_{z}(\cdot)=f(\cdot)+\sum_{i=1}^{l}z_{i}g_{i}(\cdot)$ (169)

is a Morse function.

###### Proof.

Define the smooth function $F:\mathbb{R}^{l}\times M\to T^{*}M$ given by

$F(z,x)=(x,d_{x}f+\sum_{i=1}^{l}z_{i}d_{x}g_{i})=(x,d_{x}f_{z}).$ (170)

The derivative of this map at $(z,x)$ evaluated at $(\eta,\chi)\in
T_{z}\mathbb{R}^{l}\times T_{x}M$ is then

$d_{(z,x)}F(\eta,\chi)=(\chi,\mathrm{Hess}_{x}f_{z}(\chi)+\sum_{i=1}^{l}\eta_{i}d_{x}g_{i})\in
T_{F(z,x)}(T^{*}M)\simeq T_{x}M\oplus T^{*}_{x}M.$ (171)

For every $x$, we have $\mathrm{span}(\\{d_{x}g_{i}\\}_{i=1}^{l})=T^{*}_{x}M$,
then $d_{(z,x)}F(T_{z}\mathbb{R}^{l},T_{x}M)=T_{F(z,x)}(T^{*}M)$ and
$d_{(z,x)}F$ is surjective. Thus, $F$ is a submersion and is therefore
transversal to the zero section of $T^{*}M$ and by Lemma 9 for almost every
$z\in Z$ the map $F_{z}(x)=F(z,x)$ is transversal to the zero section of
$T^{*}M$. Finally, by Lemma 10 we can conclude that for almost every $z\in Z$,
the critical points of $f_{z}$ are nondegenerate, that is, $f_{z}$ is a Morse
function. ∎

We are now in position to show the proposition. Recall from the definition of
the policy in (5) that there is an index set $\mathcal{I}$ and a function
$h:\mathcal{S}\to\mathcal{I}$ that determines the parameter dependence of
$\\{\theta_{i,a}:(i,a)\in\mathcal{I}\times\mathcal{A}\\}$. For
$s\in\mathcal{I}$, let $z_{(a,i)}=\tilde{\pi}(a|i)$ and denote
$\tilde{\zeta}(i)=\sum_{s\in\mathcal{S}:h(s)=i}\zeta(s)$. We can write

$\displaystyle d_{\theta}\mathcal{R}_{\tilde{\pi}}(\theta)$
$\displaystyle=b\sum_{s\in\mathcal{S}}\zeta(s)\sum_{a\in\mathcal{A}}\tilde{\pi}(a|s)d_{\theta}\log(\pi(a|s,\theta))$
$\displaystyle=b\sum_{s\in\mathcal{S}}\zeta(s)\sum_{a\in\mathcal{A}}\tilde{\pi}(a|s)\Bigl{(}\sum_{a^{\prime}\in\mathcal{A}}(\mathds{1}[a=a^{\prime}]-\pi(a^{\prime}|s,\theta))d\theta_{h(s),a^{\prime}}\Bigl{)}$
$\displaystyle=b\sum_{s\in\mathcal{S}}\zeta(s)\sum_{a^{\prime}\in\mathcal{A}}(\tilde{\pi}(a|s)-\pi(a^{\prime}|s,\theta))d\theta_{h(s),a^{\prime}}$
$\displaystyle=b\sum_{i\in\mathcal{I}}\sum_{a\in\mathcal{A}}\tilde{\zeta}(i)(\tilde{\pi}(a|i)-\pi(a|i,\theta))d\theta_{i,a}$
$\displaystyle=b\sum_{(i,a)\in\mathcal{I}\times\mathcal{A}}\tilde{\zeta}(i)(z_{(i,a)}-\pi(a|i,\theta))d\theta_{i,a}$
(172)

If $\tilde{\zeta}(i)>0$ for all $i\in\mathcal{I}$, it is clear from (172) that
the terms $\\{d\theta_{i,a}\\}_{(i,a)\in\mathcal{I}\times\mathcal{A}}$ span
$T^{*}_{\theta}\mathbb{R}^{|\mathcal{A}|\times|\mathcal{I}|}$ for each
$\theta$, since $\pi(a|s,\theta)\neq 0$ for any finite $\theta$. By Lemma 11
and the assumption on $\zeta$, we immediately obtain that for almost all
policies $\tilde{\pi}$, the function

$J_{\tilde{\pi}}(\theta)=J(\theta)-b\mathcal{R}_{\bar{\pi}}(\theta).$ (173)

is Morse and has nondegenerate critical points—including the maximum. Finally,
the set of maxima of (173) will be nonempty. Indeed, the function
$-b\mathcal{R}_{\bar{\pi}}(\theta)\to-\infty$ whenever for any
$s\in\mathcal{S}$, $\pi(\,\cdot\,|s)\to\partial\Delta(\mathcal{S})$. Thus, by
continuity, the set of maxima belongs to a compact set.