Finite-Sample Analysis of Off-Policy Natural Actor-Critic Algorithm
Preprint
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.
Keywords
All Related Versions
This publication has 23 references indexed in Scilit:
- On the sample complexity of actor-critic method for reinforcement learning with function approximationMachine Learning, 2023
- Policy mirror descent for reinforcement learning: linear convergence, new sampling complexity, and generalized problem classesMathematical Programming, 2022
- First-order and Stochastic Optimization Methods for Machine Learning2020
- Mastering the game of Go with deep neural networks and tree searchNature, 2016
- Policy gradient in Lipschitz Markov Decision ProcessesMachine Learning, 2015
- Error bounds for constant step-size -learningSystems & Control Letters, 2012
- Natural Actor-CriticNeurocomputing, 2008
- Learning Rates for Q-LearningLecture Notes in Computer Science, 2001
- Average cost temporal-difference learningAutomatica, 1999
- The actor-critic algorithm as multi-time-scale stochastic approximationSādhanā, 1997