  Reinforcement learning defines the problem facing agents that learn to make
good decisions through action and observation alone. To be effective problem
solvers, such agents must efficiently explore vast worlds, assign credit from
delayed feedback, and generalize to new experiences, all while making use of
limited data, computational resources, and perceptual bandwidth. Abstraction is
essential to all of these endeavors. Through abstraction, agents can form
concise models of their environment that support the many practices required of
a rational, adaptive decision maker. In this dissertation, I present a theory
of abstraction in reinforcement learning. I first offer three desiderata for
functions that carry out the process of abstraction: they should 1) preserve
representation of near-optimal behavior, 2) be learned and constructed
efficiently, and 3) lower planning or learning time. I then present a suite of
new algorithms and analysis that clarify how agents can learn to abstract
according to these desiderata. Collectively, these results provide a partial
path toward the discovery and use of abstraction that minimizes the complexity
of effective reinforcement learning.
