Efficient approximation of optimal control for continuous-time Markov games



Fearnley, J, Rabe, MN, Schewe, S ORCID: 0000-0002-9093-9518 and Zhang, L
(2016) Efficient approximation of optimal control for continuous-time Markov games. INFORMATION AND COMPUTATION, 247. 106 - 129.

[img] Text
app.pdf - Accepted Version

Download (489kB)

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 partition time into discrete intervals of size ε, and optimal control is approximated for each interval separately. Current techniques provide an accuracy of on each interval, which leads to an infeasibly large number of intervals. We propose a sequence of approximations that achieve accuracies of , , and , 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 Buchholz 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 memoryless strategies for both players that achieve similar error bounds.

Item Type: Article
Uncontrolled Keywords: Continuous time Markov decision processes and games, Optimal control, Discretisation
Depositing User: Symplectic Admin
Date Deposited: 22 Feb 2017 10:41
Last Modified: 19 Oct 2021 11:13
DOI: 10.1016/j.ic.2015.12.002
Related URLs:
URI: https://livrepository.liverpool.ac.uk/id/eprint/3005458