* Hsu et al. [2019] D. Hsu, A. Kontorovich, D. A. Levin, Y. Peres, C. Szepesvári, and G. Wolfer.  Mixing time estimation in reversible Markov chains from a single sample path.  _The Annals of Applied Probability_ , 29(4):2439–2480, 2019.
  * Johnson and Zhang [2013] R. Johnson and T. Zhang.  Accelerating stochastic gradient descent using predictive variance reduction.  In _Advances in Neural Information Processing Systems_ , volume 26, pages 315–323, 2013.
  * Kaelbling et al. [1996] L. P. Kaelbling, M. L. Littman, and A. W. Moore.  Reinforcement learning: A survey.  _Journal of artificial intelligence research_ , 4:237–285, 1996.
  * Khamaru et al. [2021a] K. Khamaru, A. Pananjady, F. Ruan, M. J. Wainwright, and M. I. Jordan.  Is temporal difference learning optimal? An instance-dependent analysis.  _SIAM Journal on Mathematics of Data Science_ , 3(4):1013–1040, 2021a.
  * Khamaru et al. [2021b] K. Khamaru, E. Xia, M. J. Wainwright, and M. I. Jordan.  Instance-optimality in optimal value estimation: Adaptivity via variance-reduced Q-learning.  _arXiv preprint arXiv:2106.14352_ , 2021b.
  * Kober et al. [2013] J. Kober, J. A. Bagnell, and J. Peters.  Reinforcement learning in robotics: A survey.  _The International Journal of Robotics Research_ , 32(11):1238–1274, 2013.
  * Korda and La [2015] N. Korda and P. La.  On TD (0) with function approximation: Concentration bounds and a centered variant with exponential convergence.  In _International conference on machine learning_ , pages 626–634. PMLR, 2015.
  * Kotsalis et al. [2020a] G. Kotsalis, G. Lan, and T. Li.  Simple and optimal methods for stochastic variational inequalities, I: operator extrapolation.  _arXiv preprint arXiv:2011.02987_ , 2020a.
  * Kotsalis et al. [2020b] G. Kotsalis, G. Lan, and T. Li.  Simple and optimal methods for stochastic variational inequalities, II: Markovian noise and policy evaluation in reinforcement learning.  _arXiv preprint arXiv:2011.08434_ , 2020b.
  * Lakshminarayanan and Szepesvári [2018] C. Lakshminarayanan and C. Szepesvári.  Linear stochastic approximation: How far does constant step-size and iterate averaging go?  In _International Conference on Artificial Intelligence and Statistics_ , pages 1347–1355. PMLR, 2018.
  * Le Cam [1972] L. Le Cam.  Limits of experiments.  In _Proceedings of the Sixth Berkeley Symposium on Mathematical Statistics and Probability, Volume 1: Theory of Statistics_ , pages 245–282. University of California Press, 1972.
  * Le Cam and Yang [2000] L. Le Cam and G. L. Yang.  _Asymptotics in statistics: Some basic concepts_.  Springer Science & Business Media, 2000.
  * Li et al. [2020] G. Li, Y. Wei, Y. Chi, Y. Gu, and Y. Chen.  Breaking the sample size barrier in model-based reinforcement learning with a generative model.  In _Advances in Neural Information Processing Systems_ , volume 33, pages 12861–12872. Curran Associates, Inc., 2020.
  * Li et al. [2021] G. Li, C. Cai, Y. Chen, Y. Gu, Y. Wei, and Y. Chi.  Is q-learning minimax optimal? a tight sample complexity analysis.  _arXiv preprint arXiv:2102.06548_ , 2021.
  * Min et al. [2021] Y. Min, T. Wang, D. Zhou, and Q. Gu.  Variance-aware off-policy evaluation with linear function approximation.  _Advances in neural information processing systems_ , 34:7598–7610, 2021.
  * Mou et al. [2020] W. Mou, A. Pananjady, and M. J. Wainwright.  Optimal oracle inequalities for solving projected fixed-point equations.  _arXiv preprint arXiv:2012.05299_ , 2020.
  * Mou et al. [2021] W. Mou, A. Pananjady, M. J. Wainwright, and P. L. Bartlett.  Optimal and instance-dependent guarantees for Markovian linear stochastic approximation.  _preprint_ , 2021.
  * Nemirovsky [1991] A. S. Nemirovsky.  On optimality of Krylov’s information when solving linear operator equations.  _Journal of Complexity_ , 7(2):121–130, 1991\.
  * Nemirovsky [1992] A. S. Nemirovsky.  Information-based complexity of linear operator equations.  _Journal of Complexity_ , 8(2):153–175, 1992\.
  * Nesterov [2003] Y. Nesterov.  _Introductory lectures on convex optimization: A basic course_ , volume 87.  Springer Science & Business Media, 2003.
  * Ouyang and Xu [2021] Y. Ouyang and Y. Xu.  Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems.  _Mathematical Programming_ , 185(1):1–35, 2021\.
  * Pananjady and Wainwright [2021] A. Pananjady and M. J. Wainwright.  Instance-dependent $\ell_{\infty}$-bounds for policy evaluation in tabular reinforcement learning.  _IEEE Transactions on Information Theory_ , 67(1):566–585, 2021.
  * Papini et al. [2018] M. Papini, D. Binaghi, G. Canonaco, M. Pirotta, and M. Restelli.  Stochastic variance-reduced policy gradient.  In _International conference on machine learning_ , pages 4026–4035. PMLR, 2018.
  * Polyak and Juditsky [1992] B. T. Polyak and A. B. Juditsky.  Acceleration of stochastic approximation by averaging.  _SIAM journal on control and optimization_ , 30(4):838–855, 1992.
  * Puterman [2014] M. L. Puterman.  _Markov decision processes: discrete stochastic dynamic programming_.  John Wiley & Sons, 2014.
  * Schmidt et al. [2017] M. Schmidt, N. Le Roux, and F. Bach.  Minimizing finite sums with the stochastic average gradient.  _Mathematical Programming_ , 162(1-2):83–112, 2017.
  * Sidford et al. [2018] A. Sidford, M. Wang, X. Wu, L. F. Yang, and Y. Ye.  Near-optimal time and sample complexities for solving Markov decision processes with a generative model.  In _Proceedings of the 32nd International Conference on Neural Information Processing Systems_ , pages 5192–5202, 2018.
  * Srikant and Ying [2019] R. Srikant and L. Ying.  Finite-time error bounds for linear stochastic approximation and TD learning.  In _Conference on Learning Theory_ , pages 2803–2830. PMLR, 2019\.
  * Sutton [1988] R. S. Sutton.  Learning to predict by the methods of temporal differences.  _Machine learning_ , 3(1):9–44, 1988.
  * Sutton et al. [2009] R. S. Sutton, H. R. Maei, D. Precup, S. Bhatnagar, D. Silver, C. Szepesvári, and E. Wiewiora.  Fast gradient-descent methods for temporal-difference learning with linear function approximation.  In _International Conference on Machine Learning_ , pages 993–1000, 2009.
  * Tadic [2004] V. B. Tadic.  On the almost sure rate of convergence of linear stochastic approximation algorithms.  _IEEE Transactions on Information Theory_ , 50(2):401–409, 2004.
  * Tsitsiklis and Van Roy [1997] J. N. Tsitsiklis and B. Van Roy.  An analysis of temporal-difference learning with function approximation.  _IEEE transactions on automatic control_ , 42(5):674–690, 1997.
  * Wai et al. [2018] H.-T. Wai, Z. Yang, Z. Wang, and M. Hong.  Multi-agent reinforcement learning via double averaging primal-dual optimization.  _Advances in Neural Information Processing Systems_ , 31, 2018.
  * Wai et al. [2019] H. T. Wai, M. Hong, Z. Yang, Z. Wang, and K. Tang.  Variance reduced policy evaluation with smooth function approximation.  In _Advances in Neural Information Processing Systems_ , volume 32, pages 5784–5795, 2019.
  * Wainwright [2019] M. J. Wainwright.  Variance-reduced ${Q}$-learning is minimax optimal.  _arXiv preprint arXiv:1906.04697_ , 2019.
  * Wang et al. [2020] R. Wang, D. P. Foster, and S. M. Kakade.  What are the statistical limits of offline rl with linear function approximation?  _arXiv preprint arXiv:2010.11895_ , 2020.
  * Wolfer and Kontorovich [2019] G. Wolfer and A. Kontorovich.  Estimating the mixing time of ergodic Markov chains.  In _Conference on Learning Theory_ , pages 3120–3159. PMLR, 2019\.
  * Xiao and Zhang [2014] L. Xiao and T. Zhang.  A proximal stochastic gradient method with progressive variance reduction.  _SIAM Journal on Optimization_ , 24(4):2057–2075, 2014.
  * Xu et al. [2020] T. Xu, Z. Wang, Y. Zhou, and Y. Liang.  Reanalysis of variance reduced temporal difference learning.  _arXiv preprint arXiv:2001.01898_ , 2020.
  * Zanette [2021] A. Zanette.  Exponential lower bounds for batch reinforcement learning: Batch rl can be exponentially harder than online rl.  In _International Conference on Machine Learning_ , pages 12287–12297. PMLR, 2021.

