Reinforcement Learning in Multi-dimensional State-Action Space using
Random Rectangular Coarse Coding and Gibbs Sampling
Hajime Kimura
Abstract— This paper presents a coarse coding technique andan action selection scheme for reinforcement learning (RL) in
multi-dimensional and continuous state-action spaces following
conventional and sound RL manners. RL in high-dimensional
continuous domains includes two issues: One is a generalization
problem for value-function approximation, and the other is asampling problem for action selection over multi-dimensional
continuous action spaces. The proposed method combines
random rectangular coarse coding with an action selection
scheme using Gibbs-sampling. 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 algorithm is demonstrated through Rod in mazeproblem and a redundant-arm reaching task comparing withconventional regular grid approaches.

I. INTRODUCTION
Reinforcement learning (RL) is a promising paradigm for
robots to acquire control rules automatically in unknown
environments. The most popular RL algorithm is tabular Qlearning [13] because of its simplicity and well-developed
theory. However, RL in real world applications is to deal
with high-dimensional continuous state-action spaces, that
immediately raises the curse of dimensionality [6], in whichcosts increase exponentially with the number of the stateaction variables. It includes two issues in RL: One is a
generalization problem for Q-function over high-dimensional
continuous spaces, and the other is a sampling problem thatis to select actions following a given distribution over highdimensional continuous action spaces.
To deal with continuous state space, a number of RL algorithms combining with function approximation techniques
have been invented: Q-net [5] is an extended Q-learningalgorithm by means of using neural networks to generalize
the Q-function, SARSA with CMAC [10] is a better method
because it is based on linear function approximation, that has
good theoretical convergence properties in RL [1]. [9] and[12] proposed RL algorithms with instance-based function
approximation, and [7] extended it to consider continuous
action spaces. However, these works are not aimed at handling high-dimensional spaces. [11] introduced hashing tocope with high-dimensional spaces. Hashing is a consistent
pseudo-random collapsing of a large tiling into a muchsmaller set of tiles. This approach is quite favorable, however,
the action sampling problem remains.
Dept. of Marine Engineering, Graduate School of Engineering,
Kyushu University, 744 Motooka, Nishi-ku, Fukuoka, 819-0395 JAPANkimura@nams.kyushu-u.ac.jp

In the Q-learning, the state-action value function directly
approximates the optimum state-action value function independent of the policy being followed. During learning,
there is a difficult exploration vs exploitation trade-off tobe made [4]. One standard practice is known as Boltzmann
exploration, however, its naive computational cost increases
exponentially with the number of action variables, independently of the generalization costs. One solution to overcome
this problem is to use Gibbs sampling, that is a Markov
chain Monte Carlo (MCMC) method for drawing samples inhigh-dimensional spaces [3][8].
This paper presents a new approach combining random
rectangular coarse coding with an action selection scheme
using Gibbs-sampling. The proposed coding method is quite
suited both to approximate Q-functions in high-dimensional
spaces, and to execute Gibbs sampling.
II. PROBLEM FORMULATIONLet S denote state space, A be action space, R be a setof real number. At each discrete time t, the agent observesstate st ∈ S, selects action at ∈ A, and then receives an
instantaneous reward rt ∈ R resulting from state transitionin the environment. In Markov decision processes (MDPs),
the reward and the next state may be random, but theirprobability distributions are assumed to depend only on st
and at . And the next state st+1 is chosen according to thetransition probability T (st , a, st+1 ), and the reward rt isgiven 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 theagent’s performance. Consider cumulative discounted reward
as a performance measure 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 
γ rt  s0 = s, π ,(2)V (s) = E
t=0where E{·} denotes the expectation. The learning objective
in MDPs is to find optimum policies that maximize the valueof each state s defined by (2). The state S and the action A
are both defined as multi-dimensional continuous spaces inthis paper.

III. R ANDOM R ECTANGULAR C OARSE C ODING FOR
H IGH - DIMENSIONAL S PACES

a2

T9
T5

T8

T7
T6
T3

T2

T1
T4

a1

Fig. 1. An example of the random rectangular coarse coding using 9
features in two-dimensional action space. The coarse feature T4 is sensitive
to the component a1, and it is defined by the arrow width in the sub-space
a1. But the T4 ignores the component a2, then the rectangle covers the otherall sub-space a2. The feature T5 is defined similarly.

