# Strategy Complexity of Mean Payoff, Total Payoff and Point Payoff Objectives in Countable MDPs

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 5 of its 25 references that are in the map.
- First posted on arXiv 1 Jul 2021.

## Builds on (most cited first, 5 of 5)

- [Reachability and safety objectives in Markov decision processes on long but finite horizons](https://mlsanity.com/paper/1911.05578/) (2019)
- [Strategy Complexity of Parity Objectives in Countable MDPs](https://mlsanity.com/paper/2007.05065/) (2020)
- [Parity Objectives in Countable MDPs](https://mlsanity.com/paper/1704.04490/) (2017)
- [B"uchi Objectives in Countable MDPs](https://mlsanity.com/paper/1904.11573/) (2019)
- [Transience in Countable MDPs](https://mlsanity.com/paper/2012.13739/) (2020)

## Abstract (arXiv)

We study countably infinite Markov decision processes (MDPs) with real-valued transition rewards. Every infinite run induces the following sequences of payoffs: 1. Point payoff (the sequence of directly seen transition rewards), 2. Total payoff (the sequence of the sums of all rewards so far), and 3. Mean payoff. For each payoff type, the objective is to maximize the probability that the liminf is non-negative. We establish the complete picture of the strategy complexity of these objectives, i.e., how much memory is necessary and sufficient for varepsilon-optimal (resp. optimal) strategies. Some cases can be won with memoryless deterministic strategies, while others require a step counter, a reward counter, or both.