$M \cap U$ is a compact manifold. More details on tubular neighborhoods and their existence for embedded manifolds can be found in the work of Lee (2013).

## Appendix E. Proof of Proposition 4

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

$$f(\theta) = 1 - \theta^2. \qquad (179)$$

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}\setminus[-D, D]$.

We let $H_m$ be such that $H_m = 0$ in $\mathbb{R}\setminus[-D, D]$. Hence, the set $\mathbb{R}\setminus[-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 approximates a heavy tailed random variable. 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] \ge \frac{c}{s^{2+\beta}T_m} \quad \text{for } s > D. \qquad (180)$$

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

$$
\begin{align*}
\mathbb{P}[f(\Theta_m) < f^* - \epsilon | \Theta_0 \in V] &\overset{(i)}{\ge} \mathbb{P}[f(\Theta_m) < f^* - \epsilon | \Theta_0 = \theta^{\min}] \\
&= \mathbb{P}[|\Theta_m| > \sqrt{\epsilon}|\Theta_0 = \theta^{\min}] \\
&\overset{(ii)}{\ge} \mathbb{P}\left[\sup_{l \le m} |\Theta_l| > 2D|\Theta_0 = \theta^{\min}\right] \\
&\overset{(iii)}{\ge} \mathbb{P}[|\Theta_1| > 2D|\Theta_0 = \theta^{\min}] \\
&= \mathbb{P}[|\theta^{\min} + \alpha_1\eta_1| > 2D|\Theta_0 = \theta_0] \\
&\overset{(180)}{\ge} c \frac{\alpha_1^{2+\beta}}{D^{2+\beta}T_1} \\
&\overset{(181)}{\ge} c \frac{\alpha^{2+\beta}}{D^{2+\beta}\ell},
\end{align*}
$$

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

$$
\begin{align}
\mathbb{P}[f(\Theta_m) < f^* - \epsilon | \Theta_0 \in V] &= \int_{\theta \in V} \mathbb{P}[f(\Theta_m) < f^* - \epsilon | \Theta_0 = \theta] d\mathbb{P}[\Theta_0 = \theta | \Theta_0 \in V] \nonumber \\
&\ge \min_{\theta \in V} \mathbb{P}[f(\Theta_m) < f^* - \epsilon | \Theta_0 = \theta] \nonumber \\
&\ge \mathbb{P}[f(\Theta_m) < f^* - \epsilon | \Theta_0 = \theta^{\min}] \tag{182}
\end{align}
$$

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 \le m} |\Theta_l| > 2D\} \in \{|\Theta_m| > 2D\}$, since the set $\mathbb{R}\setminus[-D, D]$ is
absorbent for the process {$\Theta_t$}$_{t\ge0}$. In (iii), we have used that $\theta^{\min}$ belongs at least to $[-D, D]$, since otherwise it cannot be the minimum as defined in (182). To guarantee that $\epsilon \in (0,1)$ we may choose $D = 1/2$, for example.

## Appendix F. Proof of Proposition 5

We define the total number of samples $T$ up to epoch $m$ as

$$T = t_{m+1} = \sum_{k=1}^{m} \ell k^{\kappa+\sigma/2} = \ell \Theta(m^{\kappa+\frac{\sigma}{2}+1}). \quad (183)$$

and so for a given $T \ge 1$, define $m = \lceil (T/\ell)^{1/(\kappa+\frac{\sigma}{2}+1)} \rceil$. Note that according to definition in (28), we have $m(T) \le m \le m(T) + 1$.

We show first an intermediate result in Lemma 19. Recall the definition of the set $V$ in (38). Since the closure of $V$ is compact we have that $\sup_{\theta \in V} |J(\theta)|$ exists. From Theorem 2 we directly obtain:

**Lemma 19** Under the same assumptions and setting as in Theorem 2, assume either (i) there exists some $b > 0$ such that $|r(s,a)| < b$ for any $(s,a) \in S \times A$ or (ii) the event $B_m = \{\Theta_t \in V : t \in [m]\}$ holds. Under condition (i) we have that

$$\mathbb{E}[J^* - J(\Theta_m) | \Theta_0 \in V] \le 3(\mathcal{L}^*)^{\frac{1}{3}} \left(\frac{cb}{2}\right)^{\frac{1}{3}} m^{-\frac{(\sigma+\kappa)}{3}} + 2\frac{bc}{\ell} m^{1-(\sigma+\kappa)} + 2bc\frac{\alpha^2}{\ell} \\ + 2bc\alpha m^{-\kappa/2} + 2\frac{bc\alpha}{\ell} m^{1-(\sigma+\kappa)/2}.$$

