Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning

Abstract

Temporal-Difference (TD) learning with nonlinear smooth function approximation for policy evaluation has achieved great success in modern reinforcement learning. It is shown that such a problem can be reformulated as a stochastic nonconvex-strongly-concave optimization problem, which is challenging as naive stochastic gradient descent-ascent algorithm suffers from slow convergence. Existing approaches for this problem are based on two-timescale or double-loop stochastic gradient algorithms, which may also require sampling large-batch data. However, in practice, a single-timescale single-loop stochastic algorithm is preferred due to its simplicity and also because its step-size is easier to tune. In this paper, we propose two single-timescale single-loop algorithms which require only one data point each step. Our first algorithm implements momentum updates on both primal and dual variables achieving an $O({\epsilon }^{-4})$ sample complexity, which shows the important role of momentum in obtaining a single-timescale algorithm. Our second algorithm improves upon the first one by applying variance reduction on top of momentum, which matches the best known $O({\epsilon }^{-3})$ sample complexity in existing works. Furthermore, our variance-reduction algorithm does not require a large-batch checkpoint. Moreover, our theoretical results for both algorithms are expressed in a tighter form of simultaneous primal and dual side convergence.

45 pages; initial draft submitted in Feb, 2020

References in corpus (13)

• High-Dimensional Continuous Control Using Generalized Advantage Estimation
• On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems
• Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methods
• Hybrid Block Successive Approximation for One-Sided Non-Convex Min-Max Problems: Algorithms and Applications
• Finite-Sample Analysis of Proximal Gradient TD Algorithms
• Stochastic Variance Reduction Methods for Policy Evaluation
• Finite-Time Analysis of Distributed TD(0) with Linear Function Approximation for Multi-Agent Reinforcement Learning
• Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learning
• Momentum-Based Variance Reduction in Non-Convex SGD
• 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
• A Finite-Time Analysis of Q-Learning with Neural Network Function Approximation
• A Single Time-Scale Stochastic Approximation Method for Nested Stochastic Optimization

Cited by in corpus (6)

• Sample Complexity Bounds for Two Timescale Value-based Reinforcement Learning Algorithms
• Temporal-difference learning with nonlinear function approximation: lazy training and mean field regimes
• Finding Second-Order Stationary Points in Nonconvex-Strongly-Concave Minimax Optimization
• Minimax Problems with Coupled Linear Constraints: Computational Complexity, Duality and Solution Methods
• CDMA: A Practical Cross-Device Federated Learning Algorithm for General Minimax Problems
• Randomized Stochastic Gradient Descent Ascent