{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,27]],"date-time":"2026-03-27T04:51:15Z","timestamp":1774587075497,"version":"3.50.1"},"publisher-location":"Cham","reference-count":39,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319681665","type":"print"},{"value":"9783319681672","type":"electronic"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017]]},"DOI":"10.1007\/978-3-319-68167-2_25","type":"book-chapter","created":{"date-parts":[[2017,9,25]],"date-time":"2017-09-25T23:50:53Z","timestamp":1506383453000},"page":"380-399","source":"Crossref","is-referenced-by-count":11,"title":["Efficient Strategy Iteration for Mean Payoff in Markov Decision Processes"],"prefix":"10.1007","author":[{"given":"Jan","family":"K\u0159et\u00ednsk\u00fd","sequence":"first","affiliation":[]},{"given":"Tobias","family":"Meggendorfer","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,9,27]]},"reference":[{"key":"25_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1007\/978-3-319-46520-3_2","volume-title":"Automated Technology for Verification and Analysis","author":"A Abate","year":"2016","unstructured":"Abate, A., \u010ce\u0161ka, M., Kwiatkowska, M.: Approximate policy iteration for Markov Decision Processes via quantitative adaptive aggregations. In: Artho, C., Legay, A., Peled, D. (eds.) ATVA 2016. LNCS, vol. 9938, pp. 13\u201331. Springer, Cham (2016). doi: 10.1007\/978-3-319-46520-3_2"},{"key":"25_CR2","doi-asserted-by":"crossref","unstructured":"Ashok, P., Chatterjee, K., Daca, P., K\u0159et\u00ednsk\u00fd, J., Meggendorfer, T.: Value iteration for long-run average reward in Markov Decision Processes. In: CAV (2017). To appear","DOI":"10.1007\/978-3-319-63387-9_10"},{"key":"25_CR3","unstructured":"Baier, C., Katoen, J.-P.: Principles of Model Checking (2008)"},{"key":"25_CR4","doi-asserted-by":"crossref","unstructured":"Baier, C., Klein, J., Leuschner, L., Parker, D., Wunderlich, S.: Ensuring the reliability of your model checker: Interval iteration for Markov Decision Processes. In: CAV (2017). To appear","DOI":"10.1007\/978-3-319-63387-9_8"},{"issue":"3","key":"25_CR5","doi-asserted-by":"crossref","first-page":"310","DOI":"10.1007\/s11768-011-1005-3","volume":"9","author":"DP Bertsekas","year":"2011","unstructured":"Bertsekas, D.P.: Approximate policy iteration: a survey and some new methods. J. Control Theor. Appl. 9(3), 310\u2013335 (2011)","journal-title":"J. Control Theor. Appl."},{"issue":"2","key":"25_CR6","first-page":"210","volume":"155","author":"H Bj\u00f6rklund","year":"2007","unstructured":"Bj\u00f6rklund, H., Vorobyov, S.G.: A combinatorial strongly subexponential strategy improvement algorithm for mean payoff games. DAM 155(2), 210\u2013229 (2007)","journal-title":"DAM"},{"key":"25_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"98","DOI":"10.1007\/978-3-319-11936-6_8","volume-title":"Automated Technology for Verification and Analysis","author":"T Br\u00e1zdil","year":"2014","unstructured":"Br\u00e1zdil, T., Chatterjee, K., Chmel\u00edk, M., Forejt, V., K\u0159et\u00ednsk\u00fd, J., Kwiatkowska, M., Parker, D., Ujma, M.: Verification of Markov Decision Processes using learning algorithms. In: Cassez, F., Raskin, J.-F. (eds.) ATVA 2014. LNCS, vol. 8837, pp. 98\u2013114. Springer, Cham (2014). doi: 10.1007\/978-3-319-11936-6_8"},{"key":"25_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1007\/978-3-662-46681-0_12","volume-title":"Tools and Algorithms for the Construction and Analysis of Systems","author":"T Br\u00e1zdil","year":"2015","unstructured":"Br\u00e1zdil, T., Chatterjee, K., Forejt, V., Ku\u010dera, A.: MultiGain: a controller synthesis tool for MDPs with multiple mean-payoff objectives. In: Baier, C., Tinelli, C. (eds.) TACAS 2015. LNCS, vol. 9035, pp. 181\u2013187. Springer, Heidelberg (2015). doi: 10.1007\/978-3-662-46681-0_12"},{"issue":"3","key":"25_CR9","first-page":"585","volume":"23","author":"L Brim","year":"2012","unstructured":"Brim, L., Chaloupka, J.: Using strategy improvement to stay alive. IJCSIS 23(3), 585\u2013608 (2012)","journal-title":"IJCSIS"},{"key":"25_CR10","doi-asserted-by":"crossref","unstructured":"Chatterjee, K., Henzinger, T.: Value iteration. 25 Years of Model Checking, pp. 107\u2013138 (2008)","DOI":"10.1007\/978-3-540-69850-0_7"},{"key":"25_CR11","unstructured":"Condon, A.: On algorithms for simple stochastic games. In: Advances in Computational Complexity Theory, pp. 51\u201372 (1990)"},{"issue":"4","key":"25_CR12","doi-asserted-by":"crossref","first-page":"857","DOI":"10.1145\/210332.210339","volume":"42","author":"C Courcoubetis","year":"1995","unstructured":"Courcoubetis, C., Yannakakis, M.: The complexity of probabilistic verification. J. ACM 42(4), 857\u2013907 (1995)","journal-title":"J. ACM"},{"key":"25_CR13","unstructured":"de Alfaro, L.: Formal verification of probabilistic systems. Ph.D thesis (1997)"},{"issue":"1","key":"25_CR14","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1007\/s00446-003-0102-z","volume":"17","author":"M Duflot","year":"2004","unstructured":"Duflot, M., Fribourg, L., Picaronny, C.: Randomized dining philosophers without fairness assumption. Distrib. Comput. 17(1), 65\u201376 (2004)","journal-title":"Distrib. Comput."},{"key":"25_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"551","DOI":"10.1007\/978-3-642-14162-1_46","volume-title":"Automata, Languages and Programming","author":"J Fearnley","year":"2010","unstructured":"Fearnley, J.: Exponential lower bounds for policy iteration. In: Abramsky, S., Gavoille, C., Kirchner, C., Meyer auf der Heide, F., Spirakis, P.G. (eds.) ICALP 2010. LNCS, vol. 6199, pp. 551\u2013562. Springer, Heidelberg (2010). doi: 10.1007\/978-3-642-14162-1_46"},{"key":"25_CR16","unstructured":"Fearnley, J.: Strategy iteration algorithms for games and Markov Decision Processes. Ph.D thesis, University of Warwick (2010)"},{"key":"25_CR17","doi-asserted-by":"crossref","unstructured":"Fearnley, J.: Efficient parallel strategy improvement for parity games. In: CAV (2017). To appear","DOI":"10.1007\/978-3-319-63390-9_8"},{"key":"25_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1007\/978-3-642-19811-3_2","volume-title":"Fundamental Approaches to Software Engineering","author":"L Feng","year":"2011","unstructured":"Feng, L., Kwiatkowska, M., Parker, D.: Automated learning of probabilistic assumptions for compositional reasoning. In: Giannakopoulou, D., Orejas, F. (eds.) FASE 2011. LNCS, vol. 6603, pp. 2\u201317. Springer, Heidelberg (2011). doi: 10.1007\/978-3-642-19811-3_2"},{"key":"25_CR19","volume-title":"Competitive Markov Decision Processes","author":"J Filar","year":"1997","unstructured":"Filar, J., Vrieze, K.: Competitive Markov Decision Processes. Springer, New York (1997)"},{"key":"25_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1007\/978-3-642-05258-3_7","volume-title":"MICAI 2009: Advances in Artificial Intelligence","author":"J Frausto-Solis","year":"2009","unstructured":"Frausto-Solis, J., Santiago, E., Mora-Vargas, J.: Cosine policy iteration for solving infinite-horizon Markov Decision Processes. In: Aguirre, A.H., Borja, R.M., Garci\u00e1, C.A.R. (eds.) MICAI 2009. LNCS, vol. 5845, pp. 75\u201386. Springer, Heidelberg (2009). doi: 10.1007\/978-3-642-05258-3_7"},{"key":"25_CR21","doi-asserted-by":"crossref","unstructured":"Friedmann, O.: An exponential lower bound for the parity game strategy improvement algorithm as we know it. In: LICS, pp. 145\u2013156 (2009)","DOI":"10.1109\/LICS.2009.27"},{"key":"25_CR22","unstructured":"Gawlitza, T.M., Schwarz, M.D., Seidl, H.: Parametric strategy iteration. arXiv preprint arXiv:1406.5457 (2014)"},{"key":"25_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1007\/978-3-319-11439-2_10","volume-title":"Reachability Problems","author":"S Haddad","year":"2014","unstructured":"Haddad, S., Monmege, B.: Reachability in MDPs: refining convergence of value iteration. In: Ouaknine, J., Potapov, I., Worrell, J. (eds.) RP 2014. LNCS, vol. 8762, pp. 125\u2013137. Springer, Cham (2014). doi: 10.1007\/978-3-319-11439-2_10"},{"key":"25_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"266","DOI":"10.1007\/978-3-319-52234-0_15","volume-title":"Verification, Model Checking, and Abstract Interpretation","author":"EM Hahn","year":"2017","unstructured":"Hahn, E.M., Schewe, S., Turrini, A., Zhang, L.: Synthesising strategy improvement and recursive algorithms for solving 2.5 player parity games. In: Bouajjani, A., Monniaux, D. (eds.) VMCAI 2017. LNCS, vol. 10145, pp. 266\u2013287. Springer, Cham (2017). doi: 10.1007\/978-3-319-52234-0_15"},{"issue":"2","key":"25_CR25","doi-asserted-by":"crossref","first-page":"380","DOI":"10.1007\/s00224-013-9524-6","volume":"55","author":"KA Hansen","year":"2014","unstructured":"Hansen, K.A., Ibsen-Jensen, R., Miltersen, P.B.: The complexity of solving reachability games using value and strategy iteration. Theor. Comput. Syst. 55(2), 380\u2013403 (2014)","journal-title":"Theor. Comput. Syst."},{"issue":"1","key":"25_CR26","doi-asserted-by":"crossref","first-page":"1:1","DOI":"10.1145\/2432622.2432623","volume":"60","author":"TD Hansen","year":"2013","unstructured":"Hansen, T.D., Miltersen, P.B., Zwick, U.: Strategy iteration is strongly polynomial for 2-player turn-based stochastic games with a constant discount factor. J. ACM 60(1), 1:1\u20131:16 (2013)","journal-title":"J. ACM"},{"issue":"1","key":"25_CR27","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1287\/moor.12.1.163","volume":"12","author":"A Hordijk","year":"1987","unstructured":"Hordijk, A., Puterman, M.L.: On the convergence of policy iteration in finite state undiscounted Markov Decision Processes: the unichain case. MMOR 12(1), 163\u2013176 (1987)","journal-title":"MMOR"},{"key":"25_CR28","unstructured":"Howard, R.A.: Dynamic Programming and Markov Processes (1960)"},{"key":"25_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"310","DOI":"10.1007\/978-3-642-31424-7_25","volume-title":"Computer Aided Verification","author":"A Komuravelli","year":"2012","unstructured":"Komuravelli, A., P\u0103s\u0103reanu, C.S., Clarke, E.M.: Assume-guarantee abstraction refinement for probabilistic systems. In: Madhusudan, P., Seshia, S.A. (eds.) CAV 2012. LNCS, vol. 7358, pp. 310\u2013326. Springer, Heidelberg (2012). doi: 10.1007\/978-3-642-31424-7_25"},{"key":"25_CR30","doi-asserted-by":"crossref","unstructured":"K\u0159et\u00ednsk\u00fd, J., Meggendorfer, T.: Efficient strategy iteration for mean payoff in Markov Decision Processes. Technical report abs\/1707.01859. arXiv.org (2017)","DOI":"10.1007\/978-3-319-68167-2_25"},{"key":"25_CR31","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"585","DOI":"10.1007\/978-3-642-22110-1_47","volume-title":"Computer Aided Verification","author":"M Kwiatkowska","year":"2011","unstructured":"Kwiatkowska, M., Norman, G., Parker, D.: PRISM 4.0: verification of probabilistic real-time systems. In: Gopalakrishnan, G., Qadeer, S. (eds.) CAV 2011. LNCS, vol. 6806, pp. 585\u2013591. Springer, Heidelberg (2011). doi: 10.1007\/978-3-642-22110-1_47"},{"issue":"12\u201313","key":"25_CR32","doi-asserted-by":"crossref","first-page":"1272","DOI":"10.1016\/j.tcs.2008.12.058","volume":"410","author":"M Kwiatkowska","year":"2009","unstructured":"Kwiatkowska, M., Norman, G., Parker, D., Vigliotti, M.G.: Probabilistic mobile ambients. Theoret. Comput. Sci. 410(12\u201313), 1272\u20131303 (2009)","journal-title":"Theoret. Comput. Sci."},{"key":"25_CR33","unstructured":"Luttenberger, M.: Strategy iteration using non-deterministic strategies for solving parity games. CoRR, abs\/0806.2923 (2008)"},{"key":"25_CR34","unstructured":"Puterman, M.L.: Markov Decision Processes: Discrete Stochastic Dynamic Programming. Wiley (2014)"},{"key":"25_CR35","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1007\/978-3-540-87531-4_27","volume-title":"Computer Science Logic","author":"S Schewe","year":"2008","unstructured":"Schewe, S.: An optimal strategy improvement algorithm for solving parity and payoff games. In: Kaminski, M., Martini, S. (eds.) CSL 2008. LNCS, vol. 5213, pp. 369\u2013384. Springer, Heidelberg (2008). doi: 10.1007\/978-3-540-87531-4_27"},{"issue":"1","key":"25_CR36","first-page":"61","volume":"78","author":"O Shlakhter","year":"2013","unstructured":"Shlakhter, O., Lee, C.-G.: Accelerated modified policy iteration algorithms for Markov Decision Processes. MMOR 78(1), 61\u201376 (2013)","journal-title":"MMOR"},{"issue":"2","key":"25_CR37","doi-asserted-by":"crossref","first-page":"146","DOI":"10.1137\/0201010","volume":"1","author":"R Tarjan","year":"1972","unstructured":"Tarjan, R.: Depth-first search and linear graph algorithms. SICOMP 1(2), 146\u2013160 (1972)","journal-title":"SICOMP"},{"key":"25_CR38","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"202","DOI":"10.1007\/10722167_18","volume-title":"Computer Aided Verification","author":"J V\u00f6ge","year":"2000","unstructured":"V\u00f6ge, J., Jurdzi\u0144ski, M.: A discrete strategy improvement algorithm for solving parity games. In: Emerson, E.A., Sistla, A.P. (eds.) CAV 2000. LNCS, vol. 1855, pp. 202\u2013215. Springer, Heidelberg (2000). doi: 10.1007\/10722167_18"},{"issue":"4","key":"25_CR39","doi-asserted-by":"crossref","first-page":"593","DOI":"10.1287\/moor.1110.0516","volume":"36","author":"Y Ye","year":"2011","unstructured":"Ye, Y.: The simplex and policy-iteration methods are strongly polynomial for the Markov decision problem with a fixed discount rate. MMOR 36(4), 593\u2013603 (2011)","journal-title":"MMOR"}],"container-title":["Lecture Notes in Computer Science","Automated Technology for Verification and Analysis"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-68167-2_25","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,10,3]],"date-time":"2019-10-03T19:38:39Z","timestamp":1570131519000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-68167-2_25"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319681665","9783319681672"],"references-count":39,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-68167-2_25","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017]]}}}