Value function approximation can be significantly enhanced through the use of feature extraction, a processthat 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. Oneof the most important cases of the value function approximation is that in which the approximate function is a linear
function of the parameter vector W = (w1 , w2 , · · · , wn ) thathas the same number of the components as the feature vector
F (x). For example, the state value is approximated by
V (x) =n
fi (x) wi

.

(3)

i=1

This value function is said to be linear. When the set of thefeature vectors {F (x)|x ∈ S} is linearly independent, thenit is known that the predictions of the TD-methods converge
in expected value to the ideal predictions [11].
To generate feature vectors that are linearly independent
in high-dimensional spaces, random rectangular coarse coding is described below. This idea is directly inspired from
”CMAC with hashing” [11]. And it is also derived fromconsideration of the Parti-game algorithm [6] in multi-joint
arm problems, in which the complexity of the ultimate
task remains roughly constant as the number of degrees of
freedom increases. These deliberation lead that a fine stateaction representation may be practicable by regarding somesubsets of the state (or action) variables in high-dimensional
spaces.
To explain the concept of the random rectangular coding,consider a randomized rectangular feature f (x) that is anelement of the feature vector. When an input vector x is

inside of the rectangle, then the corresponding feature has thevalue 1, otherwise 0. In our approach, the feature rectangles
are overlapped in many places. This kind of approach is
known as coarse coding [11]. In higher dimensional space,a feature f (x) selects a few arbitrary sensitive componentsof the input vector x, and composes a hyper rectangle inthe sensitive subspace. That is, a feature f (x) ignores nonsensitive components of the input vector x. For example inFig.1, the input vector x is two-dimensional (a1 , a2 ), and therectangular T1, T2, · · · T9 are associated with componentsof the feature vector respectively. Notice that T1, T2, T3,
T6, T7, T8 and T9 are sensitive to the components botha1 and a2 , however, T4 is sensitive only to a1 and T5
is sensitive only to a2 . In this paper, the set of sensitive
components, the ranges and the size of the rectangles are
given randomly, but it is also possible to consider someother sophisticated methods. Aggregating a number of suchfeatures, it is possible to give a set of feature vectors thatis linearly independent so that the state-action values can beadequately approximated over essential states (or actions) in
real-world tasks, without exponential growth of the memory
requirements.
In this paper, 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 (1 is the best1 ) in linear function
approximation. Therefore, state-feature vectors F (s) that has
2Ts components F (s) = (F1 (s), F2 (s), · · · F2Ts (s)) andaction-feature vectors G(a) that has 2Ta components G(a) =(G1 (a), G2 (a), · · · G2Ta (a)) are given by the state-featuresfj (s) and action-features gk (a) respectively according tofj (s), where j ≤ Ts
(4)
Fj (s) =1 − f(j−Ts ) (s) otherwise.

gk (a), where k ≤ Ta
(5)
Gk (a) =1 − g(k−Ta ) (a) otherwise.
Then the approximate value function of state-action pairs(i.e., Q-function) is given by
2T 2Ta1 s 
Fj (s) Gk (a) wjk
Q(s, a) =Ts Ta j=1

,

(6)

k=1

where wjk are 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) and Gk (a) keep 1
constant. The parameters wjk are updated by a gradientdescent method. The specification are shown later. In thispaper, the agent selects action following Boltzmann distribution using Q-function. The proposed generalization method
has the following advantages:• The rectangular feature can directly represent mutual
dependence between its sensitive components. It isuseful to incorporate domain knowledge about the task
into the agent.
1 The reason is to keep consistency of Q-learning’s learning rate parameteravoiding influence of magnitude of the norm.

The computation both to generate feature vectors andto update parameters are quite simple and easy.
• The computation for action selection in highdimensional action-space can be effective particularly
with using Gibbs sampling as shown in the next section.
Although this approximation itself is promising, naive execution of the Boltzmann exploration over high-dimensional
continuous action-space gives rise to exponential growth ofthe computational cost.
•

IV. S AMPLING AND L EARNING IN H IGH - DIMENSIONALS PACE
A. Conventional Approach: Flat Action Selection
select

P(a)

a2

a1
Fig. 2. An action-selection with a regular grid approach in two-dimensional
action space. The probability function of the action selection P (a) isrepresented by quantizing the action space a1 − a2 into a finite numberof cells.