##  Appendix A Extension of Theorem 1

In this section, we extend Theorem 1 to a broader method class motivated by
Nemirovsky [1991, 1992]. This method class, which allows a matrix transpose in
addition to the family covered by Assumption 1, is defined by the following.

######  Assumption 4.

The iterative method generates a sequence of iterates $v_{k}$ such that
$v_{0}=0$ and

$\displaystyle v_{k}\in\mathrm{span}\\{r,(I-\gamma P)v_{1},(I-\gamma
P)^{\top}v_{1},...,(I-\gamma P)v_{k-1},(I-\gamma P)^{\top}v_{k-1}\\},\quad
k\geq 1.$ (93)

It should be noted that the method class covered by Assumption 4 is not
particularly natural for solving the policy evaluation problem under standard
observation models. In particular, in typical stochastic settings, the
stochastic operator corresponding to the vector $(I-\gamma P)^{\top}v$ is hard
to obtain with transitions and reward samples. However, the oracle complexity
lower bound applies in the deterministic setting and still serves as a useful
baseline; in particular, it disallows the possibility that the transpose of
the matrix $(I-\gamma P)$ can somehow be leveraged to obtain faster rates.

######  Corollary 1.

Fix a discount factor $\gamma>\tfrac{1}{2}$. There exists a transition kernel
$P$ and an expected reward vector $r$ such that for any iterative method
satisfying Assumption 4, the following statement holds. If $(D,k)$ satisfies
$\tfrac{1-(2\gamma-1)^{2D-4k+2}}{1-(2\gamma-1)^{2D}}\geq\tfrac{1}{2}$, then

$\displaystyle\|v_{k}-v^{*}\|_{\Pi}^{2}\geq\tfrac{1}{2}(2\gamma-1)^{2k}\|v_{0}-v^{*}\|_{\Pi}^{2}.$

###### Proof.

In this proof, we utilize the same worst-case instance as in Theorem 1, which
is defined in Eqs. (48) and (50). Then the square matrix $(I-\gamma
P)^{\top}\in\mathbb{R}^{D\times D}$ is

$\displaystyle(I-\gamma
P)^{\top}=\begin{bmatrix}\tfrac{1}{2}&\tfrac{1}{2}-\gamma&0&...&0&0\\\
0&\tfrac{1}{2}&\tfrac{1}{2}-\gamma&...&0&0\\\ 0&0&\tfrac{1}{2}&...&0&0\\\
\vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\\
\tfrac{1}{2}-\gamma&0&0&...&0&\tfrac{1}{2}\end{bmatrix},$ (94)

which is an upper triangular matrix except for one elements on the bottom
left. Let $\mathbb{R}^{(k,j),D}:=\\{v\in\mathbb{R}^{D}\;|\;v_{(i)}=0\text{ for
all }k+1\leq i\leq D-j\\}$ denote the subspace of vectors in $\mathbb{R}^{D}$
in which only the first $k$ and the last $j$ components can be nonzero.
Provided $D>2k$, we claim that the sequence $\\{v_{k}\\}$ generated by the
iterative method satisfies

$\displaystyle v_{k}\in\mathbb{R}^{(k,k-1),D}.$ (95)

Taking this claim as given for the moment, let us establish the claimed
result. Recall the solution vector $v^{*}$ given by Eq. (51). We have

$\displaystyle\|v_{k}-v^{*}\|_{\Pi}^{2}\geq\tfrac{1}{D}\textstyle{\sum}_{i=k+1}^{D-k+1}(2\gamma-1)^{2i}=\tfrac{(2\gamma-1)^{2k+2}[1-(2\gamma-1)^{2D-4k+2}]}{D[1-(2\gamma-1)^{2}]}.$

If $\tfrac{1-(2\gamma-1)^{2D-4k+2}}{1-(2\gamma-1)^{2D}}\geq\tfrac{1}{2}$, then
together with Eq. (52) we conclude that

$\displaystyle\|v_{k}-v^{*}\|_{\Pi}^{2}\geq\tfrac{1}{2}(2\gamma-1)^{2k}\|v_{0}-v^{*}\|_{\Pi}^{2},$

as desired. ∎

##### Proof of claim (95):

We prove the claim by induction on $k$.
Base case: Given all entries of $r$ except for its first are equal to $0$, we
immediately have $v_{1}\in\mathbb{R}^{(1,0),D}$. Thus, the claim is true for
$k=1$.
Induction step: Now assume that the claim holds for all $t=1,2,...,k-1$, i.e.,
that $v_{t}\in\mathbb{R}^{(t,t-1),D}$. From the special structure of $I-\gamma
P$ and $(I-\gamma P)^{\top}$, we obtain that

$\displaystyle(I-\gamma
P)v_{t}\in\mathbb{R}^{(t+1,t-1),D}~{}\text{and}~{}(I-\gamma
P)^{\top}v_{t}\in\mathbb{R}^{(t,t),D}.$

Assumption 4 then guarantees that $v_{k}\in\mathbb{R}^{(k,k-1),D}$, thus
completing the induction step.

##  Appendix B Proofs of supporting lemmas

In this section, we provide deferred proofs of various lemmas used throughout
the main text and Section 7.

###  B.1 Proof of Lemma 1

Let
$\Pi_{\tau}(s_{t+\tau}):=\operatorname{diag}([P(s_{t+\tau}=1|s_{t})~{}...~{}P(s_{t+\tau=D}|s_{t})])$.
We have

