&\geq \left(\sum\limits_{m'\neq m^*}\Delta_{m'} \right) \frac{\Delta^2\left(\sum\limits_{m\neq m^*}\pi_{t_s}(m)\right)^2}{\left(\sum\limits_{m'\neq m^*}\Delta_{m'} \right)^2}\\
&= \frac{\Delta^2\left(1-\pi_{t_s}(m^*)\right)^2}{\left(\sum\limits_{m'\neq m^*}\Delta_{m'} \right)}.
\end{align*}

Hence we get,

\[p(s) - \expect{p(s+1)\given H(t_s)} \leq  -\alpha \frac{\Delta^2\left(1-p(s)\right)^2}{\left(\sum\limits_{m'\neq m^*}\Delta_{m'} \right)} \implies \expect{p(s+1)\given H(t_s)}\geq p(s) +  \alpha \frac{\Delta^2\left(1-p(s)\right)^2}{\left(\sum\limits_{m'\neq m^*}\Delta_{m'} \right)}. \]

This implies immediately that $\{p(s)\}_{s\geq 1}$ is a submartingale.

Since, $\{p(s)\}$ is non-negative and bounded by 1, by Martingale Convergence Theorem, $\lim_{s\to \infty} p(s)$ exists. We will now show that the limit is 1.  Clearly, it is sufficient to show that $\limsup\limits_{s\to \infty} p(s)=1$. For $a>2$, let

\[\phi_a:= \min\left\{s\geq 1: p(s)\geq \frac{a-1}{a} \right\}.  \]

As is shown in [Denisov & Walton, 2020], it is sufficient to show $\phi_a<\infty$, with probability 1, because then one can define a sequence of stopping times for increasing $a$, each finite w.p. 1. which implies that $p(s)\to 1$. By the previous display, we have

\[\expect{p(s+1)\given H(t_s)}- p(s) \geq  \alpha \frac{\Delta^2}{\left(\sum\limits_{m'\neq m^*}\Delta_{m'} \right)a^2} \]

as long as $p(s)\leq \frac{a-1}{a}$. Hence by applying Optional Stopping Theorem and rearranging we get,

\[\expect{\phi_a}\leq \lim_{s\to \infty} \expect{\phi_a \land s} \leq \frac{\left(\sum\limits_{m'\neq m^*}\Delta_{m'} \right)a^2}{\alpha \Delta}(1-\expect{p(1)}) <\infty. \]

Since $\phi_a$ is a non-negative random variable with finite expectation, $\phi_a<\infty a.s.$
Let $q(s)=1-p(s)$. We have :

\[\expect{q(s+1)} -\expect{q(s)} \leq -\alpha \frac{\Delta^2\left(q(s)\right)^2}{\left(\sum\limits_{m'\neq m^*}\Delta_{m'} \right)}. \]

By the useful result <ref>, we get,

\[\expect{q(s)} \leq \frac{\expect{q(1)}}{1+ \alpha\frac{\Delta^2\expect{q(1)}}{\left(\sum\limits_{m'\neq m^*}\Delta_{m'} \right)}s } \leq  \frac{1}{1+ \alpha\frac{\Delta^2}{\left(\sum\limits_{m'\neq m^*}\Delta_{m'} \right)} s}.\]

This completes the proof of the lemma.

Finally we provide a lemma to tie the results above. We refer (Appendix A.5 [Denisov & Walton, 2020]) for the proof of this lemma.

\[\sum\limits_{t\geq 1}\prob{\pi_t(m^*)<1/2} <\infty. \]

Also, with probability 1, $\pi_t(m^*)\to 1$, as $t\to \infty$.

Proof of regret bound:
Since $\kr^*-\kr(m)\leq 1$, we have by the definition of regret (see eq <ref>)

\[\cR(T) = \expect{\frac{1}{1-\gamma}\sum\limits_{t=1}^T\left(\sm \pi^*(m)\kr_m - \pi_t(m)\kr_m \right)}.\]

Here we recall that $\pi^*=e_{m^*}$, we have:

\begin{align*}
\cR(T) &= \frac{1}{1-\gamma}\expect{\sum\limits_{t=1}^T\left(\sm (\pi^*(m)\kr_m - \pi_t(m)\kr_m) \right)}\\
&=\frac{1}{1-\gamma}\expect{\sum\limits_{m=1}^M\left(\sum\limits_{t=1}^T (\pi^*(m)\kr_m - \pi_t(m)\kr_m) \right)}\\
&=\frac{1}{1-\gamma}\expect{\sum\limits_{t=1}^T\left(\kr^* -\sm \pi_t(m)\kr_m \right)}\\
&=\frac{1}{1-\gamma}\expect{\left(\sum\limits_{t=1}^T\kr^* -\sum\limits_{t=1}^T\sm \pi_t(m)\kr_m \right)}\\
&=\frac{1}{1-\gamma}\expect{\left(\sum\limits_{t=1}^T\kr^*(1-\pi_t(m^*)) -\sum\limits_{t=1}^T\sum\limits_{m\neq m^*} \pi_t(m)\kr_m \right)}\\
&=\frac{1}{1-\gamma}\expect{\left(\sum\limits_{t=1}^T\sum\limits_{m\neq m^*}\kr^*\pi_t(m) -\sum\limits_{t=1}^T\sum\limits_{m\neq m^*} \pi_t(m)\kr_m \right)}\\
&= \frac{1}{1-\gamma} \sum\limits_{m\neq m^*} (\kr^*-\kr_m)\expect{\sum\limits_{t=1}^T \pi_t(m)}.
\end{align*}

Hence we have,

\begin{align*}
\cR(T) &= \frac{1}{1-\gamma} \sum\limits_{m\neq m^*} (\kr^*-\kr_m)\expect{\sum\limits_{t=1}^T \pi_t(m)}\\
&\leq \frac{1}{1-\gamma} \sum\limits_{m\neq m^*}\expect{\sum\limits_{t=1}^T \pi_t(m)}\\
&=\frac{1}{1-\gamma} \expect{\sum\limits_{t=1}^T (1-\pi_t(m^*))}\\
\end{align*}

We analyze the following  term:

\[\expect{\sum\limits_{t=1}^T  (1-\pi_t(m^*))} =\expect{\sum\limits_{t=1}^T  (1-\pi_t(m^*))\ind\{\pi_t(m^*)\geq 1/2 \}}+\expect{\sum\limits_{t=1}^T  (1-\pi_t(m^*))\ind\{\pi_t(m^*)<1/2 \}} \]

\[=\expect{\sum\limits_{t=1}^T  (1-\pi_t(m^*))\ind\{\pi_t(m^*)\geq 1/2 \}} +C_1.  \]

where, $C_1:=\sum\limits_{t=1}^\infty \prob{\pi_t(m^*)<1/2}<\infty$ by Lemma <ref>. Next we observe that,

\[\expect{\sum\limits_{t=1}^T  (1-\pi_t(m^*))\ind\{\pi_t(m^*)\geq 1/2 \}} = \expect{\sum\limits_{s=1}^T  q(s)\ind\{\pi_t(m^*)\geq 1/2 \}} \leq \expect{\sum\limits_{s=1}^T  q(s)} \]

\[= \sum\limits_{t=1}^T \frac{1}{1+ \alpha\frac{\Delta^2}{\left(\sum\limits_{m'\neq m^*}\Delta_{m'} \right)} s} \leq \sum\limits_{t=1}^T \frac{{\left(\sum\limits_{m'\neq m^*}\Delta_{m'} \right)}}{ \alpha{\Delta^2} s} \]

\[ \leq \frac{{\left(\sum\limits_{m'\neq m^*}\Delta_{m'} \right)}}{ \alpha{\Delta^2} }\log T. \]

Putting things together, we get,

\begin{align*}
\cR(T) &\leq \frac{1}{1-\gamma} \left( \frac{{\left(\sum\limits_{m'\neq m^*}\Delta_{m'} \right)}}{ \alpha{\Delta^2} }\log T + C_1 \right)\\
&=\frac{1}{1-\gamma} \left( \frac{{\left(\sum\limits_{m'\neq m^*}\Delta_{m'} \right)}}{ \alpha{\Delta^2} }\log T \right) + C .
\end{align*}

This completes the proof of Theorem <ref>.

§ PROOFS FOR MDPS

First we recall the policy gradient theorem.

\[\frac{\partial}{\partial \theta}V^{\pi_\theta} (\mu) = \frac{1}{1-\gamma}\sum\limits_{s\in \cS} d_\mu^{\pi_\theta}(s) \sa \frac{\partial \pi_\theta(a|s)}{\partial \theta}Q^{\pi_\theta}(s,a). \]

Let $s\in \cS$ and $m\in [m]$.
Let $\Q^{\pi_\theta}(s,m)\bydef \sum\limits_{a\in \cA}K_m(s,a)Q^{\pi_\theta}(s,a) $. Also let $\A(s,m) \bydef \Q(s,m)-V(s)$.
[Gradient Simplification]lemmagradientofV
The softmax policy gradient with respect to the parameter $\theta\in \Real^M$ is $\frac{\partial}{\partial \theta_m}V^{\pi_{\theta}}(\mu) = \frac{1}{1-\gamma}\sum\limits_{s\in \cS}d_\mu^{\pi_\theta}(s) \pi_\theta(m)\tilde{A}(s,m)$,
where $\tilde{A}(s,m):=\Q(s,m)-V(s)$ and $\Q(s,m):= \sum\limits_{a\in \cA}K_m(s,a)Q^{\pi_\theta}(s,a) $, and $d_\mu^{\pi_\theta}(.)$ is the discounted state visitation measure starting with an initial distribution $\mu$ and following policy $\pi_\theta$.

The interpretation of $\tilde{A}(s,m)$ is the advantage of following controller $m$ at state $s$ and then following the policy $\pi_\theta$ for all time versus following $\pi_\theta$ always.
As mentioned in section <ref>, we proceed by proving smoothness of the $V^{\pi}$ function over the space $\Real^M$.

From the policy gradient theorem <ref>, we have:

