$\displaystyle\quad+\left(\frac{2-\varrho}{\varrho}\right)\left(\mathbb{E}[\left\|\kappa^{*}_{t+1}-\kappa^{*}_{t}\right\|_{2}^{2}|\mathcal{F}_{t}]+\mathbb{E}[\left\|\xi^{*}_{t+1}-\xi^{*}_{t}\right\|_{2}^{2}|\mathcal{F}_{t}]+\mathbb{E}[\left\|\zeta^{*}_{t+1}-\zeta^{*}_{t}\right\|_{2}^{2}|\mathcal{F}_{t}]\right)$
$\displaystyle\overset{(i)}{\leq}\left(1-\frac{1}{2}\varrho\right)\Delta_{t}+\frac{2}{\varrho}\left(\mathbb{E}[\left\|\kappa^{*}_{t+1}-\kappa^{*}_{t}\right\|_{2}^{2}|\mathcal{F}_{t}]+\mathbb{E}[\left\|\xi^{*}_{t+1}-\xi^{*}_{t}\right\|_{2}^{2}|\mathcal{F}_{t}]+\mathbb{E}[\left\|\zeta^{*}_{t+1}-\zeta^{*}_{t}\right\|_{2}^{2}|\mathcal{F}_{t}]\right)+\frac{C_{5}}{(1-\varrho)N}$
$\displaystyle\leq\left(1-\frac{1}{2}\varrho\right)\Delta_{t}+\frac{2}{\varrho}(L^{2}_{\kappa}+L^{2}_{\xi}+L^{2}_{\zeta})\mathbb{E}[\left\|w_{t+1}-w_{t}\right\|_{2}^{2}|\mathcal{F}_{t}]+\frac{C_{5}}{(1-\varrho)N}.$
(79)

where $(i)$ follows from eq. 78. ∎

##  Appendix D Proof of Theorem 2

In order to prove the convergence for the DR-Off-PAC algorithm, we first
introduce the following Lipschitz property of $J(w)$, which was established in
(Xu et al., 2020b).

######  Proposition 1.

Suppose Assumptions 2 and 3 hold. For any $w,w^{\prime}\in\mathbb{R}^{d}$, we
have $\left\|\nabla_{w}J(w)-\nabla_{w}J(w^{\prime})\right\|_{2}\leq
L_{J}\left\|w-w^{\prime}\right\|_{2},\quad\text{for all
}\;w,w^{\prime}\in\mathbb{R}^{d}$, where $L_{J}=\Theta(1/(1-\gamma))$.

The Lipschitz property established in Proposition 1 is important to establish
the local convergence of the gradient-based algorithm.

To proceed the proof of Theorem 2, consider the update in Algorithm 1. For
brevity, we define
$G_{\text{DR}}(w_{t},\mathcal{M}_{t})=\frac{1}{N}\sum_{i}G^{i}_{\text{DR}}(w_{t})$,
where $\mathcal{M}_{t}$ represents the sample set
$\mathcal{B}_{t}\cup\mathcal{B}_{t,0}$. Following the $L_{J}$-Lipschitz
property of objective $J(w)$, we have

$\displaystyle J(w_{t+1})$ $\displaystyle\geq
J(w_{t})+\langle\nabla_{w}J(w_{t}),w_{t+1}-w_{t}\rangle-\frac{L_{J}}{2}\left\|w_{t+1}-w_{t}\right\|_{2}^{2}$
$\displaystyle=J(w_{t})+\alpha\langle\nabla_{w}J(w_{t}),G_{\text{DR}}(w_{t},\mathcal{M}_{t})-\nabla_{w}J(w_{t})+\nabla_{w}J(w_{t})\rangle-\frac{L_{J}\alpha^{2}}{2}\left\|G_{\text{DR}}(w_{t},\mathcal{M}_{t})\right\|_{2}^{2}$
$\displaystyle=J(w_{t})+\alpha\left\|\nabla_{w}J(w_{t})\right\|_{2}^{2}+\alpha\langle\nabla_{w}J(w_{t}),G_{\text{DR}}(w_{t},\mathcal{M}_{t})-\nabla_{w}J(w_{t})\rangle$
$\displaystyle\quad-\frac{L_{J}\alpha^{2}}{2}\left\|G_{\text{DR}}(w_{t},\mathcal{M}_{t})-\nabla_{w}J(w_{t})+\nabla_{w}J(w_{t})\right\|_{2}^{2}$
$\displaystyle\overset{(i)}{\geq}J(w_{t})+\Big{(}\frac{1}{2}\alpha-
L_{J}\alpha^{2}\Big{)}\left\|\nabla_{w}J(w_{t})\right\|_{2}^{2}-\Big{(}\frac{1}{2}\alpha+L_{J}\alpha^{2}\Big{)}\left\|G_{\text{DR}}(w_{t},\mathcal{M}_{t})-\nabla_{w}J(w_{t})\right\|_{2}^{2},$
(80)

where $(i)$ follows because

$\displaystyle\langle\nabla_{w}J(w_{t}),G_{\text{DR}}(w_{t},\mathcal{M}_{t})-\nabla_{w}J(w_{t})\rangle\geq-\frac{1}{2}\left\|\nabla_{w}J(w_{t})\right\|_{2}^{2}-\frac{1}{2}\left\|G_{\text{DR}}(w_{t},\mathcal{M}_{t})-\nabla_{w}J(w_{t})\right\|_{2}^{2},$

and

$\displaystyle\left\|G_{\text{DR}}(w_{t},\mathcal{M}_{t})-\nabla_{w}J(w_{t})+\nabla_{w}J(w_{t})\right\|_{2}^{2}\leq
2\left\|G_{\text{DR}}(w_{t},\mathcal{M}_{t})-\nabla_{w}J(w_{t})\right\|_{2}^{2}+2\left\|\nabla_{w}J(w_{t})\right\|_{2}^{2}.$

Taking the expectation on both sides of eq. 80 conditioned on
$\mathcal{F}_{t}$ and rearranging eq. 80 yield

$\displaystyle\Big{(}\frac{1}{2}\alpha$ $\displaystyle-
L_{J}\alpha^{2}\Big{)}\mathbb{E}[\left\|\nabla_{w}J(w_{t})\right\|_{2}^{2}|\mathcal{F}_{t}]$
$\displaystyle\leq\mathbb{E}[J(w_{t+1})|\mathcal{F}_{t}]-J(w_{t})+\Big{(}\frac{1}{2}\alpha+L_{J}\alpha^{2}\Big{)}\mathbb{E}[\left\|G_{\text{DR}}(w_{t},\mathcal{M}_{t})-\nabla_{w}J(w_{t})\right\|_{2}^{2}|\mathcal{F}_{t}].$
(81)

Then, we upper-bound the term
$\mathbb{E}[\left\|G_{\text{DR}}(w_{t},\mathcal{M}_{t})-\nabla_{w}J(w_{t})\right\|_{2}^{2}|\mathcal{F}_{t}]$
as follows. By definition, we have

