Two Time-scale Off-Policy TD Learning: Non-asymptotic Analysis over Markovian Samples

Abstract

Gradient-based temporal difference (GTD) algorithms are widely used in off-policy learning scenarios. Among them, the two time-scale TD with gradient correction (TDC) algorithm has been shown to have superior performance. In contrast to previous studies that characterized the non-asymptotic convergence rate of TDC only under identical and independently distributed (i.i.d.) data samples, we provide the first non-asymptotic convergence analysis for two time-scale TDC under a non-i.i.d.\ Markovian sample path and linear function approximation. We show that the two time-scale TDC can converge as fast as O(log t/(t^(2/3))) under diminishing stepsize, and can converge exponentially fast under constant stepsize, but at the cost of a non-vanishing error. We further propose a TDC algorithm with blockwisely diminishing stepsize, and show that it asymptotically converges with an arbitrarily small error at a blockwisely linear convergence rate. Our experiments demonstrate that such an algorithm converges as fast as TDC under constant stepsize, and still enjoys comparable accuracy as TDC under diminishing stepsize.

To appear in NeurIPS 2019

Cited by in corpus (12)

• Non-asymptotic Convergence Analysis of Two Time-scale (Natural) Actor-Critic Algorithms
• Finite Time Analysis of Linear Two-timescale Stochastic Approximation with Markovian Noise
• Finite-Time Analysis of Asynchronous Stochastic Approximation and $Q$-Learning
• Finite-sample Analysis of Greedy-GQ with Linear Function Approximation under Markovian Noise
• Greedy-GQ with Variance Reduction: Finite-time Analysis and Improved Complexity
• Online Robust Reinforcement Learning with Model Uncertainty
• On the Stability of Random Matrix Product with Markovian Noise: Application to Linear Stochastic Approximation and TD Learning
• Sample Complexity Bounds for Two Timescale Value-based Reinforcement Learning Algorithms
• Multi-Agent Off-Policy TD Learning: Finite-Time Analysis with Near-Optimal Sample Complexity and Communication Complexity
• Temporal Difference Learning as Gradient Splitting
• A Unified Off-Policy Evaluation Approach for General Value Function
• On Convergence of Gradient Expected Sarsa($\lambda$)