2019/12/22 by Thinh T. Doan, Doan, Thinh T. · 1 citation
Computer Science · Engineering · #Age of Information Optimization #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Optimization and Control (math.OC) #Reinforcement Learning in Robotics #Traffic control and management
paper · pdf · doi:10.48550/arxiv.1912.10583
openalex publication_date 2019/12/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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(k2/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