Under condition (ii), we have that if $b = \sup_{\theta \in V} |J(\theta)|$ and $\mathbb{P}[B_m] > 1/2$, then

$$\mathbb{E}[J^* - J(\Theta_m) | \mathcal{B}_m] \le 3(\mathcal{L}^*)^{\frac{1}{3}}(cb)^{\frac{1}{3}}m^{-\frac{(\sigma+\kappa)}{3}}. \quad (184)$$

**Proof** Under condition (i), optimizing the following bound over $\epsilon > 0$,

$$\mathbb{E}[J^* - J(\Theta_m) | \Theta_0 \in V] \le \mathbb{P}[J(\Theta_m) < J^* - \epsilon | \Theta_0 \in V] 2b + \epsilon, \quad (185)$$

immediately yields the result by using the bound from (23). For condition (ii), using (82), we have directly that

$$\begin{aligned} \frac{1}{2} \mathbb{P}[\{J^* - J(\Theta_m) > \epsilon\} | \mathcal{B}_m] &\le \mathbb{P}[\{J^* - J(\Theta_m) > \epsilon\} | \mathcal{B}_m] \mathbb{P}[\mathcal{B}_m] \\ &= \mathbb{P}[\{J^* - J(\Theta_m) > \epsilon\} \cap \mathcal{B}_m] \\ &\le c\epsilon^{-2} \mathcal{L}^* m^{-(\sigma+\kappa)}. \end{aligned} \quad (186)$$

Finally, we repeat the same argument as in part (i) using the new bound $b$. ■
## F.1 Proof of Proposition 5(i)

Recall that both $V$ and $\alpha$ are fixed. Let $\tilde{\Theta}_t$ for $t \in [T]$ be defined as in Section 5.4. Then using Lemma 19 and the definition of $m$ in terms of $T$ in (183), we have that there exists a constant $c > 0$ independent of $\ell \ge \ell_0$ such that for any $T$ we have

$$ \mathbb{E}[J^* - J(\Theta_{m(T)}) | \Theta_0 \in V] \le c \left( \left(\frac{T}{\ell}\right)^{-\frac{(\sigma+\kappa)}{3(\kappa+\frac{\sigma}{2}+1)}} + \frac{1}{\ell^{1/2}} \left(\frac{T}{\ell}\right)^{\frac{1-(\sigma+\kappa)}{2(\kappa+\frac{\sigma}{2}+1)}} \right. \\ \left. + \frac{1}{\ell} \left(\frac{T}{\ell}\right)^{\frac{1-\sigma+\kappa}{2(\kappa+\frac{\sigma}{2}+1)}} + T^{\frac{-\kappa}{2(\kappa+\frac{\sigma}{2}+1)}} + \frac{\alpha^2}{\ell} \right). \quad (187) $$

Note that by looking at the orders in (187) we can make $\kappa$ large to obtain an approximation for the exponents. In particular, for any $\zeta > 0$ there exists $\kappa_0(\zeta) > 0$ such that if $\kappa \ge \kappa_0(\epsilon)$, then

$$ \mathbb{E}[J^* - J(\Theta_{m(T)}) | \Theta_0 \in V] \le c \left( (\mathcal{L}^*)^{\frac{1}{3}} \ell^{\frac{1}{3}} + \zeta T^{-\frac{1}{3}} + \zeta + \ell^{1/2} + \zeta T^{-\frac{1}{2}} + \zeta + \ell^{2/3} + \zeta T^{-1} + \zeta + \frac{\alpha^2}{\ell} \right). \quad (188) $$

## F.2 Proof of Proposition 5(ii)

Repeating the same argument as in (i) we obtain that

$$ \mathbb{E}[J^* - J(\Theta_{m(T)}) | \mathcal{B}_{m(T)}] \le c(\mathcal{L}^*)^{\frac{1}{3}} \ell^{\frac{1}{3}} + \zeta T^{-\frac{1}{3}} + \zeta. \quad (189) $$

The bound on the probability $\mathbb{P}[\mathcal{B}_{m(T)}]$ is given in (84) together with the remark on the exponents thereafter. In terms of $T/\ell$, this observation yields