During learning, Boltzmann exploration is a standard strategy to cope with exploration vs exploitation trade-off in the
Q-learning. A common approach to treat multi-dimensional
continuous action is to quantize the action space into a finite
number of cells and aggregate all actions within each cell.
Then the action is treated discretely. Note that each cellneedn’t have own variables to represent action value, because
the value is provided by the coarse coding. In this paper,
regular grid partitioning is used that divide D equivalent parts
into each dimension of the action-space. That is, when theaction-space is N -dimensional, the partitioning yields DN
cells. Each cell is considered to be a discrete action ai wherei = {1, · · · , DN }. For each decision epoch, an action ai isselected following an associated probability function P (ai ).
Fig.2 shows the regular grid partitions and its distributionfunction in two-dimensional action-space. In this paper, theaction-selection 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 ) =(7)
Q(s,aj )−of f set(s)DN
j=1 exp
T ×width(s)where T is a temperature parameter that controls exploration
behavior. In many cases, of f set(s) = 0 and width(s) = 1,
but this paper recommends2 of f set(s) to be average of Qvalue in state s and width(s) to be deviation of Q-value
in state s. As shown in (7), the naive flat action-selection
scheme needs to calculate all discrete action values, that
2 The reason is to keep consistensy of parameter T avoiding magnitude
influence of Q-value.

gives rise to exponentially increase with the number of thedimension. For this reason, Q-learning nor SARSA havelittle opportunity to apply real-world tasks that have highdimensional continuous action-space.
B. Selecting Action by Gibbs SamplingThis section describes an action-selection method for highdimensional action space using Gibbs sampling, that is
a powerful technique for generating samples from multidimensional complex distribution. In the Gibbs sampler, thecomponents of the multidimensional random variable areresampled in turn, conditional on the others, using some fixedordering. Fig.3 illustrates the Gibbs sampling for a case withtwo variables (a1, a2). The distribution for action selection
probability is equal to Fig.2. 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.3 represents selecting
action a1 following the conditional probability given a2, andthe bottom left (2) in Fig.3 represents selecting action a2
following the conditional probability given a1 at the top right(1) in Fig.3, then the iteration is completed. The bottom right(3) in Fig.3 represents the next iteration, selecting action
a1 again, following the conditional probability given a2
at the bottom left (2) in Fig.3. After a sufficient numberof iterations, we can take a1 and a2 as the sample fromthe distribution. The resulting sample can be considered to
be independent of the sample in the initial step. It is adifficult problem to predict the lower bounds of the numberof the iteration, therefore we should choose it experimentally.
Gibbs sampling is particularly well-adapted when the joint
distribution is not known explicitly, but the conditional
distribution of each variable is known. In high-dimensions,
getting joint distribution costs too expensive computational
resources. For example, if a regular grid partition divides
10 parts into each dimension of the 8-dimensional action
space, 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 (7), but we use particular notation for Gibbs
sampling. Suppose that a regular grid partition divides Dparts into each dimension of the N -dimensional action space,same as the case of the flat action selection. We give a
N -dimensional action a as a = (a1 , a2 , . . . aN ), where
each component an (n ∈ {1, 2, · · · N }) is an ∈ and (d ∈{1, 2, · · · D}). A value of state s and action a is given by
Q(s, a) = Q(a1 , a2 , . . . aN |s). This value is also equal to
the flat action selection method’s. Sampled components of
the action vector at the iteration t in the Gibbs samplingis 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)

∼ P (a1 |a2 (t), a3 (t), . . . aN (t)) ,P(a)select

P(a)

a2
a2
a1
a1
(1)
selectselect

P(a)

P(a)

a2

a2

a1

a1

(2)

(3)

Fig. 3. An example of the Gibbs sampling scheme with the regular grid approach in two-dimensional action space. The top left shows a joint distributionof 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).

a2 (t + 1)

∼ P (a2 |a1 (t), a3 (t), . . . aN (t)) ,..
.

aN (t + 1)

∼ 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 )
 1 2 n N
Q(a ,a ,...ai ,...a |s)−of f set(s)exp
T ×width(s) . (8)
 1 2 n N=
