Paper on RL, feature selection, hidden state

[Andrew McCallum]

The following paper on reinforcement learning, hidden state and
feature selection is available by FTP.  Comments and suggestions are
welcome.

     "Learning to Use Selective Attention and Short-Term Memory"

		       Andrew Kachites McCallum

			(to appear in SAB'96)

			       Abstract

 This paper presents U-Tree, a reinforcement learning algorithm that
 uses selective attention and short-term memory to simultaneously
 address the intertwined problems of large perceptual state spaces and
 hidden state.  By combining the advantages of work in instance-based
 (or ``memory-based'') learning and work with robust statistical tests
 for separating noise from task structure, the method learns quickly,
 creates task-relevant state distinctions, and handles noise well.
 
 U-Tree uses a tree-structured representation, and is related to work
 on Prediction Suffix Trees [Ron et al 94], Parti-game [Moore 94],
 G-algorithm [Chapman and Kaelbling 91], and Variable Resolution
 Dynamic Programming [Moore 91].  It builds on Utile Suffix Memory
 [McCallum 95], which only used short-term memory, not selective
 perception.
 
 The algorithm is demonstrated solving a highway driving task in which
 the agent weaves around slower and faster traffic.  The agent uses
 active perception with simulated eye movements.  The environment has
 hidden state, time pressure, stochasticity, over 21,000 world states
 and over 2,500 percepts.  From this environment and sensory system,
 the agent uses a utile distinction test to build a tree that
 represents depth-three memory where necessary, and has just 143
 internal states---far fewer than the 2500^3 states that would have
 resulted from a fixed-sized history-window approach.
 

Retrieval information:

FTP-host:      ftp.cs.rochester.edu
FTP-pathname:  /pub/papers/robotics/96.mccallum-sab.ps.gz
URL: ftp://ftp.cs.rochester.edu/pub/papers/robotics/96.mccallum-sab.ps.gz