{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,21]],"date-time":"2026-07-21T14:36:32Z","timestamp":1784644592513,"version":"3.55.0"},"reference-count":61,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2023,1,23]],"date-time":"2023-01-23T00:00:00Z","timestamp":1674432000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,1,23]],"date-time":"2023-01-23T00:00:00Z","timestamp":1674432000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100000001","name":"national science foundation","doi-asserted-by":"publisher","award":["2106739"],"award-info":[{"award-number":["2106739"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"national science foundation","doi-asserted-by":"publisher","award":["1907661"],"award-info":[{"award-number":["1907661"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"national science foundation","doi-asserted-by":"publisher","award":["2106778"],"award-info":[{"award-number":["2106778"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"national science foundation","doi-asserted-by":"publisher","award":["2106778"],"award-info":[{"award-number":["2106778"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000183","name":"army research office","doi-asserted-by":"publisher","award":["W911NF-20-1-0097"],"award-info":[{"award-number":["W911NF-20-1-0097"]}],"id":[{"id":"10.13039\/100000183","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000183","name":"army research office","doi-asserted-by":"publisher","award":["W911NF-18-1-0303"],"award-info":[{"award-number":["W911NF-18-1-0303"]}],"id":[{"id":"10.13039\/100000183","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000181","name":"air force office of scientific research","doi-asserted-by":"publisher","award":["FA9550-19-1-0030"],"award-info":[{"award-number":["FA9550-19-1-0030"]}],"id":[{"id":"10.13039\/100000181","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000006","name":"office of naval research","doi-asserted-by":"publisher","award":["N00014-19-1-2120"],"award-info":[{"award-number":["N00014-19-1-2120"]}],"id":[{"id":"10.13039\/100000006","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000006","name":"office of naval research","doi-asserted-by":"publisher","award":["N00014-18-1-2142"],"award-info":[{"award-number":["N00014-18-1-2142"]}],"id":[{"id":"10.13039\/100000006","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000006","name":"office of naval research","doi-asserted-by":"publisher","award":["N00014-19-1-2404"],"award-info":[{"award-number":["N00014-19-1-2404"]}],"id":[{"id":"10.13039\/100000006","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2023,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The softmax policy gradient (PG) method, which performs gradient ascent under softmax policy parameterization, is arguably one of the de facto implementations of policy optimization in modern reinforcement learning. For<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\gamma $$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>\u03b3<\/mml:mi><\/mml:math><\/jats:alternatives><\/jats:inline-formula>-discounted infinite-horizon tabular Markov decision processes (MDPs), remarkable progress has recently been achieved towards establishing global convergence of softmax PG methods in finding a near-optimal policy. However, prior results fall short of delineating clear dependencies of convergence rates on salient parameters such as the cardinality of the state space<jats:inline-formula><jats:alternatives><jats:tex-math>$${\\mathcal {S}}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>S<\/mml:mi><\/mml:math><\/jats:alternatives><\/jats:inline-formula>and the effective horizon<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\frac{1}{1-\\gamma }$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mfrac><mml:mn>1<\/mml:mn><mml:mrow><mml:mn>1<\/mml:mn><mml:mo>-<\/mml:mo><mml:mi>\u03b3<\/mml:mi><\/mml:mrow><\/mml:mfrac><\/mml:math><\/jats:alternatives><\/jats:inline-formula>, both of which could be excessively large. In this paper, we deliver a pessimistic message regarding the iteration complexity of softmax PG methods, despite assuming access to exact gradient computation. Specifically, we demonstrate that the softmax PG method with stepsize<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\eta $$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>\u03b7<\/mml:mi><\/mml:math><\/jats:alternatives><\/jats:inline-formula>can take<jats:disp-formula><jats:alternatives><jats:tex-math>$$\\begin{aligned} \\frac{1}{\\eta } |{\\mathcal {S}}|^{2^{\\Omega \\big (\\frac{1}{1-\\gamma }\\big )}} ~\\text {iterations} \\end{aligned}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mtable><mml:mtr><mml:mtd><mml:mrow><mml:mfrac><mml:mn>1<\/mml:mn><mml:mi>\u03b7<\/mml:mi><\/mml:mfrac><mml:msup><mml:mrow><mml:mo>|<\/mml:mo><mml:mi>S<\/mml:mi><mml:mo>|<\/mml:mo><\/mml:mrow><mml:msup><mml:mn>2<\/mml:mn><mml:mrow><mml:mi>\u03a9<\/mml:mi><mml:mrow><mml:mo>(<\/mml:mo><\/mml:mrow><mml:mfrac><mml:mn>1<\/mml:mn><mml:mrow><mml:mn>1<\/mml:mn><mml:mo>-<\/mml:mo><mml:mi>\u03b3<\/mml:mi><\/mml:mrow><\/mml:mfrac><mml:mrow><mml:mo>)<\/mml:mo><\/mml:mrow><\/mml:mrow><\/mml:msup><\/mml:msup><mml:mspace\/><mml:mtext>iterations<\/mml:mtext><\/mml:mrow><\/mml:mtd><\/mml:mtr><\/mml:mtable><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:disp-formula>to converge, even in the presence of a benign policy initialization and an initial state distribution amenable to exploration (so that the distribution mismatch coefficient is not exceedingly large). This is accomplished by characterizing the algorithmic dynamics over a carefully-constructed MDP containing only three actions. Our exponential lower bound hints at the necessity of carefully adjusting update rules or enforcing proper regularization in accelerating PG methods.<\/jats:p>","DOI":"10.1007\/s10107-022-01920-6","type":"journal-article","created":{"date-parts":[[2023,1,23]],"date-time":"2023-01-23T18:01:15Z","timestamp":1674496875000},"page":"707-802","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["Softmax policy gradient methods can take exponential time to converge"],"prefix":"10.1007","volume":"201","author":[{"given":"Gen","family":"Li","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yuting","family":"Wei","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yuejie","family":"Chi","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9256-5815","authenticated-orcid":false,"given":"Yuxin","family":"Chen","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2023,1,23]]},"reference":[{"issue":"98","key":"1920_CR1","first-page":"1","volume":"22","author":"A Agarwal","year":"2021","unstructured":"Agarwal, A., Kakade, S.M., Lee, J.D., Mahajan, G.: On the theory of policy gradient methods: optimality, approximation, and distribution shift. J. Mach. Learn. Res. 22(98), 1\u201376 (2021)","journal-title":"J. Mach. Learn. Res."},{"key":"1920_CR2","unstructured":"Agazzi, A., Lu, J.: Global optimality of softmax policy gradient with single hidden layer neural networks in the mean-field regime. In: International Conference on Learning Representations (ICLR) (2021)"},{"key":"1920_CR3","unstructured":"Alacaoglu, A., Viano, L., He, N., Cevher, V.: A natural actor-critic framework for zero-sum Markov games. In: International Conference on Machine Learning, pp. 307\u2013366. PMLR (2022)"},{"key":"1920_CR4","unstructured":"Asadi, K., Littman, M.L.: An alternative softmax operator for reinforcement learning. In: International Conference on Machine Learning, pp. 243\u2013252 (2017)"},{"issue":"3","key":"1920_CR5","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1007\/s10994-013-5368-1","volume":"91","author":"MG Azar","year":"2013","unstructured":"Azar, M.G., Munos, R., Kappen, H.J.: Minimax PAC bounds on the sample complexity of reinforcement learning with a generative model. Mach. Learn. 91(3), 325\u2013349 (2013)","journal-title":"Mach. Learn."},{"key":"1920_CR6","doi-asserted-by":"crossref","DOI":"10.1137\/1.9781611974997","volume-title":"First-Order Methods in Optimization","author":"A Beck","year":"2017","unstructured":"Beck, A.: First-Order Methods in Optimization. SIAM, Philadelphia, PA (2017)"},{"key":"1920_CR7","unstructured":"Bhandari, J.: Optimization foundations of reinforcement learning. Ph.D. thesis, Columbia University (2020)"},{"key":"1920_CR8","unstructured":"Bhandari, J., Russo, D.: Global optimality guarantees for policy gradient methods. arXiv preprint arXiv:1906.01786 (2019)"},{"key":"1920_CR9","unstructured":"Bhandari, J., Russo, D.: On the linear convergence of policy gradient methods for finite MDPs. In: International Conference on Artificial Intelligence and Statistics, pp. 2386\u20132394. PMLR (2021)"},{"key":"1920_CR10","unstructured":"Cai, Q., Yang, Z., Jin, C., Wang, Z.: Provably efficient exploration in policy optimization. In: International Conference on Machine Learning, pp. 1283\u20131294 (2020)"},{"issue":"4","key":"1920_CR11","doi-asserted-by":"crossref","first-page":"2563","DOI":"10.1287\/opre.2021.2151","volume":"70","author":"S Cen","year":"2022","unstructured":"Cen, S., Cheng, C., Chen, Y., Wei, Y., Chi, Y.: Fast global convergence of natural policy gradient methods with entropy regularization. Oper. Res. 70(4), 2563\u20132578 (2022)","journal-title":"Oper. Res."},{"key":"1920_CR12","unstructured":"Cen, S., Chi, Y., Du, S.S., Xiao, L.: Faster last-iterate convergence of policy optimization in zero-sum Markov games. arXiv preprint arXiv:2210.01050 (2022)"},{"key":"1920_CR13","first-page":"27952","volume":"34","author":"S Cen","year":"2021","unstructured":"Cen, S., Wei, Y., Chi, Y.: Fast policy extragradient methods for competitive games with entropy regularization. Adv. Neural Inf. Process. Syst. 34, 27952\u201327964 (2021)","journal-title":"Adv. Neural Inf. Process. Syst."},{"key":"1920_CR14","first-page":"5527","volume":"33","author":"C Daskalakis","year":"2020","unstructured":"Daskalakis, C., Foster, D.J., Golowich, N.: Independent policy gradient methods for competitive reinforcement learning. Adv. Neural Inf. Process. Syst. 33, 5527\u20135540 (2020)","journal-title":"Adv. Neural Inf. Process. Syst."},{"key":"1920_CR15","first-page":"8378","volume":"33","author":"D Ding","year":"2020","unstructured":"Ding, D., Zhang, K., Basar, T., Jovanovic, M.: Natural policy gradient primal\u2013dual method for constrained Markov decision processes. Adv. Neural Inf. Process. Syst. 33, 8378\u20138390 (2020)","journal-title":"Adv. Neural Inf. Process. Syst."},{"key":"1920_CR16","unstructured":"Domingues, O.D., M\u00e9nard, P., Kaufmann, E., Valko, M.: Episodic reinforcement learning in finite MDPs: minimax lower bounds revisited. In: Algorithmic Learning Theory, pp. 578\u2013598 (2021)"},{"key":"1920_CR17","first-page":"1068","volume":"30","author":"S Du","year":"2017","unstructured":"Du, S., Jin, C., Jordan, M., P\u00f3czos, B., Singh, A., Lee, J.: Gradient descent can take exponential time to escape saddle points. Adv. Neural Inf. Process. Syst. 30, 1068\u20131078 (2017)","journal-title":"Adv. Neural Inf. Process. Syst."},{"key":"1920_CR18","unstructured":"Fazel, M., Ge, R., Kakade, S., Mesbahi, M.: Global convergence of policy gradient methods for the linear quadratic regulator. In: International Conference on Machine Learning, pp. 1467\u20131476 (2018)"},{"key":"1920_CR19","doi-asserted-by":"crossref","unstructured":"Jansch-Porto, J.P., Hu, B., Dullerud, G.E.: Convergence guarantees of policy optimization methods for Markovian jump linear systems. In: American Control Conference, pp. 2882\u20132887. IEEE (2020)","DOI":"10.23919\/ACC45564.2020.9147571"},{"key":"1920_CR20","first-page":"1531","volume":"14","author":"SM Kakade","year":"2002","unstructured":"Kakade, S.M.: A natural policy gradient. Adv. Neural Inf. Process. Syst. 14, 1531\u20131538 (2002)","journal-title":"Adv. Neural Inf. Process. Syst."},{"issue":"4","key":"1920_CR21","doi-asserted-by":"crossref","first-page":"1013","DOI":"10.1137\/20M1331524","volume":"3","author":"K Khamaru","year":"2021","unstructured":"Khamaru, K., Pananjady, A., Ruan, F., Wainwright, M.J., Jordan, M.I.: Is temporal difference learning optimal? An instance-dependent analysis. SIAM J. Math. Data Sci. 3(4), 1013\u20131040 (2021)","journal-title":"SIAM J. Math. Data Sci."},{"key":"1920_CR22","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2022.3190032","author":"S Khodadadian","year":"2022","unstructured":"Khodadadian, S., Doan, T.T., Romberg, J., Maguluri, S.T.: Finite sample analysis of two-time-scale natural actor-critic algorithm. IEEE Trans. Automatic Control. (2022). https:\/\/doi.org\/10.1109\/TAC.2022.3190032","journal-title":"IEEE Trans. Automatic Control."},{"key":"1920_CR23","first-page":"1008","volume":"12","author":"VR Konda","year":"2000","unstructured":"Konda, V.R., Tsitsiklis, J.N.: Actor-critic algorithms. Adv. Neural Inf. Process. Syst. 12, 1008\u20131014 (2000)","journal-title":"Adv. Neural Inf. Process. Syst."},{"key":"1920_CR24","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-022-01816-5","author":"G Lan","year":"2022","unstructured":"Lan, G.: Policy mirror descent for reinforcement learning: linear convergence, new sampling complexity, and generalized problem classes. Math. Program. (2022). https:\/\/doi.org\/10.1007\/s10107-022-01816-5","journal-title":"Math. Program."},{"key":"1920_CR25","unstructured":"Lan, G.: Policy optimization over general state and action spaces. arXiv preprint arXiv:2211.16715 (2022)"},{"key":"1920_CR26","unstructured":"Lee, J.D., Simchowitz, M., Jordan, M.I., Recht, B.: Gradient descent only converges to minimizers. In: Conference on learning Theory, pp. 1246\u20131257 (2016)"},{"key":"1920_CR27","unstructured":"Li, G., Cai, C., Chen, Y., Wei, Y., Chi, Y.: Is Q-learning minimax optimal? A tight sample complexity analysis. arXiv preprint arXiv:2102.06548 (2021)"},{"key":"1920_CR28","unstructured":"Li, G., Shi, L., Chen, Y., Chi, Y., Wei, Y.: Settling the sample complexity of model-based offline reinforcement learning. arXiv preprint arXiv:2204.05275 (2022)"},{"key":"1920_CR29","unstructured":"Li, Y., Zhao, T., Lan, G.: First-order policy optimization for robust Markov decision process. arXiv preprint arXiv:2209.10579 (2022)"},{"key":"1920_CR30","first-page":"10565","volume":"32","author":"B Liu","year":"2019","unstructured":"Liu, B., Cai, Q., Yang, Z., Wang, Z.: Neural proximal\/trust region policy optimization attains globally optimal policy. Adv. Neural Inf. Process. Syst. 32, 10565\u201310576 (2019)","journal-title":"Adv. Neural Inf. Process. Syst."},{"key":"1920_CR31","first-page":"7624","volume":"33","author":"Y Liu","year":"2020","unstructured":"Liu, Y., Zhang, K., Basar, T., Yin, W.: An improved analysis of (variance-reduced) policy gradient and natural policy gradient methods. Adv. Neural Inf. Process. Syst. 33, 7624\u20137636 (2020)","journal-title":"Adv. Neural Inf. Process. Syst."},{"key":"1920_CR32","unstructured":"Mei, J., Gao, Y., Dai, B., Szepesvari, C., Schuurmans, D.: Leveraging non-uniformity in first-order non-convex optimization. In: International Conference on Machine Learning, pp. 7555\u20137564 (2021)"},{"key":"1920_CR33","first-page":"21130","volume":"33","author":"J Mei","year":"2020","unstructured":"Mei, J., Xiao, C., Dai, B., Li, L., Szepesv\u00e1ri, C., Schuurmans, D.: Escaping the gravitational pull of softmax. Adv. Neural Inf. Process. Syst. 33, 21130\u201321140 (2020)","journal-title":"Adv. Neural Inf. Process. Syst."},{"key":"1920_CR34","unstructured":"Mei, J., Xiao, C., Szepesvari, C., Schuurmans, D.: On the global convergence rates of softmax policy gradient methods. In: International Conference on Machine Learning, pp. 6820\u20136829 (2020)"},{"issue":"7540","key":"1920_CR35","doi-asserted-by":"crossref","first-page":"529","DOI":"10.1038\/nature14236","volume":"518","author":"V Mnih","year":"2015","unstructured":"Mnih, V., Kavukcuoglu, K., Silver, D., Rusu, A.A., Veness, J., Bellemare, M.G., Graves, A., Riedmiller, M., Fidjeland, A.K., Ostrovski, G., et al.: Human-level control through deep reinforcement learning. Nature 518(7540), 529\u2013533 (2015)","journal-title":"Nature"},{"issue":"1","key":"1920_CR36","doi-asserted-by":"crossref","first-page":"566","DOI":"10.1109\/TIT.2020.3027316","volume":"67","author":"A Pananjady","year":"2020","unstructured":"Pananjady, A., Wainwright, M.J.: Instance-dependent $$\\ell _{\\infty }$$-bounds for policy evaluation in tabular reinforcement learning. IEEE Trans. Inf. Theory 67(1), 566\u2013585 (2020)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"7\u20139","key":"1920_CR37","doi-asserted-by":"crossref","first-page":"1180","DOI":"10.1016\/j.neucom.2007.11.026","volume":"71","author":"J Peters","year":"2008","unstructured":"Peters, J., Schaal, S.: Natural actor-critic. Neurocomputing 71(7\u20139), 1180\u20131190 (2008)","journal-title":"Neurocomputing"},{"key":"1920_CR38","unstructured":"Schulman, J., Levine, S., Abbeel, P., Jordan, M., Moritz, P.: Trust region policy optimization. In: International Conference on Machine Learning, pp. 1889\u20131897 (2015)"},{"key":"1920_CR39","unstructured":"Schulman, J., Wolski, F., Dhariwal, P., Radford, A., Klimov, O.: Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347 (2017)"},{"key":"1920_CR40","doi-asserted-by":"crossref","unstructured":"Shani, L., Efroni, Y., Mannor, S.: Adaptive trust region policy optimization: global convergence and faster rates for regularized MDPs. In: AAAI Conference on Artificial Intelligence, vol. 34, pp. 5668\u20135675 (2020)","DOI":"10.1609\/aaai.v34i04.6021"},{"issue":"7587","key":"1920_CR41","doi-asserted-by":"crossref","first-page":"484","DOI":"10.1038\/nature16961","volume":"529","author":"D Silver","year":"2016","unstructured":"Silver, D., Huang, A., Maddison, C.J., Guez, A., Sifre, L., Van Den Driessche, G., Schrittwieser, J., Antonoglou, I., Panneershelvam, V., Lanctot, M., et al.: Mastering the game of Go with deep neural networks and tree search. Nature 529(7587), 484\u2013489 (2016)","journal-title":"Nature"},{"key":"1920_CR42","unstructured":"Sutton, R.S.: Temporal credit assignment in reinforcement learning. Ph.D. thesis, University of Massachusetts (1984)"},{"key":"1920_CR43","first-page":"1057","volume":"12","author":"RS Sutton","year":"2000","unstructured":"Sutton, R.S., McAllester, D.A., Singh, S.P., Mansour, Y.: Policy gradient methods for reinforcement learning with function approximation. Adv. Neural Inf. Process. Syst. 12, 1057\u20131063 (2000)","journal-title":"Adv. Neural Inf. Process. Syst."},{"key":"1920_CR44","unstructured":"Tu, S., Recht, B.: The gap between model-based and model-free methods on the linear quadratic regulator: an asymptotic viewpoint. In: Conference on Learning Theory, pp. 3036\u20133083 (2019)"},{"key":"1920_CR45","unstructured":"Wang, L., Cai, Q., Yang, Z., Wang, Z.: Neural policy gradient methods: global optimality and rates of convergence. In: International Conference on Learning Representations (2019)"},{"key":"1920_CR46","unstructured":"Wei, C.-Y., Lee, C.-W., Zhang, M., Luo, H.: Last-iterate convergence of decentralized optimistic gradient descent\/ascent in infinite-horizon competitive Markov games. In: Conference on Learning Theory, pp. 4259\u20134299. PMLR (2021)"},{"issue":"3\u20134","key":"1920_CR47","first-page":"229","volume":"8","author":"RJ Williams","year":"1992","unstructured":"Williams, R.J.: Simple statistical gradient-following algorithms for connectionist reinforcement learning. Mach. Learn. 8(3\u20134), 229\u2013256 (1992)","journal-title":"Mach. Learn."},{"key":"1920_CR48","first-page":"17617","volume":"33","author":"YF Wu","year":"2020","unstructured":"Wu, Y.F., Zhang, W., Xu, P., Gu, Q.: A finite-time analysis of two time-scale actor-critic methods. Adv. Neural Inf. Process. Syst. 33, 17617\u201317628 (2020)","journal-title":"Adv. Neural Inf. Process. Syst."},{"key":"1920_CR49","unstructured":"Xie, Q., Yang, Z., Wang, Z., Minca, A.: Provable fictitious play for general mean-field games. arXiv preprint arXiv:2010.04211 (2020)"},{"key":"1920_CR50","unstructured":"Xu, T., Liang, Y., Lan, G.: A primal approach to constrained policy optimization: global optimality and finite-time analysis. arXiv preprint arXiv:2011.05869 (2020)"},{"key":"1920_CR51","unstructured":"Xu, T., Wang, Z., Liang, Y.: Non-asymptotic convergence analysis of two time-scale (natural) actor-critic algorithms. arXiv preprint arXiv:2005.03557 (2020)"},{"key":"1920_CR52","unstructured":"Yan, Y., Li, G., Chen, Y., Fan, J.: Model-based reinforcement learning is minimax-optimal for offline zero-sum Markov games. arXiv preprint arXiv:2206.04044 (2022)"},{"key":"1920_CR53","unstructured":"Yang, W., Li, X., Xie, G., Zhang, Z.: Finding the near optimal policy via adaptive reduced regularization in MDPs. arXiv preprint arXiv:2011.00213 (2020)"},{"key":"1920_CR54","unstructured":"Zhan, W., Cen, S., Huang, B., Chen, Y., Lee, J.D., Chi, Y.: Policy mirror descent for regularized reinforcement learning: a generalized framework with linear convergence. arXiv preprint arXiv:2105.11066 (2021)"},{"key":"1920_CR55","doi-asserted-by":"crossref","unstructured":"Zhang, J., Kim, J., O\u2019Donoghue, B., Boyd, S.: Sample efficient reinforcement learning with REINFORCE. In: AAAI Conference on Artificial Intelligence, vol. 35, pp. 10887\u201310895 (2021)","DOI":"10.1609\/aaai.v35i12.17300"},{"key":"1920_CR56","first-page":"4572","volume":"33","author":"J Zhang","year":"2020","unstructured":"Zhang, J., Koppel, A., Bedi, A.S., Szepesvari, C., Wang, M.: Variational policy gradient method for reinforcement learning with general utilities. Adv. Neural Inf. Process. Syst. 33, 4572\u20134583 (2020)","journal-title":"Adv. Neural Inf. Process. Syst."},{"key":"1920_CR57","first-page":"2228","volume":"34","author":"J Zhang","year":"2021","unstructured":"Zhang, J., Ni, C., Szepesvari, C., Wang, M.: On the convergence and sample efficiency of variance-reduced policy gradient method. Adv. Neural Inf. Process. Syst. 34, 2228\u20132240 (2021)","journal-title":"Adv. Neural Inf. Process. Syst."},{"key":"1920_CR58","doi-asserted-by":"crossref","unstructured":"Zhang, K., Hu, B., Basar, T.: Policy optimization for $$\\cal{H}_2$$ linear control with $$\\cal{H}_{\\infty }$$ robustness guarantee: implicit regularization and global convergence. In: Learning for Dynamics and Control, pp. 179\u2013190 (2020)","DOI":"10.1137\/20M1347942"},{"issue":"6","key":"1920_CR59","doi-asserted-by":"crossref","first-page":"3586","DOI":"10.1137\/19M1288012","volume":"58","author":"K Zhang","year":"2020","unstructured":"Zhang, K., Koppel, A., Zhu, H., Basar, T.: Global convergence of policy gradient methods to (almost) locally optimal policies. SIAM J. Control. Optim. 58(6), 3586\u20133612 (2020)","journal-title":"SIAM J. Control. Optim."},{"key":"1920_CR60","unstructured":"Zhang, X., Chen, Y., Zhu, X., Sun, W.: Robust policy gradient against strong data corruption. In: International Conference on Machine Learning, pp. 12391\u201312401 (2021)"},{"key":"1920_CR61","unstructured":"Zhao, Y., Tian, Y., Lee, J., Du, S.: Provably efficient policy gradient methods for two-player zero-sum Markov games. in: International Conference on Artificial Intelligence and Statistics (2021)"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-022-01920-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-022-01920-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-022-01920-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,12,5]],"date-time":"2023-12-05T07:34:32Z","timestamp":1701761672000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-022-01920-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,1,23]]},"references-count":61,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2023,9]]}},"alternative-id":["1920"],"URL":"https:\/\/doi.org\/10.1007\/s10107-022-01920-6","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,1,23]]},"assertion":[{"value":"12 June 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 December 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 January 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}