{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,29]],"date-time":"2026-05-29T09:19:21Z","timestamp":1780046361569,"version":"3.53.1"},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2026,5,9]],"date-time":"2026-05-09T00:00:00Z","timestamp":1778284800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2026,5,9]],"date-time":"2026-05-09T00:00:00Z","timestamp":1778284800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR-22-CE48-0005"],"award-info":[{"award-number":["ANR-22-CE48-0005"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/X042596\/1"],"award-info":[{"award-number":["EP\/X042596\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Ann Oper Res"],"published-print":{"date-parts":[[2026,6]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    We study countably infinite Markov decision processes with B\u00fcchi objectives, which ask to visit a given subset of states infinitely often. A question left open by T.P. Hill (1979) is whether there always exist\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$\\varepsilon $$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mi>\u03b5<\/mml:mi>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    -optimal Markov strategies, i.e., strategies that base decisions only on the current state and on the clock (the number of steps taken so far). We provide a negative answer to this question by constructing a non-trivial counterexample.\n                  <\/jats:p>","DOI":"10.1007\/s10479-026-07226-6","type":"journal-article","created":{"date-parts":[[2026,5,9]],"date-time":"2026-05-09T07:35:55Z","timestamp":1778312155000},"page":"711-726","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["No good Markov strategies for B\u00fcchi objectives in countable MDPs"],"prefix":"10.1007","volume":"361","author":[{"given":"Stefan","family":"Kiefer","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Richard","family":"Mayr","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mahsa","family":"Shirmohammadi","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5274-8190","authenticated-orcid":false,"given":"Patrick","family":"Totzke","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2026,5,9]]},"reference":[{"key":"7226_CR1","doi-asserted-by":"publisher","unstructured":"Abbeel, P., Ng, A.Y.: Learning first-order Markov models for control. In: Proceedings of the 18th International Conference on Neural Information Processing Systems. NIPS\u201904, pp. 1\u20138. MIT Press, Cambridge, MA, USA (2004). https:\/\/doi.org\/10.5555\/2976040.2976041","DOI":"10.5555\/2976040.2976041"},{"key":"7226_CR2","volume-title":"Principles of Model Checking","author":"C Baier","year":"2008","unstructured":"Baier, C., & Katoen, J.-P. (2008). Principles of Model Checking. Cambridge, MA: MIT Press."},{"key":"7226_CR3","doi-asserted-by":"crossref","unstructured":"B\u00e4uerle, N., & Rieder, U. (2011). Markov Decision Processes with Applications to Finance. Springer","DOI":"10.1007\/978-3-642-18324-9"},{"key":"7226_CR4","unstructured":"Billingsley, P.: Probability and Measure. Wiley, New York, NY (1995). Third edition"},{"issue":"9","key":"7226_CR5","doi-asserted-by":"publisher","first-page":"1249","DOI":"10.1016\/S0005-1098(00)00050-9","volume":"36","author":"VD Blondel","year":"2000","unstructured":"Blondel, V. D., & Tsitsiklis, J. N. (2000). A survey of computational complexity results in systems and control. Automatica, 36(9), 1249\u20131274. https:\/\/doi.org\/10.1016\/S0005-1098(00)00050-9","journal-title":"Automatica"},{"key":"7226_CR6","doi-asserted-by":"publisher","unstructured":"Chatterjee, K., Alfaro, L., & Henzinger, T. (2004). Trading memory for randomness. In: Annual Conference on Quantitative Evaluation of Systems, pp. 206\u2013217. IEEE Computer Society, Los Alamitos, CA, USA. https:\/\/doi.org\/10.1109\/QEST.2004.10051","DOI":"10.1109\/QEST.2004.10051"},{"key":"7226_CR7","unstructured":"Chatterjee, K., Jurdzi\u0144ski, M., & Henzinger, T.A. (2004). Quantitative stochastic parity games. In: Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 121\u2013130. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA. http:\/\/dl.acm.org\/citation.cfm?id=982792.982808"},{"issue":"2","key":"7226_CR8","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. (2012). A survey of stochastic $$\\omega $$-regular games. Journal of Computer and System Sciences, 78(2), 394\u2013413. https:\/\/doi.org\/10.1016\/j.jcss.2011.05.002","journal-title":"Journal of Computer and System Sciences"},{"key":"7226_CR9","doi-asserted-by":"publisher","unstructured":"Clarke, E.M., Henzinger, T.A., Veith, H., & Bloem, R. (eds.) (2018). Handbook of Model Checking. Springer. https:\/\/doi.org\/10.1007\/978-3-319-10575-8","DOI":"10.1007\/978-3-319-10575-8"},{"key":"7226_CR10","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1090\/S0002-9947-1979-0517690-9","volume":"247","author":"TP Hill","year":"1979","unstructured":"Hill, T. P. (1979). On the existence of good Markov strategies. Transactions of the American Mathematical Society, 247, 157\u2013176. https:\/\/doi.org\/10.1090\/S0002-9947-1979-0517690-9","journal-title":"Transactions of the American Mathematical Society"},{"issue":"2","key":"7226_CR11","doi-asserted-by":"publisher","first-page":"125","DOI":"10.15517\/rmta.v6i2.173","volume":"6","author":"TP Hill","year":"1999","unstructured":"Hill, T. P. (1999). Goal problems in gambling theory. Revista de Matem\u00e1tica: Teor\u00eda y Aplicaciones, 6(2), 125\u2013132. https:\/\/doi.org\/10.15517\/rmta.v6i2.173","journal-title":"Revista de Matem\u00e1tica: Teor\u00eda y Aplicaciones"},{"key":"7226_CR12","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s10479-019-03460-3","volume":"283","author":"MN Katehakis","year":"2019","unstructured":"Katehakis, M. N., Smit, L. C., & Spieksma, F. M. (2019). Inversion and spectral analysis of matrices arising in the analysis of Markov processes. Annals of Operations Research, 283, 1\u201332. https:\/\/doi.org\/10.1007\/s10479-019-03460-3","journal-title":"Annals of Operations Research"},{"key":"7226_CR13","doi-asserted-by":"publisher","unstructured":"Kiefer, S., Mayr, R., Shirmohammadi, M., & Totzke, P. (2025). Strategy complexity of B\u00fcchi and Transience objectives in concurrent stochastic games. In: EC\u201925: Proceedings of the 26th ACM Conference on Economics and Computation, pp. 390\u2013409. ACM. https:\/\/doi.org\/10.1145\/3736252.3742560","DOI":"10.1145\/3736252.3742560"},{"key":"7226_CR14","doi-asserted-by":"publisher","unstructured":"Kiefer, S., Mayr, R., Shirmohammadi, M., & Wojtczak, D. (2017). Parity Objectives in Countable MDPs. In: ACM\/IEEE Symposium on Logic in Computer Science (LICS), pp. 1\u201311. IEEE. https:\/\/doi.org\/10.1109\/LICS.2017.8005100","DOI":"10.1109\/LICS.2017.8005100"},{"key":"7226_CR15","unstructured":"Kr\u010d\u00e1l, J. (2009). Determinacy and Optimal Strategies in Stochastic Games. Master\u2019s thesis, Masaryk University, School of Informatics, Brno, Czech Republic. http:\/\/is.muni.cz\/th\/139854\/fi_m\/dp.pdf"},{"key":"7226_CR16","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-4002-0","author":"AP Maitra","year":"1996","unstructured":"Maitra, A. P., & Sudderth, W. D. (1996). Discrete Gambling and Stochastic Games. Springer. https:\/\/doi.org\/10.1007\/978-1-4612-4002-0","journal-title":"Discrete Gambling and Stochastic Games. Springer"},{"issue":"2","key":"7226_CR17","doi-asserted-by":"publisher","first-page":"563","DOI":"10.2307\/2035700","volume":"20","author":"D Ornstein","year":"1969","unstructured":"Ornstein, D. (1969). On the existence of stationary optimal strategies. Proceedings of the American Mathematical Society, 20(2), 563\u2013569. https:\/\/doi.org\/10.2307\/2035700","journal-title":"Proceedings of the American Mathematical Society"},{"key":"7226_CR18","doi-asserted-by":"publisher","unstructured":"Puterman, M.L. (1994). Markov Decision Processes: Discrete Stochastic Dynamic Programming, 1st edn. John Wiley & Sons, Inc., New York, NY, USA. https:\/\/doi.org\/10.1002\/9780470316887","DOI":"10.1002\/9780470316887"},{"key":"7226_CR19","doi-asserted-by":"publisher","unstructured":"Sch\u00e4l, M. (2002). Markov decision processes in finance and dynamic options. In: Handbook of Markov Decision Processes, pp. 461\u2013487. Springer. https:\/\/doi.org\/10.1007\/978-1-4615-0805-2_15","DOI":"10.1007\/978-1-4615-0805-2_15"},{"key":"7226_CR20","doi-asserted-by":"publisher","DOI":"10.1002\/9781118557426","author":"O Sigaud","year":"2013","unstructured":"Sigaud, O., & Buffet, O. (2013). Markov Decision Processes in Artificial Intelligence. John Wiley & Sons. https:\/\/doi.org\/10.1002\/9781118557426","journal-title":"John Wiley & Sons"},{"key":"7226_CR21","doi-asserted-by":"publisher","unstructured":"Sutton, R.S., & Barto, A.G. (2018). Reinforcement Learning: An Introduction. Adaptive Computation and Machine Learning. MIT Press. https:\/\/doi.org\/10.5555\/3312046","DOI":"10.5555\/3312046"},{"key":"7226_CR22","unstructured":"Thuijsman, F. (1992). Optimality and Equilibria in Stochastic Games. CWI Tract - Centrum voor Wiskunde en Informatica, vol. 82. Centrum voor Wiskunde en Informatica. https:\/\/ir.cwi.nl\/pub\/13203"}],"container-title":["Annals of Operations Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10479-026-07226-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10479-026-07226-6","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10479-026-07226-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,29]],"date-time":"2026-05-29T08:53:49Z","timestamp":1780044829000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10479-026-07226-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,5,9]]},"references-count":22,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,6]]}},"alternative-id":["7226"],"URL":"https:\/\/doi.org\/10.1007\/s10479-026-07226-6","relation":{},"ISSN":["0254-5330","1572-9338"],"issn-type":[{"value":"0254-5330","type":"print"},{"value":"1572-9338","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,5,9]]},"assertion":[{"value":"9 October 2025","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 April 2026","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 May 2026","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}