Solving Factored MDPs via Non-Homogeneous Partitioning
Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence. Pages 683-688.
Abstract
This paper describes an algorithm for solving large state-space MDPs (represented as factored MDPs) using search by successive refinement in the space of non-homogeneous partitions. Homogeneity is defined in terms of bisimulation and reward equivalence within blocks of a partition. Since homogeneous partitions that define equivalent reduced state-space MDPs can have a large number of blocks, we relax the requirement of homogeneity. The algorithm constructs approximate aggregate MDPs from non-homogeneous partitions, solves the aggregate MDPs exactly, and then uses the resulting value functions as part of a heuristic in refining the current best non-homogeneous partition. We outline the theory motivating the use of this heuristic and present empirical results and comparisons.
@inproceedings{ijcai2001p94,
title = {Solving Factored MDPs via Non-Homogeneous Partitioning},
author = {Kim, Kee-Eung and Dean, Thomas L.},
booktitle = {Proceedings of the Seventeenth International Joint Conference on
Artificial Intelligence, {IJCAI-01}},
publisher = {International Joint Conferences on Artificial Intelligence},
pages = {683--688},
year = {2001},
url = {https://ijcai.org/proceedings/2001/94},
}
TY - CPAPER TI - Solving Factored MDPs via Non-Homogeneous Partitioning AU - Kim, Kee-Eung AU - Dean, Thomas L. T2 - Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence, IJCAI-01 PB - International Joint Conferences on Artificial Intelligence PY - 2001 SP - 683 EP - 688 UR - https://ijcai.org/proceedings/2001/94 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
