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

DOI10.1007/S10957-020-01681-2zbMATH Open1445.90114arXiv1911.05578OpenAlexW3027826968MaRDI QIDQ2188953FDOQ2188953

Authors: Galit Ashkenazi-Golan, Arkadi Predtetchinski, Eilon Solan, János Flesch 

Publication date: 15 June 2020

Published in: Journal of Optimization Theory and Applications (Search for Journal in Brave)

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 $sigm{a}^{\prime }$, if the probability of reaching the target state within horizon $t$ is larger under $sigma$ than under $sigm{a}^{\prime }$, for all sufficiently large $tinNN$. 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.

Full work available at URL: https://arxiv.org/abs/1911.05578

Recommendations

• Reachability in continuous-time Markov reward decision processes
• Reachability in Recursive Markov Decision Processes
• Reachability in recursive Markov decision processes
• Reachability analysis of uncertain systems using bounded-parameter Markov decision processes
• scientific article
• Maximal cost-bounded reachability probability on continuous-time Markov decision processes
• On reachability and safety in infinite-state systems
• Control of continuous-time Markov chains with safety constraints
• On the Complexity of Reachability in Parametric Markov Decision Processes
• Controlled Markov Processes With Safety State Constraints

zbMATH Keywords

Markov decision processPerron-Frobenius eigenvalueovertaking optimalityreachability objectivesafety objective

Mathematics Subject Classification ID

Markov and semi-Markov decision processes (90C40)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Stochastic Games
• Turnpike phenomenon and infinite horizon optimal control
• Turnpike properties in the calculus of variations and optimal control
• Title not available (Why is that?)
• Continuous-time Markov decision processes. Theory and applications
• A survey of stochastic \(\omega \)-regular games
• Title not available (Why is that?)
• Discrete Dynamic Programming
• On quantitative convergence to quasi-stationarity
• A counterexample on overtaking optimality
• Variations on the Stochastic Shortest Path Problem
• Criteria of optimality in the infinite-time optimal control problem
• Overtaking and Almost-Sure Optimality for Infinite Horizon Markov Decision Processes
• Computer aided synthesis: a game-theoretic approach
• On equilibria in quantitative games with reachability/safety objectives
• Optimal choice for finite and infinite horizons
• Percentile queries in multi-dimensional Markov decision processes
• Sporadic overtaking optimality in Markov decision problems
• Usual and stochastic tail orders between hitting times for two Markov chains

Cited In (2)

• Strategy Complexity of Point Payoff, Mean Payoff and Total Payoff Objectives in Countable MDPs
• Equilibrium in two-player stochastic games with shift-invariant payoffs

This page was built for publication: Reachability and safety objectives in Markov decision processes on long but finite horizons

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2188953)