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

Understand

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.