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

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 42 references that are in the map.
- First posted on arXiv 10 Mar 2022.

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

- [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)
- [Qualitative Analysis of VASS-Induced MDPs](https://mlsanity.com/paper/1512.08824/) (2015)

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

- [More for Less: Safe Policy Improvement With Stronger Performance Guarantees](https://mlsanity.com/paper/2305.07958/) (2023)
- [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)

## 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. Mean payoff (the sequence of the sums of all rewards so far, divided by the number of steps), and 3. Total payoff (the sequence of the sums of all rewards so far). 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.