On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shift
This work addresses a foundational gap in reinforcement learning theory for researchers and practitioners, offering rigorous insights into policy gradient methods, though it is incremental in extending existing theoretical frameworks.
The paper tackles the lack of theoretical convergence guarantees for policy gradient methods in reinforcement learning, providing provable characterizations of computational, approximation, and sample size properties in discounted Markov Decision Processes, with results including global convergence to optimal policies in tabular settings and agnostic learning for parametric classes.
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).