SICE Annual Conference 2007
Sept. 17-20, 2007, Kagawa University, Japan

Reinforcement Learning in Multi-dimensional State-Action Space using
Random Rectangular Coarse Coding and Gibbs Sampling
Hajime Kimura½
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: This paper presents a coarse coding technique and an action selection scheme for reinforcement learning (RL)in multi-dimensional and continuous state-action spaces following conventional and sound RL manners. RL in highdimensional continuous domains includes two issues: One is a generalization problem for value-function approximation,and the other is a sampling 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 andto execute Gibbs sampling. Gibbs sampling enables us to execute action selection following Boltsmann distribution overhigh-dimensional action space.
Keywords: Reinforcement learning, 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
is tabular Q-learning [11] because of its simplicity andwell-developed theory. However, RL in real world applications is to deal with high-dimensional continuous
state-action spaces, that immediately raises the curse ofdimensionality [5], in which costs increase exponentiallywith the number of the state-action variables. It includes
two issues in RL: One is a generalization problem for Qfunction over high-dimensional continuous spaces, andthe other is a sampling problem that is to select actions
following a given distribution over high-dimensional continuous action spaces.
To deal with continuous state space, a number of RL
algorithms combining with function approximation techniques have been invented: Q-net [4] is an extended Qlearning algorithm by means of using neural networks
to generalize the Q-function, SARSA with CMAC [9]is a better method because it is based on linear function approximation, that has good theoretical convergence properties in RL [1]. [8] and [10] proposed RL
algorithms with instance-based function approximation,and [6] extended it to consider continuous action spaces.
However, these works are not aimed at handling highdimensional spaces. [9] introduced hashing to cope withhigh-dimensional spaces. Hashing is a consistent pseudorandom collapsing of a large tiling into a much smaller
set of tiles. This approach is quite favorable, however,
the action sampling problem remains.
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 to be made [3]. One standard practice is known
as Boltzmann exploration, however, its naive computa-

tional 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 in high-dimensional spaces[2][7].
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.

2. PROBLEM FORMULATION
Let denote state space,  be action space,  be a
set of real number. At each discrete time , the agent
observes state   , selects action   , and thenreceives an instantaneous reward    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  and  . And the next state   is chosen according to the transition probability       ,and the reward  is given randomly following the expectation    . The agent does not know       and     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:
 


 



  ,(1)

where the discount factor,      specifies the importance of future rewards, and  is the value at time . In
MDPs, the value can be defined as:




 



 






  



,(2)

where  denotes the expectation. The learning objective in MDPs is to find optimum policies that maximize
the value of each state  defined by (2). The state andthe action  are both defined as multi-dimensional continuous spaces in this paper.

3. RANDOM RECTANGULAR COARSECODING FOR HIGH-DIMENSIONALSPACES

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 other all 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 into some vector         , that is refered to feature vector associated with . 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           that has the same number of the components as the feature vector
. For example, the statevalue is approximated by








 

.

(3)



This value function is said to be linear. When the setof the feature vectors   is linearly independent, then it is known that the predictions of the TDmethods converge in expected value to the ideal predictions [9].
To generate feature vectors that are linearly independent in high-dimensional spaces, random rectangularcoarse coding is described below. This idea is directly
inspired from ”CMAC with hashing” [9]. And it is also
derived from consideration of the Parti-game algorithm[5] in multi-joint arm problems, in which the complexityof the ultimate task remains roughly constant as the number of degrees of freedom increases. These deliberation
lead that a fine state-action representation may be practicable by regarding some subsets of the state (or action)
variables in high-dimensional spaces.
To explain the concept of the random rectangular cod that
ing, consider a randomized rectangular feature
is an element of the feature vector. When an input vector
is inside of the rectangle, then the corresponding feature has the value , otherwise . In our approach, thefeature rectangles are overlapped in many places. Thiskind of approach is known as coarse coding [9]. In higher
dimensional space, a feature selects a few arbitrary
sensitive components of the input vector , and composesa hyper rectangle in the sensitive subspace. That is, a feature
 ignores non-sensitive components of the input
