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

DOI10.1007/S10957-020-01681-2MaRDI QIDQ2188953zbMATHOpenAlexFDO

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)

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

zbMATH Keywords

Markov decision processPerron-Frobenius eigenvalueovertaking optimalityreachability objectivesafety objective

Mathematics Subject Classification ID

Markov and semi-Markov decision processes (90C40)

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.

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
• Multi-weighted Markov decision processes with reachability objectives
• 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

Cites work

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

Cited in

(4)

• Strategy Complexity of Point Payoff, Mean Payoff and Total Payoff Objectives in Countable MDPs
• The linear programming approach to reach-avoid problems for Markov decision processes
• Equilibrium in two-player stochastic games with shift-invariant payoffs
• Distribution-based objectives for Markov decision processes

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)