Non-asymptotic Convergence Analysis of Two Time-scale (Natural) Actor-Critic Algorithms

Abstract

As an important type of reinforcement learning algorithms, actor-critic (AC) and natural actor-critic (NAC) algorithms are often executed in two ways for finding optimal policies. In the first nested-loop design, actor's one update of policy is followed by an entire loop of critic's updates of the value function, and the finite-sample analysis of such AC and NAC algorithms have been recently well established. The second two time-scale design, in which actor and critic update simultaneously but with different learning rates, has much fewer tuning parameters than the nested-loop design and is hence substantially easier to implement. Although two time-scale AC and NAC have been shown to converge in the literature, the finite-sample convergence rate has not been established. In this paper, we provide the first such non-asymptotic convergence rate for two time-scale AC and NAC under Markovian sampling and with actor having general policy class approximation. We show that two time-scale AC requires the overall sample complexity at the order of $\mathcal{O}({\epsilon }^{-2.5}{\log }^3({\epsilon }^{-1}))$ to attain an $\epsilon$-accurate stationary point, and two time-scale NAC requires the overall sample complexity at the order of $\mathcal{O}({\epsilon }^{-4}{\log }^2({\epsilon }^{-1}))$ to attain an $\epsilon$-accurate global optimal point. We develop novel techniques for bounding the bias error of the actor due to dynamically changing Markovian sampling and for analyzing the convergence rate of the linear critic with dynamically changing base functions and transition kernel.

arXiv commentThe results of this paper were initially submitted for publication in February 2020

References in corpus (12)

• On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shift
• Neural Policy Gradient Methods: Global Optimality and Rates of Convergence
• Convergence rate and averaging of nonlinear two-time-scale stochastic approximation algorithms
• Neural Proximal/Trust Region Policy Optimization Attains Globally Optimal Policy
• Two Time-scale Off-Policy TD Learning: Non-asymptotic Analysis over Markovian Samples
• Global Convergence of Policy Gradient Methods to (Almost) Locally Optimal Policies
• Finite Sample Analysis of Two-Timescale Stochastic Approximation with Applications to Reinforcement Learning
• Finite Time Analysis of Linear Two-timescale Stochastic Approximation with Markovian Noise
• Improving Sample Complexity Bounds for (Natural) Actor-Critic Algorithms
• Reanalysis of Variance Reduced Temporal Difference Learning
• Non-asymptotic Convergence of Adam-type Reinforcement Learning Algorithms under Markovian Sampling
• A Tale of Two-Timescale Reinforcement Learning with the Tightest Finite-Time Bound

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
• A Finite Time Analysis of Two Time-Scale Actor Critic Methods
• Towards Understanding Asynchronous Advantage Actor-critic: Convergence and Linear Speedup
• Improving Sample Complexity Bounds for (Natural) Actor-Critic Algorithms
• Scalable Multi-Agent Reinforcement Learning for Networked Systems with Average Reward
• Single-Timescale Actor-Critic Provably Finds Globally Optimal Policy
• Doubly Robust Off-Policy Actor-Critic: Convergence and Optimality
• Finite-Sample Analysis of Off-Policy Natural Actor-Critic Algorithm
• Softmax Policy Gradient Methods Can Take Exponential Time to Converge
• Provably Convergent Two-Timescale Off-Policy Actor-Critic with Function Approximation
• Sample and Communication-Efficient Decentralized Actor-Critic Algorithms with Finite-Time Analysis
• A Two-Time-Scale Stochastic Optimization Framework with Applications in Control and Reinforcement Learning
• State Dependent Performative Prediction with Stochastic Approximation
• On the Convergence Rate of Off-Policy Policy Optimization Methods with Density-Ratio Correction
• Analysis of a Target-Based Actor-Critic Algorithm with Linear Function Approximation
• Global Convergence of the ODE Limit for Online Actor-Critic Algorithms in Reinforcement Learning
• Actor-critic is implicitly biased towards high entropy optimal policies
• A Unified Off-Policy Evaluation Approach for General Value Function
• Some Limit Properties of Markov Chains Induced by Stochastic Recursive Algorithms