文章基本信息

标题：Strategy Complexity of Parity Objectives in Countable MDPs
本地全文：下载
作者：Stefan Kiefer ; Richard Mayr ; Mahsa Shirmohammadi 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：171
页码：39:1-39:17
DOI：10.4230/LIPIcs.CONCUR.2020.39
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Markov decision processes; Parity objectives; Levyâs zero-one law