TY - JOUR
T1 - On the theory of policy gradient methods
T2 - Optimality, approximation, and distribution shift
AU - Agarwal, Alekh
AU - Kakade, Sham M.
AU - Lee, Jason D.
AU - Mahajan, Gaurav
N1 - Publisher Copyright: © 2021 Microtome Publishing. All rights reserved.
PY - 2021
Y1 - 2021
N2 - 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).
AB - 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).
KW - Policy Gradient
KW - Reinforcement Learning
UR - http://www.scopus.com/inward/record.url?scp=85107297227&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85107297227&partnerID=8YFLogxK
M3 - Article
SN - 1532-4435
VL - 22
JO - Journal of Machine Learning Research
JF - Journal of Machine Learning Research
ER -