Finite optimal control for time-bounded reachability in CTMDPs and continuous-time Markov games

DOI10.1007/S00236-011-0140-0MaRDI QIDQ766176zbMATH OpenOpenAlexFDO

Authors Markus Rabe, Sven Schewe

Publication date 23 March 2012

Published in Acta Informatica (Search for Journal in Brave)

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

zbMATH Keywords

optimal schedulingcontinuous time Markov decision processzero-sum Markov game

Mathematics Subject Classification ID

Markov and semi-Markov decision processes (90C40) Stochastic games, stochastic differential games (91A15) Optimal stochastic control (93E20)

Abstract: We establish the existence of optimal scheduling strategies for time-bounded reachability in continuous-time Markov decision processes, and of co-optimal strategies for continuous-time Markov games. Furthermore, we show that optimal control does not only exist, but has a surprisingly simple structure: The optimal schedulers from our proofs are deterministic and timed-positional, and the bounded time can be divided into a finite number of intervals, in which the optimal strategies are positional. That is, we demonstrate the existence of finite optimal control. Finally, we show that these pleasant properties of Markov decision processes extend to the more general class of continuous-time Markov games, and that both early and late schedulers show this behaviour.

Recommendations

• Optimal time-abstract schedulers for CTMDPs and Markov games
• Optimal time-abstract schedulers for CTMDPs and continuous-time Markov games
• Continuous-time stochastic games with time-bounded reachability
• Continuous-time stochastic games with time-bounded reachability
• Efficient approximation of optimal control for continuous-time Markov games

Cites work

• scientific article; zbMATH DE number 3126094 (Why is no real title available?)
• scientific article; zbMATH DE number 1361121 (Why is no real title available?)
• scientific article; zbMATH DE number 700091 (Why is no real title available?)
• scientific article; zbMATH DE number 729460 (Why is no real title available?)
• A Characterization of Meaningful Schedulers for Continuous-Time Markov Decision Processes
• Continuous Time Discounted Jump Markov Decision Processes: A Discrete-Event Approach
• Delayed Nondeterminism in Continuous-Time Markov Decision Processes
• Efficient computation of time-bounded reachability probabilities in uniform continuous-time Markov decision processes
• Finite State Continuous Time Markov Decision Processes with a Finite Planning Horizon
• Finite optimal control for time-bounded reachability in CTMDPs and continuous-time Markov games
• Interactive Markov chains. And the quest for quantified quality
• Model Checking Interactive Markov Chains
• Model-checking continuous-time Markov chains
• Numerical analysis of continuous time Markov decision processes over finite horizons
• Optimal time-abstract schedulers for CTMDPs and continuous-time Markov games
• Optimality of the shortest line discipline
• Time-bounded model checking of infinite-state continuous-time Markov chains
• Zero-sum continuous-time Markov games with unbounded transition and discounted payoff rates
• Zero-sum games for continuous-time Markov chains with unbounded transition and average payoff rates
• Zero-sum games for continuous-time jump Markov processes in Polish spaces: discounted payoffs

Cited in

(14)

• Continuous-time stochastic games with time-bounded reachability
• Playing optimally on timed automata with random delays
• Continuous-time stochastic games with time-bounded reachability
• Reachability in continuous-time Markov reward decision processes
• Maximal cost-bounded reachability probability on continuous-time Markov decision processes
• Approximate Time Bounded Reachability for CTMCs and CTMDPs: A Lyapunov Approach
• Optimal time-abstract schedulers for CTMDPs and Markov games
• A modest Markov automata tutorial
• Finite optimal control for time-bounded reachability in CTMDPs and continuous-time Markov games
• A uniformization-based algorithm for continuous-time stochastic games model checking
• Efficient approximation of optimal control for continuous-time Markov games
• Efficient approximation of optimal control for continuous-time Markov games
• Optimal time-abstract schedulers for CTMDPs and continuous-time Markov games
• Model checking for performability

This page was built for publication: Finite optimal control for time-bounded reachability in CTMDPs and continuous-time Markov games

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