Optimality and Approximation with Policy Gradient Methods in Markov Decision Processes

By Alekh Agarwal, Sham M. Kakade, Jason D. Lee, Gaurav Mahajan. 2019

345 citations recorded by the source corpus.

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 (say with a sufficiently rich policy class); how they cope with approximation error due to using a restricted class of parametric policies; or their finite sample behavior. Such characterizations are important not only to compare these methods to their approximate value function counterparts (where such issues are relatively well understood, at least in the worst case), but also to help with more principled approaches to algorithm design. This work provides provable characterizations of computational, approximation, and sample size issues with regards to policy gradient methods in the context of discounted Markov Decision Processes (MDPs). We focus on both: 1) "tabular" policy parameterizations, where the optimal policy is contained in the class and where we show global convergence to the optimal policy, and 2) restricted policy classes, which may not contain the optimal policy and where we provide agnostic learning results. One insight of this work is in formalizing the importance how a favorable initial state distribution provides a means to circumvent worst-case exploration issues. Overall, these results place policy gradient methods under a solid theoretical footing, analogous to the global convergence guarantees of iterative value function based algorithms.

Subfields: Artificial Intelligence, Electrical and Electronic Engineering

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Electrical and Electronic Engineering

Citations in the corpus

D4RL: Datasets for Deep Data-Driven Reinforcement Learning (2020, methodology): “…those from deterministic expert policies, are particularly problematic for oﬄine RL algorithms and may cause divergence both empirically [Fujimoto et al., 2018, Kumar et al., 2019] and theoretically [Munos, 2003, Farahmand et al., 2010, Kumar et al., 2019, Agarwal et al., 2019a, Du et al., 2020].”
Statistically Efficient Off-Policy Policy Gradients (2020, neutral): “A similar assumption is made in Agarwal et al. (2019). The above uniform bounds may also be replaced with bounds on second moments at the cost of stronger conditions on nuisance estimate convergence in, e.”
Reinforcement Learning with Trajectory Feedback (2020, background): “However, this approach fails in cases the exploration is challenging (Agarwal et al. 2020), i.”
A Game Theoretic Framework for Model Based Reinforcement Learning (2020, background): “To obtain a globally accurate model, we need the ability to collect data from all parts of the state space (Agarwal et al., 2019b), which is often impossible.”
Exponential Lower Bounds for Batch Reinforcement Learning: Batch RL can be Exponentially Harder than Online RL (2020, methodology): “The available results for learning in tabular MDPs consider a similar setting, where only noisy observations are available (Azar et al., 2012; Li et al., 2020; Agarwal et al., 2020b).”
Q* Approximation Schemes for Batch Reinforcement Learning: A Theoretical Comparison (2020, background): “, CPI [Kakade and Langford, 2002] (see also Agarwal et al. [2019]).”
Reward-Free Exploration for Reinforcement Learning (2020, methodology): “However, the episodic setting has some unique characters (For example, we not every state can be arrive at the ﬁrst step and the corresponding analysis in Agarwal et al. [2019] does not apply).”
Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithms (2019, methodology): “Compared with value-based RL methods, policy-based ones enjoy better convergence guarantees [69, 75, 76, 77], especially with neural networks for function approximation [78, 79], which can readily handle massive or even continuous state-action spaces.”
Reinforcement Learning: Theory and Algorithms (2019, methodology): “The convergence rates in this chapter are largely derived from [Agarwal et al., 2019].”
Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimism (2021, background): “(3) When C ∈ [1, 2), the most played arm achieves an exponential rate in N , whereas the upper bound for LCB is only 1/ √ N .”
Revisiting Design Choices in Proximal Policy Optimization (2020, neutral): “Mirror Descent has proven a valuable theoretical tool for deriving convergence results for policy gradient-type methods [1, 11, 14, 16].”
Provably Efficient Exploration in Policy Optimization (2019, methodology): “In the special case where the reward function r h is linear in the feature map φ k−1 h defined subsequently, which implies that the Q-function Q ,k−1 h is also linear in φ k−1 h , the updated policy π k can be equivalently obtained by one iteration of NPG when the policy is parameterized by an energ”
Reinforcement Learning for Selective Key Applications in Power Systems: Recent Advances and Future Challenges (2021, methodology): “The convergence of policy-based methods with restricted policy classes to the global optimum has been shown in a recent work [20] under the tabular policy parameterization.”
Applications of reinforcement learning in energy systems (2021, background): “The research community has also attempted to study the theoretical convergence properties of PG methods from a non-convex optimization perspective [184,185].”
Provably Good Batch Reinforcement Learning Without Great Exploration (2020, methodology): “For detailed discussions on the unreasonableness of concentrability, please see [5, 34, 1].”
Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning? (2019, methodology): “For policy-based learning, Agarwal et al. (2019) gave polynomial upper bounds which depend on a parameter that measures the difference between the initial distribution and the distribution induced by the optimal policy.”
A review of cooperative multi-agent deep reinforcement learning (2019, background): “Despite the issue of data efficiency, policy-based algorithms provide better convergence guarantees over the value-based algorithms [2, 245, 257].”
On the Global Convergence Rates of Softmax Policy Gradient Methods (2020, methodology): “Recently, Agarwal et al. (2019) showed that softmax policy gradient asymptotically converges to π∗, i.e., V πθt (ρ) → V ∗(ρ) as t → ∞ provided that µ(s) > 0 holds for all states s ∈ S.”
On Reward-Free Reinforcement Learning with Linear Function Approximation (2020, methodology): “…this framework is to collect a dataset with suﬃciently good coverage over the state space during the exploration phase, so that one can apply a batch RL algorithm on the dataset [Chen and Jiang, 2019, Agarwal et al., 2019, Antos et al., 2008, Munos and Szepesvári, 2008] during the planning phase.”