Strategy Complexity of Limsup and Liminf Threshold Objectives in Countable MDPs, with Applications to Optimal Expected Payoffs

Richard Mayr, Eric Munday

We study Markov decision processes (MDPs) with a countably infinite number of states. The $\mathrm{limsup}$ (resp. $\mathrm{liminf}$) threshold objective is to maximize the probability that the $\…