An Approximate Policy Iteration Viewpoint of Actor-Critic Algorithms
This provides the first theoretical sample complexity guarantee for policy-based methods in off-policy settings, addressing a key bottleneck in reinforcement learning for applications like robotics and control.
The paper tackles the sample complexity of policy-based reinforcement learning methods under off-policy sampling and linear function approximation, establishing an overall O(ε^{-2}) sample complexity for finding an optimal policy, with geometric convergence for the actor and finite-sample guarantees for the critic.
In this work, we consider policy-based methods for solving the reinforcement learning problem, and establish the sample complexity guarantees. A policy-based algorithm typically consists of an actor and a critic. We consider using various policy update rules for the actor, including the celebrated natural policy gradient. In contrast to the gradient ascent approach taken in the literature, we view natural policy gradient as an approximate way of implementing policy iteration, and show that natural policy gradient (without any regularization) enjoys geometric convergence when using increasing stepsizes. As for the critic, we consider using TD-learning with linear function approximation and off-policy sampling. Since it is well-known that in this setting TD-learning can be unstable, we propose a stable generic algorithm (including two specific algorithms: the $λ$-averaged $Q$-trace and the two-sided $Q$-trace) that uses multi-step return and generalized importance sampling factors, and provide the finite-sample analysis. Combining the geometric convergence of the actor with the finite-sample analysis of the critic, we establish for the first time an overall $\mathcal{O}(ε^{-2})$ sample complexity for finding an optimal policy (up to a function approximation error) using policy-based methods under off-policy sampling and linear function approximation.