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

Richard Mayr; Eric Munday

doi:10.4230/LIPIcs.CONCUR.2021.12

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

Research output: Chapter in Book/Report/Conference proceeding › Conference 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 language	English
Title of host publication	32nd International Conference on Concurrency Theory (CONCUR 2021)
Editors	Serge Haddad, Daniele Varacca
Publisher	Schloss Dagstuhl - Leibniz-Zentrum für Informatik
Pages	12:1-12:15
Number of pages	15
ISBN (Electronic)	978-3-95977-203-7
DOIs	https://doi.org/10.4230/LIPIcs.CONCUR.2021.12
Publication status	Published - 13 Aug 2021
Event	32nd International Conference on Concurrency Theory - Online, Paris, France Duration: 23 Aug 2021 → 27 Aug 2021 https://qonfest2021.lacl.fr/concur21.php

Publication series

Name	LIPIcs - Leibniz International Proceedings in Informatics
Volume	203
ISSN (Electronic)	1868-8969

Conference

Conference	32nd International Conference on Concurrency Theory
Abbreviated title	CONCUR 2021
Country/Territory	France
City	Paris
Period	23/08/21 → 27/08/21
Internet address	https://qonfest2021.lacl.fr/concur21.php

Keywords / Materials (for Non-textual outputs)

Markov decision processe
Strategy complexity
Mean payoff

Access to Document

10.4230/LIPIcs.CONCUR.2021.12Licence: Creative Commons: Attribution (CC-BY)

Strategy Complexity_MAYR_DoA14072021_VOR_CC-BYFinal published version, 3.89 MBLicence: Creative Commons: Attribution (CC-BY)

https://drops.dagstuhl.de/opus/volltexte/2021/14389Licence: Creative Commons: Attribution (CC-BY)

1 Article

Strategy Complexity of Point Payoff, Mean Payoff and Total Payoff Objectives in Countable MDPs
Mayr, R. & Munday, E., 6 Mar 2023, In: Logical Methods in Computer Science. 19, 1, p. 1-43
Research output: Contribution to journal › Article › peer-review

Open Access
File

Cite this

Mayr, R., & Munday, E. (2021). Strategy Complexity of Mean Payoff, Total Payoff and Point Payoff Objectives in Countable MDPs. In S. Haddad, & D. Varacca (Eds.), 32nd International Conference on Concurrency Theory (CONCUR 2021) (pp. 12:1-12:15). (LIPIcs - Leibniz International Proceedings in Informatics; Vol. 203). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.CONCUR.2021.12

@inproceedings{c35772fcda3c4e1ab6a73fccb82cd67f,

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

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

keywords = "Markov decision processe, Strategy complexity, Mean payoff",

author = "Richard Mayr and Eric Munday",

year = "2021",

month = aug,

day = "13",

doi = "10.4230/LIPIcs.CONCUR.2021.12",

language = "English",

series = "LIPIcs - Leibniz International Proceedings in Informatics",

publisher = "Schloss Dagstuhl - Leibniz-Zentrum f{\"u}r Informatik",

pages = "12:1--12:15",

editor = "Serge Haddad and Daniele Varacca",

booktitle = "32nd International Conference on Concurrency Theory (CONCUR 2021)",

note = "32nd International Conference on Concurrency Theory, CONCUR 2021 ; Conference date: 23-08-2021 Through 27-08-2021",

url = "https://qonfest2021.lacl.fr/concur21.php",

}

Mayr, R & Munday, E 2021, Strategy Complexity of Mean Payoff, Total Payoff and Point Payoff Objectives in Countable MDPs. in S Haddad & D Varacca (eds), 32nd International Conference on Concurrency Theory (CONCUR 2021). LIPIcs - Leibniz International Proceedings in Informatics, vol. 203, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, pp. 12:1-12:15, 32nd International Conference on Concurrency Theory, Paris, France, 23/08/21. https://doi.org/10.4230/LIPIcs.CONCUR.2021.12

Strategy Complexity of Mean Payoff, Total Payoff and Point Payoff Objectives in Countable MDPs. / Mayr, Richard; Munday, Eric.
32nd International Conference on Concurrency Theory (CONCUR 2021). ed. / Serge Haddad; Daniele Varacca. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. p. 12:1-12:15 (LIPIcs - Leibniz International Proceedings in Informatics; Vol. 203).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

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

AU - Mayr, Richard

AU - Munday, Eric

PY - 2021/8/13

Y1 - 2021/8/13

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

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

KW - Markov decision processe

KW - Strategy complexity

KW - Mean payoff

U2 - 10.4230/LIPIcs.CONCUR.2021.12

DO - 10.4230/LIPIcs.CONCUR.2021.12

M3 - Conference contribution

T3 - LIPIcs - Leibniz International Proceedings in Informatics

SP - 12:1-12:15

BT - 32nd International Conference on Concurrency Theory (CONCUR 2021)

A2 - Haddad, Serge

A2 - Varacca, Daniele

PB - Schloss Dagstuhl - Leibniz-Zentrum für Informatik

T2 - 32nd International Conference on Concurrency Theory

Y2 - 23 August 2021 through 27 August 2021

ER -

Mayr R, Munday E. Strategy Complexity of Mean Payoff, Total Payoff and Point Payoff Objectives in Countable MDPs. In Haddad S, Varacca D, editors, 32nd International Conference on Concurrency Theory (CONCUR 2021). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. 2021. p. 12:1-12:15. (LIPIcs - Leibniz International Proceedings in Informatics). doi: 10.4230/LIPIcs.CONCUR.2021.12

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

Abstract

Publication series

Conference

Keywords / Materials (for Non-textual outputs)

Access to Document

Fingerprint

Research output

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

Cite this