A Convergent Reinforcement Learning Algorithm in the Continuous Case Based on a Finite Difference Method

1 Introduction

This paper is concerned with convergence results of Re­ inforcement Learning (RL) algorithms in the continuous­ time, continuous-state-space case. We discuss the prob­ lem of the necessary discretization of the state space and propose a RL algorithm that converges to the optimal solution.

*DASSAULT-AVIATION, DGT-DTN-EL-Et. Avancees, 78 quai Marcel Dassault, 92214 Saint-Cloud, FRANCE

The objective of RL is to find -thanks to a reinforce­ ment signal- an optimal strategy for solving a dynamical control problem, such as target or obstacle problems, vi­ ability or optimization problems. The technique used belongs to the Dynamic Programming (DP) methods which define an optimal feed-back control by approxi­ mating the value function (VF), which is the best ex­ pected cumulative reinforcement as a function of initial state.

In the continuous case, the VF has to be represented with a function approximator with a finite number of pa­ rameters. Several author have pointed out that the com­ bination of RL algorithms with general approximation systems (such as neural networks, fuzzy sets, polynomial approximators, etc.) may produce unstable or divergent results even for very simple problems (see [Boyan and Moore, 1995], [Baird, 1995], [Gordon, 1995]). Here we show that classical RL algorithms, like Q-learning (see [Watkins, 1989]), used with a look-up table built from a simple discretization of the state space may produce a very bad approximation of the value function. The main reason is that the discretization of a determinis­ tic continuous process is not Markovian. So algorithms such as Q-learning which estimate the value of a state as an average of the values of successive states according to their occurrence will not converge. We propose as an alternative an algorithm that averages the values of the next states according to the state dynamics.

Section 2 proposes a formalism for optimal control problems in the continuous case. The VF is intro­ duced and the Hamilton-Jacobi-Bellman (HJB) equation is stated. Section 3 J iscusses the lost of the Markov property with the discretization of the state space and studies the Q-learning algorithm with a look-up table. Section 4 describes the discretization of the HJB equa­ tion by a Finite Difference (FD) method, which leads to a DP equation for a finite Markov Decision Process (MDP) and whose solution approximates the VF. Sec­ tion 5 presents the algorithm, called Finite Difference Reinforcement Learning (FDRL), that converges to the value function of the continuous process. Appendix A gives the proof of convergence of the algorithm.

2 A formalism for Reinforcement Learning in the continuous case

In this paper, we consider deterministic controlled sys­ tems with infinite time horizon and discounted reinforce­ ment. Let x(t) E 0 be the state of the system with 0 c IRd an open and bounded subset. The evolution of the system (the state dynamics f) depends on the current state x( t) and control u( t) ; it is defined by a controlled differential equation :

where the control u(t) is a bounded, Lebesgue measur­ able function with values in a compact U.

From any initial state x, the choice of a control u(t) leads to a unique trajectory x(t). LetT be the exit time of x(t) from 0 (with the convention that if x(t) always stays in 0, then T = oo). Then, we define the discounted reinforcement functional of state x, control u(.) :

Where r(x, u) is the running reinforcement and R(x) the boundary reinforcement. 1 is the discount factor (0 ::; I< 1).

The objective of the control problem is to find the optimal feed-back control u * ( x) that optimizes the reinforcement functional for any state x.

2.1 The Reinforcement Learning approach

RL techniques belongs to the class of DP methods which compute the optimal control by the means of the value function, which is the maximum value of the functional as a function of initial state x :

In the RL approach, the system tries to approximate this function without knowing the state dynamics f nor the reinforcement functions r, R. RL appears as a construc­ tive and iterative process, based on experience, that es­ timates the value function by successive approximations.

2.2 The Hamilton-Jacobi-Bellman equation

Following the dynamic programming principle, the value function satisfies a first-order nonlinear partial differen­ tial equation called the Hamilton-Jacobi-Bellman equa­ tion (see [Fleming and Soner, 1993] for a survey).

Theorem 1 (Hamilton-Jacobi-Bellman) If V is differentiable at x E 0, let DV(x) be the gradient of V at x, then the following HJB equation holds at x.

Besides, V satisfies the following boundary condition :

Remark 1 The challenge of learning the value function is motivated by the fact that from V, we can deduce the following optimal feed-back control policy:

In the following, we assume that :

- f and rare bounded with M1 (respectively Mr) and Lipschitzian: lf(x, u)- f(y, u)l ::; LJ llx- Yll 1 (resp. lr(x,u)- r(y,u)l::; Lr llx- Yll 1).

