Finite-Sample Analysis of Proximal Gradient TD Algorithms

Abstract

In this paper, we analyze the convergence rate of the gradient temporal difference learning (GTD) family of algorithms. Previous analyses of this class of algorithms use ODE techniques to prove asymptotic convergence, and to the best of our knowledge, no finite-sample analysis has been done. Moreover, there has been not much work on finite-sample analysis for convergent off-policy reinforcement learning algorithms. In this paper, we formulate GTD methods as stochastic gradient algorithms w.r.t.~a primal-dual saddle-point objective function, and then conduct a saddle-point error analysis to obtain finite-sample bounds on their performance. Two revised algorithms are also proposed, namely projected GTD2 and GTD2-MP, which offer improved convergence guarantees and acceleration, respectively. The results of our theoretical analysis show that the GTD family of algorithms are indeed comparable to the existing LSTD methods in off-policy learning scenarios.

31st Conference on Uncertainty in Artificial Intelligence (UAI). arXiv admin note: substantial text overlap with arXiv:2006.03976

References in corpus (4)

• Proximal Reinforcement Learning: A New Theory of Sequential Decision Making in Primal-Dual Spaces
• A Dantzig Selector Approach to Temporal Difference Learning
• Sparse Q-learning with Mirror Descent
• Statistical Linear Estimation with Penalized Estimators: an Application to Reinforcement Learning

Cited by in corpus (17)

• On the Global Convergence of Actor-Critic: A Case for Linear Quadratic Regulator with Ergodic Cost
• Finite Time Analysis of Linear Two-timescale Stochastic Approximation with Markovian Noise
• Accelerating Stochastic Composition Optimization
• Off-Policy Evaluation via the Regularized Lagrangian
• Learning from Conditional Distributions via Dual Embeddings
• Actor-Critic Provably Finds Nash Equilibria of Linear-Quadratic Mean-Field Games
• Decentralized Multi-Agent Reinforcement Learning with Networked Agents: Recent Advances
• Reanalysis of Variance Reduced Temporal Difference Learning
• A Finite-Time Analysis of Q-Learning with Neural Network Function Approximation
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning
• Doubly Robust Bias Reduction in Infinite Horizon Off-Policy Estimation
• Finite-sample Analysis of Greedy-GQ with Linear Function Approximation under Markovian Noise
• Finite-Sample Analysis of Decentralized Temporal-Difference Learning with Linear Function Approximation
• A Tale of Two-Timescale Reinforcement Learning with the Tightest Finite-Time Bound
• Privacy Preserving Off-Policy Evaluation
• Online Monotone Games
• Analyzing Reinforcement Learning Benchmarks with Random Weight Guessing