vector . For example in Fig.1, the input vector is twodimensional   , and the 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  and , however,T4 is sensitive only to  and T5 is sensitive only to  .
In this paper, the set of sensitive components, the ranges
and the size of the rectangles are given randomly, but it isalso possible to consider some other sophisticated methods. 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.
In this paper, state-features   where         that are defined in state space and actionfeatures   where          that are defined in action space are introduced. It is desirable
that  norm of the feature vectors are constant (is the best1 ) in linear function approximation. Therefore, state-feature vectors
 that has  components       
 and actionfeature vectors   that has  components             are given by the statefeatures   and action-features   respectively according to    






 

, where   otherwise.

(4)  

, where   otherwise.

(5)

 





 





Then the approximate value function of state-action pairs(i.e., Q-function) is given by   


 



 
    ,(6)  

where  are parameters of which the number is 
is a normalization factor so that the  , and

½ The reason is to keep consistency of Q-learning’s learning rate param-

eter avoiding influence of magnitude of the norm.

norm of the feature vectors composed of   and  
keep  constant. The parameters  are updated by agradient-descent method. The specification are shown
later. In this paper, the agent selects action following
Boltzmann distribution using Q-function. The proposed
generalization method has the following advantages:         so that                 

,(7)

 The rectangular feature can directly represent mu-

where  is a temperature parameter that controls exploration behavior. In many cases,      and2    , but this paper recommends  
to be average of Q-value in state  and    to be
deviation of Q-value in state . As shown in (7), thenaive flat action-selection scheme needs to calculate all
discrete action values, that gives rise to exponentially increase with the number of the dimension. For this reason,
Q-learning nor SARSA have little opportunity to apply
real-world tasks that have high-dimensional continuous
action-space.

Although this approximation itself is promising, naive
execution of the Boltzmann exploration over highdimensional continuous action-space gives rise to exponential growth of the computational cost.

4.2 Selecting Action by Gibbs SamplingThis section describes an action-selection method forhigh-dimensional action space using Gibbs sampling,that is a powerful technique for generating samples frommulti-dimensional complex distribution. In the Gibbs
sampler, the components of the multidimensional randomvariable are resampled in turn, conditional on the others, using some fixed ordering. Fig.3 illustrates the Gibbs
sampling for a case with two variables  . The distribution for action selection probability is equal to Fig.2.
In the initial step of Gibbs sampling, an arbitrary sample
  is selected in advance. In each iteration, the top
right (1) in Fig.3 represents selecting action  following the conditional probability given , and the bottom
left (2) in Fig.3 represents selecting action  following
the conditional probability given  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
 again, following the conditional probability given at the bottom left (2) in Fig.3. After a sufficient numberof iterations, we can take  and  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 number of 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  parts into each dimensionof the 8-dimensional action space, then finding the joint
distribution for the flat action selection costs memory capacity and computation over  variables, whereas theGibbs sampling, that uses conditional distribution, costsvariables and the number of iteration can be reduced to  or  . That is, Gibbs sampling cuts down
the computational cost over .
Throughout this paper, probability of the action selection is given by (7), but we use particular notationtual dependence between its sensitive components.
It is useful to incorporate domain knowledge about
the task into the agent.
 The computation both to generate feature vectors
and to 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.

4. SAMPLING AND LEARNING IN
HIGH-DIMENSIONAL SPACE
4.1 Conventional Approach: Flat Action Selection
select

P(a)

a2

a1

Fig. 2 An action-selection with a regular grid approachin two-dimensional action space. The probability
function of the action selection   is represented
by quantizing the action space   into a finite
number of 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 multidimensional 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 cell needn’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  equivalent parts into eachdimension of the action-space. That is, when the actionspace is  -dimensional, the partitioning yields  cells.
Each cell is considered to be a discrete action  where        . For each decision epoch, an action
 is selected following an associated probability function  . Fig.2 shows the regular grid partitions andits distribution function in two-dimensional action-space.
In this paper, the action-selection probability    isgiven by Boltzmann distribution that contains associated¾ The reason is to keep consistensy of parameter Ì avoiding magnitude

