Constructing Action Set from Basis Functions for Reinforcement
Learning of Robot Control
Akihiko Yamaguchi∗ , Jun Takamatsu∗ , and Tsukasa Ogasawara∗∗ Graduate School of Information Science,

Nara Institute of Science and Technology
8916-5, Takayama, Ikoma, Nara 630-0192, JAPANE-mail: {akihiko-y, j-taka, ogasawar}@is.naist.jp
Abstract— Continuous action sets are used in many reinforcement learning (RL) applications in robot control since thecontrol input is continuous. However, discrete action sets also
have the advantages of ease of implementation and compatibility with some sophisticated RL methods, such as the Dyna
[1]. However, one of the problem is the absence of generalprinciples on designing a discrete action set for robot control
in higher dimensional input space. In this paper, we propose
to construct a discrete action set given a set of basis functions(BFs). We designed the action set so that the size of the set is
proportional to the number of the BFs. This method can exploit
the function approximator’s nature, that is, in practical RL
applications, the number of BFs does not increase exponentiallywith the dimension of the state space (e.g. [2]). Thus, the sizeof the proposed action set does not increase exponentially withthe dimension of the input space. We apply an RL with theproposed action set to a robot navigation task and a crawling
and a jumping tasks. The simulation results demonstrate thatthe proposed action set has the advantages of improved learning
speed, and better ability to acquire performance, compared toa conventional discrete action set.
Index Terms— Reinforcement learning, discrete action set,
motion learning, crawling, jumping.

I. I NTRODUCTION
Many highly functional robots, such as humanoid robots,
can walk, jump, and perform other motions, but, preprogrammed ones only. Essential for the next generation ofrobots is the function to acquire a motion when given an
objective. Reinforcement Learning (RL) is one of the technologies that realizes this function, and it has been applied torobot control [2]∼[11]. However, it is still a difficult problem
to deal with large state and action spaces. In this paper, we
focus on the design of action set A.
In most robot control problems, the input space U of therobot is continuous. Therefore, A is designed to be continuous in many robotics applications of RL. A typical method
is a kind of Gaussian policy [3], [4]. Some researchers
use a function approximator, such as Normalized Gaussian
Network (NGnet) [12], to represent and learn continuous
actions [2], [5]. Alternative methods are wire-fitting [13], [6]that enables to calculate an arg max operation quickly, andthe B-Spline function approximator [7], [14].
In contrast, a discrete action set is also often used [8],[9], [10], [11], because of ease of implementation. Moreover,a discrete action set is compatible with some hierarchicalarchitectures [9], multi-module learning systems [8], andthe Dyna architecture [1]. However, there are few generalprinciples on the design of an action set for robot controlof higher dimensional input space. The problem of theconventional design is the exponential increase of the sizeof the action set with the dimension of the input space. For
instance, a “Grid Action Set” mentioned in section VI-C has
this problem.
Therefore, we intend to construct a compact discrete action
set for robot control applications of RL. Concretely, we
propose to construct an action set given a set of basis
functions that have a center in the state space as a parameter.
We design an action as a trajectory calculated from thecurrent state and a center of a basis function. In this case,the size of our action set is the same as, or a few times
larger than the number of the basis functions. In practicalapplications, such as motion learning of multi-link robots, thenumber of the basis functions used to approximate a valuefunction does not increase exponentially with the dimensionof the state space [2]. The proposed action set can exploit thisnature by constructing it given the basis functions. We callthe proposed action set DCOB, which stands for Directed toa Center Of a Basis function.
Miyamoto et al. proposed a reinforcement learning with
via-point representation [15]. This method is similar to the
proposed action set in generating a reference trajectory. In
contrast, their method is a continuous action and does not use
basis functions like our method. Yamaguchi et al. proposed
to construct an action set given a set of basis functions[16]. However there are two problems: (1) their method does
not consider carefully about the boundary conditions of the
trajectory, which strongly affects the Markov property of thetask as mentioned in section IV, and (2) a constructed action
is too long to acquire a fine behavior since they directly use
the trajectory calculated from the current state and the centerof a basis function. The proposed method in this paper solves
these problems as described in section III.
II. R EINFORCEMENT L EARNING WITH BASIS F UNCTIONSFirst, we introduce RL with a function approximator.
The purpose of RL is that a system (agent) whose input
is a state, xn ∈ X , and a reward, Rn ∈ R, and whose
output is an action, an ∈ A, acquires the policy, π(xn ) :X[∑→ A, that maximizes
the expected discounted return,]∞E k=1 γ k−1 Rn+k , where n ∈ N = {0, 1, . . . } denotesthe time step and γ ∈ [0, 1) denotes a discount factor. In
some RL methods, such as Q-learning [17] and Sarsa [18],an action value function, Q(x, a) : X ×A → R, is learned torepresent the expected discounted return by taking an actiona from a state x. Then, the optimal action rule is obtained
from the greedy policy π(x) = arg maxa Q(x, a).
If X or A are continuous, a function approximator is used.
Here, we assume to use a linear function approximator overa continuous X and a discrete A. An action value function
is represented as follows:
Q(x, a) = θa> φ(x)(1)>

