An Analysis of Actor/Critic Algorithms using Eligibility Traces:
Reinforcement Learning with Imperfect Value Functions

Hajime Kimura

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

Abstract
We present an analysis of actor/critic algorithms, in which the actor updates its policy
using eligibility traces of the policy parameters. Most of the theoretical results for eligibility traces have been for only critic's value
iteration algorithms. This paper investigates
what the actor's eligibility trace does. The
results show that the algorithm is an extension of Williams' REINFORCE algorithms
for in nite horizon reinforcement tasks, andthen the critic provides an appropriate reinforcement baseline for the actor. Thanks
to the actor's eligibility trace, the actor improves its policy by using a gradient of actual return, not by using a gradient of theestimated return in the critic. It enables theagent to learn a fairly good policy under thecondition that the approximated value function in the critic is hopelessly inaccurate forconventional actor/critic algorithms. Also, if
an accurate value function is estimated by thecritic, the actor's learning is dramatically accelerated in our test cases. The behavior of
the algorithm is demonstrated through simulations of a linear quadratic control problem
and a pole balancing problem.

1 Introduction

Actor/critic architecture is an adaptive version of policy iteration [Kaelbling et al.96]. In general, policy
iteration alternates two phases: a policy evaluation
phase and a policy improvement phase. The actor implements a stochastic policy that maps from a representation of a state to a probability distribution over
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
actions. The critic attempts to estimate the evaluation
function for the current policy. The actor improves its
control policy using critic's temporal di erence (TD)as an e ective reinforcement. In many cases, the policy
improvement is executed concurrently with the policy
evaluation, because it is not feasible to wait for thepolicy evaluation to converge.
The actor/critic algorithms have been successfully applied to a variety of delayed reinforcementtasks; ASE/ACE architecture for a pole balancing[Barto et al. 83] [Gullapalli 92], RFALCON for a polebalancing and for control of a ball-beam system[Lin et al. 96], a cart-pole swing-up task [Doya 96].
Although convergence proofs for the actor/critic algorithms (e.g. [Williams et al. 90] and [Gullapalli 92])
are less than value-iteration based algorithms suchas Q-learning [Watkins et.al 92], the actor/critic algorithms have the following practical advantages.
 It is easy to implement multidimensional continuous action, that is often mixed with discrete action [Gullapalli 92]. Because the actor selects action by its stochastic policy, therefore problems ofaction selection like as Q-learning does not exist.
The Q-learning needs to estimate returns for allstate-action pairs, but the critic would estimate
only the return of each state.
 Memory-less stochastic policies can be considerably better than memory-less deterministic policies in the case of partially observable
Markov decision processes (POMDPs) [Singh 94][Jaakkola 94] or multi-player games [Littman 94].
 It is easy to incorporate an expert's knowledge
into the learning system by applying conventional supervised learning techniques to the actor[Clouse et al. 92].
Eligibility traces are a fundamental mechanismthat has been widely used to handle delayed
reward [Singh 96]. Also the traces are often
used to overcome non-Markovian e ects [Sutton 95],

[Pendrith et al. 96]. In Barto, Sutton and Anderson's
ASE/ACE architecture, both the critic and the actor
make use of the eligibility trace. Theoretical results ofeligibility traces in the context of TD() [Sutton 88]
have been obtained. But, in actor/critic algorithms,
the e ect of the actor's trace has not been investigated.
This paper presents an analysis of an actor/critic algorithm, in which the actor improves its policy using
eligibility traces of the policy parameters. This may
be the rst analysis of the actor's eligibility traces.

the other is the actor improves its policy using TDerror. This paper especially investigates an algorithm
for the actor.

xt

t

-

2 Discounted Reward Criteria

6

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. The objective of reinforcement
learning is to construct a policy that maximizes theagent's performance. A natural performance measure
for in nite horizon tasks is the cumulative discounted
reward:1Xk
Vt =rt k ,(1)+

k =0

where the discount factor, 0  < 1 speci es theimportance of future rewards. Vt is called the actual
return, that speci es how good the reward sequence
after time t is. By this notation, the goal of the learning is to maximize the expected return. In MDPs, theexpected return can be de ned for all states as:
V (x) = E


