---
title: "Solving Factored MDPs via Non-Homogeneous Partitioning"
authors:
  - "Kee-Eung Kim"
  - "Thomas L. Dean"
doi: ""
url: "https://ijcai.org/proceedings/2001/94"
pdf: "https://ijcai.org/proceedings/2001/0094.pdf"
venue: "Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence"
year: 2001
pages: "683-688"
track: ""
keywords:
---

# Solving Factored MDPs via Non-Homogeneous Partitioning

Kee-Eung Kim, Thomas L. Dean

*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.