Q(ad ,ad ,...ad ,...ad |s)−of f set(s)
D
exp
d=1
T ×width(s)It is simply repetition of similar processes to the flat action
selection’s shown in (7), however, getting off with one
dimensional action selection. The obvious advantage is that
the Gibbs sampler can get equivalent3 samples following(7) without checking out all the Q-values over the highdimensional action-space. Note that since the calculationof the conditional probability in each iteration is along an
arbitrary axis of the action space, the computational cost canbe reduced in the proposed rectangular coarse coding.
C. Learning Algorithms
This section describes Q-learning and SARSA algorithms
combined with random rectangular coarse-coding and theaction selection using Gibbs sampling. As shown in thesection III, state-feature vectors F (s) that has 2Ts components F (s) = (F1 (s), F2 (s), · · · F2Ts (s)) and actionfeature vectors G(a) that has 2Ta components G(a) =(G1 (a), G2 (a), · · · G2Ta (a)) are given by the state-features
3 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 (7).

fj (s) where j ∈ {1, 2, . . . Ts } and action-features gk (a)where k ∈ {1, 2, . . . Ta } respectively according to (4) and(5). Then the approximate value function is given by (6).
The agent observes state s, and selects action ai following
Boltzmann distribution given by (7). However, actual processof choosing action would be executed following Gibbs
sampling given by (8). After that, the agent observes thenext state s and instantaneous reward r resulting from thestate transition. The standard Q-learning algorithm updates
values by
TD error=Q(s, ai ) ←r + γ max Q(s , a) − Q(s, ai ) ,(9)Q(s, ai ) + α TD error ,

(10)

a

where γ is a discount factor, α is a learning rate parameter,where 0 ≤ α ≤ 1. In my approach, the Q-function isrepresented by (6), therefore the updating of (10) is executedby modifying the parameters wjk using a gradient-descentmethod as
Fj (s) Gk (ai )α TD error .
(11)
wjk ← wjk +Ts Ta
Unfortunately, it is difficult to operate maxa Q(s , a) strictly
in high-dimensions, we are to substitute approximatedmaxa Q(s , a) found in the process of the Gibbs sampling.
For the other hand, strict SARSA algorithm can be executed
easily by replacing maxa Q(s , a) with Q(s , a ), where a
is an action selected in state s .
V. E XPERIMENTS
This section evaluates the proposed method empiricallyin two learning tasks. Fig.4 shows a slightly modified rodin-maze task in which both the state and the action are
three-dimensional. The original rod-in-maze task is proposed

30

GOAL

Averaged Reward (1000 steps)

25

20
Random rectangularcoarse coding 200x200
15Regular grid coding(6x6x6)x(6x6x6)

10

5

0
0

20000

40000

60000

80000

100000

Learning Steps

Fig. 5. Learning results averaged over 10 runs in the rod in maze task.
The vertical axis gives the averaged reward over 1000 decision steps. The
errorbars are standard deviation.

Fig. 4. An example of learned behavior in the rod-in-maze task. The black
circles of the bottom of the rod represent the positions at which the learner
is making decisions.

