Publication Type
Conference Proceeding Article
Version
publishedVersion
Publication Date
11-2010
Abstract
Model minimization in Factored Markov Decision Processes (FMDPs) is concerned with finding the most compact partition of the state space such that all states in the same block are action-equivalent. This is an important problem because it can potentially transform a large FMDP into an equivalent but much smaller one, whose solution can be readily used to solve the original model. Previous model minimization algorithms are iterative in nature, making opaque the relationship between the input model and the output partition. We demonstrate that given a set of well-defined concepts and operations on partitions, we can express the model minimization problem in an analytic fashion. The theoretical results developed can be readily applied to solving problems such as estimating the size of the minimum partition, refining existing algorithms, and so on. Copyright © 2010, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.
Discipline
Computer Sciences
Publication
24th AAAI Conference on Artificial Intelligence
Volume
2
First Page
1077
Last Page
1082
ISBN
9781577354659
Publisher
The AAAI Press
City or Country
Atlanta, GA, USA
Citation
Guo W. and Tze-Yun LEONG.
An Analytic Characterization of Model Minimization in Factored Markov Decision Processes. (2010). 24th AAAI Conference on Artificial Intelligence. 2, 1077-1082.
Available at: https://ink.library.smu.edu.sg/sis_research/2989
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.