$$ \mathbb{P}[\mathcal{B}_{m(T)}] \ge 1 - c \left( \frac{\alpha^2}{\ell} + \ell^{1/2+\zeta} T^{-\frac{1}{2}+\zeta} + \ell^{2/3+\zeta} T^{-1+\zeta} \right). \quad (190) $$

Finally, we make $\ell_0$ large enough to guarantee that if $T \ge T_0$ for some $T_0 > 0$, we have $\mathbb{P}[\mathcal{B}_{m(T)}] \ge 1/2$. Then note that $\mathbb{P}[\mathcal{B}_{m(k)}] \ge \mathbb{P}[\mathcal{B}_{m(T_0)}]$ for any $k \le T_0$.

## Appendix G. Proof of Corollary 6

We will use the same notation as in the proof of Proposition 5 in Appendix F. Moreover, for an epoch $l$ corresponding samples $t \in [t_l, t_{l+1}]$, we will consider that $\Theta_l$ is fixed for any sample in the epoch and define the parameter corresponding to sample $t$ as $\tilde{\Theta}_t = \Theta_{m(l)}$, where $m(l)$ was defined in (28). We need first the following inequalities.

**Lemma 20** Under the same assumptions and notation as in Theorem 2, we fix $\alpha$ and $\delta$ satisfying such assumptions. Then for any $1 > \zeta > 0$ there exists $\kappa(\zeta) \ge 0$, $c > 0$ and $\ell_0 > 0$ such that for any $\ell \ge \ell_0$, $\kappa \ge \kappa(\zeta)$ and $T \ge 1$, (i) if $r(s, a)$ is bounded,

$$ \mathbb{E}[T J^* - \sum_{t=1}^{T} r(S_t, A_t) | \Theta_0 \in V] \le \mathbb{E}[T J^* - \sum_{t=1}^{T} J(\tilde{\Theta}_t) | \Theta_0 \in V] \\ + c(\alpha^2 T \ell^{-1} + \ell^{1/2+\zeta} T^{\frac{1}{2}+\zeta} + \ell^{2/3+\zeta} T^{\zeta} + T^{\zeta}), $$
and (ii) if $r(s, a)$ is unbounded,

$$ \mathbb{E}[TJ^* - \sum_{t=1}^{T} r(S_t, A_t) | \mathcal{B}_{m(T)}] \le \mathbb{E}[TJ^* - \sum_{t=1}^{T} J(\tilde{\Theta}_t) | \mathcal{B}_{m(T)}] + c \left(\frac{T}{\ell}\right)^{\frac{1}{\sigma/2+\kappa}}. $$

**Proof** We show (ii) first. We use that

$$ \mathbb{E}[TJ^* - \sum_{t=1}^{T} r(S_t, A_t) | \mathcal{B}_{m(T)}] = \mathbb{E}[TJ^* - \sum_{t=1}^{T} J(\tilde{\Theta}_t) | \mathcal{B}_{m(T)}] + \mathbb{E}[\sum_{t=1}^{T} J(\tilde{\Theta}_t) - r(S_t, A_t) | \mathcal{B}_{m(T)}]. \quad (191) $$

From the same argument as that of (190), we may pick $\ell_0$ such that $\mathbb{P}[\mathcal{B}_{m(T)}] > 1/2$ and for some $c > 0$

$$ \left| \mathbb{E} \left[ \sum_{t=1}^{T} J(\tilde{\Theta}_t) - r(S_t, A_t) \middle| \mathcal{B}_{m(T)} \right] \right| \le c \left| \mathbb{E} \left[ \mathbb{1}[\mathcal{B}_{m(T)}] \sum_{t=1}^{T} J(\tilde{\Theta}_t) - r(S_t, A_t) \middle| \Theta_0 \in V \right] \right|. \quad (192) $$

We need to bound only the last term in (192). From Assumption 6, we have that $|r(s, a)| \le c\mathcal{L}(s, a)$. From (71) we obtain for epoch $m$ that if $\Theta_m \in V$ there exists a constant $C > 0$ such that

$$ \left| \mathbb{E} \left[ \sum_{t=t_m}^{t_{m+1}} J(\tilde{\Theta}_t) - r(S_t, A_t) \middle| \mathcal{F}_m \right] \right| \le C \mathcal{L}_4(S_{t_m}, A_{t_m}). \quad (193) $$