by [6]. The state s = (x, y, θ) is three-dimensional. (x, y)denotes the position of the center of the rod and must lie
in the area 0 ≤ x ≤ 1 and 0 ≤ y ≤ 1. The θ denotes theangle of the rod from the horizontal, and is constrained tolie in the range 0 ≤ θ ≤ π. The action a = (xd , yd , θd )is also three-dimensional, representing a destination of therod in the state. When the destination position is given
as the agent’s action, the simulation of the movement is
executed by summing small displacements (δx, δy, δθ) in
the state . The small displacements are given so that eachstate variable would reach the destination as fast as possible,1δx2 + δy 2 ≤ 100
andbut it is constrained such thatππ
− 20 ≤ δθ ≤ 20 . If the rod collides with obstacles, or reaches
the goal region, or reaches the destination, then the agent
makes the next decision. The goal region is 0.8 ≤ x ≤ 0.9
and 0.6 ≤ y ≤ 0.7. The rod has length 0.4. In the field, there
exist four polygonal obstacles; Obstacle 1 is a triangle andits apexes are (1.0, 0.1), (0.5, 0.4) and (1.0, 0.4). Obstacle 2
is a triangle and its apexes are (0.4, 0.0), (0.5, 0.25) and(0.8, 0.0). Obstacle 3 is a quadrangle and its apexes are(0.0, 0.5), (0.25, 0.35), (0.25, 0.3) and (0.0, 0.1). Obstacle
4 is a quadrangle and its apexes are (0.0, 1.0), (0.3, 0.8),(0.35, 0.55) and (0.0, 0.9). When the rod reaches the goal
region, the agent receives reward 100 and the rod is removed
to the initial state. Otherwise, the reward is zero.
In this experiment, all the agents partition the state space
into 1003 = 106 grids, dividing each dimension into ahundred regular partitions. The action space is also partitioned into 1003 = 106 grids in the same way. Thus, thediscrete state-action space grows 1003 × 1003 = 1012 . In
our approach, we make 200 randomized rectangular features
over the state space. In each feature, the sensitive components
are selected from the components of the input vector withthe probability 0.6 per component. However, the featuresthat select no sensitive component are thrown away andreproduced. The ranges of the rectangles in the sensitive
subspace are randomly selected from the grid (e.g., 100partitions) by uniform distribution. The features for the action
space are generated 200 randomized hyper-rectangles in thesame way as the state’s. The number of iteration in the Gibbs
sampling is 15, the discount factor γ = 0.9, the temperature
keeps T = 0.4 constant, and the learning rate α = 0.2,
of f set(s) and width(s) in (7) are given by the average anddeviation of Q-values in state s over 20 actions that are selected by uniform distribution. It is compared with a regulargrid approach: The state space is uniformly partitioned into
6 × 6 × 6 = 216 regular exclusive hyper-rectangles without
gaps, and the action space is also uniformly partitioned into
6 × 6 × 6 = 216 regular exclusive hyper-rectangles without
gaps. Note that in the regular grid approaches, the hyperrectangles correspond to the components of the feature vector
and used only for value approximation, therefore the actions
are selected from the 12 × 12 × 12 discrete action space inthe case of the 6 × 6 × 6 = 216 hyper-rectangles.
Fig.5 compares the performance of the random coarse
coding against regular grid approaches averaging over 10
runs. The best solutions of this task are composed of only
three decision steps as shown in Fig.4, but unfortunately the
proposed method often couldn’t find it resulting four or fivedecisions. The reason of this result is that the random coarse
coding generates different rectangles for each trial, therefore
the essential features for the optimum solutions couldn’t bemade in such cases. On the other hand, the uniform grid
coding couldn’t find any solutions at all even though thenumber of features is larger than the random coarse coding’s
one, especially in the case of 63 states and 63 actions.
As the second example, Fig.8 shows a slightly modified
multi-joint arm reaching task in which both the state andthe action are 8-dimensional. The original benchmark is also
proposed by [6]. The arm is planar and composed of eightlinks that are connected by the joints in series. The states = (θ1 , θ2 , · · · θ8 ) is 8-dimensional, θ1 denotes the angleof the root link from the horizontal, and θi where i > 1 is

GOAL

Fig. 6. A learned example behavior of a reaching task using redundantarm that have three-joints. The conditions that the joints are shown by black
circles are the positions at which the learner is making decisions.

GOAL

Fig. 7. A learned example behavior of a reaching task using redundantarm that have four-joints. The conditions that the joints are shown by black
circles are the positions at which the learner is making decisions.

the angle of the joint between ith link and (i − 1)th link.
All angles are constrained to lie in the range −0.75π ≤θ ≤ 0.75π. The arm is constrained to lie in the area 0 ≤x ≤ 1 and 0 ≤ y ≤ 1. The action a = (θ1d , θ2d , · · · θ8d ) is
also 8-dimensional, representing a destination of the joint’s
angles. When a destination is given as the agent’s action, thesimulation of the movement is executed by summing small
displacements (δθ1 , δθ2 , δθ8 ) in the state space. It is givenby(δθ1 , δθ2 , δθ8 )λ= λ(a − s) , where
π
, 1
= min
15|a − s|

GOAL

Fig. 8. A learned example behavior of a reaching task using redundantarm that have eight-joints. The conditions that the joints are shown by black
circles are the positions at which the learner is making decisions.