$\displaystyle{\mathbb{E}}[\widetilde{g}(\theta,\xi_{t+\tau}^{\tau})|\mathcal{F}_{t}]$
$\displaystyle={\mathbb{E}}[\left(\langle\psi(s_{t+\tau})-\gamma\psi(s_{t+\tau+1}),\theta\rangle-r(s_{t+\tau},s_{t+\tau+1})\right)\psi(s_{t+\tau})|s_{t}]$
$\displaystyle=\Psi\Pi_{\tau}(s_{t+\tau})(\Psi^{\top}\theta-r-\gamma
P\Psi^{\top}\theta).$

Combining the above equality with the definition of $g(\cdot)$ in (15) yields

$\displaystyle\|g(\bar{\theta})-{\mathbb{E}}[\widetilde{g}(\bar{\theta},\xi_{t+\tau})|\mathcal{F}_{t}]\|_{2}$
$\displaystyle=\|\Psi\big{(}\Pi-\Pi_{t}(s_{t+\tau})\big{)}(\Psi^{\top}\bar{\theta}-r-\gamma
P\Psi^{\top}\bar{\theta})\|_{2}$
$\displaystyle=\|\Psi\big{(}\Pi-\Pi_{t}(s_{t+\tau})\big{)}(I-\gamma
P)(\Psi^{\top}\bar{\theta}-v^{*})\|_{2}$ $\displaystyle\leq
C_{P}\rho^{\tau}\|\Psi\|_{2}\|I-\gamma P\|_{2}\|\bar{v}-v^{*}\|_{2}$
$\displaystyle\leq C_{M}\rho^{\tau}\|\bar{v}-v^{*}\|_{\Pi},$

as claimed. ∎

###  B.2 Proof of Lemma 2

We write

$\displaystyle\|g(\theta)$
$\displaystyle-{\mathbb{E}}[\widetilde{g}(\theta,\xi_{t+\tau})|\mathcal{F}_{t}]-g(\theta^{\prime})+{\mathbb{E}}[\widetilde{g}(\theta^{\prime},\xi_{t+\tau})|\mathcal{F}_{t}]\|_{2}$
$\displaystyle=\|\Psi\big{(}\Pi-\Pi_{t}(s_{t+\tau})\big{)}(I-\gamma
P)\Psi^{\top}(\theta-\theta^{\prime})\|_{2}$ $\displaystyle\leq
C_{P}\rho^{\tau}\|\Psi\|_{2}\|I-\gamma
P\|_{2}\|\Psi^{\top}(\theta-\theta^{\prime})\|_{2}$ $\displaystyle\leq
C_{M}\rho^{\tau}\|v-v^{\prime}\|_{\Pi},$

which completes the proof. ∎

###  B.3 Proof of Lemma 10

We compute the pseudo-inverse of the Fisher information matrix
$J^{\dagger}_{\vartheta}$ and the gradient $\nabla h(\vartheta)$ separately
and combine them to obtain the desired result.

Step 1: Note that by a sufficiency argument, the problem is equivalent to one
in which we observe

$\displaystyle\widehat{H}=\big{(}\psi(s)\psi(s)^{\top}-\gamma\psi(s)\psi(s^{\prime})^{\top},R(s,s^{\prime})\psi(s)\big{)},\quad\text{where}~{}s\sim\omega,~{}s^{\prime}\sim\mathsf{P}(\cdot|s).$

Let us denote

$\displaystyle H:=(\Psi\Omega\Psi^{\top}-\gamma\Psi\Omega
P\Psi^{\top},\Omega\Psi r)$

to be the respective means of these observations. For each pair $i,j\in[D]$,
let
$H^{i,j}:=\big{(}\psi(i)\psi(i)^{\top}-\gamma\psi(i)\psi(j)^{\top},R(i,j)\psi(i)\big{)}$.
The log-likelihood given our observation is then

$\displaystyle\mathcal{L}(\vartheta|\widehat{H})=\sum_{i,j\in[D]}\mathbb{I}_{\\{\widehat{H}=H^{i,j}\\}}\cdot(\log\omega_{i}+\log
P_{i,j}).$

It should be noted that for $\omega$, we take the first $D-1$ components as
the parameters and the last component of $\omega$ is determined by the fact
that the entries sum to $1$. A similar statement holds for each row of $P$.
Taking derivatives with respect to $\omega$, $P$ and $R$, we obtain

$\displaystyle\frac{\partial\mathcal{L}}{\partial\omega_{k}}$
$\displaystyle=\sum_{j\in[D]}\mathbb{I}_{\\{\widehat{H}=H^{k,j}\\}}\cdot\omega^{-1}_{k}-\mathbb{I}_{\\{\widehat{H}=H^{D,j}\\}}\cdot\omega^{-1}_{D},\;\;\text{
for all }k\in[D-1].$ $\displaystyle\frac{\partial\mathcal{L}}{\partial
P_{i,j}}$
$\displaystyle=\mathbb{I}_{\\{\hat{H}=H^{i,j}\\}}{P_{i,j}^{-1}}-\mathbb{I}_{\\{\hat{H}=H^{i,D}\\}}{P_{i,D}^{-1}},\;\;\text{
for all }i\in[D],~{}j\in[D-1].$
$\displaystyle\frac{\partial\mathcal{L}}{\partial R_{i,j}}$
$\displaystyle=0,\;\;\text{ for all }i,j\in[D].$

Consequently, a direct calculation yields

$\displaystyle{\mathbb{E}}\left[\frac{\partial\mathcal{L}}{\partial\omega_{k}}\times\frac{\partial\mathcal{L}}{\partial\omega_{k}}\right]$
$\displaystyle={\omega_{k}^{-1}}+{\omega_{D}^{-1}},\;\;$ $\displaystyle\text{
for all }k\in[D-1].$
$\displaystyle{\mathbb{E}}\left[\frac{\partial\mathcal{L}}{\partial\omega_{k}}\times\frac{\partial\mathcal{L}}{\partial\omega_{l}}\right]$
$\displaystyle={\omega_{D}^{-1}},\;\;$ $\displaystyle\text{ for all
}k,l\in[D-1],~{}k\neq l.$
$\displaystyle{\mathbb{E}}\left[\frac{\partial\mathcal{L}}{\partial\omega_{k}}\times\frac{\partial\mathcal{L}}{\partial
P_{i,j}}\right]$ $\displaystyle=0,\;\;$ $\displaystyle\text{ for all
}i\in[D],~{}j,k\in[D-1].$
$\displaystyle{\mathbb{E}}\left[\frac{\partial\mathcal{L}}{\partial
P_{i,j}}\times\frac{\partial\mathcal{L}}{\partial P_{i,j}}\right]$
$\displaystyle=\frac{\omega_{i}}{P_{i,j}}+\frac{\omega_{i}}{P_{i,D}},\;\;$
$\displaystyle\text{ for all }i\in[D],~{}j\in[D-1].$
$\displaystyle{\mathbb{E}}\left[\frac{\partial\mathcal{L}}{\partial
P_{i,j}}\times\frac{\partial\mathcal{L}}{\partial P_{i,j^{\prime}}}\right]$
$\displaystyle=\frac{\omega_{i}}{P_{i,D}},\;\;$ $\displaystyle\text{ for all
}i\in[D],~{}j,j^{\prime}\in[D-1],~{}j\neq j^{\prime}.$

The other terms in $J_{\vartheta}$ matrix are all $0$. Therefore
$J_{\vartheta}$ can be written as a block diagonal matrix of the form