Recall from (28) that $m(T) = \min\{m \in \mathbb{N}: \ell m^{\sigma/2+\kappa} \ge T\}$. From Lemma 14, we know that there exists a constant $c > 0$ such that for any $n \ge 1$ $\mathbb{E}[\mathcal{L}_4(S_{t_n}, A_{t_n})\mathbb{1}[\mathcal{B}_n]] \le c$. Let $\mathcal{F}_n$ be defined as in (41). Recall that $\mathbb{1}[\mathcal{B}_m] \le \mathbb{1}[\mathcal{B}_n]$ if $n < m$. By using in the following the tower property of the conditional expectation in (i) we have

$$ \begin{aligned} & \left| \mathbb{E} \left[ \mathbb{1}[\mathcal{B}_{m(T)}] \sum_{t=1}^{T} J(\tilde{\Theta}_t) - r(S_t, A_t) \middle| \Theta_0 \in V \right] \right| \\ & \le \sum_{n=1}^{m(T)} \left| \mathbb{E} \left[ \mathbb{1}[\mathcal{B}_n] \sum_{t=t_n}^{t_{n+1}} J(\tilde{\Theta}_t) - r(S_t, A_t) \middle| \Theta_0 \in V \right] \right| \\ & \stackrel{(i)}{\le} \sum_{n=1}^{m(T)} \mathbb{E} \left[ \left| \mathbb{E} \left[ \mathbb{1}[\mathcal{B}_n] \sum_{t=t_n}^{t_{n+1}} J(\tilde{\Theta}_t) - r(S_t, A_t) \middle| \mathcal{F}_n \right] \right| \middle| \Theta_0 \in V \right] \\ & \stackrel{(193)}{\le} c \sum_{n=1}^{m(T)} \mathbb{E} \left[ \mathbb{1}[\mathcal{B}_n] \mathcal{L}_4(S_{t_n}, A_{t_n}) \middle| \Theta_0 \in V \right] \\ & \stackrel{(\text{Lemma 14})}{\le} c \sum_{m=1}^{m(T)} C \le c \left(\frac{T}{\ell}\right)^{\frac{1}{\sigma/2+\kappa}}. \end{aligned} \quad (194) $$

Substituting (194) in (192) yields the result. We now show (i) using a similar argument. First note that for $n \in [m(T)]$ we have

$$ \left| \mathbb{E} \left[ \sum_{t=t_n}^{t_{n+1}} J(\tilde{\Theta}_t) - r(S_t, A_t) \middle| \Theta_0 \in V \right] \right| $$
$$
\begin{align}
&\leq \left| \mathbb{E} \left[ \mathbb{1}[\mathcal{B}_n] \sum_{t=t_n}^{t_{n+1}} J(\tilde{\Theta}_t) - r(S_t, A_t) \middle| \Theta_0 \in V \right] \right| + \left| \mathbb{E} \left[ \mathbb{1}[\overline{\mathcal{B}}_n] \sum_{t=t_n}^{t_{n+1}} J(\tilde{\Theta}_t) - r(S_t, A_t) \middle| \Theta_0 \in V \right] \right| \nonumber \\
&\stackrel{(a)}{\leq} C + c \mathbb{P}[\overline{\mathcal{B}}_n] \tag{195} \\
&\leq C + c \ell n^{\sigma/2+\kappa} \left( \frac{\alpha^2}{\ell} + \frac{n^{1-(\sigma+\kappa)}}{\ell} + n^{-\kappa/2} + \frac{n^{1-(\sigma+\kappa)/2}}{\ell} \right), \nonumber
\end{align}
$$

where in (a) we have used the same argument as in (194) for the first term, and for the second term, we have used that since the reward is bounded, $|J(\tilde{\Theta}_t) - r(S_t, A_t)|$ is also bounded, regardless of the stability of $\tilde{\Theta}_t$. We are left with a constant times $\mathbb{P}[\overline{\mathcal{B}}_n]$ for the second term. We add the remaining terms in (195) for $n \in [m(T)]$ and use the inequality $\sum_{i=1}^h i^\eta \le Ch^{\eta+1}$ for $\eta \ge 0$. Setting $m(T)$ in terms of $T$ according to (183), we are left with