φ(x) = (φ1 (x), . . . , φ|K| (x))(2)

where θa and φ(x) denote a parameter vector and a feature
vector respectively. K = {φk |k = 1, 2, ..} denotes predetermined basis functions. In this paper, we use a Normalized
Gaussian Network (NGnet) that is often used in RL applications [5], [2]. A basis function of the NGnet is defined asfollows:G(x; µk , Σk )φk (x) = ∑(3)00
k0 G(x; µk , Σk )where G(x; µ, Σ) denotes a Gaussian with mean µ andcovariance matrix Σ.

Fig. 1. Illustration of how the possible actions of the DCOB at the Current
State are generated.

III. BASIS F UNCTION BASED ACTION C ONSTRUCTION
As mentioned in section I, we propose to construct anaction set given a set of basis functions (BFs) to relax the
exponential increase problem of an action set. To accomplish
this, we assume the following:(1) Each BF k∈K has a fixed center µk ∈X in the state

space.
(2) A space in which a trajectory is defined is given as

Q (e.g. a joint angle space). A function that extractsq∈Q from a state x∈X is given as q = Cp (x) : X →Q. A function that extracts the derivative of q∈Q (e.g.
joint angular velocities) from a state x∈X is given asq̇ = Cd (x). Moreover, a function to follow the designed
trajectory qd (t), that is, calculate a control input u∈U(e.g. torques) from the trajectory is given as u(t) =Ctrl (x(t), qd (t + δt)), such as a PD controller. Here, δtdenotes a time step size to generate the trajectory.
Obviously a basis function of the NGnet defined by eq. (3)satisfies (1), however, note that the proposed method is not
restricted to the NGnet as mentioned in section VII.
An action of the proposed action set, DCOB, directed toa center of a BF, is generated through the following threesteps (see Fig. 1):
At a time step n ∈ N, a current time tn ∈ R,
and a current state xn = x(tn ),For a given target BF k∈K, and an interval Tf ∈I,
1. Generating a reference trajectory qd (tn + ta ), ta ∈[0, Tf ]with which the robot can transit from the current state
xn to the center of the target BF µk in the interval Tf .
2. Abbreviating the trajectory to ta ∈[0, Tn (xn , k)] where
Tn (xn , k) 6 Tf is decided from xn and k. Since thetrajectory of step 1 may change the state greatly (Fig.
1 (b)), a behavior, i.e. a sequence of the trajectories,
is coarse. To make the behavior fine, the reference
trajectory is abbreviated by an estimated distance toa neighbor BF (Fig. 1 (c)).
3. Following the abbreviated trajectory with a controlleru(tn + ta ) = Ctrl (x(tn + ta ), qd (tn + ta + δt)),ta ∈[0, Tn (xn , k)). The trajectory is terminated at t =tn + Tn (xn , k), the action ends, and the time step n isincremented by one.
Thus, the action set can be represented as A , K × I. Theinterval Tf is chosen from a discrete set I whose size istypically a small integer. Therefore, the size of the action
set is less than a few times of the number of the BFs. Fig.
1 illustrates how the possible actions at a current state are
generated. Thus, the exponential increase of the size of A is
prevented.
The DCOB has another advantage, that is, when the robot
is near the boundary of the state space, the DCOB prevents itfrom exceeding the boundary. This is because in most cases,
few or no BFs are allocated out of the boundary. For instance,
a multi-link robot has no actions that exceed the joint limits
if some joint angles are already near the limits.
The role of the interval Tf is to configure the speed of
the action. In order to relax a problem that the speed of theaction changes with the distance between the current state
xn and µk even for the same Tf , we define I as follows:δCp (xn , µk ) = max(Cp (µk )[j] − Cp (xn )[j] )(4)

I = {gi δCp (xn , µk ) | gi ∈ R, i = 1, 2, . . . }(5)jwhere Cp (·)[j] denotes j-th element of Cp (·), and gi is apositive constant.
In the rest of this section, we describe the details of each
step.
A. Generating a Reference Trajectory

C. Following the Abbreviated TrajectoryThe
abbreviatedtrajectory
qd (t=tn + ta ),ta ∈[0, Tn (xn , k)) is followed by a given controlleru(t) = Ctrl (x(t), qd (t + δt)), t∈[tn , tn + Tn (xn , k)). In a
simple PD controller case, it can be written asu(t) = Kp {qd (t+δt)−Cp (x(t))}−Kd Cd (x(t))(13)

The purpose of this step is to generate a reference trajectory qd (tn +ta ), ta ∈[0, Tf ] from the current state xn = x(tn )to the center of the BF µk in the interval Tf . We simply use
a cubic function,