$\displaystyle J_{\vartheta}=\begin{bmatrix}J_{\omega}&0&0&...&0&0\\\
0&J_{P_{1}}&0&...&0&0\\\ 0&0&J_{P_{2}}&...&0&0\\\
\vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\\ 0&0&0&...&J_{P_{D}}&0\\\
0&0&0&...&0&J_{R}\end{bmatrix},$

where $J_{R}$ is the all-zero matrix. Hence the matrix
$J^{\dagger}_{\vartheta}$ is also block diagonal, of the form

$\displaystyle
J_{\vartheta}^{\dagger}=\begin{bmatrix}J_{\omega}^{\dagger}&0&0&...&0&0\\\
0&J_{P_{1}}^{\dagger}&0&...&0&0\\\ 0&0&J_{P_{2}}^{\dagger}&...&0&0\\\
\vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\\
0&0&0&...&J_{P_{D}}^{\dagger}&0\\\ 0&0&0&...&0&0\end{bmatrix}.$ (96)

By using the Sherman–Morrison–Woodbury formula we can straightforwardly
compute $J_{\omega}^{\dagger}$ and $J_{P_{i}}^{\dagger}$ as

$\displaystyle J_{\omega}^{\dagger}$
$\displaystyle=\operatorname{diag}\left([\omega_{1},...,\omega_{D-1}]\right)-[\omega_{1},...,\omega_{D-1}]^{\top}\cdot[\omega_{1},...,\omega_{D-1}]$
$\displaystyle J_{P_{i}}^{\dagger}$
$\displaystyle=\omega^{-1}_{i}\cdot\left(\operatorname{diag}([P_{i,1},...,P_{i,D-1}])-[P_{i,1},...,P_{i,D-1}]^{\top}\cdot[P_{i,1},...,P_{i,D-1}]\right),\quad\text{
for all }i\in[D].$

Step 2: Next, we turn our attention to evaluating the gradient $\nabla
h(\vartheta)$. We do not need to compute $\nabla_{R}h(\vartheta)$ since
$J^{\dagger}_{R}=0$. Letting $U:=\Psi\Omega\Psi^{\top}-\gamma\Psi\Omega
P\Psi^{\top}$ and
$U^{i,j}:=\psi(i)\psi(i)^{\top}-\gamma\psi(i)\psi(j)^{\top},~{}\text{for
all}~{}i,j\in[D]$, we have

$\displaystyle\frac{\partial h(\vartheta)}{U_{j,k}}$
$\displaystyle=-U^{-1}e_{j}e_{k}^{\top}U^{-1}\Psi\Omega
r=-U^{-1}e_{j}e_{k}^{\top}h(\vartheta),$ $\displaystyle\frac{\partial
U}{\partial\omega_{i}}$
$\displaystyle=\sum_{j\in[D]}\left(P_{i,j}U^{i,j}-P_{D,j}U^{D,j}\right).$

Using the chain rule yields that

$\displaystyle\frac{\partial
h(\vartheta)}{\partial\omega_{i}}=U^{-1}\psi(i)r(i)-U^{-1}\psi(D)r(D)-U^{-1}\cdot\sum_{j\in[D]}\left(P_{i,j}U^{i,j}-P_{D,j}U^{D,j}\right)h(\vartheta)$
(97)

for all $i\in[D-1]$. As for the gradient with respect to $P$, we have

$\displaystyle\frac{\partial U}{\partial P_{i,j}}=\omega_{i}\cdot
U^{i,j}-\omega_{i}\cdot U^{i,D}.$

Using the chain rule once again, we obtain

$\displaystyle\frac{\partial h(\vartheta)}{\partial P_{i,j}}=\omega_{i}\cdot
U^{-1}(U^{i,D}-U^{i,j})h(\vartheta)+\omega_{i}\cdot
U^{-1}\psi(i)\big{(}R(i,j)-R(i,D)\big{)}.$ (98)

for all $i\in[D]$ and $j\in[D-1]$.

Step 3: Finally, we evaluate $\nabla
h(\vartheta)^{\top}J_{\vartheta}^{\dagger}~{}\nabla h(\vartheta)$. From the
block structure, we can write

$\displaystyle\nabla h(\vartheta)^{\top}J_{\vartheta}^{\dagger}~{}\nabla
h(\vartheta)=\nabla_{\omega}h(\vartheta)^{\top}J_{\omega}^{\dagger}~{}\nabla_{\omega}h(\vartheta)+\sum_{i\in[D]}\nabla_{P_{i}}h(\vartheta)^{\top}J_{P_{i}}^{\dagger}~{}\nabla_{P_{i}}h(\vartheta).$
(99)

Let
$y(s,s^{\prime}):=\psi(s)\psi(s)^{\top}h(\vartheta)-\gamma\psi(s)\psi(s^{\prime})^{\top}h(\vartheta)-R(s,s^{\prime})\psi(s)$.
Combining the relations (96), (97) and (98), we have

$\displaystyle\nabla_{\omega}h(\vartheta)^{\top}J_{\omega}^{\dagger}$
$\displaystyle~{}\nabla_{\omega}h(\vartheta)$ $\displaystyle=$ $\displaystyle
U^{-1}\bigg{\\{}\sum_{i\in[D]}\omega_{i}\cdot\big{(}{\mathbb{E}}[y(i,s^{\prime})|s^{\prime}\sim\mathsf{P}(\cdot|i)]\big{)}\cdot\big{(}{\mathbb{E}}[y(i,s^{\prime})|s^{\prime}\sim\mathsf{P}(\cdot|i)]\big{)}^{\top}$
$\displaystyle\quad-\bigg{(}\sum_{i\in[D]}\omega_{i}\cdot{\mathbb{E}}[y(i,s^{\prime})|s^{\prime}\sim\mathsf{P}(\cdot|i)]\bigg{)}\bigg{(}\sum_{i\in[D]}\omega_{i}\cdot{\mathbb{E}}[y(i,s^{\prime})|s^{\prime}\sim\mathsf{P}(\cdot|i)]\bigg{)}^{\top}\bigg{\\}}\cdot
U^{-\top},$ (100a) and
$\displaystyle\nabla_{P_{i}}h(\vartheta)^{\top}J_{P_{i}}^{\dagger}~{}\nabla_{P_{i}}h(\vartheta)=\omega_{i}\cdot
U^{-1}\bigg{\\{}$ $\displaystyle\sum_{j\in[D]}P_{i,j}\cdot
y(i,j)y(i,j)^{\top}$
$\displaystyle-\big{(}{\mathbb{E}}[y(i,s^{\prime})|s^{\prime}\sim\mathsf{P}(\cdot|i)]\big{)}\big{(}{\mathbb{E}}[y(i,s^{\prime})|s^{\prime}\sim\mathsf{P}(\cdot|i)]\big{)}^{\top}\bigg{\\}}\cdot
U^{-\top}.$ (100b)

Substituting Eqs. (100) and (100) into Eq. (99), we obtain

