Sample Efficient Policy Gradient Methods with Recursive Variance Reduction

Abstract

Improving the sample efficiency in reinforcement learning has been a long-standing research problem. In this work, we aim to reduce the sample complexity of existing policy gradient methods. We propose a novel policy gradient algorithm called SRVR-PG, which only requires $O(1/{\epsilon }^{3/2})$ episodes to find an $\epsilon$-approximate stationary point of the nonconcave performance function $J(\mathbf{\theta })$ (i.e., $\mathbf{\theta }$ such that $\Vert \nabla J(\mathbf{\theta }){\Vert }_2^2\le \epsilon$). This sample complexity improves the existing result $O(1/{\epsilon }^{5/3})$ for stochastic variance reduced policy gradient algorithms by a factor of $O(1/{\epsilon }^{1/6})$. In addition, we also propose a variant of SRVR-PG with parameter exploration, which explores the initial policy parameter from a prior probability distribution. We conduct numerical experiments on classic control problems in reinforcement learning to validate the performance of our proposed algorithms.

arXiv comment23 pages, 2 figures, 3 tables. In ICLR 2020

References in corpus (19)

• Trust Region Policy Optimization
• High-Dimensional Continuous Control Using Generalized Advantage Estimation
• A Convergence Theory for Deep Learning via Over-Parameterization
• Deep Reinforcement Learning: An Overview
• Safe, Multi-Agent, Reinforcement Learning for Autonomous Driving
• SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator
• Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networks
• Non-convex Finite-Sum Optimization Via SCSG Methods
• Neural Policy Gradient Methods: Global Optimality and Rates of Convergence
• Variance Reduction for Policy Gradient with Action-Dependent Factorized Baselines
• Stop Wasting My Gradients: Practical SVRG
• A Simple Proximal Stochastic Gradient Method for Nonsmooth Nonconvex Optimization
• Stochastic Variance Reduction Methods for Policy Evaluation
• Neural Proximal/Trust Region Policy Optimization Attains Globally Optimal Policy
• Generalization Error Bounds of Gradient Descent for Learning Over-parameterized Deep ReLU Networks
• The Mirage of Action-Dependent Baselines in Reinforcement Learning
• On the Global Convergence of Actor-Critic: A Case for Linear Quadratic Regulator with Ergodic Cost
• Policy Optimization via Importance Sampling
• Stochastic Variance Reduction for Policy Gradient Estimation

Cited by in corpus (20)

• Neural Policy Gradient Methods: Global Optimality and Rates of Convergence
• Variational Policy Gradient Method for Reinforcement Learning with General Utilities
• A Finite Time Analysis of Two Time-Scale Actor Critic Methods
• Improving Sample Complexity Bounds for (Natural) Actor-Critic Algorithms
• On the Convergence and Sample Efficiency of Variance-Reduced Policy Gradient Method
• Stochastic Recursive Momentum for Policy Gradient Methods
• Non-asymptotic Convergence of Adam-type Reinforcement Learning Algorithms under Markovian Sampling
• History-Gradient Aided Batch Size Adaptation for Variance Reduced Algorithms
• Policy Mirror Descent for Regularized Reinforcement Learning: A Generalized Framework with Linear Convergence
• A general sample complexity analysis of vanilla policy gradient
• Joint Optimization of Multi-Objective Reinforcement Learning with Policy Gradient Based Algorithm
• A Hybrid Stochastic Policy Gradient Algorithm for Reinforcement Learning
• A Deeper Look at Discounting Mismatch in Actor-Critic Algorithms
• Variance-Reduced Off-Policy Memory-Efficient Policy Search
• Generative Adversarial Imitation Learning with Neural Networks: Global Optimality and Convergence Rate
• Sample complexity of variance-reduced policy gradient: weaker assumptions and lower bounds
• Bregman Gradient Policy Optimization
• Distributed Policy Gradient with Variance Reduction in Multi-Agent Reinforcement Learning
• On the Convergence Rate of Off-Policy Policy Optimization Methods with Density-Ratio Correction
• A Study of Policy Gradient on a Class of Exactly Solvable Models