Model Reduction Techniques for Computing Approximately Optimal Solutions for Markov Decision Processes

Understand

We present a method for solving implicit (factored) Markov decision processes (MDPs) with very large state spaces.

• We introduce a property of state space partitions which we call epsilon-homogeneity.
• Intuitively, an epsilon-homogeneous partition groups together states that behave approximately the same under all or some subset of policies.
• Borrowing from recent work on model minimization in computer-aided software verification, we present an algorithm that takes a factored representation of an MDP and an 0<=epsilon<=1 and computes a factored epsilon-homogeneous partition of the state space.