2026-07-22T06:50:12Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10695 2024-03-06T10:46:29Z ddc:004 open_access

Büchi Objectives in Countable MDPs (Track B: Automata, Logic, Semantics, and Theory of Programming) Kiefer, Stefan Mayr, Richard Shirmohammadi, Mahsa Totzke, Patrick Markov decision processes We study countably infinite Markov decision processes with Büchi objectives, which ask to visit a given subset F of states infinitely often. A question left open by T.P. Hill in 1979 [Theodore Preston Hill, 1979] is whether there always exist epsilon-optimal Markov strategies, i.e., strategies that base decisions only on the current state and the number of steps taken so far. We provide a negative answer to this question by constructing a non-trivial counterexample. On the other hand, we show that Markov strategies with only 1 bit of extra memory are sufficient. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Stefan Kiefer and Richard Mayr and Mahsa Shirmohammadi and Patrick Totzke 2019 Is Part Of LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2019.119 urn:nbn:de:0030-drops-106959 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.119 eng https://creativecommons.org/licenses/by/3.0/legalcode