Strategy Complexity of Mean Payoff, Total Payoff and Point Payoff Objectives in Countable MDPs

Richard Mayr, Eric Munday

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We study countably infinite Markov decision processes (MDPs) with real-valued transition rewards. Every infinite run induces the following sequences of payoffs: 1. Point payoff (the sequence of directly seen transition rewards), 2. 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 lim inf 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.
Original languageEnglish
Title of host publication32nd International Conference on Concurrency Theory (CONCUR 2021)
EditorsSerge Haddad, Daniele Varacca
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Pages12:1-12:15
Number of pages15
ISBN (Electronic)978-3-95977-203-7
DOIs
Publication statusPublished - 13 Aug 2021
Event32nd International Conference on Concurrency Theory - Online, Paris, France
Duration: 23 Aug 202127 Aug 2021
https://qonfest2021.lacl.fr/concur21.php

Publication series

NameLIPIcs - Leibniz International Proceedings in Informatics
Volume203
ISSN (Electronic)1868-8969

Conference

Conference32nd International Conference on Concurrency Theory
Abbreviated titleCONCUR 2021
Country/TerritoryFrance
CityParis
Period23/08/2127/08/21
Internet address

Keywords

  • Markov decision processe
  • Strategy complexity
  • Mean payoff

Fingerprint

Dive into the research topics of 'Strategy Complexity of Mean Payoff, Total Payoff and Point Payoff Objectives in Countable MDPs'. Together they form a unique fingerprint.

Cite this