Büchi Objectives in Countable MDPs

Stefan Kiefer, Richard Mayr, Mahsa Shirmohammadi, Patrick Totzke

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract / Description of output

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 [10] is whether there always exist ε-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.
Original languageEnglish
Title of host publication46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
EditorsChristel Baier, Ioannis Chatzigiannakis, Paola Flocchini, Stefano Leonardi
PublisherSchloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany
Number of pages27
ISBN (Electronic)978-3-95977-109-2
Publication statusE-pub ahead of print - 12 Jul 2019
Event46th International Colloquium on Automata, Languages and Programming - Patras, Greece
Duration: 8 Jul 201912 Jul 2019

Publication series

PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
ISSN (Electronic)1868-8969


Conference46th International Colloquium on Automata, Languages and Programming
Abbreviated titleICALP 2019
Internet address

Keywords / Materials (for Non-textual outputs)

  • math.PR
  • cs.FL
  • math.OC
  • Markov decision process
  • Random walks
  • Markov chains
  • Probability
  • Statistics


Dive into the research topics of 'Büchi Objectives in Countable MDPs'. Together they form a unique fingerprint.

Cite this