  We study countably infinite MDPs with parity objectives, and special cases
with a bounded number of colors in the Mostowski hierarchy (including
reachability, safety, Buchi and co-Buchi).
  In finite MDPs there always exist optimal memoryless deterministic (MD)
strategies for parity objectives, but this does not generally hold for
countably infinite MDPs. In particular, optimal strategies need not exist. For
countable infinite MDPs, we provide a complete picture of the memory
requirements of optimal (resp., $\epsilon$-optimal) strategies for all
objectives in the Mostowski hierarchy. In particular, there is a strong
dichotomy between two different types of objectives. For the first type,
optimal strategies, if they exist, can be chosen MD, while for the second type
optimal strategies require infinite memory. (I.e., for all objectives in the
Mostowski hierarchy, if finite-memory randomized strategies suffice then also
MD strategies suffice.) Similarly, some objectives admit $\epsilon$-optimal
MD-strategies, while for others $\epsilon$-optimal strategies require infinite
memory. Such a dichotomy also holds for the subclass of countably infinite MDPs
that are finitely branching, though more objectives admit MD-strategies here.
