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 / Description of output

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
Number of pages15
ISBN (Electronic)978-3-95977-203-7
Publication statusPublished - 13 Aug 2021
Event32nd International Conference on Concurrency Theory - Online, Paris, France
Duration: 23 Aug 202127 Aug 2021

Publication series

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


Conference32nd International Conference on Concurrency Theory
Abbreviated titleCONCUR 2021
Internet address

Keywords / Materials (for Non-textual outputs)

  • Markov decision processe
  • Strategy complexity
  • Mean payoff

Cite this