Memoryless policies: Theoretical limitations and practical results

Michael L. Littman
Brown University / Bellcore 
Department of Computer Science 
Brown University
Providence, RI 02912-1910

mlittman@cs.brown.edu

Abstract

One form of adaptive behavior is "goal-seeking" in which an agent acts
so as to minimize the time it takes to reach a goal state.  This paper
presents some theoretical and empirical findings on algorithms that
devise goal-seeking behaviors for "memoryless" agents who base their
behavioral decisions solely on current sensations.  The basic results
are that (1) the general problem of finding good deterministic
memoryless policies is intractable, however, (2) simple
branch-and-bound heuristics can be used to find optimal memoryless
policies extremely quic kly for some established example environments.