"

1
X

k =0

#

k

rk jx0 = x,(2)where E denotes the expectation assuming
the agentalways uses stationary policy . V  (x) is called thevalue function, that speci es how good the given statex is. In MDPs, the goal of the learning is to nd an
optimal policy that maximizes the value of each statex de ned by Equation 2. Although similar value functions can be given in POMDPs, diÆculties to de ne
the optimum have pointed out in [Singh 94].

3 Actor/Critic Algorithms

Agent
Actor
a
stochastic policy 
reinforcement for a
TD-errorr + V^ (x +1 ) V^ (x )Figure 1 and 2 give an overview of actor/critic algorithms [Sutton 90] [Crites et al. 94]. There are many
ways to implement the policy and its updating scheme
in the actor. The algorithms for the critic are mostly
TD methods. We should notice the following two
points; one is the actor implements stochastic policy,

t

xt

t

t

t

Critic V^ (x)rObservation
RewardEnvironment-tAction?

Figure 1: A generic actor/critic framework.

1. The agent observes x in the environment, and theactor executes action a according to the current
stochastic policy .
2. The critic receives the immediate reward r , and thenobserves the resulting next state x +1 . The critic provides TD error as an useful reinforcement feedback to
the actor, according to(TD-error) = r + V^ (x +1 ) V^ (x ) ,where 0  < 1 is the discount factor, V^ (x) is an
estimated value function by the critic.
3. The actor updates the stochastic policy using the TDerror. If (TD-error) > 0, action a performed relatively good and its probability should be increased. If(TD-error) < 0, action a performed relatively poorly
and its probability should be decreased.
4. The critic updates estimated value function V^ (x) according to TD methods. e.g., TD(0) algorithm adjustsV^ (x ) V^ (x )+ (TD-error), where is the learningrate.
5. Go to step 1.
t

t

t

t

t

t

t

t

t

t

t

Figure 2: Main loop of the generic actor/critic algorithm.

4 Adding Eligibility Trace to the
Actor
4.1

t

t

Function Approximation for Stochastic
Policies

Details of the Algorithm

Figure 3 speci es the actor/critic algorithm that uses
the eligibility trace in the actor. The ASE/ACE system con gured for pole-balancing [Barto et al. 83] isjust an instance of this algorithm. The actor's eligibility in step 3 is the same variable de ned in Williams'
REINFORCE algorithms [Williams 92]. The eligibility ei(t) speci es a correlation between the associatedpolicy parameter wi and the executed action at. The
eligibility trace Di(t) is a discounted running averageof eligibility. It accumulates the agent's history. Whena positive reinforcement is given, the actor updates W
so that the probability of actions recorded in the history is increased. It means the TD-error at the timet a ects not only the action at but also at ; at ;   .
At rst glance, this idea is senseless for improving thepolicy, but it has very interesting features given in detail later. Note that the algorithm shown in Figure 3 is
identical to a stochastic gradient ascent for discounted
reward [Kimura et al. 97] when the actor's discountfactor = and the V^ (x) in the critic equals a constant b for all observations.
The actor requires a memory to implement W for thepolicy and to implement Di for the eligibility trace.
The amount of the memory for Di is equal to W 's.
1

4.3

t

t

t

In this paper, (a; W; x) denotes probability of selecting action a under the policy  in the observation x.
The (a; W; X ) is taken to be a probability density
function when the set of possible action is continuous. The policy is represented by a parametric function approximator using the internal variable vector
W . The agent can improve the policy  by modifying
W . For example, W corresponds to synaptic weights
where the action selecting probability is represented byneural networks, or W means weight of rules in classi er systems. The advantage of using the notationof the parametric function () is that computational
restriction and mechanisms of the agent can be speci ed simply by a form of the function, and then wecan provide a sound theory of learning algorithms forarbitrary types of the actor.
4.2

