Strategy complexity of limsup and liminf threshold objectives in countable MDPs, with applications to optimal expected payoffs

Richard Mayr () and Eric Munday ()
Additional contact information
Richard Mayr: University of Edinburgh
Eric Munday: University of Edinburgh

Decisions in Economics and Finance, 2025, vol. 48, issue 1, No 28, 643-692

Abstract: Abstract We study Markov decision processes with a countably infinite number of states. The $$\limsup $$ lim sup (resp. $$\liminf $$ lim inf ) threshold objective is to maximize the probability that the $$\limsup $$ lim sup (resp. $$\liminf $$ lim inf ) of the infinite sequence of directly seen rewards is non-negative. We establish the complete picture of the strategy complexity of these objectives, i.e., the upper and lower bounds on the memory required by $$\varepsilon $$ ε -optimal (resp. optimal) strategies. We then apply these results to solve two open problems from (Sudderth in Decis Econ Finan 43:43–54, 2020) about the strategy complexity of optimal strategies for the expected $$\limsup $$ lim sup (resp. $$\liminf $$ lim inf ) payoff.

Keywords: Gambling theory; Markov decision processes; Strategy complexity; Markov strategy; Lim sup; Lim inf; 90C40; 91A60 (search for similar items in EconPapers)
JEL-codes: C44 C73 C81 (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10203-024-00485-7 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:decfin:v:48:y:2025:i:1:d:10.1007_s10203-024-00485-7

Ordering information: This journal article can be ordered from
http://www.springer. ... ry/journal/10203/PS2

DOI: 10.1007/s10203-024-00485-7

Access Statistics for this article

Decisions in Economics and Finance is currently edited by Paolo Ghirardato

More articles in Decisions in Economics and Finance from Springer, Associazione per la Matematica
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().