- R is Lipschitzian: IR(x)- R(y)l ::; LR llx- Yll 1 .

with the norm llxlh = L::1=l lxil·

• The boundary 80 is C 2 .

Besides, we consider the following hypothesis concern­ ing the state dynamics f around the boundary 80 and we state a theorem of continuity whose proof is in [Bar­ les and Perthame, 1990]. For all x E 80, let Tt(x) be the outward normal of 0 at x, we assume that:

- If there exists u E U, such that f(x, u). Tt(x) ::; 0

then there exists v E U, such that f(x, v)Tt(x) < 0.

- ff there exists u E U, such that f(x, u). Tt(x) ~ 0

then there exists v E U, such that f(x, v)Tt(x) > 0.

Theorem 2 Suppose that these hypotheses hold, then the value function is continuous in 0.

3 The discretization implies a lost of the Markov property

Let us discretize the state space into a regular grid and define a finite discretized state space composed of cells X. Consider a trajectory x(t) and the corresponding sequence of cells X; containing it: x(t) E X; for t E [t;, t;+1]. Suppose that the control ui is kept constant inside X;. We observe that the transition from a cell X to an adjacent cell X 1 not only depends on X but also on the place from which the trajectory enters inside X (see figure 1). Thus, in general, the succession of cells X; does not provide a MDP even when the continuous process is deterministic.

Q-learning with a look-up table:

RL algorithms such as Q-learning (see [Watkins, 1989]) are classically used in order to approximate the value function. Here, the updating rule could be:

for some time T; and some decreasing learning rate o:;.

This is an iterative recursive equation that incremen­ tally computes the ayerage of the values of successive cells according to their occurrence. Meanwhile, from the non-Markovian aspect of the succession of cells, in gen­ eral, this algorithm (whose convergence is proved for fi­ nite MDP) has no chance to converge. For example, suppose that in figure 1, most of the trajectories comes inside X from its bottom side thus leaves X from its right side. Then from the algorithm, Q(X, u) will almost ex­ clusively depend on V(X1 ) . In fact, the values computed by such algorithms will depend on the exploration strate­ gies and will not converge to the value function.

As the Q-learning with look-up table do not converge, the combination of similar RL algorithms with function approximators appears unlikely to converge. As an al­ ternative, we propose that the updating rule should take into account the state dynamics f in order to approxi­ mate a convergent FD scheme studied next section.

4 A Finite Difference scheme

Let e1 , e2 , ... , ed be a basis for IR.d. The state dynamics is: f =(!I , ... , !d)· Let the positive and negative parts of j; be : t/ = max(!;, 0), !;- =max( -li, 0). For any discretization step D, let us consider the lattices : DZd = {D. L:~=l j;e;} wherej1 , ... ,jd are any integers, and L: 6 = { ~ E DZd such that at least one adjacent points ~±De; E 0}. The interior of L: 6 is L: 6 n 0. Let 8L: 6 ' the frontier of L; 6 , denote the set of points of L: 6 which are not in the interior of L: 6 .

Let U 6 c U be a finite control set that approximates U in the sense : D :S D 1 '* U 6 ' c U 6 and U0U 6 = U.

