Efficient Approximation of Optimal Control for Markov Games

John Fearnley, Markus Rabe, Sven Schewe, Lijun Zhang

    Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

    107 Downloads (Pure)

    Abstract

    We study the time-bounded reachability problem for continuous-time Markov decision processes (CTMDPs) and games (CTMGs). Existing techniques for this problem use discretisation techniques to break time into discrete intervals, and optimal control is approximated for each interval separately. Current techniques provide an accuracy of O("2) on each interval, which leads to an infeasibly large number of intervals. We propose a sequence of approximations that achieve accuracies of O("3), O("4), and O("5), that allow us to drastically reduce the number of intervals that are considered. For CTMDPs, the performance of the resulting algorithms is comparable to the heuristic approach given by Buckholz and Schulz [6], 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.
    Original languageEnglish
    Title of host publicationProceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science
    Publication date2011
    Publication statusPublished - 2011
    Event31st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science - Mumbai, India
    Duration: 12 Dec 201114 Dec 2011
    http://fsttcs.org/archives/2011/

    Conference

    Conference31st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science
    CountryIndia
    CityMumbai
    Period12/12/201114/12/2011
    Internet address

    Cite this