Improving Sample Complexity Bounds for (Natural) Actor-Critic Algorithms

Abstract

The actor-critic (AC) algorithm is a popular method to find an optimal policy in reinforcement learning. In the infinite horizon scenario, the finite-sample convergence rate for the AC and natural actor-critic (NAC) algorithms has been established recently, but under independent and identically distributed (i.i.d.) sampling and single-sample update at each iteration. In contrast, this paper characterizes the convergence rate and sample complexity of AC and NAC under Markovian sampling, with mini-batch data for each iteration, and with actor having general policy class approximation. We show that the overall sample complexity for a mini-batch AC to attain an $\epsilon$-accurate stationary point improves the best known sample complexity of AC by an order of $\mathcal{O}({\epsilon }^{-1}\log (1/\epsilon ))$, and the overall sample complexity for a mini-batch NAC to attain an $\epsilon$-accurate globally optimal point improves the existing sample complexity of NAC by an order of $\mathcal{O}({\epsilon }^{-1}/\log (1/\epsilon ))$. Moreover, the sample complexity of AC and NAC characterized in this work outperforms that of policy gradient (PG) and natural policy gradient (NPG) by a factor of $\mathcal{O}((1-\gamma {)}^{-3})$ and $\mathcal{O}((1-\gamma {)}^{-4}{\epsilon }^{-1}/\log (1/\epsilon ))$, respectively. This is the first theoretical study establishing that AC and NAC attain orderwise performance improvement over PG and NPG under infinite horizon due to the incorporation of critic.

Accepted by NeurIPS 2020

References in corpus (7)

• Sample Efficient Policy Gradient Methods with Recursive Variance Reduction
• A Finite Time Analysis of Two Time-Scale Actor Critic Methods
• Non-asymptotic Convergence Analysis of Two Time-scale (Natural) Actor-Critic Algorithms
• Non-asymptotic Analysis of Biased Stochastic Approximation Scheme
• Reanalysis of Variance Reduced Temporal Difference Learning
• Non-asymptotic Convergence of Adam-type Reinforcement Learning Algorithms under Markovian Sampling
• Provably Convergent Two-Timescale Off-Policy Actor-Critic with Function Approximation

Cited by in corpus (5)

• Towards Understanding Asynchronous Advantage Actor-critic: Convergence and Linear Speedup
• Non-asymptotic Convergence Analysis of Two Time-scale (Natural) Actor-Critic Algorithms
• Sample Complexity Bounds for Two Timescale Value-based Reinforcement Learning Algorithms
• Provably Convergent Two-Timescale Off-Policy Actor-Critic with Function Approximation
• Actor-critic is implicitly biased towards high entropy optimal policies