influence of Q-value.

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 distribution of the action selection probability. The top right (1) represents selecting
action  following the conditional probability given . The bottom left (2) represents selecting action  following
the conditional probability given  at the top right (1). The bottom right (3) represents selecting action  again,
following the conditional probability given  at the bottom left (2).
for Gibbs sampling. Suppose that a regular grid partition divides  parts into each dimension of the  dimensional action space, same as the case of the flat
action selection. We give a  -dimensional action 
as          , where each component (        ) is   
 (        ).
A value of state  and action  is given by             . This value is also equal to the flat
action selection method’s. Sampled components of theaction vector at the iteration in the Gibbs sampling isgiven by         . Then, the Gibbs sampler
updates components of the action vector at the iteration
 following the conditional distribution as












 
 





 

    

 ,



 

    

 ,



 

..
.




 

     



 ,


where the conditional probability         

given by the following Boltzmann distribution:         







 
 



 is




½ ¾        
(8).
½ ¾       

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¿ It is supposed that the number of the iteration is enough. Since predict-ing the lower bounds of this number is a difficult problem, the samples
would be likely to approximate (7).

high-dimensional action-space. Note that since the calculation of the conditional probability in each iteration isalong an arbitrary axis of the action space, the computational cost can be reduced in the proposed rectangularcoarse coding.
4.3 Learning Algorithms
This section describes Q-learning and SARSA algorithms combined with random rectangular coarse-coding
and the action selection using Gibbs sampling. As shownin the section 3., state-feature vectors
 that has
 components       
 andaction-feature vectors   that has  components             are given by thestate-features   where         and actionfeatures   where          respectively according to (4) and (5). Then the approximate value function is given by (6). The agent observes state , and selects action  following Boltzmann distribution given by(7). However, actual process of choosing action would
be executed following Gibbs sampling given by (8). After that, the agent observes the next state  and instantaneous reward  resulting from the state transition. The
standard Q-learning algorithm updates values by
TD error   









           , (9)! TD error ,(10)

where  is a discount factor, ! is a learning rate parameter, where   !  . In my approach, the Q-function isrepresented by (6), therefore the updating of (10) is executed by modifying the parameters  using a gradientdescent method as




     

! TD error .

(11)

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 therod 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-inmaze task. The black circles of the bottom of the rod
represent the positions at which the learner is making
decisions.
Unfortunately, it is difficult to operate    
strictly in high-dimensions, we are to substitute approximated     found in the process of the Gibbs
sampling. For the other hand, strict SARSA algorithm
can be executed easily by replacing     with    , where  is an action selected in state  .

5. EXPERIMENTS
This section evaluates the proposed method empirically in two learning tasks. Fig.4 shows a slightly modified rod-in-maze task in which both the state and theaction are three-dimensional. The original rod-in-mazetask is proposed by [5]. The state    " # is threedimensional.  " denotes the position of the center ofthe rod and must lie in the area     and   "  .
The # denotes the angle of the rod from the horizontal,
and is constrained to lie in the range   #  . The
action     "  #  is also three-dimensional, representing a destination of the rod 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 Æ  Æ" Æ# in the state . The small displacements are given so that each state variable would reachthe destination as fast as possible, but it is constrainedsuch that Æ  Æ"   and  Æ#  . If
the rod collides with obstacles, or reaches the goal region, or reaches the destination, then the agent makes thenext decision. The goal region is    and  "  . The rod has length . In the field,
there exist four polygonal obstacles; Obstacle 1 is a triangle and its apexes are  ,   and  .
Obstacle 2 is a triangle and its apexes are  ,  and   . Obstacle 3 is a quadrangle
and its apexes are  ,  ,   and . Obstacle 4 is a quadrangle and its apexes are ,   ,   and  . Whenthe rod reaches the goal region, the agent receives reward 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    grids, dividing each dimension
into a hundred regular partitions. The action space is also
partitioned into    grids in the same way. Thus,
the discrete state-action space grows     .
In our approach, we make 200 randomized rectangularfeatures over the state space. In each feature, the sensitive
components are selected from the components of the input vector with the probability  per component. However, the features that select no sensitive component are
thrown away and reproduced. The ranges of the rectangles in the sensitive subspace are randomly selected fromthe grid (e.g., 100 partitions) by uniform distribution. The
features for the action space are generated 200 randomized hyper-rectangles in the same way as the state’s. The
number of iteration in the Gibbs sampling is , the discount factor   , the temperature keeps   
constant, and the learning rate !  ,    and   in (7) are given by the average and deviationof Q-values in state  over 20 actions that are selectedby uniform distribution. It is compared with a regulargrid approach: The state space is uniformly partitioned
into      regular exclusive hyper-rectangles
without gaps, and the action space is also uniformly partitioned into      regular exclusive hyperrectangles without gaps. Note that in the regular grid approaches, the hyper-rectangles correspond to the components of the feature vector and used only for value approximation, therefore the actions are selected from the discrete action space in the case of the   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 fouror five decisions. The reason of this result is that the random coarse coding generates different rectangles for eachtrial, therefore the essential features for the optimum solutions couldn’t be made in such cases. On the other
hand, the uniform grid coding couldn’t find any solutions
at all even though the number of features is larger than
the random coarse coding’s one, especially in the case of states and  actions.