$$
\begin{align}
& \left| \mathbb{E} \left[ \sum_{t=t_n}^{t_{n+1}} J(\tilde{\Theta}_t) - r(S_t, A_t) \middle| \Theta_0 \in V \right] \right| \nonumber \\
& \le c \left( \left( T^{\frac{1}{\sigma/2+\kappa}} \ell^{-\frac{1}{\sigma/2+\kappa}} + T \frac{\alpha^2}{\ell} + \ell^{1/2+\zeta} T^{\frac{1}{2}+\zeta} + \ell^{2/3+\zeta} T^{\zeta} + T^{\zeta} \right) \right. \nonumber \\
& \qquad \left. \le c \left( \alpha^2 T \ell^{-1} + \ell^{1/2+\zeta} T^{\frac{1}{2}+\zeta} + \ell^{2/3+\zeta} T^{\zeta} + T^{\zeta} \right), \right) \tag{196}
\end{align}
$$

where we have used that $T^{-1/(\sigma/2+\kappa)}\ell^{-1/(\sigma/2+\kappa)} \le T/\ell$ for any $T \ge \ell$. ■

<figure><img src="image_10.png" /></figure>

G.1 Proof of Corollary 6(i)

Let $\ell \ge \ell_0$ be fixed, where $\ell_0$ is given by the conditions of Theorem 2. We add for each $t \in [T]$ the performance gap of Proposition 5 which yields

$$
\begin{align}
& \mathbb{E} \left[ T J^* - \sum_{t=1}^{T} J(\tilde{\Theta}_t) \middle| \Theta_0 \in V \right] \nonumber \\
& \le \sum_{t=1}^{T} c \left( \left( \mathcal{L}^* \right)^{\frac{1}{3}} \ell^{\frac{1}{3}+\zeta} t^{-\frac{1}{3}+\zeta} + \alpha^2 \ell^{-1} + \ell^{1/2+\zeta} t^{-\frac{1}{2}+\zeta} + \ell^{2/3+\zeta} t^{-1+\zeta} + t^{-1+\zeta} \right) \right. \nonumber \\
& \le c \left( \left( \mathcal{L}^* \right)^{\frac{1}{3}} \ell^{\frac{1}{3}+\zeta} T^{\frac{2}{3}+\zeta} + \alpha^2 \ell^{-1} + \ell^{1/2+\zeta} T^{\frac{1}{2}+\zeta} + \ell^{2/3+\zeta} T^{\zeta} + T^{\zeta} \right). \tag{197}
\end{align}
$$

Use now Lemma 20 together with (197). In this manner we obtain the bound:

$$
\begin{align*}
& \mathbb{E} \left[ T J^* - \sum_{t=1}^{T} r(S_t, A_t) \middle| \Theta_0 \in V \right] \\
& \le c \left( (\mathcal{L}^*)^{\frac{1}{3}} \ell^{\frac{1}{3}+\zeta} T^{\frac{2}{3}+\zeta} + \alpha^2 T \ell^{-1} + \ell^{1/2+\zeta} T^{\frac{1}{2}+\zeta} + \ell^{2/3+\zeta} T^{\zeta} + T^{\zeta} \right).
\end{align*}
$$

Then, for $\ell \ge \ell_0$ fixed and for any $T > 0$ the following holds

$$
\mathbb{E} \left[ T J^* - \sum_{t=1}^{T} r(S_t, A_t) \middle| \Theta_0 \in V \right] \le c \left( (\mathcal{L}^*)^{\frac{1}{3}} T^{\frac{2}{3}+\zeta} + \frac{\alpha^2}{\ell} T \right). \quad (198)
$$
Similarly, if we choose $\ell$ depending on a given $T$ fixed, then setting $\ell = T^{1/4}$ we obtain

$$ \mathbb{E}[T J^* - \sum_{t=1}^{T} r(S_t, A_t) | \Theta_0 \in V] \le c T^{\frac{3}{4}+\zeta}. \quad (199) $$

## G.2 Proof of Corollary 6(ii)

Let $\ell \ge \ell_0$ be fixed, where $\ell_0$ is given by the conditions of Theorem 2 and satisfies the same conditions as (190). We repeat the argument used in (i) by using Proposition 5 and Lemma 20. We obtain that if $\sigma/2 + \kappa \ge 3/2$ then

$$ \mathbb{E}[T J^* - \sum_{t=1}^{T} r(S_t, A_t) | \mathcal{B}_{m(T)}] \le c(\mathcal{L}^*)^{\frac{1}{3}} \ell^{\frac{1}{3}+\zeta} T^{\frac{2}{3}+\zeta} + c \left(\frac{T}{\ell}\right)^{\frac{1}{\sigma/2+\kappa}} \le c(\mathcal{L}^*)^{\frac{1}{3}} T^{\frac{2}{3}+\zeta}. \quad (200) $$

