{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T16:53:13Z","timestamp":1753894393202,"version":"3.41.2"},"reference-count":0,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","license":[{"start":{"date-parts":[[2023,3,6]],"date-time":"2023-03-06T00:00:00Z","timestamp":1678060800000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"<jats:p>We study countably infinite Markov decision processes (MDPs) with real-valued\ntransition rewards. Every infinite run induces the following sequences of\npayoffs: 1. Point payoff (the sequence of directly seen transition rewards), 2.\nMean payoff (the sequence of the sums of all rewards so far, divided by the\nnumber of steps), and 3. Total payoff (the sequence of the sums of all rewards\nso far). For each payoff type, the objective is to maximize the probability\nthat the $\\liminf$ is non-negative. We establish the complete picture of the\nstrategy complexity of these objectives, i.e., how much memory is necessary and\nsufficient for $\\varepsilon$-optimal (resp. optimal) strategies. Some cases can\nbe won with memoryless deterministic strategies, while others require a step\ncounter, a reward counter, or both.<\/jats:p>","DOI":"10.46298\/lmcs-19(1:16)2023","type":"journal-article","created":{"date-parts":[[2023,3,6]],"date-time":"2023-03-06T08:55:23Z","timestamp":1678092923000},"source":"Crossref","is-referenced-by-count":0,"title":["Strategy Complexity of Point Payoff, Mean Payoff and Total Payoff Objectives in Countable MDPs"],"prefix":"10.46298","volume":"Volume 19, Issue 1","author":[{"given":"Richard","family":"Mayr","sequence":"first","affiliation":[]},{"given":"Eric","family":"Munday","sequence":"additional","affiliation":[]}],"member":"25203","published-online":{"date-parts":[[2023,3,6]]},"container-title":["Logical Methods in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/lmcs.episciences.org\/11029\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/lmcs.episciences.org\/11029\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,20]],"date-time":"2023-06-20T20:20:47Z","timestamp":1687292447000},"score":1,"resource":{"primary":{"URL":"https:\/\/lmcs.episciences.org\/9216"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,3,6]]},"references-count":0,"URL":"https:\/\/doi.org\/10.46298\/lmcs-19(1:16)2023","relation":{"has-preprint":[{"id-type":"arxiv","id":"2203.07079v2","asserted-by":"subject"},{"id-type":"arxiv","id":"2203.07079v1","asserted-by":"subject"}],"is-same-as":[{"id-type":"arxiv","id":"2203.07079","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.2203.07079","asserted-by":"subject"}]},"ISSN":["1860-5974"],"issn-type":[{"type":"electronic","value":"1860-5974"}],"subject":[],"published":{"date-parts":[[2023,3,6]]},"article-number":"9216"}}