A Study of Reinforcement Learning in the Continuous Case by the Means of Viscosity Solutions.
This paper proposes a study of Reinforcement Learning (RL) for continuous state-space and time control problems, based on the theoretical framework of viscosity solutions (VSs). We use the method of dynamic programming (DP) which introduces the value function (VF), expectation of the best future cumulative reinforcement. In the continuous case, the value function satisfies a non-linear first (or second) order (depending on the deterministic or stochastic aspect of the process) differential equation called the Hamilton-Jacobi-Bellman (HJB) equation. It is well known that there exists an infinity of generalized solutions (differentiable almost everywhere) to this equation, other than the VF. We show that gradient-descent methods may converge to one of these generalized solutions, thus failing to find the optimal control.In order to solve the HJB equation, we use the powerful framework of viscosity solutions and state that there exists a unique viscosity solution to the HJB equation, which is the value function. Then, we use another main result of VSs (their stability when passing to the limit) to prove the convergence of numerical approximations schemes based on finite difference (FD) and finite element (FE) methods. These methods discretize, at some resolution, the HJB equation into a DP equation of a Markov Decision Process (MDP), which can be solved by DP methods (thanks to a strong contraction property) if all the initial data (the state dynamics and the reinforcement function) were perfectly known. However, in the RL approach, as we consider a system in interaction with some a priori (at least partially) unknown environment, which learns from experience, the initial data are not perfectly known but have to be approximated during learning. The main contribution of this work is to derive a general convergence theorem for RL algorithms when one uses only approximations (in a sense of satisfying some weak contraction property) of the initial data. This result can be used for model-based or model-free RL algorithms, with off-line or on-line updating methods, for deterministic or stochastic state dynamics (though this latter case is not described here), and based on FE or FD discretization methods. It is illustrated with several RL algorithms and one numerical simulation for the Car on the Hill problem.
Introduction
This paper is about Reinforcement Learning (RL) in the continuous state-space and
time case. RL techniques (see (Kaelbling, Littman, & Moore, 1996) for a survey)
are adaptive methods for solving optimal control problems for which only a partial
amount of initial data are available to the system that learns. In this paper, we
focus on the Dynamic Programming (DP) method which introduces a function,
EMI MUNOS
called the value function (VF) (or cost function), that estimates the best future
cumulative reinforcement (or cost) as a function of initial states.
RL in the continuous case is a difficult problem for at least two reasons. Since we
consider a continuous state-space, the first reason is that the value function has
to be approximated, either by using discretization (with grids or triangulations) or
general approximation (such as neural networks, polynomial functions, fuzzy sets,
etc.) methods. RL algorithms for continuous state-space have been implemented
with neural networks (see for example (Barto, Sutton, & Anderson, 1983), (Barto,
1990), (Gullapalli, 1992), (Williams, 1992), (Lin, 1993), (Sutton & Whitehead,
1993), (Harmon, Baird, & Klopf, 1996), and (Bertsekas & Tsitsiklis, 1996)), fuzzy
sets (see (Now'e, 1995), (Glorennec & Jouffe, 1997)), approximators based on state
aggregation (see (Singh, Jaakkola, & Jordan, 1994)), clustering (see (Mahadevan
sparse-coarse-coded functions (see (Sutton, 1996)) and variable
resolution grids (see (Moore, 1991), (Moore & Atkeson, 1995)). However, as it has
been pointed out by several authors, the combination of DP methods with function
approximators may produce unstable or divergent results even when applied to
very simple problems (see (Boyan & Moore, 1995), (Baird, 1995), (Gordon, 1995)).
Some results using clever algorithms (like Residual algorithms of (Baird, 1995)) or
particular classes of approximation functions (like the Averagers of (Gordon, 1995))
can lead to the convergence to a local or global solution within the class of functions
considered.
Anyway, it is difficult to define the class of functions (for a neural network, the
suitable architecture) within which the optimal value function could be approxi-
mated, knowing that we have little prior knowledge of its smoothness properties.
The second reason is because we consider a continuous-time variable. Indeed,
the value function derived from the DP equation (see (Bellman, 1957)), relates
the value at some state as a function of the values at successor states. In the
continuous-time limit, as the successor states get infinitely closer, the value at
some point becomes a function of its differential, defining a non linear differential
equation, called the Hamilton-Jacobi-Bellman (HJB) equation.
In the discrete-time case, the resolution of the Markov Decision Process (MDP)
is equivalent to the resolution, on the whole state-space, of the DP equation ; this
property provides us with DP or RL algorithms that locally solve the DP equation
and lead to the optimal solution. With continuous time, it is no longer the case
since the HJB equation holds only if the value function is differentiable. And in
general, the value function is not differentiable everywhere (even for smooth initial
data), thus this equation cannot be solved in the usual sense, because this leads to
either no solution (if we look for classical solutions, i.e. differentiable everywhere)
or an infinity of solutions (if we look for generalized solutions, i.e. differentiable
almost everywhere).
This fact, which will be illustrated with a very simple 1-dimensional example,
explains why there could be many "bad" solutions to gradient-descent methods for
RL. Indeed, such methods intend to minimize the integral of some Hamiltonian.
But the generalized solutions of the HJB equation are global optima of this problem,
REINFORCEMENT LEARNING BY THE MEANS OF VISCOSITY SOLUTIONS 3
so the gradient-descent methods may lead to approximate any (among an infinity
of) generalized solutions giving little chance to reach the desired value function.
In order to deal with the problem of integrating the HJB equation, we use the
formalism of Viscosity Solutions (VSs), introduced by Crandall and Lions (in (Cran-
dall & Lions, 1983) ; see the user's guide (Crandall, Ishii, & Lions, 1992)) in order
to define an adequate class (which appears as a weak formulation) of solutions to
non-linear first (and second) order differential equation such as HJB equations.
The main properties of VSs are their existence, their uniqueness and the fact that
the value function is a VS. Thus, for a large class of optimal control problems, there
exists a unique VS to the HJB equation, which is the value function. Furthermore,
VSs have remarkable stability properties when passing to the limit, from which we
can derive proofs of convergence for discretization methods.
Our approach here consists in defining a class of convergent numerical schemes,
among which are the finite element (FE) and finite difference (FD) approximation
schemes introduced in (Kushner, 1990) and (Kushner & Dupuis, 1992) to discretize,
at some resolution ffi , the HJB equation into a DP equation for some discrete Markov
Decision Process. We apply a result of convergence (from (Barles & Souganidis,
1991)) to prove the convergence of the value function V ffi of the discretized MDP to
the value function V of the continuous problem as the discretization step ffi tends
to zero.
The DP equation of the discretized MDP could be solved by any DP method
(because the DP equation satisfies a "strong" contraction property leading successive
iterations to converge to the value function, the unique fixed point of this
equation), but only if the data (the transition probabilities and the reinforcements)
were perfectly known by the learner, which is not the case in the RL approach.
Thus, we propose a result of convergence for RL algorithms when we only use
"approximations" of these data (in the sense that the approximated DP equation
need to satisfy some "weak" contraction property). The convergence occurs as the
number of iterations tends to infinity and the discretization step tends to zero.
This result applies to model-based or model-free RL algorithms, for off-line or on-line
methods, for deterministic or stochastic state dynamics, and for FE or FD
based discretization methods. It is illustrated with several RL algorithms and one
numerical simulation for the "Car on the Hill" problem.
In what follows, we consider the discounted, infinite-time horizon case (for a
description of the finite-time horizon case, see (Munos, 1997a)) with deterministic
state dynamics (for the stochastic case, see (Munos & Bourgine, 1997) or (Munos,
1997a)).
Section 2 introduces the formalism for RL in the continuous case, defines the
value function, states the HJB equation and presents a result showing continuity
of the VF.
Section 3 illustrates the problems of classical solutions to the HJB equation with
a simple 1-dimensional example and introduces the notion of viscosity solutions.
Section 4 is concerned with numerical approximation of the value function using
discretization schemes. The finite element and finite difference methods are
EMI MUNOS
presented and a general convergence theorem (whose proof is in appendix A) is
stated.
Section 5 states a convergence theorem (whose proof is in appendix B) for a
general class of RL algorithms and illustrates it with several algorithms.
Section 6 presents a simple numerical simulation for the "Car on the Hill" problem

2. A formalism for reinforcement learning in the continuous case
The objective of reinforcement learning is to learn from experience how to influence
the behavior of a dynamic system in order to maximize some payoff function
called the reinforcement or reward function (or equivalently to minimize some cost
function). This is a problem of optimal control in which the state dynamics and
the reinforcement function are, a priori, at least partially unknown.
In this paper we are concerned with deterministic problems in which the dynamics
of the system is governed by a controlled differential equation. For similar results
in the stochastic case, see (Munos & Bourgine, 1997), (Munos, 1997a), for a related
work using multi-grid methods, see (Pareigis, 1996).
The two possible approaches for optimal control are Pontryagin's maximum principle
(for theoretical work, see (Pontryagin, Boltyanskii, Gamkriledze, & Mischenko,
1962) and more recently (Fleming and Rishel1975), for a study of Temporal Differ-
ence, see (Doya, 1996), and for an application to the control with neural networks,
see (Bersini & Gorrini, 1997)) and the Bellman's Dynamic Programming (DP) (in-
troduced in (Bellman, 1957)) approach considered in this paper.
2.1. Deterministic optimal control for discounted infinite-time horizon problems
In what follows, we consider infinite-time horizon problems under the discounted
framework. In that case, the state dynamics do not depend on the time. For a
study of the finite time horizon case (for which there is a dependency in time), see
(Munos, 1997a).
Let x(t) be the state of the system, which belongs to the state-space O, closure of
an open subset O ae IR d . The evolution of the system depends on the current state
x(t) and control (or action) u(t) 2 U , where U , closed subset, is the control space ;
it is defined by the controlled differential equation :
dt
where the control u(t) is a bounded, Lebesgue measurable function with values in
U . The function f is called the state dynamics. We assume that f is Lipschitzian
with respect to the first variable : there exists some constant L f ? 0 such that :
For initial state x 0 at time the choice of a control u(t) leads to a unique
(because the state dynamics (1) is deterministic) trajectory x(t) (see figure 1).
REINFORCEMENT LEARNING BY THE MEANS OF VISCOSITY SOLUTIONS 5
Definition 1. We define the discounted reinforcement functional J , which depends
on initial data x 0 and control u(t) for 0 - t - , with - the exit time of x(t)
from O (with the trajectory always stays inside O) :
with r(x; u) the current reinforcement (defined on O) and R(x) the boundary reinforcement
(defined on @O, the boundary of the state-space). fl 2 [0; 1) is the
discount factor which weights short-term rewards more than long-term ones (and
ensures the convergence of the integral).
The objective of the control problem is to find, for any initial state x 0 , the
control u   (t) that optimizes the reinforcement functional J(x
x

Figure

1. The state-space O. From initial state x 0 at the choice of control u(t) leads to the
trajectory x(t) for 0 - t -; where - is the exit time from the state-space.
Remark. Unlike the discrete case, in the continuous case, we need to consider
two different reinforcement functions : r is obtained and accumulated during the
running of the trajectory, whereas R occurs whenever the trajectory exits from the
state-space (if it does). This formalism enables us to consider many optimal control
problem, such as reaching a target while avoiding obstacles, viability problems, and
many other optimization problems.
Definition 2. We define the value function, the maximum value of the reinforcement
functional as a function of initial state at time
EMI MUNOS
Before giving some properties of the value function (HJB equation, continuity and
differentiability properties), let us first describe the reinforcement learning frame-work
considered here and the constraints it implies.
2.2. The reinforcement learning approach
RL techniques are adaptive methods for solving optimal control problems whose
data are a priori (at least partially) unknown. Learning occurs iteratively, based
on the experience of the interactions between the system and the environment,
through the (current and boundary) reinforcement signals.
The objective of RL is to find the optimal control, and the techniques used are
those of DP. However, in the RL approach, the state dynamics f(x; u), and the
reinforcement functions r(x; u); R(x) are partially unknown to the system. Thus
RL is a constructive and iterative process that estimates the value function by
successive approximations.
The learning process includes both a mechanism for the choice of the control,
which has to deal with the exploration versus exploitation dilemma (exploration
provides the system with new information about the unknown data, whereas exploitation
consists in optimizing the estimated values based on the current knowl-
edge) (see (Meuleau, 1996)), and a mechanism for integrating new information for
refining the approximation of the value function. The latter topic is the object of
this paper.
The study and the numerical approximations of the value function is of great
importance in RL and DP because from this function we can deduce an optimal
feed-back controller. The next section shows that the value function satisfies a local
property, called the Hamilton-Jacobi-Bellman equation, and points out its relation
to the optimal control.
2.3. The Hamilton-Jacobi-Bellman equation
Using the dynamic programming principle (introduced in (Bellman, 1957)), we can
prove that the value function satisfies a local condition, called the Hamilton-Jacobi-
Bellman (HJB) equation (see (Fleming & Soner, 1993) for a complete survey). In
the deterministic case studied here, it is a first-order non-linear partial differential
equation (in the stochastic case, we can prove that a similar equation of order two
holds). Here we assume that U is a compact set.
Theorem 1 (Hamilton-Jacobi-Bellman) If the value function V is differentiable
at x, let DV (x) be the gradient of V at x, then the Hamilton-Jacobi-Bellman
u2U
holds at x 2 O. Additionally, V satisfies the following boundary condition :
REINFORCEMENT LEARNING BY THE MEANS OF VISCOSITY SOLUTIONS 7
Remark. The boundary condition is an inequality because at some boundary point
(for example at x 1 2 @O on figure 1) there may exist a control u(t) such that
the corresponding trajectory stays inside O and whose reinforcement functional is
strictly superior to the immediate boundary reinforcement R(x 1 ). In such cases,
holds with a strict inequality.
Remark. Using an equivalent definition, the HJB equation (5) means that V is
the solution of the equation :
with the Hamiltonian H defined, for any differentiable function W , by :
u2U
Dynamic programming computes the value function in order to find the optimal
control with a feed-back control policy, that is a function -(x) : O ! U such that
the optimal control u   (t) at time t depends on current state x(t) : u
Indeed, from the value function, we deduce the following optimal feed-back control
policy
u2U
Now that we have pointed out the importance of computing the value function
for defining the optimal control, we show some properties of V (continuity, dif-
ferentiability) and how to integrate (and in what sense) the HJB equation for approximating
.
2.4. Continuity of the value function
The property of continuity of the value function may be obtained under the following
assumption concerning the state dynamics f around the boundary @O (which
is assumed smooth, i.e. @O 2 C
For all x 2 @O, let \Gamma! n (x) be the outward normal of O at x (for example, see
figure 1), we assume that :
These hypotheses mean that at any point of the boundary, there ought not be only
trajectories tangential to the boundary of the state space.
Theorem 2 (Continuity) Suppose that (2) and (9) are satisfied, then the value
function is continuous in O.
The proof of this theorem can be found in (Barles & Perthame, 1990).
EMI MUNOS
3. Introduction to viscosity solutions
From theorem 1, we know that if the value function is differentiable then it solves
the HJB equation. However, in general, the value function is not differentiable
everywhere even when the data of the problem are smooth. Thus, we cannot expect
to find classical solutions (i.e. differentiable everywhere) to the HJB equation. Now,
if we look for generalized solutions (i.e. differentiable almost everywhere), we find
that there are many solutions other than the value function that solve the HJB
equation.
Therefore, we need to define a weak class of solutions to this equation. Crandall
and Lions introduced such a weak formulation by defining the notion of Viscosity
Solutions (VSs) in (Crandall & Lions, 1983). For a complete survey, see (Crandall
et al., 1992), (Barles, 1994) or (Fleming & Soner, 1993). This notion has been
developed for a very broad class of non-linear first and second order differential
equations (including HJB equations for the stochastic case of controlled diffusion
processes). Among the important properties of viscosity solutions are some uniqueness
results, the stability of solutions to approximated equations when passing to
the limit (this very important result will be used to prove the convergence of the
approximation schemes in section 4.4) and mainly the fact that the value function is
the unique viscosity solution of the HJB equation (5) with the boundary condition
(6).
First, let us illustrate with a simple example the problems raised here when one
looks for classical or generalized solutions to the HJB equation.
3.1. 3 problems illustrated with a simple example
Let us study a very simple control problem in 1 dimension. Let the state x(t) 2
[0; 1], the control u(t) 2 f\Gamma1; +1g and the state dynamics be : dx
Consider a current reinforcement everywhere and a boundary reinforcement
defined by R(0) and R(1). In this example, we deduce that the value function is :
and the HJB equation is :
with the boundary conditions V (0) - R(0) and V (1) - R(1):
1. First problem : there is no classical solution to the HJB equation.
0:3. The corresponding value function is
plotted in figure 2. We observe that V is not differentiable everywhere, thus
does not satisfy the HJB equation everywhere : there is no classical solution to
the HJB equation.
REINFORCEMENT LEARNING BY THE MEANS OF VISCOSITY SOLUTIONS 9
x
Optimal
Value function

Figure

2. The value function is not differentiable everywhere.
2. Second problem : there are several generalized solutions.
If one looks for generalized solutions that satisfy the HJB equation almost
everywhere, we find many functions other than the value function. An example
of a function satisfying (11) almost everywhere with the boundary conditions
is illustrated in figure 3.
x
Optimal
Value function

Figure

3. There are many generalized solutions other than the value function.
Remark. This problem is of great importance when one wants to use gradient-descent
methods with some general function approximator, like neural networks,
to approximate the value function. The use of gradient-descent methods may
lead to approximate any of the generalized solutions of the HJB equation and
thus fail to find the value function. Indeed, suppose that we use a gradient-descent
method for finding a function W minimizing the error :
EMI MUNOS
Z
x2O
with H the Hamiltonian defined in section 2.3. Then, the method will converge,
in the best case, to any generalized solution V g of (7) (because these functions
are global optima of this minimization problem, since their error E(V
which are probably different from the value function V . Moreover the control
induced by such functions (by the closed loop policy (8)) might be very different
from the optimal control (defined by V ). For example, the function plotted in
figure 3 generates a control (given by the direction of the gradient) very different
from the optimal control, defined by the value function plotted in figure 2.
In fact, in such continuous time and space problems, there exists an infinity of
global minima for gradient descent methods, and these functions may be very
different from the expected value function.
In the case of neural networks, we usually use smooth functions (differentiable
everywhere), thus neither the value function V (figure 2), nor a generalized
solution V g (figure 3) can be exactly represented, but both can be approximated.
Let us denote ~
V and ~
, the best approximations of V and V g in the network.
Then ~
V and ~
are local minima of the gradient-descent method minimizing E,
but nothing proves that ~
V is a global minimum. In this example, it could seem
that V is "smoother" than the generalized solutions (because it has only one
discontinuity instead of several ones) in the sense that E( ~
E( ~
is not true in general. In any case, in the continuous-time case, when we use
a smooth function approximator, there exists an infinity of local solutions for
the problem of minimizing the error E and nothing proves that the expected
~
V is a global solution. See (Munos, Baird, & Moore, 1999) for some numerical
experiments on simple (one and two dimensional) problems.
When time is discretized, this problem disappears, but we still have to be careful
when passing to the limit. In this paper, we describe discretization methods
that converge to the value function when passing to the limit of the continuous
case.
3. Third problem : the boundary condition is an inequality.
Here we illustrate the problem of the inequality of the boundary condition. Let
5. The corresponding value function is plotted in figure 4.
We observe that V (0) is strictly superior to the boundary reinforcement R(0).
This strict inequality occurs at any boundary point x 2 @O for which there
exists a control u(t) such that the trajectory goes immediately inside O and
generates a better reinforcement functional than the boundary reinforcement
R(x) obtained by exiting from O at x:
We will give (in definition 4 that follows) a weak (viscosity) formulation of the
boundary condition (6).
REINFORCEMENT LEARNING BY THE MEANS OF VISCOSITY SOLUTIONS 11
x
Value function

Figure

4. The boundary condition may hold with a strict inequality condition
3.2. Definition of viscosity solutions
In this section, we define the notion of viscosity solutions for continuous functions
(a definition for discontinuous functions is given in appendix A).
Definition 3 (Viscosity solution). Let W be a continuous real-valued function
defined in O.
ffl W is a viscosity sub-solution of (7) in O if for all functions '
local maximum of W \Gamma ' such that W
ffl W is a viscosity super-solution of (7) in O if for all functions '
local minimum of W \Gamma ' such that W
ffl W is a viscosity solution of (7) in O if it is a viscosity sub-solution and a viscosity
super-solution of (7) in O:
3.3. Some properties of viscosity solutions
The following theorem (whose proof can be found in (Crandall et al., 1992)) states
that the value function is a viscosity solution.
Theorem 3 Suppose that the hypotheses of Theorem 2 hold. Then the value function
V is a viscosity solution of (7) in O:
EMI MUNOS
In order to deal with the inequality of the boundary condition (6), we define
a viscosity formulation in a differential type condition instead of a pure Dirichlet
condition.
Definition 4 (Viscosity boundary condition). Let W be a continuous real-valued
function defined in O,
ffl W is a viscosity sub-solution of (7) in O with the boundary condition (6) if it
is a viscosity sub-solution of (7) in O and for all functions '
local maximum of W \Gamma ' such that W
minfH(x;W;DW
ffl W is a viscosity super-solution of (7) in O with the boundary condition (6) if it
is a viscosity super-solution of (7) in O and for all functions '
local minimum of W \Gamma ' such that W
minfH(x;W;DW
ffl W is a viscosity solution of (7) in O with the boundary condition (6) if it is a
viscosity sub- and super-solution of (7) in O with the boundary condition (6).
Remark. When the Hamiltonian H is related to an optimal control problem
(which is the case here), the condition (13) is simply equivalent to the boundary
inequality (6).
With this definition, theorem 3 extends to viscosity solutions with boundary
conditions. Moreover, from a result of uniqueness, we obtain the following theorem
(whose proof is in (Crandall et al., 1992) or (Fleming & Soner,
Theorem 4 Suppose that the hypotheses of theorem 2 hold. Then the value function
V is the unique viscosity solution of (7) in O with the boundary condition
(6).
Remark. This very important theorem shows the relevance of the viscosity solutions
formalism for HJB equations. Moreover this provides us with a very useful
framework (as will be illustrated in next few sections) for proving the convergence
of numerical approximations to the value function.
Now we study numerical approximations of the value function. We define approximation
schemes by discretizing the HJB equation with finite element or finite
difference methods, and prove the convergence to the viscosity solution of the HJB
equation, thus to the value function of the control problem.
4. Approximation with convergent numerical schemes
4.1.

Introduction

The main idea is to discretize the HJB equation into a Dynamic Programming
(DP) equation for some stochastic Markovian Decision Process (MDP). For any
resolution ffi , we can solve the MDP and find the discretized value function V ffi by
using DP techniques, which are guaranteed to converge since the DP equation is
a fixed-point equation satisfying some strong contraction property (see (Puterman,
1994), (Bertsekas, 1987)). We are also interested in the convergence properties of
the discretized V ffi to the value function V as ffi decreases to 0.
From (Kushner, 1990) and (Kushner & Dupuis, 1992), we define two classes
of approximation schemes based on finite difference (FD) (section 4.2) and finite
element methods (section 4.3). Section 4.4 provides a very general theorem of
convergence (deduced from the abstract formulation of (Barles & Souganidis, 1991)
and using the stability properties of viscosity solutions), that covers both FE and
FD methods (the only important required properties for the convergence are the
monotonicity and the consistency of the scheme).
In the following, we assume that the control space U is approximated by finite
control spaces U ffi such that :
ae U
4.2. Approximation with finite difference methods
d be a basis for IR d . The dynamics are Let the
positive and negative parts of f i be
any discretization step ffi , let us consider the lattices : ffi Z
where
are any integers, and \Sigma the frontier of \Sigma ffi , denote
the set of points f- 2 ffi Z d n O such that at least one adjacent point - \Sigma
(see figure 5). Let us denote by jjyjj
the 1-norm of any vector y.
O
S d S d

Figure

5. The discretized state-space \Sigma ffi (the dots) and its frontier @ \Sigma ffi (the crosses).
EMI MUNOS
The FD method consists of replacing the gradient DV (-) by the forward and
backward difference quotients of V at - 2 \Sigma ffi in direction e
Thus the HJB equation can be approximated by the following equation :
Knowing that (\Deltat ln fl) is an approximation of (fl \Deltat \Gamma 1) as \Deltat tends to 0, we deduce
the following equivalent approximation equation : for - 2 \Sigma ffi ,
with p(- 0 j-;
for
which is a DP equation for a finite Markovian Decision Process whose state-space
is space is U ffi and probabilities of transition are p(- 0 j-; u) (see figure 6
for a geometrical interpretation).12
x
x
x
x
x
x
u'
x
. p( | ,u)
. p( | ,u)
p( | ,u)
x
x
d
d State Control Next
state
x
d
Prob.

Figure

6. A geometrical interpretation of the FD discretization. The continuous process (on the
left) is discretized at some resolution ffi into an MDP (right). The transition probabilities p(-
of the MDP are the coordinates of the vector 1
(j \Gamma -) with j the projection of - onto the segment
in a direction parallel to f(-; u).
From the boundary condition, we define the absorbing terminal states :
For
REINFORCEMENT LEARNING BY THE MEANS OF VISCOSITY SOLUTIONS 15
By defining F ffi
FD the finite difference scheme :
DP equation
FD
This equation states that V ffi is a fixed point of F ffi
FD . Moreover, as f is bounded
from above (with some value M f
FD satisfies the following strong contraction
and since - ! 1, there exists a fixed point which is the value function
is unique and can be computed by DP iterative methods (see (Puterman, 1994),
(Bertsekas, 1987)).
Computation of V ffi and convergence. : There are two standard methods
for computing the value function V ffi of some MDP : value iteration (V ffi is the
limit of a sequence of successive iterations V ffi
FD
) and policy iteration
(approximations in policy space by alternative policy evaluation steps and policy
improvement steps). See (Puterman, 1994), (Bertsekas, 1987) or (Bertsekas &
Tsitsiklis, 1996) for more information about DP theory. In section 5, we describe
RL methods for computing iteratively the approximated value functions
In the following section, we study a similar method for discretizing the continuous
process into an MDP by using finite element methods. The convergence of these
two methods (i.e. the convergence of the discretized V ffi to the value function V as
tends to 0) will be derived from a general theorem in section 4.4.
4.3. Approximations with finite element methods
We use a finite element (FE) method (with linear simplexes) based on a triangulation
covering the state-space (see figure 7).
The value function V is approximated by piecewise linear functions V ffi defined
by their values at the vertices f-g of the triangulation \Sigma ffi . The value of V ffi at any
point x inside some simplex (- linear combination of V ffi at the vertices
d
with being the barycentric coordinates of x inside the simplex (-
(We recall that the definition of the barycentric coordinates is that - i
EMI MUNOS
xd d
x

Figure

7. Triangulation \Sigma ffi of the state-space. V ffi (x) is a linear combination of the V ffi (- i ), for
weighted by the barycentric coordinates - i (x).
By using a finite element approximation scheme derived from (Kushner, 1990),
the continuous HJB equation is approximated by the following equation :
where j(-; u) is a point inside \Sigma ffi such that j(-;
We require that -
satisfies the following condition, for some positive constants k 1 and
Remark. It is interesting to notice that this time discretization function -; u)
does not need to be constant and can depend on the state - and the control u.
This provides us with some freedom on the choice of these parameters, assuming
that equation (19) still holds. For a discussion on the choice of a constant time
discretization function - according to the space discretization size ffi in order to
optimize the precision of the approximations, see (Pareigis, 1997).
Let us denote (- 0 ; :::; - d ) the simplex containing j(-; u): As V ffi is linear inside the
simplex, this equation can be written :
d
which is a DP equation for a Markov Decision Process whose state-space is the
set of vertices f-g and the probability of transition from (state -, control u) to
next states - are the barycentric coordinates of j(-; u) inside simplex
8). The boundary states satisfy
the terminal condition :
REINFORCEMENT LEARNING BY THE MEANS OF VISCOSITY SOLUTIONS 17
x
x
x
l (h )x
xx
x
x
x
l
l
x
x
x
x
hState Control Proba. Next
state
x
l (h )x

Figure

8. A finite element approximation. Consider a vertex - and j 1
linear combination of V weighted by the barycentric coordinates
). Thus, the probabilities of transition of the MDP are these barycentric coordinates.
For
By defining F ffi
FE the finite element scheme,
d
the approximated value function V ffi satisfies the DP equation
Similarly to the FD scheme, F ffi
FE satisfies the following "strong" contraction
and since - ! 1, there is a unique solution, V ffi to (23) with (21) which can be
computed by DP techniques.
4.4. Convergence of the approximation schemes
In this section, we present a convergence theorem for a general class of approximation
schemes. We use the stability properties of viscosity solutions (described
in (Barles & Souganidis, 1991)) to obtain the convergence. Another kind of convergence
result, using probabilistic considerations, can be found in (Kushner &
Dupuis, 1992), but such results do not treat the problem with the general boundary
condition (9). In fact, the only important required properties for convergence
is monotonicity (property (27)) and consistency (properties (30) and (31) below).
As a corollary, we deduce that the FE and the FD schemes studied in the previous
sections are convergent.
EMI MUNOS
4.4.1. A general convergence theorem. Let \Sigma ffi and @ \Sigma ffi be two discrete and finite
subsets of IR d . We assume that for all x 2 O; lim ffi#0 dist(x; \Sigma
be an operator on the space of bounded
functions on \Sigma ffi . We are concerned with the convergence of the solution V ffi to the
dynamic programming equation :
with the boundary condition :
We make the following assumptions on F
ffl For any constant c,
ffl For any ffi ,
there exists a solution V ffi to (25) and (26) which is (29)
bounded with a constant M V independent of ffi:
Consistency : there exists a constant k ? 0 such that :
lim inf
lim sup
Remark. Conditions (30) and (31) are satisfied in the particular case of :
lim
Theorem 5 (Convergence of the scheme) Assume that the hypotheses of theorem
are satisfied. Assume that (27), (28) (30) and (31) hold, then F ffi is a
convergent approximation scheme, i.e. the solutions V ffi of (25) and
lim
\Gamma!x
uniformly on any
REINFORCEMENT LEARNING BY THE MEANS OF VISCOSITY SOLUTIONS 19
4.4.2. Outline of the proof. We use the procedure described in (Barles and
Perthame1988). The idea is to define the largest limit function V
and the smallest limit function V prove that they are respectively
discontinuous sub- and super viscosity solutions. This proof, based on the
general convergence theorem of (Barles & Souganidis, 1991), is given in appendix
A. Then we use a comparison result which states that if (9) holds then viscosity
sub-solutions are less than viscosity super-solutions, thus V sup - V inf . By definition
and the limit function V is the viscosity solution
of the HJB equation, thus (from theorem 4) the value function of the problem.
4.4.3. FD and FE approximation schemes converge
Corollary 1 The approximation schemes F ffi
FD and F ffi
FE are convergent.
Indeed, for the finite difference scheme, it is obvious that since p(- 0 j-; u) are
considered as transition probabilities, the approximation scheme F ffi
FD satisfies (27)
and (28). As (17) is a DP equation for some MDP, DP theory ensures that (29) is
true. We can check that the scheme is also consistent : conditions (30) and (31)
hold with
FD satisfy the hypotheses of theorem 5.
Similarly, for the finite element scheme, from the basic properties of the barycentric
coordinates - i (x), the approximation scheme F ffi
FE satisfies (27). From (19),
condition holds. DP theory ensures that (29) is true. The scheme is consistent
and conditions (30) and (31) hold with
FE satisfies the hypotheses
of theorem 5.
4.5. Summary of the previous results of convergence
For any given discretization step ffi , from the "strong" contraction property (18) or
(24), DP theory ensures that the values V ffi
iterated by some DP algorithm converge
to the value V ffi of the approximation scheme F ffi as n tends to infinity. From the
convergence of the scheme (theorem 5), the V ffi tend to the value function V of the
continuous problem as ffi tends to 0 (see figure 9).
d
d
the "strong"
contraction
property
HJB equation DP equation

Figure

9. The HJB equation is discretized, for some resolution ffi; into a DP equation whose
solution is V ffi . The convergence of the scheme ensures that V 0: Thanks to the
"strong" contraction property, the iterated values V ffi
n tend to V ffi as
EMI MUNOS
Remark. Theorem 5 gives a result of convergence on any
that the hypothesis (9), for the continuity of V , is satisfied. However, if this
hypothesis is not satisfied, but if the value function is continuous, the theorem still
applies. Now, if (9) is not satisfied and the value function is discontinuous at some
area, then we still have the convergence on any
O where the value
function is continuous.
5. Designing convergent reinforcement learning algorithms
In order to solve the DP equation (14) or (20), one can use DP off-line methods
-such as value iteration, policy iteration, modified policy iteration (see (Puterman,
1994)), with synchronous or asynchronous back-ups, or on-line methods -like Real
Time DP (see (Barto, Bradtke, & Singh, 1991), (Bertsekas & Tsitsiklis, 1996)).
For example, by introducing the Q-values Q
equation (20) can be solved by
successive back-ups (indexed by n) of states -; control u (in any order provided
that every state and control are updated regularly) by :
The values V ffi
n of this algorithm converges to the value function V ffi of the discretized
MDP as n !1.
However, in the RL approach, the state dynamics f and the reinforcement functions
are unknown to the learner. Thus, the right side of the iterative rule (33)
is unknown and has to be approximated thanks to the available knowledge. In the
RL terminology, there are two possible approaches for updating the values :
ffl The model-based approach consists of first, learning a model of the state dynamics
and of the reinforcement functions, and then using DP algorithms based on
such a rule (33) with the approximated model instead of the true values. The
learning (the updating of the estimated Q-value Q
iteratively during
the simulation of trajectories (on-line learning) or at the end (at the exit
time) of one or several trajectories (off-line or batch learning).
ffl The model-free approach consists of updating incrementally the estimated values
n or Q-value Q
n of the visited states without learning any model.
In what follows, we propose a convergence theorem that applies to a large class
of RL algorithms (model-based or model-free, on-line or off-line, for deterministic
or stochastic dynamics) provided that the updating rule satisfies some "weak"
contraction property with respect to some convergent approximation scheme
such as the FD and FE schemes studied previously.
5.1. Convergence of RL algorithms
The following theorem gives a general condition for which an RL algorithm converges
to the optimal solution of the continuous problem. The idea is that the
REINFORCEMENT LEARNING BY THE MEANS OF VISCOSITY SOLUTIONS 21
updated values (by any model-free or model-based method) must be close enough
to those of a convergent approximation scheme so that their difference satisfies the
"weak" contraction property (34) below.
Theorem 6 (Convergence of RL algorithms) For any ffi , let us build finite
subsets \Sigma ffi and @ \Sigma ffi satisfying the properties of section 4.4. We consider an algorithm
that leads to update every state - 2 \Sigma ffi regularly and every state - 2 @ \Sigma ffi at
least once. Let F ffi be a convergent approximation scheme (for example (22)) and
V ffi be the solution to (25) and (26). We assume that the values updated at the
iteration n satisfy the following properties
in the sense of the following "weak"
contraction property :
for some positive constant k and some function e(ffi) that tends to 0 as
in the sense :
for some positive constant kR ;
then for any
ae O; for all " ? 0, there exists \Delta such that for any
there exists N; for all n - N ,
sup
This result states that when the hypotheses of the theorem applies (mainly when
we find some updating rule satisfying the weak contraction property (34)) then
the values V ffi
computed by the algorithm converge to the value function V of the
continuous problem as the discretization step ffi tends to zero and the number of
iterations n tends to infinity.
5.1.1. Outline of the proof The proof of this theorem is given in appendix B. If
condition (34) were a strong contraction property such as
for some constant - ! 1; then the convergence would be obvious since from (25)
and from the fact that all the states are updated regularly, for a fixed
would
converge to V ffi as From the fact (theorem 5) that V ffi converges to V as
could deduce that V ffi
EMI MUNOS
If it is not the case, we can no longer expect that V ffi
if (34) holds, we can prove (this is the object of section B.2 in appendix B) that
for any " ? 0; there exists small enough values of ffi such that at some stage N ,
This result together with the convergence of the scheme
leads to the convergence of the algorithm as ffi # 0 and n !1 (see figure 10).
contraction
property
the "weak"
RL with
d
d
HJB equation DP equation

Figure

10. The values V ffi
iterated by an RL algorithm do not converge to V ffi as n !1. However,
if the "weak" contraction property is satisfied, the V ffi
tend to V as
5.1.2. The challenge of designing convergent algorithms. In general the "strong"
contraction property (36) is impossible to obtain unless we have perfect knowledge
of the dynamics f and the reinforcement functions r and R. In the RL approach,
these components are estimated and approximated during some learning phase.
Thus the iterated values V ffi
are imperfect, but may be "good enough" to satisfy
the weak contraction property (34). Defining such "good" approximations is
the challenge for designing convergent RL algorithms.
In order to illustrate the method, we present in section 5.2 a procedure for designing
model-based algorithms, and in section 5.3, we give a model-free algorithm
based on a FE approximation scheme.
5.2. Model-based algorithms
The basic idea is to build a model of the state dynamics f and the reinforcement
functions r and R at states - from the local knowledge obtained through the simulation
of trajectories. So, if some trajectory xn (t) goes inside the neighborhood
of - (by defining the neighborhood as an area whose diameter is bounded by kN :ffi
for some positive constant kN ) at some time t n and keep a constant control u for
a period - n (from )), we can build the model of
f(-; u) and r(-; u) :
(see figure 11). Then we can approximate the scheme (22), by the following values
using the previous model : the Q-values Q
are updated according to :
(for any function -; u) satisfying (19)), which corresponds to the iterative rule
(33) with the model f f n and er instead of f and r.
y
x
x
x

Figure

11. A trajectory goes through the neighborhood (the grey area) of -. The state dynamics
is approximated by ~
-n
It is easy to prove (see (Munos & Moore, 1998) or (Munos, 1997a)) that assuming
some smoothness assumptions (r; R Lipschitzian), the approximated V ffi
n satisfy the
condition (34) and theorem 6 applies.
Remark. Using the same model, we can build a similar convergent RL algorithm
based on the finite difference scheme (22) (see (Munos, 1998)). Thus, it appears
quite easy to design model-based algorithms satisfying the condition (34).
Remark. This method can also be used in the stochastic case, for which a model
of the state dynamics is the average, for several trajectories, of such yn \Gammax n
-n , and a
model of the noise is their variance (see (Munos & Bourgine, 1997)).
Furthermore, it is possible to design model-free algorithms satisfying the condition
(34), which is the topic of the following section.
5.3. A Model-free algorithm
The Finite Element RL algorithm. Consider a triangulation \Sigma ffi satisfying the
properties of section 4.3. The direct RL approach consists of updating on-line the
Q-values of the vertices without learning any model of the dynamics.
We consider the FE scheme (22) with -; u) being such that j(-;
-; u):f(-; u) is the projection of - onto the opposite side of the simplex, in a
parallel direction to f(-; u) (see figure 12). If we suppose that the simplexes are
EMI MUNOS
non degenerated (i.e. 9k ae such that the radius of the sphere inscribed in each
simplex is superior to k ae ffi ) then (19) holds.
Let us consider that a trajectory x(t) goes through a simplex. Let
the input point and be the output point. The control u is assumed to be
constant inside the simplex.
x
x
x
y
x

Figure

12. A trajectory going through a simplex. j(-; u) is the projection of - onto the opposite
side of the simplex. y\Gammax
is a good approximation of j(-; u) \Gamma -.
As the values -; u) and j(-; u) are unknown to the system, we make the following
estimations (from Thales'
ffl -; u) is approximated by -
(where - (x) is the - \Gammabarycentric coordinate
of x inside the simplex)
ffl j(-; u) is approximated by -
which only use the knowledge of the state at the input and output points (x and
y), the running time - of the trajectory inside the simplex and the barycentric
coordinate - (x) (which can be computed as soon as the system knows the vertices
of the input side of the simplex). Besides, r(-; u) is approximated by the current
reinforcement r(x; u) at the input point.
Thanks to the linearity of V ffi inside the simplex, V ffi (j(-; u)) is approximated by
the algorithm consists in updating the quality Q
with the estimation :
and if the system exits from the state-space inside the simplex (i.e. y 2 @O), then
update the closest vertex of the simplex with :
By assuming some additional regularity assumptions (r and R Lipschitzian, f
bounded from below), the values V ffi
and (35) which proves the
convergence of the model-free RL algorithm based on the FE scheme (see (Munos,
1996) for the proof).
In a similar way, we can design a direct RL algorithm based on the finite difference
scheme F ffi
FD (16) and prove its convergence (see (Munos, 1997b)).
6. A numerical simulation for the "Car on the Hill" problem
For a description of the dynamics of this problem, see (Moore & Atkeson, 1995).
This problem has a state-space of dimension 2 : the position and the velocity of
the car. 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
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 (see figure 13). The control u has only 2 possible
positive or negative thrust.
Thrust
Gravitation
Resistance
Goal
Position
x
R=+1 for null velocity
R=-1 for max. velocity
Reinforcement

Figure

13. The "Car on the Hill" problem.
In order to approximate the value function, we used 3 different triangulations
composed respectively of 9 by 9, 17 by 17 and 33 by 33 states (see
figure 14), and, for each of these, we ran the two algorithms that follows :
ffl An asynchronous Real Time DP (based on the updating rule (33)), assuming
that we have a perfect model of the initial data (the state dynamics and the
reinforcement functions).
ffl An asynchronous Finite Element RL algorithm, described in section 5.3 (based
on the updating rule (37)), for which the initial data are approximated by parts
of trajectories selected at random.
EMI MUNOS
Velocity
Triangulation 2 Triangulation 3
Position
Triangulation 1

Figure

14. Three triangulations used for the simulations.
In order to evaluate the quality of approximation of these methods, we also computed
a very good approximation of the value function V (plotted in figure 15) by
using DP (with rule (33)) on a very dense triangulation (of 257 by 257 states) with
a perfect model of the initial data.

Figure

15. The value function of the "Car on the Hill", computed with a triangulation composed
of 257 by 257 states.
We have computed the approximation error En
being the discretization step of triangulation T k . For this problem, we notice
that hypothesis (9) does not hold (because all the trajectories are tangential to
the boundary of the state-space at the boundary states of zero velocity), and the
value function is discontinuous. A frontier of discontinuity happens because a point
beginning just above this frontier can eventually get a positive reward whereas any
point below is doomed to exit on the left side of the state-space. Thus, following
the remark in section 4.5, in order to compute En (T k ), we
chose\Omega to be the whole
state-space except some area around the discontinuity.

Figures

and 17 represent, respectively for the 2 algorithms, the approximation
error En (T k ) (for the 3 triangulations function of the number
of iterations n. We observe the following points :
of approximation
Triangulation 1
Triangulation 2
Triangulation 3

Figure

16. The approximation error En (T k ) of the values computed by the asynchronous Real
Time DP algorithm as a function of the number of iterations n for several triangulations.
of approximation
Triangulation 1
Triangulation 3
Triangulation 2

Figure

17. The approximation error En (T k ) of the values computed by the asynchronous Finite
Element RL algorithm.
ffl Whatever the resolution of the discretization ffi is, the values V ffi
computed by
RTDP converge, as n increases. Their limit is V ffi , solution of the DP equation
EMI MUNOS
(20). Moreover, we observe the convergence of the V ffi to the value function
V as the resolution ffi tends to zero. These results illustrate the convergence
properties showed in figures 9.
ffl For a given triangulation, the values V ffi
computed by FERL do not converge.
For discretization), the error of approximation decreases rapidly, and
then oscillates within a large range. For T 2 , the error decreases more slowly
(because there are more states to be updated) but then oscillates within a
smaller range. And for T 3 (dense discretization), the error decreases still more
slowly but eventually gets close to zero (while still oscillating). Thus, we observe
that, as illustrated in figure 10, for any given discretization step ffi , the values do
not converge. However, they oscillate within a range depending on ffi . Theorem
6 simply states that for any desired precision (8"), there exists a discretization
step ffi such that eventually (9N; 8n ? N ), the values will approximate the value
function at that precision (supjV ffi
").
7. Conclusion and future work
This paper proposes a formalism for the study of RL in the continuous state-space
and time case. The Hamilton-Jacobi-Bellman equation is stated and several properties
of its solutions are described. The notion of viscosity solution is introduced
and used to integrate the HJB equation for finding the value function. We describe
discretization methods (by using finite element and finite difference schemes) for
approximating the value function, and use the stability properties of the viscosity
solutions to prove their convergence.
Then, we propose a general method for designing convergent (model-based or
model-free) RL algorithms and illustrate it with several examples. The convergence
result is obtained by substituting the "strong" contraction property used to prove
the convergence of DP method (which cannot hold any more when the initial data
are not perfectly known) by some "weak" contraction property, that enables some
approximations of these data. The main theorem states a convergence result for
RL algorithms as the discretization step ffi tends to 0 and the number of iterations
n tends to infinity.
For practical applications of this method, we must combine to the learning dynamics
(n !1) some structural dynamics which operates on the discretization
process. For example, in (Munos, 1997c), an initial rough Delaunay triangulation
progressively refined (by adding new vertices) according to a local criterion
estimating the irregularities of the value function. In (Munos & Moore, 1999),
a Kuhn triangulation embedded in a kd-tree is adaptively refined by a non-local
splitting criterion that allows the cells to take into account their impact on other
cells when deciding whether to split.
Future theoretical work should consider the study of approximation schemes (and
the design of algorithms based on these scheme) for adaptive and variable resolution
discretizations (like the adaptive discretizations of (Munos & Moore, 1999;
Munos, 1997c), the parti-game algorithm of (Moore & Atkeson, 1995), the multi-
grid methods of (Akian, 1990) and (Pareigis, 1996), or the sparse grids of (Griebel,
1998)), the study of the rates of convergence of these algorithms (which already
exists in some cases, see (Dupuis & James, 1998)), and the study of generalized
control problems (with "jumps", generalized boundary conditions, etc.
To adequately address practical issues, extensive numerical simulations (and comparison
to other methods) have to be conducted, and in order to deal with high dimensional
state-spaces, future work should concentrate on designing relevant structural
dynamics and condensed function representations.

Acknowledgments

This work has been funded by DASSAULT-AVIATION, France, and has been
carried out at the Laboratory of Engineering for Complex Systems (LISC) of the
CEMAGREF, France. I would like to thank Paul Bourgine, Martine Naillon, Guillaume
Guy Barles and Andrew Moore.
I am also very grateful to my parents, my mentor Daisaku Ikeda and my best
friend Guyl'ene.


Appendix

A
Proof of theorem 5
A.1. Outline of the proof
We use the Barles and Perthame procedure in (Barles & Perthame, 1988). First
we give a definition of discontinuous viscosity solutions. Then we define the largest
limit function V sup and the smallest limit function V inf and prove (following (Barles
& Souganidis, 1991)), in lemma (1), that V sup (respectively V inf ) is a discontinuous
viscosity sub-solution (resp. super-solution). Then we use a strong comparison
result (lemma 2) which states that if (9) holds then viscosity sub-solutions are less
than viscosity super-solutions, thus V sup - V inf . By definition V sup - V inf , thus
and the limit function V is the viscosity solution of the HJB
equation, and thus the value function of the problem.
A.2. Definition of discontinuous viscosity solutions
Let us recall the notions of the upper semi-continuous envelope W   and the lower
semi-continuous envelope W   of a real valued function W :
Definition 5. Let W be a locally bounded real valued function defined on O.
EMI MUNOS
ffl W is a viscosity sub-solution of H(x; W;DW O if for all functions
local maximum of W \Lambda \Gamma ' such that W
we have :
ffl W is a viscosity super-solution of H(x; W;DW O if for all functions
local minimum of W \Lambda \Gamma ' such that W
we have :
ffl W is a viscosity solution of H(x; W;DW O if it is a viscosity sub-solution
and a viscosity super-solution of H(x; W;DW
A.3. V sup and V inf are viscosity sub- and super-solutions
Lemma 1 The two limit functions V sup and
are respectively viscosity sub- and super-solutions.
Proof: Let us prove that V sup is a sub-solution. The proof that V inf is a supersolution
is similar. Let ' be a smooth test function such that V sup \Gamma ' has a
maximum (which can be assumed to be strict) at x such that V sup
n be a sequence converging to zero. Then V has a maximum at - n which
tends to x as tends to 0. Thus, for all - 2 \Sigma
By (27), we have :
\Theta
By (28), we obtain :
By
\Theta
\Theta

As tends to 0, the left side of this inequality tends to 0 as
Thus, by (31), we have :
Thus V sup is a viscosity sub-solution.
A.4. Comparison principle between viscosity sub- and super-solutions
Assume (9), then (7) and (6) has a weak comparison principle, i.e. for
any viscosity sub-solution W and super-solution W of (7) and (6), for all x 2 O
we have :
For a proof of this comparison result between viscosity sub- and super-solutions
see (Barles, 1994), (Barles & Perthame, 1988), (Barles & Perthame, 1990) or for
slightly different hypothesis (Fleming & Soner, 1993).
A.5. Proof of theorem 5
Proof: From lemma 1, the largest limit function V sup and the smallest limit
function V inf are respectively viscosity sub-solution and super-solution of the HJB
equation. From the comparison result of lemma 2, V sup - V inf . But by their
definition and the approximation scheme V ffi
converges to the limit function V , which is the viscosity solution of the HJB equation
thus the value function of the problem, and (32) holds true.


Appendix

Proof of theorem 6
B.1. Outline of the proof
We know that from the convergence of the scheme V ffi (theorem 5), for any compact
ae O; for any " 1 ? 0; there exists a discretization step ffi such that :
sup
Let us define :
As we have seen in section 5.1.1, if we had the strong contraction property (36),
then for any ffi; E
would converge to 0 as As we only have the weak
contraction property
the idea of the following proof is that for any " 2 ? 0; there exists ffi and a stage N;
such that for n - N ,
EMI MUNOS
Then we deduce that for any " ? 0; we can find
sup
B.2. A sufficient condition for
Lemma 3 Let us suppose that there exists some constant ff ? 0 such that for any
state - updated at stage n, the following condition hold :
then there exists N such that for n - N;E ffi
Proof: As the algorithm updates every state - 2 \Sigma ffi regularly, there exists an
integer m such that at stage n+m all the states - 2 \Sigma ffi have been updated at least
once since stage n. Thus, from (B.2) and (B.3) we have :
Thus, there exists N 1 such that : 8n -
sup
Moreover, all states - 2 @ \Sigma ffi are updated at least once, thus there exists N 2 such
that
for any ffi -
Thus from (B.4) and (B.5), for n -
Lemma 4 For any " 1 ? 0; there exists \Delta 2 such that for the conditions
(B.2) and (B.3) are satisfied.
Proof: Let us consider a From the convergence of e(ffi) to 0 when
# 0, there exists \Delta 1 such that for
Let us prove that (B.2) and (B.3) hold. Let E
then from (34),
From (B.6),
" 2and (B.2) holds for
from (34), we have :
and condition (B.3) holds.
B.3. Convergence of the algorithm
Proof: Let us prove theorem 6. For any
ae O; for all " ? 0, let us
". From lemma 4, for
conditions (B.2) and (B.3) are satisfied, and from lemma 3, there exists N; for all
Moreover, from the convergence of the approximation scheme, theorem 5 implies
that for any
ae O; there exists \Delta 2 such that for all
sup
Thus for finite discretized state-space \Sigma ffi and @ \Sigma ffi
satisfying the properties of section 4.4, there exists N; for all n - N ,
sup



--R

M'ethodes multigrilles en contr-ole stochastique

Solutions de viscosit'e des 'equations de Hamilton-Jacobi, Vol. <Volume>17</Volume> of Math'ematiques et Applications.
time problems in optimal control and vanishing viscosity solutions of hamilton-jacobi equations
Comparison principle for dirichlet-type hamilton-jacobi equations and singular perturbations of degenerated elliptic equations
Convergence of approximation schemes for fully nonlinear second order equations.
Neural networks for control.


Neuronlike adaptive elements that can solve difficult learning control problems.
Dynamic Programming.
A simplification of the back-propagation-through- time algorithm for optimal neurocontrol
Dynamic Programming

Generalization in reinforcement learning
User's guide to viscosity solutions of second order partial differential equations.
Viscosity solutions of hamilton-jacobi equations


Rates of convergence for approximation schemes in optimal control.
Controlled Markov Processes and Viscosity Solutions.
Fuzzy q-learning
Stable function approximation in dynamic programming.
Adaptive sparse grid multilevel methods for elliptic pdes based on finite differences.
Reinforcement Learning and its application to control.

Reinforcement learning applied to a differential game.
Reinforcement learning: a survey.
Numerical methods for stochastic control problems in continuous time.

Reinforcement Learning for Robots using Neural Networks.

Automatic programming of behavior-based robots using reinforcement learning
Le dilemme Exploration/Exploitation dans les syst'emes d'apprentissage par renforcement.
Variable resolution dynamic programming: Efficiently learning action maps in multivariate real-valued state-spaces
The parti-game algorithm for variable resolution reinforcement learning in multidimensional state space





A general convergence theorem for reinforcement learning in the continuous case.
Gradient descent approaches to neural- net-based solutions of the hamilton-jacobi-bellman equation
Reinforcement learning for continuous stochastic control problems.
Barycentric interpolators for continuous space and time reinforcement learning.
Variable resolution discretization for high-accuracy solutions of optimal control problems
Fuzzy reinforcement learning.

Adaptive choice of grid and time in reinforcement learning.
Neural Information Processing Systems.
The Mathematical Theory of Optimal Processes.
Markov Decision Processes
Reinforcement learning with soft state aggregation.
Online learning with random representations.
International Conference on Machine Learning.
Simple statistical gradient-following algorithms for connectionist reinforcement learning
--TR
Dynamic programming: deterministic and stochastic models
Numerical methods for stochastic control problems in continuous time
Connectionist learning for control
Automatic programming of behavior-based robots using reinforcement learning
Simple Statistical Gradient-Following Algorithms for Connectionist Reinforcement Learning
Reinforcement learning and its application to control
Numerical methods for stochastic control problems in continuous time
Reinforcement learning for robots using neural networks
The Parti-game Algorithm for Variable Resolution Reinforcement Learning in Multidimensional State-spaces
Rates of Convergence for Approximation Schemes in Optimal Control
Reinforcement learning for continuous stochastic control problems
Adaptive choice of grid and time in reinforcement learning
Barycentric interpolators for continuous space MYAMPERSANDamp; time reinforcement learning
Markov Decision Processes
Neuro-Dynamic Programming
Finite-Element Methods with Local Triangulation Refinement for Continuous Reimforcement Learning Problems
A General Convergence Method for Reinforcement Learning in the Continuous Case
Variable Resolution Discretization for High-Accuracy Solutions of Optimal Control Problems
Dynamic Programming

--CTR
Rmi Munos , Andrew Moore, Variable Resolution Discretization in Optimal Control, Machine Learning, v.49 n.2-3, p.291-323, November-December 2002
optimal control;reinforcement learning;viscosity solutions;finite difference and finite element methods;dynamic programming;Hamilton-Jacobi-Bellman equation