Stochastic

Real-Valued

Reinforcement
Learning
Problem
H. Kimurato Solve a non-Linear

Control& S. Kobayashi**Tokyo Institute of Technology
Departmentof Computational
Intelligence and Systems Science,
Interdisciplinary
Graduate
School of Science and Engineering,
4259, Nagatsuta,
Midori-ku,
Yokohama,
226-8502
JAPAN

genQfe.dis.titech.ac.jp, kobayasi@dis.titech.ac.jp

ABSTRACTThis paper presents a new approach to reinforcement
learning (RL) to solve a non-linear
control problem
efficiently in which state and action spaces are continuous, Many DP-based reinforcement
learning (RL)
algorithms approximate
the value function and give agreedy policy with respect to the learned value function. However, it is too expensive to fit highly accurate
value functions, particularly in continuous state-action
spaces. We provide a hierarchical
RL algorithm composed of local linear controllers and TD-learning,which
are both very simple.
The continuous state space isdiscretized into an array of coarse boxes, and each box
has its own local linear controller for choosing primitive
continuous actions.
The higher-level of the hierarchy
accumulates
state-values
using tables with one entry
for each box. Each linear controller improves the local
control policy by using an actor-critic
method.
Thealgorithm was applied to a simulation of a cart-poleswing-up problem, and feasible solutions are found inless time than those of conventional discrete RL methods.
1

INTRODUCTION

Many DP-based
reinforcement
learning(RL)
algorithms approximate
the value function
and give agreedy policy with respect to the learned value function. Theoreticalresults guarantee that several DPbased algorithms will find optimal policies (e.g. [16],[15], etc.) and a great deal of effort has been made on
the techniques
to approximate
value functions(e.g.,CMAC, Neural-Net).
However, it is too expensive to
fit highly accurate value functions, particularly in continuous state-action
spaces.
To overcome this problem, several techniques are proposed (e.g., Parti-game[lo], Coarse grids Senvironment
models +search techniques [4], interpolation
on a coarse grid [3]). On theother hand, it is shown that a local gradient-ascentsearch over stochastic policy-spaceis possible without
explicitly computing value or gradient estimates[17],[8]. That is to say, the DP-based
RL methods havefeatures of a global search in terms of optimality
andcomputational
expense, and the gradient RL methods
have a feature of a local search. This paper presents a

0-7803-5731-O/99$10.00

01999 IEEE