1. The agent observes x , and the actor executes action
a with probability (a ; W; x ).
2. The critic receives the immediate reward r , and thenobserves the resulting next state x +1 . The critic provides TD error to the actor according to(TD-error) = r + V^ (x +1 ) V^ (x ) , (3)where 0  < 1 is the discount factor, V^ (x) is an
estimated value function by the critic.
3. The actor updates the stochastic policy using the TDerror according to:
Eligibility:e (t) = @ ln (a ; W; x ) ,@w
Eligibility Trace: D (t) = e (t) + D (t 1) ,w (t) = (TD-error) D (t)W
W + W (t) ,thwhere w denotes the i component of W , e andD are the associated eligibility and eligibility trace
respectively, (0  < 1) is a discount factor for theeligibility trace, is the learning rate for the actor.
4. The critic updates estimated value function V^ (x) according to TD methods. e.g., TD(0) algorithm adjustsV^ (x) V^ (x) + (TD-error), where is the learningrate.
5. Go to step 1.
ttAssume that the actor's discount factor equals ,and for all t < 0, Di(t) = 0, then the algorithm shown

t

i

t

i

i

i

t

i

i

i

p

i

i

i

p

Figure 3: The actor/critic algorithm adding the eligibility trace to the actor.
in Figure 3 updates the policy parameters as:
1
X
t=0wi(t)=

2

An Analysis of the Algorithm

t

=
=
=
=

1
X
t=0



rt + V^ (xt+1 ) V^ (xt ) Di (t)

1
X



rt + V^ (xt ) V^ (xt )

t
X

+1

t=0

1
X
t=0

1
X
t=0

1
X
t=0

1
X

ei (t)

 t



 =t

1
X

ei (t)

 =t



 =0

ei (t)!

r + V^ (x +1 ) V^ (x )
!

 t

!

t 

r


ei (t) Vt V^ (xt )!

V^ (xt)(4)(5)

Equation 5 is given by Equation 1 and 4. Here we assume that the statistics of the random variable Vt depends only on the current policy parameter. It means
E fVt g is a deterministic function of W , where E de-notes the expectation operator. This assumption may
be right if the policy is converged to an equilibrium
point. The critic's estimation V^ (xt) is obviously independent of the action at the time t. From the theoryof Williams' REINFORCE algorithm [Williams 92],
the value Vt and V^ (xt) in Equation 5 can be seen
as a reinforcement signal and a reinforcement baseline respectively, then we have Efei(t) (Vt V^ (xt))g =(@=@wi)EfVtg. It says that the algorithm updates policy parameters statistically in a direction for increasing
the actual return Vt, not in a direction of a gradientof estimated value function in the critic. Also It canbe seen as an extension of reinforcement comparison
methods [Sutton et al. 98], then V^ (xt) corresponds to
the reference reward.
From the above analysis and Figure 3, we can explain what the actor's eligibility trace does. At thetime t, the algorithm reinforces at using TD error
rt + V^ (xt ) V^ (xt) as a temporary expedient, thereafter the actor's eligibility trace replaces V^ (xt ) withthe actual return (rt + rt + rt   ) in order.
The critic does not a ect the direction of the average
update vector, because the critic works as a reinforcement baseline. Therefore, the actor can improve its
policy, whether the critic is able to learn the valuefunction or not. If the critic approximates the valuefunction well, the actor's learning would be accelerated.
The above results are under the special condition =. If = 0, the actor updates W in the directionof the gradient of the approximated value function in
the critic. The (0 < < ) interpolates between
the above two limiting cases. The characteristics ofthe are similar to the  in TD() [Sutton 88] andQ()-learning [Peng et al. 94].
+1

+1

+2

2

+1

+3

5 Preliminary Experiments
This section demonstrates the performance of the algorithm applying to a simple linear control problem.
5.1

A Linear Quadratic Regulator (LQR)

The following linear control problem can serve as abenchmark of delayed reinforcement tasks [Baird 94].
At a given discrete-time t, the state of the environment is the real value xt. The agent chooses a control
action at that is also real value. The dynamics of theenvironment is:
xt = xt + at + noise ,(6)
where the noise is the normal distribution that follows
the standard deviation noise = 0:5. The immediate+1

