> Details

Kiefer, Stefan [Author]; Mayr, Richard [Author]; Shirmohammadi, Mahsa [Author]; Totzke, Patrick [Author] ; Stefan Kiefer and Richard Mayr and Mahsa Shirmohammadi and Patrick Totzke [Contributor]

Strategy Complexity of Parity Objectives in Countable MDPs

Reference
management

Bookmarks

Remove from
bookmarks

Share this on Whatsapp

Close

Bookmarks



You can manage bookmarks using lists, please log in to your user account for this.
  • Media type: Text; E-Article; Electronic Conference Proceeding
  • Title: Strategy Complexity of Parity Objectives in Countable MDPs
  • Contributor: Kiefer, Stefan [Author]; Mayr, Richard [Author]; Shirmohammadi, Mahsa [Author]; Totzke, Patrick [Author]
  • Published: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2020
  • Language: English
  • DOI: https://doi.org/10.4230/LIPIcs.CONCUR.2020.39
  • Keywords: Levy’s zero-one law ; Parity objectives ; Markov decision processes
  • Origination:
  • Footnote: Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
  • Description: We study countably infinite MDPs with parity objectives. Unlike in finite MDPs, optimal strategies need not exist, and may require infinite memory if they do. We provide a complete picture of the exact strategy complexity of ε-optimal strategies (and optimal strategies, where they exist) for all subclasses of parity objectives in the Mostowski hierarchy. Either MD-strategies, Markov strategies, or 1-bit Markov strategies are necessary and sufficient, depending on the number of colors, the branching degree of the MDP, and whether one considers ε-optimal or optimal strategies. In particular, 1-bit Markov strategies are necessary and sufficient for ε-optimal (resp. optimal) strategies for general parity objectives.
  • Access State: Open Access