# Reachability and safety objectives in Markov decision processes on long but finite horizons

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Nov 2019.

## 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)
- [Strategy Complexity of Mean Payoff, Total Payoff and Point Payoff Objectives in Countable MDPs](https://mlsanity.com/paper/2107.03287/) (2021)
- [Reductive MDPs: A Perspective Beyond Temporal Horizons](https://mlsanity.com/paper/2205.07338/) (2022)

## Abstract (arXiv)

We consider discrete-time Markov decision processes in which the decision maker is interested in long but finite horizons. First we consider reachability objective: the decision maker's goal is to reach a specific target state with the highest possible probability. Formally, strategy σ overtakes another strategy σ', if the probability of reaching the target state within horizon t is larger under σ than under σ', for all sufficiently large t∈NN. We prove that there exists a pure stationary strategy that is not overtaken by any pure strategy nor by any stationary strategy, under some condition on the transition structure and respectively under genericity. A strategy that is not overtaken by any other strategy, called an overtaking optimal strategy, does not always exist. We provide sufficient conditions for its existence. Next we consider safety objective: the decision maker's goal is to avoid a specific state with the highest possible probability. We argue that the results proven for reachability objective extend to this model. We finally discuss extensions of our results to two-player zero-sum perfect information games.