Abstract
We consider the problem of designing sample efficient learning algorithms for infinite horizon discounted reward Markov Decision Process. Specifically, we propose the Accelerated Natural Policy Gradient (ANPG) algorithm that utilizes an accelerated stochastic gradient descent process to obtain the natural policy gradient. ANPG achieves $\mathcal{O}({\epsilon^{-2}})$ sample complexity and $\mathcal{O}(\epsilon^{-1})$ iteration complexity with general parameterization where $\epsilon$ defines the optimality error. This improves the state-of-the-art sample complexity by a $\log(\frac{1}{\epsilon})$ factor. ANPG is a first-order algorithm and unlike some existing literature, does not require the unverifiable assumption that the variance of importance sampling (IS) weights is upper bounded. In the class of Hessian-free and IS-free algorithms, ANPG beats the best-known sample complexity by a factor of $\mathcal{O}(\epsilon^{-\frac{1}{2}})$ and simultaneously matches their state-of-the-art iteration complexity.
Introduction
In Reinforcement Learning (RL), the primary objective is to find a policy that maximizes cumulative rewards over time. Natural Policy Gradient (NPG) is a widely adopted approach because it accounts for the underlying geometry of the policy space, often leading to more stable and efficient updates than standard gradient descent.
However, NPG methods have historically faced a "sample complexity" bottleneck. To achieve an $\epsilon$-optimal policy, many existing methods require $O(\epsilon^{-3})$ or $O(\epsilon^{-2.5})$ samples. While some recent variance-reduced methods have reached $O(\epsilon^{-2})$, they typically rely on Importance Sampling (IS)—which necessitates the "unverifiable assumption" that the variance of sampling weights remains bounded—or Hessian-aided techniques that are computationally and memory-intensive. This work introduces Accelerated Natural Policy Gradient (ANPG) to address whether an algorithm can be both Hessian-free and IS-free while hitting the optimal $O(\epsilon^{-2})$ sample complexity.
Methodology
ANPG utilizes a two-loop structure to estimate the natural gradient direction efficiently. The "secret sauce" of the algorithm is the application of Accelerated Stochastic Gradient Descent (ASGD) in the inner loop, rather than standard SGD.
To obtain unbiased estimates of the Fisher Information matrix and the advantage function, the authors employ a specific trajectory-based sampling method. A critical theoretical discovery in this work is that while the second-order estimation error in the inner loop decreases at a rate of $1/H$ (where $H$ is the number of inner steps), the first-order error actually decreases exponentially ($e^{-H}$). This exponential decay is the key mathematical lever that allows ANPG to achieve its superior sample efficiency.
Key Results and Comparison
As a theoretical study, the results for ANPG are established through rigorous mathematical proofs under standard assumptions like Fisher Non-Degeneracy. The algorithm achieves a "pure" $O(\epsilon^{-2})$ sample complexity, removing the $\log(1/\epsilon)$ factor found in previous state-of-the-art methods and matching the theoretical lower bound for this class of problems.
As shown in Table 1, ANPG is the first algorithm to simultaneously achieve $O(\epsilon^{-2})$ sample complexity and $O(\epsilon^{-1})$ iteration complexity while remaining both Hessian-free and IS-free. This makes it highly practical for high-dimensional problems, such as those using Deep Neural Networks, where second-order methods are often computationally prohibitive. Furthermore, the paper proves convergence to the global optimum, accounting for a bias term ($\epsilon_{bias}$) that represents the representational limits of the chosen policy class.
Conclusion
ANPG represents a significant step forward in RL optimization, proving that optimal sample complexity is achievable without the computational burden of Hessians or the restrictive assumptions of Importance Sampling. Future research may extend this accelerated analysis to more complex scenarios, such as Constrained RL or Concave Utility RL, and investigate if iteration complexity can be further improved without compromising sample efficiency.
Summary updated