{
  "id": "1911.05578",
  "version": "v1",
  "published": "2019-11-13T16:17:40.000Z",
  "updated": "2019-11-13T16:17:40.000Z",
  "title": "Reachability and safety objectives in Markov decision processes on long but finite horizons",
  "authors": [
    "Galit Ashkenazi-Golan",
    "János Flesch",
    "Arkadi Predtetchinski",
    "Eilon Solan"
  ],
  "categories": [
    "math.OC"
  ],
  "abstract": "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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2019-11-13T16:17:40.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "C73"
    ],
    "keywords": [
      "markov decision processes",
      "finite horizons",
      "safety objective",
      "reachability",
      "decision makers goal"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}