{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,8]],"date-time":"2025-09-08T06:48:54Z","timestamp":1757314134553,"version":"3.37.3"},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2020,5,18]],"date-time":"2020-05-18T00:00:00Z","timestamp":1589760000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,5,18]],"date-time":"2020-05-18T00:00:00Z","timestamp":1589760000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"COST Action European Network for Game Theory","award":["CA16228","CA16228"],"award-info":[{"award-number":["CA16228","CA16228"]}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"crossref","award":["grants #217\/17 and #722\/18 and the NSFC-ISF Grant #2510\/17","grants #217\/17 and #722\/18 and the NSFC-ISF Grant #2510\/17"],"award-info":[{"award-number":["grants #217\/17 and #722\/18 and the NSFC-ISF Grant #2510\/17","grants #217\/17 and #722\/18 and the NSFC-ISF Grant #2510\/17"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"crossref"}]},{"name":"COST Action European Network for Game Theory","award":["CA16228","CA16228"],"award-info":[{"award-number":["CA16228","CA16228"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Optim Theory Appl"],"published-print":{"date-parts":[[2020,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We consider discrete-time Markov decision processes in which the decision maker is interested in long but finite horizons. First we consider reachability objective: the decision maker\u2019s goal is to reach a specific target state with the highest possible probability. A strategy is said to overtake another strategy, if it gives a strictly higher probability of reaching the target state on all sufficiently large but finite horizons. We prove that there exists a pure stationary strategy that is not overtaken by any pure strategy nor by any stationary strategy, under some condition on the transition structure and respectively under genericity. A strategy that is not overtaken by any other strategy, called an overtaking optimal strategy, does not always exist. We provide sufficient conditions for its existence. Next we consider safety objective: the decision maker\u2019s goal is to avoid a specific state with the highest possible probability. We argue that the results proven for reachability objective extend to this model.<\/jats:p>","DOI":"10.1007\/s10957-020-01681-2","type":"journal-article","created":{"date-parts":[[2020,5,18]],"date-time":"2020-05-18T17:04:17Z","timestamp":1589821457000},"page":"945-965","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Reachability and Safety Objectives in Markov Decision Processes on Long but Finite Horizons"],"prefix":"10.1007","volume":"185","author":[{"given":"Galit","family":"Ashkenazi-Golan","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9599-4615","authenticated-orcid":false,"given":"J\u00e1nos","family":"Flesch","sequence":"additional","affiliation":[]},{"given":"Arkadi","family":"Predtetchinski","sequence":"additional","affiliation":[]},{"given":"Eilon","family":"Solan","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,5,18]]},"reference":[{"key":"1681_CR1","volume-title":"Principles of Model Checking","author":"C Baier","year":"2008","unstructured":"Baier, C., Katoen, J.P.: Principles of Model Checking. MIT Press, Cambridge (2008)"},{"key":"1681_CR2","doi-asserted-by":"publisher","first-page":"394","DOI":"10.1016\/j.jcss.2011.05.002","volume":"78","author":"K Chatterjee","year":"2012","unstructured":"Chatterjee, K., Henzinger, T.A.: A survey of stochastic $$\\omega $$-regular games. J. Comput. Syst. Sci. 78, 394\u2013413 (2012)","journal-title":"J. Comput. Syst. Sci."},{"key":"1681_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/978-3-319-62809-7_1","volume-title":"Developments in Language Theory","author":"V Bruy\u00e8re","year":"2017","unstructured":"Bruy\u00e8re, V.: Computer aided synthesis: a game-theoretic approach. In: Charlier, E., Leroy, J., Rigo, M. (eds.) Developments in Language Theory. Lecture Notes in Computer Science, vol. 10396, pp. 3\u201335. Springer, Berlin (2017)"},{"key":"1681_CR4","volume-title":"Dynamic Programming and Markov Processes","author":"RA Howard","year":"1960","unstructured":"Howard, R.A.: Dynamic Programming and Markov Processes. MIT Press, Cambridge (1960)"},{"key":"1681_CR5","doi-asserted-by":"publisher","first-page":"719","DOI":"10.1214\/aoms\/1177704593","volume":"33","author":"D Blackwell","year":"1962","unstructured":"Blackwell, D.: Discrete dynamic programming. Ann. Math. Stat. 33, 719\u2013726 (1962)","journal-title":"Ann. Math. Stat."},{"key":"1681_CR6","doi-asserted-by":"publisher","first-page":"212","DOI":"10.1007\/s13235-016-0186-2","volume":"7","author":"J Flesch","year":"2017","unstructured":"Flesch, J., Predtetchinski, A., Solan, E.: Sporadic overtaking optimality in Markov decision problems. Dyn. Games Appl. 7, 212\u2013228 (2017)","journal-title":"Dyn. Games Appl."},{"key":"1681_CR7","doi-asserted-by":"crossref","unstructured":"Randour, M., Raskin, J.-F., Sankur, O.: Variations on the stochastic shortest path problem. In: International Workshop on Verification, Model Checking, and Abstract Interpretation, pp. 1\u201318. Springer, Berlin, Heidelberg (2015)","DOI":"10.1007\/978-3-662-46081-8_1"},{"issue":"2\u20133","key":"1681_CR8","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1007\/s10703-016-0262-7","volume":"50","author":"M Randour","year":"2017","unstructured":"Randour, M., Raskin, J.-F., Sankur, O.: Percentile queries in multi-dimensional Markov decision processes. Form. Methods Syst. Des. 50(2\u20133), 207\u2013248 (2017)","journal-title":"Form. Methods Syst. Des."},{"key":"1681_CR9","doi-asserted-by":"publisher","first-page":"150","DOI":"10.1007\/s00224-013-9495-7","volume":"54","author":"T Brihaye","year":"2014","unstructured":"Brihaye, T., Bruy\u00e8re, V., De Pril, J.: On equilibria in quantitative games with reachability\/safety objectives. Theory Comput. Syst. 54, 150\u2013189 (2014)","journal-title":"Theory Comput. Syst."},{"key":"1681_CR10","doi-asserted-by":"publisher","first-page":"497","DOI":"10.1007\/BF00935464","volume":"44","author":"LE Stern","year":"1984","unstructured":"Stern, L.E.: Criteria of optimality in the infinite-time optimal control problem. J. Optim. Theory Appl. 44, 497\u2013508 (1984)","journal-title":"J. Optim. Theory Appl."},{"key":"1681_CR11","doi-asserted-by":"publisher","DOI":"10.1002\/9780470316887","volume-title":"Markov Decision Processes: Discrete Stochastic Dynamic Programming","author":"ML Puterman","year":"1994","unstructured":"Puterman, M.L.: Markov Decision Processes: Discrete Stochastic Dynamic Programming. Wiley, New York (1994)"},{"key":"1681_CR12","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-76755-5","volume-title":"Infinite Horizon Optimal Control","author":"DA Carlson","year":"1991","unstructured":"Carlson, D.A., Haurie, A., Leizarowitz, A.: Infinite Horizon Optimal Control. Springer-Verlag, Berlin (1991)"},{"key":"1681_CR13","volume-title":"Turnpike Properties in the Calculus of Variations and Optimal Control","author":"AJ Zaslavski","year":"2006","unstructured":"Zaslavski, A.J.: Turnpike Properties in the Calculus of Variations and Optimal Control. Springer, New York (2006)"},{"key":"1681_CR14","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-08828-0","volume-title":"Turnpike Phenomenon and Infinite Horizon Optimal Control","author":"AJ Zaslavski","year":"2014","unstructured":"Zaslavski, A.J.: Turnpike Phenomenon and Infinite Horizon Optimal Control. Springer, New York (2014)"},{"key":"1681_CR15","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02547-1","volume-title":"Continuous-Time Markov Decision Processes","author":"X Guo","year":"2009","unstructured":"Guo, X., Hern\u00e1ndez-Lerma, O.: Continuous-Time Markov Decision Processes. Springer, Berlin (2009)"},{"key":"1681_CR16","doi-asserted-by":"publisher","first-page":"469","DOI":"10.1016\/j.orl.2012.08.005","volume":"40","author":"Z M\u00e9der","year":"2012","unstructured":"M\u00e9der, Z., Flesch, J., Peeters, R.: Optimal choice for finite and infinite horizons. Oper. Res. Lett. 40, 469\u2013474 (2012)","journal-title":"Oper. Res. Lett."},{"key":"1681_CR17","doi-asserted-by":"publisher","first-page":"435","DOI":"10.1007\/s001860050059","volume":"49","author":"AS Nowak","year":"1999","unstructured":"Nowak, A.S., Vega-Amaya, O.: A counterexample on overtaking optimality. Math. Method Oper. Res. 49, 435\u2013439 (1999)","journal-title":"Math. Method Oper. Res."},{"key":"1681_CR18","doi-asserted-by":"publisher","first-page":"158","DOI":"10.1287\/moor.21.1.158","volume":"21","author":"A Leizarowitz","year":"1996","unstructured":"Leizarowitz, A.: Overtaking and almost-sure optimality for infinite horizon Markov decision processes. Math. Oper. Res. 21, 158\u2013181 (1996)","journal-title":"Math. Oper. Res."},{"key":"1681_CR19","doi-asserted-by":"publisher","first-page":"1095","DOI":"10.1073\/pnas.39.10.1953","volume":"39","author":"LS Shapley","year":"1953","unstructured":"Shapley, L.S.: Stochastic games. Proc. Natl. Acad. Sci. 39, 1095\u20131100 (1953)","journal-title":"Proc. Natl. Acad. Sci."},{"key":"1681_CR20","doi-asserted-by":"crossref","first-page":"353","DOI":"10.1111\/j.2517-6161.1984.tb01308.x","volume":"46","author":"MHA Davis","year":"1984","unstructured":"Davis, M.H.A.: Piecewise-deterministic Markov processes: a general class of non-diffusion stochastic models. J. R. Stat. Soc. Ser. B Methodol. 46, 353\u2013388 (1984)","journal-title":"J. R. Stat. Soc. Ser. B Methodol."},{"key":"1681_CR21","doi-asserted-by":"publisher","first-page":"526","DOI":"10.1002\/asmb.2177","volume":"32","author":"E De Santis","year":"2016","unstructured":"De Santis, E., Spizzichino, F.: Usual and stochastic tail orders between hitting times for two Markov chains. Appl. Stoch. Models Bus. Ind. 32, 526\u2013538 (2016)","journal-title":"Appl. Stoch. Models Bus. Ind."},{"key":"1681_CR22","doi-asserted-by":"publisher","first-page":"973","DOI":"10.5802\/afst.1472","volume":"24","author":"P Diaconis","year":"2015","unstructured":"Diaconis, P., Laurent, M.: On quantitative convergence to quasi-stationarity. Ann. Facult\u00e9 Sci. Toulouse: Math. 24, 973\u20131016 (2015)","journal-title":"Ann. Facult\u00e9 Sci. Toulouse: Math."}],"container-title":["Journal of Optimization Theory and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10957-020-01681-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10957-020-01681-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10957-020-01681-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,8,5]],"date-time":"2024-08-05T23:45:50Z","timestamp":1722901550000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10957-020-01681-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,5,18]]},"references-count":22,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2020,6]]}},"alternative-id":["1681"],"URL":"https:\/\/doi.org\/10.1007\/s10957-020-01681-2","relation":{},"ISSN":["0022-3239","1573-2878"],"issn-type":[{"type":"print","value":"0022-3239"},{"type":"electronic","value":"1573-2878"}],"subject":[],"published":{"date-parts":[[2020,5,18]]},"assertion":[{"value":"11 November 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 April 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 May 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}