文章基本信息

标题：Strategy Complexity of Mean Payoff, Total Payoff and Point Payoff Objectives in Countable MDPs
本地全文：下载
作者：Mayr, Richard ; Munday, Eric
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2021
卷号：203
DOI：10.4230/LIPIcs.CONCUR.2021.12
语种：English
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：We study countably infinite Markov decision processes (MDPs) with real-valued transition rewards. Every infinite run induces the following sequences of payoffs: Point payoff (the sequence of directly seen transition rewards), Total payoff (the sequence of the sums of all rewards so far), and 3. Mean payoff. For each payoff type, the objective is to maximize the probability that the liminf is non-negative. We establish the complete picture of the strategy complexity of these objectives, i.e., how much memory is necessary and sufficient for ε-optimal (resp. optimal) strategies. Some cases can be won with memoryless deterministic strategies, while others require a step counter, a reward counter, or both.
关键词：Markov decision processes;Strategy complexity;Mean payoff