Natural Gradient Actor-Critic Algorithms using Random Rectangular Coarse
CodingHajime Kimura1
1

Department of Marine Engineering, Graduate School of Engineering, Kyushu University, 744 Motooka, Nishi-ku,
Fukuoka, 819-0395 Japan(http://sysplan.nams.kyushu-u.ac.jp/gen/index.html)

Abstract: Learning performance of natural gradient actor-critic algorithms is outstanding especially in high-dimensional
spaces than conventional actor-critic algorithms. However, representation issues of stochastic policies or value functions
are remaining because the actor-critic approaches need to design it carefully. The author has proposed random rectangularcoarse coding, that is very simple and suited for approximating Q-values in high-dimensional state-action space. This
paper shows a quantitative analysis of the random coarse coding comparing with regular-grid approaches, and presents a
new approach that combines the natural gradient actor-critic with the random rectangular coarse coding.
Keywords: Reinforcement learning, actor-critic, Q-learning, continuous state-action spaces, Function approximation

1. INTRODUCTION
Reinforcement learning (RL) is a promising paradigm
for robots to acquire control rules automatically in unknown environments. The most popular RL algorithm istabular Q-learning [7] because of its simplicity and welldeveloped theory. However, RL in robotics is to deal
with high-dimensional continuous state-action spaces,that immediately raises the curse of dimensionality, inwhich costs increase exponentially with the number ofthe state-action variables. It includes two issues in RL:
One is a generalization problem for Q-function overhigh-dimensional continuous spaces, and the other is asampling problem that is to select actions following agiven distribution over high-dimensional continuous action spaces. To deal with these issues, a novel techniqueof Q-learning is proposed that combines random rectangular coarse coding with an action selection scheme using Gibbs-sampling[4]. The random rectangular coarse
coding is very simple and quite suited both to approximate Q-functions in high-dimensional spaces and to execute Gibbs sampling. Gibbs sampling enables us to
execute action selection following Boltsmann distribution over high-dimensional action space. The Q-learningalgorithm can approximate optimum state-action valuefunction independent of the policy being followed, however, Boltzmann exploration strategy does not always improve the agent’s behavior efficiently.
In high-dimensimonal space, applying gradient methods to improve the agent’s policy is one promising solution. Natural-gradient actor-critic algorithms are elegant
policy gradient methods that are making use of first andsecond order partial derivatives, therefore its performanceis outstanding especially in high-dimensional spaces thanconventional actor-critic algorithms[2][5]. However, representation issues of stochastic policies or value functions
are remaining because the actor-critic approaches need todesign it carefully. This paper presents a new approachthat combines the natural gradient actor-critic with therandom rectangular coarse coding and Gibbs-sampling.

It discharges us from burdensome designing policy functions for each task.

2. PROBLEM FORMULATIONLet S denote state space, A be action space, R be a
set of real number. At each discrete time t, the agent
observes state st ∈ S, selects action at ∈ A, and thenreceives an instantaneous reward rt ∈ R resulting fromstate transition in the environment. In Markov decision
processes (MDPs), the reward and the next state may berandom, but their probability distributions are assumed todepend only on st and at . And the next state st+1 is chosen according to the transition probability T (st , a, st+1 ),and the reward rt is given randomly following the expectation r(st , a). The agent does not know T (st , a, st+1 )and r(st , a) ahead of time. The objective of RL is to construct a policy that maximizes the agent’s performance.
Consider cumulative discounted reward as a performancemeasure for infinite horizon tasks:∞Vt =γ k rt+k ,(1)
k=0

where the discount factor, 0 ≤ γ ≤ 1 specifies the importance of future rewards, and Vt is the value at time t. In
MDPs, the value can be defined as:

 ∞



π
t 
V (s) = Eγ rt  s0 = s, π ,
(2)

t=0

where E{·} denotes the expectation. The learning objective in MDPs is to find optimum policies that maximize
the value of each state s defined by Eq.(2). The state S
and the action A are both defined as multi-dimensional
continuous spaces in this paper.

3. RANDOM RECTANGULAR COARSECODING FOR HIGH-DIMENSIONALSPACES
Value function approximation can be significantly enhanced through the use of feature extraction, a process

T9
T5

T8

T7
T6
T3

T2

T1
T4

x1

Fig. 1 An example of the random rectangular coarse
coding using 9 features in two-dimensional input
space. The coarse feature T4 is sensitive to the component x1, and it is defined by the arrow width in the
sub-space x1. But the T4 ignores the component x2,
then the rectangle covers the other all sub-space x2.
The feature T5 is defined similarly.
that maps the input space x into some vector F (x) =(f1 (x), f2 (x), · · · , fn (x)), that is refered to feature vector associated with x. Feature vectors summarize what
are considered to be important characteristics of the input space. One of the most important cases of the valuefunction approximation is that in which the approximate
function is a linear function of the parameter vector W =(w1 , w2 , · · · , wn ) that has the same number of the components as the feature vector F (x). For example, thestate value is approximated by1V̂ (s) =wi fi (x),||F (x)|| i=1

rectangular T1, T2, · · · T9 are associated with components of the feature vector respectively. Notice that T1,
T2, T3, T6, T7, T8 and T9 are sensitive to the components both x1 and x2 , however, T4 is sensitive only to x1
and T5 is sensitive only to x2 .
For practical use, the feature fi (x) is defined by a rectangular area in a subspace of the input vector. The subspace is composed of arbitrary plural components of the
input vector, named sensitive elements. When the location of the input vector x is the inside of the rectangle,
the value of the feature is given by fi (x) = 1, otherwise fi (x) = 0. The selecting the sensitive elements or
the size of the rectangle are given randomly, but it hassound statistics, i.e., the expected activating probability
is 10 % when the input vector x is thrown by uniform
distribution. Aggregating a number of such features, it
is possible to give a set of feature vectors that is linearly
independent so that the state-action values can be adequately approximated over essential states (or actions) in
real-world tasks, without exponential growth of the memory requirements.
1

Rate of linearly independent vectors

x2

Random Rectangular
Coarse Coding
0.8

0.6

0.4

Regular Grid Coding

0.2

0
10

100

Number of features1nThis value function is said to be linear. When the setof the feature vectors {F (x)|x ∈ S} is linearly independent, then it is known that the predictions of the TDmethods converge in expected value to the ideal predictions [6].
To generate feature vectors that are linearly independent in high-dimensional spaces, random rectangularcoarse coding is introduced. To explain the concept of therandom rectangular coding, consider a randomized rectangular feature f (x) that is an element of the feature vector. When an input vector x is inside of the rectangle,
then the corresponding feature has the value 1, otherwise
0. In our approach, the feature rectangles are overlappedin many places. This kind of approach is known as coarse
coding [6]. In higher dimensional space, a feature f (x)selects a few arbitrary sensitive components of the input
vector x, and composes a hyper rectangle in the sensitive
subspace. That is, a feature f (x) ignores non-sensitive
components of the input vector x. For example in Fig.1,
the input vector x is two-dimensional (x1 , x2 ), and theRate of linearly independent vectors

(3)
0.8

Random Rectangular
Coarse Coding

0.6

0.4

Regular Grid Coding
0.2

0
10

100

1000

Number of features

Fig. 2 Linearly independence rates of the feature vectors
varying the number of the features (i.e., hyper rectangles) in multi-dimensional input spaces. The upper is
2-dimensional, the lower is 8-dimensional space.
The random rectangular coarse coding seems ad hoc,
but its performance is nothing to regular grid approaches’
in the condition of the same number of features. Figure 2
shows linearly independence rates of the feature vectors
varying the number of the features in 2 or 8 dimensional
1. Observe state st , choose action at with probability π(at |st , θ) that is a behavior policy, andperform it. Observe immediate reward rt andnext state st+1 .
2. Calculate the eligibility ∂ ln π(at |st ,θ ) with re-
1
fk (s, a) θk ,Θ(s, a, θ) =||F (s, a)||n∂θspect to policy parameters θ. Using these eligibilities and corresponding weight parameters,
find the estimated advantage function:TÂπ (st , at ) = (∇θ ln π(at |st , θ)) w
3. Calculate the TD error and update the estimated state value in the critic according toδt = rt + γ V̂ π (st+1 ) − V̂ π (st ) ,V̂ π (st ) ← V̂ π (st ) + αδt ,where α is a learning rate, δt is temporal difference (TD).
4. Update weight parameters w for the advantage
function using δt and the eligibility:w ← w + α δt − Âπ (st , at ) ∇θ ln π(at |st , θ)
5. Update policy parameters θ using the advantage function parameter w:θ ← θ + αp w ,6. Let t ← t + 1, and go to step 1.

Fig. 3 A natural gradient Actor-Critic algorithm

where F (s, a) is a feature vector F (s, a) =(f1 (s, a), f2 (s, a), · · · , fn (s, a)), that is the rectangularcoarse coding defined over the state-action space (s, a).
A policy parameter θk is associated with the feature
fk (s, a). From partially differentiating Eq.(4),⎧(Θ(st ,ai ,θ ))⎪ 1 −  exp
DN∂ ln π(ai |st , θ) ⎨exp(Θ(st ,aj ,θ ))
j=1
=
1
⎪
∂Θ(st , ak , θ)
⎩ − DN
exp(Θ(st ,aj ,θ ))
j=1

,k=i
otherwise.

Since the denominator in Eq.(4) grows too large in highdimensional action space, the eligibility in Fig.3 can beapproximated as :

4. LEARNING ALGORITHM
4.1 A Natural-Gradient Actor-Critic
Natural-Gradient Actor-Critic Algorithms (Fig.3) areelegant policy gradient methods that are making use of
first and second order partial derivatives, therefore its performance is outstanding especially in high-dimensional
spaces. The advantage function is given by substructing
the state value from the state-action value. Note that thebasis function for approximating the advantage function
is given by the eligibility of the policy parameters. In
this paper, the action-selection probability π(ai |s, θ) is
given by Boltzmann distribution that contains associatedΘ(s, ai , θ) so that
(4)

(5)

k=1

input space. The rate is higher, it grows the higher probability of distinction between two inputs nearby, where
one input is given by uniform distribution provided in[0, 1] for each axis, the other input is given by the normal
distribution of which the center is the former input andthe deviation is 0.1. Reinforcement learning in robotics
often encounters such a difficult situation that the agent
must distinguish near two points in the input space. The
reason of the outperformance of the random coarse coding is that the regular grid coding generates unnecessarily
restricted feature vectors so that only one of the component is 1 and the others are 0.

exp (Θ(s, ai , θ))π(ai |s, θ) = DN,
j=1 exp (Θ(s, aj , θ))

where N denotes the number of regular quantization foreach axis of the action space, and D is the number of thedimension of the action space. The function Θ(s, a, θ) is
given by∂ ln π(ai |st , θ)
fk (st , ai )∂θk||F (st , ai )||As a result, the algorithm becomes very simple form.
The feature vector over state-action space F (s, a) is
composed of state features and action features as below. State features fj (s) where j ∈ {1, 2, . . . Ts }that are defined in state space and action-features gk (a)where k ∈ {1, 2, . . . Ta } that are defined in action
space are introduced. It is desirable that L1 norm of
the feature vectors are constant in linear function approximation. Therefore, state-feature vectors F (s) thathas 2Ts components F (s) = (F1 (s), F2 (s), · · · F2Ts (s))
and action-feature vectors G(a) that has 2Ta components G(a) = (G1 (a), G2 (a), · · · G2Ta (a)) are given by
the state-features fj (s) and action-features gk (a) respectively according toFj (s) =fj (s)
1 − f(j−Ts ) (s), where j ≤ Ts
otherwise.

(6)

Gk (a) =gk (a)
1 − g(k−Ta ) (a), where k ≤ Taotherwise.

(7)

In this paper, the state-action feature F (s, a) =(f1 (s, a), · · · , fn (s, a)) is given by the product of thestate feature Fj (s) and the action feature Gk (a). Then,the function Θ(s, a, θ) in Eq.5 is given by
2T 2Ta1 s 
Θ(s, a, θ) =Fj (s) Gk (a) θjk
Ts Ta j=1

, (8)

k=1

where θjk are policy parameters of which the number is
2Ts × 2Ta , and Ts1Ta is a normalization factor so that the
L1 norm of the feature vectors composed of Fj (s) andGk (a) keep 1 constant. The state value V̂ π (s) in Fig.3 isrepresented using only the state feature Fj (s) as Eq.3.

4.2 Action Selection Scheme in High-Dimensional Action SpaceAs shown in Eq.(4), the naive action-selection scheme
needs to calculate all discrete action values, that gives
rise to exponentially increase with the number of the action dimension. However, an action-selection method forhigh-dimensional action space using Gibbs sampling is
a powerful technique for generating samples from multidimensional complex distribution [4].
select

P(a)

a2

a1

Fig. 4 An action-selection with a regular grid approachin two-dimensional action space. The probability
function of the action selection P (a) is represented
by quantizing the action space a1 − a2 into a finite
number of cells.
In this paper, regular grid partitioning is used that divide D equivalent parts into each dimension of the actionspace. That is, when the action-space is N -dimensional,
the partitioning yields DN cells. Each cell is considered
to be a discrete action ai where i = {1, · · · , DN }. For
each decision epoch, an action ai is selected following
an associated probability function P (ai ). Fig.4 shows
the regular grid partitions and its distribution function in
two-dimensional action-space.
In the Gibbs sampler, the components of the multidimensional random variable are resampled in turn, conditional on the others, using some fixed ordering. Fig.5 illustrates the Gibbs sampling for a case with two variables(a1, a2). The distribution for action selection probability
is equal to Fig.4. In the initial step of Gibbs sampling,
an arbitrary sample (a1, a2) is selected in advance. In
each iteration, the top right (1) in Fig.5 represents selecting action a1 following the conditional probability given
a2, and the bottom left (2) in Fig.5 represents selecting
action a2 following the conditional probability given a1
at the top right (1) in Fig.5, then the iteration is completed. The bottom right (3) in Fig.5 represents the next
iteration, selecting action a1 again, following the conditional probability given a2 at the bottom left (2) in Fig.5.
After a sufficient number of iterations, we can take a1
and a2 as the sample from the distribution. The resulting
sample can be considered to be independent of the sample in the initial step. It is a difficult problem to predictthe lower bounds of the number of the iteration, therefore we should choose it experimentally. Gibbs samplingis particularly well-adapted when the joint distribution is
not known explicitly, but the conditional distribution ofeach variable is known. In high-dimensions, getting joint
distribution costs too expensive computational resources.
For example, if a regular grid partition divides each dimension of the 8-dimensional action space into 10 parts,

then finding the joint distribution for the flat action selection costs memory capacity and computation over 108
variables, whereas the Gibbs sampling, that uses conditional distribution, costs 10 + 8 variables and the number of iteration can be reduced to 102 or 103 . That is,
Gibbs sampling cuts down the computational cost over
1/10000.
Throughout this paper, probability of the action selection is given by Eq.(4), but we use particular notation for Gibbs sampling. Suppose that a regular grid
partition divides D parts into each dimension of the
N -dimensional action space, same as the case of theflat action selection. We give a N -dimensional actiona as a = (a1 , a2 , . . . aN ), where each component an(n ∈ {1, 2, · · · N }) is an ∈ and (d ∈ {1, 2, · · · D}). A
value of Θ(s, a, θ) in Eq.(4) is given by Θ(s, a, θ) =Θ(a1 , a2 , . . . aN |s). This value is equal to the flat action
selection method’s. Sampled components of the action
vector at the iteration t in the Gibbs sampling is given by
a1 (t), a2 (t), . . . aN (t). Then, the Gibbs sampler updates
components of the action vector at the iteration t + 1 following the conditional distribution asa1 (t + 1)
a2 (t + 1)
aN (t + 1)

∼ P (a1 |a2 (t), a3 (t), . . . aN (t)) ,∼ P (a2 |a1 (t), a3 (t), . . . aN (t)) ,..
.
∼ P (aN |a1 (t), a2 (t), . . . aN −1 (t)) ,where the conditional probability P (ani |a1 , a2 , . . . aN ) is
given by the following Boltzmann distribution:
P (ani |a1 , a2 , . . . aN )
exp Θ(a1 , a2 , . . . ani , . . . aN |s)= D . (9)1 2nN
d=1 exp Θ(ad , ad , . . . ad , . . . ad |s)
It is simply repetition of similar processes to the flat action selection’s shown in Eq.(4), however, getting off with
one dimensional action selection. The obvious advantage
is that the Gibbs sampler can get equivalent1 samples following Eq.(4) without checking out all Θ(s, ai , θ) overthe high-dimensional action-space. Note that since thecalculation of the conditional probability in each iterationis along an arbitrary axis of the action space, the computational cost can be reduced in the proposed rectangularcoarse coding.

5. EXPERIMENTS
This section evaluates the proposed method empirically comparing with Q-learning.
5.1 Crawling Robots
Fig.6 shows a several-legged crawling robot in which
both the state and the action are high-dimensional. In
the robot, each leg has two joints, and it is arranged inparallel. Therefore the dimension of state-action spaces
can be easily varied according to adding or removing the
1 It is supposed that the number of the iteration is enough. Since predicting the lower bounds of this number is a difficult problem, the samples
would be likely to approximate Eq.(4).

P(a)select

P(a)

a2
a2
a1
a1
(1)
selectselect

P(a)

P(a)

a2

a2

a1

a1

(2)

(3)

Fig. 5 An example of the Gibbs sampling scheme with the regular grid approach in two-dimensional action space.
The top left shows a joint distribution of the action selection probability. The top right (1) represents selecting
action a1 following the conditional probability given a2. The bottom left (2) represents selecting action a2 following
the conditional probability given a1 at the top right (1). The bottom right (3) represents selecting action a1 again,
following the conditional probability given a2 at the bottom left (2).
Table 1 Relation between the number of legs anddimensions of state or action space
Legs
1
2
3
4

Fig. 6 A simulator of a several-legged crawling robot.

legs. Note that although the state and action space grows
largely, the complexity of the problem is not so changed
because the number of solutions also increases. The main
issue of this simulation is to find better policies in highdimensional action space.
In this simulation, the objective of learning is to findcontrol rules to move forward, but the agent does notknow the dynamics ahead of time. The controller improves its behavior through a process of trial and error.
At each time step, the agent observes current state, andselect action, and immediate reward is given as a result of
the action and state transition, and the time step proceeds
to the next step. The reward signal reflects the speed of
the body at each step. These robots have bounded continuous and discrete state variables. Continuous state variables are angular-position of the joints, and discrete statevariables represent touch sensors for each leg. The learning agent observes these state variables. The action thatthe agent selects is an objective angular-position of theState dimension
3
6
9
12

Action dimension
24
6
8

joint-motors. That is, the number of dimension of the action space is the same as the continuous state’s. Whenthe agent selects action, the robot moves the motors towards the commanded positions. When the joint-angles
move to the commanded position, or changing the variables of touch sensors in the way of moving, then the
movement stops and reward is given as the result of thetransition, and the time step proceeds to the next step.
When the case of sensor variable changing in the wayof moving joint-motors, the angular-position would notcorrespond to the selected objective position. The bodymoves forward or backward when some legs are touching
the ground and moving it. The learning controller shouldfind good assignment of crawling control rules for eachleg. For simplicity, it is assumed that there is no noisein the state observation. Note that there are many control
rules that can move the body ahead.
Table 1 shows the relation between the number of legsand dimensions of state or action spaces. When the robot
has only one leg, then the state space is 3-dimensional
where one is the touch sensor of the leg top, the others are angular positions of the joints, and the action is
2-dimensional where the destination of the angular po-

Table 2 Relation between the number of legs and thenumber of discrete states or actions by regular partition

12

Legs
1
2
3
4

Number of states
2 × 1002
22 × 1004
23 × 1006
24 × 108

Number of actions
1002
1004
1006
108

Averaged Reward (1000 steps)

10

8

QL
NGAC 0.001
NGAC 0.0005
NGAC 0.00025

6

4

2

The discount factor γ = 0.9, the temperature T keeps
0.4 constant, and the learning rate α = 0.2, of f set(s)and width(s) in Eq.(10) are given by the average anddeviation of Q-values in state s over 20 actions that aresampled from uniform distribution. The number of iteration in the Gibbs sampling is the same as the proposed
method’s. The features of the state and action are also thesame.
Fig.7, 8, 9 and 10 compare the performance of thenatural gradient actor-critic (NGAC) against Q-learning
averaging over 10 runs. When the state and action
spaces are small as Fig.7, the Q-learning outperforms
than the proposed method. However, even though thelearning parameters are all the same, the performanceof the proposed NGAC is improved in high-dimensional
state-action spaces. The learning parameter for the actor should be small for the learning stability in all cases.
The deviaton of the performance of the NGAC is larger
than the Q-learning’s. The performance of the Q-learning
is not so different between small and large state-action
spaces. In both algorithms, the learned behavior seems

0
0

5000

10000

15000

20000

25000

30000

35000

40000

Learning Steps

Fig. 7 Learning results averaged over 10 runs in the
crawling robot where state is 3-dimensional and action is 2-dimensional (one leg). The vertical axis
gives the averaged reward over 1000 decision steps.
The errorbars are standard deviation.
12

Averaged Reward (1000 steps)

10

QL
NGAC 0.001
NGAC 0.0005
NGAC 0.00025

8

6

4

2

0
0

5000

10000

15000

20000

25000

30000

35000

40000

Learning Steps

Fig. 8 Learning results averaged over 10 runs in the
crawling robot where state is 6-dimensional and action is 4-dimensional (two legs). The vertical axis
gives the averaged reward over 1000 decision steps.
The errorbars are standard deviation.
12

10

Averaged Reward (1000 steps)

sitions of the 2-joints. A regular grid partition divides
each dimension of the state or action space into 10 or
100 parts. Table 2 shows the number of discrete statesor actions by regular grid partitioning. The edges of therandom hyper-rectangles for the features are generated
along the dividing lines of the regular grid. In this experiment, all the agents use 200 randomized rectangularstate features where its sensitive elements and the sizeof the rectangle are randomly given so that the expected
activating probability is 10 % under the uniform distribution. The features for the action space are also generated 200 randomized hyper-rectangles in the same way
as the state’s. The number of iteration in the Gibbs sampling is (numOfActionDimension) × 5, the discount factor γ = 0.9, and the learning rate for the critic α = 0.2,
and the learning parameter for the actor αp = 0.001,
0.0005 or 0.00025. Before learning, all the state valuesV̂ (s) are initialized to 20.
The proposed method is compared with a Q-learning
approach using the same rectangular coarse coding andGibbs sampling [4][5]. In the Q-learning, the actionselection probability P (ai ) is given by Boltzmann distribution that contains associated Q(s, ai ) so thati )−of f set(s)exp Q(s,a
T ×width(s).
P (ai ) =  N(10)Q(s,aj )−of f set(s)Dj=1 exp
T ×width(s)QL
NGAC 0.001
NGAC 0.0005
NGAC 0.00025

8

6

4

2

0
0

5000

10000

15000

20000

25000

30000

35000

40000

Learning Steps

Fig. 9 Learning results averaged over 10 runs in the
crawling robot where state is 9-dimensional and action is 6-dimensional (3 legs). The vertical axis gives
the averaged reward over 1000 decision steps. The
errorbars are standard deviation.

12

Averaged Reward (1000 steps)

10

QL
NGAC 0.001
NGAC 0.0005
NGAC 0.0005

GOAL

8

6

4

2

0
0

5000

10000

15000

20000

25000

30000

35000

40000

Learning Steps

Fig. 10 Learning results averaged over 10 runs in the
crawling robot where state is 12-dimensional and action is 8-dimensional (4 legs). The vertical axis gives
the averaged reward over 1000 decision steps. The
errorbars are standard deviation.
similar. In the case of one-leg, the robot crawls intermittently only when the leg scratches the ground . In thecase that the number of legs is 2, 3 or 4, the robots move
two-legs alternately so that the body always moves to thefront without stopping.
5.2 Reaching Tasks using Multi-Link RedundantArms

GOAL

Fig. 12 A learned example behavior of a reaching taskusing redundant-arm that have eight-joints. The conditions that the joints are shown by black circles are
the positions at which the learner is making decisions.
rotating, 3) extending the arm, and thereafter reaching thegoal. Also many best solutions exist in these tasks. In the
4-link-arm, the agents divide each dimension of the state
and action spaces into 100 parts by regular grids, and in
the 8-link-arm the agents divide each dimension into 10
parts. All the agents use 200 randomized rectangular statefeatures and 200 randomized rectangular action features
same as the crawling robots’.
30

