Finite-Sample Analysis of Off-Policy Natural Actor-Critic with Linear Function Approximation
This addresses the challenge of sample-efficient off-policy learning in reinforcement learning, which is crucial for real-world applications like robotics and autonomous systems, though it is incremental as it builds on existing actor-critic methods.
The paper tackles the problem of off-policy reinforcement learning with function approximation by developing a novel natural actor-critic algorithm, achieving a sample complexity of O(ε^{-3}) and an improved convergence rate of O(1/T) for the policy gradient, outperforming prior bounds.
In this paper, we develop a novel variant of off-policy natural actor-critic algorithm with linear function approximation and we establish a sample complexity of $\mathcal{O}(ε^{-3})$, outperforming all the previously known convergence bounds of such algorithms. In order to overcome the divergence due to deadly triad in off-policy policy evaluation under function approximation, we develop a critic that employs $n$-step TD-learning algorithm with a properly chosen $n$. We present finite-sample convergence bounds on this critic under both constant and diminishing step sizes, which are of independent interest. Furthermore, we develop a variant of natural policy gradient under function approximation, with an improved convergence rate of $\mathcal{O}(1/T)$ after $T$ iterations. Combining the finite sample error bounds of actor and the critic, we obtain the $\mathcal{O}(ε^{-3})$ sample complexity. We derive our sample complexity bounds solely based on the assumption that the behavior policy sufficiently explores all the states and actions, which is a much lighter assumption compared to the related literature.