Büchi Objectives in Countable MDPs

Stefan Kiefer; Richard Mayr; Mahsa Shirmohammadi; Patrick Totzke

doi:10.4230/LIPIcs.ICALP.2019.119

Büchi Objectives in Countable MDPs

Stefan Kiefer, Richard Mayr, Mahsa Shirmohammadi, Patrick Totzke

Research output: Chapter in Book/Report/Conference proceeding › Conference 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 language	English
Title of host publication	46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Editors	Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, Stefano Leonardi
Publisher	Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany
Pages	119:1–119:14
Number of pages	27
Volume	132
ISBN (Electronic)	978-3-95977-109-2
DOIs	https://doi.org/10.4230/LIPIcs.ICALP.2019.119
Publication status	E-pub ahead of print - 12 Jul 2019
Event	46th International Colloquium on Automata, Languages and Programming - Patras, Greece Duration: 8 Jul 2019 → 12 Jul 2019 https://icalp2019.upatras.gr/index.php#welcome

Publication series

Name	LIPICS
Publisher	Schloss Dagstuhl - Leibniz-Zentrum für Informatik
Volume	132
ISSN (Electronic)	1868-8969

Conference

Conference	46th International Colloquium on Automata, Languages and Programming
Abbreviated title	ICALP 2019
Country/Territory	Greece
City	Patras
Period	8/07/19 → 12/07/19
Internet address	https://icalp2019.upatras.gr/index.php#welcome

Keywords

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

Access to Document

10.4230/LIPIcs.ICALP.2019.119

1904.11573v2Accepted author manuscript, 373 KB
Büchi Objectives_KIEFER_DoA250419_VoR_CC-BY
© Stefan Kiefer, Richard Mayr, Mahsa Shirmohammadi, and Patrick Totzke; licensed under Creative Commons License CC-BY
Final published version, 549 KBLicence: Creative Commons: Attribution (CC-BY)

http://drops.dagstuhl.de/opus/portals/lipics/index.php?semnr=16111

1 Finished

Energy Efficient Control
Mayr, R.
EPSRC
1/09/15 → 31/08/19
Project: Research

Cite this

Kiefer, S., Mayr, R., Shirmohammadi, M., & Totzke, P. (2019). Büchi Objectives in Countable MDPs. In C. Baier, I. Chatzigiannakis, P. Flocchini, & S. Leonardi (Eds.), 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019) (Vol. 132, pp. 119:1–119:14). [119] (LIPICS; Vol. 132). Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany. https://doi.org/10.4230/LIPIcs.ICALP.2019.119

Kiefer, Stefan ; Mayr, Richard ; Shirmohammadi, Mahsa ; Totzke, Patrick. / Büchi Objectives in Countable MDPs. 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). editor / Christel Baier ; Ioannis Chatzigiannakis ; Paola Flocchini ; Stefano Leonardi. Vol. 132 Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany, 2019. pp. 119:1–119:14 (LIPICS).

@inproceedings{3e4035b29ff8452f8331f5cc833b61df,

title = "B{\"u}chi Objectives in Countable MDPs",

abstract = "We study countably infinite Markov decision processes with B{\"u}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.",

keywords = "math.PR, cs.FL, math.OC, Markov decision process, Random walks, Markov chains, Probability, Statistics",

author = "Stefan Kiefer and Richard Mayr and Mahsa Shirmohammadi and Patrick Totzke",

note = "Full version of an ICALP'19 paper.; 46th International Colloquium on Automata, Languages and Programming, ICALP 2019 ; Conference date: 08-07-2019 Through 12-07-2019",

year = "2019",

month = jul,

day = "12",

doi = "10.4230/LIPIcs.ICALP.2019.119",

language = "English",

volume = "132",

series = "LIPICS",

publisher = "Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany",

pages = "119:1–119:14",

editor = "Christel Baier and Ioannis Chatzigiannakis and Paola Flocchini and Stefano Leonardi",

booktitle = "46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)",

url = "https://icalp2019.upatras.gr/index.php#welcome",

}

Kiefer, S, Mayr, R, Shirmohammadi, M & Totzke, P 2019, Büchi Objectives in Countable MDPs. in C Baier, I Chatzigiannakis, P Flocchini & S Leonardi (eds), 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). vol. 132, 119, LIPICS, vol. 132, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany, pp. 119:1–119:14, 46th International Colloquium on Automata, Languages and Programming, Patras, Greece, 8/07/19. https://doi.org/10.4230/LIPIcs.ICALP.2019.119

Büchi Objectives in Countable MDPs. / Kiefer, Stefan; Mayr, Richard; Shirmohammadi, Mahsa; Totzke, Patrick.

46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). ed. / Christel Baier; Ioannis Chatzigiannakis; Paola Flocchini; Stefano Leonardi. Vol. 132 Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany, 2019. p. 119:1–119:14 119 (LIPICS; Vol. 132).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Büchi Objectives in Countable MDPs

AU - Kiefer, Stefan

AU - Mayr, Richard

AU - Shirmohammadi, Mahsa

AU - Totzke, Patrick

N1 - Full version of an ICALP'19 paper.

PY - 2019/7/12

Y1 - 2019/7/12

N2 - 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.

AB - 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.

KW - math.PR

KW - cs.FL

KW - math.OC

KW - Markov decision process

KW - Random walks

KW - Markov chains

KW - Probability

KW - Statistics

U2 - 10.4230/LIPIcs.ICALP.2019.119

DO - 10.4230/LIPIcs.ICALP.2019.119

M3 - Conference contribution

VL - 132

T3 - LIPICS

SP - 119:1–119:14

BT - 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

A2 - Baier, Christel

A2 - Chatzigiannakis, Ioannis

A2 - Flocchini, Paola

A2 - Leonardi, Stefano

PB - Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany

T2 - 46th International Colloquium on Automata, Languages and Programming

Y2 - 8 July 2019 through 12 July 2019

ER -

Kiefer S, Mayr R, Shirmohammadi M, Totzke P. Büchi Objectives in Countable MDPs. In Baier C, Chatzigiannakis I, Flocchini P, Leonardi S, editors, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Vol. 132. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany. 2019. p. 119:1–119:14. 119. (LIPICS). https://doi.org/10.4230/LIPIcs.ICALP.2019.119

Büchi Objectives in Countable MDPs

Abstract

Publication series

Conference

Keywords

Access to Document

Fingerprint

Projects

Energy Efficient Control

Cite this