An Improved Convergence Analysis of Stochastic Variance-Reduced Policy Gradient

Abstract

We revisit the stochastic variance-reduced policy gradient (SVRPG) method proposed by Papini et al. (2018) for reinforcement learning. We provide an improved convergence analysis of SVRPG and show that it can find an $\epsilon$-approximate stationary point of the performance function within $O(1/{\epsilon }^{5/3})$ trajectories. This sample complexity improves upon the best known result $O(1/{\epsilon }^2)$ by a factor of $O(1/{\epsilon }^{1/3})$. At the core of our analysis is (i) a tighter upper bound for the variance of importance sampling weights, where we prove that the variance can be controlled by the parameter distance between different policies; and (ii) a fine-grained analysis of the epoch length and batch size parameters such that we can significantly reduce the number of trajectories required in each iteration of SVRPG. We also empirically demonstrate the effectiveness of our theoretical claims of batch sizes on reinforcement learning benchmark tasks.

arXiv comment10 pages, 2 figures, 1 table. To appear in the proceedings of the 35th International Conference on Uncertainty in Artificial Intelligence

References in corpus (7)

• The Optimal Reward Baseline for Gradient-Based Reinforcement Learning
• Variance Reduction for Faster Non-Convex Optimization
• Stop Wasting My Gradients: Practical SVRG
• Stochastic Variance Reduction Methods for Policy Evaluation
• The Mirage of Action-Dependent Baselines in Reinforcement Learning
• Policy Optimization via Importance Sampling
• Stochastic Variance Reduction for Policy Gradient Estimation

Cited by in corpus (6)

• Neural Policy Gradient Methods: Global Optimality and Rates of Convergence
• Stochastic Recursive Momentum for Policy Gradient Methods
• History-Gradient Aided Batch Size Adaptation for Variance Reduced Algorithms
• Joint Optimization of Multi-Objective Reinforcement Learning with Policy Gradient Based Algorithm
• Generative Adversarial Imitation Learning with Neural Networks: Global Optimality and Convergence Rate
• Sample complexity of variance-reduced policy gradient: weaker assumptions and lower bounds