Reference:

Stefan Kiefer, Richard Mayr, Mahsa Shirmohammadi, and Patrick Totzke. Büchi objectives in countable MDPs. In Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP), Leibniz International Proceedings in Informatics (LIPIcs), pages 119:1–119:14, 2019.

Abstract:

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.

Suggested BibTeX entry:

@inproceedings{19KMST-ICALP,
    author = {Stefan Kiefer and Richard Mayr and Mahsa Shirmohammadi and Patrick Totzke},
    booktitle = {Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP)},
    pages = {119:1--119:14},
    series = {Leibniz International Proceedings in Informatics (LIPIcs)},
    title = {B{\"{u}}chi Objectives in Countable {MDP}s},
    year = {2019}
}