http:^^www.cs.duke.edu^~mlittman^courses^cps370^

This data set contains WWW-pages collected from computer science departments of various universities

<p>

<!WA25><img src="http://www.cs.duke.edu/~mlittman/courses/cps370/book.gif"> Gerald Tesauro. Temporal difference learning and TD-Gammon.
<em>Communications of the ACM</em>, 38(3):58--68, 1995. (<!WA26><a
href="http://www.research.ibm.com/massdist/tdl.html">html</a>) <p>

Slides: <!WA27><a href="http://www.cs.duke.edu/~mlittman/courses/cps370/slides/lect4.fm.ps">postscript</a> <p>

Another interesting application of TD lambda and neural networks
applied to MDP-like problems is Crites and Barto's elevator
controller. <p>

<!WA28><img src="http://www.cs.duke.edu/~mlittman/courses/cps370/book.gif"> Robert H. Crites and Andrew G. Barto.  Improving
elevator performance using reinforcement learning.  In
D. S. Touretzky, M. C. Mozer and M. E. Hasselmo, editors, <em>Advances
in Neural Information Processing Systems 8</em>, 1996.  The MIT Press.
(<!WA29><a
href="http://www-anw.cs.umass.edu./cgi-bin/getfile/pub/anw/pub/crites/nips8.ps.Z">compressed
postscript</a>) <p>

An even simpler and similarly successful example for cellular phone
channel assignments is based on TD(0) and a linear function
approximator. <p>

<!WA30><img src="http://www.cs.duke.edu/~mlittman/courses/cps370/book.gif"> Satinder Singh and Dimitri Bertsekas.
Reinforcement learning for dynamic channel allocation in cellular
telephone systems.  To appear in <em>Advances in Neural Information
Processing Systems 9</em>, 1997.  The MIT Press.  (<!WA31><a
href="ftp://ftp.cs.colorado.edu/users/baveja/Papers/CellPhone.ps">postscript</a>)
<p>

Tesauro's work is difficult to generalize because it simultaneously
addresses many unsolved problems.  More recent work has begun to tease
apart the effect of using function approximation in dynamic
programming from the use of the temporal difference algorithm. <p>

<!WA32><img src="http://www.cs.duke.edu/~mlittman/courses/cps370/book.gif"> Justin A. Boyan and Andrew W. Moore. Generalization in
reinforcement learning: Safely approximating the value function.  In
G. Tesauro, D. S. Touretzky and T. K. Leen, editors, <em>Advances in
Neural Information Processing Systems 7</em>, 1995.  The MIT
Press.  (<!WA33><a
href="http://www.cs.cmu.edu/afs/cs/project/reinforcement/papers/boyan.funapprox-dp.ps.Z">compressed
postscript</a>, <!WA34><a
href="http://www.cs.cmu.edu/afs/cs/project/reinforcement/ml95/index.html">Recent
workshop on value function approximation</a>) <p>

These results were not convincing to everyone. <p>

<!WA35><img src="http://www.cs.duke.edu/~mlittman/courses/cps370/book.gif"> Richard S. Sutton. Generalization in reinforcement learning:
Successful examples using sparse coarse coding.  In <em>Advances in
Neural Information Processing Systems 8</em>, 1996.  The MIT Press.
(<!WA36><a
href="ftp://ftp.cs.umass.edu/pub/anw/pub/sutton/sutton-96.ps">postscript</a>)
<p>

Slides: <!WA37><a href="http://www.cs.duke.edu/~mlittman/courses/cps370/slides/lect6.fm.ps">postscript</a> <p>

Some of the most interesting recent work has concerned theoretical
results on when function approximation will and will not result in a
convergent algorithm.  Results exist concerning gradient descent
methods and averaging methods.  <p>

<!WA38><img src="http://www.cs.duke.edu/~mlittman/courses/cps370/book.gif"> Leemon Baird.  Residual algorithms: Reinforcement
learning with function approximation.  In Armand Prieditis and Stuart
Russell, editors, <em>Proceedings of the Twelfth International
Conference on Machine Learning</em>, 30--37, 1995.  Morgan Kaufmann.
(<!WA39><a
href="http://www.cs.cmu.edu/afs/cs.cmu.edu/Web/People/baird/papers/residual.ps.Z">compressed
postscript</a>, <!WA40><a
href="http://www.cs.cmu.edu/afs/cs.cmu.edu/Web/People/baird/papers/residual">html</a>) <p>

<!WA41><img src="http://www.cs.duke.edu/~mlittman/courses/cps370/book.gif"> Geoffrey J. Gordon.  Stable function approximation in dynamic
programming.  In Armand Prieditis and Stuart Russell, editors,
<em>Proceedings of the Twelfth International Conference on Machine
Learning</em>, 261--268.  1995.  Morgan Kaufmann. (<!WA42><a 
href="http://www.cs.cmu.edu/afs/cs.cmu.edu/user/ggordon/www/ml95-stable-dp.ps.Z">compressed
postscript</a>) <p>

