From mccallum@cs.rochester.edu Sun Jun 30 01:15:46 1996
Received: from lucy.cs.wisc.edu (lucy.cs.wisc.edu [128.105.2.11]) by sea.cs.wisc.edu (8.6.12/8.6.12) with ESMTP id BAA25999 for <ml@sea.cs.wisc.edu>; Sun, 30 Jun 1996 01:15:39 -0500
Received: from TELNET-1.SRV.CS.CMU.EDU (TELNET-1.SRV.CS.CMU.EDU [128.2.254.108]) by lucy.cs.wisc.edu (8.6.12/8.6.12) with SMTP id BAA22667 for <ml@cs.wisc.edu>; Sun, 30 Jun 1996 01:15:37 -0500
Received: from TELNET-1.SRV.CS.CMU.EDU by telnet-1.srv.cs.CMU.EDU id aa23084;
          30 Jun 96 1:01:48 EDT
Received: from DST.BOLTZ.CS.CMU.EDU by TELNET-1.SRV.CS.CMU.EDU id aa23082;
          30 Jun 96 0:46:45 EDT
Received: from DST.BOLTZ.CS.CMU.EDU by DST.BOLTZ.CS.CMU.EDU id aa03967;
          30 Jun 96 0:46:02 EDT
Received: from RI.CMU.EDU by B.GP.CS.CMU.EDU id aa21348; 29 Jun 96 19:35:49 EDT
Received: from cayuga.cs.rochester.edu by RI.CMU.EDU id aa08225;
          29 Jun 96 19:35:42 EDT
Received: from slate.cs.rochester.edu (slate.cs.rochester.edu [192.5.53.101]) by cayuga.cs.rochester.edu (8.6.9/H) with ESMTP id TAA19284; Sat, 29 Jun 1996 19:34:59 -0400
Received: from vein.cs.rochester.edu (vein.cs.rochester.edu [192.5.53.112]) by slate.cs.rochester.edu (8.6.9/K) with SMTP id TAA19728; Sat, 29 Jun 1996 19:34:28 -0400
Message-Id: <199606292334.TAA19728@slate.cs.rochester.edu>
To: connectionists@cs.cmu.edu, reinforce@cs.uwa.edu.au,
        intcon@phoenix.ee.unsw.edu.au, genetic-programming@cs.stanford.edu,
        learning@uran.informatik.uni-bonn.de, ml@ics.uci.edu
Subject: Paper on RL, feature selection, hidden state
Date: Sat, 29 Jun 1996 19:34:28 -0400
From: Andrew McCallum <mccallum@cs.rochester.edu>

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
