EÆcient Non-Linear Control by Combining Q-learning with
Local Linear Controllers
Hajime Kimura

Tokyo Institute of Technology
gen@fe.dis.titech.ac.jp
Abstract

This paper presents a new approach to reinforcement learning (RL) to solve a non-linear
control problem eÆciently in which state andaction spaces are continuous. 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. We providea hierarchical RL algorithm composed of local linear controllers and Q-learning, which
are both very simple. The continuous stateaction space is discretized into an array ofcoarse boxes, and each box has its own local linear controller as an abstract action.
The higher-level of the hierarchy is a conventional discrete RL algorithm that chooses
the abstract actions. Each linear controller
improves the local control policy by using anactor-critic method. The coarse state-space
discretization is a quite simple way to copewith the curse of dimensionality, but often
gives rise to non-Markovian e ects. In our
approach, the local linear controllers makeup for these undesirable e ects. The algorithm was applied to a simulation of a cartpole swing-up problem, and feasible solutions
are found in less 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Interdisciplinary Graduate School of Science and Engineering, Tokyo Institute of Technology, 4259 Nagatsuta
Midori-ku Yokohama 226{8502 JAPAN.

Shigenobu Kobayashi

Tokyo Institute of Technology
kobayasi@dis.titech.ac.jp
function. Theoretical results guarantee that several DP-based algorithms will nd optimal policies (e.g. [Watkins et.al 92], [Jaakkola et al. 93],
[Tsitsiklis et al. 97], etc.) and a great deal of effort has been made on the techniques to approximate
value functions (e.g., CMAC, Neural-Net [Lin 93]).
However, it is too expensive to t highly accurate
value functions, particularly in continuous state-action
spaces. To overcome this problem, several techniques are proposed (e.g., Parti-game [Moore 95],
Coarse grids +environment models +search techniques [Davies et al. 98], interpolation on a coarse grid[Davies 96]). On the other hand, it is shown thata local gradient-ascent search over stochastic policyspace is possible without explicitly computing value or
gradient estimates [Williams 92], [Kimura et al. 95],
[Kimura et al. 98]. That is to say, the DP-based RL
methods have features of a global search in terms of
optimality and computational expense, and the gradient RL methods have a feature of a local search. This
paper presents a new model-free approach that bridges
a gap between DP-based methods and local gradientascent methods.
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 Q-learningand local linear controllers, which are both 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-space quantization is a quite simple

way to cope with the curse of dimensionality. But
in many cases, it often gives rise to undesirable nonMarkovian e ects. In our approach, local linear controllers, which use a continuous-vector for the local
state representation, make up for these e ects.
Although hierarchical algorithms can often yield
sub-optimal solutions, there are signi cant bene ts
in learning eÆciency, search space, and re-use ofknowledge [Singh 92], [Kaelbling 93], [Dietterich98],[Sutton et al. 98], [Parr et al. 98]. In general, the lowlevel of the hierarchy is composed of learning control
modules that represent subtasks or abstract actions.
Each subtask is de ned in terms of termination conditions, and the low-level module is to nd a local
optimal policy. The RL techniques for discrete semiMarkov decision processes (SMDPs) would be applied
to learning of the high-level module that selects a lowlevel modules as abstract action. In our approach, thelow-level modules correspond to linear controllers.
Actor-critic methods [Barto et al. 83] are often used
for learning on the linear controllers [Gullapalli 92],
[Doya 96]. Generic actor-critic methods can be classied into a local gradient-ascent 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 algorithm using eligibility traces in the actor can improve its stochastic policy
even though the estimated value function is inaccurate[Kimura et al. 98]. We take advantage of this method
for the local policy improvement.
This paper is structured as follows. First, we review the basic notion of RL and control problems incontinuous state dynamic systems. In Section 3 weintroduce the generalization techniques for continuous state-action spaces and the hierarchical algorithm
combining Q-learning with linear controllers. Section
4 presents behavior of the algorithm through simulations of a cart-pole swing-up task. In Section 5, wesummarize the paper and discuss some directions ofcombining other methods for future work.
2

Problem Formulation

2.1 Markov 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 transition in 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 learningalgorithms are studied. In MDPs, the next statea yis chosen according to the transition probability pxy,and the reward
is given randomly according to the expectation rxa. but the agent does not know paxy and rxa
ahead of time. The objective of reinforcement learning
is to construct a policy that maximizes the agent's performance. A natural performance measure for in nitehorizon tasks is the cumulative discounted reward:
1
X
k
Vt =
rt k ,(1)+

k =0

where the discount factor, 0  < 1 speci es theimportance of future rewards, and Vt is the value ontime t. In MDPs, the value can be de ned as:
V (x) = E


"1
X

#

k

k =0

rk jx0 = x,(2)where E denotes the expectation assuming the agent
always uses stationary policy . The objective in
MDPs is to nd an optimal policy that maximizes thevalue of each state x de ned by Equation 2. In MDPs,
The optimalvalue of taking action a in state x, denoted Q(x; a), satis es the Bellman equations for all
x and a:X
Q (x; a) = rxa +paxy maxQ (y; a0 )
(3)
a
y

0

2.2 A Non-Linear Control Problem

We are given learning control of non-linear dynamic
systems in which : State and action spaces are continuous and multidimensional.
 The task could be decomposed into several local
linear or bang-bang control tasks.
 The agent does not know dynamics of the environment ahead of time.
Throughout the paper, we use a cart-pole swing-up
task for the example.
3

Combining Q-learning with Local
Linear Controllers

3.1 Hierarchical Decomposition

In our approach, the agent adopts hierarchical state
representation. The higher-level of the hierarchy uses
discrete representation of the state variables by coarse
quantization. Representative points are situated at thecenter of the grid's boxes. Each box has its own local linear controllers as discrete abstract actions, thatis, the controllers in a particular box are di erently
initialized.
Assume that given a n-dimensional state input(x ; x ;    xn) and the correspondingbox (Bi) withthe representative point at (bi ; bi ;    bin), then the lowlevel linear controller gets a local continuous input
C = (c ; c    cn) = (x bi ; x bi ;    ; xn bin ) . (4)Figure 1 shows an example of the state representationin which the state space is two-dimensional.
1

2

1

2

1

1

2

1

2

B1

B2

2

Decision Making

X2

B3
State Input (X1, X2)
Discrete State = B2

0State Transition

X2

B1

B2

B3

B4

Vector C
Linear controller uses
this vector.

X1

Figure 1: An example of the hierarchical state representation in a 2-dimensional task. Small circles atthe center of the grid's boxes denote its representative
points.
3.2 Event-driven Decision Making

In dynamic control, an optimal policy often selects thesame action (or holds similar continuous action) for acertain period of time. Then, uniform regions are likely
to exist in the state space where all of the states havethe same (or similar) optimal 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
an extension of Markov options [Sutton et al. 98] inwhich the policy is given by linear control and thetermination condition is given by the boundary of thebox.
Figure 2 helps to de ne the big-steps that the highlevel learner takes. If all the linear controllers holdstationary policy, the high-level learner is to solve asemi-Markov decision problem.
When a linear controller (option) o is taken, then primitive actions
are selected according to its linear control
rule o until the next decision making occurs on thehigh-level hierarchy. In this paper, we will use theofollowing notation based on [Sutton et al. 98]. Let  (x)

B4

0

X1

Figure 2: The big-steps on the high-level learner. Thismodeling is closely related to semi-Markov decision
processes (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.
be the primitive action taken in state x according too. Assume that current o terminates at next time step
according to the probability T (x; a), where a = o(x).
Then, we can de ne the optimal option-value function
recursively byQ (x; o)= r + (1ax

+ T (x; a)T (x; a))
X
y

X
y

!

p Q (y; o)axy!

p max Q (y; o0 ) ; (5)
a
xy

o0

where
a = o (x). If all states x, y are discrete ando is stationary, then Equation 5 can be solved by
Intra-Option value learning [Sutton et al. 98]. Unfortunately, the state spaces are continuous and it is too
expensive to learn the accurate value function. In thenext section, we will present a new method that uses
Q-values averaged in the coarse regions.
3.3 A Learning Algorithm

Figure 3 gives an overview of the hierarchical algorithm. The high-level decision maker accumulates Qvalues using tables with one entry for each box-option
pair. In this case, each box-option value (or box value)
Q(Bi ; o) and V (Bi ) represent approximation of averaged values weighted by the visiting
frequency overthe coarse regions,P i.e., V (Bi) ' Px2B U  (x)V  (x),and Q(Bi; o) ' x2B U  (x)Q(x; o), where Bi denotes the box, U o (x) denotes the probability of occupying state x under the policy . The learner also
accumulates state value V (Bi). Unfortunately, thisvalue function does not satisfy Bellman equations iniiAgentLinear Controllers BxO
B1,o1

B1,o2

B1,o3

B2,o1

Primitive
ActionSelected
Bi, ojV(Bi)Local Vector

Bi, ojHigh-level
Decision Maker

State Input

Bn,o1

Bn,o3
Actor-Critic

Q-learning, TD(0)RewardFigure 3: The hierarchical structure of the algorithm. B ; B ;    Bi    Bn denote the state boxes, and every
small rectangle labeled \B; o" denotes a linear controller. In this gure, a particular box Bi has three controllers
which are di erently initialized.
1

2

the strict sense. However, we try to provide a good A Learning Method for High-Level Module:
approximation algorithm.
To estimate box values, the algorithm updates by
Assume that the agent selects ot at time t in the region
V (B (t)) V (B (t)) + v (TD-error) ,(8)
B (t) and makes next decision at time t + k + 1 in theregion B(t + k + 1). Then we approximate values at where v is a learning coeÆcient, and TD-error is givenby (7). Similarly, the box-option value is updated byeach time by:Q(B (t); ot ) Q(B (t); ot )E fVt g ' E frt + rt + rt    + k rt k g
0
1
k
k
i
h 1
+ V (B(t + k + 1)),XX
+ v k + 1 @ rt i j A
E fVt g ' E frt + rt + rt    + k rt k gij!
+ k V (B(t + k + 1)),
k
X
i
...
max
Q(B (t + k + 1); o0)+ k +1 1oii
E fVt k g ' E frt kg + V (B (t + k + 1)).
Q(B (t); ot ) .
(9)
We approximate the value of the box Bi according toaveraging these values:
Although this algorithm is ad hoc, it works very wellfor two reasons:1
V (Bi ) =Vt + Vt    + Vt k . (6)k+1
1. Policies that are greedy for Q-functions are optimal if the Q-functions are a certain degree ofThen, the TD-error for V (B) in the high-level module
approximation [Singh et al. 94], [Heger 96].
is given by
0
1
2. In our approach, learning in the linear controllers
kiXX
makes up for undesirable e ects.
1jA
TD-error = k + 1 @ rt iij
A Learning Method for Linear Controllers:!
k
The high-level decision maker selects one of B Xi
O linear controllers according to some exploration+ k +1 1
V (B (t + k + 1)) V (B (t)) .
strategy, where B denotes the number of the statei
O is the number of possible options per each(7) boxes,box. When the state input vector is n-dimensional,
This result leads us to the learning algorithm for the the linear controllers have n + 1 parameters W =(w ; w ;    wn ) per dimension of the output vector.
high-level module.
2

+1

+2

+

+1

+1

+1

2

+2

1

+3

+

+

=0

=0

+1

=0

+

+

+1

+

+

=0

=0

+1

=0

1

2

+1

0

c1
c2

-

jj #
jj "!
H

g1

g2

H

-

...

cn

-

...

H
H
H
X
X
X

...

X
X

P









gn
gn+1

gi ci

-

a

Initial feedback-gain parameters are all set to zero, except that the linear controllers in the same state region
have di erent initial o sets of the primitive actions,
i.e., every wn are di erent. Owing to this initializing, the agent can execute various actions even if thelinear controllers do not move the parameters at all.
+1

1
Figure 4: An instanceof the linear controller. gi denotes a feedback gain which is characterized by wi according to gi = wi + N (0;  ). The controller learns
wi to achieve good control.


2

The controllers learn W to make good control. A linear controller o determines its state feedback-gaino parameters (g ; g ;    gn ) as to the control rule  byusing W , . After
that, primitive actions are selectedaccording to o until the termination of the option.
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 at in the same state region. Therefore we adopt a slightly modi ed actor-critic algorithm
using eligibility traces in the actor [Kimura et al. 98],
that can improve its policy even though the estimatedvalue function is inaccurate.
Figure 4 shows an instance of the actor-critic algorithm in which the action is of one dimension. In the
beginning of the option, the actor selects its feedbackgain parameters (g ; g ;    gn ) according to gi =wi + N (0;  ) for all i = 1; 2;    n + 1, where N (0;  )denotes the normal distribution. At each time stept < t + i  t + k, primitive actions are selected until
the termination of the option according toa = c g + c g +    + cngn + gn , (10)where C = (c ; c ;    cn) is the local continuous vector
at the time t + i as shown in Equation 4. When theoption terminates at time t + k +1 in the region B(t +k + 1), all linear controllers updates according to
T raceiT racei + (gi wi )wi
wi + ac (TD-error) T raceik
1 (Xj) T racei
T raceik+1
1

2

Applying to a Cart-Pole Swing-Up
Task

The behavior of this algorithm is demonstrated
through a computer simulation of a cart-pole swingup task. We modi ed the cart-pole problem describedin [Barto et al. 83] so that the action is taken to becontinuous.

+1

1

2

1 1

1

4

2

+1

2

2 2

+1

2

+1

j =0

,where T racei denotes an eligibility trace on wi, andac is a coeÆcient of learning. TD-error is shownin Equation 7. The eligibility of wi corresponds to(gi wi) that is similar to Gaussian unit [Williams 92]
and Gullapalli's neural reinforcement learning unit forcontinuous action [Gullapalli 92].









jj










F

-

x=0

x

-

Figure 5: A simulation model of the cart-pole task.
4.1 Details of the Cart-Pole Simulation

The dynamics are modeled by
g sin  + cos  F m` M m  sgn x


 =
m

_ 2 sin + c
+



` 43

cos2

(_)

p _
m`

,

M +m



F + m` _2 sin   cos  c sgn(x_ )
x =
,
M +m
where M = 1:0(kg) denotes mass of the cart, m =0:1(kg) is mass of the pole,2` = 1(m) is the length ofthe pole, g = 9:8(m=sec2) is the acceleration of gravity, F (N) denotes the force applied to cart's center ofmass, c = 0:05 and p = 0:01 are coeÆcient of fric-tion of the pole and the cart respectively. In this simulation, we use discrete-time system to approximate
these equations, where t = 0:02sec. At each discrete
time step, the agent observes (x; x_ ; ; _), and controls
the force 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 [ 10; 10](N ). Whenthe agent chooses an action which does not lie in that

range, the action F is saturated. The system begins
with (x; x;_ ; _) = (0; 0; 3:0; 0). When the cart collides
with the end of the track ( 3:0  x  3:0), the cart rebounds from the bumper with a coeÆcient of rebound
0:2. The agent receives a reward (penalty) signal of(a) 1 when the pole falls over 0:8 (rad),(b) 4 when the cart bounces at the end of the track,(c) 3 when _ < 10 or 10 < _ (rad/sec),(d) +1 when 0:133 < 0:133 and 2 < _ < 2(rad/sec).
Note that the domain shown here di ers from traditional cart-pole tasks in that the environment has no
termination condition.
4.2 Implementation

In this experiment, the state space is normalized as(x; x;_ ; _)=(3:0 m; 10 m/sec;
 rad; 10 rad/sec) into (0:5; 0:5; 0:5; 0:5).
The agent discretizes the normalized state space evenly
into 3  3  5  5 = 225 or 3  3  6  6 = 324 boxes,
and attempts to store in each box V (Bi ) and Q(Bi ; o).
Each linear controller accumulates ve feedback-gain
parameters w ; w ;    w , for the continuous-state input is 4-dimensional. On each state box, the high-level
decision maker selects one of 3 (or 4) options. When
3 options are within the box, the initial parameters
are set to w = 1=3, w = 0, w = 1=3 respectively.
When 4 options are within the box, the initial parameters are set to w = 3=8, w = 1=8, w = 1=8,
w = 3=8 respectively. In the linear controllers, anaction a is generated by Equation 10, where the normal distribution follows  = 0:5. Then the force F is
executed according to F = a  20.
The high-level hierarchy makes decision each time
when the continuous state input moves to a di erent
box or the state input keeps within the same box for 2
seconds (100 steps). It uses -greedy exploration strategy, kthat is, choosing greedy options with probability
0:99 , where k is the period of time steps on the previous option. The learning rate v is set to 0:3 in
3x3x6x6 boxes or to 0:1 in 3x3x5x5 boxes. The learning coeÆcient of the actor-critic is set to ac = 0:01.
The discount rate is set to = 0:98.
1

2

5

5

5

5

5

5

5

5

4.3 Simulation Results

Figure 6, 9, 12, and 15 show the on-line performancewith using di erent grids and di erent number of abstract actions. The performance measure is the occupancy rate of the current state in which the systemgives positive reward. The rate is calculated by using 20 independent runs. The results show that the
proposed methods achieved learning to gain positive
rewards. However, Q-learning-only methods in which

linear controllers do not learn (i.e., ac = 0) couldn't
learn it at all. It is clear that learning on linear controllers has these e ects. The increase of the performance with 3  3  5  5 boxes is better than with3  3  6  6 boxes. One reason for this is an effect of decreasing the number of boxes by the coarse
discretization. The other is that the location of theboundaries of the boxes ts for this task fortuitously.
Since the agents retained the exploration strategy for
all learning steps, the performance could not approach
to one. Figure 7, 10, 13 and 16 show examples oftrajectories on learned greedy policies after 7,200,000
steps (40 hours on simulation time). The policies werefeasible, but no agent could obtain optimal swing-up
behavior. The reason is that the growth of swing-up
behavior is slowed down for decreasing in opportunityof swing-up, because the agent makes progress in keeping the pole vertical.
Figure 8, 11, 14 and 17 show the corresponding stateaction ow respectively. The behavior seems to bea mixture of bang-bang control and linear control.
Around  = 0, we should notice that a bang-bang control rule was found by the algorithms with 3  3  6  6boxes whereas a linear control rule was found by thealgorithms with 3  3  5  5 boxes. Anyway, thealgorithm founds preferable solutions.
Figure 18 and 19 show the on-line performance of
conventional Q-learning using 3x3x10x5 and 3x3x12x6
boxes, which are just twice the boxes. The performance is slightly better than that of Q-learning onlyin Figure 6, 9, 6 and 9, but they could not learn thecontrol to keep the pole standing. The results showthat the task is not trivial.
5

Discussion

Evaluation: We cannot conclude superiority of the

proposed method, because the complexity of our approach is obviously larger than that of conventional
Q-learning in the experiment. The experiment showsthat the learning of the local linear controllers canmake up for lack of control ability in the high-level
decision maker.
E ects of the Partitioning Location: In our test
cases, di erent discretizations led the algorithms tolearning quite di erent control rules, especially around = 0. These things make it clear that the shape andlocation of the quantized regions have great e ects on
the performance. Joint use of variable-grid methods(e.g. parti-game [Moore 95]), would be needed for generating discrete representation rather than the use of
the xed grid.
Time Intervals of High-level Decision Making:In our approach, time intervals of decision making on

1

Sampling point
Q-learning + Linear Controller
Q-learning Only 3x3x6x6

Ratio of the agents in reward state over 20 runs

Ratio of the agents in reward state over 20 runs

1

0.8

0.6

0.4

0.2

0

Sampling point
Q-learning + Linear Controller
Q-learning Only

0.8

0.6

0.4

0.2

0
0

2e+06

4e+06

6e+06
Learning Steps

8e+06

1e+07

0

2e+06

4e+06

6e+06
Learning Steps

8e+06

1e+07

Figure 6: On-line performance using 3x3x6x6 grids
and 4 abstract actions.

Figure 9: On-line performance using 3x3x6x6 grids
and 3 abstract actions.

Figure 7: An example of swing-up behavior on
3x3x6x6 grids and 4 actions.

Figure 10: An example of swing-up behavior on
3x3x6x6 grids and 3 actions.

0.4

0.2
State or Action

0.2
State or Action

ActionTheta / (2Pi)
X / 6 (m)0.4

ActionTheta / (2Pi)
X / 6 (m)

0

0

-0.2

-0.2

-0.4

-0.4

0

50

100
steps

150

Figure 8: Detail of the behavior.

200

0

50

100
steps

150

Figure 11: Detail of the behavior.

200

1

Sampling point
Q-learning + Linear Controller
Q-learning Only

Ratio of the agents in reward state over 20 runs

Ratio of the agents in reward state over 20 runs

1

0.8

0.6

0.4

0.2

0

Q-learning + Linear Controller
Q-learning Only
0.8

0.6

Sampling point

0.4

0.2

0
0

2e+06

4e+06

6e+06
Learning Steps

8e+06

1e+07

0

2e+06

4e+06

6e+06
Learning Steps

8e+06

1e+07

Figure 12: On-line performance using 3x3x5x5 grids
and 4 abstract actions.

Figure 15: On-line performance using 3x3x5x5 grids
and 3 abstract actions.

Figure 13: An example of swing-up behavior on
3x3x5x5 grids and 4 actions.

Figure 16: An example of swing-up behavior on
3x3x5x5 grids and 3 actions

ActionTheta / (2Pi)
X / 6 (m)0.4

0.2State or Action

0.2
State or Action

ActionTheta / (2Pi)
X / 6 (m)

0.4

0

0

-0.2

-0.2

-0.4

-0.4

0

50

100
steps

150

Figure 14: Detail of the behavior.

200

0

50

100
steps

150

Figure 17: Detail of the behavior.

200

the high-level hierarchy are mostly owing to the size ofthe state boxes. It can be seen as an adaptive choice oftime intervals in continuous-time domains [Pareigis 98][Buckland et al. 93].

Ratio of the agents in reward state over 20 runs

1

Learning with Extremely Coarse Value Approximation: Many DP-based (RL) algorithms are

0.8

0.6

Q-learning Only, 3 actions
Q-learning Only, 4 actions

0.4

0.2

0
0

2e+06

4e+06

6e+06
Learning Steps

8e+06

1e+07

Figure 18: On-line performance of conventional Qlearning using 3x3x10x5 grids and 3 (or 4) abstract
actions. It is just twice as many as the boxes in Figure 12 and 15.

motivated by a desire for nding highly accurate valuefunctions. However, it costs too much memory toapproximate such functions in many cases. In contrast, our approach does not stick to nding accurate
value functions, because the policy can be improved bya gradient-ascent search without explicitly computing
value estimates. However, shown in the experiments,
it costs many experiences instead of the memory required in DP-based methods.
Combining with Model-based Methods: Since
the proposed algorithm in this paper is a model-freeand memory-less method, many model-based methods can make use of it easily. It is interesting tonote that [Davies et al. 98] proposed a model-based
approach that uses environment models to make up
for the poor ability of the value function approximation.
6

This paper presented a hierarchical RL algorithmcomposed of Q-learning and local linear controllers to solvea non-linear control problem in which state and action
spaces are continuous. It is a hybrid method between
DP-based value estimation and policy improvement by
gradient-ascent without value estimation. The continuous state-action space is discretized into an arrayof coarse boxes, and roughly the high-level hierarchy
estimates the value functions over the discrete space
to nd a globally preferable policy. The local linear controllers are to improve the policy by stochastic gradient-ascent. This method does not need to t
accurate value functions, therefore it may be promising to overcome the curse of dimensionality. The algorithm was applied to a simulation of a cart-pole swingup problem, and better solutions are found than thoseof traditional discrete RL methods.

Ratio of the agents in reward state over 20 runs

1

0.8

0.6

Conclusions

Q-learning Only, 3 actions
Q-learning Only, 4 actions

0.4

0.2

Acknowledgements
0
0

2e+06

4e+06

6e+06
Learning Steps

8e+06

1e+07

Figure 19: On-line performance of conventional Qlearning using 3x3x12x6 grids and 3 (or 4) abstract
actions. It is just twice as many as the boxes in Figure 6 and 9.

We would like to thank reviewers for many helpfulcomments and suggestions.
References[Barto et al. 83] Barto, A. G., Sutton, R. S. and Anderson,
C. W.: Neuronlike Adaptive Elements That Can SolveDiÆcult Learning Control Problems, IEEE Transactions on Systems, Man, and Cybernetics, vol. SMC-13,
no.5, September/October 1983, pp. 834-846.

[Buckland et al. 93] Buckland, K. M. and Lawrence, P. D.:
Transition Point Dynamic Programming, Advances in
Neural Information Processing Systems 6 , pp. 639{646(1993).
[Davies 96] Davies, S.: Multidimensional Triangulation
and Interpolation for Reinforcement Learning, Advances in Neural Information Processing Systems 9 ,pp. 1005-1011 (1996).
[Davies et al. 98] Davies, S., Ng, A. Y. & Moore, A.: Applying Online Search Techniques to Continuous-State
Reinforcement Learning, 15th National Conference on
Arti cial Intelligence, pp. 753{760 (1998).
[Dietterich98] Dietterich, T. G.: The MAXQ Method for
Hierarchical Reinforcement Learning, Proceedings ofthe 15th International Conference on Machine Learning, pp. 118{126 (1998).
[Doya 96] Doya, K. : EÆcient Nonlinear Control with
Actor-Tutor Architecture, Advances in Neural Information Processing Systems 9 , pp. 1012{1018 (1996).
[Gullapalli 92] Gullapalli, V.: Reinforcement Learning
and Its Application to Control, PhD Thesis, Universityof Massachusetts, Amherst, COINS Technical Report92-10 (1992).
[Heger 96] Heger, M.: The Loss from Imperfect Value
Functions in Expectation-Based and Minimax-Based
Tasks, Machine Learning, 22,, pp. 197{225 (1996).
[Jaakkola et al. 93] Jaakkola, T., Jordan, M. I. & Singh,
S. P.: On the Convergence of Stochastic Iterative Dynamic Programming Algorithms, Neural Computation
6 , pp.1185{1201 (1993).
[Kaelbling 93] Kaelbling, L. P.: Hierarchical Learning in
Stochastic Domains: Preliminary Results, Proceedings of the 10th International Conference on Machine
Learning, pp. 167{173 (1993).
[Kaelbling et al.96] Kaelbling, L. P., & Littman, M. L.,& Moore, A. W.: Reinforcement Learning: A Survey,
Journal of Arti cial Intelligence Research, Vol. 4, pp.
237{277 (1996).
[Kimura et al. 95] Kimura, H., Yamamura, M. andKobayashi, S.: Reinforcement Learning by Stochastic
Hill Climbing on Discounted Reward, Proceedings ofthe 12th International Conference on Machine Learning, pp. 295{303 (1995).
[Kimura et al. 98] Kimura, H. & Kobayashi, S.: An
Analysis of Actor/Critic Algorithms using Eligibility
Traces: Reinforcement Learning with Imperfect Value
Function, 15th International Conference on Machine
Learning, pp.278{286 (1998).
[Lin 93] Lin, L. J.: Scaling Up Reinforcement Learning for
Robot Control, Proceedings of the 10th International
Conference on Machine Learning, pp. 182{189 (1993).
[Lin et al. 96] Lin, C. J. and Lin, C. T.: Reinforcement
Learning for An ART-Based Fuzzy Adaptive Learning
Control Network, IEEE Transactions on Neural Networks, Vol.7, No. 3, pp. 709-731 (1996).
[Moore 95] Moore A. W. & Atkeson, C. G.: The Partigame Algorithm for Variable Resolution Reinforcement
Learning in Multidimensional State-spaces, Machine
Learning 21 , pp. 199-233 (1995).

[Pareigis 98] Pareigis, S.: Adaptive choice of grid and timein reinforcement learning, Advances in Neural Information Processing Systems 10 , pp. 1036{1042 (1998).
[Parr et al. 98] Parr, R. & Russell, S.: Reinforcement
Learning with Hierarchies of Machines, Advances in
Neural Information Processing Systems 10 , pp. 1043{
1049 (1998).
[Singh 92] Singh, S. P.: Transfer of Learning by Composing Solutions of Elemental Sequential Tasks, Machine
Learning 8 , pp. 323-339 (1992).
[Singh et al. 94] Singh, S. P. and Yee, R. C.: An Upper
Bound on the Loss from Approximate Optimal-Value
Functions, Machine Learning, 16 , pp. 227-233 (1994).
[Singh 96] Singh, S. P., & Sutton, R.S.: Reinforcement
Learning with Replacing Eligibility Traces, Machine
Learning 22 , pp. 123-158 (1996).
[Sutton 88] Sutton, R. S.: Learning to Predict by the
Methods of Temporal Di erences, Machine Learning
3 , pp. 9-44 (1988).
[Sutton 90] Sutton, R. S.: Reinforcement Learning Architectures for Animats, Proceedings of the 1st International Conference on Simulation of Adaptive Behavior,
pp. 288-295 (1990).
[Sutton et al. 98] Sutton, R. S. & Barto, A.: Reinforcement Learning: An Introduction, A Bradford Book,
The MIT Press (1998).
[Sutton et al. 98] Sutton, R. S., Precup, D. & Singh, S.:
Intra-Option Learning about Temporary Abstract Actions, Proceedings of the 15th International Conference
on Machine Learning, pp. 556{564 (1998).
[Tsitsiklis et al. 97] Tsitsiklis, J. N., & Roy, B. V.: An
Analysis of Temporal-Di erence Learning with Function Approximation, IEEE Transactions on AutomaticControl, Vol.42, No.5, pp. 674{690 (1997).
[Watkins et.al 92] Watkins, C. J. C. H., & Dayan, P.:
Technical Note: Q-Learning, Machine Learning 8 , pp.
55-68 (1992).
[Williams 92] Williams, R. J.: Simple Statistical Gradient
Following Algorithms for Connectionist Reinforcement
Learning, Machine Learning 8 , pp. 229-256 (1992).