1 Search Results for "Munday, Eric"

Document
DOI: 10.4230/LIPIcs.CONCUR.2021.12
Strategy Complexity of Mean Payoff, Total Payoff and Point Payoff Objectives in Countable MDPs

Authors: Richard Mayr and Eric Munday

Published in: LIPIcs, Volume 203, 32nd International Conference on Concurrency Theory (CONCUR 2021)

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

Richard Mayr and Eric Munday. Strategy Complexity of Mean Payoff, Total Payoff and Point Payoff Objectives in Countable MDPs. In 32nd International Conference on Concurrency Theory (CONCUR 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 203, pp. 12:1-12:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2021.12},
  URN =		{urn:nbn:de:0030-drops-143893},
  doi =		{10.4230/LIPIcs.CONCUR.2021.12},
  annote =	{Keywords: Markov decision processes, Strategy complexity, Mean payoff}
}
  • Refine by Author
  • 1 Mayr, Richard
  • 1 Munday, Eric

  • Refine by Classification
  • 1 Mathematics of computing → Probability and statistics
  • 1 Theory of computation → Random walks and Markov chains

  • Refine by Keyword
  • 1 Markov decision processes
  • 1 Mean payoff
  • 1 Strategy complexity

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2021

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact