On the Convergence and Sample Efficiency of Variance-Reduced Policy Gradient Method

Abstract

Policy gradient (PG) gives rise to a rich class of reinforcement learning (RL) methods. Recently, there has been an emerging trend to accelerate the existing PG methods such as REINFORCE by the \emph{variance reduction} techniques. However, all existing variance-reduced PG methods heavily rely on an uncheckable importance weight assumption made for every single iteration of the algorithms. In this paper, a simple gradient truncation mechanism is proposed to address this issue. Moreover, we design a Truncated Stochastic Incremental Variance-Reduced Policy Gradient (TSIVR-PG) method, which is able to maximize not only a cumulative sum of rewards but also a general utility function over a policy's long-term visiting distribution. We show an $\tilde{\mathcal{O}}({\epsilon }^{-3})$ sample complexity for TSIVR-PG to find an $\epsilon$-stationary policy. By assuming the overparameterizaiton of policy and exploiting the hidden convexity of the problem, we further show that TSIVR-PG converges to global $\epsilon$-optimal policy with $\tilde{\mathcal{O}}({\epsilon }^{-2})$ samples.

References in corpus (15)

• Trust Region Policy Optimization
• Global Convergence of Policy Gradient Methods for the Linear Quadratic Regulator
• SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator
• Provably Efficient Maximum Entropy Exploration
• On the Global Convergence Rates of Softmax Policy Gradient Methods
• Finite-sum Composition Optimization via Variance Reduced Gradient Descent
• Reinforcement Learning with Convex Constraints
• Fast Global Convergence of Natural Policy Gradient Methods with Entropy Regularization
• Sample Efficient Policy Gradient Methods with Recursive Variance Reduction
• Global Convergence of Policy Gradient Methods to (Almost) Locally Optimal Policies
• Variational Policy Gradient Method for Reinforcement Learning with General Utilities
• Fast Incremental Method for Nonconvex Optimization
• Accelerated Method for Stochastic Composition Optimization with Nonsmooth Regularization
• Cautious Reinforcement Learning via Distributional Risk in the Dual Domain
• A Hybrid Stochastic Policy Gradient Algorithm for Reinforcement Learning

Cited by in corpus (5)

• Policy Mirror Descent for Regularized Reinforcement Learning: A Generalized Framework with Linear Convergence
• Joint Optimization of Multi-Objective Reinforcement Learning with Policy Gradient Based Algorithm
• Softmax Policy Gradient Methods Can Take Exponential Time to Converge
• Sample complexity of variance-reduced policy gradient: weaker assumptions and lower bounds
• Understanding the Effect of Stochasticity in Policy Optimization