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