Variance-Reduced Off-Policy TDC Learning: Non-Asymptotic Convergence Analysis

Abstract

Variance reduction techniques have been successfully applied to temporal-difference (TD) learning and help to improve the sample complexity in policy evaluation. However, the existing work applied variance reduction to either the less popular one time-scale TD algorithm or the two time-scale GTD algorithm but with a finite number of i.i.d.\ samples, and both algorithms apply to only the on-policy setting. In this work, we develop a variance reduction scheme for the two time-scale TDC algorithm in the off-policy setting and analyze its non-asymptotic convergence rate over both i.i.d.\ and Markovian samples. In the i.i.d.\ setting, our algorithm {matches the best-known lower bound $\tilde{O}({\epsilon }^{-1}$).} In the Markovian setting, our algorithm achieves the state-of-the-art sample complexity $O({\epsilon }^{-1}\log {\epsilon }^{-1})$ that is near-optimal. Experiments demonstrate that the proposed variance-reduced TDC achieves a smaller asymptotic convergence error than both the conventional TDC and the variance-reduced TD.

Accepted for publication in NeurIPS 2020

References in corpus (5)

• SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
• Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learning
• Finite Time Analysis of Linear Two-timescale Stochastic Approximation with Markovian Noise
• On TD(0) with function approximation: Concentration bounds and a centered variant with exponential convergence
• A Multistep Lyapunov Approach for Finite-Time Analysis of Biased Stochastic Approximation

Cited by in corpus (1)

• Non-Asymptotic Analysis for Two Time-scale TDC with General Smooth Function Approximation