new model-free approach that bridges a gap between
DP-based methods and local gradient-ascentmethods.
In real-world applications,an approach combining
discrete RL methods with linear controllers is promising since there are many non-linear control problems
that can be decomposed into several local linear control tasks. Based on this principle, we provide a newalgorithm with the key ideas including:A hierarchical RL method composed of discrete TD
method [13] and local linear controllers,
which areboth very simple.
Generalization
techniques
for continuous
stateaction spaces:
coarse discretization
for the highlevel of the hierarchy, and local continuous-vector
representation
for the low-level linear controllers.
A policy improvement algorithm for the local linear
controllers with imperfect value functions.
The coarse state-spacequantization
is a quite simple
way to cope with the curse of dimensionality.
But
in many cases, it often gives rise to undesirable
nonMarkovian effects.
In our approach, local linear controllers, which use a continuous-vector
for the local
state representation,
make up for these effects.
Althoughhierarchicalalgorithms
can often yield
sub-optimal
solutions, there are significant benefits inlearning efficiency, search space, and re-use of knowledge [51,P41,WI. 1n general, the low-level of the hierarchy is composed of learning control modules that
represent subtasks or abstract actions.
Each subtask
is defined in terms of termination
conditions,and thelow-level module is to find a local optimal policy. The
RL techniques for discrete semi-Markov
decision processes (SMDPs)
would be applied to learning of thehigh-level module that selects a low-level modules as
abstract action.
In our approach, the low-level modules correspond to linear controllers.
Actor-critic
methods [l] are often used for learning on the linear controllers[7], [6]. Generic actorcritic methods can be classified into a local gradientascent method with respect to policy space by using
learned value functions.
But in our hierarchy, the linear controllers cannot hold accurate value functions on
account of practical limitations
on the computational
resources. Fortunately,
it is shown that an actor-critic

v -510algorithm using eligibility traces in the actor can improve its stochastic
policy even though the estimatedvalue function is inaccurate[8]. We take advantage ofthis method for the local policy improvement.
2

2.1

PROBLEM

Markov

FORMULATION

Decision Processes

At each discrete time t, the agent observes xt containing information
about its current state, select action
at, and then receives an instantaneous
reward rt resulting from state transitionin the environment.
In
general, the reward and the next state may be random, but their probability
distributions
are assumed
to depend only on xt and at in Markov decision processes (MDPs),
in which many reinforcement
learning
algorithms are studied. In MDPs, the next state y ischosen according to the transition probability p&, andthe reward is given randomly according to the expectation r,“. but the agent does not know p& and rg
ahead of time. The objective of reinforcement
learning
is to construct a policy that maximizes the agent’s performance.
A natural performancemeasure for infinite
horizon tasks is the cumulative discounted reward:

3
3.1

COMBININGDISCRETE
TD(0) WITH
LOCAL LINEAR
CONTROLLERS
Hierarchical

Decomposition

In our approach, the agent adopts hierarchicalstate
representation.
The higher-level of the hierarchy uses
discrete representationof the state variables by coarse
quantization.
Representative
points are situated at thecenter of the grid’s boxes. Each box has its own local
linear controller.
Assume that given a n-dimensional
state input
.xn)
and
the
correspondingbox(Bi) with(Zl,Z2,..
the representative
point at (bf, b$, . . . bk), then the lowlevel linear controller gets a local continuous inputc=(c1,c2..

.cn) = (x1-bf,x2-b&.,x,-b;). (4)Figure 1 shows an example of the state representationin which the state space is two-dimensional.
x2

Discrete State = 82
Linear controller uses
this vector.

(1)
k=O

where the discount factor, 0 5 y < 1 specifies theimportanceof future rewards, and Vt is the value ontime t. In MDPs, the value can be defined as:0

where E, denotes the expectation
assuming the agent
The objective
inalways uses stationary
policy r.
MDPs is to find an optimal policy that maximizes thevalue of each state a: defined by Equation 2. In MDPs,
the optimal value in state x, denoted V*(x) satisfies
the Bellman equations for all CC:

V*(x) = m;xr,”+ x$(x,[2.2

A Non-LinearllState and action
dimensional.

1
.

(3)

Control Problem

We are given learning
systems in which :lY) + 7 V*(Y)Y

control

spacesof non-linear

are continuous

dynamic
and multi-

The task could be decomposed
into several
linear or bang-bang control tasks.
The agent does not know dynamics
ment ahead of time.

Throughout
the paper,task for the example.

localof the environ-

we use a cart-poleswing-up

v-511

Xl

Figure 1: An example of the hierarchicalstate representation
in a 2-dimensional
task.
Small circles atthe center of the grid’s boxes denote its representative
points.

3.2

Event-driven

Decision

MakingIn dynamic control, an optimal policy often selects thesame action (or holds similar continuous action) fora certain period of time.
Then, uniform regions arelikely to exist in the state space where all of the states
have the same (or similar) action.
In our approach,the coarse grids approximate the uniform regions. The
high-level decision maker selects abstract action eachtime when the continuous state input is going acrossthe boundary of the box, or a certain period of time
passes. This model of abstract action can be seen as anextension of Markov options [14] in which the policy
is given by linear controller and the termination
condition is given by the boundary of the box. Figure 2
helps to define the big-steps that the high-level learnertakes. If all the linear controllers hold stationary
policy, the high-level learner is to solve a semi-Markov
decision problem.

approximate

State Transition

E(V)values at each time by:= E{rt +y rt+1
+ykflV(B(t

EN;,)

=

E{n+1

+

+ykV(B(t+Y2P+2. . . + y%+k}+ k + l)),-v-t+2+y2rt+3. . . + y +3+k)+ k + l)),Decision Making

JW&}

