{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:35:41Z","timestamp":1787340941674,"version":"build-2736575974"},"reference-count":43,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Optim."],"published-print":{"date-parts":[[2024,3,31]]},"abstract":"<jats:p>Abstract.<\/jats:p>\n                  <jats:p>Entropy regularized Markov decision processes have been widely used in reinforcement learning. This paper is concerned with the primal-dual formulation of the entropy regularized problems. Standard first-order methods suffer from slow convergence due to the lack of strict convexity and concavity. To address this issue, we first introduce a new quadratically convexified primal-dual formulation. The natural gradient ascent descent of the new formulation enjoys global convergence guarantee and exponential convergence rate. We also propose a new interpolating metric that further accelerates the convergence significantly. Numerical results are provided to demonstrate the performance of the proposed methods under multiple settings.<\/jats:p>","DOI":"10.1137\/21m1468851","type":"journal-article","created":{"date-parts":[[2024,2,20]],"date-time":"2024-02-20T13:45:00Z","timestamp":1708436700000},"page":"764-789","source":"Crossref","is-referenced-by-count":0,"title":["Accelerating Primal-Dual Methods for Regularized Markov Decision Processes"],"prefix":"10.1137","volume":"34","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":"Hsiang-Fu","family":"Yu","sequence":"additional","affiliation":[{"name":"Amazon Search, Palo Alto, CA 94301 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 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Inderjit S.","family":"Dhillon","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Texas at Austin, Austin, TX 78712 USA, and Google, Mountain View, CA 94043 USA. This work was done while this author was at Amazon Search."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2024,2,20]]},"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 Thirty-Third Conference on Learning Theory, PMLR 125, 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 36th International Conference on Machine Learning, PMLR 97, 2019, pp. 151\u2013160."},{"key":"ref3","unstructured":"K. Asadi  and \nM. L. Littman  , An alternative softmax operator for reinforcement learning, in 34th International Conference on Machine Learning, PMLR 70, 2017, pp. 243\u2013252."},{"key":"ref4","volume-title":"Applied Dynamic Programming","author":"Bellman R. E.","year":"2015"},{"key":"ref5","unstructured":"F. Berkenkamp , \nM. Turchetta , \nA. P. Schoellig , and \nA. Krause  , Safe Model-based Reinforcement Learning with Stability Guarantees, preprint, https:\/\/arxiv.org\/abs\/1705.08551, 2017."},{"key":"ref6","unstructured":"G. Brockman , \nV. Cheung , \nL. Pettersson , \nJ. Schneider , \nJ. Schulman , \nJ. Tang , and \nW. Zaremba  , OpenAI Gym, preprint, arXiv:1606.01540, 2016."},{"key":"ref7","unstructured":"S. Cen , \nC. Cheng , \nY. Chen , \nY. Wei , and \nY. Chi  , Fast Global Convergence of Natural Policy Gradient Methods with Entropy Regularization, preprint, https:\/\/arxiv.org\/abs\/2007.06558, 2020."},{"key":"ref8","unstructured":"W. S. Cho  and \nM. Wang  , Deep Primal-Dual Reinforcement Learning: Accelerating Actor-Critic Using Bellman Duality, preprint, https:\/\/arxiv.org\/abs\/1712.02467, 2017."},{"key":"ref9","unstructured":"Y. Chow , \nO. Nachum , \nE. Duenez-Guzman , and \nM. Ghavamzadeh  , A Lyapunov-based Approach to Safe Reinforcement Learning, preprint, https:\/\/arxiv.org\/abs\/1805.07708, 2018."},{"key":"ref10","unstructured":"B. Dai , \nA. Shaw , \nL. Li , \nL. Xiao , \nN. He , \nZ. Liu , \nJ. Chen , and \nL. Song  , SBEED: Convergent reinforcement learning with nonlinear function approximation, in 35th International Conference on Machine Learning, PMLR 80, 2018, pp. 1125\u20131134."},{"key":"ref11","first-page":"8378","volume-title":"Advances in Neural Information Processing Systems 33","author":"Ding D.","year":"2020"},{"key":"ref12","unstructured":"M. Geist , \nB. Scherrer , and \nO. Pietquin  , A theory of regularized Markov decision processes, in 36th International Conference on Machine Learning, PMLR 97, 2019, pp. 2160\u20132169."},{"key":"ref13","unstructured":"H. Gong  , Primal-Dual Method for Reinforcement Learning and Markov Decision Processes, Ph.D. thesis, Princeton University, 2021."},{"key":"ref14","doi-asserted-by":"publisher","DOI":"10.2307\/j.ctvcm4hws"},{"key":"ref15","first-page":"1531","volume-title":"Advances in Neural Information Processing Systems 14","author":"Kakade S. M.","year":"2001"},{"key":"ref16","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.1959.1104895"},{"key":"ref17","doi-asserted-by":"publisher","DOI":"10.1115\/1.3662604"},{"key":"ref18","doi-asserted-by":"crossref","unstructured":"S. Khodadadian , \nP. R. Jhunjhunwala , \nS. M. Varma , and \nS. T. Maguluri  , On the linear convergence of natural policy gradient algorithm, in 2021 60th IEEE Conference on Decision and Control (CDC), IEEE, 2021, pp. 3794\u20133799.","DOI":"10.1109\/CDC45484.2021.9682908"},{"key":"ref19","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-022-01816-5"},{"key":"ref20","unstructured":"D. Lee  and \nN. He  , Stochastic Primal-Dual Q-Learning, preprint, https:\/\/arxiv.org\/abs\/1810.08298, 2018."},{"key":"ref21","unstructured":"G. Li , \nY. Wei , \nY. Chi , \nY. Gu , and \nY. Chen  , Softmax Policy Gradient Methods Can Take Exponential Time to Converge, preprint, https:\/\/arxiv.org\/abs\/2102.11270v2, 2021."},{"key":"ref22","doi-asserted-by":"publisher","DOI":"10.1137\/22M1492088"},{"key":"ref23","doi-asserted-by":"publisher","DOI":"10.1080\/00207179208934253"},{"key":"ref24","unstructured":"J. Mei , \nC. Xiao , \nC. Szepesvari , and \nD. Schuurmans  , On the global convergence rates of softmax policy gradient methods, in 37th International Conference on Machine Learning, PMLR 119, 2020, pp. 6820\u20136829."},{"key":"ref25","volume-title":"Markov Chains and Stochastic Stability","author":"Meyn S. P.","year":"2012"},{"key":"ref26","unstructured":"O. Nachum , \nM. Norouzi , \nK. Xu , and \nD. Schuurmans  , Trust-PCL: An Off-Policy Trust Region Method for Continuous Control, preprint, https:\/\/arxiv.org\/abs\/1707.01891, 2017."},{"key":"ref27","unstructured":"G. Neu , \nA. Jonsson , and \nV. G\u00f3mez  , A Unified View of Entropy-Regularized Markov Decision Processes, preprint, https:\/\/arxiv.org\/abs\/1705.07798, 2017."},{"key":"ref28","first-page":"803","volume":"3","author":"Perkins T. J.","year":"2002","journal-title":"J. Mach. Learn. Res."},{"key":"ref29","volume-title":"Markov Decision Processes: Discrete Stochastic Dynamic Programming","author":"Puterman M. L.","year":"2014"},{"key":"ref30","doi-asserted-by":"crossref","unstructured":"K. Rawlik , \nM. Toussaint , and \nS. Vijayakumar  , On stochastic optimal control and reinforcement learning by approximate inference (extended abstract), in Twenty-Third International Joint Conference on Artificial Intelligence, AAAI Press, 2013, pp. 3052\u20133056.","DOI":"10.7551\/mitpress\/9816.003.0050"},{"key":"ref31","unstructured":"J. Schulman , \nS. Levine , \nP. Abbeel , \nM. Jordan , and \nP. Moritz  , Trust region policy optimization, in 32nd International Conference on Machine Learning, PMLR 37, 2015, pp. 1889\u20131897."},{"key":"ref32","unstructured":"J. Schulman , \nP. Moritz , \nS. Levine , \nM. Jordan , and \nP. Abbeel  , High-Dimensional Continuous Control Using Generalized Advantage Estimation, preprint, https:\/\/arxiv.org\/abs\/1506.02438, 2015."},{"key":"ref33","unstructured":"J. Schulman , \nF. Wolski , \nP. Dhariwal , \nA. Radford , and \nO. Klimov  , Proximal Policy Optimization Algorithms, preprint, https:\/\/arxiv.org\/abs\/1707.06347, 2017."},{"key":"ref34","first-page":"413","volume-title":"Conference on Learning for Dynamics and Control","author":"Serrano J. B.","year":"2020"},{"key":"ref35","volume-title":"Reinforcement Learning: An Introduction","author":"Sutton R. S.","year":"2018"},{"key":"ref36","series-title":"Advances in Neural Information Processing Systems 12","first-page":"1057","author":"Sutton R. S.","year":"2000"},{"key":"ref37","unstructured":"M. Wang  , Primal-Dual \\(\\pi\\) Learning: Sample Complexity and Sublinear Run Time for Ergodic Markov Decision Problems, preprint, https:\/\/arxiv.org\/abs\/1710.06100, 2017."},{"key":"ref38","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2019.1000"},{"key":"ref39","doi-asserted-by":"crossref","unstructured":"M. Wang  and \nY. Chen  , An online primal-dual method for discounted Markov decision processes, in IEEE 55th Conference on Decision and Control, IEEE, 2016, pp. 4516\u20134521.","DOI":"10.1109\/CDC.2016.7798956"},{"key":"ref40","doi-asserted-by":"publisher","DOI":"10.1007\/BF00992696"},{"key":"ref41","doi-asserted-by":"publisher","DOI":"10.4310\/CMS.2022.v20.n3.a5"},{"key":"ref42","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, preprint, https:\/\/arxiv.org\/abs\/2105.11066, 2021."},{"key":"ref43","doi-asserted-by":"publisher","DOI":"10.1109\/JSAIT.2021.3081108"}],"container-title":["SIAM Journal on Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/21M1468851","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:57:17Z","timestamp":1787338637000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/21M1468851"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,2,20]]},"references-count":43,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,3,31]]}},"alternative-id":["10.1137\/21M1468851"],"URL":"https:\/\/doi.org\/10.1137\/21m1468851","relation":{},"ISSN":["1052-6234","1095-7189"],"issn-type":[{"value":"1052-6234","type":"print"},{"value":"1095-7189","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,2,20]]}}}