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

Abstract We study Markov decision processes with a countably infinite number of states. The $$\limsup $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mo>lim sup</mml:mo> </mml:math> (resp. $$\liminf $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mo>lim inf</mml:mo> </mml:math> ) threshold objective is to maximize the probability that the $$\limsup $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mo>lim sup</mml:mo> </mml:math> (resp. $$\liminf $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mo>lim inf</mml:mo> </mml:math> ) 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 $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>ε</mml:mi> </mml:math> -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 $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mo>lim sup</mml:mo> </mml:math> (resp. $$\liminf $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mo>lim inf</mml:mo> </mml:math> ) payoff.