where Kp and Kd are the gain parameters of the PD
controller.

qd (tn + ta ) = c0 + c1 ta + c2 t2a + c3 t3a .

IV. T HEORETICAL BASIS OF THE DCOBIn this section, we discuss the convergence of RL with the
DCOB and the computational cost.

(6)

The coefficients are determined with the following boundary
conditions:qd (tn ) = Cp (xn ),qd (tn + Tf ) = Cp (µk ),q̇d (tn + Tf ) = Cd (µk ),q̈d (tn + Tf ) = 0(7)where 0 denotes zero vector. The definition of the boundary
conditions are discussed in section IV.
If the system is underactuated, such as a humanoid whosebody is not fixed to the environment (see section VI), therobot can not transit to µk after following qd (tn + ta ). However, this problem is not important for RL, since RL attempts
to maximize the discounted return with any predefined action
set.
B. Abbreviating the Trajectory
Next, we attempt to abbreviate the trajectory to ta ∈[0, Tn (xn , k)] where Tn (xn , k) 6 Tf so that the state transits
to a neighbor BF. To calculate Tn (xn , k), first, we estimate
the distance from the current state xn to a neighbor BF
Dn (xn ) (eq. (11)). Then we decide Tn (xn , k) from the ratio
of Dn (xn ) and the distance between the current state andthe target BF (eq. (12)).
Initially, for each BF, k 0 ∈K, we evaluate the distance tothe nearest BF dn (k 0 ) as follows:kn (k 0 ) = arg min kµk00 − µk0 k(8)dn (k 0 ) = max (kµkn (k0 ) − µk0 k, dmin k0 ),(9)

k00 ∈K,k00 6=k0

where kn (k 0 ) is the BF that is nearest from the BF k 0 .
dmin k0 is a constant related to the BF k 0 to adjust dn (k 0 )for very small√kµkn (k0 ) − µk0 k. For a NGnet case, we define
as dmin k0 = λk0 where λk0 is the maximum eigenvalue ofthe covariance matrix of the BF k 0 .
dn (k 0 ) is a special case of Dn (xn ) where xn = µk0 . We
estimate Dn (xn ) for a general xn ∈X with φ(xn ) defined ineq. (2) as follows:
dn , (dn (1), dn (2), . . . , dn (|K|))>(10)

Dn (xn ) = d>n φ(xn ).

(11)

Finally, we calculate Tn :Tn (xn , k) =min(Dn (xn ), kµk − xn k)
Tf .
kµk − xn k

(12)Note that Tn (xn , k) is equal to Tf if the distance to the target
BF kµk − xn k is less than Dn (xn ).

A. Convergence of RL with the DCOB
Before discussing about the convergence of RL with theproposed action set DCOB, we define the relation between
the continuous task model and our discrete one as follows:n−1∑
t0 = 0, tn =Tnn0 , xn = x(tn )
(14)
n0 =0

∫ tn +Tnn
Rn =r(t)dt(15)tnwhere Tnn denotes Tn calculated for an action an at a time
step n, r(t) denotes a reward given for the input u(t) fromthe state x(t).
Most proofs of the convergence of RL with a linear
function approximator assumes a Markovian task [19], [20].
Assume that the task x(t), u(t), r(t) is Markovian. Ifu(t), t∈[tn , tn + Tnn0 ) is determined by an and x(t),t∈[tn , tn + Tnn0 ), it is obvious that the converted task xn ,an , Rn is also Markovian. The reference trajectory qd (t) andthe interval Tnn0 are calculated from the state x(tn ) and theaction an . The given controller u = Ctrl (x, qd ) calculates
the control input from a state and the reference trajectory.
Therefore, the converted task with the proposed action set
satisfies the conditions to be Markovian if the original task is
Markovian. Thus, the DCOB does not affect the convergenceof RL algorithms.
However, it is known that in many robotics applicationsof RL, the generalization of a function approximator isnecessary but it affects Markovian (e.g. [21]). Though thisproblem occurs in both the DCOB and the general RL cases,
we have to design the DCOB not to impose the Markov
property any more. To do this, let us consider the boundary
conditions (BCs) used to determine the coefficients of thereference trajectory (eq. (6)). There are some candidates of
the BCs other than eq. (7), such as using q̇d (0) = Cd (x(0))
instead of q̈d (Tf ) = 0. However, if the reference trajectorywere determined with the current velocity Cd (x(0)), thetrajectory would be so sensitive about Cd (x(0)) that anaction value function would become complex. In such case,
the Markov property might be affected. In most situationsof our preliminary experiments, eq. (7) resulted in a better
convergence and a discounted return compared to the otherBCs. These results are possible because the eq. (7) BCs
prevents to affect the Markov property unlike the other BCs.

