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

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 \) $\epsilon$ -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.