On the Sample Complexity of Actor-Critic Method for Reinforcement Learning with Function Approximation
This work provides foundational theoretical guarantees for actor-critic methods in continuous spaces with function approximation, addressing a key bottleneck in reinforcement learning theory.
The authors tackled the problem of unknown convergence rates for actor-critic algorithms in reinforcement learning by introducing a new variant that uses Monte Carlo rollouts to control bias, enabling the first derivation of sample complexity bounds for policy gradient updates. They established conditions where sample complexity is comparable to stochastic gradient methods or slower due to critic error, with results validated on navigation and pendulum problems.
Reinforcement learning, mathematically described by Markov Decision Problems, may be approached either through dynamic programming or policy search. Actor-critic algorithms combine the merits of both approaches by alternating between steps to estimate the value function and policy gradient updates. Due to the fact that the updates exhibit correlated noise and biased gradient updates, only the asymptotic behavior of actor-critic is known by connecting its behavior to dynamical systems. This work puts forth a new variant of actor-critic that employs Monte Carlo rollouts during the policy search updates, which results in controllable bias that depends on the number of critic evaluations. As a result, we are able to provide for the first time the convergence rate of actor-critic algorithms when the policy search step employs policy gradient, agnostic to the choice of policy evaluation technique. In particular, we establish conditions under which the sample complexity is comparable to stochastic gradient method for non-convex problems or slower as a result of the critic estimation error, which is the main complexity bottleneck. These results hold in continuous state and action spaces with linear function approximation for the value function. We then specialize these conceptual results to the case where the critic is estimated by Temporal Difference, Gradient Temporal Difference, and Accelerated Gradient Temporal Difference. These learning rates are then corroborated on a navigation problem involving an obstacle and the pendulum problem which provide insight into the interplay between optimization and generalization in reinforcement learning.