On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shift

Abstract

Policy gradient methods are among the most effective methods in challenging reinforcement learning problems with large state and/or action spaces. However, little is known about even their most basic theoretical convergence properties, including: if and how fast they converge to a globally optimal solution or how they cope with approximation error due to using a restricted class of parametric policies. This work provides provable characterizations of the computational, approximation, and sample size properties of policy gradient methods in the context of discounted Markov Decision Processes (MDPs). We focus on both: "tabular" policy parameterizations, where the optimal policy is contained in the class and where we show global convergence to the optimal policy; and parametric policy classes (considering both log-linear and neural policy classes), which may not contain the optimal policy and where we provide agnostic learning results. One central contribution of this work is in providing approximation guarantees that are average case -- which avoid explicit worst-case dependencies on the size of state space -- by making a formal connection to supervised learning under distribution shift. This characterization shows an important interplay between estimation error, approximation error, and exploration (as characterized through a precisely defined condition number).

arXiv commentCorollary 6.1 added for a cleaner comparison to prior work. ${\epsilon }_{\mathrm{bias}}$ is now used instead of ${\epsilon }_{\mathrm{approx}}$ to denote the transfer approximation error

References in corpus (12)

• Trust Region Policy Optimization
• Global Convergence of Policy Gradient Methods for the Linear Quadratic Regulator
• Maximum a Posteriori Policy Optimisation
• Provably Efficient Reinforcement Learning with Linear Function Approximation
• Contextual Decision Processes with Low Bellman Rank are PAC-Learnable
• A unified view of entropy-regularized Markov decision processes
• A Theory of Regularized Markov Decision Processes
• Parallelizing Stochastic Gradient Descent for Least Squares Regression: mini-batching, averaging, and model misspecification
• Neural Proximal/Trust Region Policy Optimization Attains Globally Optimal Policy
• Information-Theoretic Considerations in Batch Reinforcement Learning
• Approximate Policy Iteration Schemes: A Comparison
• Exploration-Enhanced POLITEX

Cited by in corpus (66)

• D4RL: Datasets for Deep Data-Driven Reinforcement Learning
• Neural Policy Gradient Methods: Global Optimality and Rates of Convergence
• A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis and Application to Actor-Critic
• Safe Reinforcement Learning via Curriculum Induction
• Fast Global Convergence of Natural Policy Gradient Methods with Entropy Regularization
• Global Convergence of Policy Gradient Methods to (Almost) Locally Optimal Policies
• Variational Policy Gradient Method for Reinforcement Learning with General Utilities
• Provably Efficient Safe Exploration via Primal-Dual Policy Optimization
• Provably Good Batch Reinforcement Learning Without Great Exploration
• Non-asymptotic Convergence Analysis of Two Time-scale (Natural) Actor-Critic Algorithms
• Conservative Safety Critics for Exploration
• Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?
• PC-PG: Policy Cover Directed Exploration for Provable Policy Gradient Learning
• Information Theoretic Regret Bounds for Online Nonlinear Control
• Reward-Free Exploration for Reinforcement Learning
• Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal Sample Complexity
• Improving Sample Complexity Bounds for (Natural) Actor-Critic Algorithms
• SquirRL: Automating Attack Analysis on Blockchain Incentive Mechanisms with Deep Reinforcement Learning
• Model-free Reinforcement Learning in Infinite-horizon Average-reward Markov Decision Processes
• Average-reward model-free reinforcement learning: a systematic review and literature mapping
• Bellman-consistent Pessimism for Offline Reinforcement Learning
• Single-Timescale Actor-Critic Provably Finds Globally Optimal Policy
• Revisiting Design Choices in Proximal Policy Optimization
• Muesli: Combining Improvements in Policy Optimization
• Upper Confidence Primal-Dual Reinforcement Learning for CMDP with Adversarial Loss
• MADE: Exploration via Maximizing Deviation from Explored Regions
• Provably Efficient Reinforcement Learning with Aggregated States
• Optimistic Policy Optimization with Bandit Feedback
• Robust Policy Gradient against Strong Data Corruption
• Sparse Feature Selection Makes Batch Reinforcement Learning More Sample Efficient
• Non-asymptotic Convergence of Adam-type Reinforcement Learning Algorithms under Markovian Sampling
• Greedification Operators for Policy Optimization: Investigating Forward and Reverse KL Divergences
• Corruption-Robust Offline Reinforcement Learning
• Policy-Aware Model Learning for Policy Gradient Methods
• Reinforcement Learning for Load-balanced Parallel Particle Tracing
• On Connections between Constrained Optimization and Reinforcement Learning
• Finite-Sample Analysis of Off-Policy Natural Actor-Critic Algorithm
• Provable Representation Learning for Imitation with Contrastive Fourier Features
• Softmax Policy Gradient Methods Can Take Exponential Time to Converge
• On the Convergence and Optimality of Policy Gradient for Markov Coherent Risk
• A Deeper Look at Discounting Mismatch in Actor-Critic Algorithms
• Generative Adversarial Imitation Learning with Neural Networks: Global Optimality and Convergence Rate
• Infinite-Horizon Offline Reinforcement Learning with Linear Function Approximation: Curse of Dimensionality and Algorithm
• On the Sample Complexity of Reinforcement Learning with Policy Space Generalization
• Towards General Function Approximation in Zero-Sum Markov Games
• Online Sparse Reinforcement Learning
• Escaping from Zero Gradient: Revisiting Action-Constrained Reinforcement Learning via Frank-Wolfe Policy Optimization
• Mean-Field Multi-Agent Reinforcement Learning: A Decentralized Network Approach
• Policy Search by Target Distribution Learning for Continuous Control
• GDI: Rethinking What Makes Reinforcement Learning Different From Supervised Learning
• Provably Correct Optimization and Exploration with Non-linear Policies
• Sample complexity of variance-reduced policy gradient: weaker assumptions and lower bounds
• Finding the Near Optimal Policy via Adaptive Reduced Regularization in MDPs
• Safe Exploration by Solving Early Terminated MDP
• Non-Asymptotic Analysis for Two Time-scale TDC with General Smooth Function Approximation
• On the Convergence Rate of Off-Policy Policy Optimization Methods with Density-Ratio Correction
• Bregman Gradient Policy Optimization
• On the Sample Complexity and Metastability of Heavy-tailed Policy Search in Continuous Control
• A learning-based approach to stochastic optimal control under reach-avoid constraint
• LinkThief: Combining Generalized Structure Knowledge with Node Similarity for Link Stealing Attack against GNN
• Convergence of a Human-in-the-Loop Policy-Gradient Algorithm With Eligibility Trace Under Reward, Policy, and Advantage Feedback
• Curious Explorer: a provable exploration strategy in Policy Learning
• Low Variance Trust Region Optimization with Independent Actors and Sequential Updates in Cooperative Multi-agent Reinforcement Learning
• A Study of Policy Gradient on a Class of Exactly Solvable Models
• Explaining Fast Improvement in Online Imitation Learning
• Variance-Aware Off-Policy Evaluation with Linear Function Approximation