reward is given by= xt at .
(7)
The goal is to maximize the total discounted reward,de ned by Equation 1 or 2 for all x. Because the task isa linear quadratic regulator (LQR) problem, it is possible to calculate the optimal control rule. From thediscrete-time Riccati equation, the optimum regulator
is given by2p
at = k xt , where k = 1
1 + 2 + 4 + 1.
(8)
The optimum value function is given by V (xt) =k xt , where k is a some positive constant. In thisexperiment, the set of possible states is constrained tolie in the range [ 4; 4]. When the state transition given
by Equation 6 does not result in the range [ 4; 4], thext is truncated.When the agent chooses an action thatis not lie in the range [ 4; 4], the action executed in
the environment is also truncated.
rt

1

2

5.2
5.2.1

2

2

2

1

2

2

Implementation for the LQR Problem
The Actor

Remember the policy (a; W; X ) is a probability density function when the set of possible action is continuous. The normal distribution is a simple multiparameter distribution for a continuous random variable.
It has two parameters, the mean  and the standard
deviation . When the policy function  is given by
the equation 9, the eligibility of  and  are1(a ) ) (9)(a; ; ) = p exp(
2
 2
2

2

= at (at )
e =

e

(10)

2

2

3

2

.

(11)

One useful feature of such a Gaussian unit
[Williams 92] is that the agent has a potential to control its degree of exploratory behavior. We must draw
attention to the fact that the eligibility is to divergent
when  goes close to 0, because the parameter  is
occupying the denominators of Equation 10 and 11.
The divergence of the eligibility has a bad in uence on
the algorithm. One way to overcome this problem is
to control the step size of the update parameter vector using . It is obtained by setting the learning rate
parameter proportional to  , then the eligibility canbe seen as(a )  . (12)e = at  ,e = t
2

2



2

The actor would rst compute  and  deterministically and then draw its output from the normal distribution that follows mean equal to  and standard

1

2

1

deviation equal to . The actor has two internal variables, w and w , and computes the values of  and 
according to

The Critic(13)
 = w1 xt ,  =1 + exp( w2) :Then, w1 can be seen as a feedback gain. The reason
for this calculation of  is to guarantee the  to keep
positive. The e1 and e2 are the characteristic eligibilities of w1 and w2 respectively. From Equation 12, e1
and e2 are given by@
e1 = e = (at ) xt ,
(14)
@w1
@
 = ((at )2 2 )(1 ) .(15)e2 = e@w2
The w1 is initialized to 0:35  0:15, and w2 = 0, i.e., = 0:5. The learning rate p is xed to 0:001.
5.2.2

Simulation Results

The critic quantizes the continuous state-space ( 4 x  4) into an array of boxes. We have tried two typesof the quantizing: one is discretizing x evenly into 3
boxes, the other is 10 boxes. And the critic attempts tostore in each box a prediction of the value V^ by using
TD(0) [Sutton 88]. The learning rate for TD(0) is
xed to 0:2.
5.3

Figure 4, 5, 6, 7 and 8 show the performance of 100
trials in the LQR problem with the discount rate =0:9.
Figure 4 shows the performance of the algorithm, inwhich the critic uses 3 boxes, the actor does not use
eligibility traces, i.e, = 0. Figure 6 shows the performance where the critic uses 10 boxes, the actor does
not use the traces. The algorithm in Figure 6 converged close to the optimum feedback gain. In contrast, Figure 4 didn't. The reason for this is that theability of the function approximation (3 boxes) is insuÆcient for learning policy without the trace.
Figure 5 shows the performance where the critic uses
3 boxes, the actor uses the trace, = = 0:9. It
achieved much better results in terms of both thelearning eÆciency and the quality of the mean value ofthe converged policy than the algorithm in Figure 4 or
5. Obviously, the actor's eligibility trace relates these
two advantages. The reason for the learning eÆciency
in this case may be that the actor's trace accelerates
propagating information. The better quality of thepolicy is clearly owing to the property that the actor
improves its policy by using a gradient of actual return, shown in Section 4.3. Therefore, the algorithm
500

1000

1500

2500

optimum

2000

Learning steps

3000

4000

4500

gamma = 0.9
Critic’s Grid = 3
beta = 0.0

3500

5000

using the trace was not in uenced by the critic's ability in terms of the quality of the mean of the policy.
We can also see this property in Figure 8, but its deviation is considerably large. Figure 9 shows the valuefunction that is de ned by Equation 1 and 7 over theparameter space  and . The value of performance isfairly at around the optimal solution. This is the reason that the deviation of the policy is large in Figure
8. This example makes it clear that the critic controls
step-size of the actor's backups so that the step-size istaken to be smaller around the local maximum.
The algorithm in Figure 7 achieved best results interms of both the mean and the deviation of the policy. The reason for this may be owing to the critic's
perfect value estimation.
In this preliminary experiment, we can see that thealgorithm using the actor's eligibility trace performed
better than the algorithm without using the trace inthe same computational resources.
Here we presented the results of the actor-critic thatuse only TD(0) in the critic, but we have also experimented on TD() where 0 <   1. Roughly speaking,we have poor performance when the  approaches close
to 1. It follows from this that the eligibility trace inthe critic cannot make up for the critic's poor abilityof function approximation. The details of the experiments using TD() will appear in other papers.
0.6

0.4

0.2

0

-0.2

-0.4

-0.6

-0.8

-1
0

Figure 4: The average performance of 100 trials without the actor's eligibility trace ( = 0). The critic uses
3 boxes.

Feedback gain

0.6

0.4

0.2

0

-0.2

-0.4

-0.6

-0.8

-1
0

500

500

optimum

1000

1500

1500

optimum

1000

2000

2500

3000

Learning steps

2500

3000

Learning steps

2000

4000

4500

gamma = 0.9
Critic’s Grid = 3
beta = 0.9

3500

4000

4500

gamma = 0.9
Critic’s Grid = 3
beta = 0.9

3500

5000

5000

Figure 5: The average performance of 100 trials using
the actor's trace = 0:9. The critic uses 3 boxes.

0.6

0.4

0.2

0

-0.2

-0.4

-0.6

-0.8

-1
0

Figure 6: The average performance of 100 trials without the actor's trace ( = 0). The critic uses 10 boxes.

0.6

0.4

0.2

0

-0.2

-0.4

-0.6

-0.8

-1

0.6

0.4

0.2

0

-0.2

-0.4

-0.6

-0.8

-1

0

1000

optimum

500

500

1000

1500

2000

2500

3000

Learning steps

2500

3000

Learning steps

2000

optimum

1500

4000

4500

gamma = 0.9
Critic’s Grid = 10
beta = 0.9

3500

3500

4500

beta = 0.9

4000

5000

5000

Figure 8: The average performance of 100 trials. =
0:9. The agent learns without the critic, i.e., the critic
provides V^ (x) = 0 for all x.

0

Figure 7: The average performance of 100 trials using
the actor's trace = 0:9. The critic uses 10 boxes.

Feedback gain
Feedback gain

Feedback gain
Feedback gainOptimum point











0



-50



-100



F

-150
-200

x=0

-250
-300
0

-1.5

0.5
-1

-0.5

0

0.5

Feedback gain

Deviation
1

1.5

1

2

Figure 9: Value function over the parameter space inthe LQR problem, where = 0:9. It is fairly ataround the optimum:  = 0:5884,  = 0.

6 Applying to a Cart-Pole Problem

6.1

Problem Formulation_ 2 sin + c
+



` 43

(_)

p_

cos2

M +m



F + m` _ sin   cos  c sgn(x_ ),=M +mwhere M = 1:0 (kg) denotes mass of the cart, m = 0:1(kg) is mass of the pole, 2` = 1 (m) is a length ofthe pole, g = 9:8 (m=sec ) is the acceleration of gravity, F (N) denotes the force applied to cart's center ofmass, c = 0:0005 is a coeÆcient of friction of cart,
p = 0:000002 is a coeÆcient of friction of pole. In
this simulation, we use discrete-time system to approximate these equations, where t = 0:02 sec. At eachdiscrete time step, the agent observes (x; x_ ; ; _), andcontrols the force F . The agent can execute action in
x

2

2

Details of the AgentIn this experiment, the actor adopts similar implementation shown in Equation 9 and 12. The
state space is constrained in the range (x; x;_ ; _) =(2:4 m; 2 m/sec;   12=180 rad; 1:5 rad/sec).
The actor has ve internal variables w    w , andcomputes the  and  according to
x
x_
t
_
 = w t +w t +w
+
w t ,
2:4
2
12=180
1:5
1(16)
 = 0:1 +1 + exp( w ) :Similarly to Equation 14 and 15, the eligibilitiese    e are given bye = (at ) xt , e = (at ) x_t
e = (at ) t , e = (at ) _te = ((at )  )(1 + 0:1 ) .
The critic discretizes the normalized state space evenly
into 3  3  3  3 = 81 boxes, and attempts to store ineach box V^ by using TD(0) algorithm [Sutton 88]. The
parameters are set to = 0:95, = 0:5, p = 0:001.
1

1

The dynamics of the cart-pole system is modeled by g sin  + cos  F m` M m  sgn x
m`
 =


,
m


-

arbitrary range, but the possible action in the cart-polesystem is constrained to lie in the range [ 20; 20](N).
When the agent chooses an action which is not lie inthat range, the action executed in the system is truncated. The system begins with (x; x;_ ; _) = (0; 0; 0; 0).
The system fails and receives a reward (penalty) signalof 1 when the pole falls over 12 degrees or the cartruns over the bounds of its track ( 2:4  x  2:4),
then the cart-pole system is reset to the initial state.
6.2

The behavior of this algorithm is demonstrated
through a computer simulation of a cart-pole control task, that is a multi-dimensional nonlinear nonquadratic problem. We modi ed the cart-pole problem described in [Barto et al. 83] so that the action istaken to be continuous.

xj j

Figure 10: The cart-pole problem.

-350

-2

-

2

3

5

4

5

1

5

1

2

3
5

6.3

4

2

2

Simulation Results

Figure 11 shows the performance of three learningalgorithms in which the policy representation is the

100

Actor/Critic
using actor’seligibility trace

50

150

Trials250

Actor only
using actor’seligibility trace

200

350

400

450

Actor/Critic without
actor’s eligibility trace

300

500

same. The actor/critic algorithm using the actor's
trace achieved best results. In contrast, the algorithm
without using the trace couldn't learn the control policy because of the poor ability of function approximation in the critic.
3000

2500

0

Representation of Policies: First of all, actor/critic algorithms should have suÆcient ability toapproximate policies. If it is satis ed, use of the actor's eligibility trace ( = ) enables to learn an acceptable policy with less cost rather than increasing
the critic's ability of function approximation in our
test cases. The reason is that the policy function representation would require less memory than the representation of the state-action value function in manycases.
Controlling Step-Size of Backups: It isanalytically shown in Section 4.3 that the critic provides an appropriate reinforcement baseline to the actor. The adaptive baseline controls step-size of theactor's backups so that the step-size is taken to besmaller around the local maximum. This property
would contribute the better learning eÆciency andthe suppression of harmful drift of the policy that are
shown in the experiments.

7 Discussion

Figure 11: The average performance of three algorithms on 100 trials. The critic uses 3  3  3  3boxes. A trial means an attempt from initial state toa failure.

0

500

1000

1500

2000

Time steps until failure

To Overcome non-Markovian: There
are many ways to implement the critic's learning
scheme. [Peng et al. 94] and [Sutton 95] pointed outthat increasing  makes TD() less sensitive to nonMarkovian e ect. The actor's eligibility traces arealso useful in getting over non-Markovian problems[Kimura et al. 97]. Therefore, the combination ofTD() and the actor's eligibility trace will be robuster
in non-Markovian problems.
Combining with EÆicient DP-based
Methods: If the hidden state is relatively small
in the state space, the agent may perform good inwhich eÆcient DP-based algorithms are adopted forthe critic. The DP-based algorithms accelerate the actor's learning in completely observable states, and theactor's stochastic policy and its trace ( = ) would
make up for the non-Markovian e ects owing to thehidden state or function approximation.
8 Conclusions
This paper presented an analysis of actor/critic algorithms in which the actor updates its policy using theeligibility trace of the policy parameters. The results
show that when the discount rate of the value function
equals the discount factor of the actor's trace, the actor
improves its policy by using a gradient of actual return,not by using a gradient of the estimated return in thecritic. Then, the critic provides an adaptive reinforcement baseline to the actor controlling the step-size ofthe actor's backups. It enables the agent to learn afairly good policy under the condition that the approximated value function in the critic is hopelessly imperfect. The behavior is demonstrated through simulations showing that the trace contributes the learningeÆciency and the suppression of undesirable drifts ofthe policy. Analysis of the algorithm in non-Markovian
environments is a future work.
Acknowledgements

We would like to thank Andrew Barto, Jing Peng,
Je Schneider, Satinder Singh, Richard Sutton, andreviewers for many helpful comments and suggestions.

References[Baird 94] Baird, L. C.: Reinforcement Learning in Continuous Time: Advantage Updating, Proceedings ofIEEE International Conference on Neural Networks ,Vol. IV, pp. 2448-2453 (1994).
[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.

[Clouse et al. 92] Clouse, J. A. & Utogo , P. E.: A Teaching Method for Reinforcement Learning, Proc. of the
9th International Conference on Machine Learning ,pp. 93-101 (1992).
[Crites et al. 94] Crites, R. H. and Barto, A. G.: An Actor/Critic Algorithm that is Equivalent to Q-Learning,
Advances in Neural Information Processing Systems 7 ,pp. 401-408 (1994).
[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).
[Jaakkola 94] Jaakkola, T., Singh, S. P., & Jordan, M.
I.: Reinforcement Learning Algorithm for PartiallyObservable Markov Decision Problems, Advances in
Neural Information Processing Systems 7 , pp.345-352(1994).
[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., &Kobayashi, 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. 97] Kimura,
H., Miyazaki, K. and Kobayashi, S.: Reinforcement
Learning in POMDPs with Function Approximation,
Proceedings of the 14th International Conference on
Machine Learning , pp. 152{160 (1997).
[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).
[Littman 94] Littman, M. L.: Markov games as a framework for multi-agent reinforcement learning, Proc. of
11th International Conference on Machine Learning ,pp. 157-163 (1994).
[Pendrith et al. 96] Pendrith, M. D. & Ryan, M. R. K.:
Actual return reinforcement learning versus TemporalDi erences: Some theoretical and experimental results,
Proceedings of the 13th International Conference on
Machine Learning , pp. 373{381 (1996).
[Peng et al. 94] Peng, J. and Williams, R. J.: Incremental
Multi-Step Q-Learning, Proceedings of the 11th International Conference on Machine Learning , pp. 226-232(1994).
[Singh 94] Singh, S. P., Jaakkola, T., & Jordan, M. I.:
Learning Without State-Estimation in Partially Observable Markovian Decision Processes, Proceedings ofthe 11th International Conference on Machine Learning , pp. 284-292 (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 95] Sutton, R. S.: TD Models: Modeling the world
at a Mixture of Time Scales, Proceedings of the 12th International Conference on Machine Learning , pp. 531539 (1995).
[Sutton et al. 98] Sutton, R. S. & Barto, A.: Reinforcement Learning: An Introduction, A Bradford Book ,The MIT Press (1998).
[Watkins et.al 92] Watkins, C. J. C. H., & Dayan, P.:
Technical Note: Q-Learning, Machine Learning 8 , pp.
55-68 (1992).
[Williams et al. 90] Williams, R. J. & Baird, L. C.: A
Mathematical Analysis of Actor-Critic Architectures
for Learning Optimal Controls through Incremental
Dynamic Programming, Proceedings of the Sixth Yale
Workshop on Adaptive and Learning Systems , pp. 96101. Center for Systems Science, Dunham Laboratory,
Yale University, New Haven (1990).
[Williams 92] Williams, R. J.: Simple Statistical Gradient
Following Algorithms for Connectionist Reinforcement
Learning, Machine Learning 8 , pp. 229-256 (1992).