$\displaystyle\nabla h(\vartheta)^{\top}J_{\vartheta}^{\dagger}~{}\nabla
h(\vartheta)$
$\displaystyle\quad=U^{-1}\bigg{\\{}\sum_{i\in[D]}\sum_{j\in[D]}\omega_{i}P_{i,j}\cdot
y(i,j)y(i,j)^{\top}$
$\displaystyle\qquad\qquad\quad-\bigg{(}\sum_{i\in[D]}\omega_{i}\cdot{\mathbb{E}}[y(i,s^{\prime})|s^{\prime}\sim\mathsf{P}(\cdot|i)]\bigg{)}\bigg{(}\sum_{i\in[D]}\omega_{i}\cdot{\mathbb{E}}[y(i,s^{\prime})|s^{\prime}\sim\mathsf{P}(\cdot|i)]\bigg{)}^{\top}\bigg{\\}}\cdot
U^{-\top}$
$\displaystyle\quad=U^{-1}\cdot\operatorname{cov}_{s\sim\omega,s^{\prime}\sim\mathsf{P}(\cdot|s)}\big{\\{}y(s,s^{\prime})\big{\\}}\cdot
U^{-\top},$

which completes the proof. ∎

###  B.4 Proof of Lemma 11

By the definition of $g(\cdot)$ , we have

$\displaystyle\Psi\Pi\Psi^{\top}(\bar{\theta}-\underline{\theta})$
$\displaystyle=\Psi\Pi r+\gamma\Psi\Pi P\Psi^{\top}\bar{\theta}-\big{(}\Psi\Pi
r+\gamma\Psi\Pi
P\Psi^{\top}\underline{\theta}+g(\widetilde{\theta})-\widehat{g}(\widetilde{\theta})\big{)}$
$\displaystyle=\gamma\Psi\Pi
P\Psi^{\top}(\bar{\theta}-\underline{\theta})+\big{(}\widehat{g}(\widetilde{\theta})-g(\widetilde{\theta})\big{)}.$

Invoking the fact that $\Phi=B^{-\frac{1}{2}}\Psi$ and
$\Phi\Pi\Phi^{\top}=I_{d}$, we obtain

$\displaystyle
B^{\frac{1}{2}}(\bar{\theta}-\underline{\theta})=(\Phi\Pi\Phi^{\top}-\gamma\Phi\Pi
P\Phi^{\top})^{-1}B^{-\frac{1}{2}}\big{(}\widehat{g}(\widetilde{\theta})-g(\widetilde{\theta})\big{)}=(I_{d}-M)^{-1}B^{-\frac{1}{2}}\big{(}\widehat{g}(\widetilde{\theta})-g(\widetilde{\theta})\big{)}.$
(101)

Therefore, we have that

$\displaystyle{\mathbb{E}}\|\underline{v}-\bar{v}\|_{\Pi}^{2}$
$\displaystyle={\mathbb{E}}\|\Psi^{\top}B^{-\frac{1}{2}}(I_{d}-M)^{-1}B^{-\frac{1}{2}}\big{(}\widehat{g}(\widetilde{\theta})-g(\widetilde{\theta})\big{)}\|_{\Pi}^{2}$
$\displaystyle={\mathbb{E}}\|(I_{d}-M)^{-1}B^{-\frac{1}{2}}\big{(}\widehat{g}(\widetilde{\theta})-g(\widetilde{\theta})\big{)}\|_{2}^{2}.$
(102)

Applying Young’s inequality then yields

$\displaystyle{\mathbb{E}}\|\underline{v}-\bar{v}\|_{\Pi}^{2}$
$\displaystyle\leq
2{\mathbb{E}}\|(I_{d}-M)^{-1}B^{-\frac{1}{2}}\big{(}\widehat{g}(\bar{\theta})-g(\bar{\theta})\big{)}\|_{2}^{2}$
$\displaystyle\qquad\quad+2{\mathbb{E}}\|(I_{d}-M)^{-1}B^{-\frac{1}{2}}\big{(}\widehat{g}(\widetilde{\theta})-\widehat{g}(\bar{\theta})-g(\widetilde{\theta})+g(\bar{\theta})\big{)}\|_{2}^{2}$
$\displaystyle\overset{(i)}{\leq}\tfrac{2}{N_{k}}\cdot{\mathbb{E}}\|(I_{d}-M)^{-1}B^{-\frac{1}{2}}\big{(}\widetilde{g}(\bar{\theta},\xi_{1})-g(\bar{\theta})\big{)}\|_{2}^{2}$
$\displaystyle\qquad\quad+\tfrac{2}{N_{k}}\cdot{\mathbb{E}}\|(I_{d}-M)^{-1}B^{-\frac{1}{2}}\big{(}\widetilde{g}(\widetilde{\theta},\xi_{1})-\widetilde{g}(\bar{\theta},\xi_{1})-g(\widetilde{\theta})+g(\bar{\theta})\big{)}\|_{2}^{2}$
$\displaystyle\overset{(ii)}{\leq}\tfrac{2}{N_{k}}\cdot\mathrm{trace}\left((I_{d}-M)^{-1}\bar{\Sigma}_{\mathsf{iid}}(I_{d}-M)^{-\top}\right)$
$\displaystyle\qquad\quad+\tfrac{2}{N_{k}(1-\gamma)^{2}\mu}\cdot{\mathbb{E}}\|\widetilde{g}(\widetilde{\theta},\xi_{1})-\widetilde{g}(\bar{\theta},\xi_{1})-g(\widetilde{\theta})+g(\bar{\theta})\|_{\Pi}^{2}$
$\displaystyle\overset{(ii)}{\leq}\tfrac{2}{N_{k}}\cdot\mathrm{trace}\left((I_{d}-M)^{-1}\bar{\Sigma}_{\mathsf{iid}}(I_{d}-M)^{-\top}\right)+\tfrac{2\varsigma^{2}}{N_{k}(1-\gamma)^{2}\mu}\cdot{\mathbb{E}}\|\widetilde{v}-\bar{v}\|_{\Pi}^{2},$

where step (i) follows from the i.i.d. property of the samples, step (ii)
follows from Lemma 7, and step (iii) follows from Assumption 2.∎

###  B.5 Proof of Lemma 12

We index samples $\xi_{t}=(s_{t},s_{t+1},R(s_{t},s_{t+1}))$ successively as in
Section 2.3. We have

$\displaystyle{\mathbb{E}}[\|\widetilde{g}(\theta,\xi_{t+\tau})-\widetilde{g}(\theta^{\prime},\xi_{t+\tau})-g(\theta)+g(\theta^{\prime})\|^{2}_{2}|\mathcal{F}_{t}]$
$\displaystyle=\sum_{i\in[D]}\mathbb{P}(s_{t+\tau}=i|s_{t})\cdot{\mathbb{E}}[\|\langle\psi(i)-\gamma\psi(s_{t+\tau+1}),\theta-\theta^{\prime}\rangle\psi(i)-g(\theta)+g(\theta^{\prime})\|^{2}_{2}|s_{t+\tau}=i]$
$\displaystyle\leq\sum_{i\in[D]}\pi_{i}\cdot{\mathbb{E}}\left[\|\langle\psi(i)-\gamma\psi(s_{t+\tau+1}),\theta-\theta^{\prime}\rangle\psi(i)-g(\theta)+g(\theta^{\prime})\|^{2}_{2}|s_{t+\tau}=i\right]$
$\displaystyle\quad+\sum_{i\in[D]}\|\mathbb{P}(s_{t+\tau}=\cdot|s_{t})-\pi\|_{\infty}{\mathbb{E}}\left[\|\langle\psi(i)-\gamma\psi(s_{t+\tau+1}),\theta-\theta^{\prime}\rangle\psi(i)-g(\theta)+g(\theta^{\prime})\|^{2}_{2}|s_{t+\tau}=i\right]$
$\displaystyle\overset{(i)}{\leq}\sum_{i\in[D]}2\pi_{i}{\mathbb{E}}\left[\|\langle\psi(i)-\gamma\psi(s_{t+\tau+1}),\theta-\theta^{\prime}\rangle\psi(i)-g(\theta)+g(\theta^{\prime})\|^{2}_{2}|s_{t+\tau}=i\right]$
$\displaystyle\overset{(ii)}{\leq}2\varsigma^{2}\|v-v^{\prime}\|_{\Pi}^{2},$

