Reanalysis of Variance Reduced Temporal Difference Learning

Abstract

Temporal difference (TD) learning is a popular algorithm for policy evaluation in reinforcement learning, but the vanilla TD can substantially suffer from the inherent optimization variance. A variance reduced TD (VRTD) algorithm was proposed by Korda and La (2015), which applies the variance reduction technique directly to the online TD learning with Markovian samples. In this work, we first point out the technical errors in the analysis of VRTD in Korda and La (2015), and then provide a mathematically solid analysis of the non-asymptotic convergence of VRTD and its variance reduction performance. We show that VRTD is guaranteed to converge to a neighborhood of the fixed-point solution of TD at a linear convergence rate. Furthermore, the variance error (for both i.i.d.\ and Markovian sampling) and the bias error (for Markovian sampling) of VRTD are significantly reduced by the batch size of variance reduction in comparison to those of vanilla TD. As a result, the overall computational complexity of VRTD to attain a given accurate solution outperforms that of TD under Markov sampling and outperforms that of TD under i.i.d.\ sampling for a sufficiently small conditional number.

To appear in ICLR 2020

References in corpus (7)

• Finite-Sample Analysis of Proximal Gradient TD Algorithms
• Stochastic Variance Reduction Methods for Policy Evaluation
• Finite Sample Analysis of Two-Timescale Stochastic Approximation with Applications to Reinforcement Learning
• 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
• On Convergence of some Gradient-based Temporal-Differences Algorithms for Off-Policy Learning
• SVRG for Policy Evaluation with Fewer Gradient Evaluations

Cited by in corpus (8)

• Non-asymptotic Convergence Analysis of Two Time-scale (Natural) Actor-Critic Algorithms
• Improving Sample Complexity Bounds for (Natural) Actor-Critic Algorithms
• Is Q-Learning Minimax Optimal? A Tight Sample Complexity Analysis
• Doubly Robust Off-Policy Actor-Critic: Convergence and Optimality
• Greedy-GQ with Variance Reduction: Finite-time Analysis and Improved Complexity
• Sample Complexity Bounds for Two Timescale Value-based Reinforcement Learning Algorithms
• When Will Generative Adversarial Imitation Learning Algorithms Attain Global Convergence
• Multi-Agent Off-Policy TD Learning: Finite-Time Analysis with Near-Optimal Sample Complexity and Communication Complexity