\section*{\bibname}}
\usepackage{apalike}

\usepackage{geometry}
\geometry{verbose,tmargin=1in,bmargin=1in,lmargin=1in,rmargin=1in}
\hypersetup{
	colorlinks,linkcolor=red,anchorcolor=blue,citecolor=blue}
\setlength{\parindent}{0pt}
\usepackage{multirow}


\usepackage{authblk}

\makeatletter
\newcommand{\printfnsymbol}[1]{%
	\textsuperscript{\@fnsymbol{#1}}%
}
\makeatother



\begin{document}
	
\title{Sample Complexity Bounds for Two Timescale Value-based Reinforcement Learning Algorithms}

\author[ ]{Tengyu Xu, Yingbin Liang}
\affil[ ]{Department of Electrical and Computer Engineering, The Ohio State University}
\affil[ ]{\{xu.3260, liang.889\}@osu.edu}

\date{}
\maketitle

\begin{abstract}
Two timescale stochastic approximation (SA) has been widely used in value-based reinforcement learning algorithms. In the policy evaluation setting, it can model the linear and nonlinear temporal difference learning with gradient correction (TDC) algorithms as linear SA and nonlinear SA, respectively. In the policy optimization setting, two timescale nonlinear SA can also model the greedy gradient-Q (Greedy-GQ) algorithm. In previous studies, the non-asymptotic analysis of linear TDC and Greedy-GQ has been studied in the Markovian setting, with diminishing or accuracy-dependent stepsize. For the nonlinear TDC algorithm, only the asymptotic convergence has been established. In this paper, we study the non-asymptotic convergence rate of two timescale linear and nonlinear TDC and Greedy-GQ under Markovian sampling and with accuracy-independent constant stepsize. For linear TDC, we provide a novel non-asymptotic analysis and show that it attains an $\epsilon$-accurate solution with the optimal sample complexity of $\mathcal{O}(\epsilon^{-1}\log(1/\epsilon))$ under a constant stepsize. For nonlinear TDC and Greedy-GQ, we show that both algorithms attain $\epsilon$-accurate stationary solution with sample complexity $\mathcal{O}(\epsilon^{-2})$. It is the first non-asymptotic convergence result established for nonlinear TDC under Markovian sampling and our result for Greedy-GQ outperforms the previous result orderwisely by a factor of $\mathcal{O}(\epsilon^{-1}\log(1/\epsilon))$.
\end{abstract}

\section{Introduction}

Two timescale stochastic approximation (SA) algorithms have wide applications in reinforcement learning (RL) \cite{sutton2018reinforcement}. Typically, two timescale SA algorithms involve iterations of two types of variables updated at different speeds, i.e., the stepsizes for two iterates are chosen differently so that one iterate runs much faster than the other \cite{borkar1997stochastic,borkar2009stochastic}. Such algorithms are widely used to solve both policy evaluation and policy optimization problems in RL, in which the goal of policy evaluation is to estimate the expected total reward (i.e. value function) of a target policy, and the goal of policy optimization is to search for a policy with the optimal expected total reward.

In the policy evaluation problem, temporal difference (TD) learning \cite{sutton1988learning} is one of the most widely used algorithms when a linear function class is utilized to approximate the value function. However, in the off-policy setting, in which the target policy to be evaluated is different from the behavior policy that generates samples, TD learning may diverge to infinity. To overcome such an issue, \cite{sutton2009fast} proposed the two timescale linear TD with gradient correction (TDC) algorithm, which has convergence guarantee in the off-policy setting. The two timescale linear TDC is a special case of two timescale linear SA, whose asymptotic convergence has been established in \cite{sutton2009fast,borkar2009stochastic} and \cite{yu2017convergence,tadic2004almost,yaji2016stochastic} for the i.i.d. and Markovian settings, respectively. The non-asymptotic convergence rate of two timescale linear TDC/SA has also been studied. In the i.i.d. setting, under diminishing stepsize, \cite{dalal2017finite} established the sample complexity of $\mathcal{O}(\epsilon^{-1.5})$, and an improved complexity of $\mathcal{O}(\epsilon^{-1})$ was later established in \cite{dalal2019tale}. In the Markovian setting, \cite{xu2019two} established the complexity of $\mathcal{O}(\epsilon^{-1.5}\log^2(1/\epsilon))$ under a diminishing stepsize, and \cite{gupta2019finite} established the complexity of $\mathcal{O}(\epsilon^{-1-\zeta}\log^2(1/\epsilon))$ under a $\epsilon$-dependent stepsize, where $\zeta$ can be an arbitrarily small positive constant. Recently, \cite{kaledin2020finite} provides a tighter complexity bound of $\mathcal{O}(\epsilon^{-1})$ for two timescale linear SA under a diminishing stepsize. Although having progressed significantly, existing convergence guarantee were established either under a {\em diminishing} stepsize or a drastically small {\em $\epsilon$-level} stepsize, which yield very slow convergence and are rarely used in practice.
\begin{list}{$\bullet$}{\topsep=0.ex \leftmargin=0.15in \rightmargin=0.in \itemsep =0.01in}
	\item {\em Thus, the first goal of this paper is to investigate the two timescale linear TDC {\bf under a constant stepsize (not $\epsilon$-dependent)}, which is commonly adopted in practice, and to provide the finite-sample convergence guarantee for such a case. This necessarily requires a new approach differently from the existing ones. }

\end{list}

When a nonlinear function is utilized to approximate the value function, TD learning still suffers from the divergence issue \cite{tsitsiklis1996analysis}. To address that, \cite{bhatnagar2009convergent} proposed the two timescale nonlinear TDC, which can be modeled as a two timescale nonlinear SA. 
The asymptotic convergence of two timescale nonlinear SA has been well established in \cite{borkar1997stochastic,tadic2004almost,karmakar2018two}. However, the non-asymptotic convergence of two timescale nonlinear SA has only been established in the i.i.d.\ setting under some restrict assumptions such as global (local) stability and local linearizion \cite{borkar2018concentration,mokkadem2006convergence}. 
So far, the non-asymptotic convergence performance of two timescale nonlinear TDC has not been studied under the general Markovian sampling.
\begin{list}{$\bullet$}{\topsep=0.ex \leftmargin=0.15in \rightmargin=0.in \itemsep =0.01in}
	\item {\em The second goal of this paper is to provide the first non-asymptotic convergence analysis for two timescale nonlinear TDC with a constant stepsize, under {\bf Markovian sampling}, and without restricted assumptions.}
\end{list}

Moreover, in the policy optimization problem, Q-learning \cite{watkins1992q} has been widely used and has achieved significant success in practice. However, in the function approximation setting, Q-learning does not have convergence guarantee \cite{baird1995residual} unless under some restricted regularity assumptions \cite{melo2008analysis, zou2019finite, cai2019neural}. In corresponding to this, \cite{maei2010gq} proposed the Greedy-GQ algorithm in the linear function approximation setting, in which the algorithm is guaranteed to converge to a locally optimal policy without restricted assumptions. Similarly to nonlinear TDC algorithms, Greedy-GQ also adopts a two timescale update scheme, and is a special case of two timescale nonlinear SA. Under single-sample update and Markovian sampling, \cite{wang2020finite} provided the non-asymptotic convergence rate of Greedy-GQ with diminishing stepsize, which achieves the complexity of $\mathcal{O}(\epsilon^{-3}\log(\epsilon^{-1}))$. However, such a rate does not attain the typical complexity order of nonconvex optimization, and can be potentially improved with a larger stepsize.
\begin{list}{$\bullet$}{\topsep=0.ex \leftmargin=0.15in \rightmargin=0.in \itemsep =0.01in}
	\item {\em The last focus of this paper is to provide an improved non-asymptotic convergence rate for two timescale Greedy-GQ under a constant stepsize.}
\end{list}

\subsection{Our Contributions}

For two timescale linear TDC, we show that it achieves the sample complexity of $\mathcal{O}(\epsilon^{-1}\log(\epsilon^{-1}))$, which has the optimal dependence on $\epsilon$ due to the lower bound given in \cite{dalal2019tale}. Such a rate has been established in \cite{kaledin2020finite}, but only under a {\em diminishing} stepsize, which is rarely used in practice due to the slow empirical performance. In contrast, our guarantee is established under a {\bf constant (not $\epsilon$-dependent) stepsize}, which is commonly used in practice. Our analysis approach leverages the mini-batch sampling for each iteration to control the convergence error, which is significantly different from that in \cite{kaledin2020finite}, and can be of independent interest.

For two timescale nonlinear TDC, we establish the first non-asymptotic convergence rate under {\bf Markovian sampling}. We show that the mini-batch two timescale nonlinear TDC algorithm achieves the sample complexity of $\mathcal{O}(\epsilon^{-2})$.

For two timescale Greedy-GQ, we 
show that mini-batch two timescale Greedy-GQ with a constant stepsize and under Markovian sampling achieves the sample complexity of $\mathcal{O}(\epsilon^{-2})$. Our result orderwisely outperforms the previous result of Greedy-GQ with diminishing stepsize in \cite{wang2020finite} by a factor of $\mathcal{O}(\epsilon^{-1}\log(1/\epsilon))$.

\subsection{Related Work}
Due to the vast amount of studies on SA and value-based RL algorithms, we include here only the studies that are highly related to our work.

\textbf{Policy evaluation with {\em linear} function approximation.} In the on-policy setting, TD learning \cite{sutton1988learning} has been proposed to solve the policy evaluation problem in the linear function approximation setting. The non-asymptotic convergence rate of TD learning has been established in \cite{dalal2018finite} for the i.i.d. setting and in \cite{bhandari2018finite,srikant2019finite,hu2019characterizing} for the Markovian setting. \cite{cai2019neural} explored the linearizable structure of neural networks in the overparameterized regime, and studied the non-asymptotic convergence rate of TD learning with neural network approximation.
\cite{zou2019finite} studied the convergence rate of SARSA with linear function approximation in the Markovian setting, which can been viewed as a policy evaluation with dynamic changing transition kernel.

In the off-policy setting, GTD, GTD2 and TDC have been proposed to solve the divergence issue of TD learning \cite{sutton2008convergent,sutton2009fast,maei2011gradient}. The convergence rate of one timescale GTD and GTD2 algorithms has been established in \cite{liu2015finite} by converting the objective into a convex-concave saddle problem in the i.i.d. setting, and was further generalized to the Markovian setting in \cite{wang2017finite}. For two timescale linear TDC, in the i.i.d.\ setting, the non-asymptotic analysis was provided in \cite{dalal2017finite,dalal2019tale}. In the Markovian setting, the non-asymptotic convergence rate was first established in \cite{xu2019two} under diminishing stepsize and in \cite{gupta2019finite} under constant stepsize. The result in \cite{xu2019two} was later improved by \cite{kaledin2020finite} to achieve the optimal convergence rate.


\textbf{Policy evaluation with {\em nonlinear} function approximation.}
Two timescale nonlinear TDC is proposed by \cite{bhatnagar2009convergent}, in which a smooth nonlinear function is utilized to approximate the value function. Nonlinear TDC with i.i.d.\ samples is a special case of two time-scale nonlinear SA with martingale noise, whose asymptotic convergence has been established in \cite{bhatnagar2009convergent,maei2011gradient} by using asymptotic convergence results in nonlinear SA \cite{borkar1997stochastic,borkar2009stochastic,tadic2004almost}. Under the global/local asymptotic stability assumptions or local linearizion assumption, the non-asymptotic convergence of two timescale nonlinear SA with martingale noise has been studied in \cite{borkar2018concentration}. Under certain stability assumptions, the asymptotic convergence of two timescale nonlinear SA with Markov noise was established in \cite{karmakar2016asymptotic,karmakar2018two}. 
A concurrent study \cite{qiu2020single} also investigated nonlinear TDC and obtained the same sample complexity of $\mathcal{O}(\epsilon^{-2})$ as our result. However, \cite{qiu2019finite} only considered the i.i.d. setting, whereas we considered the more general Markovian setting.

\textbf{Policy optimization with {\em linear} function approximation.}
Q-learning \cite{watkins1992q} is one of the most widely used value-based policy optimization algorithms. The asymptotic and non-asymptotic convergence have been established for Q-learning with linear function approximation in \cite{melo2008analysis} and \cite{zou2019finite}, respectively, under certain regularity assumption. Under a similar regularity assumption, \cite{cai2019neural} established the convergence rate of Q-Learning in the neural network approximation setting. However, without regularity assumptions, Q-Learning does not have convergence guarantee in the function approximation setting.
\cite{maei2010toward} proposed two timescale Greedy-GQ to solve the divergence issue of Q-Learning with linear function approximation, and the asymptotic convergence of Greedy-GQ was also established therein. Recently, \cite{wang2020finite} studied the non-asymptotic convergence rate of Greedy-GQ under diminishing stepsize in the Markovian setting. In this paper, we provide an orderwisely better convergence rate than that in \cite{wang2020finite}.

\section{Markov Decision Process}\label{sc: mdp}

Consider a Markov decision process (MDP) denoted $(\mathcal S, \mathcal A, \mathsf{P},r,\gamma)$. Here, $\mathcal S\subset \mathbb{R}^d$ is a state space, $\mathcal A$ is an action set, $\mathsf{P}=\mathsf{P}(s^\prime|s,a)$ is the transition kernel,  $r(s, a, s^\prime)$ is the reward function bounded by $r_{\max}$, and $\gamma\in(0,1)$ is the discount factor. A stationary policy $\pi$ maps a state $s\in \mathcal S$ to a probability distribution $\pi(\cdot|s)$ over the action space $\mathcal A$. At time-step $t$, suppose the process is in some state $s_t\in \mathcal S$. Then an action $a_t\in \mathcal A$ is taken based on the distribution $\pi(\cdot|s_t)$, the system transitions to a next state $s_{t+1}\in \mathcal S$ governed by the transition kernel $\mathsf{P}(\cdot|s_t,a_t)$, and a reward $r_t=r(s_t, a_t, s_{t+1})$ is received. We assume the associated Markov chain $p(s^\prime|s)=\sum_{a\in\mathcal A}p(s^\prime|s,a)\pi(a|s)$ is ergodic, and let $\mu_\pi$ be the induced stationary distribution of this MDP, i.e., $\sum_{s}p(s^\prime|s)\mu_{\pi}(s)=\mu_{\pi}(s^\prime)$. The state value function for policy $\pi$ is defined as: $V^\pi\left(s\right)=\mathbb E[\sum_{t=0}^{\infty}\gamma^t r(s_t,a_t, s_{t+1})|s_0=s,\pi]$, and the state-action value function is defined as: $Q^\pi(s,a)=\mathbb E[\sum_{t=0}^{\infty}\gamma^t r(s_t,a_t, s_{t+1})|s_0=s, a_0=a, \pi]$. It is known that $V^\pi(s)$ is the unique fixed point of the Bellman operator $T^\pi$, i.e., $V^\pi(s) = T^\pi V^\pi(s)\coloneqq r^\pi(s)+\gamma\mathbb E_{s^\prime |s} V^\pi(s^\prime)$, where $r^\pi(s)=\mathbb E_{a, s^\prime|s}r(s,a,s^\prime)$ is the expected reward of the Markov chain induced by the policy $\pi$. We take the following standard assumption for the MDP in this paper, which has also been adopted in previous works \cite{bhandari2018finite,zou2019finite,srikant2019finite,xu2019two,xu2020reanalysis}.

\begin{assumption}[Geometric ergodicity]\label{ass1}
	There exist constants $\kappa>0$ and $\rho\in(0,1)$ such that
	\begin{flalign*}
	\sup_{s\in\mathcal S}d_{TV}(\mathbb P(s_t|s_0=s),\mu_{\pi_b})\leq \kappa\rho^t, \forall t\geq 0,
	\end{flalign*}
	where $\mathbb P(s_t|s_0=s)$ is the distribution of $s_t$ conditioned on $s_0=s$ and $d_{TV}(P,Q)$ denotes the total-variation distance between the probability measures $P$ and $Q$.
\end{assumption}
\Cref{ass1} holds for any time-homogeneous Markov chain with finite state space and any uniformly ergodic Markov chain with general state space \cite{bhandari2018finite,zou2019finite,xu2019two}.

\section{Two Timescale TDC with Linear Function Approximation}\label{sc: linearTDC}
In this section we first introduce the two timescale linear TDC algorithm to solve the policy evaluation problem, and then present our convergence rate result.

\subsection{Algorithm}

When $\mathcal S$ is large or infinite, a linear function $\hat{v}(s,\theta)=\phi(s)^\top\theta$ is often used to approximate the value function $V^\pi(s)$, where $\phi(s)\in\mathbb{R}^d$ is a fixed feature vector for state $s$ and $\theta\in\mathbb{R}^d$ is a parameter vector. We can also write the linear approximation in the vector form as $\hat{v}(\theta)={\rm \Phi} \theta$, where ${\rm \Phi}$ is the $|\mathcal S|\times d$ feature matrix. Without loss of generality, we assume that the feature vector $\ltwo{\phi(s)}\leq 1$ for all $s\in\mathcal S$ and the columns of the feature matrix $\Phi$ are linearly independent. 
Here we consider policy evaluation problem in the off-policy setting. Namely, a sample path $\{ (s_t,a_t,s_{t+1}) \}_{t\geq 0}$ is generated by the Markov chain according to a behavior policy $\pi_b$, but our goal is to obtain the value function of a target policy $\pi$, which is different from $\pi_b$. 

To find a parameter $\theta^*\in\mathbb{R}^d$ with $ \mathbb E_{\mu_{\pi_b}}\hat{v}(s,\theta^*)= \mathbb E_{\mu_{\pi_b}}T^\pi\hat{v}(s,\theta^*)$. The linear TDC algorithm \cite{sutton2009fast} updates the parameter by minimizing the mean-square projected Bellman error (MSPBE) objective, defined as
\begin{flalign*}
J(\theta)&=\mathbb E_{\mu_{\pi_b}}[\hat{v}(s,\theta)-{\rm \Pi} T^\pi\hat{v}(s,\theta)]^2,
\end{flalign*}
where ${\rm \Pi}$ is the orthogonal projection operation onto the function space $\hat{\mathcal V}=\{\hat{v}(\theta)\  |\  \theta\in\mathbb{R}^d\  \text{and}\ \hat{v}(\cdot, \theta)=\phi(\cdot)^\top \theta   \}$. When the columns of the feature matrix $\Phi$ are linearly independent, \cite{sutton2009fast} shows that $J(\theta)$ is strongly convex and has $\theta^*=-A^{-1}b$ as its global minimum, i.e., $J(\theta^*)=0$, where $A=\mathbb E_{\mu_{\pi_b}}[(\gamma\mathbb E_\pi[\phi(s^\prime)|s]-\phi(s))\phi(s)]$ and $b=\mathbb E_{\mu_{\pi_b}}[\mathbb E_\pi[r(s,a,s^\prime)|s]\phi(s)]$. A convenient way to find $\theta^*$ is to minimize the MSPBE objective function $J(\theta)$ using the gradient descent method: $\theta_{t+1}=\theta_t - \frac{\alpha}{2} \nabla J(\theta_t)$, where $\alpha>0$ is the stepsize and the gradient $\nabla J(\theta)$ was derived by \cite{bhatnagar2009convergent} as follows:
{\begin{flalign}\label{linear-TDCupdate}
	-\frac{1}{2}\nabla J(\theta) = \mathbb E_{\mu_{\pi_b}}[\mathbb E_\pi[\delta(\theta)|s]\phi(s)]-\gamma\mathbb E_{\mu_{\pi_b}}[ \mathbb E_\pi[\phi(s^\prime)|s]\phi(s)^\top ]w(\theta),
	\end{flalign}}
where $\delta(\theta)=r(s,a,s^\prime) + \gamma \hat{v}(s^\prime,\theta) - \hat{v}(s,\theta)$ is the temporal difference error, $w(\theta)\coloneqq \mathbb E_{\mu_{\pi_b}}[\phi(s)\phi(s)^\top]^{-1}\mathbb E_{\mu_{\pi_b}}[ \mathbb E_\pi[\delta(\theta)|s]\phi(s)]$.
In practice, stochastic gradient descent (SGD) method is usually adopted to perform the update in \cref{linear-TDCupdate} approximately. However, directly sampling is not applicable to $w(\theta)$. To solve such an issue, an auxiliary parameter $w_t$ can be introduced to estimate the vector $w(\theta_t)$, i.e., $w_t\approx w(\theta_t)$, by solving a linear SA with the following corresponding ODE:
\begin{flalign*}
\dot{w}=-\mathbb E_{\mu_{\pi_b}}[\phi(s)\phi(s)^\top]w + \mathbb E_{\mu_{\pi_b}}[\mathbb E_\pi[\delta(\theta)|s]\phi(s)].
\end{flalign*}

Given $w_t$, the parameter $\theta_t$ can then be updated with a stochastic approximation of $\nabla J(\theta_t)$ obtained via directly sampling:
\begin{flalign}
\theta_{t+1}=\theta_t + \alpha \frac{1}{\lone{\mathcal B_t}}\sum_{j\in \mathcal B_t}g(\theta_t, w_t,x_j),\label{eq: linearTDC_stoc}
\end{flalign}
where $\mathcal B_t$ is the mini-batch sampled from the MDP, $g(\theta_t, w_t,x_j)=\rho(s_j, a_j)(\delta_j(\theta_t)\phi(s_j)-\gamma\phi(s_{j+1})\phi(s_j)^\top w_t)$, $\rho(s,a)=\pi(a|s)/\pi_b(a|s)$ is the importance weighting factor with $\rho_{\max}$ being its maximum value, and $x_j$ denotes the sample $(s_j,a_j,s_{j+1})$.

\Cref{al: linearTDC} is an {\bf online }algorithm based on a {\bf single sample path}. \Cref{al: linearTDC} adopts a two timescale update scheme, in which parameters $\theta_t$ and $w_t$ are updated simultaneously but with different stepsizes. Specifically, the main parameter $\theta_t$ iterates at a slow timescale with a smaller stepsize, and the auxiliary parameter $w_t$ iterates at a fast timescale with a larger stepsize. By doing so, $w_t$ can be close to $w(\theta_t)$ asymptotically, so that $\theta_t$ is updated approximately in the direction of $-\nabla J(\theta)$. 
\Cref{al: linearTDC} utilizes an accuracy-independent constant stepsize, i.e., $\alpha, \beta=\mathcal{O}(1)$ for both the updates of $\theta_t$ and $w_t$, and a mini-batch of samples $\{ (s_j, a_j, s_{j+1}) \}_{i_t\leq j\leq i_t+M-1}$ are taken sequentially from the trajectory at each iteration to perform the update. As we will show later, linear TDC in this setting is guaranteed to converge to the global optimal with an arbitrary accuracy level.


\begin{algorithm}[H]
	\null
	\caption{Two Timescale Linear TDC}
	\label{al: linearTDC}
	\begin{algorithmic}[1]
		\STATE {\bfseries Input:} batch size $M$, learning rate $\alpha$ and $\beta$
		\STATE {\bfseries Sampling:} A trajectory $\{ s_j, a_j\}_{j\geq 0}$ is sampled by following the behaviour policy $\pi_b$
		\STATE \textbf{Initialization: } $\theta_0$ and $w_0$
		\FOR{$t=0,\cdots,T-1$}
		\STATE $i_t=tM$
		\STATE $w_{t+1} = w_t + \beta\frac{1}{M}\sum_{j=i_t}^{i_t+M-1}(-\phi(s_j)\phi(s_j)^\top w_t + \rho(s_j, a_j)\delta_j(\theta_t)\phi(s_j))$
		\STATE $\theta_{t+1}=\theta_t + \alpha\frac{1}{M}\sum_{j=i_t}^{i_t+M-1} \rho(s_j, a_j)(\delta_j(\theta_t)\phi(s_j)-\gamma \phi(s_{j+1})\phi(s_j)^\top w_t)$
		\ENDFOR
		\STATE {\bfseries Output:} $\theta_T$
	\end{algorithmic}
\end{algorithm}

\subsection{Convergence Analysis}
We define matrix $C=-\mathbb E_{\mu_{\pi_b}}[\phi(s)\phi(s)^\top]$. Let $\lambda_1=\lone{\lambda_{\max}(A^\top C^{-1} A)}$, $\lambda_2=\lone{\lambda_{\max}(C)}$ and $R_\theta=\ltwo{\theta^*}$. The following theorem provides the convergence rate and sample complexity of \Cref{al: linearTDC}.
\begin{theorem}\label{thm1}
	Suppose \Cref{ass1} hold. Consider \Cref{al: linearTDC} of two timescale linear TDC update. Let the stepsize $\alpha\leq \min\left\{ \frac{1}{8\lambda_1}, \frac{\lambda_1\lambda_2}{12}, \frac{\sqrt{\lambda_2\beta}}{4\sqrt{6}\rho_{\max}} \frac{\lambda_2\sqrt{\lambda_2}\beta}{16\rho^2_{\max}}, \frac{\lambda_1\lambda_2\beta}{64\rho^2_{\max}}, \frac{\lambda_1\lambda^2_2\beta}{768}  \right\}$, $\beta \leq  \min\left\{ \frac{1}{8\lambda_2}, \frac{\lambda_2}{4}\right\}$ and the batch size $M\geq 128\left( \rho^2_{\max} + \frac{1}{\lambda^2_2} \right)\frac{1+(\kappa-1)\rho}{1-\rho}\max\left\{1,\frac{8\beta+8\lambda_2\beta^2}{\lambda_1\lambda_2\alpha}, \frac{8+12\lambda_1\alpha}{\lambda_1} \right\}$. Then we have
	{\small \begin{flalign}
		&\mathbb E[\ltwo{\theta_{T}-\theta^*}^2] \leq \left(1- \frac{\min\{  \lambda_1\alpha, \lambda_2\beta \}}{8} \right)^{T}\Delta_0 + \frac{A_1}{M},\label{eq: thm1_ub}
		\end{flalign}}where $\Delta_0 = \ltwo{w_0 - w^*(\theta_0)}^2 + \ltwo{\theta_0 - \theta^*}^2$, where $A_1$ is a constant defined in \cref{eq: 32} in \Cref{sc: proflemma1}. Furthermore, let $M\geq \frac{2A_1}{\epsilon}$ and $T\geq \frac{8}{\min\{  \lambda_1\alpha, \lambda_2\beta \}}\ln\left( \frac{2\Delta_0}{\epsilon} \right)$. The total sample complexity for \Cref{al: linearTDC} to achieve an $\epsilon$-accurate optimal solution $\theta^*$, i.e., $\mathbb E[\ltwo{\theta_T-\theta^*}^2]\leq \epsilon$, is given by
	{\small \begin{flalign*}
		TM=\Theta\left( \frac{1}{\epsilon}\log\left( \frac{1}{\epsilon} \right) \right).
		\end{flalign*}}
\end{theorem}
\Cref{thm1} shows that the convergence error of \Cref{al: linearTDC} consists of two terms: the first term is the transient error decreasing at an exponential rate, and the second term is the variance error that diminishes as the batch size $M$ increases. This is in contrast to the single-sample TDC under constant stepsizes, which suffers from the variance and bias errors with order $\mathcal{O}(\beta^2/\alpha)$ \cite{gupta2019finite}. Thus, $\epsilon$-level small stepsizes $\alpha$ and $\beta$ are required in single-sample TDC to reduce the variance error to achieve the required $\epsilon$-accurate optimal solution, which can slow down the practical convergence speed significantly. In contrast, mini-batch TDC can attain high accuracy with a large constant (not $\epsilon$-level) stepsize. Our result of $\mathcal{O}(\epsilon^{-1}\log(1/\epsilon))$ achieves the optimal complexity order due to the lower bound given in \cite{dalal2019tale}. In contrast to the same sample complexity established in \cite{kaledin2020finite}, which is applicable only under a diminishing stepsize, our result given in \Cref{thm1} is applicable under the constant stepsize, which is practically preferred due to the much better performance.


We next provide a sketch of the proof for \Cref{thm1}. 
\begin{proof}[{\bf Proof Sketch of \Cref{thm1}}]
	The proof of \Cref{thm1} consists of the following three steps. At $t$-th step, we call $\ltwo{\theta_t-\theta^*}^2$ as the training error and $\ltwo{w_t - w(\theta_t)}^2$ as the tracking error.
	
	\noindent\textbf{Step 1:} We establish the following induction relationships for the tracking error:
	\begin{flalign}\label{eq: sketch1}
	\mathbb E\left[ \ltwo{w_{t+1}-w(\theta_{t+1})}^2 \right]&\leq (1 - \Theta(\lambda_2\beta) +  \Theta(\alpha^2/\beta) )\mathbb E\left[ \ltwo{w_{t}-w(\theta_{t})}^2 \right] \nonumber\\
	&\quad + \Theta(\alpha^2/\beta + \lambda_1\alpha)\mathbb E[\ltwo{\theta_t - \theta^*}^2] + \Theta(1/M).
	\end{flalign}
	
	\noindent\textbf{Step 2:} We then establish the induction relationships for the training error:
	\begin{flalign}\label{eq: sketch2}
	\mathbb E\left[\ltwo{\theta_{t+1}-\theta^*}^2\right]&\leq ( 1 - \Theta(\lambda_1\alpha) + \Theta( \alpha^2))\mathbb E\left[\ltwo{\theta_{t}-\theta^*}^2\right] \nonumber\\
	&\quad + \Theta(\alpha + \alpha^2)\mathbb E\left[ \ltwo{w_{t}-w(\theta_{t})}^2 \right] + \Theta(1/M).
	\end{flalign}
	
	\noindent\textbf{Step 3:} Combing \cref{eq: sketch1} and \cref{eq: sketch2} and letting the stepsize $\alpha$ and $\beta$ and batch size $M$ satisfy the requirement specified in \Cref{thm1}, we establish the induction relationship of $\Delta_t =\mathbb E[\ltwo{\theta_{t}-\theta^*}^2] + \mathbb E[ \ltwo{w_{t}-w(\theta_{t})}^2]$ as follows:
	\begin{flalign}\label{eq: sketch3}
	\Delta_{t+1} \leq \left(1- \Theta(\min\{  \lambda_1\alpha, \lambda_2\beta \}) \right) \Delta_t + \Theta( 1/M).
	\end{flalign}
	Applying \cref{eq: sketch3} recursively from $t=T-1$ to $0$ yields the desired convergence result.
\end{proof}

\section{Two Timescale TDC with Nonlinear Function Approximation}\label{sc: nonlinearTDC}

In this section we first introduce the nonlinear two timescale TDC algorithm to solve the policy evaluation problem, then we provide our non-asymptotic convergence rate result.
\subsection{Algorithm}\label{sc: nonlineartd}

In this section we consider policy evaluation problem with nonlinear function approximation, in which a parameterized smooth {\em nonlinear} function $\hat{v}(s,\theta)$ is used to approximate the value function $V^\pi(s)$. \cite{bhatnagar2009convergent} proposed an algorithm to find a parameter for the approximator $\hat{v}(s,\theta)$, named nonlinear TDC.
The nonlinear TDC updates the parameter by minimizing the following mean-square projected Bellman error objective defined as:
\begin{flalign}
J(\theta)&=\mathbb E_{\mu_{\pi}}[\hat{v}(s,\theta)-{\rm \Pi}_\theta T^\pi \hat{v}(s,\theta)]^2,\label{mspbe1}
\end{flalign}
where ${\rm \Pi}_\theta$ is the orthogonal projection operation into the function space $\bar{\mathcal V}=\{\bar{V}(s,\zeta)\  |\  \zeta\in\mathbb{R}^d\  \text{and}\ \bar{v}(s, \zeta)=\phi_\theta(s)^\top \zeta \,\text{with}\, (\phi_\theta(s))_i=\nabla_{\theta_i}\hat{v}(s,\theta)   \}$.
In general, since $J(\theta)$ defined in \cref{mspbe1} is nonconvex with respect to the parameter $\theta$, finding the global minimum of $J(\theta)$ is NP-hard. However, we can still apply gradient descent method to find a local optimum (i.e., first-order stationary point) of $J(\theta)$, via updating the parameter $\theta$ iteratively as $\theta_{t+1}=\theta_t - \frac{\alpha_t}{2} \nabla J(\theta_t)$, where $\alpha_t>0$ is the stepsize and the gradient $\nabla J(\theta)$ was derived by \cite{bhatnagar2009convergent} as follows:
{\begin{flalign}\label{nonlinear-TDCupdate}
	-\frac{1}{2}\nabla J(\theta) = \mathbb E[\delta(\theta)\phi_\theta(s)]-\gamma\mathbb E[\phi_\theta(s^\prime)\phi_\theta(s)^\top ]w(\theta)-h(\theta,w(\theta)),
	\end{flalign}}
where $\delta(\theta)=r(s,a,s^\prime) + \gamma \hat{v}(s^\prime,\theta)-\hat{v}(s,\theta)$ is the temporal difference and
{\begin{flalign*}
	&w(\theta)\coloneqq \mathbb E[\phi_\theta(s)\phi_\theta(s)^\top]^{-1}\mathbb E[\delta(\theta)\phi_\theta(s)],\nonumber\\ &h(\theta,u)\coloneqq \mathbb E[(\delta(\theta)-\phi_\theta(s)^\top u)\nabla^2_\theta V_\theta(s)u].
	\end{flalign*}}
Similarly to linear TDC studied in \Cref{sc: linearTDC}, in order to estimate the gradient in \cref{nonlinear-TDCupdate}, an auxiliary parameter $w_t$ can be used to estimate the vector $w(\theta_t)$, i.e., $w_t\approx w(\theta_t)$, by solving a linear SA with the following corresponding ODE:
\begin{flalign}\label{eq: ODE1}
\dot{w}=-\mathbb E[\phi_\theta(s)\phi_\theta(s)^\top]w + \mathbb E[\delta(\theta)\phi_\theta(s)].
\end{flalign}
Given $w_t$, the parameter $\theta_t$ can then be updated with a stochastic approximation of $\nabla J(\theta_t)$ obtained via directly sampling:
\begin{flalign}
\theta_{t+1}&=\theta_t + \alpha_t\frac{1}{\lone{\mathcal B_t}}\sum_{j\in \mathcal B_t} g(\theta_t, w_t,x_j), \label{eq: nonlinearTDC_stoc}
\end{flalign}
where $\mathcal B_t$ is the minibatch sampled from the MDP, $x_j$ denotes the sample $(s_j,a_j,s_{j+1})$ and we define $g(\theta_t, w_t,x_j)=\delta_j(\theta_t)\phi_{\theta_t}(s_j)-\gamma\phi_{\theta_t}(s_{j+1})\phi_{\theta_t}(s_j)^\top w_t-h_j(\theta_t,w_t)$, where $h_j(\theta_t,w_t)=(\delta_j(\theta_t)-\phi_{\theta_t}(s_j)^\top w_t)\nabla^2_\theta V_{\theta_t}(s_j)w_t$.
The nonlinear TDC algorithm is shown in \Cref{al: nonlinearTDC}. Similarly to \Cref{al: linearTDC}, here we also use a mini-batch of samples for each update.

\begin{algorithm}[H]
	\null
	\caption{Two Time-scale Nonlinear TDC}
	\label{al: nonlinearTDC}
	\begin{algorithmic}[1]
		\STATE \textbf{Input} batch size $M$, learning rate $\alpha$ and $\beta$
		\STATE {\bfseries Sampling:} A trajectory $\{ s_j, a_j\}_{j\geq 0}$ is sampled by following the policy $\pi$
		\STATE \textbf{Initialization: } $\theta_0$ and $w_0$
		\FOR{$t=0, 1, ..., T-1$}
		\STATE $i_t=tM$
	
		\STATE $w_{t+1} = w_t + \beta\frac{1}{M}\sum_{j=i_t}^{i_t+M-1}(-\phi_{\theta_t}(s_j)\phi_{\theta_t}(s_j)^\top w_t + \delta_j(\theta_t)\phi_{\theta_t}(s_j))$
		\STATE $\theta_{t+1}=\theta_t + \alpha\frac{1}{M}\sum_{j=i_t}^{i_t+M-1}(\delta_j(\theta_t)\phi_{\theta_t}(s_j)-\gamma\phi_{\theta_t}(s_{j+1})\phi_{\theta_t}(s_j)^\top w_t-h_j(\theta_t,w_t))$
		\ENDFOR
		\OUTPUT $\tilde{\theta}_{\hat{T}}$ with $\hat{T}$ chosen uniformly from $\{1,\cdots,T\}$
	\end{algorithmic}
\end{algorithm}

\subsection{Convergence Analysis}

Our analysis of \Cref{al: nonlinearTDC} will be based on the following assumptions.
\begin{assumption}[Bounded feature]\label{ass2}
	For any state $s\in \mathcal{S}$ and any vector $\theta\in \mathbb{R}^d$, we have $\ltwo{\phi_\theta(s)}\leq C_\phi$, $\lone{V(s,\theta)}\leq C_v$ and $\lF{\nabla^2_\theta V(s,\theta)}\leq D_v$, where $C_\phi$, $C_v$ and $D_v$ are positive constants.
\end{assumption}
\begin{assumption}[Smoothness]\label{ass3}
	For any state $s\in \mathcal{S}$ and any vector $\theta, \theta^\prime\in \mathbb{R}^d$, we have $\lone{V(s,\theta)-V(s,\theta^\prime)}\leq L_v\ltwo{\theta-\theta^\prime}$, $\ltwo{\phi_\theta(s)-\phi_{\theta^\prime}(s)}\leq L_\phi \ltwo{\theta-\theta^\prime}$, and $\ltwo{\nabla^2_\theta V(s,\theta) - \nabla^2_\theta V(s,\theta^\prime) } \leq L_h\ltwo{\theta-\theta^\prime} $, where $L_v$, $L_\phi$, and $L_h$ are positive constants.
\end{assumption}
\begin{assumption}[Non-singularity]\label{ass4}
	For any vector $\theta\in \mathbb{R}^d$, we have $\text{eig}\{\mathbb E[\phi_\theta(s) \phi_\theta(s)^\top]\} \geq \lambda_v$, where $\lambda_v$ is a positive constant.
\end{assumption}
\begin{assumption}[Lipschitz gradient]\label{ass5}
	For any vector $\theta, \theta^\prime$ and $w,w^\prime\in \mathbb{R}^d$, and any sample $x$, we have $\ltwo{\nabla J(\theta)- \nabla J(\theta^\prime)}\leq L_J\ltwo{\theta-\theta^\prime}$, and $\ltwo{g(\theta, w,x)-g(\theta, w^\prime,x)}\leq L_e\ltwo{w-w^\prime}$ where $L_J$ and $L_e$ are positive constants.
\end{assumption}
Assumptions \ref{ass2}-\ref{ass5} are equivalent to the assumptions adopted in the original nonlinear TDC analysis \cite{bhatnagar2009convergent}, and can be satisfied by appropriately choosing the approximation function class $\hat{v}(s,\theta)$. The following theorem characterizes the converge rate and sample complexity of \Cref{al: nonlinearTDC}.





\begin{theorem}\label{thm2}
	Consider the two timescale nonlinear TDC algorithm in \Cref{al: nonlinearTDC}. Suppose Assumptions \ref{ass1}-\ref{ass5} hold. Let the stepsize $\beta\leq \min\{\frac{\lambda_v}{8C^4_\phi}, \frac{8}{\lambda_v} \}$ and $\alpha\leq \min\{\frac{1}{2L_J}, \frac{\lambda_v \beta}{8\sqrt{2}L_w L_e}, \frac{L_J \lambda^2_v\beta^2}{384 L^2_wL^2_e} \}$. We have
	\begin{flalign*}
	\mathbb E\left[\ltwo{\nabla J(\theta_{\hat{T}})}^2\right]\leq \frac{8(J(\theta_0)-\mathbb E[J(\theta_T)])}{\alpha T} + \frac{B_1\ltwo{w_0-w(\theta_0)}^2}{T} + \frac{B_2}{M},
	\end{flalign*}

	where $B_1$ and $B_2$ are constants defined in \Cref{sc: proflemma2} in \cref{eq: 33}. Furthermore, let $M\geq \frac{2	B_2}{\epsilon}$ and $T\geq \frac{2}{\epsilon}\left[ \frac{8J(\theta_0)}{\alpha} + B_1\ltwo{w_0-w(\theta_0)}^2 \right]$. The total sample complexity for \Cref{al: nonlinearTDC} to achieve an $\epsilon$-accurate stationary point, i.e., $\mathbb E\big[ \ltwo{\nabla J(\theta_{\hat{T}})}^2 \big]\leq \epsilon$, is given by
	\begin{flalign*}
	TM=\Theta\left( \frac{1}{\epsilon^2} \right).
	\end{flalign*}
\end{theorem}

\Cref{thm2} shows that the convergence error of \Cref{al: nonlinearTDC} consists of three terms: the first two terms are the transient error decreasing at a sublinear rate as $T$ increases, and the third term contains the variance and bias errors that diminish as the batch size $M$ increases. 
We next provide a sketch of the proof for \Cref{thm2}.
\begin{proof}[{\bf Proof Sketch of \Cref{thm2}}]
	The proof of \Cref{thm2} consists of the following four steps.
	
	\noindent\textbf{Step 1:} We first provide \Cref{lemma: fixpointlip} to show that $w(\theta)$ is $L_w$-Lipschitz:
	\begin{flalign*}
	\ltwo{w(\theta)-w(\theta^\prime)}\leq L_w\ltwo{\theta - \theta^\prime},\quad \text{for all }\theta,\theta^\prime\in \mathbb{R}^d.
	\end{flalign*}
	This property is crucial for the convergence analysis of two time-scale nonlinear TDC. It indicates that if $\theta_t$ changes slowly, then $w(\theta_t)$ also changes slowly. This allows our finite time analysis to be over a slowly changing linear SA with corresponding ODE defined in \cref{eq: ODE1}, guaranteeing that $\ltwo{w_t - w(\theta_t)}^2$ is small in an amortized sense.
	
	\noindent\textbf{Step 2:} We then establish the induction relationships for the tracking error $\ltwo{w_t - w(\theta_t)}^2$:
	\begin{flalign}\label{eq: sketch4}
	\mathbb E\left[ \ltwo{w_{t+1}-w(\theta_{t+1})}^2 \right] &\leq \left(1 - \Theta(\lambda_v\beta)  \right)\mathbb E\left[ \ltwo{w_{t}-w(\theta_{t})}^2 \right] \nonumber\\
	&\quad + \Theta(\alpha^2/\beta)\mathbb E\left[\ltwo{\nabla J(\theta_t)}^2\right] + \Theta(1/M).
	\end{flalign}
	
	\noindent\textbf{Step 3:} We then establish the induction relationships for the gradient norm $\ltwo{\nabla J(\theta_t)}^2$:
	\begin{flalign}\label{eq: sketch5}
	\left(\Theta(\alpha) - \Theta(\alpha^2) \right) \mathbb E\left[\ltwo{\nabla J(\theta_t)}^2\right]&\leq \mathbb E[J(\theta_t)] - \mathbb E[J(\theta_{t+1})] + \Theta(\alpha + \alpha^2)\mathbb E\left[ \ltwo{w_{t}-w(\theta_{t})}^2 \right] +  \Theta(1/M).
	\end{flalign}
	
	\noindent\textbf{Step 4:} Applying \cref{eq: sketch4} and \cref{eq: sketch5} recursively from $t=T-1$ to $0$ and combing those two results together yield
	\begin{flalign*}
	\left( \Theta(\alpha) - \Theta(\alpha^2) - \Theta(\alpha^3) \right)\sum_{t=0}^{T-1}\mathbb E\left[\ltwo{\nabla J(\theta_t)}^2\right]\leq J(\theta_0) - \mathbb E[J(\theta_T)] + \Theta((\alpha + \alpha^2)/\beta)\ltwo{w_0 - w(\theta_0)}^2 + \Theta(1/M).
	\end{flalign*}
	Letting the stepsize $\alpha$ and $\beta$ and the batch size $M$ satisfies the requirement specified in \Cref{thm2}, we can then obtain the desired convergence result.
\end{proof}


\section{Policy Optimization: Greedy-GQ Algorithm}

In this section, we will provide the non-asymptotic convergence result of Greedy-GQ \cite{maei2010toward}, which is also a two timescale nonlinear SA algorithm. 

Greedy-GQ was proposed in \cite{maei2010toward} to solve the divergence issue of Q-Learning in the linear function approximation setting.
In Greedy-GQ, the goal of the agent is to learn an optimal policy for the MDP with respect to the total expected discounted reward.
In the linear function approximation setting, a linear function $\hat{Q}(s,a,\theta)=\phi(s,a)^\top \theta$ is used to approximate the state-action value function $Q(s,a)$, where $\phi(s,a)\in \mathbb{R}^d$ is a fixed feature vector for state-action pair $(s,a)$ and $\theta\in \mathbb{R}^d$ is a parameter vector. Without loss of generality, we assume that the feature vector $\ltwo{\phi(s,a)}\leq 1$ for all $(s,a)\in\mathcal S\times \mathcal A$ and the columns of the feature matrix $\Phi$ are linearly independent.  In this setting, we hope to find a solution $\theta$ that satisfies 
\begin{flalign}\label{eq: gq_goal}
\Pi T^{\pi_{\theta}}\hat{Q}(s,a,\theta)=\hat{Q}(s,a,\theta),\quad \text{for all } (s,a)\in \mathcal S\times\mathcal A,
\end{flalign}
where $\pi_{\theta}$ is the soft-max greedy policy with respect to the state-action value function $\hat{Q}(s,a,\theta)$, i.e., $\pi_\theta(a|s)=\frac{\exp(\tau\hat{Q}(s,a,\theta))}{\sum_{a^\prime \in \mathcal A}\exp(\tau\hat{Q}(s,a^\prime,\theta))}$, where $\tau>0$ is the temperature parameter, and $T^{\pi_{\theta}}$ denotes the Bellman operator with policy $\pi_{\theta}$.
Similarly to the TDC algorithms, Gready-GQ searches a parameter that satisfies \cref{eq: gq_goal} by minimizing a projected Bellman error objective function defined as:
\begin{flalign}\label{mspbe2}
J(\theta)=\mathbb E_{\mu_{\pi_b}}[\hat{Q}(s,a,\theta)-{\rm \Pi} T^{\pi_\theta} \hat{Q}(s,a,\theta)]^2,
\end{flalign}
where $\delta(\theta)=r(s,a,s^\prime) + \gamma \hat{Q}(s^\prime,b,\theta)-\hat{Q}(s,a,\theta)$ is the temporal difference error, with $a \sim \pi_\theta(\cdot|s)$ and $b \sim \pi_\theta(\cdot|s^\prime)$. Since $J(\theta)$ is nonconvex and smooth everywhere, we can apply gradient descent method to find a local optimal (stationary point) of the objective $J(\theta)$ via applying the update $\theta_{t+1}=\theta_t - \frac{\alpha}{2}\nabla J(\theta_t)$ iteratively, in which
\begin{flalign*}
\frac{1}{2}\nabla J(\theta_t)&=-\mathbb E_{\mu_{\pi_b}}[\mathbb E_{\pi_\theta}[\delta(\theta)|s,a]\phi(s,a)] + \gamma \mathbb E_{\mu_{\pi_b}}[\mathbb E_{\pi_\theta}[\phi(s^\prime,b)|s,a]\phi(s,a)^\top] w(\theta)
\end{flalign*}
where
{\small \begin{flalign*}
	w(\theta)=\mathbb E_{\mu_{\pi_b}}[\phi(s,a)\phi(s,a)^\top]^{-1}\mathbb E_{\mu_{\pi_b}}[\mathbb E_{\pi_\theta}[\delta(\theta)|s,a]\phi(s,a)].
	\end{flalign*} }
Similarly to the nonlinear TDC algorithms in \cref{sc: nonlinearTDC}, here an auxiliary parameter $w_t$ is adopted to estimate the vector $w(\theta_t)$ by solving a linear SA with the following corresponding ODE:
{\small \begin{flalign*}
	\dot{w}=-\mathbb E_{\mu_{\pi_b}}[\phi(s,a)\phi(s,a)^\top]w + \mathbb E_{\mu_{\pi_b}}[\mathbb E_{\pi_\theta}[\delta(\theta)|s,a]\phi(s,a)].
	\end{flalign*}}
Then, $\theta_t$ can be updated via direct sampling
\begin{flalign*}
\theta_{t+1}=\theta_t + \alpha_t \frac{1}{\lone{\mathcal B_t}}\sum_{j\in \mathcal B_t} g(\theta_t, w_t,x_j),
\end{flalign*}
where $\rho_{\theta}(s,a)=\pi_\theta(a|s)/\pi_b(a|s)$ is the importance weighting factor bounded by $\rho_{\max}$ and we define $g(\theta_t, w_t,x_j)=\rho_{\theta_t}(s_{j+1}, a_{j+1})(\delta_j(\theta_t)\phi(s_j,a_j) - \gamma \phi(s_{j+1},a_{j+1}) \phi(s_j,a_j)^\top w_t)$. The two timescale Greedy-GQ algorithm is shown below. 

\begin{algorithm}[H]
	\null
	\caption{Two Timescale Greedy-GQ}
	\label{al: GreedyGQ}
	\begin{algorithmic}[1]
		\STATE {\bfseries Input:} batch size $M$, learning rate $\alpha$ and $\beta$
		\STATE {\bfseries Sampling:} A trajectory $\{ s_j, a_j\}_{j\geq 0}$ is sampled by following the behaviour policy $\pi_b$
		\STATE \textbf{Initialization: } $\theta_0$ and $w_0$
		\FOR{$t=0,\cdots,T-1$}
		\STATE $i_t=tM$
		\STATE {\small $w_{t+1} = w_t + \beta\frac{1}{M}\sum_{j=i_t}^{i_t+M-1}(-\phi(s_j, a_j)\phi(s_j, a_j)^\top w_t + \rho_{\theta_j}(s_j, a_j)\delta_j(\theta_t)\phi(s_j, a_j))$}
		\STATE {\small $\theta_{t+1}=\theta_t + \alpha\frac{1}{M}\sum_{j=i_t}^{i_t+M-1} \rho_{\theta_t}(s_{j+1}, a_{j+1})(\delta_j(\theta_t)\phi(s_j)-\gamma \phi(s_{j+1}, a_{j+1})\phi(s_j, a_j)^\top w_t)$}
		\ENDFOR
		\OUTPUT $\tilde{\theta}_{\hat{T}}$ with $\hat{T}$ chosen uniformly from $\{1,\cdots,T\}$
	\end{algorithmic}
\end{algorithm}

By slightly abusing notations in \Cref{sc: nonlinearTDC}, we make the follow standard assumptions.
\begin{assumption}[Non-singularity]\label{ass6}
	We have $(\max_{\theta\in \mathbb{R}^d}\lone{\lambda_{\max}\{A^\top_\theta C^{-1} A_\theta\}})^{-1}=\lambda_1$ and $\lone{\lambda_{\max}\{C\}} = \lambda_2$, where $A_\theta=\mathbb E_{\mu_{\pi_b}}[(\gamma\mathbb E_{\pi_\theta}[\phi(s^\prime)|s]-\phi(s))\phi(s)^\top]$ and $C=-\mathbb E_{\mu_{\pi_b}}[\phi(s)\phi(s)^\top]$ and $\lambda_1$ and $\lambda_2$ are positive constants.
\end{assumption}
\begin{assumption}[Bounded importance factor]\label{ass7}
	For any state-action pair $(s,a)\in \mathcal{S}\times\mathcal{A}$ and any $\theta\in \mathbb{R}^d$, we have $\rho_\theta(s,a)\leq \rho_{\max}$, where $\rho_{\max}$ is a positive constant.
\end{assumption}
Note that \Cref{ass7} can be satisfied when the behaviour policy is non-degenerated for all states.
Moreover, \cite{wang2020finite} provide the following Lipschitz property of the gradient $\nabla J(\theta)$.
\begin{lemma}
	Suppose \Cref{ass1} and \Cref{ass6} hold, for any $\theta, \theta^\prime\in \mathbb{R}^d$, we have $\ltwo{\nabla J(\theta)-\nabla J(\theta^\prime)}\leq L_J\ltwo{\theta-\theta^\prime}$, where $L_J$ is a positive constant.
\end{lemma}
Note that the Greedy-GQ algorithm in \Cref{al: GreedyGQ} and nonlinear TDC algorithm in \Cref{al: nonlinearTDC} share similar structures. Both objectives are nonconvex and both algorithms adopt a two timescale update scheme, in which the fast timescale iteration corresponds to a linear SA and the slow time-scale iteration corresponds to a nonlinear SA.
Thus, the analysis of two time-scale nonlinear TDC in \Cref{sc: nonlinearTDC} can be extended to study the convergence rate of Greedy-GQ algorithm. The following theorem characterizes the convergence rate and sample complexity of \Cref{al: GreedyGQ}.
\begin{theorem}\label{thm3}
	Consider the two timescale Greedy-GQ algorithm in \Cref{al: GreedyGQ}. Suppose Assumptions \ref{ass1}, \ref{ass6} and \ref{ass7} hold. Let the stepsize $\beta\leq \min\{ \frac{\lambda_2}{4}, \frac{8}{\lambda_2} \}$ and $\alpha\leq \min\{ \frac{1}{8L_J},\frac{\lambda_2\sqrt{\lambda_2}}{8\sqrt{2}\rho_{\max}}\beta, \frac{L_J\lambda^3_2}{5312\rho^2_{\max}\lambda^2_1}\beta^2 \}$, and batch size $M\geq \frac{1+(\kappa-1)\rho}{1-\rho} \max\{128\left( \rho^2_{\max} + \frac{1}{\lambda^2_2} \right)[1+ \frac{\lambda^2_2\beta}{4\alpha^2}(\frac{2\beta}{\lambda_2} + 2\beta^2)], \frac{\beta^2\lambda^3_2(\rho_{\max}+1)^4}{\rho^2_{\max}\alpha^2}\}$. We have
	{\begin{flalign*}
		\mathbb E\left[\ltwo{\nabla J(\theta_{\hat{T}})}^2\right]&\leq \frac{8(J(\theta_0)-\mathbb E[J(\theta_T)])}{\alpha T} + \frac{192\rho^2_{\max}}{\lambda_2\beta}\frac{\ltwo{w_0 - w^*(\theta_0)}^2}{T} + \frac{32C_1[1+(\kappa-1)\rho]}{M(1-\rho)},
		\end{flalign*}}

	where $C_1$ is a positive constant defined in \cref{eq: 30} in \Cref{sc: appGQ}. Furthermore, let $M\geq \frac{64C_2[1+(\kappa-1)\rho]}{(1-\rho)\epsilon}$ and $T\geq \frac{2}{\epsilon}\left[ \frac{8J(\theta_0)}{\alpha} + \frac{192\rho^2_{\max}\ltwo{w_0-w(\theta_0)}^2}{\lambda_2\beta} \right]$. The total sample complexity for \Cref{al: nonlinearTDC} to achieve an $\epsilon$-accurate stationary point, i.e., $\mathbb E\big[ \ltwo{\nabla J(\theta_{\hat{T}})}^2 \big]\leq \epsilon$, is given by
	\begin{flalign*}
	TM=\Theta\left( \frac{1}{\epsilon^2} \right).
	\end{flalign*}
\end{theorem}

Similarly to \Cref{thm2}, in \Cref{thm3} we show that \Cref{al: GreedyGQ} converges to an $\epsilon$-accurate stationary point with sample complexity $\mathcal{O}(\epsilon^{-2})$. Note that \cite{wang2020finite} studied the convergence rate of two timescale Greedy-GQ with diminishing stepsize, which achieves the complexity of $\mathcal{O}(\epsilon^{-3}\log(1/\epsilon))$. \Cref{thm3} for two timescale Greedy-GQ with constant stepsize outperforms the result in \cite{wang2020finite} by a factor of $\mathcal{O}(\epsilon^{-1}\log(1/\epsilon))$, indicating that the constant stepsize can significantly improve the convergence rate of two timescale Greedy-GQ algorithm. 


\section{Conclusion}

In this paper, we study the convergence rate for two timescale linear and nonlinear TDC and Greedy-GQ under Markovian sampling and constant stepsize. Specifically, we show that the complexity result of linear TDC orderwisely achieves the optimal convergence rate under a constant stepsize. Our result for nonlinear TDC is the first under Markovian sampling. Moreover, our sample complexity result of Greedy-GQ outperforms the previous result orderwisely.
For future work, it is interesting to apply more advance optimization techniques, e.g., acceleration, variance reduction, to further improve the convergence performance of the value-based RL algorithms studied in this paper.

\newpage
\bibliographystyle{apalike}
