Finite-Time Convergence Rates of Nonlinear Two-Time-Scale Stochastic Approximation under Markovian Noise

We study the so-called two-time-scale stochastic approximation, a\nsimulation-based approach for finding the roots of two coupled nonlinear\noperators. Our focus is to characterize its finite-time performance in a Markov\nsetting, which often arises in stochastic control and reinforcement learning\nproblems. In particular, we consider the scenario where the data in the method\nare generated by Markov processes, therefore, they are dependent. Such\ndependent data result to biased observations of the underlying operators. Under\nsome fairly standard assumptions on the operators and the Markov processes, we\nprovide a formula that characterizes the convergence rate of the mean square\nerrors generated by the method to zero. Our result shows that the method\nachieves a convergence in expectation at a rate $\\mathcal{O}(1/k^{2/3})$, where\n$k$ is the number of iterations. Our analysis is mainly motivated by the\nclassic singular perturbation theory for studying the asymptotic convergence of\ntwo-time-scale systems, that is, we consider a Lyapunov function that carefully\ncharacterizes the coupling between the two iterates. In addition, we utilize\nthe geometric mixing time of the underlying Markov process to handle the bias\nand dependence in the data. Our theoretical result complements for the existing\nliterature, where the rate of nonlinear two-time-scale stochastic approximation\nunder Markovian noise is unknown.\n