GOAL

GOAL

Fig. 8 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.

Fig. 6 A learned example behavior of a reaching taskusing redundant-arm 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 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.
As the second example, Fig.8 shows a slightly modified multi-joint arm reaching task in which both the state
and the action are 8-dimensional. The original benchmark is also proposed by [5]. The arm is planar and com-posed of eight links that are connected by the joints inseries. The state  #  #     #  is 8-dimensional, #denotes the angle of the root link from the horizontal, and# where  $  is the angle of the joint between th linkand  th link. All angles are constrained to lie in therange   #   . The arm is constrained tolie in the area     and   "  . The action  #   #     #  is also 8-dimensional, representing a destination of the joint’s angles. When a destination is given as the agent’s action, the simulation of the
movement is executed by summing small displacements
Æ#  Æ#  Æ#  in the state space. It is given byÆ#  Æ#  Æ# 



% 

%







, where  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 theroot-joint connected to the base is  , and thearm has length . The goal region is    and   "  . The initial state is #   andthe others are all . There exist two polygonal obstacles;
Obstacle 1 is a rectangle, and its apexes are   ,   ,   and  , Obstacle 2 is aquadrangle, and its apexes are  ,  ,  and  .
In this experiment, all the agents partition the state
space into  grids, dividing each dimension into regular 10 partitions. The action space is also partitioned into
 grids in the same way. Thus, the discrete state-action
space grows     . In our approach, we make200 randomized rectangular features for the state space
and the action space respectively. In each feature, the sensitive components are selected from the components of30

25
Averaged Reward (1000 steps)

the input vector with the probability  per component.
The number of iteration in the Gibbs sampling is , andthe other settings are the same as the rod-in-maze problem’s. It is compared with a regular grid approach: thestate space is uniformly partitioned into    regular
exclusive hyper-rectangles without gaps, and the action
space is also uniformly partitioned into    regular
exclusive hyper-rectangles without gaps. Note that in theregular grid approaches, the hyper-rectangles correspondto the components of the feature vector and used only forvalue approximation, therefore the actions are selectedfrom the  discrete action space.

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

15

10

5

0
0

25
Averaged Reward (1000 steps)

40000

60000

80000

100000Fig. 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.

Random rectangularcoarse coding 200x200

2015

6. DISCUSSION
105Regular grid coding(6x6x6)x(6x6x6)
0
0

20000

40000

60000

80000

100000

Learning Steps

Fig. 9 Learning results averaged over 10 trials in the 3joints redundant-arm reaching task. The vertical axis
gives the averaged reward over making 1000 decision
steps.
30
Random rectangularcoarse coding 200x200
25
Averaged Reward (1000 steps)

20000

Learning Steps

30

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 redundant-arm reaching task. The verticalaxis gives the averaged reward over making 1000 decision steps.
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
three decision steps. Although the proposed method generates different features in each trial, it can find the bestsolution in all the cases. On the other hand, the uniform
grid approach couldn’t find any solutions even though thenumber of features are larger than the random coarse coding’s.

