Convergence rate of linear two-time-scale stochastic approximation

Abstract

We study the rate of convergence of linear two-time-scale stochastic approximation methods. We consider two-time-scale linear iterations driven by i.i.d. noise, prove some results on their asymptotic covariance and establish asymptotic normality. The well-known result [Polyak, B. T. (1990). Automat. Remote Contr. 51 937-946; Ruppert, D. (1988). Technical Report 781, Cornell Univ.] on the optimality of Polyak-Ruppert averaging techniques specialized to linear stochastic approximation is established as a consequence of the general results in this paper.

Cited by in corpus (35)

• Convergence rate and averaging of nonlinear two-time-scale stochastic approximation algorithms
• A Game Theoretic Framework for Model Based Reinforcement Learning
• Strong error analysis for stochastic gradient descent optimization algorithms
• A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis and Application to Actor-Critic
• Averaging principle and normal deviations for multiscale stochastic systems
• A Finite Time Analysis of Two Time-Scale Actor Critic Methods
• The Evolution of Reinforcement Learning in Quantitative Finance: A Survey
• FedGAN: Federated Generative Adversarial Networks for Distributed Data
• Fastest Convergence for Q-learning
• Risk-Sensitive Reinforcement Learning: a Martingale Approach to Reward Uncertainty
• Finite Time Analysis of Linear Two-timescale Stochastic Approximation with Markovian Noise
• Distributed two-time-scale methods over clustered networks
• Learning to Predict Independent of Span
• General multilevel adaptations for stochastic approximation algorithms
• Zap Q-Learning With Nonlinear Function Approximation
• Networks of reinforced stochastic processes: asymptotics for the empirical means
• Asymptotic behavior of multiscale stochastic partial differential equations
• A Tale of Two-Timescale Reinforcement Learning with the Tightest Finite-Time Bound
• Stochastic Compositional Gradient Descent: Algorithms for Minimizing Compositions of Expected-Value Functions
• Computation of VaR and CVaR using stochastic approximations and unconstrained importance sampling
• Optimal Matrix Momentum Stochastic Approximation and Applications to Q-learning
• Finite-Time Convergence Rates of Nonlinear Two-Time-Scale Stochastic Approximation under Markovian Noise
• Generative Adversarial Networks are Special Cases of Artificial Curiosity (1990) and also Closely Related to Predictability Minimization (1991)
• Robust Batch Policy Learning in Markov Decision Processes
• Finite-Time Performance of Distributed Two-Time-Scale Stochastic Approximation
• Scalable Multi-agent Reinforcement Learning Algorithm for Wireless Networks
• Who Leads and Who Follows in Strategic Classification?
• A Two-Time-Scale Stochastic Optimization Framework with Applications in Control and Reinforcement Learning
• Continuous-time Value Function Approximation in Reproducing Kernel Hilbert Spaces
• Non-Asymptotic Analysis for Two Time-scale TDC with General Smooth Function Approximation
• Asymptotic Theory for IV-Based Reinforcement Learning with Potential Endogeneity
• Asymptotic Error Analysis of Multilevel Stochastic Approximations for the Value-at-Risk and Expected Shortfall
• A kernel-based stochastic approximation framework for contextual optimization
• Quantile Tracking in Dynamically Varying Data Streams Using a Generalized Exponentially Weighted Average of Observations
• Sequential online subsampling for thinning experimental designs