Institutional Repository
| Efficient approximation of optimal control for continuous-time Markov games | |
| Fearnley, J; Rabe, MN; Schewe, S; Zhang, LJ | |
| 2016 | |
| Source | INFORMATION AND COMPUTATION
 |
| ISSN | 0890-5401 |
| Volume | 247Pages:106-129 |
| English 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 epsilon, 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 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. (C) 2015 Elsevier Inc. All rights reserved.; 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 epsilon, 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 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. (C) 2015 Elsevier Inc. All rights reserved. |
| Indexed Type | SCI |
| Keyword | Continuous Time Markov Decision Processes And Games Optimal Control Discretisation |
| Department | Univ Liverpool, Dept Comp Sci, Liverpool, Merseyside, England. Univ Calif Berkeley, Elect Engn & Comp Sci, Berkeley, CA 94720 USA. Chinese Acad Sci, Inst Software, State Key Lab Comp Sci, Beijing 100864, Peoples R China. |
| Language | 英语 |
| WOS ID | WOS:000372136400006 |
| Citation statistics | |
| Content Type | 期刊论文 |
| URI | http://ir.iscas.ac.cn/handle/311060/17337 |
| Collection | 中国科学院软件研究所 |
| Recommended Citation GB/T 7714 | Fearnley, J,Rabe, MN,Schewe, S,et al. Efficient approximation of optimal control for continuous-time Markov games[J]. INFORMATION AND COMPUTATION,2016,247:106-129. |
| APA | Fearnley, J,Rabe, MN,Schewe, S,&Zhang, LJ.(2016).Efficient approximation of optimal control for continuous-time Markov games.INFORMATION AND COMPUTATION,247,106-129. |
| MLA | Fearnley, J,et al."Efficient approximation of optimal control for continuous-time Markov games".INFORMATION AND COMPUTATION 247(2016):106-129. |
| Files in This Item: | ||||||
| File Name/Size | DocType | Version | Access | License | ||
| 1-s2.0-S089054011500（671KB） | 开放获取 | License | Application Full Text | |||
Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.
Edit Comment