When the arm collides with obstacles, or intersects itself,or reaches the goal region, or reaches the destination, thenthe agent makes the next decision. The position of the rootjoint connected to the base is (0.75, 0.5), and the arm has
length 0.6. The goal region is 0.3 ≤ x ≤ 0.5 and 0.8 ≤y ≤ 0.9. The initial state is θ1 = −0.75π and the others are
all 0. There exist two polygonal obstacles; Obstacle 1 is arectangle, and its apexes are (0.8, 0.0) , (0.8, 0.2), (1.0, 0.3)
and (1.0, 0.0), Obstacle 2 is a quadrangle, and its apexes are(0.0, 0.45), (0.55, 0.45), (0.55, 0.55) and (0.0, 0.55).
In this experiment, all the agents partition the state space
into 108 grids, dividing each dimension into regular 10
partitions. The action space is also partitioned into 108 grids
in the same way. Thus, the discrete state-action space grows
108 ×108 = 1016 . In our approach, we make 200 randomized
rectangular features for the state space and the action space
respectively. In each feature, the sensitive components are
selected from the components of the input vector with theprobability 0.3 per component. The number of iteration in
the Gibbs sampling is 40, and the other settings are thesame as the rod-in-maze problem’s. It is compared with aregular grid approach: the state space is uniformly partitioned
into 28 = 256 regular exclusive hyper-rectangles without
gaps, and the action space is also uniformly partitioned into
28 = 256 regular exclusive hyper-rectangles without gaps.
Note that in the regular grid approaches, the hyper-rectangles
correspond to the components of the feature vector andused only for value approximation, therefore the actions are
selected from the 108 discrete action space.
Fig.11 compares the performance of the random coarse
coding against the regular grid approach averaging over 10
runs.
The best solutions of this task are composed of only threedecision steps. Although the proposed method generates

30

30
Random rectangularcoarse coding 200x200
25
Averaged Reward (1000 steps)

Averaged Reward (1000 steps)

25

20

15

10

5

Random rectangularcoarse coding 200x200
20Regular grid coding(2x2x2x2x2x2x2x2)x(2x2x2x2x2x2x2x2)

15

10

5
Regular grid coding(6x6x6)x(6x6x6)

0

0
0

20000

40000

60000

80000

100000

0

20000

40000

60000

80000

100000

Learning Steps

Learning Steps

Fig. 9. Learning results averaged over 10 trials in the 3-joints redundantarm reaching task. The vertical axis gives the averaged reward over making
1000 decision steps.

Fig. 11. Learning results averaged over 10 or 13 trials in the 8-joints
redundant-arm reaching task. The vertical axis gives the averaged reward
over making 1000 decision steps.

30
Random rectangularcoarse coding 200x200
Averaged Reward (1000 steps)

25

20

15

10

Regular grid coding(4x4x4x4)x(4x4x4x4)

5

0
0

20000

40000

60000

80000

100000

Learning Steps

Fig. 10. Learning results averaged over 10 trials in the 4-joints redundantarm reaching task. The vertical axis gives the averaged reward over making
1000 decision steps.

different features in each trial, it can find the best solution in
all the cases. On the other hand, the uniform grid approach
couldn’t find any solutions even though the number offeatures are larger than the random coarse coding’s.
VI. D ISCUSSION
A. Relation between the Pattern of the Random Features andthe Learning Performance
In the simulation results, the coarse coding sometimes
failed to find optimum solutions because of the randomnessof the features. However, it could find approximate solutions
using just 200 state features and 200 action features not
only in the 3 × 3-dimensional state-action problem but inthe 8 × 8-dimensional problem as well. Reflection on someof these will make clear that the coarse coding is suited forfinding feasible or reasonable solutions in high-dimensional
problems that have a number of sub-optimum solutions. That
is to say, it is hard to find optimum solutions, especiallywhen the problem has a needle-like evaluation function.
The regular grid approaches could not find any solutions
at all, though using no less computational resources than thecoarse coding’s. In the grid approaches, each cell exclusively
corresponds to a specific binary (0-1-valued) feature, andthe set of feature vectors is always linearly independent. On
the other hand, the coarse coding tends to generate linearly
independent feature vectors for essential states (or actions)
without exponential growth of the variables, however, thelinearly independence between the feature vectors is notguaranteed.
Fig.12 shows landscapes of learned Q-functions in the
redundant-arm reaching task. The landscape in the randomized coarse-coding is smooth and better to approximate
functions than the regular grid approach.
The learning performance of the coarse coding also depends on the choice of the sensitive components, the ranges
and the size of the rectangles for the features. In this paper,
these parameters are simply given randomly, but it is also
possible to consider some other sophisticated methods; Oneis feature iteration approach [1], whereby a set of features isselected, some computation is done using these features, andbased on the results of the computation, some new features
are introduced. Indeed, about 30 percent of the coarse-coding
features are not used in the rod-in-maze experiments. When
we give the coarse coding features randomly, we should fix
a few parameters: One is a number of the features, andthe other is probability for choosing sensitive components
from the input vector to generate rectangular features. In
this paper, the probability for sensitive components is experimentally designed so that about 10 percent of the features
are active in all the state or action.
This paper introduced a value approximation techniquethat the state features and the action features are separately
given. It is advantageous to execute Gibbs sampling overaction space. The other approach can be considered togenerate features directly over state-action space, however,it tends to cost heavy computation in Gibbs sampling.

