Reinforcement Learning with Selective Perception and Hidden State

Thesis (Ph. D.)--University of Rochester. Dept. of Computer Science, 1996. Published in the Technical Report series, 1997.Reinforcement learning is a machine learning framework in which an agent manipulates its environment through a series of actions, and in response to each action, receives a reward value. The agent stores its knowledge about how to choose reward-maximizing actions in a mapping from agent-internal states to actions. Agents often struggle with two opposite, yet intertwined, problems regarding their internal state space. First, the agent's state space may have too many distinctions---meaning that an abundance of perceptual data has resulted in a state space so large that it overwhelms the agent's limited resources for computation, storage and learning experience. This problem can often be solved if the agent uses selective perception to prune away unnecessary distinctions, and focus its attention only on certain features. Second, even though there are too many distinctions, the agent's state space may simultaneously contain too few distinctions---meaning that perceptual limitations (such as field of view, acuity and occlusions), have temporarily hidden crucial features of the environment from the agent. This problem, called hidden state, can often be solved by using memory of features from previous views to augment the agent's perceptual inputs. This dissertation presents algorithms that use selective perception and short-term memory to simultaneously prune and augment the state space provided by the agent's perceptual inputs. During learning, the agent selects task-relevant state distinctions with a utile distinction test that uses robust statistics to determine when a distinction helps the agent predict reward. The dissertation also advocates using instance-based (or memory-based) learning for making efficient use of accumulated experience, and using a tree structure to hold variable-length memories. Four new algorithms are shown to perform a variety of tasks well---in some cases with more than an order-of-magnitude better performance than previous algorithms