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 $\mathcal{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 $\Omega (1/k)$. A simple numerical experiment is presented to support our theory.

References in corpus (5)

• Convergence rate of linear two-time-scale stochastic approximation
• Finite-Sample Analysis of Proximal Gradient TD Algorithms
• Convergence rate and averaging of nonlinear two-time-scale stochastic approximation algorithms
• Two Time-scale Off-Policy TD Learning: Non-asymptotic Analysis over Markovian Samples
• A Tale of Two-Timescale Reinforcement Learning with the Tightest Finite-Time Bound

Cited by in corpus (15)

• A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis and Application to Actor-Critic
• Non-asymptotic Convergence Analysis of Two Time-scale (Natural) Actor-Critic Algorithms
• Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model
• Distributed two-time-scale methods over clustered networks
• Sample Complexity Bounds for Two Timescale Value-based Reinforcement Learning Algorithms
• Finite-Time Convergence Rates of Nonlinear Two-Time-Scale Stochastic Approximation under Markovian Noise
• A Two-Time-Scale Stochastic Optimization Framework with Applications in Control and Reinforcement Learning
• Amortized Implicit Differentiation for Stochastic Bilevel Optimization
• Variance-Reduced Off-Policy TDC Learning: Non-Asymptotic Convergence Analysis
• Non-Asymptotic Analysis for Two Time-scale TDC with General Smooth Function Approximation
• Asymptotic Theory for IV-Based Reinforcement Learning with Potential Endogeneity
• Analysis of a Target-Based Actor-Critic Algorithm with Linear Function Approximation
• A priori guarantees of finite-time convergence for Deep Neural Networks
• Accelerating Optimization and Reinforcement Learning with Quasi-Stochastic Approximation
• A Law of Iterated Logarithm for Multi-Agent Reinforcement Learning