We approximate the value of the box Bi according
averaging these values:

83

V(Bi)=~(~~+V”;‘...+V’;“).

Figure 2: The big-steps on the high-level learner. Thismodeling is closely related to semi-Markov
decisionprocesses (SMDPs).
The high-level decisions are only
allowed at events which occur whenever the state transition goes across the boundary of the box, or a certain
period of time passes.

3.3= E{n+k) + yV(B(t + k + 1)).

A Learning

Then, the TD-error
is given by

for V(B)(5)
in the high-level

moduleAlgorithm

V(B(t + k + 1)) - V(B(t))
AgentLinear Controllers

This result leads us to the learning algorithm for thehigh-level learner.
A Learning Method for High-Level
Module:To estimate box values, the algorithm updates by

B2,ol

S&ted
Bi
V(Bi)
Lad Vector

Primitive
Action*Y

High-level
Learner
T’JWtI

V(B(t))

@

I

I

t

V(B(t))+ a,, (TD-error),(7)

where a, is a learning coefficient, and TD-error is givenby (6). Although this algorithm is ad hoc, it works
very well for a reason that the learning in the linear
controllers makes up for undesirable effects.
A Learning Method for Linear Controllers:
The high-level module selects a linear controller associated with the corresponding state box. When the state
input vector is n-dimensional,
the linear controllers
have n + 1 parameters W = (uI~, w2,. . . w,+l)
per dimension of the output vector. The controllers learn W
to make good control. A linear controller determines
its state feedback-gain
parameters (gl, g2, . . . gn+l) as
to the control rule r by using W, . After that, primitive
actions are selected according to R until the termination. The linear controllers adopt an actor-critic architecture to learn feedback-gain
parameters. The actorcritic provides continuous action as the feedback-gain,
and makes use of V(Bi) for the critic. The output of
the critic is too coarse to calculate value gradient fromthe learned value function, because the approximation
function V(Bi) is flat in the same state region. Therefore we adopt a slightly modified actor-critic algorithm
using eligibility traces in the actor [8], that can improve
its policy even though the estimated value function is
inaccurate.

Actor-Critic
t

.

(6)

E

State Inout

to

RewardI_

1.

Figure 3: The hierarchical structure of the algorithm.
B, denote the state boxes, and every
B1,B2,...Bi...
small rectangle labeled “B,, 01” denotes a linear controller.
Figure 3 gives an overview of the hierarchical algorithm. The high-level learner accumulates state values
using tables with one entry for each box. In this case,each box value V(Bi) represents approximationof averaged values weighted by the visiting frequency overthe coarse regions, i.e., V(Bi) zt CrEB, U”(z)V”(x),where Bi denotes the box, V(z)denotes the probability of occupying state x under the policy r. The
learner also accumulates state value V(Bi). Unfortunately, this value function does not satisfy Bellman
equations in the strict sense. However, we try to provide a good approximation
algorithm.
Assume that the agent selects a linear controller attime t in the region B(t) and makes next decision attime t + rE+ 1 in the region B(t + k + 1). Then weV-12Figure 4: An instanceof the linear controller.
gi denotes a feedback gain which is characterized by wi according to gi = wi + N(0, u”). The controller learns wi
to achieve good control.

