Variable Resolution Discretization in Optimal Control

Remi Munos

Abstract
The problem of making decisions in stochastic environments is central to many areas, including robotics, finance, industrial manufacturing, and game playing. When we consider optimal control problems described in terms of continuous space and time variables, we deduce highly non-linear partial differential equations: the well-known Hamilton-Jacobi-Bellman equations. Consistent discretizations of these equations (for example by using Finite-Elements or Finite-Differences methods) generate Markov Decision Processes whose solutions approximate the continuous value function and the optimal policy. Similar adaptive methods provide convergent Reinforcement Learning algorithms.

Here I will consider variable resolution discretization methods built in a top-down approach: an initial coarse grid is successively refined according to some splitting criterion. I will introduce and evaluate several splitting methods, from local to global approaches in which we take into account the impact of a cell on the whole state-space when deciding wether to split. I will illustrate their performance on several benchmark problems: ``Car on the Hill'', the ``Acrobot'', the ``Inverted pendulum'' and the ``Space-shuttle''. Futher research using sparse representations and Monte-Carlo methods will also be discussed. This is joint work with Andrew Moore.

Biography
In 1991, Munos graduated from the engineering school `Ecole Nationale Superieure des Telecommunications' in Paris. Following that, he pursued a diploma (DEA) in Cognitive Sciences and in Mathematics at the `University Pierre et Marie Curie', Paris. In 1997, he received a PhD from the `Ecole des Hautes Etudes en Sciences Sociales' where he worked on theoretical aspects of Reinforcement Learning in the continuous case and the link with Viscosity Solutions. Since May 1998, he has been working as a postdoctoral researcher at the Auton Lab supervised by Prof. Andrew Moore at the Robotics Institute, Carnegie Mellon University.

Kee-Eung Kim

Get Back

Last modified: Sat Oct 16 16:44:46 EDT 1999