B. Computational Cost
The Generating step and the Following step do not requirea large computational cost. On the other hand, the Abbreviating step requires O(|K|2 ) to calculate dn . However, dn canbe calculated before learning, since the parameters of the BFs
do not change during learning. Thus, the computational costof the Abbreviating step is reduced to O(|K|). Evaluating
the action value function also requires O(|K|), therefore, the
DCOB does not increase the computational cost substantially.
V. E XPERIMENTAL C OMPARISON ON ROBOTNAVIGATION TASK
We evaluate the proposed action set, DCOB, in a small
dimensional task where a conventional discrete action set
works well. Concretely, we apply it to a very simple navigation task on a 2-dimensional plane.
We begin RL from scratch (θa = 0 for all a) in every
experiments. As an RL algorithm, we use Peng’s Q(λ)learning [22] with γ = 0.99, λ = 0.9, and a decreasing
step size parameter α = 0.7 exp(−0.002Neps ). For exploring
actions, we use the Boltzmann policy selection with adecreasing temperature τ = exp(−0.005Neps ). Neps denotes
the number of episodes. These parameters and coefficientsare chosen through preliminary experiments.
A. Experimental Setup
We employ an omniwheel mobile robot that can movein any direction on a 2-dimensional plane (x1 , x2 ),x1 , x2 ∈[−1, 1] (Fig. 2). The state of the robot can be
expressed as x = (x1 , x2 )> , and its control input u =(∆x1 , ∆x2 )> is the state transition in a time step δt = 0.01.
In this environment, there is some wind that changes the
behavior of the robot in the direction of the arrows shown in
Fig. 2. There are also walls which the robot can not cross but
is allowed to move along. The dynamics of the environmentis calculated as follows:
Input:current state x, control input u
Output:next state x0uumax
if kuk > umax then u ← kuk
apply wind: ∆x ← u + wind (x)apply walls:
if for a wall ∈Wall , the line segment (wall .p1 , wall .p2 ) andthe line segment (x, x+∆x) are crossing (see Fig. 3) thenwall.p1 −wall.p2
uwall ← kwall.p
1 −wall.p2 k∆x ← (u>wall ∆x)uwall
if for the other wall 0 ∈Wall \{wall }, the line segment(wall 0 .p1 , wall 0 .p2 ) and the line segment (x, x+∆x) arealso crossing then ∆x ← 0
end ifreturn next state: x0 ← x + ∆x

where umax = 0.03 denotes the maximum norm of an input.
wind (x) denotes the effect of the wind at x, specifically,(kxk < ρw1 ) 0x
w(ρw1 6 kxk < ρw2 )1
wind (x) =
(16)
 kxk
x
w
(ρ
6
kxk)
2
w2
kxk

Fig. 2.

The map of the robot navigation task.

Fig. 3. If the robot action, i.e. the line segment (x, x+∆x), and the wall
are crossing, the robot action is changed to move along the wall.

where w1 = 0.01, w2 = 0.08, ρw1 = 0.5, ρw2 = 1.0.
wall ∈Wall denotes a wall whose elements are the start point
wall .p1 and the end point wall .p2 .
The objective of the navigation task is to acquire a pathwith which the robot can move from the start to the goal as
shown in Fig. 2. We design the reward function according
to this objective as:r(t) = rg (t) − rsc (t) − ros (t)(17)

