Efficient approximation of optimal control for continuous-time Markov games
文献类型：期刊论文
| 作者 | Fearnley, J ; Rabe, MN ; Schewe, S ; Zhang, LJ |
| 刊名 | INFORMATION AND COMPUTATION
 |
| 出版日期 | 2016 |
| 卷号 | 247页码:106-129 |
| 关键词 | Continuous time Markov decision processes and games Optimal control Discretisation |
| ISSN号 | 0890-5401 |
| 中文摘要 | 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. |
| 收录类别 | SCI |
| 语种 | 英语 |
| WOS记录号 | WOS:000372136400006 |
| 公开日期 | 2016-12-09 |
| 源URL | [http://ir.iscas.ac.cn/handle/311060/17337]  |
| 专题 | 软件研究所_软件所图书馆_期刊论文 |
| 推荐引用方式 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. |
入库方式： OAI收割
来源：软件研究所
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。