A Finite Time Analysis of Two Time-Scale Actor Critic Methods

Abstract

Actor-critic (AC) methods have exhibited great empirical success compared with other reinforcement learning algorithms, where the actor uses the policy gradient to improve the learning policy and the critic uses temporal difference learning to estimate the policy gradient. Under the two time-scale learning rate schedule, the asymptotic convergence of AC has been well studied in the literature. However, the non-asymptotic convergence and finite sample complexity of actor-critic methods are largely open. In this work, we provide a non-asymptotic analysis for two time-scale actor-critic methods under non-i.i.d. setting. We prove that the actor-critic method is guaranteed to find a first-order stationary point (i.e., $\Vert \nabla J(\mathbf{\theta }){\Vert }_2^2\le \epsilon$) of the non-concave performance function $J(\mathbf{\theta })$, with $\tilde{\mathcal{O}}({\epsilon }^{-2.5})$ sample complexity. To the best of our knowledge, this is the first work providing finite-time analysis and sample complexity bound for two time-scale actor-critic methods.

39 pages. In NeurIPS 2020

References in corpus (8)

• An Actor-Critic Algorithm for Sequence Prediction
• Two Time-scale Off-Policy TD Learning: Non-asymptotic Analysis over Markovian Samples
• Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learning
• Sample Efficient Policy Gradient Methods with Recursive Variance Reduction
• Non-asymptotic Convergence Analysis of Two Time-scale (Natural) Actor-Critic Algorithms
• On the Global Convergence of Actor-Critic: A Case for Linear Quadratic Regulator with Ergodic Cost
• Finite-Time Performance Bounds and Adaptive Learning Rate Selection for Two Time-Scale Reinforcement Learning
• A Finite-Time Analysis of Q-Learning with Neural Network Function Approximation

Cited by in corpus (20)

• A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis and Application to Actor-Critic
• Fast Global Convergence of Natural Policy Gradient Methods with Entropy Regularization
• Improving Sample Complexity Bounds for (Natural) Actor-Critic Algorithms
• Is Q-Learning Minimax Optimal? A Tight Sample Complexity Analysis
• Average-reward model-free reinforcement learning: a systematic review and literature mapping
• Single-Timescale Actor-Critic Provably Finds Globally Optimal Policy
• Doubly Robust Off-Policy Actor-Critic: Convergence and Optimality
• Softmax Policy Gradient Methods Can Take Exponential Time to Converge
• Greedy-GQ with Variance Reduction: Finite-time Analysis and Improved Complexity
• Finite-Sample Analysis of Off-Policy Natural Actor-Critic Algorithm
• Local Stochastic Approximation: A Unified View of Federated Learning and Distributed Multi-Task Reinforcement Learning Algorithms
• Online Robust Reinforcement Learning with Model Uncertainty
• Breaking the Deadly Triad with a Target Network
• A Deeper Look at Discounting Mismatch in Actor-Critic Algorithms
• Finite-Time Convergence Rates of Nonlinear Two-Time-Scale Stochastic Approximation under Markovian Noise
• A Two-Time-Scale Stochastic Optimization Framework with Applications in Control and Reinforcement Learning
• Actor-critic is implicitly biased towards high entropy optimal policies
• Finite-Time Complexity of Online Primal-Dual Natural Actor-Critic Algorithm for Constrained Markov Decision Processes
• Global Convergence of the ODE Limit for Online Actor-Critic Algorithms in Reinforcement Learning
• On the Convergence Rate of Off-Policy Policy Optimization Methods with Density-Ratio Correction