\begin{align*}
\frac{\partial}{\partial \theta_{m'}} V^{\pi_\theta}(\mu) &= \frac{1}{1-\gamma}\sum\limits_{s\in \cS} d_\mu^{\pi_\theta}(s) \sa \frac{\partial \pi_{\theta_{m'}}(a|s)}{\partial \theta}Q^{\pi_\theta}(s,a)\\
&=\frac{1}{1-\gamma}\sum\limits_{s\in \cS} d_\mu^{\pi_\theta}(s) \sa \frac{\partial }{\partial {\theta_{m'}}}\left(\sm \pi_\theta(m)K_m(s,a)\right)Q^{\pi_\theta}(s,a)\\
&=\frac{1}{1-\gamma}\sum\limits_{s\in \cS} d_\mu^{\pi_\theta}(s) \sm \sa \left(\frac{\partial }{\partial {\theta_{m'}}} \pi_\theta(m)\right)K_m(s,a)Q(s,a)\\
&=\frac{1}{1-\gamma}\sum\limits_{s\in \cS} d_\mu^{\pi_\theta}(s) \sa \pi_{m'}\left(K_{m'}(s,a) - \sm \pi_mK_m(s,a) \right)Q(s,a)\\
&=\frac{1}{1-\gamma}\sum\limits_{s\in \cS} d_\mu^{\pi_\theta}(s)\pi_{m'} \sa \left(K_{m'}(s,a) - \sm \pi_mK_m(s,a) \right)Q(s,a)\\
&=\frac{1}{1-\gamma}\sum\limits_{s\in \cS} d_\mu^{\pi_\theta}(s)\pi_{m'} \left[\sa K_{m'}(s,a)Q(s,a) -\sa\sm \pi_mK_m(s,a)Q(s,a) \right]\\
&=\frac{1}{1-\gamma}\sum\limits_{s\in \cS} d_\mu^{\pi_\theta}(s)\pi_{m'} \left[\Q(s,m') -V(s) \right]\\
&=\frac{1}{1-\gamma}\sum\limits_{s\in \cS} d_\mu^{\pi_\theta}(s)\pi_{m'} \A^{\pi_\theta}(s,m').
\end{align*}

${V}^{\pi_{\theta}}\left(\mu\right)$ is $\frac{7\gamma^2+4\gamma+5}{2\left(1-\gamma\right)^2}$-smooth.

The proof uses ideas from [Agarwal et al., 2020] and [Mei et al., 2020]. Let $\theta_{\alpha} = \theta+\alpha u$, where $u\in \Real^M$, $\alpha\in \Real$. For any $s\in \cS$,

\begin{align*}
\allowdisplaybreaks
\sum\limits_a \abs{\frac{\partial\pi_{\theta_{\alpha}}(a| s)}{\partial \alpha}\Big|_{\alpha=0}} &= \sum\limits_a \abs{\innprod{\frac{\partial\pi_{\theta_{\alpha}}(a| s)}{\partial \theta_{\alpha}}\Big|_{\alpha=0}, \frac{\partial\theta_\alpha}{\partial\alpha}}} = \sum\limits_a \abs{\innprod{\frac{\partial\pi_{\theta_{\alpha}}(a| s)}{\partial \theta_{\alpha}}\Big|_{\alpha=0}, u}} \\
&=\sum\limits_a\abs{\sum\limits_{m''=1}^M\sum\limits_{m=1}^M\pi_{\theta_{m''}}\left(\ind_{mm''}-\pi_{\theta_m}\right)K_m(s,a)u(m'') }\\
&= \sum\limits_a\abs{\sum\limits_{m''=1}^M\pi_{\theta_{m''}}\left(K_{m''}(s,a)u(m'')-\sum\limits_{m=1}^M K_m(s,a)u(m'')\right) }\\
&\leq \sum\limits_a\sum\limits_{m''=1}^M\pi_{\theta_{m''}}K_{m''}(s,a)\abs{u(m'')} + \sum\limits_a\sum\limits_{m''=1}^M\sum\limits_{m=1}^M\pi_{\theta_{m''}}\pi_{\theta_{m}}K_{m}(s,a)\abs{u(m'')} \\
&= \sum\limits_{m''=1}^M\pi_{\theta_{m''}}\abs{u(m'')}\underbrace{\sum\limits_a K_{m''}(s,a)}_{=1} + \sum\limits_{m''=1}^M\sum\limits_{m=1}^M\pi_{\theta_{m''}}\pi_{\theta_{m}}\abs{u(m'')}\underbrace{\sum\limits_a K_{m}(s,a) }_{=1}\\
&=\sum\limits_{m''=1}^M\pi_{\theta_{m''}}\abs{u(m'')}+ \sum\limits_{m''=1}^M\sum\limits_{m=1}^M\pi_{\theta_{m''}}\pi_{\theta_{m}}\abs{u(m'')}\\
&=2\sum\limits_{m''=1}^M \pi_{\theta_{m''}}\abs{u(m'')} \leq 2\norm{u}_2.
\end{align*}

Next we bound the second derivative.

\[\sum\limits_a \abs{\frac{\partial^2 \pi_{\theta_{\alpha}}(a\given s)}{\partial\alpha^2}\given_{\alpha=0}} = \sum
\limits_a \abs{\innprod{\frac{\partial}{\partial\theta_\alpha}\frac{\partial \pi_{\theta_{\alpha}}(a\given s)}{\partial\alpha}\given_{\alpha=0},u}}=\sum
\limits_a \abs{\innprod{\frac{\partial^2 \pi_{\theta_{\alpha}}(a\given s)}{\partial\alpha^2}\given_{\alpha=0}u,u}}.\]

Let $H^{a,\theta}\bydef \frac{\partial^2 \pi_{\theta_{\alpha}}(a\given s)}{\partial \theta^2} \in \Real^{M\times M}$. We have,

\begin{align*}
\allowdisplaybreaks
H^{a,\theta}_{i,j} &= \frac{\partial}{\partial \theta_j}\left(\sum\limits_{m=1}^{M} \pi_{\theta_i}\left(\ind_{mi}-\pi_{\theta_m}\right)K_m(s,a) \right)\\
&= \frac{\partial}{\partial \theta_j}\left(\pi_{\theta_i}K_i(s,a)-\sum\limits_{m=1}^{M} \pi_{\theta_i}\pi_{\theta_m}K_m(s,a) \right)\\
&=\pi_{\theta_j}(\ind_{ij}-\pi_{\theta_i})K_i(s,a) -\sum\limits_{m=1}^M K_m(s,a) \frac{\partial \pi_{\theta_i}\pi_{\theta_m}}{\partial\theta_j}\\
&= \pi_j(\ind_{ij}-\pi_i)K_i(s,a) - \sum\limits_{m=1}^M K_m(s,a)\left(\pi_j(\ind_{ij}-\pi_i)\pi_m + \pi_i\pi_j(\ind_{mj}-\pi_m)\right)\\
&= \pi_j\left( (\ind_{ij}-\pi_i)K_i(s,a) - \sum\limits_{m=1}^M \pi_m(\ind_{ij}-\pi_i)K_m(s,a) -\sum\limits_{m=1}^M\pi_i(\ind_{mj}-\pi_m)K_m(s,a)   \right).
\end{align*}

Plugging this into the second derivative, we get,

\begin{align*}
\allowdisplaybreaks
\begin{split}
& \abs{\innprod{\frac{\partial^2}{\partial\theta^2}\pi_\theta(a|s)u,u}}\\
&= \abs{\sum\limits_{j=1}^M\sum\limits_{i=1}^MH_{i,j}^{a,\theta}u_iu_j}\\
&=\abs{\sum\limits_{j=1}^M\sum\limits_{i=1}^M  \pi_j\left( (\ind_{ij}-\pi_i)K_i(s,a) - \sum\limits_{m=1}^M \pi_m(\ind_{ij}-\pi_i)K_m(s,a) -\sum\limits_{m=1}^M\pi_i(\ind_{mj}-\pi_m)K_m(s,a)   \right)u_iu_j  }\\
&=\Bigg|\sum\limits_{i=1}^M \pi_iK_i(s,a)u_i^2 - \si\sj\pi_i\pi_jK_i(s,a)u_iu_j - \si\sm\pi_i\pi_mK_m(s,a)u_i^2\\ &\qquad +\si\sj\sm \pi_i\pi_j\pi_m K_m(s,a)u_iu_j - \si\sj\pi_i\pi_j K_j(s,a)u_iu_j  \\
&\qquad+\si\sj\sm \pi_i\pi_j\pi_m K_m(s,a)u_iu_j \Bigg|\\
&= \Bigg| \si\pi_iK_i(s,a) u_i^2 -2\si\sj\pi_i\pi_jK_i(s,a)u_iu_j\\
&\qquad - \si\sm\pi_i\pi_mK_m(s,a) u_i^2 + 2\si\sj\sm\pi_i\pi_j\pi_mK_m(s,a)u_iu_j\Bigg|\\
&= \Bigg|\si\pi_iu_i^2\left(K_i(s,a) -\sm\pi_mK_m(s,a) \right) -2\si\pi_iu_i\sj\pi_ju_j\left( K_i(s,a) -\sm\pi_mK_m(s,a) \right)\Bigg|\\
&\leq \si\pi_iu_i^2\underbrace{\abs{K_i(s,a) -\sm\pi_mK_m(s,a)}}_{\leq 1} +2 \si\pi_i\abs{u_i} \sj\pi_j\abs{u_j} \underbrace{\abs{K_i(s,a) -\sm\pi_mK_m(s,a)}}_{\leq 1}\\
&\leq \norm{u}_2^2 +2 \si\pi_i\abs{u_i}\sj\pi_j\abs{u_j}\leq 3\norm{u}^2_2.
\end{split}
\end{align*}

The rest of the proof is similar to [Mei et al., 2020] and we include this for completeness. Define $P(\alpha)\in \Real^{S\times S}$, where $\forall (s,s'),$

\[\left[P(\alpha) \right]_{(s,s')} = \sa \pi_{\theta_\alpha} (a\given s).\tP(s'|s,a). \]

The derivative w.r.t. $\alpha$ is,

\[ \left[\frac{\partial}{\partial \alpha} P(\alpha)\Big|_{\alpha=0} \right]_{(s,s') } = \sa \left[\frac{\partial}{\partial \alpha}\pi_{\theta_\alpha} (a\given s)\Big|_{\alpha=0}\right].\tP(s'|s,a).\]

For any vector $x\in \Real^S$,

\[\left[\frac{\partial}{\partial \alpha} P(\alpha)\Big|_{\alpha=0}x \right]_{(s) } = \sum\limits_{s'\in \cS}\sa \left[\frac{\partial}{\partial \alpha}\pi_{\theta_\alpha} (a\given s)\Big|_{\alpha=0}\right].\tP(s'|s,a). x(s'). \]

The $l_\infty$ norm can be upper-bounded as,

\begin{align*}
\norm{\frac{\partial}{\partial \alpha} P(\alpha)\Big|_{\alpha=0}x}_\infty &= \max\limits_{s\in \cS}\abs{ \sum\limits_{s'\in \cS}\sa \left[\frac{\partial}{\partial \alpha}\pi_{\theta_\alpha} (a\given s)\Big|_{\alpha=0}\right].\tP(s'|s,a). x(s') }\\
&\leq \max\limits_{s\in \cS} \sum\limits_{s'\in \cS}\sa \abs{\frac{\partial}{\partial \alpha}\pi_{\theta_\alpha} (a\given s)\Big|_{\alpha=0}}.\tP(s'|s,a). \norm{x}_\infty\\
&\leq 2\norm{u}_2\norm{x}_\infty.
\end{align*}

Now we find the second derivative,

\begin{align*}
\left[\frac{\partial^2P(\alpha)}{\partial\alpha^2} \Big|_{\alpha=0}\right]_{(s,s')} = \sa \left[\frac{\partial^2\pi_{\theta_\alpha}(a|s)}{\partial \alpha^2}\Big|_{\alpha=0} \right]\tP(s'|s,a)
\end{align*}

taking the $l_\infty$ norm,

\begin{align*}
\norm{\left[\frac{\partial^2P(\alpha)}{\partial\alpha^2} \Big|_{\alpha=0}\right]x}_{\infty} &= \max_s \abs{\sum\limits_{s'\in \cS}\sa \left[\frac{\partial^2\pi_{\theta_\alpha}(a|s)}{\partial \alpha^2}\Big|_{\alpha=0} \right]\tP(s'|s,a)x(s')}\\
&\leq \max_s \sum\limits_{s'\in \cS}\left[\abs{\frac{\partial^2\pi_{\theta_\alpha}(a|s)}{\partial \alpha^2}\Big|_{\alpha=0}} \right]\tP(s'|s,a)\norm{x}_\infty \leq 3\norm{u}_2\norm{x}_\infty.
\end{align*}

Next we observe that the value function of $\pi_{\theta_\alpha}:$

\[V^{\pi_{\theta_\alpha}}(s) = \underbrace{\sa \pi_{\theta_{\alpha}}(a|s)r(s,a)}_{r_{\theta_\alpha}} + \gamma \sa \pi_{\theta_{\alpha}}(a|s) \sum\limits_{s'\in \cS} \tP(s'|s,a)V^{\pi_{\theta_{\alpha}}}(s').  \]

In matrix form,

\begin{align*}
V^{\pi_{\theta_{\alpha}}} = r_{\theta_{\alpha}} + \gamma P(\alpha)V^{\pi_{\theta_{\alpha}}}\\
\implies \left(Id-\gamma P(\alpha) \right)V^{\pi_{\theta_{\alpha}}} = r_{\theta_{\alpha}}\\
V^{\pi_{\theta_{\alpha}}} = \left(Id-\gamma P(\alpha) \right)^{-1}r_{\theta_{\alpha}}.
\end{align*}

Let $M(\alpha):=\left(Id-\gamma P(\alpha) \right)^{-1}= \sum\limits_{t=0}^\infty \gamma^t [P(\alpha)]^t $.
Also, observe that

\[\mathbf{1} = \frac{1}{1-\gamma} \left(Id-\gamma P(\alpha) \right) \mathbf{1}\implies M(\alpha)\mathbf{1}=\frac{1}{1-\gamma}\mathbf{1}.\]

\[\implies \forall i \norm{[M(\alpha)]_{i,:}}_1 = \frac{1}{1-\gamma}\]

where $[M(\alpha)]_{i,:}$ is the $i^{th}$ row of $M(\alpha)$.
Hence for any vector $x\in \Real^S$, $\norm{M(\alpha)x}_\infty\leq \frac{1}{1-\gamma} \norm{x}_\infty.$

By assumption <ref>, we have $\norm{r_{\theta_\alpha}}_{\infty} = \max_s \abs{r_{\theta_\alpha}(s)} \leq 1$. Next we find the derivative of $r_{\theta_\alpha}$ w.r.t $\alpha$.

\begin{align*}
\abs{\frac{\partial r_{\theta_\alpha}(s)}{\partial \alpha}} &= \abs{\left(\frac{\partial r_{\theta_\alpha}(s)}{\partial \theta_\alpha}\right)\transpose \frac{\partial \theta_\alpha}{\partial \alpha}}\\
&\leq \abs{\sum\limits_{m''=1}^M\sm \sa \pi_{\theta_\alpha}(m'') (\ind_{mm''}-\pi_{\theta_\alpha}(m))K_m(s,a) r(s,a)u(m'')  }\\
&=\abs{\sum\limits_{m''=1}^M \sa \pi_{\theta_\alpha}(m'')K_{m''}(s,a) r(s,a)u(m'') - \sum\limits_{m''=1}^M \sm\sa \pi_{\theta_\alpha}(m'')\pi_{\theta_\alpha}(m)K_m(s,a) r(s,a)u(m'')}\\
%&\leq \abs{\sum\limits_{m''=1}^M \sa \pi_{\theta_\alpha}(m'')K_{m''}(s,a) u(m'') - \sum\limits_{m''=1}^M \sm\sa \pi_{\theta_\alpha}(m'')\pi_{\theta_\alpha}(m)K_m(s,a) u(m'')}\\
&\leq \abs{\sum\limits_{m''=1}^M \sa \pi_{\theta_\alpha}(m'')K_{m''}(s,a) r(s,a) - \sum\limits_{m''=1}^M \sm\sa \pi_{\theta_\alpha}(m'')\pi_{\theta_\alpha}(m)K_m(s,a) r(s,a)}\norm{u}_\infty \leq \norm{u}_2.\\
\end{align*}

Similarly, we can calculate the upper-bound on second derivative,

\begin{align*}
\norm{\frac{\partial r_{\theta_\alpha}}{\partial \alpha^2}}_\infty &= \max_s \abs{ \frac{\partial r_{\theta_\alpha}(s)}{\partial \alpha^2} }\\
&=\max_s \abs{\left( \frac{\partial}{\partial \alpha} \left\{ \frac{\partial r_{\theta_\alpha}(s)}{\partial \alpha}\right\} \right)\transpose \frac{\partial \theta_\alpha}{\partial \alpha}}\\
&= \max_s \abs{\left( \frac{\partial^2 r_{\theta_\alpha}(s)}{\partial \alpha^2}   \frac{\partial \theta_\alpha}{\partial \alpha}  \right)\transpose   \frac{\partial \theta_\alpha}{\partial \alpha} }
&\leq 5/2 \norm{u}_2^2.
\end{align*}

Next, the derivative of the value function w.r.t $\alpha$ is given by,

\[\frac{\partial V^{\pi_{\theta_\alpha}}(s)}{\partial \alpha} = \gamma e_s\transpose M(\alpha) \frac{\partial P(\alpha)}{\partial\alpha}M(\alpha)r_{\theta_\alpha} + e_s\transpose M(\alpha) \frac{\partial r_{\theta_\alpha}}{\partial \alpha}.\]

And the second derivative,

\begin{align*}
\begin{split}
\frac{\partial^2 V^{\pi_{\theta_\alpha}}(s)}{\partial \alpha^2} &= \underbrace{2\gamma^2e_s\transpose M(\alpha)\frac{\partial P(\alpha)}{\partial\alpha} M(\alpha)\frac{\partial P(\alpha)}{\partial\alpha}M(\alpha)r_{\theta_\alpha}}_{T1} + \underbrace{\gamma e_s\transpose M(\alpha) \frac{\partial^2 P(\alpha)}{\partial\alpha^2} M(\alpha)r_{\theta_\alpha}}_{T2}\\& + \underbrace{2\gamma  e_s\transpose M(\alpha)\frac{\partial P(\alpha)}{\partial\alpha} M(\alpha)\frac{\partial r_{\theta_\alpha}}{\partial \alpha}}_{T3}+ \underbrace{e_s\transpose M(\alpha)\frac{\partial^2 r_{\theta_\alpha}}{\partial\alpha^2}}_{T4}.
\end{split}
\end{align*}

We use the above derived bounds to bound each of the term in the above display. The calculations here are same as shown for Lemma 7 in [Mei et al., 2020], except for the particular values of the bounds. Hence we directly, mention the final bounds that we obtain and refer to [Mei et al., 2020] for the detailed but elementary calculations.

\begin{align*}
\abs{T1} &\leq \frac{4}{(1-\gamma)^3} \norm{u}_2^2\\
\abs{T2} &\leq \frac{3}{(1-\gamma)^2} \norm{u}_2^2\\
\abs{T3} &\leq \frac{2}{(1-\gamma)^2} \norm{u}_2^2\\
\abs{T4} &\leq \frac{5/2}{(1-\gamma)} \norm{u}_2^2.
\end{align*}

Combining the above bounds we get,

\[\abs{\frac{\partial^2 V^{\pi_{\theta_\alpha}}(s)}{\partial \alpha^2}\Big|_{\alpha=0}}\leq \left(\frac{8\gamma^2}{(1-\gamma)^3} + \frac{3\gamma}{(1-\gamma)^2} + \frac{4\gamma}{(1-\gamma)^2} + \frac{5/2}{(1-\gamma)} \right)\norm{u}_2^2 \]

\[=\frac{7\gamma^2+4\gamma+5}{2(1-\gamma)^3}\norm{u}_2. \]

Finally, let $y\in \Real^M$ and fix a $\theta \in \Real^M$:

\begin{align*}
\abs{y\transpose\frac{\partial^2 V^{\pi_{\theta}}(s)}{\partial\theta^2}y} &=\abs{\frac{y}{\norm{y}_2}\transpose\frac{\partial^2 V^{\pi_{\theta}}(s)}{\partial\theta^2}\frac{y}{\norm{y}_2}}.\norm{y}_2^2\\
&\leq \max\limits_{\norm{u}_2=1}\abs{\innprod{\frac{\partial^2 V^{\pi_{\theta}}(s)}{\partial\theta^2}u,u }}.\norm{y}_2^2\\
&= \max\limits_{\norm{u}_2=1}\abs{\innprod{\frac{\partial^2 V^{\pi_{\theta_\alpha}}(s)}{\partial\theta_\alpha^2}\Big|_{\alpha=0}\frac{\partial\theta_\alpha}{\partial \alpha},\frac{\partial\theta_\alpha}{\partial \alpha} }}.\norm{y}_2^2\\
&= \max\limits_{\norm{u}_2=1}\abs{\frac{\partial^2V^{\pi_{\theta_\alpha}}(s)}{\partial\alpha^2}\Big|_{\alpha=0}}.\norm{y}_2^2\\
&\leq \frac{7\gamma^2+4\gamma+5}{2(1-\gamma)^3}\norm{y}_2^2.
\end{align*}

Let $\theta_\xi:= \theta + \xi(\theta'-\theta)$ where $\xi\in [0,1]$. By Taylor's theorem $\forall s,\theta,\theta'$,

\[\abs{V^{\pi_{\theta'}}(s) -V^{\pi_{\theta}}(s) -\innprod{\frac{\partial V^{\pi_{\theta}}(s)}{\partial \theta} } } = \frac{1}{2}.\abs{(\theta'-\theta)\transpose \frac{\partial^2V^{\pi_{\theta_\xi}}(s) }{\partial \theta_\xi^2}(\theta'-\theta) } \]

\[\leq \frac{7\gamma^2+4\gamma+5}{4(1-\gamma)^3}\norm{\theta'-\theta}_2^2. \]

Since $V^{\pi_\theta}(s)$ is $\frac{7\gamma^2+4\gamma+5}{2(1-\gamma)^3}$ smooth for every $s$, $V^{\pi_\theta}(\mu)$ is also $\frac{7\gamma^2+4\gamma+5}{2(1-\gamma)^3}-$ smooth.

For any two policies $\pi$ and $\pi'$, and for any state $s\in \cS$, the following is true.

\[V^{\pi'}(s)-V^{\pi}(s) = \frac{1}{1-\gamma} \sum\limits_{s'\in \cS}d_s^{\pi'}(s')\sm \pi'_m \tilde{A}(s',m).\]

\begin{align*}
\allowdisplaybreaks
V^{\pi'}(s) - V^{\pi}(s) &= \sm\pi_m'\Q'(s,m) - \sm \pi_m \Q(s,m)\\
&=\sm \pi_m'\left(\Q'(s,m)-\Q(s,m) \right) +\sm (\pi_m'-\pi_m)\Q(s,m)\\
&=\sm(\pi_m'-\pi_m)\Q(s,m) +\underbrace{\sm\pi_m'\sum\limits_{a\in \cA} K_m(s,a)}_{=\sum\limits_{a\in \cA}\pi_\theta(a|s)}\sum\limits_{s'\in \cS} \tP(s'|s,a)\left[V^{\pi'}(s')-V^{\pi}(s') \right]\\
&=\frac{1}{1-\gamma}\sum\limits_{s'\in \cS} d_s^{\pi'}(s') \sum\limits_{m'=1}^M (\pi'_{m'}-\pi_{m'})\Q(s',m')\\
&=\frac{1}{1-\gamma}\sum\limits_{s'\in \cS} d_s^{\pi'}(s') \sum\limits_{m'=1}^M \pi'_{m'}(\Q{s',m'}-V(s'))\\
&=\frac{1}{1-\gamma}\sum\limits_{s'\in \cS} d_s^{\pi'}(s') \sum\limits_{m'=1}^M \pi'_{m'}\tilde{A}(s',m').
\end{align*}

(Value Difference Lemma-2)
For any two policies $\pi$ and $\pi'$ and state $s\in \cS$, the following is true.

\[V^{\pi'}(s)-V^{\pi}(s) = \frac{1}{1-\gamma} \sum\limits_{s'\in \cS} d_s^{\pi}(s')\sm (\pi_m'-\pi_m)\Q^{\pi'}(s',m). \]

We will use $\Q$ for $\Q^{\pi}$ and $\Q'$ for $\Q^{\pi'}$ as a shorthand.

\begin{align*}
\begin{split}
V^{\pi'}(s)-V^{\pi}(s) &= \sm \pi_m'\Q'(s,m) - \sm \pi_m\Q(s,m)\\
&=\sm(\pi_m'-\pi_m)\Q'(s,m) + \sm \pi_m(\Q'(s,m)-\Q(s,m))\\
&= \sm(\pi_m'-\pi_m)\Q'(s,m) + \\ & \gamma \sm \pi_m\left(\sum\limits_{a\in \cA} K_m(s,a)\sum\limits_{s'\in \cS} \tP(s'|s,a)V'(s') - \sum\limits_{a\in \cA} K_m(s,a)\sum\limits_{s'\in \cS} \tP(s'|s,a)V(s') \right)\\
&=\sm(\pi_m'-\pi_m)\Q'(s,m) + \gamma\sum\limits_{a\in \cA} \pi_\theta(a|s) \sum\limits_{s'\in \cS} \tP(s'|s,a) \left[V'(s)-V(s') \right]\\
&=\frac{1}{1-\gamma} \sum\limits_{s'\in \cS} d_s^{\pi}(s') \sm (\pi'_m-\pi_m) \Q'(s',m).
\end{split}
\end{align*}

The reward $r(s,a)\in [0,1]$, for all pairs $(s,a)\in \cS\times \cA$.

Let $\pi^*\bydef \argmax\limits_{\pi\in \cP_M} V^\pi(s_0)$. We make the following assumption.

\[\mathbb{E}_{m\sim \pi^*} \left[Q^{\pi_\theta}(s,m) \right] -V^{\pi_\theta}(s) \geq 0, \forall s\in \cS,\forall \pi_\theta \in \Pi. \]

Let the best controller be a point in the $M-simplex$, i.e., $K^* \bydef \sm\pi^*_mK_m$.

\begin{align*}
\norm{\frac{\partial}{\partial\theta}V^{\pi_\theta}(\mu)}_2 &=\left(\sm \left(\frac{\partial V^{\pi_\theta}(\mu)}{\partial\theta_m}\right)^2  \right)^{1/2}\\
&\geq \frac{1}{\sqrt{M}} \sm \abs{\frac{\partial V^{\pi_\theta}(\mu)}{\partial\theta_m}} \text{      \quad\quad (Cauchy-Schwarz)}\\
&=\frac{1}{\sqrt{M}} \sm \frac{1}{1-\gamma} \abs{\sum\limits_{s\in \cS} d_\mu^{\pi_\theta}(s)\pi_m\tilde{A}(s,m)} \text{\quad \quad Lemma \ref{lemma:Gradient simplification}}\\
&\geq\frac{1}{\sqrt{M}} \sm \frac{\pi_m^*\pi_m}{1-\gamma} \abs{\sum\limits_{s\in \cS} d_\mu^{\pi_\theta}(s)\tilde{A}(s,m)}\\
&\geq \left(\min\limits_{m:\pi^*_{\theta_{m}}>0} \pi_{\theta_m} \right) \frac{1}{\sqrt{M}} \sm \frac{\pi_m^*}{1-\gamma} \abs{\sum\limits_{s\in \cS} d_\mu^{\pi_\theta}(s)\tilde{A}(s,m)}\\
&\geq \left(\min\limits_{m:\pi^*_{\theta_{m}}>0} \pi_{\theta_m} \right) \frac{1}{\sqrt{M}} \abs{\sm \frac{\pi_m^*}{1-\gamma} \sum\limits_{s\in \cS} d_\mu^{\pi_\theta}(s)\tilde{A}(s,m)}\\
% &= \left(\min\limits_{m:\pi^*_{\theta_{m}}>0} \pi_{\theta_m} \right) \frac{1}{\sqrt{M}} \abs{\sm \frac{\pi_m^*}{1-\gamma} \sum\limits_{s\in \cS} d_\mu^{\pi_\theta}(s)\tilde{A}(s,m)}\\
&= \left(\min\limits_{m:\pi^*_{\theta_{m}}>0} \pi_{\theta_m} \right) \abs{\frac{1}{\sqrt{M}} \sum\limits_{s\in \cS} d_\mu^{\pi_\theta}(s){\sm \frac{\pi_m^*}{1-\gamma} \tilde{A}(s,m)}}\\
&= \left(\min\limits_{m:\pi^*_{\theta_{m}}>0} \pi_{\theta_m} \right) \frac{1}{\sqrt{M}} \sum\limits_{s\in \cS} d_\mu^{\pi_\theta}(s){\sm \frac{\pi_m^*}{1-\gamma} \tilde{A}(s,m)} \text{\quad \quad Assumption \ref{assumption:positivity of advantage}}\\
%&=\frac{1}{\sqrt{M}} \sm \frac{\pi_m^*\pi_m}{1-\gamma} \sum\limits_{s\in \cS} \frac{d_\mu^{\pi_\theta}(s)}{d_{\rho}^{\pi^*}(s)}d_{\rho}^{\pi^*}(s)\tilde{A}(s,m)\\
&\geq \frac{1}{\sqrt{M}}\frac{1}{1-\gamma}\left(\min\limits_{m:\pi^*_{\theta_{m}}>0} \pi_{\theta_m} \right) \norm{\frac{d_{\rho}^{\pi^*}}{d_{\mu}^{\pi_\theta}}}_{\infty}^{-1} \sum\limits_{s\in \cS} d_{\rho}^*(s) \sm \pi_m^*\tilde{A}(s,m)\\
&=\frac{1}{\sqrt{M}}\left(\min\limits_{m:\pi^*_{\theta_{m}}>0} \pi_{\theta_m} \right) \norm{\frac{d_{\rho}^{\pi^*}}{d_{\mu}^{\pi_\theta}}}_{\infty}^{-1} \left[V^*(\rho) -V^{\pi_\theta}(\rho) \right] \text{\quad \quad Lemma \ref{lemma:value diffence lemma}}.
\end{align*}

§.§ Proof of the Theorem <ref>

Let $\beta:=\frac{7\gamma^2+4\gamma+5}{\left(1-\gamma\right)^2}$. We have that,

\begin{align*}
V^*(\rho) -V^{\pi_\theta}(\rho) &= \frac{1}{1-\gamma} \sum\limits_{s\in \cS} d_\rho^{\pi_\theta}(s) \sm (\pi^*_m-\pi_m)\Q^{\pi^*}(s,m) \text{$\qquad$ (Lemma \ref{lemma:value diffrence lemma-2})}\\
&= \frac{1}{1-\gamma} \sum\limits_{s\in \cS} \frac{d_\rho^{\pi_\theta}(s)}{d_\mu^{\pi_\theta}(s)}d_\mu^{\pi_\theta}(s) \sm (\pi^*_m-\pi_m)\Q^{\pi^*}(s,m) \\
&\leq \frac{1}{1-\gamma} \norm{\frac{1}{d_\mu^{\pi_\theta}}}_{\infty} \sum\limits_{s\in \cS} \sm (\pi^*_m-\pi_m)\Q^{\pi^*}(s,m) \\
&\leq \frac{1}{(1-\gamma)^2} \norm{\frac{1}{\mu}}_\infty \sum\limits_{s\in \cS} \sm (\pi^*_m-\pi_m)\Q^{\pi^*}(s,m) \\
&=\frac{1}{(1-\gamma)} \norm{\frac{1}{\mu}}_\infty\left[V^*(\mu) -V^{\pi_\theta}(\mu) \right] \text{$\qquad$ (Lemma \ref{lemma:value diffrence lemma-2})}.
\end{align*}

Let $\delta_t\bydef V^*(\mu) -V^{\pi_{\theta_t}}(\mu)$.

\begin{align*}
\delta_{t+1}-\delta_t &= V^{\pi_{\theta_{t}}}(\mu)-V^{\pi_{\theta_{t+1}}}(\mu) \text{\qquad (Lemma \ref{lemma:smoothness of V})}\\
&\leq -\frac{1}{2\beta} \norm{\frac{\partial}{\partial\theta}V^{\pi_{\theta_{t}}}(\mu)}^2_2 \text{\qquad (Lemma \ref{lemma:gradient ascent lemma}  )}\\
&\leq -\frac{1}{2\beta} \frac{1}{{M}}\left(\min\limits_{m:\pi^*_{\theta_{m}}>0} \pi_{\theta_m} \right)^2 \norm{\frac{d_{\rho}^{\pi^*}}{d_{\mu}^{\pi_\theta}}}_{\infty}^{-2}  \delta_t^2 \text{\qquad (Lemma \ref{lemma:nonuniform lojaseiwicz inequality})}\\
&\leq -\frac{1}{2\beta} \left(1-\gamma\right)^2 \frac{1}{{M}}\left(\min\limits_{m:\pi^*_{\theta_{m}}>0} \pi_{\theta_m} \right)^2 \norm{\frac{d_{\rho}^{\pi^*}}{d_{\mu}^{\pi_\theta}}}_{\infty}^{-2}  \delta_t^2\\
&\leq -\frac{1}{2\beta} \left(1-\gamma\right)^2 \frac{1}{{M}}\left(\min\limits_{1\leq s\leq t}\min\limits_{m:\pi^*_{\theta_{m}}>0} \pi_{\theta_m} \right)^2 \norm{\frac{d_{\rho}^{\pi^*}}{d_{\mu}^{\pi_\theta}}}_{\infty}^{-2}  \delta_t^2\\\\
&= -\frac{1}{2\beta} \frac{1}{M}\left(1-\gamma\right)^2 \norm{\frac{d_\mu^{\pi^*}}{\mu}}_{\infty}^{-2}c_t^2 \delta_t^2,\\
\end{align*}

where $c_t\bydef \min\limits_{1\leq s\leq t} \min\limits_{m:\pi^*_m>0}\pi_{\theta_s}(m)$.

Hence we have that,

\begin{equation}\label{eq:induction step}
\delta_{t+1} \leq \delta_t - \frac{1}{2\beta} \frac{\left(1-\gamma\right)^2}{M} \norm{\frac{d_\mu^{\pi^*}}{\mu}}_{\infty}^{-2}c_t^2 \delta_t^2.
\end{equation}

The rest of the proof follows from a induction argument over $t\geq1$.

Base case: Since $\delta_t\leq \frac{1}{1-\gamma}$, and $c_t \in (0,1)$, the result holds for all $t\leq \frac{2\beta M}{(1-\gamma)}\norm{\frac{d_\mu^{\pi^*}}{\mu}}_{\infty}^2.$

For ease of notation, let $\phi_t\bydef \frac{2\beta M}{c_t^2(1-\gamma)^2}\norm{\frac{d_\mu^{\pi^*}}{\mu}}_{\infty}^2$. We need to show that $\delta_t\leq \frac{\phi_t}{ t}$, for all $t\geq 1$.

Induction step: Fix a $t\geq 2$, assume $\delta_t \leq \frac{\phi_t}{t}$.

Let $g:\Real\to \Real$ be a function defined as $g(x) = x-\frac{1}{\phi_t}x^2$. One can verify easily that $g$ is monotonically increasing in $\left[ 0, \frac{\phi_t}{2}\right]$. Next with equation <ref>, we have

\begin{align*}
\delta_{t+1} &\leq \delta_t -\frac{1}{\phi_t} \delta_t^2\\
&= g(\delta_t)\\
&\leq g(\frac{\phi_t}{ t})\\
&\leq \frac{\phi_t}{t} - \frac{\phi_t}{t^2}\\
&= \phi_t\left(\frac{1}{t}-\frac{1}{t^2} \right)\\
&\leq \phi_t\left(\frac{1}{t+1}\right)\\
&\leq \phi_{t+1}\left(\frac{1}{t+1}\right).
\end{align*}

where the last step follows from the fact that $c_{t+1}\leq c_t$ (infimum over a larger set does not increase the value). This completes the proof.

Let $f:\Real^M\to \Real$ be $\beta-$smooth. Then gradient ascent with learning rate $\frac{1}{\beta}$ guarantees, for all $x,x'\in \Real^M$:

\[f(x)-f(x') \leq -\frac{1}{2\beta}\norm{\frac{df(x)}{dx}}_2^2. \]

\begin{align*}
f(x) -f(x') &\leq -\innprod{\frac{\partial f(x)}{\partial x}} + \frac{\beta}{2}.\norm{x'-x}_2^2\\
&= \frac{1}{\beta} \norm{\frac{df(x)}{dx}}_2^2 + \frac{\beta}{2}\frac{1}{\beta^2}\norm{\frac{df(x)}{dx}}_2^2\\
&= -\frac{1}{2\beta}\norm{\frac{df(x)}{dx}}_2^2.
\end{align*}

§ PROOFS FOR (NATURAL) ACTOR-CRITIC BASED IMPROPER LEARNING

We will begin with some useful lemmas.

For any $\theta,\theta\in \Real^M$, we have $\norm{\psi_\theta(m)-\psi_{\theta'}(m)}_2\leq \norm{\theta-\theta'}_2$.

Recall, $\psi_{\theta}(m):= \nabla_\theta \log \pi_\theta(m)$. Fix $m'\in [M]$,

\begin{align*}
\frac{\partial\log\pi_\theta(m)}{\partial \theta_{m'}} &= \frac{\partial\log\left( \frac{e^{\theta_m}}{\sum\limits_{j=1}^M e^{\theta_j}}  \right)}{\partial \theta_{m'}}\\
&= \frac{\partial}{\partial\theta_{m'}} \left(\theta_m-\log\left(\sum\limits_{j=1}^M e^{\theta_j}  \right) \right)\\
&= \mathbbm{1}\{m'=m\} - \frac{e^{\theta_{m'}}}{\sum\limits_{j=1}^M e^{\theta_j} } \\
&= \mathbbm{1}\{m'=m\} - \pi_{\theta}(m').
\end{align*}

\begin{align*}
\norm{\psi_\theta(m)-\psi_{\theta'}(m)}_2\leq \norm{\theta-\theta'}_2 &=\norm{\nabla_\theta \log \pi_{\theta}(m)-\nabla_\theta \log \pi_{\theta'}(m)}_2\\
&=\norm{\pi_\theta(.) - \pi_{\theta'}(.) }_2\\
&\leq^{(*)} \norm{\theta-\theta'}_2.
\end{align*}

Here (*) follows from the fact that the softmax function is 1-Lipschitz [Gao & Pavel, 2017].

For all $m\in [M]$ and $\theta\in \Real^M$,  $\norm{\psi_\theta(m)}_2 \leq \sqrt{2} $.

Proof follows by noticing that $\norm{\psi_\theta(m)}_2=\norm{\nabla_\theta \log \pi_\theta(m)}_2\leq \sqrt{2}$, where the last inequality follows because the 2-norm of a probability vector is bounded by 1.

For all $\theta,\theta'\in \Real^M$, $\norm{\pi_\theta(.)-\pi_{\theta'}(.)}_{TV}\leq \frac{\sqrt{M}}{2}\norm{\theta-\theta'}_2$.

\begin{align*}
\norm{\pi_\theta(.)-\pi_{\theta'}(.)}_{TV} &= \frac{1}{2}\norm{\pi_\theta(.)-\pi_{\theta'}(.)}_{1}\\
&\leq \frac{\sqrt{M}}{2}\norm{\pi_\theta(.)-\pi_{\theta'}(.)}_{2}.
\end{align*}

The inequality follows from relation between 1-norm and 2-norm.

For any $\theta,\theta'\in \Real^M$,

\[ \nabla V(\theta) - \nabla V(\theta')\leq \sqrt{M}L_V \norm{\theta-\theta'}_2  \]

where $L_V=\frac{2\sqrt{2}C_{\kappa \xi} +1}{1-\gamma}$, and $C_{\kappa \xi}=\left( 1+\left\lceil{\log_\xi\frac{1}{\kappa}}\right\rceil +\frac{1}{1-\xi}  \right)$.

We follow the same steps as in Proposition 1 in [Xu et al., 2020] along with Lemmas <ref>,<ref>,<ref> and that the maximum reward is bounded by 1.

We will now restate a useful result from [Xu et al., 2020], about the convergence of the critic parameter $w_t$ to the equilibrium point $w^*$ of the underlying ODE, applied to our setting.

Suppose assumptions`<ref> and  <ref> hold. Then is $\beta\leq \min\left\{\frac{\Gamma_L}{16},\frac{8}{\Gamma_L}  \right\}$ and $H\geq \left( \frac{4}{\Gamma_L}+2\alpha \right)\left[\frac{1536[1+(\kappa-1)\xi]}{(1-\xi)\Gamma_L}  \right]$. We have

\[ \expect{\norm{w_{T_c}-w^*}_2^2}\leq \left(1-\frac{\Gamma_L}{16}\alpha  \right)^{T_c}\norm{w_0-w^*}_2^2 + \left(\frac{4}{\Gamma_L}+2\alpha \right)\frac{1536(1+R_w^2)[1+(\kappa-1)\xi]}{(1-\xi)H}.   \]

If we further let $T_c\geq \frac{16}{\Gamma_L\alpha}\log \frac{2\norm{w_0-w^*}^2_2}{\epsilon}$ and $H\geq \left(\frac{4}{\Gamma_L}+2\alpha \right)\frac{3072(R_w^2+1)[1+(\kappa-1)\xi]}{(1-\xi)\Gamma_L\epsilon}$, then we have $\expect{\norm{w_{T_c}-w^*}_2^2}\leq \epsilon$ with total sample complexity given by $T_cH=\mathcal{O}\left(\frac{1}{\alpha\epsilon}\log\frac{1}{\epsilon} \right)$.

Proof follows along the similar lines as in Thm. 4 in Xu et al., 2020 and by using $\norm{\phi(s)(\gamma\phi(s')-\phi(s))^\top}_F\leq (1+\gamma)\leq 2$ and assuming $\norm{\phi(s)}_2\leq 1$ for all $s,s'\in \cS$.

§.§ Actor-critic based improper learning

Let $v_t(w):=\frac{1}{B}\sum\limits_{i=0}^{B-1}\cE(s_{t,i},m_{t,i},s_{t,i+1})\psi_{\theta_t}(m_{t,i})$ and $A_w(s,m):=\mathbb{E}_{\bar{P}}\left[\cE(s,m,s')|(s,m) \right]$ and $g(w,\theta):=\mathbb{E}_{\nu_\theta}[A_w(s,m)\psi_\theta(m)]$ for all $\theta\in \Real^M,w\in\Real^d,s\in \cS, m\in [M]$.
Using Prop <ref> we get,

\begin{align*}
\begin{split}
V(\theta_{t+1}) &\geq V(\theta_t) + \innprod{\nabla_{\theta}V(\theta_t), \theta_{t+1}-\theta_t} - \frac{\sqrt{M}L_V}{2}\norm{\theta_{t+1}-\theta_t}_2^2\\
&=V(\theta_t) + \alpha\innprod{\nabla_{\theta}V(\theta_t), v_t(w_t)-\nabla_{\theta}V(\theta_t)+\nabla_{\theta}V(\theta_t)} - \frac{\sqrt{M}L_V\alpha^2}{2}\norm{v_t(w_t)}_2^2\\
&=V(\theta_t) +\alpha\norm{\nabla_{\theta}V(\theta_t)}_2^2 \\ &+\alpha\innprod{\nabla_{\theta}V(\theta_t), v_t(w_t)-\nabla_{\theta}V(\theta_t)}- \frac{\sqrt{M}L_V\alpha^2}{2}\norm{v_t(w_t)}_2^2\\
&\geq V(\theta_t) +\left(\frac{1}{2}\alpha- {\sqrt{M}L_V\alpha^2} \right)\norm{\nabla_{\theta}V(\theta_t)}_2^2  -\left(\frac{1}{2}\alpha+ {\sqrt{M}L_V\alpha^2} \right)\norm{v_t(w_t)-\nabla_{\theta}V(\theta_t)}_2^2
\end{split}
\end{align*}

Taking expectations and rearranging, we have

\begin{align*}
&\left(\frac{1}{2}\alpha- {\sqrt{M}L_V\alpha^2} \right)\expect{\norm{\nabla_{\theta}V(\theta_t)}_2^2|\cF_t}\\
&\leq \expect{V(\theta_{t+1})|\cF_t} -V(\theta_t) + \left(\frac{1}{2}\alpha+ {\sqrt{M}L_V\alpha^2} \right)\expect{\norm{v_t(w_t)-\nabla_{\theta}V(\theta_t)}_2^2|\cF_t}.
\end{align*}

Next we will upperbound $\expect{\norm{v_t(w_t)-\nabla_{\theta}V(\theta_t)}_2^2|\cF_t}$.

\begin{align*}
& {\norm{v_t(w_t)-\nabla_{\theta}V(\theta_t)}_2^2}\\
&\leq 3\norm{v_t(w_t) -v_t(w^*_{\theta_t}) }_2^2 + 3\norm{v_t(w^*_{\theta_t})-g(w^*_{\theta_t})}_2^2 + 3\norm{g(w^*_{\theta_t})-\nabla_{\theta}V(\theta_t)}_2^2.
\end{align*}

\begin{align*}
\norm{v_t(w_t) -v_t(w^*_{\theta_t}) }_2^2 &= \norm{\frac{1}{B} \sum\limits_{i=0}^{B-1} [\cE_{w_t}(s_{t,i}, m_{t,i}, s_{t, i+1})-\cE_{w^*_{\theta_t}}(s_{t,i}, m_{t,i}, s_{t, i+1})]\psi(m_{t,i})}_2^2 \\
&\leq \frac{1}{B}\sum\limits_{i=0}^{B-1}\norm{[\cE_{w_t}(s_{t,i}, m_{t,i}, s_{t, i+1})-\cE_{w^*_{\theta_t}}(s_{t,i}, m_{t,i}, s_{t, i+1})]\psi(m_{t,i})}_2^2\\
&\leq \frac{2}{B}\sum\limits_{i=0}^{B-1}\norm{[\cE_{w_t}(s_{t,i}, m_{t,i}, s_{t, i+1})-\cE_{w^*_{\theta_t}}(s_{t,i}, m_{t,i}, s_{t, i+1})]}_2^2\\
&=\frac{2}{B}\sum\limits_{i=0}^{B-1} \norm{(\gamma \phi(s_{t,i+1})-\phi(s_{t,i}))^\top(w_t-w^*_{\theta_t})}_2^2\\
&\leq \frac{8}{B}\sum\limits_{i=0}^{B-1} \norm{(w_t-w^*_{\theta_t})}_2^2=8 \norm{(w_t-w^*_{\theta_t})}_2^2.
\end{align*}

Next we have,

\begin{align*}
\norm{g(w^*_{\theta_t})-\nabla_{\theta}V(\theta_t)}_2^2 &=\norm{\mathbb{E}_{\nu_{\theta_t}}[A_{w^*_{\theta_t}}(s,m)\psi_{\theta_t}(m)]-\mathbb{E}_{\nu_{\theta_t}}[A_{\pi_{\theta_t}}(s,m)\psi_{\theta_t}(m)]  }_2^2\\
&\leq 2 \mathbb{E}_{\nu_{\theta_t}}\norm{A_{w^*_{\theta_t}}(s,m)-A_{\pi_{\theta_t}}(s,m)}_2^2\\
&=2\mathbb{E}_{\nu_{\theta_t}}\left[ | \gamma\expect{V_{w^*_{\theta_t}}(s')-V_{\pi_{{\theta_t}}}(s')|s,m}+ +V_{\pi_{{\theta_t}}}(s)-V_{w^*_{\theta_t}}(s) |^2 \right]\\
&\leq  8 \Delta_{critic}.
\end{align*}

Finally we bound the last term $\norm{v_t(w^*_{\theta_t})-g(w^*_{\theta_t})}_2^2$ by using Assumption <ref> we have,

\begin{align*}
\norm{v_t(w^*_{\theta_t})-g(w^*_{\theta_t})}_2^2 &\leq \expect{\norm{\frac{1}{B}\sum\limits_{i=0}^{B-1}\cE_{w^*_{\theta_t}}(s_{t,i}, m_{t,i}, s_{t,i+1})\psi_{\theta_t}(m_{t,i}) - \mathbb{E}_{\nu_{\theta_t}}[A_{w^*_{\theta_t}}(s,m)\psi_{\theta_t}(m)]}_2^2 |\cF_t}.
\end{align*}

We will now proceed in the similar manner as in [Xu et al., 2020] (eq 24 to eq 26), and using Lemma <ref>, we have

\begin{align*}
\expect{\norm{v_t(w^*_{\theta_t})-g(w^*_{\theta_t})}_2^2|\cF_t} &\leq \frac{32(1+R_w)^2[1+(\kappa-1)\xi]}{B(1-\xi)}.
\end{align*}

Putting things back we have,

\begin{align*}
\expect{{\norm{v_t(w_t)-\nabla_{\theta}V(\theta_t)}_2^2}\Big|\cF_t } &\leq \frac{96(1+R_w)^2[1+(\kappa-1)\xi]}{B(1-\xi)} + {24} \expect{\norm{(w_t-w^*_{\theta_t})}_2^2} + 24 \Delta_{critic}.
\end{align*}

Hence we get,

\begin{align*}
\begin{split}
&\left(\frac{1}{2}\alpha- {\sqrt{M}L_V\alpha^2} \right)\expect{\norm{\nabla_{\theta}V(\theta_t)}_2^2}\\&\leq \expect{V(\theta_{t+1})} -\expect{V(\theta_t)} \\&+ \left(\frac{1}{2}\alpha+ {\sqrt{M}L_V\alpha^2} \right)\left(\frac{96(1+R_w)^2[1+(\kappa-1)\xi]}{B(1-\xi)}
+ {24} \expect{\norm{(w_t-w^*_{\theta_t})}_2^2} + 24 \Delta_{critic}\right).
\end{split}
\end{align*}

We put $\alpha=\frac{1}{4L_V\sqrt{M}}$ above to get,

\begin{align*}
\begin{split}
\left(\frac{1}{16L_V\sqrt{M}} \right)\expect{\norm{\nabla_{\theta}V(\theta_t)}_2^2}&\leq \expect{V(\theta_{t+1})} -\expect{V(\theta_t)} \\&+ \left(\frac{1}{4L_V\sqrt{M}} \right)\left(\frac{96(1+R_w)^2[1+(\kappa-1)\xi]}{B(1-\xi)}
+ {24} \expect{\norm{(w_t-w^*_{\theta_t})}_2^2} + 24 \Delta_{critic}\right).
\end{split}
\end{align*}

which simplifies as

\begin{align*}
\begin{split}
&\expect{\norm{\nabla_{\theta}V(\theta_t)}_2^2}\\&\leq 16L_V\sqrt{M}\left(\expect{V(\theta_{t+1})} -\expect{V(\theta_t)}\right) + \frac{384(1+R_w)^2[1+(\kappa-1)\xi]}{B(1-\xi)}
+ {96} \expect{\norm{(w_t-w^*_{\theta_t})}_2^2} + 96 \Delta_{critic}.
\end{split}
\end{align*}

Taking summation over $t=0,1,2,\ldots, T-1$ and dividing by $T$,

\begin{align*}
\begin{split}
&\leq \frac{16L_V\sqrt{M}\left(\expect{V(\theta_{T})} -\expect{V(\theta_0)}\right)}{T} + \frac{384(1+R_w)^2[1+(\kappa-1)\xi]}{B(1-\xi)}
+ {96} \frac{1}{T}\sum\limits_{t=0}^{T-1}\expect{\norm{(w_t-w^*_{\theta_t})}_2^2} + 96 \Delta_{critic}\\
&\leq \frac{16L_V\sqrt{M}}{(1-\gamma)T} + \frac{384(1+R_w)^2[1+(\kappa-1)\xi]}{B(1-\xi)}
+ {96} \frac{1}{T}\sum\limits_{t=0}^{T-1}\expect{\norm{(w_t-w^*_{\theta_t})}_2^2} + 96 \Delta_{critic}
\end{split}
\end{align*}

We now let $B\geq  \frac{1152}{(1+R_w)^2[1+(\kappa-1)\xi]}{(1-\xi)\epsilon}$, $\expect{\norm{(w_t-w^*_{\theta_t})}_2^2} \leq \frac{\epsilon}{288}$ and $T\geq \frac{48L_V\sqrt{M}}{(1-\gamma)\epsilon}$, then we have

\[\expect{\norm{\nabla_{\theta}V(\theta_{\hat{T}})}_2^2} \leq \epsilon + \cO(\Delta_{critic}).\]

This leads to the final sample complexity of $(B+HT_c)T=\left(\frac{1}{\epsilon}+\frac{\sqrt{M}}{\epsilon}\log\frac{1}{\epsilon} \right)\left(\frac{\sqrt{M}}{(1-\gamma)^2\epsilon} \right)=\cO\left(\frac{M}{(1-\gamma)^2\epsilon^2}\log\frac{1}{\epsilon}\right)$

§.§ Natural-actor-critic based improper learning

§.§.§ Proof of Theorem <ref>

We first show that the natural actor-critic improper learner converges to a stationary point. We will then show convergence to the global optima which is what is different from that of [Xu et al., 2020].

Let $v_t(w):=\frac{1}{B}\sum_{i=0}^{B-1} \cE_w(s_{t,i},m_{t,i}, s_{t,i+1})\psi_{\theta_t}(m_{t,i})$, $A_w(s,m):=\mathbb{E}_{\tilde{P}}[\cE(s,m,s')|s,m]$ and $g(w,\theta):=\mathbb{E}_{\nu_\theta}[A_w(s,m)\psi_\theta(m)]$ for $w\in \Real^d$ and $\theta\in \Real^M$. Also let $u_t(w):=[F_t(\theta_t)+\lambda I]^{-1}\left[\frac{1}{B}\sum_{i=0}^{B-1}\cE_w(s_{t,i},m_{t,i},s_{t,i+1})\psi_{\theta_t}(m_{t,i})\right] = [F_t(\theta_t)+\lambda I]^{-1}v_t(w)$.

Recall Prop <ref>. We have

Assume $\sup_{s\in \cS}\norm{\phi(s)}_2 \leq 1$. Under Assumptions <ref> and <ref> with step-sizes chosen as $\alpha=\left(\frac{\lambda^2}{2\sqrt{M}L_V(1+\lambda)}\right)$, we have

\begin{align*}
\begin{split}
\mathbb{E}[\norm{\nabla_\theta V(\theta_{\hat{T}})}_2^2]
&=\frac{1}{T}\sum_{t=0}^{T-1} \mathbb{E}[\norm{\nabla_\theta V(\theta_t)}_2^2] \\
&\leq \frac{16\sqrt{M}L_V(1+\lambda)^2}{\lambda^2}\frac{\expect{V(\theta_T)}-V(\theta_0)}{T} + \frac{108}{\lambda^2}[2(1+\lambda)^2+\lambda^2]\frac{\sum_{t=0}^{T-1}\expect{\norm{w_t-w_{\theta_t}^*}_2^2}}{T} \\
&+ [2(1+\lambda)^2 +\lambda^2]\left( \frac{32}{\lambda^4(1-\gamma)^2} + \frac{432(1+2R_w)^2}{\lambda^2}  \right) \frac{1+(\kappa-1)\xi}{(1-\xi)B} +\frac{216}{\lambda^2}[2(1+\lambda)^2+\lambda^2]\Delta_{critic}.
\end{split}
\end{align*}

Proof is similar to first part of proof of Thm 6 in [Xu et al., 2020] and similar to Thm <ref>, along with using Prop  <ref> and Lemmas  <ref>,  <ref> and <ref>.

We now move to proving the global optimality of natural actor critic based improper learner. Let $KL(\cdot,\cdot)$ be the KL-divergence between two distributions. We denote $\tt{D}(\theta):=KL(\pi^*, \pi_\theta)$, $u_{\theta_t}^\lambda:=(F(\theta_t)+\lambda I)^{-1}\nabla_\theta V(\theta_t)$ and $u^\dagger_{\theta_t}:=F(\theta_t)^\dagger \nabla_\theta V(\theta_t)$. We see that

\begin{align*}
\allowdisplaybreaks
\begin{split}
\allowdisplaybreaks
&\tt{D}({\theta_t}) -\tt{D}({\theta_{t+1}}) \\
&= \sum\limits_{m=1}^M \pi^*(m) \log\pi_{\theta_{t+1}}(m) - \log\pi_{\theta_{t}}(m)\\
&\stackrel{(i)}{=} \sum\limits_{s\in \cS}d_\rho^{\pi^*}(s)\sum\limits_{m=1}^M \pi^*(m) \log\pi_{\theta_{t+1}}(m) - \log\pi_{\theta_{t}}(m)\\
&= \mathbb{E}_{\nu_{\pi^*}} [\log\pi_{\theta_{t+1}}(m) - \log\pi_{\theta_{t}}(m)]\\
&\stackrel{(ii)}{\geq} \mathbb{E}_{\nu_{\pi^*}}\left[\nabla_\theta\log(\pi_{\theta_t}(m)) \right]^\top(\theta_{t+1}-\theta_t) -\frac{\norm{\theta_{t+1}-\theta_t}_2^2}{2}\\
&=\mathbb{E}_{\nu_{\pi^*}}\left[\psi_{\theta_t}(m) \right]^\top(\theta_{t+1}-\theta_t) -\frac{\norm{\theta_{t+1}-\theta_t}_2^2}{2}\\
&=\alpha\mathbb{E}_{\nu_{\pi^*}}\left[\psi_{\theta_t}(m) \right]^\top u_t(w_t) -\frac{\alpha^2\norm{u_t(w_t)}_2^2}{2}\\
&=\alpha\mathbb{E}_{\nu_{\pi^*}}\left[\psi_{\theta_t}(m) \right]^\top u^\lambda_{\theta_t} + \alpha\mathbb{E}_{\nu_{\pi^*}}\left[\psi_{\theta_t}(m) \right]^\top (u_t(w_t)-u^\lambda_{\theta_t})-\frac{\alpha^2\norm{u_t(w_t)}_2^2}{2}\\
&=\alpha\mathbb{E}_{\nu_{\pi^*}}\left[\psi_{\theta_t}(m) \right]^\top u^\dagger_{\theta_t} + \alpha\mathbb{E}_{\nu_{\pi^*}}\left[\psi_{\theta_t}(m) \right]^\top (u^\lambda_{\theta_t}-u^\dagger_{\theta_t}) + \alpha\mathbb{E}_{\nu_{\pi^*}}\left[\psi_{\theta_t}(m) \right]^\top (u_t(w_t)-u^\lambda_{\theta_t})-\frac{\alpha^2\norm{u_t(w_t)}_2^2}{2}\\
&=\alpha\mathbb{E}_{\nu_{\pi^*}}[A_{\pi_{\theta_t}}(s,m)] + \alpha\mathbb{E}_{\nu_{\pi^*}}[\psi_{\theta_t}(m)^\top u^\dagger_{\theta_t} - A_{\pi_{\theta_t}}(s,m)] + \alpha\mathbb{E}_{\nu_{\pi^*}}\left[\psi_{\theta_t}(m) \right]^\top (u^\lambda_{\theta_t}-u^\dagger_{\theta_t}) \\&+ \alpha\mathbb{E}_{\nu_{\pi^*}}\left[\psi_{\theta_t}(m) \right]^\top (u_t(w_t)-u^\lambda_{\theta_t})-\frac{\alpha^2\norm{u_t(w_t)}_2^2}{2}\\
&\stackrel{(iii)}{=} (1-\gamma) (V({\pi^*})-V(\pi_{\theta_t})) + \alpha\mathbb{E}_{\nu_{\pi^*}}[\psi_{\theta_t}(m)^\top u^\dagger_{\theta_t} - A_{\pi_{\theta_t}}(s,m)] + \alpha\mathbb{E}_{\nu_{\pi^*}}\left[\psi_{\theta_t}(m) \right]^\top (u^\lambda_{\theta_t}-u^\dagger_{\theta_t}) \\&+ \alpha\mathbb{E}_{\nu_{\pi^*}}\left[\psi_{\theta_t}(m) \right]^\top (u_t(w_t)-u^\lambda_{\theta_t})-\frac{\alpha^2\norm{u_t(w_t)}_2^2}{2}\\
&\geq (1-\gamma) (V({\pi^*})-V(\pi_{\theta_t})) - \alpha\sqrt{\mathbb{E}_{\nu_{\pi^*}}[[\psi_{\theta_t}(m)^\top u^\dagger_{\theta_t} - A_{\pi_{\theta_t}}(s,m)]^2]} + \alpha\mathbb{E}_{\nu_{\pi^*}}\left[\psi_{\theta_t}(m) \right]^\top (u^\lambda_{\theta_t}-u^\dagger_{\theta_t}) \\&+ \alpha\mathbb{E}_{\nu_{\pi^*}}\left[\psi_{\theta_t}(m) \right]^\top (u_t(w_t)-u^\lambda_{\theta_t})-\frac{\alpha^2\norm{u_t(w_t)}_2^2}{2}\\
&\stackrel{(iv)}{\geq} (1-\gamma) (V({\pi^*})-V(\pi_{\theta_t})) - \sqrt{\norm{\frac{\nu_{\pi^*}}{\nu_{\pi_{\theta_t}}}}_{\infty}}\alpha\sqrt{\mathbb{E}_{\nu_{\pi^*}}[[\psi_{\theta_t}(m)^\top u^\dagger_{\theta_t} - A_{\pi_{\theta_t}}(s,m)]^2]} + \alpha\mathbb{E}_{\nu_{\pi^*}}\left[\psi_{\theta_t}(m) \right]^\top (u^\lambda_{\theta_t}-u^\dagger_{\theta_t}) \\&+ \alpha\mathbb{E}_{\nu_{\pi^*}}\left[\psi_{\theta_t}(m) \right]^\top (u_t(w_t)-u^\lambda_{\theta_t})-\frac{\alpha^2\norm{u_t(w_t)}_2^2}{2}\\
&\stackrel{(v)}{\geq} (1-\gamma) (V({\pi^*})-V(\pi_{\theta_t})) - \sqrt{\frac{1}{1-\gamma}\norm{\frac{\nu_{\pi^*}}{\nu_{\pi_{\theta_0}}}}_{\infty}}\alpha\sqrt{\mathbb{E}_{\nu_{\pi^*}}[[\psi_{\theta_t}(m)^\top u^\dagger_{\theta_t} - A_{\pi_{\theta_t}}(s,m)]^2]}  \\&+\alpha\mathbb{E}_{\nu_{\pi^*}}\left[\psi_{\theta_t}(m) \right]^\top (u^\lambda_{\theta_t}-u^\dagger_{\theta_t}) + \alpha\mathbb{E}_{\nu_{\pi^*}}\left[\psi_{\theta_t}(m) \right]^\top (u_t(w_t)-u^\lambda_{\theta_t})-\frac{\alpha^2\norm{u_t(w_t)}_2^2}{2}\\
&\stackrel{(vi)}{\geq}  (1-\gamma) (V({\pi^*})-V(\pi_{\theta_t})) - \sqrt{\frac{1}{1-\gamma}\norm{\frac{\nu_{\pi^*}}{\nu_{\pi_{\theta_0}}}}_{\infty}}\alpha\sqrt{\mathbb{E}_{\nu_{\pi^*}}[[\psi_{\theta_t}(m)^\top u^\dagger_{\theta_t} - A_{\pi_{\theta_t}}(s,m)]^2]} - \alpha C_{soft}\lambda \\&- 2\alpha\norm{ u_t(w_t)-u^\lambda_{\theta_t}}_2-\frac{\alpha^2\norm{u_t(w_t)}_2^2}{2}.
\end{split}
\end{align*}

where (i) is by taking an extra expectation without changing the inner summand, (ii) follows by Lemma <ref> and Lemma 5 in [Xu et al., 2020], (iii) follows by the value difference lemma (Lemma <ref>), (iv) follows by defining $\norm{\frac{\nu_{\pi^*}}{\nu_{\pi_{\theta_t}}}}_{\infty}:=\max_{s,m}\frac{\nu_{\pi^*}(s,m)}{\nu_{\pi_{\theta_t}}(s,m)}$, (v) follows because $\nu_{\pi_{\theta_t}}(s,m) \geq (1-\gamma)\nu_{\pi_{\theta_0}}(s,m)$, (vi) follows by Lemma6 in [Xu et al., 2020]and Lemma <ref>.

Next, we denote $\Delta_{actor}:=\max_{\theta\in \Real^M}\min_{w\in \Real^d}\mathbb{E}_{\nu_{\pi_\theta}}[[\psi_\theta^\top w - A_{\pi_\theta}(s,m)]^2]$ as the actor error.

\begin{align*}
\allowdisplaybreaks
\begin{split}
&\tt{D}({\theta_t}) -\tt{D}({\theta_{t+1}}) \\
&\geq(1-\gamma) (V({\pi^*})-V(\pi_{\theta_t})) - \sqrt{\frac{1}{1-\gamma}\norm{\frac{\nu_{\pi^*}}{\nu_{\pi_{\theta_0}}}}_{\infty}}\alpha\sqrt{\Delta_{actor}} - \alpha C_{soft}\lambda \\&- 2\alpha\norm{ u_t(w_t)-u^\lambda_{\theta_t}}_2-\frac{\alpha^2\norm{u_t(w_t)}_2^2}{2}\\
&\geq (1-\gamma) (V({\pi^*})-V(\pi_{\theta_t})) - \sqrt{\frac{1}{1-\gamma}\norm{\frac{\nu_{\pi^*}}{\nu_{\pi_{\theta_0}}}}_{\infty}}\alpha\sqrt{\Delta_{actor}} - \alpha C_{soft}\lambda \\&- 2\alpha\norm{ u_t(w_t)-u^\lambda_{\theta_t}}_2-\frac{\alpha^2\norm{u_t(w_t)-u^\lambda(\theta_t)}_2^2}{2}-\frac{\alpha^2}{\lambda^2}\norm{\nabla_{\theta}V(\theta_t)}_2^2.\\
\end{split}
\end{align*}

Rearranging and dividing by $(1-\gamma)\alpha$, and taking expectation both sides we get

\begin{align*}
\begin{split}
& V({\pi^*})-\expect{V(\pi_{\theta_t})}\\
&\leq \frac{\expect{\tt{D}(\theta_t)}-\expect{\tt{D}(\theta_{t+1})}}{(1-\gamma)\alpha} +\frac{2\sqrt{\mathbb{E}[\norm{ u_t(w_t)-u^\lambda_{\theta_t}}_2^2]}}{1-\gamma} + \frac{\alpha\expect{\norm{u_t(w_t)-u^\lambda(\theta_t)}_2^2}}{2(1-\gamma)} \\&+ \frac{\alpha}{\lambda^2(1-\gamma)}\expect{\norm{\nabla_{\theta}V(\theta_t)}_2^2} + \sqrt{\frac{1}{(1-\gamma)^3}\norm{\frac{\nu_{\pi^*}}{\nu_{\pi_{\theta_0}}}}_{\infty}}\sqrt{\Delta_{actor}} + \frac{C_{soft}\lambda}{1-\gamma}.\\
\end{split}
\end{align*}

Next we use the same argument as in eq (33) and Lemma 2 in Xu et al., 2020 to bound the second term.

\begin{align*}
\expect{\norm{u_t(w_t)-u^\lambda_{\theta_t}}_2^2} &\leq \frac{C}{B}+ \frac{108\expect{\norm{w_t-w^*_{\theta_t}}_2^2}}{\lambda^2} + \frac{216\Delta_{critic}}{\lambda^2}.
\end{align*}

where $C:=\frac{18}{\lambda^2}\frac{24(1+2R_w)^2[1+(\kappa-1)\xi]}{B(1-\xi)} + \frac{4}{\lambda^4(1-\gamma)^2}.\frac{8[1+(\kappa-1)\xi]}{(1-\xi)B}.$
Using this in the bound and using $\sqrt{a+b}\leq \sqrt{a}+\sqrt{b}$ for positive $a,b$ above, we have,

\begin{align*}
\begin{split}
& V({\pi^*})-\expect{V(\pi_{\theta_t})}\\
&\leq  \frac{\expect{\tt{D}(\theta_t)}-\expect{\tt{D}(\theta_{t+1})}}{(1-\gamma)\alpha} +\frac{2}{1-\gamma}\left( \sqrt{\frac{C}{B}}+ 11\sqrt{\frac{\expect{\norm{w_t-w^*_{\theta_t}}_2^2}}{\lambda^2}} + 15\sqrt{\frac{\Delta_{critic}}{\lambda^2}}  \right) \\&+ \frac{\alpha}{2(1-\gamma)}
\left({\frac{C}{B}}+ {108\frac{\expect{\norm{w_t-w^*_{\theta_t}}_2^2}}{\lambda^2}} + {216\frac{\Delta_{critic}}{\lambda^2}}  \right)
\\&+ \frac{\alpha}{\lambda^2(1-\gamma)}\expect{\norm{\nabla_{\theta}V(\theta_t)}_2^2} + \sqrt{\frac{1}{(1-\gamma)^3}\norm{\frac{\nu_{\pi^*}}{\nu_{\pi_{\theta_0}}}}_{\infty}}\sqrt{\Delta_{actor}} + \frac{C_{soft}\lambda}{1-\gamma}.
\end{split}
\end{align*}

Summing over all $t=0,1,\ldots,T-1$ and then dividing by $T$ we get,

\begin{align*}
\begin{split}
& \leq  \frac{{\tt{D}(\theta_0)}-\expect{\tt{D}(\theta_{T})}}{(1-\gamma)\alpha T} +\frac{2}{(1-\gamma)}\left( \sqrt{\frac{C}{B}} + 15\sqrt{\frac{\Delta_{critic}}{\lambda^2}}  \right) +\frac{22}{(1-\gamma)T}\sum_{t=0}^{T-1}\sqrt{\frac{\expect{\norm{w_t-w^*_{\theta_t}}_2^2}}{\lambda^2}} \\&+ \frac{\alpha}{2(1-\gamma)}
\left({\frac{C}{B}} + {216\frac{\Delta_{critic}}{\lambda^2}}  \right) + \frac{54\alpha}{(1-\gamma)T}\sum\limits_{t=0}^{T-1}{\frac{\expect{\norm{w_t-w^*_{\theta_t}}_2^2}}{\lambda^2}}
\\&+ \frac{\alpha}{\lambda^2(1-\gamma)T}\sum\limits_{t=0}^{T-1}\expect{\norm{\nabla_{\theta}V(\theta_t)}_2^2} + \sqrt{\frac{1}{(1-\gamma)^3}\norm{\frac{\nu_{\pi^*}}{\nu_{\pi_{\theta_0}}}}_{\infty}}\sqrt{\Delta_{actor}} + \frac{C_{soft}\lambda}{1-\gamma}.
\end{split}
\end{align*}

We now put the value of $\alpha \leq\frac{\lambda^2}{2\sqrt{M}L_V(1+\lambda)}$, we get,

\begin{align*}
\begin{split}
&\leq C_1\frac{\sqrt{M}}{T} + \frac{C_2}{\sqrt{B}} + C_3\sqrt{\Delta_{critic}} + \frac{C_4}{T}\sum_{t=0}^{T-1}\sqrt{\expect{\norm{w_t-w^*_{\theta_t}}_2^2}} \\
&+ \frac{C_5}{B} + C_6\sqrt{\Delta_{critic}} +  \frac{C_7}{T}\sum\limits_{t=0}^{T-1}\expect{\norm{w_t-w^*_{\theta_t}}_2^2} + \frac{C_8}{T}\sum\limits_{t=0}^{T-1}\expect{\norm{\nabla_{\theta}V(\theta_t)}_2^2} \\
&+ \sqrt{\frac{1}{(1-\gamma)^3}\norm{\frac{\nu_{\pi^*}}{\nu_{\pi_{\theta_0}}}}_{\infty}}\sqrt{\Delta_{actor}} + C_9\lambda.
\end{split}
\end{align*}

Letting $T=\mathcal{O}\left( \frac{\sqrt{M}}{(1-\gamma)^2\epsilon} \right)$, $B=\cO\left( \frac{1}{(1-\gamma)^2\epsilon^2} \right)$ then $\expect{\norm{\nabla_{\theta}V(\theta_t)}_2^2}\leq \epsilon^2$ and

\[V({\pi^*})-\frac{1}{T}\sum\limits_{t=0}^{T-1}\expect{V(\pi_{\theta_t})} \leq \epsilon + \cO\left(\sqrt{\frac{\Delta_{actor}}{(1-\gamma)^3} }\right) + \cO(\Delta_{critic}) + \cO(\lambda). \]

This leads to the total sample complexity as

\[(B+HT_c)T = \cO\left(\left( \frac{1}{(1-\gamma)^2\epsilon^2} + \frac{\sqrt{M}}{\epsilon^2}\log\frac{1}{\epsilon} \right)\frac{\sqrt{M}}{(1-\gamma)^2\epsilon}\right) = \cO\left(\frac{M}{(1-\gamma)^4\epsilon^3} \log\frac{1}{\epsilon}\right).\]

§ SIMULATION DETAILS

In this section we describe the details of the Sec. <ref>. Recall that since neither value functions nor value gradients are available in closed-form, we modify SoftMax PG (Algorithm <ref>) to make it generally implementable using a combination of (1) rollouts to estimate the value function of the current (improper) policy and (2) a stochastic approximation-based approach to estimate its value gradient.

The Softmax PG with Gradient Estimation or SPGE (Algorithm  <ref>), and the gradient estimation algorithm  <ref>, GradEst, are shown below.

Softmax PG with Gradient Estimation (SPGE)

[1]
Input: learning rate $\eta>0$, perturbation parameter $\alpha>0$, Initial state distribution $\mu$

Initialize each $\theta^1_m=1$, for all $m\in [M]$, $s_1\sim \mu$
$t=1$ to $T$
Choose controller $m_t\sim \pi_t$.
Play action $a_t \sim K_{m_t}(s_{t},:)$.

Observe $s_{t+1}\sim \tP(.|s_t,a_t)$.
${\widehat{\nabla_{\theta^t} V^{\pi_{\theta_t}}(\mu)}}= \text{\tt GradEst}({\theta_t},\alpha,\mu)$
$\theta^{t+1} = \theta^{t}+ \eta. \widehat{\nabla_{\theta^t} V^{\pi_{\theta_t}}(\mu)}$.

GradEst (subroutine for SPGE)

[1]
Input: Policy parameters $\theta$, parameter $\alpha>0$, Initial state distribution $\mu$.

$i=1$ to $\#\tt{runs}$
$u^i\sim Unif(\mathbb{S}^{M-1}).$
$\theta_\alpha = \theta+\alpha.u^i$
$\pi_\alpha = \softmax(\theta_\alpha)$
$l=1$ to $\#\tt{rollouts}$
Generate trajectory $(s_0,a_0,r_0,s_1,a_1,r_1,\ldots, s_{\tt{lt}},a_{\tt{lt}},r_{\tt{lt}})$ using the policy $\pi_\alpha:$ and $s_0 \sim \mu$.
$\tt{mr}(i) = \tt{mean}(\tt{reward})$
$\tt{GradValue} = \frac{1}{\#runs}\sum\limits_{i=1}^{\#\tt{runs}}{\tt{mr}}(i).u^i.\frac{M}{\alpha}.$
Return: $\tt{GradValue}$.

Next we report some extra simulations we performed under different environments.

§.§ State Dependent controllers – Chain MDP
We consider a linear chain MDP as shown in Figure <ref>. As evident from the figure, $\abs{\cS}=10$ and the learner has only two actions available, which are $\cA = \{\tt{left}, \tt{right}\}$. Hence the name `chain'. The numbers on the arrows represent the reward obtained with the transition. The initial state is $s_1$. We let $s_{100}$ as the terminal state. Let us define 2 base controllers, $K_1$ and $K_2$, as follows.

\begin{align*}
K_1(\tt{left}\given s_j) &=\begin{cases}
1, & j\in[9]\backslash \{5\}\\
0.1, & j = 5\\
0, & j=10.
\end{cases}
\end{align*}

\begin{align*}
K_2(\tt{left}\given s_j) &=\begin{cases}
1, & j\in[9]\backslash \{6\}\\
0.1, & j = 6\\
0, & j=10.
\end{cases}
\end{align*}

and obviously $K_i(\tt{right}|s_j) = 1-K_i(\tt{left}|s_j)$ for $i=1,2$.
An improper mixture of the two controllers, i.e., $(K_1+K_2)/2$ is the optimal in this case. We show that our policy gradient indeed converges to the `correct' combination, see Figure  <ref>.

A chain MDP with 10 states.

Softmax PG alg applied to the linear Chain MDP with various randomly chosen initial distribution. Plot shows probability of choosing controller $K_1$ averaged over $\#\tt{trials}$.

We here provide an elementary calculation of our claim that the mixture $K_{\tt{mix}}:=(K_1+K_2)/2$ is indeed better than applying $K_1$ or $K_2$ for all time. We first analyze the value function due to $K_i, i=1,2$ (which are the same due to symmetry of the problem and the probability values described).

\begin{align*}
V^{K_i}(s_1) &= \expect{\sum\limits_{t\geq0} \gamma^tr_t(a_t,s_t)}\\
&=0.1\times \gamma^9+0.1\times 0.9\times 0.1\times \gamma^{11} + 0.1\times 0.9\times 0.1\times0.9\times 0.1\times \gamma^{13} \ldots\\
&=0.1\times \gamma^9 \left(1+\left(0.1\times 0.9 \gamma^2\right)+ \left(0.1\times 0.9 \gamma^2\right)^2+\ldots \right)=\frac{0.1\times \gamma^9}{1-0.1\times0.9\times \gamma^2}.
\end{align*}

We will next analyze the value if a true mixture controller i.e., $K_{\tt{mix}}$ is applied to the above MDP. The analysis is a little more intricate than the above. We make use of the following key observations, which are elementary but crucial.

* Let $\tt{Paths}$ be the set of all sequence of states starting from $s_1$, which terminate at $s_{10}$ which can be generated under the policy $K_{\tt{mix}}$. Observe that

\begin{equation}
V^{K_{\tt{mix}}}(s_1) = \sum\limits_{\underline{p}\in \tt{Paths}}\gamma^{{\tt{length}}(\underline{p})}\prob{\underline{p}}.1.
\end{equation}

Recall that reward obtained from the transition $s_9\to s_{10}$ is 1.

* Number of distinct paths with exactly $n$ loops: $2^n$.

* Probability of each such distinct path with $n$ cycles:

\begin{align*}
&=\underbrace{(0.55\times 0.45)\times (0.55\times 0.45)\times \ldots (0.55\times 0.45)}_{n \,\tt{ times}}\times 0.55\times 0.55\times \gamma^{9+2n}\\
&=\left(0.55\right)^2\times \gamma^9\left(0.55\times 0.45\times \gamma^2 \right)^n.
\end{align*}

* Finally, we put everything together to get:

\begin{align*}
V^{K_{\tt{mix}}}(s_1) = &\sum\limits_{n=0}^{\infty} 2^n\times \left(0.55\right)^2 \times \gamma^9\times \left(0.55\times 0.45\times \gamma^2 \right)^n\\
&=\frac{\left(0.55\right)^2\times \gamma^9}{1-2\times 0.55\times0.45\times \gamma^2} > V^{K_i}(s_1).
\end{align*}

This shows that a mixture performs better than the constituent controllers. The plot shown in Fig.  <ref> shows the Softmax PG algorithm (even with estimated gradients and value functions) converges to a (0.5,0.5) mixture correctly.

§.§ Stationary Bernoulli Queues

[Arrival rate:$(\lambda_1,\lambda_2)=(0.49,0.49)$]
[Arrival rate:$(\lambda_1,\lambda_2)=(0.49,0.49)$]
[Arrival rate:$(\lambda_1,\lambda_2)=(0.3,0.4)$]
[(Estimated) Value functions for case with the two base policies and Longest Queue First (“LQF") ]
[Case with 3 experts: Always Queue 1, Always Queue 2 and LQF.]
Softmax policy gradient algorithm applies show convergence to the best mixture policy.

We study two different settings (1) where in the first case the optimal policy is a strict improper combination of the available controllers and (2) where it is at a corner point, i.e., one of the available controllers itself is optimal. Our simulations show that in both the cases, PG converges to the correct controller distribution.

Recall the example that we discussed in Sec. <ref>. We consider the case with Bernoulli arrivals with rates $\boldsymbol{\lambda}=[\lambda_1,\lambda_2]$ and are given two base/atomic controllers $\{K_1,K_2\}$, where controller $K_i$ serves Queue $i$ with probability $1$, $i=1,2$. As can be seen in Fig. <ref> when $\boldsymbol{\lambda}=[0.49,0.49]$ (equal arrival rates), GradEst converges to an improper mixture policy that serves each queue with probability $[0.5,0.5]$. Note that this strategy will also stabilize the system whereas both the base controllers lead to instability (the queue length of the unserved queue would obviously increase without bound). Figure <ref>, shows that with unequal arrival rates too, GradEst quickly converges to the best policy.

Fig. <ref> shows the evolution of the value function of GradEst (in blue) compared with those of the base controllers (red) and the Longest Queue First policy (LQF) which, as the name suggests, always serves the longest queue in the system (black). LQF, like any policy that always serves a nonempty queue in the system whenever there is one[Tie-breaking rule is irrelevant.], is known to be optimal in the sense of delay minimization for this system [Mohan et al., 2016]. See Sec. <ref> in the Appendix for more details about this experiment.

Finally, Fig. <ref> shows the result of the second experimental setting with three base controllers, one of which is delay optimal. The first two are $K_1,K_2$ as before and the third controller, $K_3$, is LQF. Notice that $K_1,K_2$ are both queue length-agnostic, meaning they could attempt to serve empty queues as well. LQF, on the other hand, always and only serves nonempty queues. Hence, in this case the optimal policy is attained at one of the corner points, i.e., $[0,0,1]$. The plot shows the PG algorithm converging to the correct point on the simplex.

Here, we justify the value of the two policies which always follow one fixed queue, that is plotted as straight line in Figure <ref>. Let us find the value of the policy which always serves queue 1. The calculation for the other expert (serving queue 2 only) is similar. Let $q_i(t)$ denote the length of queue $i$ at time $t$. We note that since the expert (policy) always recommends to serve one of the queue, the expected cost suffered in any round $t$ is $c_t=q_1(t)+q_2(t) = 0 + t.\lambda_2$. Let us start with empty queues at $t=0$.

\begin{align*}
V^{Expert 1}(\mathbf{\underline{0}}) &= \expect{\sum\limits_{t=0}^T \gamma^tc_t\given Expert 1}\\
&= \sum\limits_{t=0}^T \gamma^t. t. \lambda_2\\
\end{align*}

With the values, $\gamma=0.9$ and $\lambda_2=0.49$, we get $V^{Expert 1}(\mathbf{\underline{0}})\leq 44$, which is in good agreement with the bound shown in the figure.

§.§ Details of Path (Interference) Graph Networks

[A basic path-graph interference system with $N=4$ communication links.]

[The associated conflict (interference) graph is a path-graph.]

An example of a path graph network. The interference constraints are such that physically adjacent queues cannot be served simultaneously.

Consider a system of parallel transmitter-receiver pairs as shown in Figure  <ref>. Due to the physical arrangement of the Tx-Rx pairs, no two adjacent systems can be served simultaneously because of interference. This type of communication system is commonly referred to as a path graph network [Mohan et al., 2020]. Figure  <ref> shows the corresponding conflict graph. Each Tx-Rx pair can be thought of as a queue, and the edges between them represent that the two connecting queues, cannot be served simultaneously. On the other hand, the sets of queues which can be served simultaneously are called independent sets in the queuing theory literature. In the figure above, the independent sets are $\{\emptyset,\{1\}, \{2\}, \{3\}, \{4\}, \{1,3\}, \{2,4\}, \{1,4\} \}$.

Finally, in Table <ref>, we report the mean delay values of the 5 base controllers we used in our simulation Fig. <ref>, Sec.<ref>. We see the controller $K_2$ which was chosen to be MER, indeed has the lowest cost associated, and as shown in Fig.  <ref>, our Softmax PG algorithm (with estimated value functions and gradients) converges to it.

Mean Packet Delay Values of Path Graph Network Simulation.

Controller     Mean delay (# time slots) over 200 trials     Standard deviation

$K_1(MW)$     22.11      0.63

${\color{blue}K_2(MER)}$     20.96      0.65

$K_3(\{1,3\})$     80.10      0.92

$K_4(\{2,4\})$     80.22     0.90

$K_5(\{1,4\})$     80.13      0.91

§.§ Cartpole Experiments

We investigate further the example in our simulation in which the two constituent controllers are $K_{opt}+\Delta$ and $K_{opt}-\Delta$. We use OpenAI gym to simulate this situation. In the Figure  <ref>, it was shown our Softmax PG algorithm (with estimated values and gradients) converged to a improper mixture of the two controllers, i.e., $\approx(0.53,0.47)$. Let $K_{\tt{conv}}$ be defined as the (randomized) controller which chooses $K_1$ with probability 0.53, and $K_2$ with probability 0.47. Recall from Sec. <ref> that this control law converts the linearized cartpole into an Ergodic Parameter Linear System (EPLS).  In Table <ref> we report the average number of rounds the pendulum stays upright when different controllers are applied for all time, over trajectories of length 500 rounds. The third column displays an interesting feature of our algorithm. Over 100 trials, the base controllers do not stabilize the pendulum for a relatively large number of trials, however, $K_{\tt{conv}}$ successfully does so most of the times.
A table showing the number of rounds the constituent controllers manage to keep the cartpole upright.

Controller     Mean number of rounds
before the pendulum falls $\land$ 500     $\#$ Trials out of 100 in which
the pendulum falls before 500 rounds

$K_1(K_{opt}+\Delta)$     403      38

${K_2(K_{opt}-\Delta)}$     355      46

${\color{blue}K_{\tt{conv}}}$     465      8

We mention here that if one follows $K^*$, which is the optimum controller matrix one obtains by solving the standard Discrete-time Algebraic Riccatti Equation (DARE) [Bertsekas, 2011], the pole does not fall over 100 trials. However, as indicated in Sec.<ref>, constructing the optimum controller for this system from scratch requires exponential, in the number of state dimension, sample complexity [Chen & Hazan, 2020]. On the other hand $K_{\tt{conv}}$ performs very close to the optimum, while being sample efficient.

Choice of hyperparameters. In the simulations, we set learning rate to be $10^{-4}$, $\#\tt{runs}=10,\#\tt{rollouts}=10, \tt{lt}= 30$, discount factor $\gamma=0.9$ and $\alpha=1/\sqrt{\#\tt{runs}}$. All the simulations have been run for 20 trials and the results shown are averaged over them. We capped the queue sizes at 1000.

§.§ Some extra simulations for natural-actor-critic based improper learner NACIL

* First we show a queuing theory where we have 2 queues to be served and we have two base controllers similar to as we discussed in the Sec <ref>. However,  here we have two different arrival rates for the two queues $(\lambda_1,\lambda_2)\equiv (0.4,0.3)$, i.e., the arrival rates are unequal. We plot in Fig. <ref> the probability of choosing the two different controllers. We see that ACIL converges to the “correct" mixture of the base controllers.

* Next, we show a simulation on the setting in Sec. <ref>, which we called a Chain MDP. We recall that this setting consists of two base controllers $K_1$ and $K_2$, however a $(1/2,1/2)$ mixture of the two controllers was shown (analytically) to perform better than each individual ones. As the plot in Fig. <ref> shows NACIL identifies the correct combination and follows it.

Choice of hyperparameters. For the queuing theoretic simulations of Algorithm <ref> ACIL, we choose $\alpha=10^{-4}$, $\beta=10^{-3}$. We choose the identity mapping $\phi(s)\equiv s$, where $s$ is the current state of the system which is a $N-$length vector, which consists of the $i^{th}$ queue length at the $i^{th}$ position. $\lambda$ was chosen to be $0.1$. The other parameters are chosen as $B=50$, $H=30$ and $T_c=20$. We choose a buffer of size 1000 to keep the states bounded, i.e., if a queue exceeds a size 1000, those arrivals are ignored and queue length is not increased. This is used to normalize the $\norm{\phi(s)}_2$ across time.

NACIL alg applied to the a queuing system with two queues, having arrival rates $(\lambda_1,\lambda_2)\equiv(0.4,0.3)$. Plot shows probability of choosing controllers $K_1$ and $K_2$ averaged over 20 trials.

NACIL alg applied to the linear Chain MDP with various randomly chosen initial distribution. Plot shows probability of choosing controller $K_1$ averaged over 20 trials.

§ ADDITIONAL COMMENTS

* Comment on the `simple' experimental settings. The motivating examples may seem “simple" and trainable from scratch with respect to progress in the field of RL. However, our main point is that there are situations where, for example, one may have trained controllers for a range of environments in simulation. However, the real life environment may differ from the simulated ones. We demonstrate that exploiting such basic pre-learnt controllers via our approach can help in generating a better (meta) controller for a new, unseen environment, instead of learning a new controller for the new environment from scratch.

* On characterizing the performance of the optimal mixture policy. As correctly noticed by the reviewer, the inverted pendulum experiment showed that the optimal mixture policy can vastly outperform the component controllers. Currently, however, we do not provide any theoretical guarantees regarding this, since this depends on the structure of the policy space and the underlying MDP, which is very challenging. We hope to explore this task in our future work.

§ DISCUSSION

We have considered the problem of using a menu of baseline controllers and combining them using improper probabilistic mixtures to form a superior controller. In many relevant MDP learning settings, we saw that this is indeed possible, and the policy gradient and actor-critic based analyses indicate that this approach may be widely applicable.

This work opens up a plethora of avenues. One can consider a richer class of mixtures that can look at the current state and mix accordingly. For example, an attention model can be used to choose which controller to use, or other state-dependent models can be relevant.
Another example is to artificially force switching across controllers to occur less frequently than in every round. The can help create momentum and allow the controlled process to 'mix' better, when using complex controllers.

A few caveats are in order regarding the potential societal impact and consequences of this work. As such, this paper offers a way of combining or `blending' a given class of decision-making entities in the hope of producing a `better' one. In this process, the definitions of what constitutes `optimal' or `expected' behavior from a policy are likely to be subjective, and may encode biases and attitudes of the system designer(s). More importantly, it is possible that the base policy class (or some elements of it) have undesirable properties to begin with (e.g., bias or insensitivity), which could get amplified in the improper learning process as an unintended outcome. We sound ample caution to practitioners who contemplate adopting this method.

Finally, in the present setting, the base controllers are fixed. It would be interesting to consider adding adaptive, or 'learning' controllers as well as the fixed ones. Including the base controllers can provide baseline performance below which the performance of the learning controllers would not drop.