By replacing the gradient DV(O by the forward and backward difference quotients of V in ~ :

we can approximate the HJB equation by the following equation:

Knowing that ( b.t ln 1) is an approximation of (r~t - 1) as b.t tends to 0, and by introducing the qualities Q 6 (~, u) such that V 6 (0 = supuEU~ Q 6 (~, u), (2) gives:

with ~; = ~ + Oe; if !;(~, u) > 0 and ~i ~ - 8e; if J;(~, u) < 0.

This equation can be interpreted as a DP equation for a finite MDP (see [Fleming and Saner, 1993]) whose state space is L; 6 , the control space is U 6 and the probabilities of transition p(~, u, ~;) from state ~ ' control u to next state ~i are the coordinates 11 'J(~:~)!J' 1 (see figure 2 for a geometrical interpretation).

Thanks to a contraction property due to the discount factor 1 (see [Bertsekas, 1987]) , DP theory insures that there exists a unique solution (the fixed-point) V 6 to equation (3) for ~ interior to E 8 with the boundary con­ dition V 8 (0 = R(~) for~ E 8E 8 .

The following theorem, whose proof uses the general convergence result of [Barles and Souganidis, 1991] and the strong comparison result between sub- and super­ viscosity solution (see [Crandall et al., 1992]) of HJB equations of [Barles, 1994], insures that V 8 is a conver­ gent approximation of V.

Theorem 3 (Convergence of the FD scheme) Let us assume that the hypotheses of section 2 hold, then V 8 converges to V as 8 tends to 0 :

Remark 2 The MDP built here depends on the state dynamics .f and is independent of the running of trajec­ tories which generates a non-Markov succession of cells as it has been seen in section 3.

In the next section, we propose a RL algorithm that approximates this FD scheme.

5 The FDRL algorithm

Let us consider a grid G 8 :::) 0 composed of regular cells X such that the center of the cells are the previously de­ fined vertices ~ of the lattice. Let 8G 8 = {X E G 8 , X n 80 =J 0} its boundary. Let Q~(X, u) and V~(X), the values of cell X computed by the algorithm at stage n, intend to approximate Q 8 ( ~ , u) and V 8 ( ~). We have the relation V~(X) = supu Q~(X, u). Let A > 0 be any (small) constant.

Let a trajectory Xi ( t) enters a cell X at some point Xi ; then a control u E U 8 is chosen and kept constant.

- If X f/_ 8G 8 then the trajectory exits at some point Yi E X n Xi for some adjacent cell Xi (see figure 1). Let r(zi, u) be the current reinforcement obtained at some point zi of the trajectory inside X. Let r i be the running time of the trajectory inside X.

The algorithm is inspired by the DP equation (3) for which f(~, u) is approximated by ~ :

If llxiYill 1 ~ >..8 then update some 'value Q~(X, u, Xi):

Then we consider an other trajectory x j ( t) going through X from Xj till Yj E xnxj with control u, which leads to update Q~ (X, u, Xj), and the process is repeated until all possible transitions (X, u) --> Xk for k = l..d are carried out at least once. Then we consider a vector xy = XkYk for some k (for example, corresponding to the most recent trajectory) and compute:

where (. )i denote the ith coordinate. For example, in figure 1, if xl(t) occurs first, Q~(X, u, X 1 ) is computed, then when x2(t) occurs, Q~(X, u, X2) and Q~+l (X, u) are updated).

- If X E 8G 8 and if the trajectory reaches the bound­ ary Yi E 80 inside X, update:

The following theorem states that with the following hypothesis of exploring-every-possible-transition:

We consider series of trajectories such that the FDRL algorithm leads to the updating of every cell X f/- 8G 8 with rule (4) for all control u and all possible successive cell Xk any (finite) number of times and every cell X E 8G 8 with rule (6) at least once.

the values computed by the algorithm converge to the VF of the continuous problem :

Theorem 4 (Convergence of the algorithm)

Suppose that the hypotheses of section 2 and the one of exploring-every-possible-transition hold, then:

For any compact n c 0, '<IE > 0, :32. st. '<18 :::; 2., by using the FDRL algorithm, :JN, '<In~ N,

Remark 3 The FDRL is a kind of Real Time (or asyn­ chronous) DP and not a kind of Q-learning {there is no learning rate an that averages the successive values ac­ cording to their occurrence). This seems more relevant here because the averaging (with rule ( 5)) of the values of next cells comes from the discretization process itself and not from the state dynamics of the continuous process which is deterministic.

Remark 4 Once the Q~(X, u) values have been com­ puted, the current optimal control in cell X is : u· = argsupuEU" Q~(X,u).

6 Conclusion

This paper uses FD methods for approximating the VF and generating a convergent RL algorithm. It need to be compared to the Finite Element method used in [Munos, 1996] that approximates the VF with piecewise linear functions defined on a triangulation of the state space.

In practical use" of this algorithm, and in general, for all approximation systems of continuous functions, we are faced to the combinatorial explosion of the num­ ber of values to be estimated. Future work should consider adaptive multi-resolutions techniques (like the parti-game algorithm of [Moore, 1994] or the multigrid methods of [Akian, 1990]).

An other improvement should be to study the stochas­ tic case for which a Q-learning version of FDRL could be relevant.

A Appendix : proof of theorem 4

A.l Idea of the proof

The idea of the demonstration is to prove that for any t:2 > 0, for small enough values of 8,

Then for all t: > 0, we can find t:1 > 0 and t:2 > 0 such that E1 + E2 = E and from the convergence of the scheme V 6 (theorem 3), supxE!l IV 6 (x)- V(x)l :<:; E1 for small 6. Thus:

In order to prove (7), we need to estimate the dif­ ference I Q~+ 1 (X, u) - Q 6 ( ~, u) I after having updated Q~(X,u) with rule (5).

WithE~= sup€E:L" IV~(X 3 0- V 6 (~)1) we prove in section A.2 that :

for some constant k and some function e( 8) that tends to 0. Then we give in section A.3 a sufficient condition for E~ :::; t:2 and summarize the proof in section A.4. In the following of this section, we give some comparisons.

Comparison of the times llt(/u)ll 1 and 11 ~ 11 , .T From Taylor's theorem, llxy- f(x, u).TII1 :<:; ~Lt.T 2 . As the state dynamics is bounded from below, the time T is bounded by !!:..§_. From the Lipschitz property off, mf llf(x, u)- !(~, u)lh :S Lt.llx- ~lh :S d:/ Lt. But llxy­ f(~,u).Tih = llxy- f(x,u).T + T[j(x,u)- f(~,u)Jih, thus: llxy- !(~, u).TII1 :<:; ~~; LJ-(1 + ~~).As llxylh :2: )....8, we have:

with: kT = 2 ,d 2 2 LJ-(1 + - 1 ). We deduce from a prop,..,m1 mf erty of the exponential function that :

C · f ~ d f;(€,u) . ompanson o llxyll 1 an llf(E,u)ll ·.

From the fact that for any couple of vector a and b h h II bll h l fi .l!:.J_I 2E sue t at a- k. < E, we ave llall - llbll :S k.lb;J 2E, we deduce from (8) that

for any 8 :<:; .6.1 = - 4 1 k . ffij, T

A.2 Estimation of IQ~+1 (X,u)- Q 8 (~,u)i

After having updated Q~ (X, u) with rule (5), let A de­ note the difference IQ~+dX,u)- Q 6 (~,u)1. From (3), ( 4) and (5),

