Abstract
Policy gradient methods are fundamental to modern reinforcement learning (RL), yet they are often hindered by high variance in gradient estimates, leading to slow convergence and poor sample efficiency. This paper provides a refined theoretical analysis of the Stochastic Variance-Reduced Policy Gradient (SVRPG) algorithm. By establishing a tighter bound on the variance of importance sampling weights, we prove that SVRPG achieves a sample complexity of $O(1/\epsilon^{5/3})$ to reach an $\epsilon$-approximate stationary point. This represents a significant improvement over the $O(1/\epsilon^2)$ complexity associated with standard policy gradient methods and previous analyses of SVRPG.
Introduction
Reinforcement learning agents learn to optimize their behavior by interacting with environments and receiving rewards. Policy gradient methods, such as REINFORCE and GPOMDP, are popular because they directly optimize the policy parameters. However, because these methods rely on stochastic trajectories to estimate gradients, they suffer from high variance. This variance necessitates a large number of samples to ensure stable updates, resulting in a sample complexity of $O(1/\epsilon^2)$.
To address this, researchers have adapted variance reduction techniques from supervised learning, specifically Stochastic Variance-Reduced Gradient (SVRG), to the RL setting. While the resulting SVRPG algorithm showed promise in practice, early theoretical work failed to demonstrate a strict improvement in sample complexity over standard methods. This paper bridges that gap by providing the first "sharp" analysis that proves SVRPG's theoretical superiority.
The SVRPG Algorithm
SVRPG reduces variance by utilizing an epoch-based approach consisting of two nested loops:
- Outer Loop: At the beginning of each epoch, the algorithm computes a "full" gradient estimate using a large batch of trajectories at a fixed reference policy.
- Inner Loop: The policy is updated over multiple iterations using smaller mini-batches. To avoid the cost of computing a full gradient at every step, SVRPG uses Importance Sampling (IS) to adjust the reference gradient based on the difference between the current policy and the reference policy.
The primary challenge in this approach is that as the current policy drifts away from the reference policy, the importance sampling weights can become highly volatile, potentially re-introducing high variance. The authors overcome this by proving a new lemma: the variance of the IS weights is bounded by the squared Euclidean distance between the parameters of the two policies ($||\theta_s - \theta_t||^2$).
Theoretical Contributions
By leveraging the tighter variance bound, the authors provide a specific strategy for tuning the epoch length ($m$) and mini-batch size ($B$). This optimization allows for a more efficient balance between the computational cost of the outer loop and the variance reduction in the inner loop.
As illustrated in the table above, this refined analysis yields a sample complexity of $O(1/\epsilon^{5/3})$. In the context of optimization theory, improving the complexity by a factor of $O(1/\epsilon^{1/3})$ is a major advancement, confirming that SVRPG is fundamentally more sample-efficient than standard stochastic gradient (SG) approaches.
Empirical Results
The authors validated their theoretical claims using two standard reinforcement learning benchmarks from OpenAI Gym: Cartpole and Mountain Car (Continuous). These environments serve as essential testbeds for evaluating the stability and efficiency of RL algorithms.
Key findings from the experiments include:
- Superior Efficiency: SVRPG reached higher cumulative rewards using significantly fewer trajectories than REINFORCE or GPOMDP.
- Enhanced Stability: In the Mountain Car task, which is notoriously difficult due to sparse rewards and high variance, standard methods often failed to converge. In contrast, SVRPG demonstrated robust and reliable convergence.
- Parameter Sensitivity: The experiments confirmed the theoretical prediction regarding optimal batch sizes. For instance, a mini-batch size of $B=10$ for Cartpole and $B=20$ for Mountain Car provided the best performance, aligning with the authors' mathematical recipe.
Conclusion and Future Work
This work establishes a new theoretical benchmark for variance-reduced policy gradients, proving they are strictly better than standard methods in terms of sample complexity. While the paper successfully bounds the variance of importance sampling, IS remains sensitive to large policy shifts. Future research may explore whether even better complexity, such as $O(1/\epsilon^{3/2})$, can be achieved by incorporating more advanced variance reduction frameworks like SPIDER or SARAH into the policy gradient setting.
Summary updated