Sample complexity of variance-reduced policy gradient: weaker assumptions and lower bounds

Abstract

Several variance-reduced versions of REINFORCE based on importance sampling achieve an improved $O({\epsilon }^{-3})$ sample complexity to find an $\epsilon$-stationary point, under an unrealistic assumption on the variance of the importance weights. In this paper, we propose the \algo (Defensive Policy Gradient) algorithm, based on defensive importance sampling, which achieves the same rate without any assumption on the variance of ordinary importance weights. We also establish lower bounds in a generalized black-box policy-optimization model that hides states and actions and permits parameter-dependent rewards. In this model, the optimal rates are $\Theta ({\epsilon }^{-4})$ with bounded-variance one-policy feedback and $\Theta ({\epsilon }^{-3})$ with mean-square-smooth coupled two-policy feedback. Under standard policy-regularity conditions, REINFORCE and \algo realize the corresponding oracle conditions and attain the $O({\epsilon }^{-4})$ and $O({\epsilon }^{-3})$ upper bounds, respectively. Although the lower bounds do not apply directly to the classical MDP interaction model in which these algorithms operate, this correspondence provides oracle-level evidence that the faster rate of \algo is optimal and genuinely separated from that of vanilla policy gradient.

References in corpus (22)

• Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems
• A Stochastic Gradient Method with an Exponential Convergence Rate for Finite Training Sets
• Infinite-Horizon Policy-Gradient Estimation
• SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator
• Stochastic Variance Reduction for Nonconvex Optimization
• On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shift
• SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradient
• Stochastic Variance Reduction Methods for Policy Evaluation
• How To Make the Gradients Small Stochastically: Even Faster Convex and Nonconvex SGD
• Sample Efficient Policy Gradient Methods with Recursive Variance Reduction
• An Improved Analysis of (Variance-Reduced) Policy Gradient and Natural Policy Gradient Methods
• Momentum-Based Variance Reduction in Non-Convex SGD
• PAGE: A Simple and Optimal Probabilistic Gradient Estimator for Nonconvex Optimization
• On the Convergence and Sample Efficiency of Variance-Reduced Policy Gradient Method
• An Improved Convergence Analysis of Stochastic Variance-Reduced Policy Gradient
• Stochastic Recursive Momentum for Policy Gradient Methods
• A general sample complexity analysis of vanilla policy gradient
• A Hybrid Stochastic Policy Gradient Algorithm for Reinforcement Learning
• Stochastic Variance Reduction for Policy Gradient Estimation
• Second-Order Information in Non-Convex Stochastic Optimization: Power and Limitations
• Stochastic Policy Gradient Methods: Improved Sample Complexity for Fisher-non-degenerate Policies
• PAGE-PG: A Simple and Loopless Variance-Reduced Policy Gradient Method with Probabilistic Gradient Estimation