A general sample complexity analysis of vanilla policy gradient

Abstract

We adapt recent tools developed for the analysis of Stochastic Gradient Descent (SGD) in non-convex optimization to obtain convergence and sample complexity guarantees for the vanilla policy gradient (PG). Our only assumptions are that the expected return is smooth w.r.t. the policy parameters, that its $H$-step truncated gradient is close to the exact gradient, and a certain ABC assumption. This assumption requires the second moment of the estimated gradient to be bounded by $A\ge 0$ times the suboptimality gap, $B\ge 0$ times the norm of the full batch gradient and an additive constant $C\ge 0$, or any combination of aforementioned. We show that the ABC assumption is more general than the commonly used assumptions on the policy space to prove convergence to a stationary point. We provide a single convergence theorem that recovers the $\tilde{\mathcal{O}}({\epsilon }^{-4})$ sample complexity of PG to a stationary point. Our results also affords greater flexibility in the choice of hyper parameters such as the step size and the batch size $m$, including the single trajectory case (i.e., $m=1$). When an additional relaxed weak gradient domination assumption is available, we establish a novel global optimum convergence theory of PG with $\tilde{\mathcal{O}}({\epsilon }^{-3})$ sample complexity. We then instantiate our theorems in different settings, where we both recover existing results and obtain improved sample complexity, e.g., $\tilde{\mathcal{O}}({\epsilon }^{-3})$ sample complexity for the convergence to the global optimum for Fisher-non-degenerated parametrized policies.

arXiv commentAccepted at AISTATS 2022. This version updates references and adds acknowledgement to Matteo Papini who greatly improved our work before the submission

References in corpus (13)

• Infinite-Horizon Policy-Gradient Estimation
• Global Convergence of Policy Gradient Methods for the Linear Quadratic Regulator
• SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator
• Bridging the Gap Between Value and Policy Based Reinforcement Learning
• On the Global Convergence Rates of Softmax Policy Gradient Methods
• Better Theory for SGD in the Nonconvex World
• Unified Optimal Analysis of the (Stochastic) Gradient Method
• Sample Efficient Policy Gradient Methods with Recursive Variance Reduction
• An Improved Analysis of (Variance-Reduced) Policy Gradient and Natural Policy Gradient Methods
• Global Optimality Guarantees For Policy Gradient Methods
• Stochastic Recursive Momentum for Policy Gradient Methods
• A Hybrid Stochastic Policy Gradient Algorithm for Reinforcement Learning
• Sample Efficient Reinforcement Learning with REINFORCE

Cited by in corpus (1)

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