reward for goal:{

1 − 0max rg (t0 )(kxg − x0 k < ρg )0(otherwise)t ∈[0,t)rg (t) =(18)

step cost:rsc (t) = 25ku(t)k2 δt(19)

penalty for going out of the plane:{ros (t) =0.5 − 0max ros (t0 )(x0 ∈/ Xpl )

0(otherwise)t ∈[0,t)(20)

where x0 =x(t+δt), Xpl ={(x1 , x2 )|x1 ∈[−1, 1], x2 ∈[−1, 1]}.
xg denotes the goal state, and ρg = 0.15 denotes the radiusof the goal. Note that the reward r(t) is not designed for eachaction, but designed for time t in order to compare different
action sets evenly, since they have different intervals. In thiscase, the reward for an action is calculated in the samemanner as eq. (15). The purpose ∫of the maxt0 . . . componentt +T
in the definition of rg (t) is to set t0n=tn nn rg (t0 )dt0 = 1 if theagent goaled in the n-th action; the definition of ros (t) is thesame. Each episode begins with the start state x(0) = xs ,and ends if the robot has reached the goal, gone outside(x0 ∈/ Xpl ), or t > 12.

We use NGnet with 64 BFs allocated as shown in Fig.
2 to approximate the action value function. These BFs areallocated on a 8 × 8 grid with added random noise to eachcenter and covariance.
B. Action Set Configurations
In order to apply the DCOB, let Cp , Cd , Ctrl , and I as
follows:
Cp (x) = x = (x1 , x2 )>

(21)

>

Cd (x) = (0, 0)(22)
Ctrl (x(ta ), qd (ta + δt)) = qd (ta + δt) − Cp (x(ta )) (23)I = {0.3δCp (x, µk )}(24)

where δCp (x, µk ) is defined in eq. (4). The size of the action
set is |A| = |K||I| = 64.
We compare the DCOB with a very simple action set thatare often used in RL applications (e.g. [9]). For the robot
navigation task, we define a “Radial Action Set” AR where
actions are constructed to move radially from the current
state. Specifically,∆ϕ = 2π/Ndir
AR = {dir a | dir a = (− sin(a∆ϕ), cos(a∆ϕ))> ,a = 0, . . . , Ndir − 1}(25)

where Ndir denotes the number of directions. Each actiona∈AR is executed as follows:u(ta ) = umax dir a ,ta ∈ [0, TR )(26)

where TR denotes the interval of the action. We choose
TR = 0.1 that have given the best performance in preliminary
experiments.
C. Results
We compared the DCOB A and the radial action set ARof Ndir = 3, 4, 6, 8, 16, 32, 64. Fig. 4 shows the resulting
learning curves (the mean of the return per episode over
25 runs). The radial action set AR has a tendency that thelearning speed decreases with increasing Ndir . However, thelearning speed of the DCOB is faster than every AR , in spite
of |A| = 64. It is considered to be a main factor that with the
DCOB, the robot has few actions to go out of the plane Xpl
since there are few BFs allocated out of Xpl . As a result, therobot with the DCOB has learned to get to the goal fasterthan the robot with the other action set.
VI. E XPERIMENTAL C OMPARISON ON M OTION
L EARNING OF M ULTI -L INK ROBOT
Next, we evaluate the proposed action set, DCOB, in
motion learning of a multi-link robot that has higher state
and action space dimensionality. The following experiments
are performed on a dynamics simulator, ODE1 .
We begin RL from scratch (θa = 0 for all a) in every
experiments. As an RL algorithm, we also use Peng’s Q(λ)learning [22] with γ = 0.9, λ = 0.9, and a decreasing step
1 Open Dynamics Engine: http://www.ode.org/

Fig. 4. Resulted learning curves of the robot navigation task. Each curveshows the mean of the return per episode over 25 runs. R? denotes AR of
Ndir = ?.

size parameter α = α0 exp(−δα Neps ). For exploring actions,
we use the Boltzmann policy selection with a decreasing
temperature τ = τ0 exp(−δτ Neps ). Neps denotes a numberof episodes. In following experiments, we set α0 = 0.7,
δα = 0.002, τ0 = 5, δτ = 0.004 for the crawling task, and
α0 = 0.7, δα = 0.0001, τ0 = 15, δτ = 0.001 for the jumpingtask.
A. Robotic System
The robot we use is a humanoid robot whose DoF is
constrained to five as shown in Fig. 5. The state and the
input spaces have large dimensionality for RL. Specifically,
the state space X is 21-dimensional and the input space U
is 5-dimensional as defined as follows:x = (c0z , qw , qx , qy , qz , q1 , q2 , q3 , q4 , q5 ,ċ0x , ċ0y , ċ0z , ωx , ωy , ωz , q˙1 , q˙2 , q˙3 , q˙4 , q˙5 )>>

u = (u1 , u2 , u3 , u4 , u5 )

(27)
(28)

where (c0x , c0y , c0z ) denotes the position of the center-ofmass of the body link, (qw , qx , qy , qz ) denotes the rotationof the body link in quaternion, (ωx , ωy , ωz ) denotes therotational velocity of the body link, qj (j=1, .., 5) denotes
the joint angles, uj (j=1, .., 5) denotes the joint torques. The
reason for the absence of c0x and c0y from the state x in eq.
(27) is that the agent should be able to learn the following
tasks (crawling and jumping tasks) without them. The joint
torque is limited to |uj | 6 umax = 2.06[Nm] for j = 1, .., 5.
The simulations are performed with a time step δt = 0.2[ms].
B. Basis Functions
Even if we allocate only 3 BFs per dimension on thestate space, 321 ≈ 1010 BFs are used which is obviously
unrealistic. In order to deal with this problem, we generate
the BFs so that the function approximator can estimate thedynamics of the robot. Specifically, first, we train a NGnetwith a sequential data sampled from random motions by
the EM algorithm [12]. After that, we execute RL with theobtained BFs to approximate a value function. More BFs
may be allocated in state where the dynamics is highly
nonlinear, while fewer in state where the dynamics is nearlyFig. 5.

Humanoid robot whose DoF is constrained to five.
Fig. 6. Resulted learning curves of the crawling task. Each curve shows themean of the return per episode over 10 runs. GRID3, 5 denotes Ngrid = 3, 5
respectively.

linear. Generally, high nonlinearity requires a complex controller, namely, a complex action value function. Therefore,
generating the BFs from training the dynamics enables thefunction approximator to estimate a value function precisely
with fewer BFs. This method is proposed by Yamaguchi etal. [16] based on the idea of MOSAIC [23], [24].
For our robot, we initially prepared 200 BFs for a NGnet,
and trained by the off-line EM algorithm with unit manipulations used in [12]. Finally, we obtained 202 BFs.

possible. According to this objective, we design the reward
function as follows:r(t) = rmv (t) − rse (t) − rsc (t) − rfd (t)rmv (t) = 0.01ċ0x (t)C. Action Set Configurations

Cp (x) = (q1 , q2 , q3 , q4 , q5 )(29)

Cd (x) = (q˙1 , q˙2 , q˙3 , q˙4 , q˙5 )>(30)

Ctrl (x(ta ), qd (ta + δt))
= Kp {qd (ta +δt) − Cp (x(ta ))} − Kd Cd (x(ta )) (31)I = {gi δCp (x, µk ) | gi = 0.075, 0.1, 0.2}

rse (t) = 0.1{c0y (t)}2(38)

step cost:rsc (t) = 0.1ku(t)kδt(39)

penalty for falling down:{

rfd (t) =4 − 0 max rfd (t0 )(falling down)

0(otherwise)t ∈[tn ,t)

(40)

(32)

where Kp = 5.0, Kd = 1.6, and δCp (x, µk ) is defined ineq. (4). The size of the action set is |A| = |K||I| = 606.
As a comparison, we employ a “Grid Action Set” AGdefined as follows:{
AG = ∆q | ∆q = (δq1 , δq2 , δq3 , δq4 , δq5 )> ,}N−1
δq1,2,3,4,5 ∈ {0, ±∆ϕ, . . . , ± grid
∆ϕ}
(33)
2
where ∆ϕ = π/12, and Ngrid denotes the number of division5, becomes too largeof the grid. The size of AG , |AG | = Ngrid
for Ngrid > 7, so we use Ngrid = 3 and 5 in the following
experiments. Each action ∆q ∈ AG is executed as
qd = Cp (x(0)) + ∆qu(ta ) = Kp {qd − Cp (x(ta ))} − Kd Cd (x(ta ))(37)

penalty for simulation error:

In order to apply the DCOB, let Cp , Cd , Ctrl , and I as
follows:>(36)

reward for moving:

(34)
(35)

where ta ∈ [0, TG ). TG = 0.1[s] denotes the interval of theaction.
D. Crawling Task
First, we apply the RL to acquire a crawling motion whose
objective is to move forward along the x-axis as far as

where the falling down of the robot is defined as the bodylink or the head link touching the ground. rse (t) is usuallyzero, but has a value for simulation error. Similar to thenavigation task, these rewards are designed for time t tocompare different action sets evenly, where the reward for an
action is calculated by eq. (15). The purpose of the maxt0 . . .
component of rfd (t) is to prevent it from becoming a hugevalue. Each episode begins with the initial state where therobotup (Fig. 5 left) and stationary, and ends if∫ t 0is standing
0
r(t
)dt
6
−40
or t > 20[s].
0Fig. 6 shows the learning curves (the mean of the return
per episode over 10 runs) resulted from applying RL with theaction set A and AG of Ngrid = 3, 5. The learning speedof AG of Ngrid = 3 is as fast as, or slightly faster thanthe DCOB. This is because |AG | = 243 is smaller than|A| = 606. However, the performance of the acquired motion
with the DCOB is obviously better than AG . The DCOB is
considered to provide a better action set for the robot motion
by constructing from the BFs. AG of Ngrid = 5 is inferiorboth in the learning speed and the acquired performance. Fig.
7 shows the acquired crawling motion with the DCOB (seealso the accompanying video).

Fig. 7.

Sequence of the acquired crawling motion with the DCOB.

E. Jumping Task
Next, we apply the RL to acquire a more difficult motion,
jumping. The objective is to jump as high as possible without
falling down. According to this objective, we design the
reward function as follows:r(t) = rjp (t) − rsc (t) − rfd (t)(41)

reward for jumping:{rjp (t) =0100c1z (t)δt(not jumping)(otherwise)(42)

where c1z denotes the z-position of the head link, i.e. theheight of the head, rsc (t) and rfd (t) are the same definition
as eq. (39) and (40) respectively. The not jumping condition
is defined as when the feet are touching the ground, ċ1z (t) <0, or c1z (t) < 0.75c1z (0). Each episode begins with theinitial state where the robot is standing up (Fig. 5 left) andstationary, and ends if one of the following is satisfied:∫t(1) 0 rfd (t0 )dt0 > 0,∫t(2) feet are touching the ground, 0 rjp (t0 )dt0 > 0, andthe robot is stationary,(3) t > 5[s].
The robot is judged stationary if every velocity element of
the state is less than 1[m/s] or 1[rad/s].
Fig. 8 shows the learning curves resulted from applying
RL with the action sets A and AG . The learning speed of
AG of Ngrid = 3 also looks faster than the others. However,its acquired performance is the worst. AG of Ngrid = 3 isconsidered not to have sufficient actions to perform jumping,while the DCOB also seems to provide a suitable action set.
Fig. 9 shows the acquired jumping motion with the DCOB
(see also the accompanying video).
VII. R ELATION TO OTHER W ORKS
A. Options
Sutton et al. proposed the options which are generalized
actions of primitive and macro actions under the RL framework [25]. Our DCOB can be regarded as a kind of theoptions specialized for robot control. There is some research
about finding options or subgoals automatically [26], [27],[28], but the discovery of the optimal options is still a open
problem. The DCOB is a practical solution to it.

Fig. 8. Resulted learning curves of the jumping task. Each curve shows themean of the return per episode over 10 runs. GRID3, 5 denotes Ngrid = 3, 5
respectively.

Fig. 9.

Snapshots of the acquired jumping motion with the DCOB.

B. Compatibility with the other BFs
In this paper, we used the DCOB only with the Normalized
Gaussian Network (NGnet). However, we can also use the
DCOB with the other BFs if they satisfies the assumptions
mentioned in section III, that is, each BF has a fixed centerin the state space. For instance, Takahashi et al. uses akind of function approximators that has a center in the state
space (they call a representative state vector) [29]. Using
the DCOB with their function approximator requires slight
modifications, such as defining dmin k0 in eq. (9).
VIII. C ONCLUSIONS AND F UTURE W ORK
In this paper, we proposed a compact action set, DCOB,
for RL that are constructed from the basis functions (BFs)
for approximating a value function. This method can exploit
the function approximator’s nature, that is, the number ofthe BFs does not increase exponentially with the dimension

of the state space. The DCOB also has a remarkable featurethat a robot does not take actions that exceed its limitations if
the BFs are not allocated out of the limitations. For instance,
the robot tends to avoid exceeding the joint limits. The
simulation results demonstrate that the DCOB is superior toconventional discrete action sets both on the learning speed
and the acquired performance.
The DCOB requires some assumptions, namely, a BF
has a fixed center in the state space and Cp , Cd , Ctrl aredefined (see section III). These assumptions may restrict theother applications of the DCOB. Especially, some researchers
proposed to improve the BFs (e.g. [2], [5]), that is, a center ofa BF is changed in the RL process. If the center were changedin the learning, convergence would not be guaranteed (seesection IV).
In the near future, we apply our results to real robots andinvestigate its validity. We also apply DCOB to other tasks,
such as a standing up motion [2]. Moreover, we will checkthe compatibility with the Dyna framework [1], and compare
it with a continuous action set, such as wire-fitting [13], inhigher dimensional tasks.
R EFERENCES[1] R. S. Sutton, C. Szepesvári, A. Geramifard, and M. Bowling, “Dynastyle planning with linear function approximation and prioritizedsweeping,” in Proceedings of the 24th Conference on Uncertainty in
Artificial Intelligence, 2008.
[2] J. Morimoto and K. Doya, “Reinforcement learning of dynamic
motor sequence: Learning to stand up,” in the IEEE/RSJ International
Conference on Intelligent Robots and Systems (IROS’98), 1998, pp.
1721–1726.
[3] H. Kimura, T. Yamashita, and S. Kobayashi, “Reinforcement learningof walking behavior for a four-legged robot,” in Proceedings of the40th IEEE Conference on Decision and Control, 2001.
[4] T. Matsubara, J. Morimoto, J. Nakanishi, S.-H. Hyon, J. G. Hale,and G. Cheng, “Learning to acquire whole-body humanoid CoM
movements to achieve dynamic tasks,” in the IEEE Internactional
Conference in Robotics and Automation (ICRA’07), 2007, pp. 2688–
2693.
[5] T. Kondo and K. Ito, “A reinforcement learning with evolutionary state
recruitment strategy for autonomous mobile robots control,” Robotics
and Autonomous Systems, vol. 46, no. 2, pp. 111–124, 2004.
[6] C. Gaskett, L. Fletcher, and A. Zelinsky, “Reinforcement learning for avision based mobile robot,” in the IEEE/RSJ International Conferenceon Intelligent Robots and Systems (IROS’00), 2000. [Online].
Available: citeseer.ist.psu.edu/article/gaskett00reinforcement.html[7] J. Zhang and B. Rössler, “Self-valuing learning and generalization withapplication in visually guided grasping of complex objects,” Robotics
and Autonomous Systems, vol. 47, no. 2-3, pp. 117–127, 2004.
[8] E. Uchibe and K. Doya, “Competitive-cooperative-concurrent reinforcement learning with importance sampling,” in In Proc. of International Conference on Simulation of Adaptive Behavior: From Animals
and Animats, 2004, pp. 287–296.
[9] Y. Takahashi and M. Asada, “Multi-layered learning systems forvision-based behavior acquisition of a real mobile robot,” in Proceedings of SICE Annual Conference 2003, 2003, pp. 2937–2942.
[10] C. K. Tham and R. W. Prager, “A modular q-learning architecture
for manipulator task decomposition,” in the Eleventh International
Conference on Machine Learning, 1994, pp. 309–317. [Online].
Available: citeseer.ist.psu.edu/article/tham94modular.html[11] F. Kirchner, “Q-learning of complex behaviours on a six-legged
walking machine,” Robotics and Autonomous Systems, vol. 25, no.
3-4, pp. 253–262, 1998.
[12] M. Sato and S. Ishii, “On-line EM algorithm for the normalized
gaussian network,” Neural Computation, vol. 12, no. 2, pp. 407–432,
2000. [Online]. Available: citeseer.ist.psu.edu/sato99line.html[13] L. C. Baird and A. H. Klopf, “Reinforcement learning withhigh-dimensional, continuous actions,” Wright Laboratory, WrightPatterson Air Force Base, Tech. Rep. WL-TR-93-1147, 1993.
[Online]. Available: citeseer.ist.psu.edu/baird93reinforcement.html[14] J. Zhang and A. Knoll, “Constructing fuzzy controllers with Bspline models–principles and applications,” International Journal ofIntelligent Systems, vol. 13, no. 2/3, pp. 257–286, 1998.
[15] H. Miyamoto, J. Morimoto, K. Doya, and M. Kawato, “Reinforcement
learning with via-point representation,” Neural Networks, vol. 17,
no. 3, pp. 299–305, 2004.
[16] A. Yamaguchi, N. Sugimoto, and M. Kawato, “Reinforcement learningwith reusing mechanism of avoidance actions and its application tolearning whole-body motions of multi-link robot,” Journal of the
Robotics Society of Japan, 2009, (in Japanese, in press).
[17] C. J. C. H. Watkins, “Learning from delayed rewards,” Ph.D. dissertation, Cambridge University, 1989.
[18] G. A. Rummery and M. Niranjan, “On-line Q-learning
using connectionist systems,” Cambridge University Engineering
Department, Tech. Rep. CUED/F-INFENG/TR 166, 1994. [Online].
Available: citeseer.ist.psu.edu/rummery94line.html[19] J. N. Tsitsiklis and B. V. Roy, “Feature-based methods for large scale
dynamic programming,” Machine Learning, vol. 22, pp. 59–94, 1996.
[20] ——, “An analysis of temporal-difference learning with function
approximation,” IEEE Transactions on Automatic Control,
vol. 42, no. 5, pp. 674–690, 1997. [Online]. Available:
citeseer.ist.psu.edu/article/tsitsiklis96analysis.html[21] H. Kimura, K. Miyazaki, and S. Kobayashi, “Reinforcement learningin pomdps with function approximation,” in ICML ’97: Proceedings ofthe Fourteenth International Conference on Machine Learning. San
Francisco, CA, USA: Morgan Kaufmann Publishers Inc., 1997, pp.
152–160.
[22] J. Peng and R. J. Williams, “Incremental multi-step Q-learning,” in International Conference on Machine Learning, 1994, pp. 226–232. [Online]. Available: citeseer.ist.psu.edu/article/peng96incremental.html[23] K. Doya, K. Samejima, K. Katagiri, and M. Kawato, “Multiple modelbased reinforcement learning,” Neural Computation, vol. 14, no. 6, pp.
1347–1369, 2002.
[24] D. M. Wolpert and M. Kawato, “Multiple paired forward and inverse
models for motor control,” Neural Networks, vol. 11, no. 7-8, pp.
1317–1329, 1998.
[25] R. S. Sutton, D. Precup, and S. Singh, “Between mdps and semi-mdps:
A framework for temporal abstraction in reinforcement learning,”
Artificial Intelligence, vol. 112, pp. 181–211, 1999.
[26] A. Mcgovern and A. G. Barto, “Automatic discovery of subgoals in
reinforcement learning using diverse density,” in In Proceedings of theeighteenth international conference on machine learning. Morgan
Kaufmann, 2001, pp. 361–368.
[27] I. Menache, S. Mannor, and N. Shimkin, “Q-cut - dynamic discovery
of sub-goals in reinforcement learning,” in ECML ’02: Proceedings ofthe 13th European Conference on Machine Learning. London, UK:
Springer-Verlag, 2002, pp. 295–306.
[28] M. Stolle, “Automated discovery of options in reinforcement
learning,” Master’s thesis, McGill University, February 2004.
[Online]. Available: http://www.cs.cmu.edu/ mstoll/publications.shtml[29] Y. Takahashi, M. Takeda, and M. Asada, “Continuous valued qlearning for vision-guided behavior acquisition,” in the IEEE/RSJ
International Conference on Intelligent Robots and Systems (IROS’99),
1999.