Figure 4 shows an instance of the actor-critic
algorithm in which the action is of one dimension.
Inthe beginning of the linear control, the actor selects
its feedback-gain
parameters (gr ,g2, . .. gn+l) according to gi = wi + N(0,(r2)for all i = 1,2,...n+ 1,
where N(0,a2)
denotes the normal distribution.
Ateach time step t < t + i 5 t + k, primitive actions
are selected until the termination of the linear control
according to
a =

cm+

c2g2 +~~~+Gzgn+$I,+11(8)where C= (cr,cs,...
c,) is the local continuous vector
at the time t + i as shown in Equation 4. When the linear controller terminates at time t + k + 1 in the region
B(t+k+l),alll’ mear controllers updates according toTraceiWi
Tracei+-Traceic

wi + CY,, (TD-error)+ (gi - wi)+$“)TraceiApplying

Swing-Up

4.1

Task

The behaviorof this algorithm
is demonstrated
through a computer simulation of a cart-pole swingup task. We modified the cart-pole problem describedin [l] so that the action is taken to be continuous. The
dynamics are modeled bygsinB+cosB
ri’ =-F-ml~Zsin

ez-x
(
2

=

F + me8+pcsgn(2)Mfm(-- /l,emeIm cd 6>4” sin B - e cos 0
M+m

>

>

- pcsgn(i)>where M = l.O(kg) denotes mass of the cart, m =O.l(kg) is mass of the pole, 2e = l(m) is the length ofv -513model of the cart-poletask.

the pole, g = 9.8( m / sec2) is the acceleration of gravity, F(N) denotes the force applied to cart’s center ofmass, pe = 0.05 and pLp= 0.01 are coefficient of frictionof the pole and the cart respectively.
In this simulation, we use discrete-time system to approximate theseequations, where At = 0.02sec. At each discrete time
step, the agent observes (z, i:, 6’,6’), and controls theforce F. The agent can execute action in arbitrary
range, but the possible action in the cart-pole system
is constrained to lie in the range [-lo, 10](N). Whenthe agent chooses an action which does not lie in that
range, the action F is saturated.
The system begins
with (x, i, 8,e) = (O,O, 3.0,O). When the cart collides
with the end of the track (-3.0 < x 5 3.0), the cart rebounds from the bumper with a coefficient of rebound0.2. The agent receives a reward (penalty) signal of(a) -1 when the pole falls over f0.8a(rad),(b) -4 when the cart bounces at the end of the track,
when e < -10(d) $1 when -0.1337r(rad/sec).

Traceito a Cart-Pole

Figure 5: A simulation(c) -3where Tracei denotes an eligibility trace on wi, and (Y,,is a coefficient of learning. TD-error is shown in Equation 6. The eligibility of wi corresponds to (gi - wi)that is similar to Gaussian unit [17] and Gullapalli’s
neural reinforcement
learning unit [7].
4

-2-e

x=0

or 10 < 4 (rad/sec),< B < 0.133n

and -2< 4 < 2

Implementation

The state space is normalized
as (x,?, B,8)=
+A rad, f10 rad/sec)(f3.0 m, AlO m/set,
into (f0.5, ~tO.5, f0.5, &0.5). The agent discretizes thenormalized state space evenly into 3 x 3 x 5 x 5 = 225
or 3 x 3 x 6 x 6 = 324 boxes, and attempts to storeV(Bi)in each box.
Each linear controller accumulates five feedback-gain
parameters wl, ~2, . . . ~5, forthe continuous-state
input is 4-dimensional.
In the linear controllers, an action a is generated by Equation 8,
where the normal distribution follows u = 0.5. Thenthe force F is executed according to F = a x 20.
The high-level hierarchy makes decision each time
when the continuous state input moves to a different
box or the state input keeps within the same box for2 seconds (100 steps).
The learning rate (Y, is set
to 0.3 in 3x3~6~6 boxes or to 0.1 in 3x3~5~5 boxes.
The learning coefficient of the actor-critic
is set to
Qae = 0.01.
The discount rate is set to y = 0.98.
Initial feedback-gain parameters are all set to zero for
all linear controllers.

I

’

I

I

’ Samphg

2
Actor-Critic

point

I

+

I

3x3~5~5 grids

3x3~6~6 grids
1
Actor-Critic

q&j
0

(

,

,

,

,

I

2e+c6

4e+ffi

6e+06

6e+06

1e+07

!
I

I

2e+O6

4e+O6

6: On-line

performanceusing 3x3~6~6

100
steps

Figure4.2

7: An example

Simulationof behavior

I

I

6e+06

Lie+06I

1e+07

Learning Steps

Learning Steps

Figure+j0

on 3x3~6~6

grids.

FigureResults

and 3x3~5~550

8: An example

grids.

100
steps

of behavior

150

on 3x3~5~5200

grids.

ries on learned greedy policies after 7,200,OOO steps (40hours on simulation time). The policies were feasible,
but no agent could obtain optimal swing-up behavior.
The reason is that the growth of swing-up behavior isslowed down for decreasing in opportunityof swingup, because the agent makes progress in keeping thepole vertical. The bottom in figure 7 and 8 shows thecorresponding
state-action
flow respectively.
The behavior seems to be a mixture of bang-bang control andlinear control.
Around B = 0, we should notice thata bang-bang control rule was found by the algorithms
with 3 x 3 x 6 x 6 boxes whereas a linear control rule
was found by the algorithms with 3 x 3 x 5 x 5 boxes.

Figure 6 shows the on-line performance with using different grids.
The performancemeasure is the occupancy rate of the current state in which the systemgives positive reward. The rate is calculated by using
20 independentruns. The results show that the proposed methods achieved learning to gain positive rewards. The increase of the performance with 3 x 3 x 5 x 5boxes is better than with 3 x 3 x 6 x 6 boxes: One reason
for this is an effect of decreasing the number of boxesby the coarse discretization.
The other is that the location of the boundaries of the boxes fits for this task
fortuitously.
Figure 7 and 8 show examples of trajecto-

v -514

Anyway, the algorithm founds preferable solutions.
We also tried
conventional
Q-learningusing
3x3~10~5 and 3x3~12~6 boxes, which are just twice
the boxes. But they could not hold the pole vertical.

Neuronlike Adaptive Elements That Can Solve Difficult Learning Control Problems, IEEE Transactions
on Systems,

Man,

pp.834-846(1983).

PI Buckland,5tion Processing

Evaluation:
We cannot conclude superiorityof theproposed method, because the complexityof our approach is obviously larger than that of conventional Qlearning in the experiment.
The experiment shows thatthe learning of the local linear controllers can make up
for lack of learning ability on the high-level module.
Effects of the Partitioning
Location:
In our test
cases, different discretizations
led the algorithms
tolearning quite different control rules, especially aroundB = 0. It makes clear that the shape and location of
the quantized regions have great effects on the performance. Joint use of variable-grid
methods (e.g. partigame [lo]), would be needed for generating
discreterepresentation
rather than the use of the fixed grids.
Time Intervals of High-level
Decision Making:In our approach, time intervals of decision making on
the high-level hierarchy are mostly owing to the size ofthe state boxes. It can be seen as an adaptive choiceof time intervals in continuous-time
domains [ll] [2].
Learning with Extremely
Coarse Value Approximation:
Many DP-based(RL) algorithms
are motivated by a desire for finding highly accurate valuefunctions.
However, it costs too much memory toapproximate
such functions
in many cases.
In contrast, our approach does not stick to finding accurate
value functions, because the policy can be improved bya gradient-ascentsearch without explicitly computing
value estimates.

polationral Information(1996).
S.,

Sutton,R. S. & Anderson,

A.

Y.

Systems& Moore,C. W.:

v-515

and Inter-

Advances
9,A.:

in Neu-pp.1005-1011
ApplyingOn-ligence,pp.753-760(1998).

[51 Dietterich, T. G.: The MAXQ Method for HierarchicalReinforcement
Learning,
Proceedingsof the 15th I&.
Conf. on Machine

Learning,

pp.118-126[61Doya, K.: Efficient

NonlinearControlArchitecture,ing Systems(1998).

with Actor-Tutor

Advances in Neural Information
9, pp.1012-1018(1996).

Process-

PI Gullapalli,V.:
Reinforcement
Learning
and Its Application to Control,
PhD Thesis, University of Massachusetts,
Amherst,COINS Technical
Report 92-10(1992).

P31Kimura,H. & Kobayashi,
S.:
An Analysis
of Actor/Critic
Algorithms
using Eligibility
Traces:Reinforcement
Learningwith Imperfect
Value Function,
15th International
Conference on Machine Learning,(1998).

pp.278-286

PILin, C. J. & Lin, C. T.: Reinforcement
ART-Based
Fuzzy Adaptive Learning

IEEE

Transactions

pp.709-731[lo]

on Neural

Learning for An
Control Network,
Vo1.7,

Networks,

No.3,(1996).

Moore A. W. & Atkeson, C. G.: The Parti-gamefor Variable

Resolution

AlLearn-

Reinforcement

MachineLearn-[ll]

Pareigis, S.: Adaptive
choice of grid and time in reinforcement
learning, Advances in Neural Information
Processing Systems 10, pp.1036-1042(1998).

[la]Parr, R. & Russell, S.:
Hierarchies of Machines,

tion Processing

Systems

Reinforcement

Learning[14] Sutton,
Learning

with

Advances in Neural Informa10, pp.1043-1049(1998).

[13] Sutton, R. S. & Barto, A.: Reinforcement
An Introduction,
MIT Press (1998).

Learning:

R. S., Precup, D. & Singh, S.: Intra-Option
about Temporary
Abstract
Actions,
Proceed-ings of the 15th International
Learning,[15] Tsitsiklis,

pp.556-564
J.

N.,

Temporal-Difference

Conference

on Machine(1998).
&

Roy,

B.

with

An

AnalysisofApprox-imation,IEEE Transactions
on Automatic
Vo1.42, No.5, pp.674-690(1997).

Control,[16] Watkins,

Learning

V.:

Function

Q-Learning,

A. G.,

Triangulation
Learning,

Processing

Ng,(1993).

ing in Multidimensional
State-spaces,ing 21, pp.199-233(1995).

REFERENCES

no.5,

line Search Techniques
to Continuous-State
Reinforcement Learning, 15th National Conf. on Artificial Intel-

CONCLUSION

This paper presented a hierarchical RL algorithm composed of TD method and local linear controllers
tosolve a non-linear control problem in which state andaction spaces are continuous.
It is a hybrid method between DP-based value estimationand policy improvement by gradient-ascent
without value estimation.
The
continuous state-action
space is discretized into an array of coarse boxes, and roughly the high-level hierarchy estimates the value functions over the discrete
space to find a globally preferable policy.
The local
linear controllers are to improve the policy by stochastic gradient-ascent.
This method does not need to fit
accurate value functions, therefore it may be promising
to overcome the curse of dimensionality.
The algorithm
was applied to a simulationof a cart-pole swing-up
problem, and better solutions are found than those of
traditional discrete RL methods.

[I] Barto,

6, pp.639-646

for Reinforcement

gorithm

6

Systems[31 Davies, S.: Multidimensional[41 Davies,

vol.SMC-13,

K. M. & Lawrence, P. D.: Transition
Point
Programming,
Advances in Neural Inforrna-

Dynamic

DISCUSSION

and Cybernetics,

C. J. C. H., & Dayan,

MachineLearning

P.:

8,pp.

Technical
55-68[17] Williams,
R. J.: Simple Statistical
Gradient
Algorithms
for Connectionist
Reinforcement
Machine Learning 8, pp.229-256(1992).

Note:(1992).
Following
Learning,