Averaged Reward (1000 steps)

25

20

QL
NGAC 0.001
NGAC 0.0005
NGAC 0.00025

15

10

5

0
0

5000

10000

15000

20000

25000

30000

35000

40000

Fig. 11 A learned example behavior of a reaching taskusing redundant-arm that have four-joints. The conditions that the joints are shown by black circles are
the positions at which the learner is making decisions.

Fig. 13 Learning results averaged over 10 trials in the
4-joints redundant-arm reaching task. The verticalaxis gives the averaged reward over making 1000 decision steps.

The second example is multi-joint arm reaching tasks[4][5]. Fig.11 shows a sample behavior of the task witha redundant arm that is composed of four links and four
joints in series where the state space and action space areboth 4-dimensional. Fig.12 shows a sample behavior in
8-joints where the state space and action space are both8-dimensional. In both tasks, the best solutions are composed of only three decision steps: 1) curling the arm, 2)

Fig.13 and 14 compare the performance of the proposed NGAC against Q-learning averaging over 10 runs.
When the state and action spaces are small as Fig.13,
NGAC is comparable to Q-learning. However, eventhough the learning parameters are the same, the NGAC
is fairly good in high-dimensional state-action space as
Fig.14. The deviaton of the performance of the NGAC islarger than the Q-learning’s in all the cases.