6.1 Relation between the Pattern of the Random Features and the Learning Performance
In the simulation results, the coarse coding sometimes
failed to find optimum solutions because of the randomness of the features. However, it could find approximate
solutions using just  state features and  action features not only in the  -dimensional state-action problem but in the-dimensional problem as well. Reflection on some of these will make clear that the coarse
coding is suited for finding feasible or reasonable solutions in high-dimensional problems that have a numberof sub-optimum solutions. That is to say, it is hard tofind optimum solutions, especially when the problem hasa needle-like evaluation function. The regular grid approaches could not find any solutions at all, though using
no less computational resources than the coarse coding’s.
In the grid approaches, each cell exclusively corresponds
to a specific binary (0-1-valued) feature, and the set offeature vectors is always linearly independent. On theother hand, the coarse coding tends to generate linearly
independent feature vectors for essential states (or actions) without exponential growth of the variables, however, the linearly independence between the feature vectors is not guaranteed.
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, theranges 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 sophisticatedmethods; One is feature iteration approach [1], whereby
a set of features is selected, some computation is done using these features, and based on the results of the computation, some new features are introduced. Indeed, about percent of the coarse-coding features are not used in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

2

4

6

8
1st element 10 12of the action
14

5th elementof the action

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 redundantarm 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.
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, and the other isprobability 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 technique that the state features and the action features are
separately given. It is advantageous to execute Gibbs
sampling over action space. The other approach can beconsidered to generate features directly over state-action
space, however, it tends to cost heavy computation in
Gibbs sampling.
6.2 Finding an Appropriate Number of the Iterationin 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[2] are possible.

7. CONCLUSION
This paper proposed a new approach combining random rectangular coarse coding with Gibbs-sampling action selection to cope with reinforcement learning in
high-dimensional domains. The proposed coding method
is very simple and quite suited both to approximate Qfunctions in high-dimensional spaces, and to execute
Gibbs sampling. The scheme using Gibbs-sampling enables to handle high-dimensional action space in RL
problems. The parameters of the rectangular features are
given randomly, however, it works well in Rod-in-maze
problem and Multi-joint arm problem.

REFERENCES[1]

Bertsekas, D.P. & Tsitsiklis, J.N.: Neuro-Dynamic
Programming, Athena Scientific (1996).
[2] Jordan, M. I.: Learning in Graphical Models, The
MIT Press, (1999).
[3] Kaelbling, L. P., & Littman, M. L., & Moore, A.
W.: Reinforcement Learning: A Survey, Journal of
Artificial Intelligence Research, Vol. 4, pp. 237–277(1996).
[4] Lin, L. J.: Scaling Up Reinforcement Learning for
Robot Control, Proceedings of the 10th International Conference on Machine Learning, pp. 182–
189 (1993).
[5] Moore A.W. and Atkeson, C.G.: The Parti-game
Algorithm for Variable Resolution Reinforcement
Learning in Multidimensional State-spaces, Machine Learning, Vol.21, pp.199–233 (1995).
[6] J.D.R. Millan,
D.Posenato & E.Dedieu:
Continuous-Action Q-Learning, Machine Learning,
Vol.49, pp.247–265 (2002).
[7] Sallans, B. & Hinton, G.E.: Reinforcement learningwith factored states and actions. Journal of Machine
Learning Research, vol.5, pp.1063-1088 (2004).
[8] 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).
[9] Sutton, R.S. & Barto, A.: Reinforcement learning:
An introduction, A Bradford Book, The MIT Press(1998).
[10] Takahashi, Y. & Takeda, M. & Asada, M.: Continuous valued Q-learning for vision-guided behavior
acquisition. Proceeding of the 1999 IEEE International Conference on Multi-sensor Fusion and Integration for Intelligent Systems, pp.255–260 (1999).
[11] Watkins, C.J.C.H. & Dayan, P.: Technical Note:
Q-Learning, Machine Learning, Vol.8, pp.279–292(1992).