paper available by ftp

[mccallum@cs.rochester.edu]

FTP-host: ftp.cs.rochester.edu
FTP-file: pub/papers/robotics/94.mccallum-tr502.ps.Z
27 pages.

        "First Results with Instance-Based State Identification 
                     for Reinforcement Learning"

                         R. Andrew McCallum
                    Department of Computer Science
                      University of Rochester
                        Technical Report 502

When a reinforcement learning agent's next course of action depends on
information that is hidden from the sensors because of problems such
as occlusion, restricted range, bounded field of view and limited
attention, we say the agent suffers from the Hidden State Problem.
State identification techniques use history information to uncover
hidden state.  Previous approaches to encoding history include: finite
state machines [Chrisman 1992; McCallum 1992], recurrent neural
networks [Lin 1992] and genetic programming with indexed memory
[Teller 1994].  A chief disadvantage of all these techniques is their
long training time.
  
This report presents Instance-Based State Identification, a new
approach to reinforcement learning with state identification that
learns with much fewer training steps.  Noting that learning with
history and learning in continuous spaces both share the property that
they begin without knowing the granularity of the state space, the
approach applies instance-based (or ``memory-based'') learning to
history sequences---instead of recording instances in a continuous
geometrical space, we record instances in action-perception-reward
sequence space.

The first implementation of this approach, called Nearest Sequence
Memory, learns with an order of magnitude fewer steps than several
previous approaches.


The paper is also available through the http URL below:

R. Andrew McCallum          EBOX: mccallum at cs.rochester.edu
Computer Science Dept       VOX: (716) 275-2527, (716) 275-1372 (lab)
University of Rochester     FAX: (716) 461-2018
Rochester, NY  14627-0226   http://www.cs.rochester.edu/u/mccallum

------- End of Blind-Carbon-Copy