## Appendix H. Proof of Proposition 7

To prove the proposition we will show that for almost all $\tilde{\pi}$ in the Lebesgue measure of the class of policies defined in (6), 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 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 (see Nicolaescu 2011).

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, \dots, w_u)$, we have namely

$$ \begin{aligned} d_x f &= \sum_{i=1}^{u} \frac{\partial f(x)}{\partial w_i} dw_i, \\ \nabla_x f &= \sum_{i=1}^{u} \frac{\partial f(x)}{\partial w_i} \frac{d}{dw_i}, \end{aligned} \quad (201) $$

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

$$ d_x(df) = \sum_{i=1}^{u} d_x \left( \frac{\partial f(x)}{\partial w_i} dw_i \right) = \sum_{i=1}^{u} \sum_{j=1}^{u} \frac{\partial^2 f(x)}{\partial w_j \partial w_i} dw_j \otimes dw_i = \text{Hess}_x f \in T_x^* M \otimes T_x^* M. \quad (202) $$

We require the following lemmas and definitions.

**Definition 21** 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. \quad (203) $$
We will use the following result that has 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 22 (Parametric Transversality Theorem (Guillemin and Pollack, 2010))**

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) \qquad (204)$$

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 23** 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. \qquad (205)$$

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 $\text{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, \text{Hess}_x f(\nu)). \qquad (206)$$

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

$$\begin{aligned}
d_x \tilde{f}(T_x M) + T_x M \oplus 0 &= (\text{Id} \oplus \text{Hess}_x(f))(T_x M) + T_x M \oplus 0 \\
&= T_x M \oplus \text{Hess}_x f(T_x M) \\
&= T_x M \oplus T_x^* M,
\end{aligned} \qquad (207)$$

which is true if and only if $\text{Hess}_x f$ is nonsingular.

<figure><img src="image_11.png" /></figure>

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 (Guillemin and Pollack, 2010).

**Lemma 24** 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$, $\text{span}(\{d_x g_i\}_{i=1}^l) = T_x^*M$. Then for almost every $z = (z_1, \dots, z_l) \in \mathbb{R}^u$ we have that

$$f_z(\cdot) = f(\cdot) + \sum_{i=1}^{l} z_i g_i(\cdot) \qquad (208)$$

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). \qquad (209)$$

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, \text{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. \qquad (210)$$

For every $x$, we have $\text{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 22 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 23 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 (6) that there is an index set $\mathcal{I}$ and a function $h: 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 S: h(s)=i} \zeta(s)$. We can write

$$
\begin{align*}
d_{\theta} \mathcal{R}_{\tilde{\pi}}(\theta) &= b \sum_{s \in S} \zeta(s) \sum_{a \in \mathcal{A}} \tilde{\pi}(a|s) d_{\theta} \log(\pi(a|s, \theta)) \\
&= b \sum_{s \in S} \zeta(s) \sum_{a \in \mathcal{A}} \tilde{\pi}(a|s) \left( \sum_{a' \in \mathcal{A}} (\mathbb{1}[a=a'] - \pi(a'|s, \theta)) d_{\theta} h_{(s),a'} \right) \\
&= b \sum_{s \in S} \zeta(s) \sum_{a' \in \mathcal{A}} (\tilde{\pi}(a|s) - \pi(a'|s, \theta)) d_{\theta} h_{(s),a'} \\
&= b \sum_{i \in \mathcal{I}} \sum_{a \in \mathcal{A}} \tilde{\zeta}(i) (\tilde{\pi}(a|i) - \pi(a|i, \theta)) d_{\theta} h_{(i,a)} \\
&= b \sum_{(i,a) \in \mathcal{I} \times \mathcal{A}} \tilde{\zeta}(i) (z_{(i,a)} - \pi(a|i, \theta)) d_{\theta} h_{(i,a)}. \tag{211}
\end{align*}
$$

If $\tilde{\zeta}(i) > 0$ for all $i \in \mathcal{I}$, it is clear from (211) 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 24 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}_{\tilde{\pi}}(\theta). \qquad (212)$$

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

Yasin Abbasi-Yadkori, Peter Bartlett, Kush Bhatia, Nevena Lazic, Csaba Szepesvari, and Gellért Weisz. Politex: Regret bounds for policy iteration using expert prediction. In *International Conference on Machine Learning (ICML)*, pages 3692–3702. PMLR, 2019.

