<p>Policy parameterization is commonly used in reinforcement learning problems to deal with large state-action spaces. Typically a gradient search is done on the parameterized policy space to find better policies. Policy gradient search is known to be very slow in practice. Here we use Nesterov’s accelerated gradient search to fasten the search. This method initially developed for convex optimization, has a faster convergence rate than plain gradient search, has recently proven to have good performance in the stochastic setting. In this work, we consider two different ways of getting the gradient: first is the using the direct gradient (first-order) from the REINFORCE method and the second is estimation using the Simultaneous Perturbation Stochastic Approximation (SPSA) scheme (zeroth-order). We study different actor-critic algorithms for the discounted cost criterion in which the actor uses this accelerated Nesterov method with both constant and time-varying momentum. Our main result is to show the convergence of this algorithm using stochastic approximation theory. To the best of our knowledge this is the first work to address the convergence issues for accelerated actor-critic algorithms with linear function approximation. We have also given experimental results to show that the accelerated algorithms perform better over plain methods on many different test domains.</p>