Finite Time Analysis Of Linear Two-timescale Stochastic Approximation With Markovian Noise

Abstract

Linear two-timescale stochastic approximation (SA) scheme is an important class of algorithms which has become popular in reinforcement learning (RL), particularly for the policy evaluation problem. Recently, a number of works have been devoted to establishing the finite time analysis of the scheme, especially under the Markovian (non-i.i.d.) noise settings that are ubiquitous in practice. In this paper, we provide a finite-time analysis for linear two timescale SA. Our bounds show that there is no discrepancy in the convergence rate between Markovian and martingale noise, only the constants are affected by the mixing time of the Markov chain. With an appropriate step size schedule, the transient term in the expected error bound is \(o(1/k^c)\) and the steady-state term is \(\{\cal O\}(1/k)\), where \(c>1\) and \(k\) is the iteration number. Furthermore, we present an asymptotic expansion of the expected error with a matching lower bound of \(Ω(1/k)\). A simple numerical experiment is

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keykaledin2020finite

Related papers

• Finite-sample Analysis Of Nonlinear Stochastic Approximation With Applications In Reinforcement Learning (2019)10.35
• Finite Sample Analysis Of Two-timescale Stochastic Approximation With Applications To Reinforcement Learning (2017)0.00
• Sample Complexity Bounds For Two Timescale Value-based Reinforcement Learning Algorithms (2020)0.00
• Central Limit Theorem For Two-timescale Stochastic Approximation With Markovian Noise: Theory And Applications (2024)0.00
• On The Convergence Of Consensus Algorithms With Markovian Noise And Gradient Bias (2020)0.00
• Stochastic Approximation With Delayed Updates: Finite-time Rates Under Markovian Sampling (2024)0.00
• Non-asymptotic Analysis Of Biased Stochastic Approximation Scheme (2019)0.00
• The ODE Method For Stochastic Approximation And Reinforcement Learning With Markovian Noise (2024)0.00