No good Markov strategies for Büchi objectives in countable MDPs
Abstract We study countably infinite Markov decision processes with Büchi objectives, which ask to visit a given subset of states infinitely often. A question left open by T.P. Hill (1979) is whether there always exist $$\varepsilon $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>ε</mml:mi> </mml:math> -optimal Markov strategies, i.e., strategies that base decisions only on the current state and on the clock (the number of steps taken so far). We provide a negative answer to this question by constructing a non-trivial counterexample.
Authors
- Mahsa Shirmohammadi (ORCID: https://orcid.org/0000-0002-7779-2339)
- Stefan Kiefer (ORCID: https://orcid.org/0000-0003-4173-6877)
- Patrick Totzke (ORCID: https://orcid.org/0000-0001-5274-8190)
- Richard Mayr
Institutions
- Centre National de la Recherche Scientifique (FR)
- University of Liverpool (GB)
- University of Oxford (GB)
- Institut de Recherche en Informatique Fondamentale (FR)
- University of Edinburgh (GB)
Publication Details
- Journal
- Annals of Operations Research
- Published
- 2026-05-09
- DOI
- https://doi.org/10.1007/s10479-026-07226-6
- Primary Topic
- Formal Methods in Verification
- Type
- article
- Field-Weighted Citation Impact
- 0.00
Funders
- Agence Nationale de la Recherche
- Engineering and Physical Sciences Research Council