  We give polynomial-time algorithms for computing the values of Markov
decision processes (MDPs) with limsup and liminf objectives. A real-valued
reward is assigned to each state, and the value of an infinite path in the MDP
is the limsup (resp. liminf) of all rewards along the path. The value of an MDP
is the maximal expected value of an infinite path that can be achieved by
resolving the decisions of the MDP. Using our result on MDPs, we show that
turn-based stochastic games with limsup and liminf objectives can be solved in
NP \cap coNP.
