Optimal continuous time Markov decisions

DOI10.1007/978-3-319-24953-7_12zbMATH Open1471.68132arXiv1507.02876OpenAlexW2262106677MaRDI QIDQ3460554FDOQ3460554

Authors: Yuliya Butkova, Hassan Hatefi, Holger Hermanns, Jan Krčál 

Publication date: 8 January 2016

Published in: Automated Technology for Verification and Analysis (Search for Journal in Brave)

Abstract: In the context of Markov decision processes running in continuous time, one of the most intriguing challenges is the efficient approximation of finite horizon reachability objectives. A multitude of sophisticated model checking algorithms have been proposed for this. However, no proper benchmarking has been performed thus far. This paper presents a novel and yet simple solution: an algorithm originally developed for a restricted subclass of models and a subclass of schedulers can be twisted so as to become competitive with the more sophisticated algorithms in full generality. As the second main contribution, we perform a comparative evaluation of the core algorithmic concepts on an extensive set of benchmarks varying over all key parameters: model size, amount of non-determinism, time horizon, and precision.

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

Recommendations

• Reachability in continuous-time Markov reward decision processes
• Efficient approximation of optimal control for continuous-time Markov games
• Efficient approximation of optimal control for continuous-time Markov games
• Optimal decisions for continuous time Markov decision processes over finite planning horizons
• Efficient computation of time-bounded reachability probabilities in uniform continuous-time Markov decision processes

Mathematics Subject Classification ID

Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Specification and verification (program logics, model checking, etc.) (68Q60) Markov and semi-Markov decision processes (90C40)

Cited In (14)

• Pure Stationary Optimal Strategies in Markov Decision Processes
• Efficient approximation of optimal control for continuous-time Markov games
• Lumpability for uncertain continuous-time Markov chains
• Continuous-time Markov decisions based on partial exploration
• A uniformization-based algorithm for continuous-time stochastic games model checking
• Multi-objective optimization of long-run average and total rewards
• Markov automata with multiple objectives
• Title not available (Why is that?)
• Optimization of a special case of continuous-time Markov decision processes with compact action set
• Optimal Markov strategies
• Cost vs. time in stochastic games and Markov automata
• Policy Synthesis for Collective Dynamics
• A modest Markov automata tutorial
• Markov-achievable payoffs for finite-horizon decision models.

This page was built for publication: Optimal continuous time Markov decisions

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