Ivo Adan, Ana Bušić, Jean Mairesse, and Gideon Weiss. Reversibility and further properties of FCFS infinite bipartite matching. *Mathematics of Operations Research*, 43(2):598–621, December 2017. Publisher: INFORMS.

Alekh Agarwal, Sham M. Kakade, Jason D. Lee, and Gaurav Mahajan. On the theory of policy gradient methods: Optimality, approximation, and distribution shift. *The Journal of Machine Learning Research*, 22(1):4431–4506, 2021.

Jonatha Anselmi, Bruno Gaujal, and Louis-Sébastien Rebuffi. Learning optimal admission control in partially observable queueing networks. *Queueing Systems*, 108(1):31–79, October 2024.

Yves F. Atchadé, Gersende Fort, and Eric Moulines. On perturbed proximal gradient algorithms. *The Journal of Machine Learning Research*, 18(1):310–342, 2017.

Forest Baskett, K. Mani Chandy, Richard R. Muntz, and Fernando G. Palacios. Open, closed, and mixed networks of queues with different classes of customers. *Journal of the ACM*, 22(2):248–260, April 1975.

Lilian Besson and Emilie Kaufmann. What doubling tricks can and can't do for multi-armed bandits. *arXiv preprint arXiv:1803.06971*, 2018.

Thomas Bonald and Jorma Virtamo. Calculating the flow level performance of balanced fairness in tree networks. *Performance Evaluation*, 58(1):1–14, October 2004.

Pierre Brémaud. *Markov Chains: Gibbs Fields, Monte Carlo Simulation, and Queues*. Texts in Applied Mathematics. Springer-Verlag, 1999.

Jeffrey P. Buzen. Computational algorithms for closed queueing networks with exponential servers. *Communications of the ACM*, 16(9):527–531, September 1973.

Shicong Cen, Chen Cheng, Yuxin Chen, Yuting Wei, and Yuejie Chi. Fast global convergence of natural policy gradient methods with entropy regularization. *Operations Research*, 70 (4):2563–2578, 2022.

Hadi Daneshmand, Jonas Kohler, Aurelien Lucchi, and Thomas Hofmann. Escaping saddles with stochastic gradients. In *International Conference on Machine Learning (ICML)*, pages 1155–1164. PMLR, 2018.

Edmundo de Souza e Silva and Mario Gerla. Queueing network models for load balancing in distributed systems. *Journal of Parallel and Distributed Computing*, 12(1):24–38, May 1991.
Edmundo de Souza e Silva and Richard R. Muntz. Simple relationships among moments of queue lengths in product form queueing networks. *IEEE Transactions on Computers*, 37 (9):1125-1129, September 1988.

Thinh T. Doan, Lam M. Nguyen, Nhan H. Pham, and Justin Romberg. Finite-time analysis of stochastic gradient descent under Markov randomness. *arXiv preprint arXiv:2003.10973*, 2020.

Maryam Fazel, Rong Ge, Sham Kakade, and Mehran Mesbahi. Global convergence of policy gradient methods for the linear quadratic regulator. In *International Conference on Machine Learning (ICML)*, pages 1467–1476. PMLR, 2018.

Benjamin Fehrman, Benjamin Gess, and Arnulf Jentzen. Convergence rates for the stochastic gradient descent method for non-convex objective functions. *The Journal of Machine Learning Research*, 21:136, 2020.

Gersende Fort and Eric Moulines. Convergence of the Monte Carlo expectation maximization for curved exponential families. *The Annals of Statistics*, 31(4):1220–1259, 2003.

Kristen Gardner and Rhonda Righter. Product forms for FCFS queueing models with arbitrary server-job compatibilities: an overview. *Queueing Systems*, 96(1):3–51, October 2020.

Victor Guillemin and Alan Pollack. *Differential topology*, volume 370. American Mathematical Society, 2010.

Libin Jiang and Jean Walrand. A distributed CSMA algorithm for throughput and utility maximization in wireless networks. *IEEE/ACM Transactions on Networking*, 18(3):960–972, 2009.

Belhal Karimi, Blazej Miasojedow, Eric Moulines, and Hoi-To Wai. Non-asymptotic analysis of biased stochastic approximation scheme. In *Conference on Learning Theory (COLT)*, pages 1944–1974. PMLR, 2019.