where step (i) follows from Assumption 3 and condition (79), and step (ii)
from Assumption 2. ∎

###  B.6 Proof of Lemma 13

By the definition of $\widehat{g}$, we write

$\displaystyle{\mathbb{E}}\|\widehat{g}(\theta)$
$\displaystyle-\widehat{g}(\theta^{\prime})-g(\theta)+g(\theta^{\prime})\|^{2}_{2}$
$\displaystyle=\tfrac{1}{(N_{k}-n_{0})^{2}}{\mathbb{E}}\|\textstyle{\sum}_{i=n_{0}+1}^{N_{k}}\big{(}\Delta^{k}_{i}(\theta)-\Delta^{k}_{i}(\theta^{\prime})\big{)}\|_{2}^{2}$
$\displaystyle=\tfrac{1}{(N_{k}-n_{0})^{2}}\sum_{i=n_{0}+1}^{N_{k}}{\mathbb{E}}\|\Delta^{k}_{i}(\theta)-\Delta^{k}_{i}(\theta^{\prime})\|_{2}^{2}$
$\displaystyle\qquad+\tfrac{1}{(N_{k}-n_{0})^{2}}\sum_{n_{0}+1\leq i<j\leq
N_{k}}2{\mathbb{E}}\langle\Delta^{k}_{i}(\theta)-\Delta^{k}_{i}(\theta^{\prime}),\Delta^{k}_{j}(\theta)-\Delta^{k}_{j}(\theta^{\prime})\rangle$
$\displaystyle=\underbrace{\tfrac{1}{(N_{k}-n_{0})^{2}}\sum_{i=n_{0}+1}^{N_{k}}{\mathbb{E}}\|\Delta^{k}_{i}(\theta)-\Delta^{k}_{i}(\theta^{\prime})\|_{2}^{2}}_{R_{1}}$
$\displaystyle\qquad+\underbrace{\tfrac{1}{(N_{k}-n_{0})^{2}}\cdot\sum_{\begin{subarray}{c}n_{0}+1\leq
i<j\leq N_{k}\\\
j-i\leq\tau\end{subarray}}2{\mathbb{E}}\langle\Delta^{k}_{i}(\theta)-\Delta^{k}_{i}(\theta^{\prime}),\Delta^{k}_{j}(\theta)-\Delta^{k}_{j}(\theta^{\prime})\rangle}_{R_{2}}$
$\displaystyle\qquad+\underbrace{\tfrac{1}{(N_{k}-n_{0})^{2}}\cdot\sum_{\begin{subarray}{c}n_{0}+1\leq
i<j\leq N_{k}\\\
j-i>\tau\end{subarray}}2{\mathbb{E}}\langle\Delta^{k}_{i}(\theta)-\Delta^{k}_{i}(\theta^{\prime}),\Delta^{k}_{j}(\theta)-\Delta^{k}_{j}(\theta^{\prime})\rangle}_{R_{3}}.$
(103)

where $\Delta^{k}_{i}(\theta)=\widetilde{g}(\theta,\xi_{i}^{k})-g(\theta)$. We
bound $R_{1}$, $R_{2}$ and $R_{3}$ separately. First, by Lemma SM1.14 and the
fact that $n_{0}$ satisfies condition (79), we have that

$\displaystyle
R_{1}\leq\tfrac{2\varsigma^{2}}{N_{k}-n_{0}}\|v-v^{\prime}\|_{\Pi}^{2}.$

For $R_{2}$, by utilizing Holder’s inequality, we obtain

$\displaystyle R_{2}$
$\displaystyle\leq\tfrac{1}{(N_{k}-n_{0})^{2}}\cdot\sum_{\begin{subarray}{c}n_{0}+1\leq
i<j\leq N_{k}\\\
j-i\leq\tau\end{subarray}}2\sqrt{{\mathbb{E}}\|\Delta^{k}_{i}(\theta)-\Delta^{k}_{i}(\theta^{\prime})\|_{2}^{2}}\sqrt{\|\Delta^{k}_{j}(\theta)-\Delta^{k}_{j}(\theta^{\prime})\|_{2}^{2}}$
$\displaystyle\overset{(i)}{\leq}\tfrac{4\varsigma^{2}\tau}{N_{k}-n_{0}}\|v-v^{\prime}\|_{\Pi}^{2},$

where step (i) follows from Lemma SM1.14. To bound $R_{3}$, we first bound the
following term

$\displaystyle{\mathbb{E}}\langle\Delta^{k}_{i}(\theta)-\Delta^{k}_{i}(\theta^{\prime}),\Delta^{k}_{j}(\theta)-\Delta^{k}_{j}(\theta^{\prime})\rangle$
$\displaystyle={\mathbb{E}}\langle\Delta^{k}_{i}(\theta)-\Delta^{k}_{i}(\theta^{\prime}),{\mathbb{E}}[\Delta^{k}_{j}(\theta)-\Delta^{k}_{j}(\theta^{\prime})|\mathcal{F}]\rangle$
$\displaystyle\overset{(i)}{\leq}C_{M}\rho^{j-i}{\mathbb{E}}[\|\Delta^{k}_{i}(\theta)-\Delta^{k}_{i}(\theta^{\prime})\|_{2}\|v-v^{\prime}\|_{\Pi}]$
$\displaystyle\overset{(ii)}{\leq}C_{M}\rho^{j-i}{\mathbb{E}}[\tfrac{\varsigma}{2}\|v-v^{\prime}\|_{\Pi}^{2}+\tfrac{1}{2\varsigma}\|\Delta^{k}_{i}(\theta)-\Delta^{k}_{i}(\theta^{\prime})\|_{2}^{2}]$
$\displaystyle\overset{(iii)}{\leq}\tfrac{3\varsigma}{2}C_{M}\rho^{j-i}\|v-v^{\prime}\|_{\Pi}^{2}.$

where step (i) follows from Lemma 2, step (ii) follows from Young’s
inequality, and step (iii) follows from Lemma SM1.14. Then we can bound
$R_{3}$ as

$\displaystyle
R_{3}\leq\tfrac{N_{k}-n_{0}-\tau}{(N_{k}-n_{0})^{2}}\cdot\tfrac{3\varsigma
C_{M}\rho^{\tau}}{1-\rho}\|v-v^{\prime}\|_{\Pi}^{2}\overset{(i)}{\leq}\tfrac{2\varsigma^{2}}{N_{k}-n_{0}}\|v-v^{\prime}\|_{\Pi}^{2},$

where step (i) follows from that $\tau$ satisfies (81). Substituting the upper
bounds on $R_{1},R_{2}$ and $R_{3}$ into Ineq. (B.6) yields the desired
result.

###  B.7 Proof of Lemma 14

We have that

