Finite-Time Analysis and Restarting Scheme for Linear Two-Time-Scale Stochastic Approximation

Motivated by their broad applications in reinforcement learning, we study the\nlinear two-time-scale stochastic approximation, an iterative method using two\ndifferent step sizes for finding the solutions of a system of two equations.\nOur main focus is to characterize the finite-time complexity of this method\nunder time-varying step sizes and Markovian noise. In particular, we show that\nthe mean square errors of the variables generated by the method converge to\nzero at a sublinear rate $\\Ocal(k^{2/3})$, where $k$ is the number of\niterations. We then improve the performance of this method by considering the\nrestarting scheme, where we restart the algorithm after every predetermined\nnumber of iterations. We show that using this restarting method the complexity\nof the algorithm under time-varying step sizes is as good as the one using\nconstant step sizes, but still achieving an exact converge to the desired\nsolution. Moreover, the restarting scheme also helps to prevent the step sizes\nfrom getting too small, which is useful for the practical implementation of the\nlinear two-time-scale stochastic approximation.\n