{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,5]],"date-time":"2026-03-05T03:03:01Z","timestamp":1772679781867,"version":"3.50.1"},"reference-count":37,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2013,2,1]],"date-time":"2013-02-01T00:00:00Z","timestamp":1359676800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Center for Algorithmic Game Theory"},{"name":"Sino-Danish Center for the Theory of Interactive Computation"},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["1306\/08"],"award-info":[{"award-number":["1306\/08"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002808","name":"Carlsbergfondet","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100002808","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001732","name":"Danish National Research Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100001732","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Center for Research in the Foundations of Electronic Markets"},{"DOI":"10.13039\/100006785","name":"Google","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100006785","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Danish Strategic Research Council"},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61061130540"],"award-info":[{"award-number":["61061130540"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2013,2]]},"abstract":"<jats:p>\n            Ye [2011] showed recently that the simplex method with Dantzig\u2019s pivoting rule, as well as Howard\u2019s\n            <jats:italic>policy iteration<\/jats:italic>\n            algorithm, solve discounted Markov decision processes (MDPs), with a constant discount factor, in strongly polynomial time. More precisely, Ye showed that both algorithms terminate after at most\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>mn<\/jats:italic>\n            1\u2212\n            <jats:italic>\u03b3<\/jats:italic>\n            log\n            <jats:italic>n<\/jats:italic>\n            1\u2212\n            <jats:italic>\u03b3<\/jats:italic>\n            ) iterations, where\n            <jats:italic>n<\/jats:italic>\n            is the number of states,\n            <jats:italic>m<\/jats:italic>\n            is the total number of actions in the MDP, and 0 &lt;\n            <jats:italic>\u03b3<\/jats:italic>\n            &lt; 1 is the discount factor. We improve Ye\u2019s analysis in two respects. First, we improve the bound given by Ye and show that Howard\u2019s policy iteration algorithm actually terminates after at most\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>m<\/jats:italic>\n            1\u2212\n            <jats:italic>\u03b3<\/jats:italic>\n            log\n            <jats:italic>n<\/jats:italic>\n            1\u2212\n            <jats:italic>\u03b3<\/jats:italic>\n            ) iterations. Second, and more importantly, we show that the same bound applies to the number of iterations performed by the\n            <jats:italic>strategy iteration<\/jats:italic>\n            (or\n            <jats:italic>strategy improvement<\/jats:italic>\n            ) algorithm, a generalization of Howard\u2019s policy iteration algorithm used for solving 2-player turn-based\n            <jats:italic>stochastic games<\/jats:italic>\n            with discounted zero-sum rewards. This provides the first strongly polynomial algorithm for solving these games, solving a long standing open problem. Combined with other recent results, this provides a complete characterization of the complexity the standard strategy iteration algorithm for 2-player turn-based stochastic games; it is strongly polynomial for a fixed discount factor, and exponential otherwise.\n          <\/jats:p>","DOI":"10.1145\/2432622.2432623","type":"journal-article","created":{"date-parts":[[2013,3,5]],"date-time":"2013-03-05T20:28:36Z","timestamp":1362515316000},"page":"1-16","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":36,"title":["Strategy Iteration Is Strongly Polynomial for 2-Player Turn-Based Stochastic Games with a Constant Discount Factor"],"prefix":"10.1145","volume":"60","author":[{"given":"Thomas Dueholm","family":"Hansen","sequence":"first","affiliation":[{"name":"Aarhus University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Peter Bro","family":"Miltersen","sequence":"additional","affiliation":[{"name":"Aarhus University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Uri","family":"Zwick","sequence":"additional","affiliation":[{"name":"Tel Aviv University"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2013,2]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-10631-6_13"},{"key":"e_1_2_1_2_1","volume-title":"Dynamic Programming","author":"Bellman R.","unstructured":"Bellman , R. 1957. Dynamic Programming . Princeton University Press . Bellman, R. 1957. Dynamic Programming. Princeton University Press."},{"key":"e_1_2_1_3_1","volume-title":"Dynamic Programming and Optimal Control","author":"Bertsekas D.","unstructured":"Bertsekas , D. 2001. Dynamic Programming and Optimal Control 2 nd Ed. Athena Scientific . Bertsekas, D. 2001. Dynamic Programming and Optimal Control 2nd Ed. Athena Scientific.","edition":"2"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.07.041"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2006.04.029"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(92)90048-K"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1090\/dimacs\/013\/04"},{"key":"e_1_2_1_8_1","first-page":"98","article-title":"A probabilistic production and inventory problem. Manage","volume":"10","author":"d\u2019Epenoux F.","year":"1963","unstructured":"d\u2019Epenoux , F. 1963 . A probabilistic production and inventory problem. Manage . Sci. 10 , 1, 98 -- 108 . d\u2019Epenoux, F. 1963. A probabilistic production and inventory problem. Manage. Sci. 10, 1, 98--108.","journal-title":"Sci."},{"key":"e_1_2_1_9_1","volume-title":"Finite State Markov Decision Processes","author":"Derman C.","unstructured":"Derman , C. 1972. Finite State Markov Decision Processes . Academic Press . Derman, C. 1972. Finite State Markov Decision Processes. Academic Press."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01768705"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1991.185392"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/1880999.1881059"},{"key":"e_1_2_1_13_1","doi-asserted-by":"crossref","unstructured":"Filar J. and Vrieze K. 1996. Competitive Markov Decision Processes. Springer-Verlag New York NY.   Filar J. and Vrieze K. 1996. Competitive Markov Decision Processes . Springer-Verlag New York NY.","DOI":"10.1007\/978-1-4612-4054-9"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.2168\/LMCS-7(3:23)2011"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/11537311_19"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/0041-5553(88)90012-2"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-007-0175-3"},{"key":"e_1_2_1_18_1","first-page":"359","article-title":"On nonterminating stochastic games. Manage","volume":"12","author":"Hoffman A.","year":"1966","unstructured":"Hoffman , A. and Karp , R. 1966 . On nonterminating stochastic games. Manage . Sci. 12 , 359 -- 370 . Hoffman, A. and Karp, R. 1966. On nonterminating stochastic games. Manage. Sci. 12, 359--370.","journal-title":"Sci."},{"key":"e_1_2_1_19_1","volume-title":"Dynamic Programming and Markov Processes","author":"Howard R.","unstructured":"Howard , R. 1960. Dynamic Programming and Markov Processes . MIT Press . Howard, R. 1960. Dynamic Programming and Markov Processes. MIT Press."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-69407-6_32"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/070686652"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/129712.129759"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/3226650.3226821"},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of the 11th UAI. 394--402","author":"Littman M.","unstructured":"Littman , M. , Dean , T. , and Kaelbling , L . 1995. On the complexity of solving markov decision problems . In Proceedings of the 11th UAI. 394--402 . Littman, M., Dean, T., and Kaelbling, L. 1995. On the complexity of solving markov decision problems. In Proceedings of the 11th UAI. 394--402."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1995.1035"},{"key":"e_1_2_1_27_1","volume-title":"Proceedings of the 15th UAI. 401--408","author":"Mansour Y.","unstructured":"Mansour , Y. and Singh , S . 1999. On the complexity of policy iteration . In Proceedings of the 15th UAI. 401--408 . Mansour, Y. and Singh, S. 1999. On the complexity of policy iteration. In Proceedings of the 15th UAI. 401--408."},{"key":"e_1_2_1_28_1","first-page":"4","article-title":"A subexponential bound for linear programming","volume":"16","author":"Matou\u0161ek J.","year":"1996","unstructured":"Matou\u0161ek , J. , Sharir , M. , and Welzl , E. 1996 . A subexponential bound for linear programming . Algorithmica 16 , 4 -- 5 , 498--516. Matou\u0161ek, J., Sharir, M., and Welzl, E. 1996. A subexponential bound for linear programming. Algorithmica 16, 4--5, 498--516.","journal-title":"Algorithmica"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01720771"},{"key":"e_1_2_1_30_1","volume-title":"Eds","author":"Neyman A.","year":"2003","unstructured":"Neyman , A. and Sorin , S. , Eds . 2003 . Stochastic Games and Applications. NATO Science Series C: Mathematical and Physical Sciences Series, vol. 570 . Springer . Neyman, A. and Sorin, S., Eds. 2003. Stochastic Games and Applications. NATO Science Series C: Mathematical and Physical Sciences Series, vol. 570. Springer."},{"key":"e_1_2_1_31_1","volume-title":"Markov Decision Processes","author":"Puterman M.","unstructured":"Puterman , M. 1994. Markov Decision Processes . Wiley . Puterman, M. 1994. Markov Decision Processes. Wiley."},{"key":"e_1_2_1_32_1","doi-asserted-by":"crossref","unstructured":"Rao S. Chandrasekaran R. and Nair K. 1973. Algorithms for discounted games. J. Optimizat. Theory Appl. 627--637.  Rao S. Chandrasekaran R. and Nair K. 1973. Algorithms for discounted games. J. Optimizat. Theory Appl. 627--637.","DOI":"10.1007\/BF00935562"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01918764"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.39.10.1953"},{"key":"e_1_2_1_35_1","volume-title":"Proceedings of the 12th CAV. Springer, 202--215","author":"V\u00f6ge J.","unstructured":"V\u00f6ge , J. and Jurdzi\u0144ski , M . 2000. A discrete strategy improvement algorithm for solving parity games (Extended abstract) . In Proceedings of the 12th CAV. Springer, 202--215 . V\u00f6ge, J. and Jurdzi\u0144ski, M. 2000. A discrete strategy improvement algorithm for solving parity games (Extended abstract). In Proceedings of the 12th CAV. Springer, 202--215."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1050.0149"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1110.0516"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(95)00188-3"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2432622.2432623","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2432622.2432623","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T08:18:20Z","timestamp":1750234700000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2432622.2432623"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,2]]},"references-count":37,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2013,2]]}},"alternative-id":["10.1145\/2432622.2432623"],"URL":"https:\/\/doi.org\/10.1145\/2432622.2432623","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,2]]},"assertion":[{"value":"2012-01-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-02-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}