<!WA43><img src="http://www.cs.duke.edu/~mlittman/courses/cps370/book.gif"> John N. Tsitsiklis and Benjamin Van Roy.  Feature-based
methods for large scale dynamic programming.  </em>Machine
Learning</em>, 22(1/2/3): 59--94, 1996. (<!WA44><a
href="http://www.cs.duke.edu/~mlittman/courses/cps370/papers/vanroy-converge.ps">local postscript</a>) <p>

Homework: Propose a research project.

<h3>Stochastic Planning</h3>

The work on function approximation attempts to exploit structure in
the state space but treats actions as black box tranformations from
states to distributions over states.  A promising alternative is to
use symbolic descriptions of the actions to reason about entire
classes of state-to-state transitions all at once.  This is the
approach taken in AI planning. <p>

<!WA45><img src="http://www.cs.duke.edu/~mlittman/courses/cps370/book.gif"> David McAllester and David Rosenblitt.  Systematic nonlinear
planning.  In <em>Proceedings of the 9th National Conference on
Artificial Intelligence</em>, 1991.  (<!WA46><a
href="http://www.ai.mit.edu/people/dam/aaai91c.ps">postscript</a>, <!WA47><a
href="http://www.cse.fau.edu/~matt/cap4630/AIMA-lisp-code/planning/snlp/">LISP
code</a>) <p>

In the last two years, planning algorithms have been proposed that
differ substantially from the classic planners.  Although
unconventional, these planners have been shown empirically to result
in much shorter running times (up to several orders of magnitude
faster).  Blum and Furst's algorithm views planning as a type of graph
search while Kautz and Selman reduce planning to a boolean
satisfiability problem. <p>

<!WA48><img src="http://www.cs.duke.edu/~mlittman/courses/cps370/book.gif"> Avrim Blum and Merrick Furst.  Fast planning
through planning graph analysis.  In <em>Proceedings of the 14th
International Joint Conference on Artificial Intelligence
(IJCAI)</em>, pages 1636--1642, 1995.  (<!WA49><a
href="http://www.cs.cmu.edu/People/avrim/Papers/planning.ps.gz">extended
version in compressed postscript</a>) <p>

<!WA50><img src="http://www.cs.duke.edu/~mlittman/courses/cps370/book.gif"> Henry Kautz and Bart Selman.  Pushing the
envelope: Planning, propositional logic, and stochastic search.  In
<em>Proceedings of the 13th National Conference on Artificial
Intelligence</em>, 1996.  (<!WA51><a
href="http://www.research.att.com:80/~kautz/papers-ftp/plan.ps">postscript</a>)
<p>

Slides: <!WA52><a href="http://www.cs.duke.edu/~mlittman/courses/cps370/slides/lect7b.fm.ps">postscript</a> <p>

In spite of recent algorithmic advances, the traditional view of
planning ignores uncertainty.  Uncertainty can be introduced gently by
assuming a deterministic domain with some randomness added in. <p>

<!WA53><img src="http://www.cs.duke.edu/~mlittman/courses/cps370/book.gif"> Jim Blythe.  Planning with external events.  In
<em>Proceedings of the Tenth Conference on Uncertainty in Artificial
Intelligence</em>, 1994.  (<!WA54><a
href="http://calvin.prodigy.cs.cmu.edu/papers/uai94.ps">postscript</a>)
<p>

The Buridan system introduces a more general representation for
stochastic STRIPS operators and extends partial order planning to
stochastic domains.  Its representation is equivalent in
expressiveness to MDPs. <p>

Slides: <!WA55><a href="http://www.cs.duke.edu/~mlittman/courses/cps370/slides/lect8a.fm.ps">postscript</a> <p>

<!WA56><img src="http://www.cs.duke.edu/~mlittman/courses/cps370/book.gif"> Nicholas Kushmerick, Steve Hanks and Daniel S. Weld.  An
algorithm for probabilistic planning.  <em>Artificial
Intelligence</em>, 76(1-2): 239--286, 1995. (<!WA57><a
href="file://cs.washington.edu/tr/1993/06/UW-CSE-93-06-03.PS.Z">compressed
postscript</a>) <p>

The Buridan system has been expanded so that the plan representation
is more powerful (though less powerful than a policy-like
representation). <p>

<!WA58><img src="http://www.cs.duke.edu/~mlittman/courses/cps370/book.gif"> Denise Draper, Steve Hanks and Dan Weld.  Probabilistic
planning with information gathering and contingent execution.
Technical Report 93-12-04, University of Washington, Department of
Computer Science, Seattle, WA, December, 1993. (<!WA59><a
href="ftp://ftp.cs.washington.edu/tr/1993/12/UW-CSE-93-12-04.PS.Z">compressed
postscript</a>) <p>

Slides: <!WA60><a href="http://www.cs.duke.edu/~mlittman/courses/cps370/slides/lect8b.fm.ps">postscript</a> <p>

