12:00, 20 Mar 1996, WeH 7220

	      Algorithms for Sequential Decision Making

			  Michael L. Littman
			   Brown University

Sequential decision making is a fundamental task faced by any
intelligent agent in an extended interaction with its environment.
Recently, I examined a collection of computational problems arising in
the study of sequential decision making under uncertainty; one problem
is finding optimal behavior for partially observable Markov decision
processes (POMDPs), a type of sequential problem in which the state of
the system and its future evolution are modeled stochastically.  I
will describe an algorithm I developed for solving POMDPs exactly, and
show how it compares favorably to existing algorithms for this
problem.  I will also present some preliminary results on the use of a
reinforcement-learning approach to solve larger problem instances
approximately; this technique has been used successfully to find good
policies for a robot navigating in an office environment.