Variable Resolution Discretization in Optimal Control.
The problem of state abstraction is of central importance in optimal control, reinforcement learning and Markov decision processes. This paper studies the case of variable resolution state abstraction for continuous time and space, deterministic dynamic control problems in which near-optimal policies are required. We begin by defining a class of variable resolution policy and value function representations based on Kuhn triangulations embedded in a kd-trie. We then consider top-down approaches to choosing which cells to split in order to generate improved policies. The core of this paper is the introduction and evaluation of a wide variety of possible splitting criteria. We begin with local approaches based on value function and policy properties that use only features of individual cells in making split choices. Later, by introducing two new non-local measures, influence and variance, we derive splitting criteria that allow one cell to efficiently take into account its impact on other cells when deciding whether to split. Influence is an efficiently-calculable measure of the extent to which changes in some state effect the value function of some other states. Variance is an efficiently-calculable measure of how risky is some state in a Markov chain: a low variance state is one in which we would be very surprised if, during any one execution, the long-term reward attained from that state differed substantially from its expected value, given by the value function.The paper proceeds by graphically demonstrating the various approaches to splitting on the familiar, non-linear, non-minimum phase, and two dimensional problem of the Car on the hill. It then evaluates the performance of a variety of splitting criteria on many benchmark problems, paying careful attention to their number-of-cells versus closeness-to-optimality tradeoff curves.
Introduction
This paper is about non-uniform discretization of state spaces when finding optimal
controllers for continuous time and space Markov Processes.
Uniform discretizations (generally based on finite element or finite difference techniques
(Kushner & Dupuis, 1992) provide us with important convergence results
(see the analytical approach of (Barles & Souganidis, 1991; Crandall, Ishii, & Li-
ons, 1992; Crandall & Lions, 1983; Munos, 1999) and the probabilistic results of
(Kushner & Dupuis, 1992; Dupuis & James, 1998)), but suffer from impractical
computational requirements when the size of the discretization step is small, especially
when the state space is high dimensional. On the other hand, approximation
methods (Bertsekas & Tsitsiklis, 1996; Baird, 1995; Sutton, 1996) can handle high
EMI MUNOS AND ANDREW MOORE
dimensionality but in general, have no guarantee of convergence to the optimal solution
(Boyan & Moore, 1995; Baird, 1995; Munos, 1999). Some local convergence
results are in (Gordon, 1995; Baird, 1998).
In this paper we try to keep the convergence properties of the discretized methods
while introducing an approximation factor by the iterative designing of a variable
resolution. In this paper we only consider the "general towards specific" approach :
an initial coarse grid is successively refined at some areas of the state space by using
a splitting process, until some desired approximation (of the value function or the
optimal control) is reached.
First, we implement two splitting criteria based on the value function (see section
6), then we define a criterion of inconsistency between the value function and the
policy (see section 7). In order to define the effect of the splitting of a state on others
states, we define in section 8 the notion of influence. And we estimate the expected
gain in the approximation of the value function when splitting states by defining
in section 9 the variance of a Markov chain. By combining these two notions, we
deduce, for a given discretization, the states whose splitting will mostly influence
the parts of the state space where there is a change in the optimal control, leading
to increase the resolution at those important areas.
We illustrate the different splitting criteria on the "Car on the hill" problem and
in section 11 we show the results for other control problems, including the well
known 4 dimensions "Cart-pole" and "Acrobot" problems.
In this paper we make the assumption that we have a model of the dynamics and of
the reinforcement function. Moreover we assume that the dynamics is deterministic.
2. Description of the optimal control problem
We consider discounted deterministic control problems, which include the well-known
reinforcement learning benchmarks of Car on the Hill (Moore, 1991), Cart-Pole
(Barto, Sutton, & Anderson, 1983) and Acrobot (Sutton, 1996). Let x(t) 2 X
be the state of the system, with the state space X be a compact subset of IR d . The
evolution of the state depends on the control u(t) 2 U (with the control space U a
finite set of discrete actions) by the differential equation, called state dynamics :
dx
dt
For an initial state x and a control function u(t), this equation leads to a unique
trajectory x(t). Let - be the exit time from the state space (with the convention
that if x(t) always stays in X, then 1). Then, we define the gain J as the
discounted cumulative reinforcement :
where r(x; u) is the current reinforcement and R(x) the boundary reinforcement.
fl is the discount factor (0 - 1). For convenience reasons, in what follows, we
assume that fl ! 1. However, most of the results apply to the undiscounted case
assuming that for any control u(t), the trajectories do not loop (i.e.
VARIABLE RESOLUTION DISCRETIZATION IN OPTIMAL CONTROL 3
The objective of the control problem is to find, for any initial condition x, the
control u   (t) that optimizes the functional J .
Here we use the method of Dynamic Programming (DP) that introduces the value
function (VF), maximum of J as a function of initial state x :
Following the DP principle, we can prove (Fleming & Soner, 1993) that V satisfies
a first-order non-linear differential equation, called the Hamilton-Jacobi-Bellman
Theorem 1 If V is differentiable at x 2 X, let DV (x) be the gradient of V at x,
then the following HJB equation holds at x.
u2U
DP computes the VF in order to define the optimal control with a feed-back
control policy U such that the optimal control u   (t) at time t only
depends on current state x(t) : u   -(x(t)). Indeed, from the value function,
we deduce the following optimal feed-back control policy :
3. The discretization process
In order to discretize the continuous control problem described in the previous sec-
tion, we use a process based on the finite element methods of (Kushner & Dupuis,
1992). We use a class of functions known as barycentric interpolators (Munos &
Moore, 1998), built from a triangulation of the state-space. These functions are
piecewise linear inside each simplex, but might be discontinuous at the boundary
between two simplexes. This representation has been chosen for its very fast
computational properties.
Here is a description of this class of functions. The state-space is discretized into
a variable resolution grid using a structure of a tree. The root of the tree covers
the whole state space, supposed to be a (hyper) rectangle. It has two branches
which divide the state space into two smaller rectangles by means of a hyperplane
perpendicular to the chosen splitting dimension. In the same way, each node (except
for the leaf ones) splits in some direction 1::d the rectangle it covers at its middle
into two nodes of half area (see Figure 1). This kind of structure is known as a kd-
trie (Knuth, 1973), and is a special kind of kd-tree (Friedman, Bentley, & Finkel,
1977) in which splits occur at the center of every cell.
For every leaf, we consider the Coxeter-Freudenthal-Kuhn triangulation (or simply
the Kuhn triangulation (Moore, 1992)). In dimension 2 (Figure 1(b)) each
rectangle is composed of 2 triangles. In dimension 3 (see Figure 2) they are composed
of 6 pyramids, and in dimension d, of d! simplexes.
The interpolated functions consider here are defined by their values at the corners
of the rectangles. We use the Kuhn triangulation to linearly interpolate inside
the rectangles. Thus these functions are piecewise linear, continuous inside each
rectangle, but may be discontinuous at the boundary between two rectangles.
EMI MUNOS AND ANDREW MOORE
(b) The corresponding tree
(a) Example of discretization

Figure

1. (a) An example of discretization of the state space. There are 12 rectangles and 24
corners (the dots). (b) The corresponding tree structure. The area covered by each node is
indicated in gray level. We implement a Kuhn triangulation on every leaf
Remark. As we are going to approximate the value function V with such piecewise
linear functions, it is very easy to compute the gradient DV at (almost) any point
of the state space, thus making possible to use the feed-back rule 4 to deduce the
corresponding optimal control.
x
x

Figure

2. The Kuhn triangulation
of a (3d) rectangle. The point x
is in the simplex (-
3.1. Computational issues
Although the number of simplexes inside a rectangle is factorial with the dimension
d, the computation time for interpolating the value at any point inside a rectangle
is only of order (d ln d), which corresponds to a sorting of the d relative coordinates
of the point inside the rectangle.
Assume we want to compute the indexes of the (d vertices of the
simplex containing a point defined by its relative coordinates
respect to the rectangle whose corners are f- dg. The indexes of the corners
VARIABLE RESOLUTION DISCRETIZATION IN OPTIMAL CONTROL 5
uses the binary decomposition in dimension d, as illustrated in Figure 2. Computing
these indexes is achieved by sorting the coordinates from the highest to the smallest :
there exist indices permutation of f0; ::; d \Gamma 1g, such that 1 - x j0 -
of the (d vertices of the
simplex containing the point are
1. For example, if the coordinates
(illustrated by the point x in Figure 2) then the vertices are : - 0 (every
simplex has this vertex, as well as - 2 d
added
The corresponding barycentric coordinates - d of the point inside the simplex
are
In the previous example, the barycentric coordinates are :
The approach of using Kuhn triangulations to interpolate the value function has
been introduced to the reinforcement learning literature by (Davies, 1997).
3.2. Building the discretized MDP
For a given discretization, we build a corresponding Markov Decision Process
(MDP) in the following way. The state space of the MDP is the set \Xi of corners
of the tree. The control space is the finite set U . For every corner - 2 \Xi and
control u 2 U we approximate a part of the corresponding trajectory x(t) (with the
Euler or Runge-Kuta method) by integrating the state dynamics (1) from initial
state - for a constant control u, during some time -; u) until it enters inside a new
rectangle at some point j(-; u) (see Figure 3). At the same time, we also compute
the integral of the current reinforcement :
R -;u)
which defines the reinforcement function of the MDP. Then we compute the
vertices of the simplex containing j(-; u) and the corresponding barycentric
coordinates -0 (j(-; u)); :::; -d (j(-; u)). The probabilities of transition
of the MDP from state - and control u to states - i are defined by these
barycentric coordinates (see Figure
(j(-; u)). Thus, the DP
equation corresponding to this MDP is :
(j(-; u)):V (-
If while integrating (1) from initial state - with the control u, the trajectory exits
from the state space at time -; u), then (-; u) lead to a terminal state - t (i.e.
satisfying p(- t
the reinforcement :
R -;u)
3.3. Resolution of the discretized MDP
We can use any of the classical methods to solve the discretized MDP, i.e. value
iteration, policy iteration, modified policy iteration (Puterman, 1994), (Bertsekas,
EMI MUNOS AND ANDREW MOORE
x
x

Figure

3. According to the current (variable res-
olution) grid, we build a discrete MDP. For every
corner - (state of the MDP) and every control u,
we integrate the corresponding trajectory until
it enters a new rectangle at j(-; u). The interpolated
value at j(-; u) is a linear combination
of the values of the vertices of the simplex it is
in (here (- Furthermore, it is a linear
combination with positive coefficients that sum
to one. Thus, doing this interpolation is mathematically
equivalent to probabilistically jumping
to a vertex. The probabilities of transition of the
MDP for (state -, control u) to (states f- i g i=0::2
are the barycentric coordinates - i
(j(-; u)) of
1987), (Barto, Bradtke, & Singh, 1995) or the prioritized sweeping (Moore & Atke-
son, 1993).
4. An example : the "Car on the Hill" control problem
For a description of the dynamics of this problem, see (Moore & Atkeson, 1995).
This problem is of dimension 2. In our experiments, we chose the reinforcement
functions as follows : the current reinforcement r(x; u) is zero everywhere. The
terminal reinforcement R(x) is \Gamma1 if the car exits from the left side of the state
space, and varies linearly between +1 and \Gamma1 depending on the velocity of the car
when it exits from the right side of the state space. The best reinforcement +1
occurs when the car reaches the right boundary with a null velocity (figure 4). The
control u has only 2 possible values : maximal positive or negative thrust.

Figure

6 represents the interpolated value function of the MDP obtained by a
regular discretization of 257 by 257 states.
We observe the following distinctive features of the value function :
ffl There is a discontinuity in the VF along the "Frontier 1" (see Figure 6) which
results from the fact that given an initial point situated above this frontier,
the optimal trajectory stays inside the state space (and eventually leads to a
positive reward) so the value function at this point is positive. Whereas for a
initial point below this frontier, any control lead the car to exit from the left
boundary (because the initial velocity is too negative), thus the corresponding
value function is negative (see the optimal trajectories in Figure 5). We observe
that there is no change in the optimal control around this frontier.
ffl There is a discontinuity in the gradient of the VF along the upper part of
"Frontier 2" which results from a change in the optimal control. For example,
a point above frontier 2 can reach directly the top of the hill, whereas a point
below this frontier has to go down and do one loop to gain enough velocity to
reach the top (see Figure 5). Moreover, we observe that around the lower part
VARIABLE RESOLUTION DISCRETIZATION IN OPTIMAL CONTROL 7
Goal
Thrust
Gravitation
Resistance
Reinforcement
R=+1 for null velocity
R=-1 for max. velocity

Figure

4. The "Car on the Hill" control problem.
Frontier 3
Frontier 2, upper part
Frontier 2, lower part
GOAL
Position
Velocity

Figure

5. The optimal policy is indicated
by different gray levels. Several optimal
trajectories are drawn for different initial
starting points.
of frontier 2 (see Figures 6), there is no visible discontinuity of the VF despite
the fact that there is a change in the optimal control.
ffl There is a discontinuity in the gradient of the VF along the "Frontier 3" because
of a change in the optimal control (below the frontier, the car accelerates in order
to reach the reward as fast as possible, whereas above, it decelerates to reach
the top of the hill with the lowest velocity and receive the highest reward).

Figure

6. The value function of the Car-on-the-Hill problem obtained by a regular grid of 257 by
states. The Frontier 1 illustrates the discontinuity of the VF, the Frontiers 2 and 3
(the dash lines) stands where there is a change in the optimal control.
EMI MUNOS AND ANDREW MOORE
We deduce from these observations that a good approximation of the value function
does not necessarily mean a good approximation of the optimal control since :
ffl The approximation of the value function is not sufficient to predict the change
in the optimal control around the lower part of frontier 2.
ffl A good approximation of the value function is not necessary around the frontier
1 since there is no change in the optimal control.
5. The variable resolution approach
The idea is to start with an initial coarse discretization, build the corresponding
MDP, solve it in order to have a (coarse) approximation of the value function, then,
locally refine the discretization by splitting some cells according to the process :
1. Score each cell and each direction i according to how promising it is to split
according to some measure, called split-criterion(i).
2. Pick the top f% (where f is a parameter) of the highest scoring cells.
3. Split them along the direction given by argmax i split-criterion(i). Use the
dynamics and reward model to create a new (larger) discretized MDP (see the
splitting process in Figure 7). Note that only the cells that were split, and those
whose successive states involve a split cell need to have their state transition
recomputed.
4. Go to step 1 until we estimate that the approximation of the value function or
the optimal control is precise enough.
Thus, the central purpose of this paper is the study of several splitting criteria.

Figure

7. Several discretizations resulting of successive splitting operations.
Remark. In this paper, we only consider a "general towards specialized" process
in the sense that the discretization is always refined. We could also consider some
"generalization" process where, for example the tree coding for the discretization
could be pruned, in order to avoid non relevant partitioning into too small subsets.
In what follows, we present several local splitting criteria and illustrate the resulting
discretizations on the previous "Car on the Hill" control problem.
VARIABLE RESOLUTION DISCRETIZATION IN OPTIMAL CONTROL 9
6. Criteria based on the value function
6.1. First criterion : average corner-value difference
For every rectangle, we compute the average of the absolute difference of the values
at the corners of the edges for all directions us denote Ave(i) this
criterion for direction i. For example, consider the square described in Figure 2.
Then this split-criterion is :

Figure

8 represents the discretization obtained after 15 iterations of this procedure,
starting with a 9 by 9 initial grid and using the corner-value difference criterion
with a splitting rate of 50% of the rectangles at each iteration.

Figure

8. The discretization of the state space
for the "Car on the Hill" problem using the
corner-value difference criterion.

Figure

9. The discretization of the state space
for the "Car on the Hill" problem using the
value non-linearity criterion.
6.2. Second criterion : value non-linearity
For every rectangle, we compute the variance of the absolute increase of the values
at the corners of the edges for all directions This criterion is similar to
the previous one except that it computes the variance instead of the average.

Figure

9 shows the corresponding discretization using the value non-linearity criterion
with a splitting rate of 50% after 15 iterations.
Comments on these results:
ffl We observe that in both cases, the splitting occurs around the frontiers 1, 3 and
the upper part of frontier 2, previously defined. In fact, the first criterion leads
to reduce the variation of the values, and splits wherever the value function is
not constant. Figure 10(a)&(b) shows a (1-dimension) cut of a discontinuity and
EMI MUNOS AND ANDREW MOORE
the corresponding discretization and approximation obtained using the corner-
value difference split criterion.
ffl The value non-linearity criterion leads to reduce the change of variation of the
values, thus splits wherever the value function is not linear. So this criterion will
also concentrate on the same irregularities but with two important differences
compared to the corner-value difference criterion :
- The value non-linearity criterion splits more parsimoniously than the corner-
value difference. See, for example, the difference of splitting in the area
above the frontier 3.
- The discretization resulting of the split of a discontinuity by the corner-
value difference and the value non-linearity criteria are different (see Figure
10). The value non-linearity criterion splits where the approximated
function (here some kind of sigmoid function whose slope depends on the
density of the resolution) is the least linear (Figure 10(c)&(d)). This explains
the 2 parallel tails observed around the frontiers (mainly the right
part of frontier 1) in Figure 9.
ffl The refinement process does not split around the bottom part of frontier 2
although there is a change in the optimal control (because the VF is almost
constant in this area). Moreover, there is a huge amount of memory spent for
the approximation of the discontinuity (frontier 1) although the optimal control
is constant in this area.
(a) Average split criterion
Coarse resolution
(b) Average split criterion
Dense resolution
(c) Variance split criterion
Coarse resolution
(d) Variance split criterion
Dense resolution

Figure

10. The discretization around a discontinuity resulting of the corner-value difference
(a)&(b) and the value non-linearity (c)&(d) split criterion, for a coarse (a)&(c) and a dense
(b)&(d) resolution.
Thus we can wonder if it is really useful to split so much around frontier 1,
knowing that it will not result in an improved policy ?
Next section introduces a new criterion which takes into account the policy.
VARIABLE RESOLUTION DISCRETIZATION IN OPTIMAL CONTROL 11
7. A criterion based on the policy

Figure

5 shows the optimal policy and several optimal trajectories for different
starting points. We would like to define a refinement process that could refine
around the areas of change in the optimal control, that is around frontier 2 (upper
and lower parts) and 3, but not around frontier 1. In what follows, we propose
such a criterion based on the inconsistency of the control derived from the value
function and from the policy.
7.1. The policy disagreement criterion
When we solve the MDP and compute the value function of the DP equation (5),
we deduce the following policy for any state - 2 \Xi :
and we can compare it with the optimal control law (4) derived from the gradient of
. The policy disagreement criterion compares the control derived from the local
gradient of V (4) with the control derived from the policy of the MDP (6).
Remark. Instead of computing the gradient DV for all the (d!) simplexes in the
rectangles, we compute an approximated gradient ~
DV for all the (2 d ) corners,
based on a finite difference quotient. For the example of figure 2, the approximated
gradient at corner - 0 is
Thus for every corner, we compute this approximated gradient and the corresponding
optimal control from (4) and compare it to the optimal policy given by (6).

Figure

11 shows the discretization obtained by splitting the rectangles where these
two measures of the optimal control diverge.
This criterion is interesting since it splits at the places where there is a change in
the optimal control, thus refining the resolution at the most important parts of the
state space for the approximation of the optimal control. However, as we can expect,
if we only use this criterion, the value function will not be well approximated, thus
this process may converge to a sub-optimal performance. Indeed, we can observe
that on Figure 11, the bottom part of frontier 2 is (lightly) situated higher than its
optimal position, illustrated on Figure 5. This results in an underestimation of the
value function at this area because of the lack of precision around the discontinuity
(frontier 1). In section 7.3, we will observe that the performance of the discretization
resulting from this splitting criterion is relatively weak.
However, this splitting criterion can be beneficially combined with the previous
ones based on the approximation of the VF.
7.2. Combination of several criteria
We can combine the policy disagreement criterion with the corner-value difference
or value non-linearity criterion in order to take the advantages of both methods : a
good approximation of the value function on the whole state space and an increase
of the resolution around the areas of change in the optimal control. We can combine
EMI MUNOS AND ANDREW MOORE

Figure

11. The discretization of the state space
using the policy disagreement criterion. Here
we used an initial grid of 33 \Theta 33 and a splitting
rate of 20%.

Figure

12. The discretization of the state space
for the "Car on the Hill" problem using the
combination of the value non-linearity and the
policy disagreement criterion.
the previous criteria in several ways, for example by a weighted sum of the respective
criteria, by a logical operation (split if an and/or combination of these criteria is
satisfied), by an ordering of the criteria (first split with one criterion, then use an
other one), etc.

Figure

12 shows the discretization obtained by alternatively, between iterations,
using the value non-linearity criterion (to obtain a good approximation of the value
function) and the policy disagreement criterion (to increasing the accuracy around
the area of change in the optimal control).
7.3. Comparison of the performance
In order to compare the respective performance of the discretizations, we ran a set
(here 256) of optimal trajectories (using the feed-back control law (4)) starting from
initial states regularly situated in the state space. The performance of a discretization
is the sum of the cumulated reinforcement (the gain defined by equation (2))
obtained by these trajectories, over the set of start positions.

Figure

13 shows the respective performances of several splitting criteria as a
function of the number of states.
In this 2 dimensional control problem, the variable resolution approach perform
much better (except for the policy disagreement criterion alone) than the uniform
grids. However, as we will see later, for higher dimensional problems, the ressources
allocated to approximate the discontinuities of the VF in areas not useful for improving
the optimal control might be prohibitely high.
Can we do better ?
So far, we have only considered local splitting criteria, in the sense that we decide
VARIABLE RESOLUTION DISCRETIZATION IN OPTIMAL CONTROL 13

Figure

13. The performance
for the uniform versus variable
resolution grids for several
splitting criterion. Both the
corner-value difference and
value non-linearity splitting
processes perform better than
the uniform grids. The policy
disagreement splitting is very
good for a small number of
states but does not improve
after, and thus leads to sub-optimal
performance. The
policy disagreement combined
with the value non-linearity
gives the best performances.
whether or not to split a rectangle according to information (value function and
policy) relative to the rectangle itself. However, the effect of the splitting is not
local : it has an influence on the whole state space.
We will thus try to see if it is possible to find a better refinement process that could
split an area if and only if it is useful to improve the performance. Sections that
follow presents two notions which will be useful for defining such a global splitting
criterion : the influence, which measures the extend to which local changes in
some state effect the global VF, and the variance, which measures how accurate
the current approximated VF is.
8. Notion of influence
Let us consider the Markov chain resulting from the choice of the control for the
optimal policy u  of the MDP. For convenience reasons, let us denote
8.1. Intuitive idea
The intuitive idea of the influence I(- i j-) of a state - i on another state - is to give
a measure of to what extend the VF of state - i "contributes" to the VF of state -,
i.e. the change in the VF at - resulting from a modification of the VF at - i .
But the VF is the solution of a Bellman equation which depends on the structure
of the Markov chain and the reinforcement values, thus we cannot modify the value
at some state - i , without violating Bellman equation.
However, we notice that the value function at state - i is affected linearly by the
reinforcement obtained at state -, thus we can compute the "contribution" of state
- i to state - by estimating the change in the VF at - resulting from a modification
of the reinforcement R(- i ).
EMI MUNOS AND ANDREW MOORE
8.2. Definition of the influence
Let us define the discounted cumulative k\Gammachained probabilities p k (- i j-), which
represent the sum of the discounted transition probabilities of all sequences of k
states from - to
Definition 1. Let - 2 \Xi. We define the influence of a state - i on the state - being
the quantity : I(- i
\Sigma be a subset of \Xi. We define the
influence of a state - i on the subset \Sigma being the quantity : I(- i
We call influencers of a state - (respectively of a subset \Sigma), the set of states
that have a non-zero influence on - (resp. on \Sigma) (note, by definition, that all
influences are non-negative).
8.3. Some properties of the influence
First, we notice that if the times -) are ? 0, then the influence is well defined
and is bounded by : I(- i
with -). Indeed, from the
definition of the discounted chained-probabilities, we have
Moreover, we can relate the definition to the intuitive idea previously stated and
the following properties hold :
ffl The influence I(- i j-) is the partial derivative of V (-) by R(-
ffl For any states - and - i , we have :
Proof : The Bellman equation is
applying
Bellman equation to V (- i ), we have :
From the definition of p 2 , we can rewrite this as :
Again we can apply Bellman equation to V (- i ) and finally deduce that :
Thus the contribution of R(- i ) to V (-) is : @V (-)
VARIABLE RESOLUTION DISCRETIZATION IN OPTIMAL CONTROL 15
Property (8) is easily deduced from the very definition of the influence and the
chained probability property (7), since for all -,
8.4. Computation of the influence
Equation (8) is not a Bellman equation since the sum of the probabilities
may be greater than 1, so we cannot deduce that the successive iterations :
I n+1 (- i
converge to the influence by using the classical contraction property in max-norm
(Puterman, 1994). However, we have the following property :
Thus, by denoting I(\Xij-) the vector whose components are the I(- i j-) and by
introducing the 1-norm jjI(\Xij-)jj
we deduce that :
and we have the contraction property in the 1-norm which insures convergence of
the iterated I n (- i j-) to the unique solution (the fixed point) I(- i j-) of (8).
8.5. Illustration on the "Car on the Hill" problem
For any
subset\Omega\Gamma we can compute
its influencers. As an exam-
ple, figure 14 shows the influencers
of some 3 points.

Figure

14. Influencers of 3 points (the
crosses). The darker the gray level, the
more important the influence. We notice
that the influence of a state "follows" the
direction of the optimal trajectory starting
from that state (see figure 5) through
some kind of "diffusion process".
EMI MUNOS AND ANDREW MOORE
Let us define the subset \Sigma to be those states of policy disagreement (in the sense of
section 7.1). Figure 15(a) shows \Sigma for a regular grid of 129 \Theta 129. The influencers
of \Sigma is computed and plotted in Figure 15(b). The darkest zones in Figure 15(b)
are the places whose splitting will most affect the value function at the places
(illustrated in Figure 15(a)) of change in the optimal control.
(a) States of policy disagreement (b) Influence of these states

Figure

15. The set of states of policy disagreement (a) and its influencers (b).
Now we would like to define the areas whose refinement could lead to the highest
quantitative change on the value function. This is closely related to the quality of
the approximation of the value function for a given discretization.
Indeed, the better the approximation, the lower a change in the value function
may result from a splitting. In the following section, we introduce the variance of
the Markov chain in order to estimate the quality of approximation of the VF for
the current discretization, thus defining the areas whose splitting may lead to the
highest change in the VF.
9. Variance of a Markov chain
By using the notation of the previous section, Bellman equation states that
\GammaR at - is a discounted average of the next
values weighted by the probabilities of transition p(- i j-). We are interested in
computing the variance of the next values in order to get an estimation of the range
of the values averaged by V (-). The first idea is to compute the one-step-ahead
variance e(-) of V
\Theta
However, the values V (- i ) also average some successive values V (- j ), so we would
like that the variance also takes into account this second-step-ahead average, as well
as all the following ones. The next sections define the value function as an averager
of the reinforcements and present the definition of the variance of a Markov chain.
VARIABLE RESOLUTION DISCRETIZATION IN OPTIMAL CONTROL 17
9.1. The value function as an averager of the reinforcements
Let us denote s k (-) a sequence of first
one is -. Let S k (-) be the set of all possible sequences s k (-). Let p(s k
the product of the probabilities of transition of the successive states
in a sequence, and for
the cumulated time of the
th first states of the sequence (with by definition - 0 (s k
We have the following property :
sk (-)2Sk (-) p(s k 1. We can prove that
the value function satisfies the following equation (similar to the Bellman equation
but for k-steps-ahead) : for any k,
sk (-)2Sk (-) p(s k (-))
Let us denote s 1 (-) an infinite sequence of states starting with -, and S1 (-)
the set of all possible such sequences. Define p(s 1
defined as previously for any i - 0. Then we still have the property :
and the value function satisfies :
9.2. Definition of the Variance of a Markov chain
Intuitively, the variance of a state - is a measure of how dissimilar the cumulative
future reward obtained along all possible trajectories starting from - are. More
precisely, we define it as the variance of the quantities averaged in equation
Definition 2. Let - 2 \Xi. We define the variance oe 2 of the Markov chain at
Let us prove that the variance satisfies a Bellman equation. By selecting out the
case in the summation, we have :
\Theta P 1
R(-))and from (11), we deduce that :
\Theta
\Theta
By successively applying (11) to - 1 and by selecting out the state - i in the sequence
\Theta
\Theta P 1
\Theta
EMI MUNOS AND ANDREW MOORE
with e(-) satisfying (10). Thus the variance oe 2 (-) is the sum of the immediate
contribution e(-) that takes into account the variation in the values of the immediate
successors - i , and the discounted average of the variance oe 2 (- i ) of these successors.
This is a Bellman equation and it can be solved by value iteration.
Remark. We can give a geometric interpretation of the term e(-) related to the
gradient of the value function at the iterated point
to the barycentric coordinates - i
(j). Indeed, from the definition of the discretized
MDP (section 3.2), we have V (j) and from the piecewise
linearity of the approximated functions we have V (-
thus
(j):fl 2-) [DV (j):(- which can be expressed as :
with the matrix Q(j) defined by its elements
Thus, e(-) is close to 0 in two specific cases : either if the gradient at the iterated
point j is very low (i.e. the values are almost constant) or if j is very close to one
vertex (then the barycentric coordinate - i
is close to 1 and the - j
(for
are close to 0, thus Q(j) is low). In both of these cases, e(-) is low and implies that
the iteration of - does not lead to a degradation of the quality of approximation of
the value function (the variance does not increase).
9.3. Example : variance of the "Car on the Hill"

Figure

shows the standard deviation oe(-) for the Car-on-the-Hill problem for a
uniform grid (of 257 by 257).

Figure

16. The standard deviation oe for
the "Car on the Hill". The standard deviation
is very high around the
indeed, a discontinuity is impossible to ap-
proximateperfectly by discretization tech-
niques, whatever the resolution is. We can
observe this fact on figure 10 where the
maximal error of approximation is equal
to half the step of the discontinuity. How-
ever, the higher the resolution is, the lower
the integral of the error is (compare figure
10(a)&(c) versus (b)&(d)). There is
a noticeable positive standard deviation
around frontier 3 and the upper part of
because the value function is
an average of different values of the discounted
terminal reinforcement.
A refinement of the resolution in the areas where the standard deviation is low
has no chance of producing an important change in the value function. Thus it
appears that the areas where a splitting might affect the most the approximation
of the value function are the rectangles of highest surface whose corners have the
highest standard deviations.
VARIABLE RESOLUTION DISCRETIZATION IN OPTIMAL CONTROL 19
10. A global splitting criterion
Now we are going to combine the notions of influence and variance in order to
define a new, non-local splitting criterion. We have seen that :
ffl The states - of highest standard deviation oe(-) are the states of lowest quality
of approximation of the VF, thus the states that could improve the most their
approximation accuracy when split (figure 17(a)).
ffl The states - of highest influence on the set \Sigma of states of policy disagreement
(figure 15(b)) are the states whose value function affects the area where there
is a change in the optimal control.
Thus in order to improve the precision of approximation at the most relevant
areas of the state space we split the states - of highest standard deviation that
have an influence on the areas of change in the optimal control, according to the
Stdev Inf criterion (see figure Figure shows
the discretization obtained by using this splitting criterion.
(a) Standard deviation (b) Influence x Standard deviation

Figure

17. (a) The standard deviation oe(-) for the "Car on the Hill" (equivalent to figure 16) and
(b) The Stdev Inf criterion, product of oe(-) by the influence I(-j\Sigma) (figure 15(b)).

Figure

18. The discretization resulting of the
Stdev Inf split criterion. We observe that the
upper part of frontier 1 is well refined. This
refinement occurred not because we split according
to the value function (such as the
corner-value difference or value non-linearity
criterion) but because the splitting there is
necessary to have a good approximation of
the value function around the bottom part of
(and even the upper part of frontier
2) where there is a change in the optimal
control.
The fact that the Stdev Inf criterion does not
split the areas where the VF is discontinuous
unless some refinement is necessary to get a
better approximation of the optimal control,
is very important since, as we will see in the
simulations that follow, in higher dimensions,
the cost to get an accurate approximation of
the VF is too high.
EMI MUNOS AND ANDREW MOORE
Remark. The performance of this criterion for the "Car on the Hill" problem are
similar to those of combining the value non-linearity and the policy disagreement
criterion. We didn't plot those performances in figure 13 for clarity reasons and
because they do not represent a major improvement. However, the difference of
performances between the local criteria and the Stdev Inf criterion are much more
significant in the case of more difficult problems (the Acrobot, the Cart-pole) as
illustrated in what follows.
11. Illustration on other control problems
11.1. The Cart-Pole problem
The dynamics of this 4-dimensional physical system (illustrated in figure 19(a))
are described in (Barto et al., 1983). In our experiments, we chose the following
parameters as follows : the state space is defined by the position y 2 [\Gamma10; +10],
angle
velocities restricted to -
2]. The control
consists in applying a strength of \Sigma10 Newton. The goal is defined by the area :
no limits on -
y and -
'). This is a notably narrow
goal to try to hit (see the projection of the state space and the goal on the 2d plan
(y,') in figure 19). Notice that our task of "minimum time manoever to a small
goal region" from an arbitrary start state is much harder than merely balancing
the pole without falling (Barto et al., 1983). The current reinforcement r is zero
everywhere and the terminal reinforcement R is \Gamma1 if the system exits from the
state space (jyj ? 10 or j'j ? -
if the system reaches the goal.
_
_ _
_
y
position
-y 4.3 0.2=
y
Goal
(b) The projection of the state space
(a) The "Cart-pole"

Figure

19. (a) Description of the Cart-pole. (b) The projection of the discretization (onto the
plane (',y)) obtained by the Stdev Inf criterion and some trajectories for several initial points.

Figure

20 shows the performance obtained for several splitting criteria previously
defined for this 4 dimensional control problem. We observe the following points :
VARIABLE RESOLUTION DISCRETIZATION IN OPTIMAL CONTROL 21
ffl The local criteria do not perform better than the uniform grids. The problem
is that the VF is discontinuous at several parts of the state space (areas of high
j'j for which it is too late to rebalance the pole, which is similar to the frontier 1
of the "Car on the Hill" problem) and the value-based criteria spend too many
resources on approximating these useless areas.
ffl The Stdev Inf criterion performs very well. We observe that the trajectories
(see figure 19(b)) are nearly optimal (the angle j'j is maximized in order to
reach the goal as fast as possible, and very close to its limit value, for which it
is no more possible to recover the balance).

Figure

20. Performance on the "Cart-pole". Figure 21. Performance on the Acrobot.
11.2. The Acrobot
The Acrobot is a 4 dimensional control problem which consists of a two-link arm
with one single actuator at the elbow. This actuator exerts a torque between the
links (see figure 22(a)). It has dynamics similar to a gymnast on a high bar, where
Link 1 is analogous to the gymnast's hands, arms and torso, Link 2 represents the
legs, and the joint between the links is the gymnast's waist (Sutton, 1996). Here,
the goal of the controller is to balance the Acrobot at its unstable, inverted vertical
position, in the minimum time (Boone, 1997). The goal is defined by a very narrow
range of -
on both angles around the vertical position
22(b)), for which the system receives a reinforcement of R = +1. Anywhere else,
the reinforcement is zero. The two first dimensions (' of the state space have a
structure of a torus (because of the 2- modulo on the angles), which is implemented
in our structure by having the vertices of 2 first dimensions being angle 0 and 2-
pointing to the same entry for the value function in the interpolated kd-trie.

Figure

21 shows the performance obtained for several splitting criteria previously
defined. The respective performance of the different criteria are similar to the "Cart-
pole" problem above : the local criteria are no better than the uniform grids ; the
Stdev Inf criterion performs much better.

Figure

22(b) shows the projection of the discretization obtained by the Stdev Inf
criterion and one trajectory onto the 2d-plane (' 1 ,' 2 ).
22 R '
EMI MUNOS AND ANDREW MOORE
Goal
Goal
(a) The Acrobot (b) Projection of the state space

Figure

22. (a) Description of the Acrobot physical system. (b) Projection of the discretization
(onto the plane (' 1 ,' 2 )) obtained by the Stdev Inf criterion, and one trajectory.
Interpretation of the results : As we noticed for the two previous 4d prob-
lems, the local splitting criteria fail to improve the performance of the uniform grids
because they spend too many resources on local considerations (either approximating
the value function or the optimal policy). For example, on the "Cart-pole"
problem, the value non-linearity criterion will concentrate on approximating the
VF mostly at parts of the state space where there is already no chance to rebalance
the pole. And the areas around the vertical position (low '), which are the most
important areas, will not be refined in time (however, if we continue the simulations
after about 90000 states, the local criteria start to perform better than the uniform
grids, because these areas get eventually refined).
The Stdev Inf criterion, which takes into account global consideration for the
splitting, performs very well for all the problems described above.
12. Conclusion and Future work
In this paper we proposed a variable resolution discretization approach to solve
continuous time and space control problems. We described several local splitting
criteria, based on the VF or the policy approximation. We observed that this
approach works well for 2d problems like the "Car on the Hill". However, for more
complex problems, these local methods fail to perform better than uniform grids.
Local value-based splitting is an efficient, model-based, relative of the Q-learning-
based tree splitting criteria used, for example, by (Chapman & Kaelbling, 1991; Si-
mons, Van Brussel, De Schutter, & Verhaert, 1982; McCallum, 1995). But it is only
when combined with new non-local measures that we are able to get truly effec-
tive, near-optimal performance on our control problems. The tree-based state-space
partitions in (Moore, 1991; Moore & Atkeson, 1995) were produced by different criteria
(of empirical performance), and produced far more parsimonious trees, but
no attempt was made to minimize cost: merely to find a valid path.
VARIABLE RESOLUTION DISCRETIZATION IN OPTIMAL CONTROL 23
In order to design a global criterion, we introduced the notions of influence which
estimates the impact of states over others, and of variance of a Markov chain, which
measure the quality of the current approximation. By combining these notions,
we defined an interesting splitting criterion that gives very good performance (in
comparison to the uniform grids) on all the problems studied.
Another extension of these measures could be to learn them through interactions
with the environment in order to design efficient exploration policies in reinforcement
learning. Our notion of variance could be used with "Interval Estima-
tion" heuristic (Kaelbling, 1993), to permit "optimism-in-the-face-of-uncertainty"
exploration, or with the "back-propagation of exploration bonuses" of (Meuleau &
Bourgine, 1999) for exploration in continuous state-spaces. Indeed, if we observe
that the learned variance of a state - is high, then a good exploration strategy could
be to inspect the states that have a high expected influence on -.
In the future, it seems important to develop the following points :
ffl A generalization process, in order to have also a "specific towards general"
grouping of areas (for example by pruning the tree) that have been over-refined.
ffl Suppose that we only want to solve the problem for a specific
area\Omega of initial
start states. Then we can restrict our refinement process to the areas used
by the trajectories. The notion of influence introduced in this paper can be
used for that purpose by computing the Stdev Inf criterion with respect to
set of states of policy disagreement that have
an influence on the area of initial
states\Omega\Gamma instead of \Sigma, and can improve
drastically the performance observed when starting from this specific area.
ffl We would like to deal with the stochastic case. If we assume that we have a
model of the noise, then the only change will be in the process of building the
MDP (Kushner & Dupuis, 1992; Munos & Bourgine, 1997).
ffl Release the assumption that we have a model and build an approximation of
the dynamics and the reinforcement, and deal with the exploration problem.



--R

Residual algorithms
Gradient descent for general reinforcement learning.
Convergence of approximation schemes for fully nonlinear second order equations.
Neuronlike Adaptive elements that that can learn difficult Control Problems.
Learning to act using real-time dynamic program- ming
Dynamic Programming



Learning from Delayed Reinforcement In a Complex Domain.
User's guide to viscosity solutions of second order partial differential equations.
Viscosity solutions of hamilton-jacobi equations
Multidimensional Triangulation and Interpolation for Reinforcement Learning.
Rates of convergence for approximation schemes in optimal control.
SIAM Journal Control and Optimization
Controlled Markov Processes and Viscosity Solutions.
An Algorithm for Finding Best Matches in Logarithmic Expected Time.
Stable function approximation in dynamic programming.
Learning in Embedded Systems.
Sorting and Searching.


In Machine Learning
Exploration of multi-state environments: Local measures and back-propagation of uncertainty
Variable Resolution Dynamic Programming: Efficiently Learning Action Maps in Multivariate Real-valued State-spaces
Prioritized sweeping: Reinforcement learning with less data and less real time.
The parti-game algorithm for variable resolution reinforcement learning in multidimensional state space
Simplical Mesh Generation with Applications.
A study of reinforcement learning in the continuous case by the means of viscosity solutions.
Reinforcement learning for continuous stochastic control problems.
Neural Information Processing Systems.
Barycentric interpolators for continuous space and time reinforcement learning.
Markov Decision Processes

Generalization in reinforcement learning
--TR

--CTR
David Wingate , Kevin D. Seppi, P3VI: a partitioned, prioritized, parallel value iterator, Proceedings of the twenty-first international conference on Machine learning, p.109, July 04-08, 2004, Banff, Alberta, Canada
Chee Wee Phua , Robert Fitch, Tracking value function dynamics to improve reinforcement learning with piecewise linear function approximation, Proceedings of the 24th international conference on Machine learning, p.751-758, June 20-24, 2007, Corvalis, Oregon
Philipp W. Keller , Shie Mannor , Doina Precup, Automatic basis function construction for approximate dynamic programming and reinforcement learning, Proceedings of the 23rd international conference on Machine learning, p.449-456, June 25-29, 2006, Pittsburgh, Pennsylvania
Sbastien Jodogne , Justus H. Piater, Interactive learning of mappings from visual percepts to actions, Proceedings of the 22nd international conference on Machine learning, p.393-400, August 07-11, 2005, Bonn, Germany
Feng , Richard Dearden , Nicolas Meuleau , Richard Washington, Dynamic programming for structured continuous Markov decision problems, Proceedings of the 20th conference on Uncertainty in artificial intelligence, p.154-161, July 07-11, 2004, Banff, Canada
Duncan Potts , Claude Sammut, Incremental Learning of Linear Model Trees, Machine Learning, v.61 n.1-3, p.5-48, November  2005
Florian Bauer , Lars Grne , Willi Semmler, Adaptive spline interpolation for Hamilton-Jacobi-Bellman equations, Applied Numerical Mathematics, v.56 n.9, p.1196-1210, September 2006
Theodore J. Perkins , Andrew G. Barto, Lyapunov design for safe reinforcement learning, The Journal of Machine Learning Research, 3, 3/1/2003
Lars Grne , Willi Semmler, Asset pricing with dynamic programming, Computational Economics, v.29 n.3-4, p.233-265, May       2007
optimal control;reinforcement learning;variable resolution discretization;adaptive mesh refinement