An area of intense interest (but remarkably little work!) is combining
direct manipulation of STRIPS-type actions with a
dynamic-programming-based algorithm.  Several papers adopt the view
that function approximation is a form of ``abstraction,'' the form of
which can be derived automatically from a propositional representation
of the planning problem. <p>

<!WA61><img src="http://www.cs.duke.edu/~mlittman/courses/cps370/book.gif"> Richard Dearden and Craig Boutilier.  Abstraction
and approximate decision theoretic planning.  To appear in
<em>Artificial Intelligence</em>. (<!WA62><a href="http://www.cs.ubc.ca/spider/cebly/Papers/abstraction.ps">postscript</a>) <p>

<!WA63><img src="http://www.cs.duke.edu/~mlittman/courses/cps370/book.gif"> Craig Boutilier, Richard Dearden and Moises
Goldszmidt.  Exploiting structure in policy construction.  To appear
in <em>Proceedings of the International Joint Conference on Artificial
Intelligence</em>, 1995. (<!WA64><a
href="http://www.cs.ubc.ca/spider/cebly/Papers/spi.ps">postscript</a>)
<p>

<!WA65><img src="http://www.cs.duke.edu/~mlittman/courses/cps370/book.gif"> Craig Boutilier and Richard Dearden.  Approximating value
trees in structured dynamic programming.  To appear in <em>Proceedings
of the Thirteenth International Conference on Machine Learning</em>,
1996.  (<!WA66><a
href="http://www.cs.ubc.ca/spider/cebly/Papers/pruning.ps">postscript</a>)

Slides: <!WA67><a href="http://www.cs.duke.edu/~mlittman/courses/cps370/slides/lect8c.fm.ps">postscript</a> <p>

Summary Slides: <!WA68><a href="http://www.cs.duke.edu/~mlittman/courses/cps370/slides/lect9.fm.ps">postscript</a> <p>

<a name="now">

Next we'll deal with partially observable Markov decision processes
and how to solve them.

<h3>Advanced Topics</h3>

If we make unexpectedly fast progress through the core topics, there
are a number of interesting issues we could explore including:
hierarchical solutions to MDPs, partially observable MDPs, solving
games. <p>

Here are some papers I've recently found that might be useful to
discuss.  The first gives a notation for representing multi-player
games of incomplete information that might be useful in defining a
similar notation for MDPs.  The second describes how to solve very
large (and even continuous state) MDPs efficiently using linear
programming. <p>

<!WA69><img src="http://www.cs.duke.edu/~mlittman/courses/cps370/book.gif"> Daphne Koller and Avi Pfeffer.  Representations
and solutions for game-theoretic problems.  Preliminary version
appeared in <em>Proceedings of the 14th International Joint Conference
on Artificial Intelligence (IJCAI)</em>, Montreal, Canada, August
1995, pages 1185--1192. (<!WA70><a
href="http://robotics.Stanford.EDU/~koller/papers/galapaper.ps">postscript</a>)
<p>

<!WA71><img src="http://www.cs.duke.edu/~mlittman/courses/cps370/book.gif"> Michael Trick and Stanley Zin.  A linear
programming approach to solving stochastic dynamic programs, 1993.
(<!WA72><a href="http://mat.gsia.cmu.edu/dyn.ps">postscript</a>) <p>

<hr>
<h2> <A NAME="projects"><!WA73><img src="http://www.cs.duke.edu/~mlittman/courses/cps370/bulb-t.gif">Project Ideas<A> </h2>

The major thrust of the seminar will be to undertake a group project
exploring some facet of the problem of planning under uncertainty.
Some sample project ideas are:

<UL>
<LI> Are there methods of efficiently evaluating plans in complex
domains?
<LI> Do MDP aggregation methods have anything to offer?
<LI> Can hierarchical methods be applied to propositional state
spaces? 
<LI> Can Blum and Furst's <!WA74><a
href="http://www.cs.cmu.edu/afs/cs.cmu.edu/Web/People/avrim/graphplan.html">Graphplan</a>
algorithm be extended to stochastic domains?
<LI> How do the known results concerning the use of function
approximation in dynamic programming relate to one another?
<LI> How does Boutilier and Dearden's structured policy iteration
algorithm perform on some simple structured MDPs?
</UL>

We're starting to make some progress on a domain for later project
development.  Stephen Majercik has written up his ideas on a load
balancing MDP, which are accessible from his <!WA75><a
href="http://www.cs.duke.edu:80/~majercik/HomePage.html">home
page</a>. <p>

We've talked about using the <!WA76><a
href="http://robotics.Stanford.EDU/~koller/gala.html">GALA</a> system
as a basis for a general declarative language for specifying MDPs.
Another options is a <!WA77><a
href="http://envy.cs.umass.edu/People/sutton/RLinterface/RLinterface.html">standard</a>
proposed by Rich Sutton.

<p>

<hr>
<address>
Last modified: Thu Nov  7 14:32:49 EST 1996
by Michael Littman, [e-mail]
</font>
</body>