{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,22]],"date-time":"2026-08-22T09:17:36Z","timestamp":1787390256631,"version":"build-2736575974"},"reference-count":40,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"5","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Sci. Comput."],"published-print":{"date-parts":[[2023,10,31]]},"abstract":"<jats:p>Abstract.<\/jats:p>\n                  <jats:p>Policy gradient algorithms have been widely applied to Markov decision processes and reinforcement learning problems in recent years. Regularization with various entropy functions is often used to encourage exploration and improve stability. This paper proposes an approximate Newton method for the policy gradient algorithm with entropy regularization. In the case of Shannon entropy, the resulting algorithm reproduces the natural policy gradient algorithm. For other entropy functions, this method results in brand-new policy gradient algorithms. We prove that all these algorithms enjoy Newton-type quadratic convergence and that the corresponding gradient flow converges globally to the optimal solution. We use synthetic and industrial-scale examples to demonstrate that the proposed approximate Newton method typically converges in single-digit iterations, often orders of magnitude faster than other state-of-the-art algorithms.<\/jats:p>","DOI":"10.1137\/22m1492088","type":"journal-article","created":{"date-parts":[[2023,9,26]],"date-time":"2023-09-26T11:09:21Z","timestamp":1695726561000},"page":"A2585-A2609","source":"Crossref","is-referenced-by-count":3,"title":["Approximate Newton Policy Gradient Algorithms"],"prefix":"10.1137","volume":"45","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7076-7600","authenticated-orcid":true,"given":"Haoya","family":"Li","sequence":"first","affiliation":[{"name":"Department of Mathematics, Stanford University, Stanford, CA 94305 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Samarth","family":"Gupta","sequence":"additional","affiliation":[{"name":"Department of Electrical and Computer Engineering, Carnegie Mellon University, Pittsburgh, PA 15213 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Hsiangfu","family":"Yu","sequence":"additional","affiliation":[{"name":"Amazon Search, Palo Alto, CA 94303 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1547-1457","authenticated-orcid":true,"given":"Lexing","family":"Ying","sequence":"additional","affiliation":[{"name":"Department of Mathematics, Stanford University, Stanford, CA 94305-2125 USA, and Amazon Search, Palo Alto, CA 94303 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Inderjit","family":"Dhillon","sequence":"additional","affiliation":[{"name":"Department of Computer Sciences, University of Texas at Austin, Austin, TX 78712-1188 USA, and Google."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2023,9,26]]},"reference":[{"key":"ref1","unstructured":"A. Agarwal , \nS. M. Kakade , \nJ. D. Lee , and \nG. Mahajan  , Optimality and approximation with policy gradient methods in Markov decision processes, in Conference on Learning Theory, PMLR, 2020, pp. 64\u201366."},{"key":"ref2","unstructured":"Z. Ahmed , \nN. Le Roux , \nM. Norouzi , and \nD. Schuurmans  , Understanding the impact of entropy on policy optimization, in International Conference on Machine Learning, PMLR, 2019, pp. 151\u2013160."},{"key":"ref3","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1111\/j.2517-6161.1966.tb00626.x","volume":"28","author":"Ali S. M.","year":"1966","journal-title":"J. Roy. Statist. Soc. Ser. B"},{"key":"ref4","first-page":"679","volume":"6","author":"Bellman R.","year":"1957","journal-title":"J. Math. Mech."},{"key":"ref5","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804441"},{"key":"ref6","unstructured":"S. Cen , \nC. Cheng , \nY. Chen , \nY. Wei , and \nY. Chi  , Fast Global Convergence of Natural Policy Gradient Methods with Entropy Regularization, https:\/\/arxiv.org\/abs\/2007.06558, 2020."},{"key":"ref7","doi-asserted-by":"publisher","DOI":"10.1023\/A:1005919601192"},{"key":"ref8","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1974-0343581-1"},{"key":"ref9","unstructured":"M. Geist , \nB. Scherrer , and \nO. Pietquin  , A theory of regularized Markov decision processes, in International Conference on Machine Learning, PMLR, 2019."},{"key":"ref10","unstructured":"S. Gunasekar , \nB. Woodworth , and \nN. Srebro  , Mirrorless mirror descent: A natural derivation of mirror descent, in International Conference on Artificial Intelligence and Statistics, PMLR, 2021, pp. 2305\u20132313."},{"key":"ref11","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-56468-0"},{"key":"ref12","first-page":"1531","volume-title":"Advances in Neural Information Processing Systems","author":"Kakade S. M.","year":"2001"},{"key":"ref13","volume-title":"Advances in Neural Information Processing Systems","author":"Konda V. R.","year":"2000"},{"key":"ref14","unstructured":"G. Lan  , Policy Mirror Descent for Reinforcement Learning: Linear Convergence, New Sampling Complexity, and Generalized Problem Classes, https:\/\/arxiv.org\/abs\/2102.00135, 2021."},{"key":"ref15","unstructured":"G. Li , \nY. Wei , \nY. Chi , \nY. Gu , and \nY. Chen  , Softmax Policy Gradient Methods Can Take Exponential Time to Converge, https:\/\/arxiv.org\/abs\/2102.11270, 2021."},{"key":"ref16","first-page":"1","volume":"21","author":"Martens J.","year":"2020","journal-title":"J. Mach. Learn. Res."},{"key":"ref17","unstructured":"J. Mei , \nC. Xiao , \nC. Szepesvari , and \nD. Schuurmans  , On the global convergence rates of softmax policy gradient methods, in International Conference on Machine Learning, PMLR, 2020, pp. 6820\u20136829."},{"key":"ref18","unstructured":"A. Mensch  and \nM. Blondel  , Differentiable dynamic programming for structured prediction and attention, in International Conference on Machine Learning, 2018, pp. 3459\u20133468."},{"key":"ref19","unstructured":"V. Mnih , \nA. P. Badia , \nM. Mirza , \nA. Graves , \nT. Lillicrap , \nT. Harley , \nD. Silver , and \nK. Kavukcuoglu  , Asynchronous methods for deep reinforcement learning, in International Conference on Machine Learning, PMLR, 2016, pp. 1928\u20131937."},{"key":"ref20","volume-title":"Problem Complexity and Method Efficiency in Optimization","author":"Nemirovskij A. S.","year":"1983"},{"key":"ref21","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-007-0149-x"},{"key":"ref22","author":"Neu G.","year":"2017","journal-title":"A Unified View of Entropy-Regularized Markov Decision Processes"},{"key":"ref23","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2015.2388583"},{"key":"ref24","unstructured":"A. R\u00e9nyi  , On measures of entropy and information, in Proceedings of the Fourth Berkeley Symposium on Mathematical Statistics and Probability, Volume 1: Contributions to the Theory of Statistics, University of California Press, 1961, pp. 547\u2013561."},{"key":"ref25","doi-asserted-by":"publisher","DOI":"10.1007\/s10957-020-01805-8"},{"key":"ref26","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-021-01622-5"},{"key":"ref27","doi-asserted-by":"crossref","unstructured":"Y. Saad  , Iterative Methods for Sparse Linear Systems, SIAM, 2003, https:\/\/doi.org\/10.1137\/1.9780898718003.","DOI":"10.1137\/1.9780898718003"},{"key":"ref28","unstructured":"J. Schulman , \nS. Levine , \nP. Abbeel , \nM. Jordan , and \nP. Moritz  , Trust region policy optimization, in International Conference on Machine Learning, PMLR, 2015, pp. 1889\u20131897."},{"key":"ref29","unstructured":"J. Schulman , \nP. Moritz , \nS. Levine , \nM. Jordan , and \nP. Abbeel  , High-Dimensional Continuous Control Using Generalized Advantage Estimation, https:\/\/arxiv.org\/abs\/1506.02438, 2015."},{"key":"ref30","unstructured":"J. Schulman , \nF. Wolski , \nP. Dhariwal , \nA. Radford , and \nO. Klimov  , Proximal Policy Optimization Algorithms, https:\/\/arxiv.org\/abs\/1707.06347, 2017."},{"key":"ref31","doi-asserted-by":"crossref","unstructured":"L. Shani , \nY. Efroni , and \nS. Mannor  , Adaptive trust region policy optimization: Global convergence and faster rates for regularized mdps, in Proceedings of the AAAI Conference on Artificial Intelligence, 2020, pp. 5668\u20135675.","DOI":"10.1609\/aaai.v34i04.6021"},{"key":"ref32","unstructured":"D. Silver , \nG. Lever , \nN. Heess , \nT. Degris , \nD. Wierstra , and \nM. Riedmiller  , Deterministic policy gradient algorithms, in International Conference on Machine Learning, PMLR, 2014, pp. I-387\u2013I-395."},{"key":"ref33","volume-title":"Reinforcement Learning: An Introduction","author":"Sutton R. S.","year":"2018"},{"key":"ref34","first-page":"1057","volume-title":"Advances in Neural Information Processing Systems","author":"Sutton R. S.","year":"2000"},{"key":"ref35","unstructured":"M. Tomar , \nL. Shani , \nY. Efroni , and \nM. Ghavamzadeh  , Mirror Descent Policy Optimization, https:\/\/arxiv.org\/abs\/2005.09814, 2020."},{"key":"ref36","doi-asserted-by":"publisher","DOI":"10.1137\/0913035"},{"key":"ref37","unstructured":"L. Wang  and \nM. Yan  , Hessian Informed Mirror Descent, https:\/\/arxiv.org\/abs\/2106.13477, 2021."},{"key":"ref38","doi-asserted-by":"publisher","DOI":"10.1007\/BF00992696"},{"key":"ref39","doi-asserted-by":"publisher","DOI":"10.1007\/s10915-020-01303-z"},{"key":"ref40","unstructured":"W. Zhan , \nS. Cen , \nB. Huang , \nY. Chen , \nJ. D. Lee , and \nY. Chi  , Policy Mirror Descent for Regularized Reinforcement Learning: A Generalized Framework with Linear Convergence, https:\/\/arxiv.org\/abs\/2105.11066, 2021."}],"container-title":["SIAM Journal on Scientific Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/22M1492088","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T15:46:39Z","timestamp":1787327199000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/22M1492088"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,9,26]]},"references-count":40,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2023,10,31]]}},"alternative-id":["10.1137\/22M1492088"],"URL":"https:\/\/doi.org\/10.1137\/22m1492088","relation":{},"ISSN":["1064-8275","1095-7197"],"issn-type":[{"value":"1064-8275","type":"print"},{"value":"1095-7197","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,9,26]]}}}