$\displaystyle\|{\mathbb{E}}[\widetilde{g}_{t}(\theta)|\mathcal{F}_{t-1}]-{\mathbb{E}}[\widetilde{g}_{t}(\theta^{\prime})|\mathcal{F}_{t-1}]-g(\theta)+g(\theta^{\prime})\|_{2}$
$\displaystyle\qquad\qquad\overset{(i)}{\leq}\tfrac{1}{m-m_{0}}\textstyle{\sum}_{j=m_{0}+1}^{m}\|{\mathbb{E}}[\widetilde{g}(\theta,\widehat{\xi}_{j}^{t})|\mathcal{F}_{t-1}]-{\mathbb{E}}[\widetilde{g}(\theta^{\prime},\widehat{\xi}_{j}^{t}))|\mathcal{F}_{t-1}]-g(\theta)+g(\theta^{\prime})\|_{2}$
$\displaystyle\qquad\qquad\overset{(ii)}{\leq}\tfrac{1}{m-m_{0}}\textstyle{\sum}_{j=m_{0}+1}^{m}C_{M}\rho^{j}\|v-v^{\prime}\|_{\Pi}\leq\tfrac{C_{M}\rho^{m_{0}}}{(1-\rho)(m-m_{0})}\|v-v^{\prime}\|_{\Pi},$

where step (i) follows from triangle inequality and step (ii) follows from
Lemma 2. ∎

###  B.8 Proof of Lemma 15

First, by the derivation of our original paper, we have that

$\displaystyle{\mathbb{E}}\|\underline{v}-\bar{v}\|_{\Pi}^{2}$
$\displaystyle={\mathbb{E}}\|(I_{d}-M)^{-1}B^{-\frac{1}{2}}\big{(}\widehat{g}(\widetilde{\theta})-g(\widetilde{\theta})\big{)}\|_{2}^{2}$
$\displaystyle\leq
2\underbrace{{\mathbb{E}}\|(I_{d}-M)^{-1}B^{-\frac{1}{2}}\big{(}\widehat{g}(\bar{\theta})-g(\bar{\theta})\big{)}\|_{2}^{2}}_{R_{1}}$
$\displaystyle\quad+2\underbrace{{\mathbb{E}}\|(I_{d}-M)^{-1}B^{-\frac{1}{2}}\big{(}\widehat{g}(\widetilde{\theta})-\widehat{g}(\bar{\theta})-g(\widetilde{\theta})+g(\bar{\theta})\big{)}\|_{2}^{2}}_{R_{2}}.$
(104)

We upper bound the two terms on the RHS of the above inequality separately. We
first define a sequence of samples obtained from a stationary Markov
trajectory, namely
$\widetilde{\xi}_{t}=(\widetilde{s}_{t},\widetilde{s}_{t+1},R(\widetilde{s}_{t},\widetilde{s}_{t+1}))$,
where $\widetilde{s}_{t}\sim\pi$. We write

$\displaystyle R_{1}$
$\displaystyle=\textstyle{\sum}_{j\in[D]}\mathbb{P}(s_{n_{0}+1}=j)\cdot{\mathbb{E}}_{s_{n_{0}+1}=j}\|(I_{d}-M)^{-1}B^{-\frac{1}{2}}\big{(}\widehat{g}(\bar{\theta})-g(\bar{\theta})\big{)}\|_{2}^{2}$
$\displaystyle\leq\textstyle{\sum}_{j\in[D]}\pi_{j}\cdot{\mathbb{E}}_{s_{n_{0}+1}=j}\|(I_{d}-M)^{-1}B^{-\frac{1}{2}}\big{(}\widehat{g}(\bar{\theta})-g(\bar{\theta})\big{)}\|_{2}^{2}$
$\displaystyle\qquad+\|\mathbb{P}(s_{n_{0}+1}=\cdot)-\pi\|_{\infty}\cdot{\mathbb{E}}_{s_{n_{0}+1}=j}\|(I_{d}-M)^{-1}B^{-\frac{1}{2}}\big{(}\widehat{g}(\bar{\theta})-g(\bar{\theta})\big{)}\|_{2}^{2}$
$\displaystyle\overset{(i)}{\leq}2{\mathbb{E}}\|(I_{d}-M)^{-1}B^{-\frac{1}{2}}\tfrac{1}{N_{k}-n_{0}}\textstyle{\sum}_{i=n_{0}+1}^{N_{k}}\big{(}\widetilde{g}(\bar{\theta},\widetilde{\xi}_{i})-g(\bar{\theta})\big{)}\|_{2}^{2}$
$\displaystyle=\tfrac{2}{(N_{k}-n_{0})^{2}}\left[(N_{k}-n_{0})\mu_{0}+\textstyle{\sum}_{i=1}^{N_{k}-n_{0}-1}2(N_{k}-n_{0}-i)\mu_{i}\right],$
(105)

where step (i) follows from condition (79) and the fact that
$\widetilde{\xi}_{i}$ is a stationary chain, and

$\mu_{i}:={\mathbb{E}}\left\langle(I_{d}-M)^{-1}B^{-\frac{1}{2}}\big{(}\widetilde{g}(\bar{\theta},\widetilde{\xi}_{0})-g(\bar{\theta})\big{)},(I_{d}-M)^{-1}B^{-\frac{1}{2}}\big{(}\widetilde{g}(\bar{\theta},\widetilde{\xi}_{i})-g(\bar{\theta})\big{)}\right\rangle.$

Recall the definition of the Markovian noise stochastic error term

$\bar{\Sigma}_{\mathsf{Mkv}}:=\sum_{t=-\infty}^{\infty}B^{-\frac{1}{2}}{\mathbb{E}}\left[\big{(}\widetilde{g}(\bar{\theta},\widetilde{\xi}_{t})-g(\bar{\theta})\big{)}\big{(}\widetilde{g}(\bar{\theta},\widetilde{\xi}_{0})-g(\bar{\theta})\big{)}^{\top}\right]B^{-\frac{1}{2}}.$

Then we have
$\mathrm{trace}\big{\\{}(I_{d}-M)^{-1}\bar{\Sigma}_{\mathsf{Mkv}}(I_{d}-M)^{-\top}\big{\\}}=\mu_{0}+2\textstyle{\sum}_{i=1}^{\infty}\mu_{i}.$
Now let us discuss the two possible cases:
Case 1 ($v^{*}=\bar{v}$): Let $\widetilde{\mathcal{F}_{i}}$ denote the
$\sigma$-field generated by samples
$\widetilde{\xi}_{0},...,\widetilde{\xi}_{i}$ and let
$\widetilde{\Pi}_{j}^{i}:=\operatorname{diag}\\{[\mathbb{P}(\widetilde{s}_{j}=1|\widetilde{s}_{i}),...,\mathbb{P}(\widetilde{s}_{j}=D|\widetilde{s}_{i})]\\}$
for $j\geq i$. Then we have