Let us consider a linear function V : 1Rd ~ 1R such that V-(')- vo(c) fo . - d· A lf;(Cull d jl'l"Yl;l '>i - '>i r z- 1.. . s llf(€,u)ll' an II'FYII, can be interpreted as barycentric coordinates, we have :

'th C ;: f(€,u) ( fi 2) d 1 C ;: ~ WI ry = ~, +u. llf(€,u)ll 1 see gure an ry = ~, +u.II'FYII,. Geometrical considerations give : 3 k, l E [1, d] st. :

Moreover,

Let EA = supxE!l IV 6 (x)- V(x)l.

Thanks to the continuity of V, there exists .6.2, for 8 :S .6.2 , IV(~k)- V(~z)l :::; E~. Thus, IV 6 (~k)- V 6 (~z)l :S 3EA. From (11) and (10), we have:

Thus, from (9), (8) and the Lipschitz property of r :

with k = .J 1 ln ~ and e(8) = 6.d 2 .mJ.kr.E~ + kr ln l .8.Mvs + _§_Lr + krLr8 3 + kr8Mr + kr8ln lE~. "' ffiJ "'

A.3 Condition for E~ ::; €2

Let us suppose that for cells X rf- 8G 8 , the following conditions hold for some a > 0

From the hypothesis of exploring-every-possible­ transition, there exists an integer m such that at stage n + m all the cells X E G 8 have been updated at least once since stage n . Since cells X E 8G 8 are updated with rule (6), w:+l(X)-V 8 (~)1 = IR(yi)-R(~)I ~ LR.8 ~ E2 for any 8 ~ ~3 f!· Thus, from (13) and (14) we have:

Thus there exists N such that : Vn ~ N, E~ ~ E2. A sufficient condition : let us suppose that

holds, then conditions (13) and (14) are true.

Indeed, assume (15) is true. Let E~ > E2, then from (12), A~ E~- k.8.E2 + e(8)8 ~ E~- k.8Jf. Thus (13) holds for a = k.8Jf.

Now suppose that E~ ~ E2. From (12), A ~ (1 - k.8)E2 + e(8)8 ~ ~ + ~ and condition (14) is true.

A.4 Convergence of the algorithm

Let us prove theorem 4. For any compact 0 c 0, for all E > 0, let us consider E1 > 0 and E2 > 0 such that E1 + E2 = E. As e(8) tends to 0, there exists ~4 for 8 ~ ~4 , (15) which is equivalent to: e(8)- k~ ~ 0 holds.

Thus for 8 ~ min { ~ 1> ~2 , ~3 , ~4 }, the sufficient con­ dition (15) is satisfied and conditions (13) and (14) are true. So there exists N, for all n ~ N, E~ ~ E2- Besides, from the convergence of the scheme (theorem (3)), there exists ~o st. V8 ~ ~o,supxEniV 8 (x)- V(x)l ~ E1.

Thus for 8 ~ min{~o,~b~2,~3,~4}, 3N, Vn ~ N,