Diffusion approximation for two time-scale stochastic approximation algorithms with constant step sizes

The problem of diffusion approximation for two time-scale stochastic approximation algorithms with constant step sizes is analyzed in this paper. The analysis is carried out for the algorithms with additive state-dependent noise, as well as for the algorithms with non-additive noise. The algorithms with additive noise Eire considered for the case where the noise is decomposable as it sum of a martingale difference sequence, vanishing sequence and a telescoping sequence, and where the conditional covariance of the martingale-difference noise component admit it similar decomposition. The algorithms with non-additive noise are analyzed for the case where the noise is strictly stationary and satisfies uniform or strong mixing conditions, as well as for the case where the noise is a Markov chain controlled by the algorithm states. The obtained diffusion approximation results directly characterize the rate of convergence of two time-scale stochastic approximation algorithms.