$\displaystyle\left\|G_{\text{DR}}(w_{t},\mathcal{M}_{t})-\nabla_{w}J(w_{t})\right\|_{2}^{2}$
$\displaystyle=\left\|G_{\text{DR}}(w_{t},\theta_{q,t},\theta_{\rho,t},\theta_{\psi,t},\theta_{d_{q},t},\mathcal{M}_{t})-\nabla_{w}J(w_{t})\right\|_{2}^{2}$
$\displaystyle\leq
6\left\|G_{\text{DR}}(w_{t},\theta_{q,t},\theta_{\rho,t},\theta_{\psi,t},\theta_{d_{q},t},\mathcal{M}_{t})-G_{\text{DR}}(w_{t},\theta_{q,t},\theta_{\rho,t},\theta_{\psi,t},\theta^{*}_{d_{q},t},\mathcal{M}_{t})\right\|_{2}^{2}$
$\displaystyle\quad+6\left\|G_{\text{DR}}(w_{t},\theta_{q,t},\theta_{\rho,t},\theta_{\psi,t},\theta^{*}_{d_{q},t},\mathcal{M}_{t})-G_{\text{DR}}(w_{t},\theta_{q,t},\theta_{\rho,t},\theta^{*}_{\psi,t},\theta^{*}_{d_{q},t},\mathcal{M}_{t})\right\|_{2}^{2}$
$\displaystyle\quad+6\left\|G_{\text{DR}}(w_{t},\theta_{q,t},\theta_{\rho,t},\theta^{*}_{\psi,t},\theta^{*}_{d_{q},t},\mathcal{M}_{t})-G_{\text{DR}}(w_{t},\theta^{*}_{q,t},\theta_{\rho,t},\theta^{*}_{\psi,t},\theta^{*}_{d_{q},t},\mathcal{M}_{t})\right\|_{2}^{2}$
$\displaystyle\quad+6\left\|G_{\text{DR}}(w_{t},\theta^{*}_{q,t},\theta_{\rho,t},\theta^{*}_{\psi,t},\theta^{*}_{d_{q},t},\mathcal{M}_{t})-G_{\text{DR}}(w_{t},\theta^{*}_{q,t},\theta^{*}_{\rho,t},\theta^{*}_{\psi,t},\theta^{*}_{d_{q},t},\mathcal{M}_{t})\right\|_{2}^{2}$
$\displaystyle\quad+6\left\|G_{\text{DR}}(w_{t},\theta^{*}_{q,t},\theta^{*}_{\rho,t},\theta^{*}_{\psi,t},\theta^{*}_{d_{q},t},\mathcal{M}_{t})-\mathbb{E}[G^{i}_{\text{DR}}(w_{t},\theta^{*}_{q,t},\theta^{*}_{\rho,t},\theta^{*}_{\psi,t},\theta^{*}_{d_{q},t})]\right\|_{2}^{2}$
$\displaystyle\quad+6\left\|\mathbb{E}[G^{i}_{\text{DR}}(w_{t},\theta^{*}_{q,t},\theta^{*}_{\rho,t},\theta^{*}_{\psi,t},\theta^{*}_{d_{q},t})]-\nabla_{w}J(w_{t})\right\|_{2}^{2}$
$\displaystyle\leq\frac{6}{N}\sum_{i}\left\|G^{i}_{\text{DR}}(w_{t},\theta_{q,t},\theta_{\rho,t},\theta_{\psi,t},\theta_{d_{q},t})-G^{i}_{\text{DR}}(w_{t},\theta_{q,t},\theta_{\rho,t},\theta_{\psi,t},\theta^{*}_{d_{q},t})\right\|_{2}^{2}$
$\displaystyle\quad+\frac{6}{N}\sum_{i}\left\|G^{i}_{\text{DR}}(w_{t},\theta_{q,t},\theta_{\rho,t},\theta_{\psi,t},\theta^{*}_{d_{q},t})-G^{i}_{\text{DR}}(w_{t},\theta_{q,t},\theta_{\rho,t},\theta^{*}_{\psi,t},\theta^{*}_{d_{q},t}\right\|_{2}^{2}$
$\displaystyle\quad+\frac{6}{N}\sum_{i}\left\|G^{i}_{\text{DR}}(w_{t},\theta_{q,t},\theta_{\rho,t},\theta^{*}_{\psi,t},\theta^{*}_{d_{q},t})-G^{i}_{\text{DR}}(w_{t},\theta^{*}_{q,t},\theta_{\rho,t},\theta^{*}_{\psi,t},\theta^{*}_{d_{q},t})\right\|_{2}^{2}$
$\displaystyle\quad+\frac{6}{N}\sum_{i}\left\|G^{i}_{\text{DR}}(w_{t},\theta^{*}_{q,t},\theta_{\rho,t},\theta^{*}_{\psi,t},\theta^{*}_{d_{q},t})-G^{i}_{\text{DR}}(w_{t},\theta^{*}_{q,t},\theta^{*}_{\rho,t},\theta^{*}_{\psi,t},\theta^{*}_{d_{q},t})\right\|_{2}^{2}$
$\displaystyle\quad+6\left\|G_{\text{DR}}(w_{t},\theta^{*}_{q,t},\theta^{*}_{\rho,t},\theta^{*}_{\psi,t},\theta^{*}_{d_{q},t},\mathcal{M}_{t})-\mathbb{E}[G^{i}_{\text{DR}}(w_{t},\theta^{*}_{q,t},\theta^{*}_{\rho,t},\theta^{*}_{\psi,t},\theta^{*}_{d_{q},t})]\right\|_{2}^{2}$
$\displaystyle\quad+6\left\|\mathbb{E}[G^{i}_{\text{DR}}(w_{t},\theta^{*}_{q,t},\theta^{*}_{\rho,t},\theta^{*}_{\psi,t},\theta^{*}_{d_{q},t})]-\nabla_{w}J(w_{t})\right\|_{2}^{2}.$
(82)

We next bound each term in eq. 82. For
$\left\|G^{i}_{\text{DR}}(w_{t},\theta_{q,t},\theta_{\rho,t},\theta_{\psi,t},\theta_{d_{q},t})-G^{i}_{\text{DR}}(w_{t},\theta_{q,t},\theta_{\rho,t},\theta_{\psi,t},\theta^{*}_{d_{q},t})\right\|_{2}$,
we proceed as follows:

$\displaystyle\left\|G^{i}_{\text{DR}}(w_{t},\theta_{q,t},\theta_{\rho,t},\theta_{\psi,t},\theta_{d_{q},t})-G^{i}_{\text{DR}}(w_{t},\theta_{q,t},\theta_{\rho,t},\theta_{\psi,t},\theta^{*}_{d_{q},t})\right\|_{2}$
$\displaystyle\leq(1-\gamma)\left\|\mathbb{E}_{\pi_{w_{t}}}\left[x(s_{0,i},a_{0,i})\right]^{\top}(\theta_{d_{q},t}-\theta^{*}_{d_{q},t})\right\|_{2}+\left\|\hat{\rho}_{\pi_{w_{t}}}(s_{i},a_{i})x(s_{i},a_{i})(\theta^{*}_{d_{q},t}-\theta_{d_{q},t})\right\|_{2}$
$\displaystyle\quad+\gamma\left\|\hat{\rho}_{\pi_{w_{t}}}(s_{i},a_{i})\mathbb{E}_{\pi_{w_{t}}}[x(s^{\prime}_{i},a^{\prime}_{i})]^{\top}(\theta_{d_{q},t}-\theta^{*}_{d_{q},t})\right\|_{2}$
$\displaystyle\leq\left(1+2R_{\rho}C_{\phi}\right)C_{x}\left\|\theta^{*}_{d_{q},t}-\theta_{d_{q},t}\right\|_{2}$
$\displaystyle=C_{6}\left\|\theta^{*}_{d_{q},t}-\theta_{d_{q},t}\right\|_{2},$
(83)

where $C_{6}=\left(1+2R_{\rho}C_{\phi}\right)$.

For
$\left\|G^{i}_{\text{DR}}(w_{t},\theta_{q,t},\theta_{\rho,t},\theta_{\psi,t},\theta^{*}_{d_{q},t})-G^{i}_{\text{DR}}(w_{t},\theta_{q,t},\theta_{\rho,t},\theta^{*}_{\psi,t},\theta^{*}_{d_{q},t}\right\|_{2}$,
we proceed as follows

$\displaystyle\left\|G^{i}_{\text{DR}}(w_{t},\theta_{q,t},\theta_{\rho,t},\theta_{\psi,t},\theta^{*}_{d_{q},t})-G^{i}_{\text{DR}}(w_{t},\theta_{q,t},\theta_{\rho,t},\theta^{*}_{\psi,t},\theta^{*}_{d_{q},t}\right\|_{2}$
$\displaystyle\leq\left\|\hat{\rho}_{\pi_{w_{t}}}(s_{i},a_{i})\varphi(s_{i},a_{i})^{\top}(\theta_{\psi,t}-\theta^{*}_{\psi,t})\left(r(s_{i},a_{i},s^{\prime}_{i})+\hat{Q}_{\pi_{w_{t}}}(s_{i},a_{i})-\gamma\mathbb{E}_{\pi_{w_{t}}}[\hat{Q}_{\pi_{w_{t}}}(s^{\prime}_{i},a^{\prime}_{i})]\right)\right\|_{2}$
$\displaystyle\leq
R_{\rho}C_{\varphi}(r_{\max}+2R_{q}C_{\phi})\left\|\theta_{\psi,t}-\theta^{*}_{\psi,t}\right\|_{2}$
$\displaystyle=C_{7}\left\|\theta_{\psi,t}-\theta^{*}_{\psi,t}\right\|_{2},$
(84)

where $C_{7}=R_{\rho}C_{\varphi}(r_{\max}+2R_{q}C_{\phi})$.

For
$\left\|G^{i}_{\text{DR}}(w_{t},\theta_{q,t},\theta_{\rho,t},\theta^{*}_{\psi,t},\theta^{*}_{d_{q},t})-G^{i}_{\text{DR}}(w_{t},\theta^{*}_{q,t},\theta_{\rho,t},\theta^{*}_{\psi,t},\theta^{*}_{d_{q},t})\right\|_{2}$,
we proceed as follows

$\displaystyle\left\|G^{i}_{\text{DR}}(w_{t},\theta_{q,t},\theta_{\rho,t},\theta^{*}_{\psi,t},\theta^{*}_{d_{q},t})-G^{i}_{\text{DR}}(w_{t},\theta^{*}_{q,t},\theta_{\rho,t},\theta^{*}_{\psi,t},\theta^{*}_{d_{q},t})\right\|_{2}$
$\displaystyle\leq(1-\gamma)\left\|\mathbb{E}_{\pi_{w_{t}}}\left[\phi(s_{0,i},a_{0,i})^{\top}(\theta_{q,t}-\theta^{*}_{q,t})\nabla_{w}\log\pi_{w_{t}}(s_{0,i},a_{0,i})\right]\right\|_{2}$
$\displaystyle\quad+\left\|\hat{\rho}_{\pi_{w_{t}}}(s_{i},a_{i})\varphi(s_{i},a_{i})^{\top}\theta^{*}_{\psi,t}\phi(s_{i},a_{i})^{\top}(\theta_{q,t}-\theta^{*}_{q,t})\right\|_{2}$
$\displaystyle\quad+\gamma\left\|\hat{\rho}_{\pi_{w_{t}}}(s_{i},a_{i})\varphi(s_{i},a_{i})^{\top}\theta^{*}_{\psi,t}\mathbb{E}_{\pi_{w_{t}}}[\phi(s^{\prime}_{i},a^{\prime}_{i})]^{\top}(\theta_{q,t}-\theta^{*}_{q,t})\right\|_{2}$
$\displaystyle\leq\left[(1-\gamma)C_{\phi}C_{sc}+(1+\gamma)R_{\rho}C^{2}_{\phi}C_{\varphi}R_{\psi}\right]\left\|\theta_{q,t}-\theta^{*}_{q,t}\right\|_{2}$
$\displaystyle=C_{8}\left\|\theta_{q,t}-\theta^{*}_{q,t}\right\|_{2},$ (85)

where
$C_{8}=(1-\gamma)C_{\phi}C_{sc}+(1+\gamma)R_{\rho}C^{2}_{\phi}C_{\varphi}R_{\psi}$.

For
$\left\|G^{i}_{\text{DR}}(w_{t},\theta^{*}_{q,t},\theta_{\rho,t},\theta^{*}_{\psi,t},\theta^{*}_{d_{q},t})-G^{i}_{\text{DR}}(w_{t},\theta^{*}_{q,t},\theta^{*}_{\rho,t},\theta^{*}_{\psi,t},\theta^{*}_{d_{q},t})\right\|_{2}$,
we proceed as follows

$\displaystyle\left\|G^{i}_{\text{DR}}(w_{t},\theta^{*}_{q,t},\theta_{\rho,t},\theta^{*}_{\psi,t},\theta^{*}_{d_{q},t})-G^{i}_{\text{DR}}(w_{t},\theta^{*}_{q,t},\theta^{*}_{\rho,t},\theta^{*}_{\psi,t},\theta^{*}_{d_{q},t})\right\|_{2}$
$\displaystyle\leq\left\|\phi(s_{i},a_{i})^{\top}(\theta_{\rho,t}-\theta^{*}_{\rho,t})\varphi(s_{i},a_{i})^{\top}\theta^{*}_{\psi,t}\left(r(s_{i},a_{i},s^{\prime}_{i})-\phi(s_{i},a_{i})^{\top}\theta^{*}_{q,t}+\gamma\mathbb{E}[\phi(s^{\prime}_{i},a^{\prime}_{i})]^{\top}\theta^{*}_{q,t}\right)\right\|_{2}$
$\displaystyle\quad+\left\|\phi(s_{i},a_{i})^{\top}(\theta_{\rho,t}-\theta^{*}_{\rho,t})\left(-x(s_{i},a_{i})^{\top}\theta^{*}_{d_{q},t}+\gamma\mathbb{E}_{\pi_{w_{t}}}[\phi(s^{\prime}_{i},a^{\prime}_{i})^{\top}\theta^{*}_{q,t}\nabla_{w}\log\pi_{w_{t}}(s^{\prime}_{i},a^{\prime}_{i})+x(s^{\prime}_{i},a^{\prime}_{i})^{\top}\theta^{*}_{d_{q},t}]\right)\right\|_{2}$
$\displaystyle\leq\left[C_{\phi}C_{\varphi}R_{\psi}(r_{\max}+(1+\gamma)C_{\phi}R_{q})+C_{\phi}(C_{x}R_{d_{q}}+\gamma(C_{\phi}R_{q}C_{sc}+C_{x}R_{d_{q}}))\right]\left\|\theta_{\rho,t}-\theta^{*}_{\rho,t}\right\|_{2}$
$\displaystyle=C_{9}\left\|\theta_{\rho,t}-\theta^{*}_{\rho,t}\right\|_{2},$
(86)

where
$C_{9}=C_{\phi}C_{\varphi}R_{\psi}(r_{\max}+(1+\gamma)C_{\phi}R_{q})+C_{\phi}(C_{x}R_{d_{q}}+\gamma(C_{\phi}R_{q}C_{sc}+C_{x}R_{d_{q}}))$.

For
$\left\|G_{\text{DR}}(w_{t},\theta^{*}_{q,t},\theta^{*}_{\rho,t},\theta^{*}_{\psi,t},\theta^{*}_{d_{q},t},\mathcal{M}_{t})-\mathbb{E}[G^{i}_{\text{DR}}(w_{t},\theta^{*}_{q,t},\theta^{*}_{\rho,t},\theta^{*}_{\psi,t},\theta^{*}_{d_{q},t})]\right\|_{2}^{2}$,
note that for all $i$, we have

$\displaystyle\left\|G^{i}_{\text{DR}}(w_{t},\theta^{*}_{q,t},\theta^{*}_{\rho,t},\theta^{*}_{\psi,t},\theta^{*}_{d_{q},t})\right\|_{2}$
$\displaystyle\leq(1-\gamma)\left\|\mathbb{E}_{\pi_{w}}[\phi_{0,i}^{\top}\theta^{*}_{q,t}\nabla_{w}\log\pi_{w}(s_{0,i},a_{0,i})+x_{0,i}^{\top}\theta^{*}_{d_{q},t}]\right\|_{2}+\left\|\psi_{i}^{\top}\theta^{*}_{\psi,t}\left(r(s_{i},a_{i},s^{\prime}_{i})-\phi_{i}^{\top}\theta^{*}_{q,t}+\gamma\mathbb{E}_{\pi_{w_{t}}}[\phi^{\prime\top}_{i}\theta^{*}_{q,t}]\right)\right\|_{2}$
$\displaystyle\quad+\left\|\phi_{i}^{\top}\theta^{*}_{\rho,t}(-x_{i}^{\top}\theta^{*}_{d_{q},t}+\gamma\mathbb{E}_{\pi_{w}}[\phi_{i}^{\top}\theta^{*}_{q,t}\nabla_{w}\log\pi_{w}(s_{t,i},a_{t,i})+x_{i}^{\top}\theta^{*}_{d_{q},t}])\right\|_{2}$
$\displaystyle\leq(1-\gamma)(C_{\phi}R_{q}C_{sc}+C_{x}R_{d_{q}})+C_{\psi}R_{\psi}(r_{\max}+(1+\gamma)C_{\phi}R_{q})+C_{\phi}R_{\rho}(C_{x}R_{d_{q}}+\gamma
C_{\phi}R_{q}C_{sc}+\gamma C_{x}R_{d-q}).$

Let
$C_{10}=(1-\gamma)(C_{\phi}R_{q}C_{sc}+C_{x}R_{d_{q}})+C_{\psi}R_{\psi}(r_{\max}+(1+\gamma)C_{\phi}R_{q})+C_{\phi}R_{\rho}(C_{x}R_{d_{q}}+\gamma
C_{\phi}R_{q}C_{sc}+\gamma C_{x}R_{d-q})$. Then following the steps similar to
those in eq. 40 and eq. 41, we obtain

$\displaystyle\mathbb{E}\left[\left\|G_{\text{DR}}(w_{t},\theta^{*}_{q,t},\theta^{*}_{\rho,t},\theta^{*}_{\psi,t},\theta^{*}_{d_{q},t},\mathcal{M}_{t})-\mathbb{E}[G^{i}_{\text{DR}}(w_{t},\theta^{*}_{q,t},\theta^{*}_{\rho,t},\theta^{*}_{\psi,t},\theta^{*}_{d_{q},t})]\right\|_{2}^{2}\Big{|}\mathcal{F}_{t}\right]\leq\frac{4C^{2}_{10}}{N}.$
(87)

Finally, consider the term
$\left\|\mathbb{E}[G^{i}_{\text{DR}}(w_{t},\theta^{*}_{q,t},\theta^{*}_{\rho,t},\theta^{*}_{\psi,t},\theta^{*}_{d_{q},t})]-\nabla_{w}J(w_{t})\right\|_{2}^{2}$.
Following the steps similar to those in proving Theorem 1, we obtain

$\displaystyle\mathbb{E}[G^{i}_{\text{DR}}(w_{t},\theta^{*}_{q,t},\theta^{*}_{\rho,t},\theta^{*}_{\psi,t},\theta^{*}_{d_{q},t})]-\nabla_{w}J(w_{t})$
$\displaystyle=\mathbb{E}_{\mathcal{D}}[(\hat{\rho}_{\pi_{w_{t}}}(s,a,\theta^{*}_{\rho,t})-{\rho}_{\pi_{w_{t}}}(s,a))(-\hat{d}^{q}_{\pi_{w_{t}}}(s,a,\theta^{*}_{d_{q},t})+{d}^{q}_{\pi_{w_{t}}}(s,a))]$
$\displaystyle\quad+\mathbb{E}_{\mathcal{D}}[(-\hat{d}^{\rho}_{\pi_{w_{t}}}(s,a,\theta^{*}_{\rho,t},\theta^{*}_{\psi,t})+{d}^{\rho}_{\pi_{w_{t}}}(s,a))(-\hat{Q}_{\pi_{w_{t}}}(s,a,\theta^{*}_{q,t})+{Q}_{\pi_{w_{t}}}(s,a))]$
$\displaystyle\quad+\gamma\mathbb{E}_{\mathcal{D}}[(\hat{\rho}_{\pi_{w_{t}}}(s,a,\theta^{*}_{\rho,t})-{\rho}_{\pi_{w_{t}}}(s,a))\mathbb{E}_{\pi_{w_{t}}}[\hat{d}^{q}_{\pi_{w_{t}}}(s^{\prime},a^{\prime},\theta^{*}_{d_{q},t})-{d}^{q}_{\pi_{w_{t}}}(s^{\prime},a^{\prime})]]$
$\displaystyle\quad+\gamma\mathbb{E}_{\mathcal{D}}[(\hat{\rho}_{\pi_{w_{t}}}(s,a,\theta^{*}_{\rho,t})-{\rho}_{\pi_{w_{t}}}(s,a))\mathbb{E}_{\pi_{w_{t}}}[(\hat{Q}_{\pi_{w_{t}}}(s^{\prime},a^{\prime},\theta^{*}_{q,t})-{Q}_{\pi_{w_{t}}}(s^{\prime},a^{\prime}))\nabla_{w}\log\pi_{w_{t}}(s^{\prime},a^{\prime})]]$
$\displaystyle\quad+\gamma\mathbb{E}_{\mathcal{D}}[(\hat{d}^{\rho}_{\pi_{w_{t}}}(s,a,\theta^{*}_{\rho,t},\theta^{*}_{\psi,t})-{d}^{\rho}_{\pi_{w_{t}}}(s,a))\mathbb{E}_{\pi_{w_{t}}}[\hat{Q}_{\pi_{w_{t}}}(s^{\prime},a^{\prime},\theta^{*}_{q,t})-{Q}_{\pi_{w_{t}}}(s^{\prime},a^{\prime})]]$
$\displaystyle\leq\sqrt{\mathbb{E}_{\mathcal{D}}[(\hat{\rho}_{\pi_{w_{t}}}(s,a,\theta^{*}_{\rho,t})-{\rho}_{\pi_{w_{t}}}(s,a))^{2}]}\sqrt{\mathbb{E}_{\mathcal{D}}[(\hat{d}^{q}_{\pi_{w_{t}}}(s,a,\theta^{*}_{d_{q},t})-{d}^{q}_{\pi_{w_{t}}}(s,a))^{2}]}$
$\displaystyle\quad+\sqrt{\mathbb{E}_{\mathcal{D}}[(\hat{d}^{\rho}_{\pi_{w_{t}}}(s,a,\theta^{*}_{\rho,t},\theta^{*}_{\psi,t})-{d}^{\rho}_{\pi_{w_{t}}}(s,a))^{2}]}\sqrt{\mathbb{E}_{\mathcal{D}}[(\hat{Q}_{\pi_{w_{t}}}(s,a,\theta^{*}_{q,t})-{Q}_{\pi_{w_{t}}}(s,a))^{2}]}$
$\displaystyle\quad+\sqrt{\mathbb{E}_{\mathcal{D}}[(\hat{\rho}_{\pi_{w_{t}}}(s,a,\theta^{*}_{q,t})-{\rho}_{\pi_{w_{t}}}(s,a))^{2}]}\sqrt{\mathbb{E}_{\mathcal{D}_{d}\cdot\pi_{w_{t}}}[(\hat{d}^{q}_{\pi_{w_{t}}}(s^{\prime},a^{\prime},\theta^{*}_{d_{q},t})-{d}^{q}_{\pi_{w_{t}}}(s^{\prime},a^{\prime}))^{2}]}$
$\displaystyle\quad+C_{sc}\sqrt{\mathbb{E}_{\mathcal{D}}[(\hat{\rho}_{\pi_{w_{t}}}(s,a,\theta^{*}_{q,t})-{\rho}_{\pi_{w_{t}}}(s,a))^{2}]}\sqrt{\mathbb{E}_{\mathcal{D}_{d}\cdot\pi_{w_{t}}}[(\hat{Q}_{\pi_{w_{t}}}(s^{\prime},a^{\prime},\theta^{*}_{q,t})-{Q}_{\pi_{w_{t}}}(s^{\prime},a^{\prime}))^{2}]}$
$\displaystyle\quad+\sqrt{\mathbb{E}_{\mathcal{D}}[(\hat{d}^{\rho}_{\pi_{w_{t}}}(s,a,\theta^{*}_{\rho,t},\theta^{*}_{\psi,t})-{d}^{\rho}_{\pi_{w_{t}}}(s,a))^{2}]}\sqrt{\mathbb{E}_{\mathcal{D}_{d}\cdot\pi_{w_{t}}}[(\hat{Q}_{\pi_{w_{t}}}(s^{\prime},a^{\prime},\theta^{*}_{q,t})-{Q}_{\pi_{w_{t}}}(s^{\prime},a^{\prime}))^{2}]}$
$\displaystyle\leq
2\epsilon_{\rho}\epsilon_{d_{q}}+2\epsilon_{d_{\rho}}\epsilon_{q}+C_{sc}\epsilon_{\rho}\epsilon_{q}.$
(88)

Recall that we define

$\displaystyle\epsilon_{\rho}$
$\displaystyle=\max_{w}\sqrt{\mathbb{E}_{\mathcal{D}}[(\hat{\rho}_{\pi_{w}}(s,a,\theta^{*}_{\rho,w})-{\rho}_{\pi_{w}}(s,a))^{2}]}$
$\displaystyle\epsilon_{d_{\rho}}$
$\displaystyle=\max_{w}\sqrt{\mathbb{E}_{\mathcal{D}}[(\hat{d}^{\rho}_{\pi_{w}}(s,a,\theta^{*}_{\rho,w},\theta^{*}_{\psi,w})-{d}^{\rho}_{\pi_{w}}(s,a))^{2}]}$
$\displaystyle\epsilon_{q}$
$\displaystyle=\max\left\\{\max_{w}\sqrt{\mathbb{E}_{\mathcal{D}}[(\hat{Q}_{\pi_{w}}(s,a,\theta^{*}_{q,w})-{Q}_{\pi_{w}}(s,a))^{2}]},\max_{w}\sqrt{\mathbb{E}_{\mathcal{D}_{d}\cdot\pi_{w}}[(\hat{Q}_{\pi_{w}}(s^{\prime},a^{\prime},\theta^{*}_{q,w})-{Q}_{\pi_{w}}(s^{\prime},a^{\prime}))^{2}]}\right\\}$
$\displaystyle\epsilon_{d_{q}}$
$\displaystyle=\max\left\\{\max_{w}\sqrt{\mathbb{E}_{\mathcal{D}}[(\hat{d}^{q}_{\pi_{w}}(s,a,\theta^{*}_{d_{q},w})-{d}^{q}_{\pi_{w}}(s,a))^{2}]},\max_{w}\sqrt{\mathbb{E}_{\mathcal{D}_{d}\cdot\pi_{w}}[(\hat{d}^{q}_{\pi_{w}}(s^{\prime},a^{\prime},\theta^{*}_{d_{q},w})-{d}^{q}_{\pi_{w}}(s^{\prime},a^{\prime}))^{2}]}\right\\},$

where

$\displaystyle\hat{\rho}_{\pi_{w}}(s,a,\theta^{*}_{q,w})$
$\displaystyle=\phi(s,a)^{\top}\theta^{*}_{\rho,w},$
$\displaystyle\hat{d}^{\rho}_{\pi_{w}}(s,a,\theta^{*}_{\rho,w},\theta^{*}_{\psi,w})$
$\displaystyle=\phi(s,a)^{\top}\theta^{*}_{\rho,w}\varphi(s,a)^{\top}\theta^{*}_{\psi,w},$
$\displaystyle\hat{Q}_{\pi_{w}}(s,a,\theta^{*}_{q,w})$
$\displaystyle=\phi(s,a)^{\top}\theta^{*}_{q,w},$
$\displaystyle\hat{d}^{q}_{\pi_{w}}(s^{\prime},a^{\prime},\theta^{*}_{d_{q},w})$
$\displaystyle=x(s,a)^{\top}\theta^{*}_{d_{q},w}.$

Then, eq. 88 implies that

$\displaystyle\left\|\mathbb{E}[G^{i}_{\text{DR}}(w_{t},\theta^{*}_{q,t},\theta^{*}_{\rho,t},\theta^{*}_{\psi,t},\theta^{*}_{d_{q},t})]-\nabla_{w}J(w_{t})\right\|_{2}^{2}\leq
6\epsilon^{2}_{\rho}\epsilon^{2}_{d_{q}}+6\epsilon^{2}_{d_{\rho}}\epsilon^{2}_{q}+3C_{sc}\epsilon^{2}_{\rho}\epsilon^{2}_{q}.$
(89)

Substituting eq. 83, eq. 84, eq. 85, eq. 86, eq. 87 and eq. 89 into eq. 82
yields

$\displaystyle\mathbb{E}\left[\left\|G_{\text{DR}}(w_{t},\mathcal{M}_{t})-\nabla_{w}J(w_{t})\right\|_{2}^{2}|\mathcal{F}_{t}\right]$
$\displaystyle\leq
6C^{2}_{6}\left\|\theta^{*}_{d_{q},t}-\theta_{d_{q},t}\right\|_{2}^{2}+6C^{2}_{7}\left\|\theta_{\psi,t}-\theta^{*}_{\psi,t}\right\|_{2}^{2}+6C^{2}_{8}\left\|\theta_{q,t}-\theta^{*}_{q,t}\right\|_{2}+6C^{2}_{9}\left\|\theta_{\rho,t}-\theta^{*}_{\rho,t}\right\|_{2}^{2}+\frac{24C^{2}_{10}}{N}$
$\displaystyle\quad+36\epsilon^{2}_{\rho}\epsilon^{2}_{d_{q}}+36\epsilon^{2}_{d_{\rho}}\epsilon^{2}_{q}+18C_{sc}\epsilon^{2}_{\rho}\epsilon^{2}_{q}$
$\displaystyle\leq
C_{11}\left(\left\|\theta^{*}_{d_{q},t}-\theta_{d_{q},t}\right\|_{2}^{2}+\left\|\theta_{\psi,t}-\theta^{*}_{\psi,t}\right\|_{2}^{2}+\left\|\theta_{q,t}-\theta^{*}_{q,t}\right\|_{2}+\left\|\theta_{\rho,t}-\theta^{*}_{\rho,t}\right\|_{2}^{2}\right)+\frac{24C^{2}_{10}}{N}$
$\displaystyle\quad+C_{12}(\epsilon^{2}_{\rho}\epsilon^{2}_{d_{q}}+\epsilon^{2}_{d_{\rho}}\epsilon^{2}_{q}+\epsilon^{2}_{\rho}\epsilon^{2}_{q})$
$\displaystyle\leq
C_{11}\Delta_{t}+\frac{24C^{2}_{10}}{N}+C_{12}(\epsilon^{2}_{\rho}\epsilon^{2}_{d_{q}}+\epsilon^{2}_{d_{\rho}}\epsilon^{2}_{q}+\epsilon^{2}_{\rho}\epsilon^{2}_{q}),$
(90)

where $C_{11}=6\max\\{C^{2}_{6},C^{2}_{7},C^{2}_{8},C^{2}_{9}\\}$, and
$C_{12}=\max\\{36,18C_{sc}\\}$. Substituting eq. 90 into eq. 81 yields

$\displaystyle\Big{(}\frac{1}{2}\alpha$ $\displaystyle-
L_{J}\alpha^{2}\Big{)}\mathbb{E}[\left\|\nabla_{w}J(w_{t})\right\|_{2}^{2}|\mathcal{F}_{t}]$
$\displaystyle\leq\mathbb{E}[J(w_{t+1})|\mathcal{F}_{t}]-J(w_{t})+\Big{(}\frac{1}{2}\alpha+L_{J}\alpha^{2}\Big{)}C_{11}\Delta_{t}+\Big{(}\frac{1}{2}\alpha+L_{J}\alpha^{2}\Big{)}\frac{24C^{2}_{10}}{N}$
$\displaystyle\quad+\Big{(}\frac{1}{2}\alpha+L_{J}\alpha^{2}\Big{)}C_{12}(\epsilon^{2}_{\rho}\epsilon^{2}_{d_{q}}+\epsilon^{2}_{d_{\rho}}\epsilon^{2}_{q}+\epsilon^{2}_{\rho}\epsilon^{2}_{q}).$
(91)

Taking the expectation on both sides of eq. 91 and taking the summation over
$t=0\cdots T-1$ yield

$\displaystyle\Big{(}\frac{1}{2}\alpha$ $\displaystyle-
L_{J}\alpha^{2}\Big{)}\sum_{t=0}^{T-1}\mathbb{E}[\left\|\nabla_{w}J(w_{t})\right\|_{2}^{2}]$
$\displaystyle\leq\mathbb{E}[J(w_{T})]-J(w_{0})+\Big{(}\frac{1}{2}\alpha+L_{J}\alpha^{2}\Big{)}C_{11}\sum_{t=0}^{T-1}\mathbb{E}[\Delta_{t}]+\Big{(}\frac{1}{2}\alpha+L_{J}\alpha^{2}\Big{)}\frac{24C^{2}_{10}T}{N}$
$\displaystyle\quad+\Big{(}\frac{1}{2}\alpha+L_{J}\alpha^{2}\Big{)}C_{12}(\epsilon^{2}_{\rho}\epsilon^{2}_{d_{q}}+\epsilon^{2}_{d_{\rho}}\epsilon^{2}_{q}+\epsilon^{2}_{\rho}\epsilon^{2}_{q})T.$
(92)

We then proceed to bound the term $\sum_{t=0}^{T-1}\mathbb{E}[\Delta_{t}]$.
Lemma 7 implies that

$\displaystyle\mathbb{E}$ $\displaystyle[\Delta_{t+1}|\mathcal{F}_{t}]$
$\displaystyle\leq\left(1-\frac{1}{2}\varrho\right)\Delta_{t}+\frac{2L^{2}_{fix}}{\varrho}\mathbb{E}[\left\|w_{t+1}-w_{t}\right\|_{2}^{2}|\mathcal{F}_{t}]+\frac{C_{5}}{(1-\varrho)N}$
$\displaystyle=\left(1-\frac{1}{2}\varrho\right)\Delta_{t}+\frac{2L^{2}_{fix}}{\varrho}\alpha^{2}\mathbb{E}[\left\|G_{\text{DR}}(w_{t},\mathcal{M}_{t})\right\|_{2}^{2}|\mathcal{F}_{t}]+\frac{C_{5}}{(1-\varrho)N}$
$\displaystyle\leq\left(1-\frac{1}{2}\varrho\right)\Delta_{t}+\frac{4L^{2}_{fix}}{\varrho}\alpha^{2}\mathbb{E}[\left\|G_{\text{DR}}(w_{t},\mathcal{M}_{t})-\nabla_{w}J(w_{t})\right\|_{2}^{2}|\mathcal{F}_{t}]+\frac{4L^{2}_{fix}}{\varrho}\alpha^{2}\mathbb{E}[\left\|\nabla_{w}J(w_{t})\right\|_{2}^{2}|\mathcal{F}_{t}]+\frac{C_{5}}{(1-\varrho)N}$
$\displaystyle\overset{(i)}{\leq}\left(1-\frac{1}{2}\varrho+\frac{4C_{11}L^{2}_{fix}\alpha^{2}}{\varrho}\right)\Delta_{t}+\frac{4L^{2}_{fix}}{\varrho}\alpha^{2}\mathbb{E}[\left\|\nabla_{w}J(w_{t})\right\|_{2}^{2}|\mathcal{F}_{t}]+\left[\frac{96L^{2}_{fix}C^{2}_{10}\alpha^{2}}{\varrho}+\frac{C_{5}}{1-\varrho}\right]\frac{1}{N}$
$\displaystyle\quad+\frac{4C_{12}L^{2}_{fix}\alpha^{2}}{\varrho}(\epsilon^{2}_{\rho}\epsilon^{2}_{d_{q}}+\epsilon^{2}_{d_{\rho}}\epsilon^{2}_{q}+\epsilon^{2}_{\rho}\epsilon^{2}_{q})$
$\displaystyle\overset{(ii)}{\leq}\left(1-\frac{1}{4}\varrho\right)\Delta_{t}+C_{12}\alpha^{2}\mathbb{E}[\left\|\nabla_{w}J(w_{t})\right\|_{2}^{2}|\mathcal{F}_{t}]+\frac{C_{13}}{N}+C_{14}(\epsilon^{2}_{\rho}\epsilon^{2}_{d_{q}}+\epsilon^{2}_{d_{\rho}}\epsilon^{2}_{q}+\epsilon^{2}_{\rho}\epsilon^{2}_{q}),$
(93)

where $L^{2}_{fix}=(L^{2}_{\kappa}+L^{2}_{\xi}+L^{2}_{\zeta})$, $(i)$ follows
from eq. 90, $(ii)$ follows from the fact that
$C_{12}=\frac{4L^{2}_{fix}}{\varrho}$,
$C_{13}=\frac{96L^{2}_{fix}C^{2}_{10}\alpha^{2}}{\varrho}+\frac{C_{5}}{1-\varrho}$
and $C_{14}=\frac{4C_{12}L^{2}_{fix}\alpha^{2}}{\varrho}$, and for small
enough $\alpha$, we have $\alpha\leq\frac{\varrho}{4\sqrt{C_{11}}L_{fix}}$.
Taking the expectation on both sides of eq. 93 and applying it iteratively
yield

$\displaystyle\mathbb{E}[\Delta_{t}]$
$\displaystyle\leq\left(1-\frac{1}{4}\varrho\right)^{t}\Delta_{0}+C_{12}\alpha^{2}\sum_{i=0}^{t-1}\left(1-\frac{1}{4}\varrho\right)^{t-1-i}\mathbb{E}[\left\|\nabla_{w}J(w_{i})\right\|_{2}^{2}]+\frac{C_{13}}{N}\sum_{i=0}^{t-1}\left(1-\frac{1}{4}\varrho\right)^{t-1-i}$
$\displaystyle\quad+C_{14}(\epsilon^{2}_{\rho}\epsilon^{2}_{d_{q}}+\epsilon^{2}_{d_{\rho}}\epsilon^{2}_{q}+\epsilon^{2}_{\rho}\epsilon^{2}_{q})\sum_{i=0}^{t-1}\left(1-\frac{1}{4}\varrho\right)^{t-1-i}.$
(94)

Taking the summation on eq. 94 over $t=0,\cdots,T-1$ yields

$\displaystyle\sum_{t=0}^{T-1}\mathbb{E}[\Delta_{t}]$
$\displaystyle\leq\Delta_{0}\sum_{t=0}^{T-1}\left(1-\frac{1}{4}\varrho\right)^{t}+C_{12}\alpha^{2}\sum_{t=0}^{T-1}\sum_{i=0}^{t-1}\left(1-\frac{1}{4}\varrho\right)^{t-1-i}\mathbb{E}[\left\|\nabla_{w}J(w_{i})\right\|_{2}^{2}]+\frac{C_{13}}{N}\sum_{t=0}^{T-1}\sum_{i=0}^{t-1}\left(1-\frac{1}{4}\varrho\right)^{t-1-i}$
$\displaystyle\quad+C_{14}(\epsilon^{2}_{\rho}\epsilon^{2}_{d_{q}}+\epsilon^{2}_{d_{\rho}}\epsilon^{2}_{q}+\epsilon^{2}_{\rho}\epsilon^{2}_{q})\sum_{t=0}^{T-1}\sum_{i=0}^{t-1}\left(1-\frac{1}{4}\varrho\right)^{t-1-i}$
$\displaystyle\leq\frac{4}{\varrho}\Delta_{0}+\frac{4C_{12}\alpha^{2}}{\varrho}\sum_{t=0}^{T-1}\mathbb{E}[\left\|\nabla_{w}J(w_{t})\right\|_{2}^{2}]+\frac{4C_{13}T}{\varrho
N}+\frac{4C_{14}T}{\varrho}(\epsilon^{2}_{\rho}\epsilon^{2}_{d_{q}}+\epsilon^{2}_{d_{\rho}}\epsilon^{2}_{q}+\epsilon^{2}_{\rho}\epsilon^{2}_{q}).$
(95)

Substituting eq. 95 into eq. 92 yields

$\displaystyle\Big{(}\frac{1}{2}\alpha$ $\displaystyle-
L_{J}\alpha^{2}\Big{)}\sum_{t=0}^{T-1}\mathbb{E}[\left\|\nabla_{w}J(w_{t})\right\|_{2}^{2}]$
$\displaystyle\leq\mathbb{E}[J(w_{T})]-J(w_{0})+\Big{(}\frac{1}{2}\alpha+L_{J}\alpha^{2}\Big{)}\frac{4C_{11}}{\varrho}\Delta_{0}+\frac{4C_{12}\alpha^{2}}{\varrho}\Big{(}\frac{1}{2}\alpha+L_{J}\alpha^{2}\Big{)}\sum_{t=0}^{T-1}\mathbb{E}[\left\|\nabla_{w}J(w_{i})\right\|_{2}^{2}]$
$\displaystyle\quad+\Big{(}\frac{1}{2}\alpha+L_{J}\alpha^{2}\Big{)}\frac{24\varrho
C^{2}_{10}T+4C_{13}T}{\varrho
N}+\Big{(}\frac{1}{2}\alpha+L_{J}\alpha^{2}\Big{)}\left(C_{12}+\frac{4C_{14}T}{\varrho}\right)(\epsilon^{2}_{\rho}\epsilon^{2}_{d_{q}}+\epsilon^{2}_{d_{\rho}}\epsilon^{2}_{q}+\epsilon^{2}_{\rho}\epsilon^{2}_{q})T,$
(96)

which implies

$\displaystyle\Big{(}\frac{1}{2}\alpha$ $\displaystyle-
L_{J}\alpha^{2}-\frac{4C_{12}\alpha^{3}}{\varrho}\Big{(}\frac{1}{2}+L_{J}\alpha\Big{)}\Big{)}\sum_{t=0}^{T-1}\mathbb{E}[\left\|\nabla_{w}J(w_{t})\right\|_{2}^{2}]$
$\displaystyle\leq\mathbb{E}[J(w_{T})]-J(w_{0})+\Big{(}\frac{1}{2}\alpha+L_{J}\alpha^{2}\Big{)}\frac{4C_{11}}{\varrho}\Delta_{0}+\Big{(}\frac{1}{2}\alpha+L_{J}\alpha^{2}\Big{)}\frac{24\varrho
C^{2}_{10}T+4C_{13}T}{\varrho N}$
$\displaystyle\quad+\Big{(}\frac{1}{2}\alpha+L_{J}\alpha^{2}\Big{)}\left(C_{12}+\frac{4C_{14}T}{\varrho}\right)(\epsilon^{2}_{\rho}\epsilon^{2}_{d_{q}}+\epsilon^{2}_{d_{\rho}}\epsilon^{2}_{q}+\epsilon^{2}_{\rho}\epsilon^{2}_{q})T.$
(97)

For small enough $\alpha$, we can guarantee that $\frac{1}{2}\alpha-
L_{J}\alpha^{2}-\frac{4C_{12}\alpha^{3}}{\varrho}\Big{(}\frac{1}{2}+L_{J}\alpha\Big{)}>0$.
Dividing both sides of eq. 97 by $T\Big{(}\frac{1}{2}\alpha-
L_{J}\alpha^{2}-\frac{4C_{12}\alpha^{3}}{\varrho}\Big{(}\frac{1}{2}+L_{J}\alpha\Big{)}\Big{)}$,
we obtain

$\displaystyle\mathbb{E}[\left\|\nabla_{w}J(w_{\hat{T}})\right\|_{2}^{2}]=\frac{1}{T}\sum_{t=0}^{T-1}\mathbb{E}[\left\|\nabla_{w}J(w_{t})\right\|_{2}^{2}]\leq\Theta\left(\frac{1}{T}\right)+\Theta\left(\frac{1}{N}\right)+\Theta(\epsilon^{2}_{\rho}\epsilon^{2}_{d_{q}}+\epsilon^{2}_{d_{\rho}}\epsilon^{2}_{q}+\epsilon^{2}_{\rho}\epsilon^{2}_{q}).$

Note that
$\mathbb{E}[\left\|\nabla_{w}J(w_{\hat{T}})\right\|_{2}]\leq\sqrt{\mathbb{E}[\left\|\nabla_{w}J(w_{\hat{T}})\right\|_{2}^{2}]}$
and $\sqrt{\sum_{i}a_{i}}\leq\sum_{i}\sqrt{a_{i}}$ for $a_{i}\geq 0$. We
obtain

$\displaystyle\mathbb{E}[\left\|\nabla_{w}J(w_{\hat{T}})\right\|_{2}]\leq\Theta\left(\frac{1}{\sqrt{T}}\right)+\Theta\left(\frac{1}{\sqrt{N}}\right)+\Theta(\epsilon_{\rho}\epsilon_{d_{q}}+\epsilon_{d_{\rho}}\epsilon_{q}+\epsilon_{\rho}\epsilon_{q}),$

which completes the proof.

##  Appendix E Proof of Theorem 3

The following proposition can be directly obtained from Corollary 6.10. in
(Agarwal et al., 2019).

######  Proposition 2.

Consider the DR-Off-PAC update given in Algorithm 1. Suppose 5 holds. Let
$w^{*}_{t}=F^{-1}(w_{t})\nabla_{w}J(w_{t})$ be the exact NPG update direction
at $w_{t}$. Then, we have

$\displaystyle J(\pi^{*})-J(w_{\hat{T}})$
$\displaystyle\leq\frac{{\epsilon_{approx}}}{1-\gamma}+\frac{1}{\alpha
T}\mathbb{E}_{\nu_{\pi^{*}}}[\text{KL}(\pi^{*}(\cdot|s)||\pi_{w_{0}}(\cdot|s))]+\frac{L_{sc}\alpha}{2T}\sum_{t=0}^{T-1}\left\|G_{\text{DR}}(w_{t},\mathcal{M}_{t})\right\|_{2}^{2}+\frac{C_{sc}}{T}\sum_{t=0}^{T-1}\left\|G_{\text{DR}}(w_{t},\mathcal{M}_{t})-w^{*}_{t}\right\|_{2}.$
(98)

Proposition 2 indicates that, as long as the DR-Off-PAC update is close enough
to the exact NPG update, then DP-Off-PAC is guaranteed to converge to a
neighbourhood of the global optimal $J(\pi^{*})$ with a
$\left(\frac{{\epsilon_{approx}}}{1-\gamma}\right)$-level gap. We then proceed
to prove Theorem 3.

###### Proof.

We start with eq. 98 as follows:

$\displaystyle J(\pi^{*})-\mathbb{E}[J(w_{\hat{T}})]$
$\displaystyle\leq\frac{{\epsilon_{approx}}}{1-\gamma}+\frac{1}{\alpha
T}\mathbb{E}_{\nu_{\pi^{*}}}[\text{KL}(\pi^{*}(\cdot|s)||\pi_{w_{0}}(\cdot|s))]+\frac{L_{sc}\alpha}{2T}\sum_{t=0}^{T-1}\mathbb{E}[\left\|G_{\text{DR}}(w_{t},\mathcal{M}_{t})\right\|_{2}^{2}]+\frac{C_{sc}}{T}\sum_{t=0}^{T-1}\mathbb{E}\left[\left\|G_{\text{DR}}(w_{t},\mathcal{M}_{t})-w^{*}_{t}\right\|_{2}\right]$
$\displaystyle\leq\frac{{\epsilon_{approx}}}{1-\gamma}+\frac{1}{\alpha
T}\mathbb{E}_{\nu_{\pi^{*}}}[\text{KL}(\pi^{*}(\cdot|s)||\pi_{w_{0}}(\cdot|s))]+\frac{L_{sc}\alpha}{T}\sum_{t=0}^{T-1}\mathbb{E}[\left\|G_{\text{DR}}(w_{t},\mathcal{M}_{t})-\nabla_{w}J(w_{t})\right\|_{2}^{2}]+\frac{L_{sc}\alpha}{T}\sum_{t=0}^{T-1}\mathbb{E}\left[\left\|\nabla_{w}J(w_{t})\right\|_{2}^{2}\right]$
$\displaystyle\quad+\frac{C_{sc}}{T}\sum_{t=0}^{T-1}\mathbb{E}[\left\|G_{\text{DR}}(w_{t},\mathcal{M}_{t})-\nabla_{w}J(w_{t})\right\|_{2}]+\frac{C_{sc}}{T}\sum_{t=0}^{T-1}\mathbb{E}[\left\|\nabla_{w}J(w_{t})-w^{*}_{t}\right\|_{2}].$
(99)

We then bound the error terms on the right-hand side of eq. 99 separately.

First consider the term
$\frac{1}{T}\sum_{t=0}^{T-1}\mathbb{E}\left[\left\|\nabla_{w}J(w_{t})\right\|_{2}^{2}\right]$.
We have

$\displaystyle\frac{1}{T}\sum_{t=0}^{T-1}$
$\displaystyle\mathbb{E}\left[\left\|\nabla_{w}J(w_{t})\right\|_{2}^{2}\right]=\mathbb{E}\left[\left\|\nabla_{w}J(w_{\hat{T}})\right\|_{2}^{2}\right]$
$\displaystyle\overset{(i)}{\leq}\Theta\left(\frac{1}{T}\right)+\Theta\left(\frac{1}{N}\right)+\Theta(\epsilon^{2}_{\rho}\epsilon^{2}_{d_{q}}+\epsilon^{2}_{d_{\rho}}\epsilon^{2}_{q}+\epsilon^{2}_{\rho}\epsilon^{2}_{q}),$
(100)

where $(i)$ follows from Theorem 2.

Then we consider the term
$\frac{1}{T}\sum_{t=0}^{T-1}\left\|\nabla_{w}J(w_{t})-w^{*}_{t}\right\|_{2}$.
We proceed as follows.

$\displaystyle\frac{1}{T}\sum_{t=0}^{T-1}$
$\displaystyle\mathbb{E}\left[\left\|\nabla_{w}J(w_{t})-w^{*}_{t}\right\|_{2}\right]$
$\displaystyle=\frac{1}{T}\sum_{t=0}^{T-1}\mathbb{E}\left[\left\|(I-F^{-1}(w_{t}))\nabla_{w}J(w_{t})\right\|_{2}\right]\leq\left(1+\frac{1}{\lambda_{F}}\right)\frac{1}{T}\sum_{t=0}^{T-1}\mathbb{E}\left[\left\|\nabla_{w}J(w_{t})\right\|_{2}\right]$
$\displaystyle=\left(1+\frac{1}{\lambda_{F}}\right)\mathbb{E}\left[\left\|\nabla_{w}J(w_{\hat{T}})\right\|_{2}\right]=\left(1+\frac{1}{\lambda_{F}}\right)\sqrt{\mathbb{E}\left[\left\|\nabla_{w}J(w_{\hat{T}})\right\|_{2}^{2}\right]}$
$\displaystyle\overset{(i)}{\leq}\Theta\left(\frac{1}{\sqrt{T}}\right)+\Theta\left(\frac{1}{\sqrt{N}}\right)+\Theta(\epsilon_{\rho}\epsilon_{d_{q}}+\epsilon_{d_{\rho}}\epsilon_{q}+\epsilon_{\rho}\epsilon_{q}),$
(101)

where $(i)$ follows from eq. 100 and the fact that
$\sqrt{\sum_{i}a_{i}}\leq\sum_{i}\sqrt{a_{i}}$ for $a_{i}\geq 0$.

We then consider the term
$\frac{1}{T}\sum_{t=0}^{T-1}\mathbb{E}[\left\|G_{\text{DR}}(w_{t},\mathcal{M}_{t})-\nabla_{w}J(w_{t})\right\|_{2}]$.
Recalling eq. 90, we have

$\displaystyle\mathbb{E}\left[\left\|G_{\text{DR}}(w_{t},\mathcal{M}_{t})-\nabla_{w}J(w_{t})\right\|_{2}^{2}|\mathcal{F}_{t}\right]\leq
C_{11}\Delta_{t}+\frac{24C^{2}_{10}}{N}+C_{12}(\epsilon^{2}_{\rho}\epsilon^{2}_{d_{q}}+\epsilon^{2}_{d_{\rho}}\epsilon^{2}_{q}+\epsilon^{2}_{\rho}\epsilon^{2}_{q}),$

which implies

$\displaystyle\mathbb{E}[\left\|G_{\text{DR}}(w_{t},\mathcal{M}_{t})-\nabla_{w}J(w_{t})\right\|_{2}|\mathcal{F}_{t}]$
$\displaystyle\leq\sqrt{\mathbb{E}\left[\left\|G_{\text{DR}}(w_{t},\mathcal{M}_{t})-\nabla_{w}J(w_{t})\right\|_{2}^{2}|\mathcal{F}_{t}\right]}$
$\displaystyle\leq\sqrt{C_{11}}\sqrt{\Delta_{t}}+\frac{5C_{10}}{\sqrt{N}}+\sqrt{C_{12}}(\epsilon_{\rho}\epsilon_{d_{q}}+\epsilon_{d_{\rho}}\epsilon_{q}+\epsilon_{\rho}\epsilon_{q}).$
(102)

Taking the expectation on both sides of eq. 102 and taking the summation over
$t=1\cdots T-1$ yield

$\displaystyle\frac{1}{T}\sum_{t=0}^{T-1}\mathbb{E}[\left\|G_{\text{DR}}(w_{t},\mathcal{M}_{t})-\nabla_{w}J(w_{t})\right\|_{2}]\leq\frac{\sqrt{C_{11}}}{T}\sum_{t=0}^{T-1}\mathbb{E}\left[\sqrt{\Delta_{t}}\right]+\frac{5C_{10}}{\sqrt{N}}+\sqrt{C_{12}}(\epsilon_{\rho}\epsilon_{d_{q}}+\epsilon_{d_{\rho}}\epsilon_{q}+\epsilon_{\rho}\epsilon_{q}).$
(103)

We then bound the term
$\sum_{t=0}^{T-1}\mathbb{E}\left[\sqrt{\Delta_{t}}\right]$. Note that

$\displaystyle\frac{1}{T}\sum_{t=0}^{T-1}\mathbb{E}[\sqrt{\Delta_{t}}]=\mathbb{E}[\sqrt{\Delta_{\hat{T}}}]\leq\sqrt{\mathbb{E}[\Delta_{\hat{T}}]}=\sqrt{\frac{1}{T}\sum_{t=0}^{T-1}\mathbb{E}[\Delta_{t}]}.$
(104)

Recalling eq. 95, we have

$\displaystyle\sum_{t=0}^{T-1}\mathbb{E}[\Delta_{t}]\leq\frac{4}{\varrho}\Delta_{0}+\frac{4C_{12}\alpha^{2}}{\varrho}\sum_{t=0}^{T-1}\mathbb{E}[\left\|\nabla_{w}J(w_{t})\right\|_{2}^{2}]+\frac{4C_{13}T}{\varrho
N}+\frac{4C_{14}T}{\varrho}(\epsilon^{2}_{\rho}\epsilon^{2}_{d_{q}}+\epsilon^{2}_{d_{\rho}}\epsilon^{2}_{q}+\epsilon^{2}_{\rho}\epsilon^{2}_{q}),$

which implies

$\displaystyle\frac{1}{T}\sum_{t=0}^{T-1}\mathbb{E}[\sqrt{\Delta_{t}}]$
$\displaystyle\leq\sqrt{\frac{1}{T}\sum_{t=0}^{T-1}\mathbb{E}[\Delta_{t}]}$
$\displaystyle\leq\sqrt{\frac{4\Delta_{0}}{\varrho
T}}+\frac{2\sqrt{C_{12}}\alpha}{\sqrt{\varrho}}\sqrt{\mathbb{E}[\left\|\nabla_{w}J(w_{\hat{T}})\right\|_{2}^{2}]}+\sqrt{\frac{4C_{13}}{\varrho
N}}+\sqrt{\frac{4C_{14}}{\varrho}}(\epsilon_{\rho}\epsilon_{d_{q}}+\epsilon_{d_{\rho}}\epsilon_{q}+\epsilon_{\rho}\epsilon_{q})$
$\displaystyle\overset{(i)}{\leq}\Theta\left(\frac{1}{\sqrt{T}}\right)+\Theta\left(\frac{1}{\sqrt{N}}\right)+\Theta(\epsilon_{\rho}\epsilon_{d_{q}}+\epsilon_{d_{\rho}}\epsilon_{q}+\epsilon_{\rho}\epsilon_{q}),$
(105)

where $(i)$ follows from eq. 100. Substituting eq. 105 into eq. 103 yields

$\displaystyle\frac{1}{T}\sum_{t=0}^{T-1}\mathbb{E}[\left\|G_{\text{DR}}(w_{t},\mathcal{M}_{t})-\nabla_{w}J(w_{t})\right\|_{2}]\leq\Theta\left(\frac{1}{\sqrt{T}}\right)+\Theta\left(\frac{1}{\sqrt{N}}\right)+\Theta(\epsilon_{\rho}\epsilon_{d_{q}}+\epsilon_{d_{\rho}}\epsilon_{q}+\epsilon_{\rho}\epsilon_{q}).$
(106)

Finally, we consider the term
$\frac{1}{T}\sum_{t=0}^{T-1}\mathbb{E}[\left\|G_{\text{DR}}(w_{t},\mathcal{M}_{t})-\nabla_{w}J(w_{t})\right\|_{2}^{2}]$.
Taking the expectation on both sides of eq. 90 and taking the summation over
$t=0,\cdots,T-1$ yield

$\displaystyle\quad\frac{1}{T}\sum_{t=0}^{T-1}\mathbb{E}\left[\left\|G_{\text{DR}}(w_{t},\mathcal{M}_{t})-\nabla_{w}J(w_{t})\right\|_{2}^{2}\right]\leq\frac{C_{11}}{T}\sum_{t=0}^{T-1}\mathbb{E}[\Delta_{t}]+\frac{24C^{2}_{10}}{N}+C_{12}(\epsilon^{2}_{\rho}\epsilon^{2}_{d_{q}}+\epsilon^{2}_{d_{\rho}}\epsilon^{2}_{q}+\epsilon^{2}_{\rho}\epsilon^{2}_{q})$
$\displaystyle\overset{(i)}{\leq}\frac{4C_{11}}{\varrho
T}\Delta_{0}+\frac{4C_{11}C_{12}\alpha^{2}}{\varrho
T}\sum_{t=0}^{T-1}\mathbb{E}[\left\|\nabla_{w}J(w_{t})\right\|_{2}^{2}]+\frac{4C_{11}C_{13}}{\varrho
N}+\frac{4C_{11}C_{14}}{\varrho}(\epsilon^{2}_{\rho}\epsilon^{2}_{d_{q}}+\epsilon^{2}_{d_{\rho}}\epsilon^{2}_{q}+\epsilon^{2}_{\rho}\epsilon^{2}_{q})$
$\displaystyle\quad+\frac{24C^{2}_{10}}{N}+C_{12}(\epsilon^{2}_{\rho}\epsilon^{2}_{d_{q}}+\epsilon^{2}_{d_{\rho}}\epsilon^{2}_{q}+\epsilon^{2}_{\rho}\epsilon^{2}_{q})$
$\displaystyle\overset{(ii)}{\leq}\Theta\left(\frac{1}{T}\right)+\Theta\left(\frac{1}{N}\right)+\Theta(\epsilon^{2}_{\rho}\epsilon^{2}_{d_{q}}+\epsilon^{2}_{d_{\rho}}\epsilon^{2}_{q}+\epsilon^{2}_{\rho}\epsilon^{2}_{q}),$
(107)

where $(i)$ follows from eq. 95, and $(ii)$ follows from Theorem 2.

Substituting eq. 100, eq. 101, eq. 106 and eq. 107 into eq. 99 yields

$\displaystyle
J(\pi^{*})-J(w_{\hat{T}})\leq\frac{{\epsilon_{approx}}}{1-\gamma}+\Theta\left(\frac{1}{\sqrt{T}}\right)+\Theta\left(\frac{1}{\sqrt{N}}\right)+\Theta(\epsilon_{\rho}\epsilon_{d_{q}}+\epsilon_{d_{\rho}}\epsilon_{q}+\epsilon_{\rho}\epsilon_{q}),$

which completes the proof.

∎