$\displaystyle\mu_{i}$
$\displaystyle={\mathbb{E}}\left\langle(I_{d}-M)^{-1}B^{-\frac{1}{2}}\big{(}\widetilde{g}(\bar{\theta},\widetilde{\xi}_{0})-g(\bar{\theta})\big{)},(I_{d}-M)^{-1}B^{-\frac{1}{2}}\big{(}{\mathbb{E}}[\widetilde{g}(\bar{\theta},\widetilde{\xi}_{i})|\widetilde{\mathcal{F}}_{0}]-g(\bar{\theta})\big{)}\right\rangle$
$\displaystyle={\mathbb{E}}\left\langle(I_{d}-M)^{-1}B^{-\frac{1}{2}}\big{(}\widetilde{g}(\bar{\theta},\widetilde{\xi}_{0})-g(\bar{\theta})\big{)},(I_{d}-M)^{-1}B^{-\frac{1}{2}}\Psi(\widetilde{\Pi}_{j}^{i}-\Pi)(\Psi^{\top}\bar{\theta}-\gamma
P\Psi^{\top}\bar{\theta}-r)\right\rangle$ $\displaystyle\overset{(i)}{=}0,$

where step (i) follows from that $v^{*}=\bar{v}=\Psi^{\top}\bar{\theta}$ and
the Bellman equation (1). As a result, we can conclude that

$\displaystyle
R_{1}\leq\tfrac{2\mu_{0}}{N_{k}-n_{0}}=\tfrac{2\cdot\mathrm{trace}\big{\\{}(I_{d}-M)^{-1}\bar{\Sigma}_{\mathsf{Mkv}}(I_{d}-M)^{-\top}\big{\\}}}{N_{k}-n_{0}}=\tfrac{2\cdot\mathrm{trace}\big{\\{}(I_{d}-M)^{-1}\bar{\Sigma}_{\mathsf{iid}}(I_{d}-M)^{-\top}\big{\\}}}{N_{k}-n_{0}}.$
(106)

Case 2 ($\bar{v}\neq v^{*}$): By Holder’s inequality, we have that
$|\mu_{i}|\leq|\mu_{0}|=\mathrm{trace}\big{\\{}(I_{d}-M)^{-1}\bar{\Sigma}_{\mathsf{iid}}(I_{d}-M)^{-\top}\big{\\}}$.
On the other hand, for $i\geq 1$, we can obtain another bound for $\mu_{i}$ as

$\displaystyle|\mu_{i}|$
$\displaystyle=|{\mathbb{E}}\langle(I_{d}-M)^{-1}B^{-\frac{1}{2}}\big{(}\widetilde{g}(\bar{\theta},\widetilde{\xi}_{0})-g(\bar{\theta})\big{)},(I_{d}-M)^{-1}B^{-\frac{1}{2}}{\mathbb{E}}[g(\bar{\theta},\widetilde{\xi}_{i})-g(\bar{\theta})|\mathcal{F}_{0}]\rangle|$
$\displaystyle\leq
C_{M}\rho^{i}\tfrac{1}{(1-\gamma)\sqrt{\mu}}{\mathbb{E}}[\|(I_{d}-M)^{-1}B^{-\frac{1}{2}}\big{(}\widetilde{g}(\bar{\theta},\widetilde{\xi}_{0})-g(\bar{\theta})\big{)}\|_{2}\|\bar{v}-v^{*}\|_{\Pi}]$
$\displaystyle\leq C_{M}\rho^{i}W,$ (107)

where
$W:=\tfrac{1}{2}\mathrm{trace}\big{\\{}(I_{d}-M)^{-1}\bar{\Sigma}_{\mathsf{iid}}(I_{d}-M)^{-\top}\big{\\}}+\tfrac{1}{2(1-\gamma)^{2}\mu}\|\bar{v}-v^{*}\|_{\Pi}^{2}$.
From Ineq. (106), we have

$\displaystyle R_{1}$
$\displaystyle\leq\tfrac{2\big{[}(N_{k}-n_{0})\mathrm{trace}\big{\\{}(I_{d}-M)^{-1}\bar{\Sigma}_{\mathsf{Mkv}}(I_{d}-M)^{-\top}\big{\\}}-\textstyle{\sum}_{i=1}^{N_{k}-n_{0}-1}i\mu_{i}-2(N_{k}-n_{0})\textstyle{\sum}_{i=N_{k}-n_{0}}^{\infty}\mu_{i}\big{]}}{(N_{k}-n_{0})^{2}}$
$\displaystyle\leq\tfrac{2\big{[}(N_{k}-n_{0})\mathrm{trace}\big{\\{}(I_{d}-M)^{-1}\bar{\Sigma}_{\mathsf{Mkv}}(I_{d}-M)^{-\top}\big{\\}}+\overbrace{|\textstyle{\sum}_{i=1}^{N_{k}-n_{0}-1}i\mu_{i}|}^{I_{1}}+2(N_{k}-n_{0})\overbrace{|\textstyle{\sum}_{i=N_{k}-n_{0}}^{\infty}\mu_{i}|}^{I_{2}}\big{]}}{(N_{k}-n_{0})^{2}}.$
(108)

It remains to bound $I_{1}$ and $I_{2}$. We write

$\displaystyle I_{1}$
$\displaystyle\leq\textstyle{\sum}_{i=1}^{\tau}\tau|\mu_{i}|+\textstyle{\sum}_{i=\tau+1}^{\infty}i|\mu_{i}|$
$\displaystyle\leq\tau^{2}\mathrm{trace}\big{\\{}(I_{d}-M)^{-1}\bar{\Sigma}_{\mathsf{iid}}(I_{d}-M)^{-\top}\big{\\}}+C_{M}W\textstyle{\sum}_{i=\tau+1}^{\infty}i\cdot\rho^{i}$
$\displaystyle\leq\tau^{2}\mathrm{trace}\big{\\{}(I_{d}-M)^{-1}\bar{\Sigma}_{\mathsf{iid}}(I_{d}-M)^{-\top}\big{\\}}+\tfrac{C_{M}[(\tau+1)\rho^{\tau+1}+\rho^{\tau+2}/(1-\rho)]}{1-\rho}\cdot
W.$

For $I_{2}$, we have

$\displaystyle
I_{2}\leq\textstyle{\sum}_{i=N_{k}-n_{0}}^{\infty}|\mu_{i}|\leq\tfrac{C_{M}\rho^{N_{k}-n_{0}}}{1-\rho}W.$

Substituting the upper bounds on $I_{1}$ and $I_{2}$ and invoking that
$\rho^{\tau}\leq\frac{2(1-\rho)^{2}}{5C_{M}}$ and
$\rho^{N_{k}-n_{0}}\leq\tfrac{\tau(1-\rho)}{5C_{M}(N_{k}-n_{0})}$, we obtain

$\displaystyle R_{1}$
$\displaystyle\leq\tfrac{2\cdot\mathrm{trace}\big{\\{}(I_{d}-M)^{-1}\bar{\Sigma}_{\mathsf{Mkv}}(I_{d}-M)^{-\top}\big{\\}}}{N_{k}-n_{0}}+\tfrac{2\tau^{2}\mathrm{trace}\big{\\{}(I_{d}-M)^{-1}\bar{\Sigma}_{\mathsf{iid}}(I_{d}-M)^{-\top}\big{\\}}}{(N_{k}-n_{0})^{2}}+\tfrac{4(\tau+1)}{5(N_{k}-n_{0})^{2}}W.$

On the other hand, by Lemma 15, we can bound $R_{2}$ as

$\displaystyle
R_{2}\leq\tfrac{4(\tau+1)\varsigma^{2}}{(1-\gamma)^{2}\mu(N_{k}-n_{0})}\|\widetilde{v}-\bar{v}\|_{\Pi}^{2}.$

Substituting the bounds on $R_{1}$ and $R_{2}$ into Ineq. (B.8) yields the
desired results for both cases.