On the Global Convergence Rates of Softmax Policy Gradient Methods

By Jincheng Mei, Chenjun Xiao, Csaba Szepesvari, Dale Schuurmans. International Conference on Machine Learning, 2020

369 citations recorded by the source corpus.

We make three contributions toward better understanding policy gradient methods in the tabular setting. First, we show that with the true gradient, policy gradient with a softmax parametrization converges at a $O(1/t)$ rate, with constants depending on the problem and initialization. This result significantly expands the recent asymptotic convergence results. The analysis relies on two findings: that the softmax policy gradient satisfies a Łojasiewicz inequality, and the minimum probability of an optimal action during optimization can be bounded in terms of its initial value. Second, we analyze entropy regularized policy gradient and show that it enjoys a significantly faster linear convergence rate $O(e^{-t})$ toward softmax optimal policy. This result resolves an open question in the recent literature. Finally, combining the above two results and additional new $\Omega(1/t)$ lower bound results, we explain how entropy regularization improves policy optimization, even with the true gradient, from the perspective of convergence rate. The separation of rates is further explained using the notion of non-uniform Łojasiewicz degree. These results provide a theoretical understanding of the impact of entropy and corroborate existing empirical studies.

Subfields: Artificial Intelligence, Management Science and Operations Research

View Paper: https://www.semanticscholar.org/paper/b76ee983dd28a388ee95a2ab4cf70e7b6f169e12

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 Management Science and Operations Research

Citations in the corpus

Reinforcement Learning: Theory and Algorithms (2019, background): “, 2020d], [Mei et al., 2020] showed that, for the softmax policy class, both the gradient ascent and entropy regularized gradient ascent asymptotically converge at a O(1/t); it is unlikely these methods are have finite rate which are polynomial in other quantities (such as the |S|, |A|, 1/(1 − γ), a”
Batch Reinforcement Learning Through Continuation Method (2021, methodology): “As pointed out in [3, 26], even with access to the exact gradient, the loss surface of the objective function maximizing the expected return is difﬁcult to optimize, leading to slow convergence.”
Recent advances in reinforcement learning in finance (2021, methodology): “The non-asymptotic convergence of policy-based algorithms is shown in other settings, see [263] for the regret analysis of the REINFORCE algorithm for discounted MDPs and [7, 162] for policy gradient methods in the setting of known model parameters.”