Büchi Objectives in Countable MDPs

Stefan Kiefer, Richard Mayr, Mahsa Shirmohammadi, Patrick Totzke

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

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 [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
Pages119:1–119:14
Number of pages27
Volume132
ISBN (Electronic)978-3-95977-109-2
DOIs
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
https://icalp2019.upatras.gr/index.php#welcome

Publication series

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

Conference

Conference46th International Colloquium on Automata, Languages and Programming
Abbreviated titleICALP 2019
Country/TerritoryGreece
CityPatras
Period8/07/1912/07/19
Internet address

Keywords

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

Fingerprint

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

    Mayr, R.

    EPSRC

    1/09/1531/08/19

    Project: Research

Cite this