Finite optimal control for time-bounded reachability in CTMDPs and continuous-time Markov games
From MaRDI portal
Publication:766176
DOI10.1007/S00236-011-0140-0zbMATH Open1242.91016arXiv1004.4005OpenAlexW2020204292MaRDI QIDQ766176FDOQ766176
Publication date: 23 March 2012
Published in: Acta Informatica (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1004.4005
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
Markov and semi-Markov decision processes (90C40) Stochastic games, stochastic differential games (91A15) Optimal stochastic control (93E20)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Optimal time-abstract schedulers for CTMDPs and continuous-time Markov games
- Efficient computation of time-bounded reachability probabilities in uniform continuous-time Markov decision processes
- A Characterization of Meaningful Schedulers for Continuous-Time Markov Decision Processes
- Model Checking Interactive Markov Chains
- Delayed Nondeterminism in Continuous-Time Markov Decision Processes
- Title not available (Why is that?)
- Zero-sum games for continuous-time Markov chains with unbounded transition and average payoff rates
- Finite State Continuous Time Markov Decision Processes with a Finite Planning Horizon
- Numerical analysis of continuous time Markov decision processes over finite horizons
- Interactive Markov chains. And the quest for quantified quality
- Finite optimal control for time-bounded reachability in CTMDPs and continuous-time Markov games
- Zero-sum continuous-time Markov games with unbounded transition and discounted payoff rates
- Continuous Time Discounted Jump Markov Decision Processes: A Discrete-Event Approach
- Optimality of the shortest line discipline
- Model-checking continuous-time Markov chains
- Zero-sum games for continuous-time jump Markov processes in Polish spaces: discounted payoffs
- Time-Bounded Model Checking of Infinite-State Continuous-Time Markov Chains
- Title not available (Why is that?)
Cited In (6)
- Efficient approximation of optimal control for continuous-time Markov games
- Model checking for performability
- 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
- Approximate Time Bounded Reachability for CTMCs and CTMDPs: A Lyapunov Approach
- A modest Markov automata tutorial
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)