Shauharda Khadka and Kagan Tumer. Evolution-guided policy gradient in reinforcement learning. In *Advances in Neural Information Processing Systems (NeurIPS)*, volume 31. Curran Associates, Inc., 2018.

Daphne Koller and Nir Friedman. *Probabilistic Graphical Models: Principles and Techniques*. The MIT Press, Cambridge, MA, 2009.

Navdeep Kumar, Yashaswini Murthy, Itai Shufaro, Kfir Y. Levy, R. Srikant, and Shie Mannor. On the global convergence of policy gradient in average reward Markov decision processes. *arXiv preprint arXiv:2403.06806*, 2024.

John M. Lee. *Introduction to Smooth Manifolds*, volume 218. Springer Science & Business Media, 2013.

David A. Levin and Yuval Peres. *Markov Chains and Mixing Times*. American Mathematical Society, 2nd edition, 2017.
Bai Liu, Qiaomin Xie, and Eytan Modiano. RL-QN: A reinforcement learning framework for optimal control of queueing systems. *ACM Transactions on Modeling and Performance Evaluation of Computing Systems*, 7(1):1-35, 2022.

Yanli Liu, Kaiqing Zhang, Tamer Basar, and Wotao Yin. An improved analysis of (variance-reduced) policy gradient and natural policy gradient methods. In *Advances in Neural Information Processing Systems (NeurIPS)*, volume 33, pages 7624-7636. Curran Associates, Inc., 2020.

Zhen Liu and Philippe Nain. Sensitivity results in open, closed and mixed product form queueing networks. *Performance Evaluation*, 13(4):237-251, 1991.

Shakir Mohamed, Mihaela Rosca, Michael Figurnov, and Andriy Mnih. Monte Carlo gradient estimation in machine learning. *The Journal of Machine Learning Research*, 21(1):5183-5244, 2020.

Pascal Moyal, Ana Bušić, and Jean Mairesse. A product form for the general stochastic matching model. *Journal of Applied Probability*, 58(2):449-468, June 2021. Publisher: Cambridge University Press.

Yashaswini Murthy, Isaac Grosof, Siva Theja Maguluri, and R. Srikant. Performance of NPG in countable state-space average-cost RL. *arXiv preprint arXiv:2405.20467*, 2024.

Liviu I. Nicolaescu. *An invitation to Morse theory*. Springer, 2011.

Yichen Qian, Jun Wu, Rui Wang, Fusheng Zhu, and Wei Zhang. Survey on reinforcement learning applications in communication networks. *Journal of Communications and Information Networks*, 4(2):30-39, 2019.

Jaron Sanders, Sem C. Borst, and Johan S. H. van Leeuwaarden. Online network optimization using product-form Markov processes. *IEEE Transactions on Automatic Control*, 61(7):1838-1853, 2016.

Richard Serfozo. *Introduction to Stochastic Networks*. Stochastic Modelling and Applied Probability. Springer-Verlag, 1999.

Devavrat Shah. Message-passing in stochastic processing networks. *Surveys in Operations Research and Management Science*, 16(2):83-104, July 2011.

Virag Shah and Gustavo de Veciana. High-performance centralized content delivery infrastructure: Models and asymptotics. *IEEE/ACM Transactions on Networking*, 23(5):1674-1687, October 2015.

Richard S. Sutton and Andrew G. Barto. *Reinforcement Learning: An Introduction*. MIT press, Cambridge, MA, USA, 2nd edition, 2018.

Vladislav B. Tadic and Arnaud Doucet. Asymptotic bias of stochastic gradient search. *Annals of Applied Probability*, 27(6):3255-3304, 2017.

Martin J. Wainwright and Michael I. Jordan. Graphical models, exponential families, and variational inference. *Foundations and Trends in Machine Learning*, 1(1):1-305, 2018.
Ronald W. Wolff. Poisson arrivals see time averages. *Operations Research*, 30(2):223-231, April 1982. Publisher: INFORMS.

Lin Xiao. On the convergence rates of policy gradient methods. *The Journal of Machine Learning Research*, 23(1):12887-12922, 2022.

Rui Yuan, Robert M. Gower, and Alessandro Lazaric. A general sample complexity analysis of vanilla policy gradient. In *International Conference on Artificial Intelligence and Statistics (AISTATS)*, pages 3332-3380. PMLR, 2022.

Stan Zachary and Ilze Ziedins. Loss networks and Markov random fields. *Journal of Applied Probability*, 36(2):403-414, June 1999. Publisher: Cambridge University Press.