1 Search Results for "Rabe, Markus"

Document
DOI: 10.4230/LIPIcs.FSTTCS.2011.399
Efficient Approximation of Optimal Control for Continuous-Time Markov Games

Authors: John Fearnley, Markus Rabe, Sven Schewe, and Lijun Zhang

Published in: LIPIcs, Volume 13, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011)

Abstract
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.
Cite as

John Fearnley, Markus Rabe, Sven Schewe, and Lijun Zhang. Efficient Approximation of Optimal Control for Continuous-Time Markov Games. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011). Leibniz International Proceedings in Informatics (LIPIcs), Volume 13, pp. 399-410, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{fearnley_et_al:LIPIcs.FSTTCS.2011.399,
  author =	{Fearnley, John and Rabe, Markus and Schewe, Sven and Zhang, Lijun},
  title =	{{Efficient Approximation of Optimal Control for Continuous-Time Markov Games}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011)},
  pages =	{399--410},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-34-7},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{13},
  editor =	{Chakraborty, Supratik and Kumar, Amit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2011.399},
  URN =		{urn:nbn:de:0030-drops-33547},
  doi =		{10.4230/LIPIcs.FSTTCS.2011.399},
  annote =	{Keywords: Continuous time Markov decision processes and games, discretisation}
}
  • Refine by Author
  • 1 Fearnley, John
  • 1 Rabe, Markus
  • 1 Schewe, Sven
  • 1 Zhang, Lijun

  • Refine by Classification

  • Refine by Keyword
  • 1 Continuous time Markov decision processes and games
  • 1 discretisation

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2011

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact