  The combinatorial explosion that plagues planning and reinforcement learning
(RL) algorithms can be moderated using state abstraction. Prohibitively large
task representations can be condensed such that essential information is
preserved, and consequently, solutions are tractably computable. However, exact
abstractions, which treat only fully-identical situations as equivalent, fail
to present opportunities for abstraction in environments where no two
situations are exactly alike. In this work, we investigate approximate state
abstractions, which treat nearly-identical situations as equivalent. We present
theoretical guarantees of the quality of behaviors derived from four types of
approximate abstractions. Additionally, we empirically demonstrate that
approximate abstractions lead to reduction in task complexity and bounded loss
of optimality of behavior in a variety of environments.
