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 (5)

• 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
• Optimal Primal-Dual Methods for a Class of Saddle Point Problems

Cited by in corpus (56)

• Multi-Agent Reinforcement Learning via Double Averaging Primal-Dual Optimization
• A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis and Application to Actor-Critic
• Characterizing the Exact Behaviors of Temporal Difference Learning Algorithms Using Markov Jump Linear System Theory
• 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
• A Multistep Lyapunov Approach for Finite-Time Analysis of Biased Stochastic Approximation
• Weak Convergence Properties of Constrained Emphatic Temporal-difference Learning with Constant and Slowly Diminishing Stepsize
• Accelerating Stochastic Composition Optimization
• On Convergence of some Gradient-based Temporal-Differences Algorithms for Off-Policy Learning
• Off-Policy Evaluation via the Regularized Lagrangian
• Learning from Conditional Distributions via Dual Embeddings
• Decentralized Multi-Agent Reinforcement Learning with Networked Agents: Recent Advances
• Actor-Critic Provably Finds Nash Equilibria of Linear-Quadratic Mean-Field Games
• Exploration-Enhanced POLITEX
• Reanalysis of Variance Reduced Temporal Difference Learning
• Generalized Emphatic Temporal Difference Learning: Bias-Variance Analysis
• A Finite-Time Analysis of Q-Learning with Neural Network Function Approximation
• Online Off-policy Prediction
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning
• Neural Temporal-Difference and Q-Learning Provably Converge to Global Optima
• Doubly Robust Bias Reduction in Infinite Horizon Off-Policy Estimation
• Fast Multi-Agent Temporal-Difference Learning via Homotopy Stochastic Primal-Dual Optimization
• GradientDICE: Rethinking Generalized Offline Estimation of Stationary Values
• Policy Gradient in Partially Observable Environments: Approximation and Convergence
• Finite-sample Analysis of Greedy-GQ with Linear Function Approximation under Markovian Noise
• Finite Sample Analyses for TD(0) with Function Approximation
• Zap Q-Learning With Nonlinear Function Approximation
• Adaptive Temporal Difference Learning with Linear Function Approximation
• Finite-Sample Analysis of Decentralized Temporal-Difference Learning with Linear Function Approximation
• Greedy-GQ with Variance Reduction: Finite-time Analysis and Improved Complexity
• A Tale of Two-Timescale Reinforcement Learning with the Tightest Finite-Time Bound
• Average-Reward Off-Policy Policy Evaluation with Function Approximation
• Online Robust Reinforcement Learning with Model Uncertainty
• Provably Convergent Two-Timescale Off-Policy Actor-Critic with Function Approximation
• Sample Complexity Bounds for Two Timescale Value-based Reinforcement Learning Algorithms
• Is the Policy Gradient a Gradient?
• Mean-Variance Policy Iteration for Risk-Averse Reinforcement Learning
• Finite-Sample Analysis For Decentralized Batch Multi-Agent Reinforcement Learning With Networked Agents
• Multi-Agent Off-Policy TD Learning: Finite-Time Analysis with Near-Optimal Sample Complexity and Communication Complexity
• Privacy Preserving Off-Policy Evaluation
• SVRG for Policy Evaluation with Fewer Gradient Evaluations
• Online Monotone Games
• Analyzing Reinforcement Learning Benchmarks with Random Weight Guessing
• A Unified Off-Policy Evaluation Approach for General Value Function
• On the Convergence Rate of Off-Policy Policy Optimization Methods with Density-Ratio Correction
• Non-Asymptotic Analysis for Two Time-scale TDC with General Smooth Function Approximation
• On Convergence of Gradient Expected Sarsa($\lambda$)
• A Law of Iterated Logarithm for Multi-Agent Reinforcement Learning
• Stable and Efficient Policy Evaluation
• An Empirical Comparison of Off-policy Prediction Learning Algorithms in the Four Rooms Environment
• Borrowing From the Future: An Attempt to Address Double Sampling
• Gradient Q$(\sigma ,\lambda )$: A Unified Algorithm with Function Approximation for Reinforcement Learning
• An Empirical Comparison of Off-policy Prediction Learning Algorithms on the Collision Task
• Expected Sarsa($\lambda$) with Control Variate for Variance Reduction
• O${}^2$TD: (Near)-Optimal Off-Policy TD Learning
• On Generalized Bellman Equations and Temporal-Difference Learning