Publication Details

Approximate Policy Iteration for Markov Decision Processes via Quantitative Adaptive Aggregations

ABATE Alessandro, ČEŠKA Milan and KWIATKOWSKA Marta. Approximate Policy Iteration for Markov Decision Processes via Quantitative Adaptive Aggregations. In: Proceedings of 14th International Symposium on Automated Technology for Verification and Analysis. Lecture Notes in Computer Science, vol. 9938. Heidelberg: Springer Verlag, 2016, pp. 13-31. ISBN 978-3-319-46519-7. Available from: http://link.springer.com/chapter/10.1007%2F978-3-319-46520-3_2
Czech title
Kvantitativní adaptivních agregace pro MDP
Type
conference paper
Language
english
Authors
Abate Alessandro (UOx)
Češka Milan, doc. RNDr., Ph.D. (DITS FIT BUT)
Kwiatkowska Marta (UOx)
URL
Keywords

Markov Decision Process, Policy Interaction, Approximation, Adaptive aggregation  

Abstract

We consider the problem of finding an optimal policy in a Markov decision process that maximises the expected discounted sum of rewards over an infinite time horizon. Since the explicit iterative dynamical programming scheme does not scale when increasing the dimension of the state space, a number of approximate methods have been developed. These are typically based on value or policy iteration, enabling further speedups through lumped and distributed updates, or by employing succinct representations of the value functions. However, none of the existing approximate techniques provides general, explicit and tunable bounds on the approximation error, a problem particularly relevant when the level of accuracy affects the optimality of the policy. In this paper we propose a new approximate policy iteration scheme that mitigates the state-space explosion problem by adaptive state-space aggregation, at the same time providing rigorous and explicit error bounds that can be used to control the optimality level of the obtained policy. We evaluate the new approach on a case study, demonstrating evidence that the state-space reduction results in considerable acceleration of the policy iteration scheme, while being able to meet the required level of precision.

Published
2016
Pages
13-31
Proceedings
Proceedings of 14th International Symposium on Automated Technology for Verification and Analysis
Series
Lecture Notes in Computer Science
Volume
9938
Conference
14th International Symposium on Automated Technology for Verification and Analysis, Chiba, JP
ISBN
978-3-319-46519-7
Publisher
Springer Verlag
Place
Heidelberg, DE
DOI
UT WoS
000389808100002
EID Scopus
BibTeX
@INPROCEEDINGS{FITPUB11211,
   author = "Alessandro Abate and Milan \v{C}e\v{s}ka and Marta Kwiatkowska",
   title = "Approximate Policy Iteration for Markov Decision Processes via Quantitative Adaptive Aggregations",
   pages = "13--31",
   booktitle = "Proceedings of 14th International Symposium on Automated Technology for Verification and Analysis",
   series = "Lecture Notes in Computer Science",
   volume = 9938,
   year = 2016,
   location = "Heidelberg, DE",
   publisher = "Springer Verlag",
   ISBN = "978-3-319-46519-7",
   doi = "10.1007/978-3-319-46520-3\_2",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/11211"
}
Back to top