Efficient approximation of optimal control for continuous-time Markov games

ISCAS OpenIR

	Efficient approximation of optimal control for continuous-time Markov games
	Fearnley, J; Rabe, MN; Schewe, S; Zhang, LJ
	2016
发表期刊	INFORMATION AND COMPUTATION
ISSN	0890-5401
卷号	247 页码:106-129
摘要	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
关键词	Continuous Time Markov Decision Processes And Games Optimal Control Discretisation
部门归属	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.
语种	英语
WOS记录号	WOS:000372136400006
引用统计
内容类型	期刊论文
URI标识	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.

条目包含的文件
文件名称/大小	文献类型	版本类型	开放类型	使用许可
1-s2.0-S089054011500（671KB）			开放获取	使用许可	请求全文