License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CONCUR.2021.12
URN: urn:nbn:de:0030-drops-143893
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14389/
Go to the corresponding LIPIcs Volume Portal

Mayr, Richard ; Munday, Eric

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

pdf-format:
LIPIcs-CONCUR-2021-12.pdf (0.7 MB)

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 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.

BibTeX - Entry

@InProceedings{mayr_et_al:LIPIcs.CONCUR.2021.12,
  author =	{Mayr, Richard and Munday, Eric},
  title =	{{Strategy Complexity of Mean Payoff, Total Payoff and Point Payoff Objectives in Countable MDPs}},
  booktitle =	{32nd International Conference on Concurrency Theory (CONCUR 2021)},
  pages =	{12:1--12:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-203-7},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{203},
  editor =	{Haddad, Serge and Varacca, Daniele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/14389},
  URN =		{urn:nbn:de:0030-drops-143893},
  doi =		{10.4230/LIPIcs.CONCUR.2021.12},
  annote =	{Keywords: Markov decision processes, Strategy complexity, Mean payoff}
}

Keywords: Markov decision processes, Strategy complexity, Mean payoff
Collection: 32nd International Conference on Concurrency Theory (CONCUR 2021)
Issue Date: 2021
Date of publication: 13.08.2021

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI