文章基本信息

标题：Efficient Approximation of Optimal Control for Continuous-Time Markov Games
本地全文：下载
作者：John Fearnley ; Markus Rabe ; Sven Schewe 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2011
卷号：13
页码：399-410
DOI：10.4230/LIPIcs.FSTTCS.2011.399
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：We study the time-bounded reachability problem for continuous time Markov decision processes (CTMDPs) and games (CTMGs). Existing techniques for this problem use discretization techniques to break time into discrete intervals, and optimal control is approximated for each interval separately. Current techniques provide an accuracy of O(\epsilon^2) on each interval, which leads to an infeasibly large number of intervals. We propose a sequence of approximations that achieve accuracies of O(\epsilon^3), O(\epsilon^4), and O(\epsilon^5), that allow us to drastically reduce the number of intervals that are considered. For CTMDPs, the resulting algorithms are comparable to the heuristic approach given by Buckholz and Schulz, while also being theoretically justified. All of our results generalise to CTMGs, where our results yield the first practically implementable algorithms for this problem. We also provide positional strategies for both players that achieve similar error bounds.
关键词：Continuous time Markov decision processes and games; discretisation