Learning Steps

7. CONCLUSION

30

Averaged Reward (1000 steps)

25

20

QL
NGAC 0.001
NGAC 0.0005
NGAC 0.00025

15

10

5

0
0

5000

10000

15000

20000

25000

30000

35000

40000

Learning Steps

Fig. 14 Learning results averaged over 10 trials in the
8-joints redundant-arm reaching task. The verticalaxis gives the averaged reward over making 1000 decision steps.

6. DISCUSSION
6.1 Relation between increase of action dimension andthe learning performance
When the dimension of the state-action space is getting large, the performance of the proposed NGAC showsa marked rising tendency whereas the performance of the
Q-learning is not so different or becoming worse. This result supports the efficiency of the natural-gradient method
in high-dimensional space.
6.2 Setting of learning parameter for policy update
In actor-critic algorithms, since the policy updatingmust be done sufficiently slowly than the estimating thestate-action value, we need to select adequate value of thelearning parameter for the actor αp carefully. For this reason, αp is a critical parameter under the current circumstances. The appropriate range of the αp would depend
on a maxmum absolute value of the advantage function
and representation of the policy function. Finding that
range is a future work.
6.3 Finding an appropriate number of the iteration in
Gibbs sampling
In the experiments, the numbers of the iteration are
given ad hoc. In general, it is difficult to predict the lower
bounds of the number of the iteration in Gibbs sampling.
It is noteworthy that the Gibbs sampling affects only thetime for action selection, it does not affect the learning
steps. Therefore, the number of the iteration should begiven as long as possible. To get good samples with lesstime, overrelaxation techniques or simulated annealing[3] are possible.
6.4 Applying eligibility traces to the NGAC
Eligibility traces enhance the robustness of the learning algorithms against not only the non-Markovian effects but incomplete state-action value approximation [5].
Combining it with the proposed approach is very easy.