Q-value

Q-value
295
290
285
280
275
270
265
260
255

0

2

6.5
6.45
6.4
6.35
6.3
6.25
6.2
6.15
6.1
6.05

0
4

6

8
1st element 10 12of the action
14

16

18

20 20

18

16

14

12

10

8

6

4

2

0

5th elementof the action

2

4

6

8
1st element 10 12of the action
14

16

18

20 20

18

16

14

12

10

8

6

4

2

0

5th elementof the action

Fig. 12. Lefthand side: A landscape of a learned Q-function using random rectangular coarse coding in the redundant-arm reaching task. The axises are
the 1st and 5th element of the action in the initial state. The other action elements are kept constant. Righthand side: A landscape of a learned Q-function
using the regular grid approach in the same condition.

B. 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 boundsof the number of the iteration in Gibbs sampling. It isnoteworthy that the Gibbs sampling affects only the time
for action selection, it does not affect the learning steps.
Therefore, the number of the iteration should be given
as long as possible. To get good samples with less time,overrelaxation techniques or simulated annealing [3] arepossible.
VII. C ONCLUSION
This paper proposed a new approach combining random rectangular coarse coding with Gibbs-sampling action selection to cope with reinforcement learning in highdimensional domains. The proposed coding method is very
simple and quite suited both to approximate Q-functions inhigh-dimensional spaces, and to execute Gibbs sampling.
The action selection scheme using Gibbs-sampling enables tohandle high-dimensional action space in RL problems. The
parameters of the rectangular features are given randomly,
however, it works very well in Rod-in-maze problem andMulti-joint arm problem. A future work is to consider someother sophisticated methods to generate (or modify) thefeature parameters.

R EFERENCES[1] Bertsekas, D.P. & Tsitsiklis, J.N.: Neuro-Dynamic Programming,
Athena Scientific (1996).
[2] Hengst, B.: Discovering Hierarchy in Reinforcement Learning with
HEXQ: Proc.of 19th International Conference on Machine Learning(ICML2002), pp.243–250.
[3] Jordan, M. I.: Learning in Graphical Models, The MIT Press, (1999).
[4] Kaelbling, L. P., & Littman, M. L., & Moore, A. W.: Reinforcement
Learning: A Survey, Journal of Artificial Intelligence Research, Vol.
4, pp. 237–277 (1996).
[5] Lin, L. J.: Scaling Up Reinforcement Learning for Robot Control, Proceedings of the 10th International Conference on Machine Learning,pp. 182–189 (1993).
[6] Moore A.W. and Atkeson, C.G.: The Parti-game Algorithm for Variable Resolution Reinforcement Learning in Multidimensional Statespaces, Machine Learning, Vol.21, pp.199–233 (1995).
[7] J.D.R. Millan, D.Posenato & E.Dedieu: Continuous-Action QLearning, Machine Learning, Vol.49, pp.247–265 (2002).
[8] Sallans, B. & Hinton, G.E.: Reinforcement learning with factored
states and actions. Journal of Machine Learning Research, vol.5,
pp.1063-1088 (2004).
[9] Santamaria, J. C., Sutton, R. S. & Ram, A.: Experiments with Reinforcement Learning in Problems with Continuous State and Action
Spaces, Adaptive Behavior 6 (2), pp.163–218 (1998).
[10] Sutton, R.S.: Generalization in reinforcement learning: Successful
examples using sparse coarse coding, Advances in Neural Information
Processing Systems 8 (NIPS8), pp.1038–1044 (1996).
[11] Sutton, R.S. & Barto, A.: Reinforcement learning: An introduction, A
Bradford Book, The MIT Press (1998).
[12] Takahashi, Y. & Takeda, M. & Asada, M.: Continuous valued Qlearning for vision-guided behavior acquisition. Proceeding of the1999 IEEE International Conference on Multi-sensor Fusion andIntegration for Intelligent Systems, pp.255–260 (1999).
[13] Watkins, C.J.C.H. & Dayan, P.: Technical Note: Q-Learning, Machine
Learning, Vol.8, pp.279–292 (1992).