Finite-Sample Analysis of Off-Policy Natural Actor-Critic Algorithm

Abstract

In this paper, we provide finite-sample convergence guarantees for an off-policy variant of the natural actor-critic (NAC) algorithm based on Importance Sampling. In particular, we show that the algorithm converges to a global optimal policy with a sample complexity of $\mathcal{O}({\epsilon }^{-3}{\log }^2(1/\epsilon ))$ under an appropriate choice of stepsizes. In order to overcome the issue of large variance due to Importance Sampling, we propose the $Q$-trace algorithm for the critic, which is inspired by the V-trace algorithm \cite{espeholt2018impala}. This enables us to explicitly control the bias and variance, and characterize the trade-off between them. As an advantage of off-policy sampling, a major feature of our result is that we do not need any additional assumptions, beyond the ergodicity of the Markov chain induced by the behavior policy.

References in corpus (15)

• Continuous control with deep reinforcement learning
• Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems
• Reinforcement Learning with Deep Energy-Based Policies
• On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shift
• A Theory of Regularized Markov Decision Processes
• Neural Policy Gradient Methods: Global Optimality and Rates of Convergence
• On the Global Convergence Rates of Softmax Policy Gradient Methods
• Neural Proximal/Trust Region Policy Optimization Attains Globally Optimal Policy
• Off-Policy Actor-Critic
• Fast Global Convergence of Natural Policy Gradient Methods with Entropy Regularization
• A Finite Time Analysis of Two Time-Scale Actor Critic Methods
• Non-asymptotic Convergence Analysis of Two Time-scale (Natural) Actor-Critic Algorithms
• Stochastic approximation with cone-contractive operators: Sharp ${\ell }_{\infty }$-bounds for $Q$-learning
• Convergent Actor-Critic Algorithms Under Off-Policy Training and Function Approximation
• A Lyapunov Theory for Finite-Sample Guarantees of Asynchronous Q-Learning and TD-Learning Variants

Cited by in corpus (2)

• A Lyapunov Theory for Finite-Sample Guarantees of Asynchronous Q-Learning and TD-Learning Variants
• Global Optimality and Finite Sample Analysis of Softmax Off-Policy Actor Critic under State Distribution Mismatch