# 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