# Strategy Complexity of Parity Objectives in Countable MDPs

arXiv: https://arxiv.org/abs/2007.05065 · HTML: https://mlsanity.com/paper/2007.05065/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Jul 2020.

## Built on by (most cited first, 3 of 3)

- [Strategy Complexity of Point Payoff, Mean Payoff and Total Payoff Objectives in Countable MDPs](https://mlsanity.com/paper/2203.07079/) (2022)
- [Mixing Any Cocktail with Limited Ingredients: On the Structure of Payoff Sets in Multi-Objective POMDPs and its Impact on Randomised Strategies](https://mlsanity.com/paper/2502.18296/) (2025)
- [Strategy Complexity of Mean Payoff, Total Payoff and Point Payoff Objectives in Countable MDPs](https://mlsanity.com/paper/2107.03287/) (2021)

## Abstract (arXiv)

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.