| Title: |
Reachability and safety objectives in Markov decision processes on long but finite horizons |
| Authors: |
Ashkenazi-Golan, Galit, Flesch, János, Predtetchinski, Arkadi, Solan, Eilon |
| Publication Year: |
2019 |
| Collection: |
Mathematics |
| Subject Terms: |
Mathematics - Optimization and Control, C73 |
| More Details: |
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 $\sigma$ overtakes another strategy $\sigma'$, if the probability of reaching the target state within horizon $t$ is larger under $\sigma$ than under $\sigma'$, for all sufficiently large $t\in\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. |
| Document Type: |
Working Paper |
| Access URL: |
http://arxiv.org/abs/1911.05578 |
| Accession Number: |
edsarx.1911.05578 |
| Database: |
arXiv |
