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

Abstract

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

arXiv commentarXiv admin note: text overlap with arXiv:2011.01868

References in corpus (9)

• Convergence rate of linear two-time-scale stochastic approximation
• Convergence rate and averaging of nonlinear two-time-scale stochastic approximation algorithms
• A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis and Application to Actor-Critic
• A Finite Time Analysis of Two Time-Scale Actor Critic Methods
• Finite Sample Analysis of Two-Timescale Stochastic Approximation with Applications to Reinforcement Learning
• Finite Time Analysis of Linear Two-timescale Stochastic Approximation with Markovian Noise
• Finite-Time Analysis of Asynchronous Stochastic Approximation and $Q$-Learning
• Distributed two-time-scale methods over clustered networks
• Convergence Rates of Accelerated Markov Gradient Descent with Applications in Reinforcement Learning

Cited by in corpus (2)

• A Two-Time-Scale Stochastic Optimization Framework with Applications in Control and Reinforcement Learning
• Finite-Time Complexity of Online Primal-Dual Natural Actor-Critic Algorithm for Constrained Markov Decision Processes