### Abstract

Motivated by applications in reinforcement learning (RL), we study anonlinear stochastic approximation (SA) algorithm under Markovian noise, andestablish its finite-sample convergence bounds under various stepsizes.Specifically, we show that when using constant stepsize (i.e.,$\epsilon_k\equiv \epsilon$), the algorithm achieves exponential fastconvergence with asymptotic accuracy $\mathcal{O}(\epsilon\log(1/\epsilon))$.When using diminishing stepsizes with appropriate decay rate, the algorithmconverges with rate $\mathcal{O}(\log(k)/k)$. Our proof is based on theLyapunov drift arguments, and to handle the Markovian noise, we exploit thefast mixing of the underlying Markov chain. To demonstrate the generality ofour theoretical results on Markovian SA, we use it to derive the finite-samplebounds of the popular $Q$-learning with linear function approximationalgorithm, under a condition on the behavior policy. Importantly, we do notneed to make the unrealistic assumption that the samples are i.i.d., and do notrequire an additional projection step in the algorithm to maintain theboundedness of the iterates. Numerical simulations corroborate our theoreticalfindings.