This paper proposed a novel actor-critic approachcombining random rectangular coarse coding with Gibbssampling action selection to cope with reinforcement
learning in high-dimensional domains. The proposed
coding method is very simple and quite suited both torepresent action-selection probability function in highdimensional spaces, and to execute Gibbs sampling foraction selection. The rectangular features are given randomly, however, it works well in several robot problems. The scheme using Gibbs-sampling enables tohandle high-dimensional action space in RL problems
without burdensome tuning of several learning parameters for varying dimensions. The natural-gradient based
actor-critic method is quite efficient in high-dimensional
spaces.

REFERENCES[1] Bertsekas, D.P. & Tsitsiklis, J.N.: Neuro-Dynamic
Programming, Athena Scientific (1996).
[2] Bhatnagar, S., Sutton, R., Ghavamzadeh, M. & Lee,
M.: Incremental Natural Actor-Critic Algorithms,
the 21st Annual Conference on Neural Information
Processing Systems (NIPS), 2007.
[3] Jordan, M. I.: Learning in Graphical Models, The
MIT Press, (1999).
[4] Kimura, H.: Reinforcement Learning in MultiDimensional State-Action Space Using Random
Rectangular Coarse Coding and Gibbs Sampling,
Proc. of the IEEE/RSJ International Conference onIntelligent Robots and Systems (IROS07), pp.88–
95, 2007.
[5] Kimura, H.: Natural Gradient Actor-Critic using
Eligibility Traces, Conference Proc. of the 19th
SICE Symposium on Decentralized Autonomous
Systems, pp.67–72 (2007 in Japanese).
[6] Sutton, R.S. & Barto, A.: Reinforcement learning:
An introduction, A Bradford Book, The MIT Press(1998).
[7] Watkins, C.J.C.H. & Dayan, P.: Technical Note:
Q-Learning, Machine Learning, Vol.8, pp.279–292(1992).