2008-07-09-isaza08a.md

title	abstract	layout	series	publisher	issn	id	month	tex_title	firstpage	lastpage	page	order	cycles	bibtex_editor	editor	bibtex_author	author	date	note	address	container-title	volume	genre	issued	pdf	extras
Speeding up planning in Markov decision processes via automatically constructed abstractions	In this paper, we consider planning in stochastic shortest path (SSP) problems, a subclass of Markov Decision Problems (MDP). We focus on medium-size problems whose state space can be fully enumerated. This problem has numerous important applications, such as navigation and planning under uncertainty. We propose a new approach for constructing a multi-level hierarchy of progressively simpler abstractions of the original problem. Once computed, the hierarchy can be used to speed up planning by first finding a policy for the most abstract level and then recursively refining it into a solution to the original problem. This approach is fully automated and delivers a speed-up of two orders of magnitude over a state-of-the-art MDP solver on sample problems while returning near-optimal solutions. We also prove theoretical bounds on the loss of solution optimality resulting from the use of abstractions.	inproceedings	Proceedings of Machine Learning Research	PMLR	2640-3498	isaza08a	0	Speeding up planning in Markov decision processes via automatically constructed abstractions	306	314	306-314	306	false	McAllester, David A. and Myllym{"a}ki, Petri	given family David A. McAllester given family Petri Myllymäki	Isaza, Alejandro and Szepesv\'{a}ri, Csaba and Bulitko, Vadim and Greiner, Russell	given family Alejandro Isaza given family Csaba Szepesvári given family Vadim Bulitko given family Russell Greiner	2008-07-09	Reissued by PMLR on 30 October 2024.		Proceedings of the 24th Conference on Uncertainty in Artificial Intelligence	R6	inproceedings	date-parts 2008 7 9	http://proceedings.mlr.press/r6/isaza08a/isaza08a.pdf