  We study countably infinite MDPs with parity objectives. Unlike in finite
MDPs, optimal strategies need not exist, and may require infinite memory if
they do. We provide a complete picture of the exact strategy complexity of
$\varepsilon$-optimal strategies (and optimal strategies, where they exist) for
all subclasses of parity objectives in the Mostowski hierarchy. Either
MD-strategies, Markov strategies, or 1-bit Markov strategies are necessary and
sufficient, depending on the number of colors, the branching degree of the MDP,
and whether one considers $\varepsilon$-optimal or optimal strategies. In
particular, 1-bit Markov strategies are necessary and sufficient for
$\varepsilon$-optimal (resp. optimal) strategies for general parity objectives.
