Trans. of the Society of Instrument
and Control Engineers
Vol.E-4, No.1, 1/9 (2007)

An Actor-Critic Algorithm using a Binary Tree Action Selector
Reinforcement Learning to Cope with Enormous Actions
Hajime Kimura∗ and Shigenobu Kobayashi∗∗In real world applications, learning algorithms often have to handle several dozens of actions, which have somedistance metrics. Epsilon-greedy or Boltzmann distribution exploration strategies, which have been applied for
Q-learning or SARSA, are very popular, simple and eﬀective in the problems that have a few actions, however, theeﬃciency would decrease when the number of actions is increased. We propose a policy function representationthat consists of a stochastic binary decision tree, and we apply it to an actor-critic algorithm for the problems
that have enormous similar actions. Simulation results show the increase of the actions does not aﬀect learning
curves of the proposed method at all.
Key Words: reinforcement learning, actor-critic, action selector, binary tree, exploration strategy

1.

chical action selection scheme for the problems that have

Introduction

enormous similar actions is proposed. It adopts a pol-Reinforcement learning (RL) is a promising approachicy function representation that consists of a stochastic

for robots to improve the behavior themselves or make upbinary decision tree, and updates the policy parameters

for lack of knowledge about the tasks 4) . Learning control

by an actor-critic algorithm 1) 5) 8) . The knowledge of thein real world applications requires dealing with both con-order of the action groups is easily embedded in the tree

tinuous state and several dozens or more of actions. There

structure of the decision making by designers in advance.

are many works about the generalization techniques to

Simulation results show the increase of the actions does8)

not aﬀect learning curves of the proposed method at allis one of linear architectures, and the others are neural-when the action space is assumed to have some good dis-

approximate value functions over state space; CMAC
3)

2)

networks, Fuzzy methods , instance-based methods ,tance metric.

etc. To deal with dozens of actions, not only the tech-2.

Problem Formulationniques of action value approximation but also exploration
strategies are essential. Q-learning or SARSA algorithms

2. 1

with -greedy or softmax action selection rules are very

Let S denote state space, A be action space, R be a

popular, simple and eﬀective in the problems which haveset of real number. At each discrete time t, the agent

a few actions. However, in these ﬂat selection methods,

observes state st ∈ S, selects action at ∈ A, and thenthe eﬃciency would decrease when the number of actions

receives an instantaneous reward rt ∈ R resulting fromis increased.

state transition in the environment. In general, the re-

You know, for example in our daily life, when we op-

Markov Decision Processes

ward and the next state may be random, but their proba-

erate a handle, we will choose ’turn right’ or ’turn left’bility distributions are assumed to depend only on st andat ﬁrst, and there after we will select the amount of theat in Markov decision processes (MDPs), in which many

operation, ’small’, ’medium’ or ’large’. Thus, hierarchicalreinforcement learning algorithms are studied. In MDPs,

decision making is more eﬀective than ﬂat action selection

the next state st+1 is chosen according to the transition

when there exisis many similar actions. In this example,

probability T (st , a, st+1 ), and the reward rt is given ran-

we group ’small turn left’, ’medium turn left’ and ’large

domly according to the expectation r(st , a). The agent

turn left’ into a higher hierarchical action ’turn left’ un-does not know T (st , a, st+1 ) and r(st , a) ahead of time.

consciously. In many real-world applications, the actions

The objective of reinforcement learning is to construct a

can be grouped and ranked in the same way. In this pa-

policy that maximizes the agent’s performance. A natu-

per, a reinforcement lerarning approach that uses hierar-

ral performance measure for inﬁnite horizon tasks is the∗

Graduate School of Eng. Kyushu University∗∗ Interdisciplinary Graduate School of Sci. and Eng. Tokyo
Institute of Technology

cumulative discounted reward:
Vt =

∞

k

γ rt+k ,

k=0

(1)

2

T. SICE Vol.E-4 No.1 2007

where the discount factor, 0 ≤ γ ≤ 1 speciﬁes the impor-Agenttance of future rewards, and Vt is the value at time t. In

stMDPs, the value can be deﬁned as: ∞ t 
πγ rt  s0 = s, π ,V (s) = E

t=0

-

at

Actor
stochastic policy π

6 reinforcement for at(2)

rt + γ V̂ (st+1 ) − V̂ (st )stwhere E{·} denotes the expectation. The objective in-

CriticV̂ (s)



MDPs is to ﬁnd an optimal policy that maximizes thevalue of each state s deﬁned by Equation 2.
2. 2

Observation

MDPs with Enormous Similar Actions

RewardTD-errorrt
Action?

Environment
Fig. 2 A standard actor-critic architecture.

a7
a3

a0

a0
a6

a1

a5
a2

a2

a1
a4

a3

4 actions

8 actionsa15 a0
a14
a1
a13
a2

a0

a12

a3

a11

Actor-Critic Method for binary-tree
action selector

Almost traditional value-based methods such as Qa24
a8

a4

a10
a9

3.

a5
a6
a8 a7

a16

16 actions

32 actions

learning or SARSA are dealing with the problems shownin Section 2. 2 by generalization techniques over the action
space. But such value-based methods work poor in nonMarkovian environments, and it needs enormous number

Fig. 1 A modiﬁed puddle-world problem. There are 4, 8, 16,
32, or 64 actions, which moves approximately 0.05 inthese directions. The state space is continuous andtwo-dimensional, which is bounded by [0, 1] for eachdimension.

of iteration for estimating the state-action value. On theother hand, actor-critic algorithms are robust against nonMarkovian environments, and its policy improvement ismuch faster. However, the actor-critic methods does nothave any scheme for dealing with many similar actions

Many real world applications would have a feature thatshown in Section 2. 2 making use of such problem’s prop-

neighboring actions will almost result in similar state

erty. We propose a new action selection scheme for thetransitions. Fig. 1 illustrates the example using a puddle-

actor-critic methods.

world task

7)

but it is slightly modiﬁed from the origi-

nal formulation. The state space is continuous and two-

3. 1

Actor-Critic Algorithm

As shown in Fig. 2, the actor-critic algorithm is com-dimensional, which is bounded by [0, 1] for each dimen-

posed of two modules; One is actor that selects action, andsion. When the agent selects an action, the agent moves

the other is critic that evaluates states. The actor imple-

approximately 0.05 in that direction unless the movement

ments a stochastic policy that maps from a representation

would cause the agent to leave the limits of the space. A

of a state to a probability distribution over actions. The

random Gaussian noise with standard deviation 0.01 wascritic attempts to estimate the evaluation function V̂ (s)added to the motion along both dimensions. Obviously,

for the current policy. After each action selection, thethe more actions increase (especially in 32 or 64 actions),

critic evaluates the new state to determine whether things

the more similar state transitions occur. The details of

have gone better or worse than expected. The evaluation

the puddle world are as below. The rewards on this task

is known as temporal diﬀerence (TD), and it is used towere −1 for each time step plus additional penalties if ei-

evaluate the action just selected as an eﬀective reinforce-ther or both of the two oval puddles were entered. These

ment. When the TD is positive, then the executed action

penalties were −400 times the distance into the puddle

would be good, therefore the probability of choosing that(distance to the nearest edge).

The puddles were 0.1

action is increased. Contrary, when the TD is negative,in radius and were located at center points (0.1, 0.75) tothen the action would be bad, and the probability of that

(0.45, 0.75) and (0.45, 0.4) to (0.45, 0.8). The initial state

action is decreased.

of each episode was selected randomly uniformly from thenon-goal states.

Fig. 3 speciﬁes an actor-critic algorithm we used 5) . It
is noteworthy that both the actor and the critic adopt el-

3

T. SICE Vol.E-4 No.1 2007(1) Observe state st , choose action at with probability π(at , θ, st ) in the actor, and perform it.
(2) Observe immediate reward rt , resulting statest+1 , and calculate the TD-error according to

tor in this paper. The actor’s learning rule is shown in
Step 4 and 5 in Fig. 3. The eligibility eπ is the same
variable deﬁned in REINFORCE algorithms 12) . The parameter λπ speciﬁes the actor’s eligibility trace, but its(3)

features are somewhat diﬀerent from TD(λ)’s. When λπwhere 0 ≤ γ ≤ 1 is the discount factor, V̂ (s) is an
estimated value function by the critic.
(3) Update the estimating value function V̂ (s) inthe critic according to the TD(λ) method as follows:

is close to 0, the policy would be updated according to the(TD-error) = rt + γ V̂ (st+1 ) − V̂ (st ) ,gradient of the estimated value function V̂ , and when λπ
is close to 1, the policy would be updated by the gradientof the actual return, deﬁned by Equation 1 5) .
3. 2 Binary-Tree Action Selector∂V̂ (st ) ,∂w
ev (t) ← ev (t) + ev (t) ,ev (t) =

Δw(t) = (TD-error) ev (t) ,




* a1
1 


f2 H
1
H
0 H
j a2
 

w ← w + αv Δw(t) ,where ev denotes the eligibility of the parameter w in
the function approximator V̂ (s), ev is its trace, and αv
is a learning rate.
(4) Update the actor’s stochastic policy accordingto∂eπ (t) =ln π(at , θ, st ) ,∂θP (a1 ) = f1 f2
P (a2 ) = f1 (1 − f2 )f1

@ 0 

* a3
1 
@
@ f3 
H
HH

0 j a4eπ (t) ← eπ (t) + eπ (t) ,P (a3 ) = (1 − f1 ) f3
P (a4 )= (1 − f1 )(1 − f3 )Δθ(t) = (TD-error) eπ (t) ,θ ← θ + απ Δθ(t) ,where eπ is the eligibility of the policy parameter θ, eπ
is its trace, and απ is a learning rate.
(5) Discount the eligibility traces as follows:
ev (t + 1) ← γ λv ev (t) ,eπ (t + 1) ← γ λπ eπ (t) ,where λv and λπ (0 ≤ λv , λπ ≤ 1) are discount factors
in the critic and the actor respectively.
(6) Let t ← t + 1, and go to step 1.

(1) Start at the root of the tree, choose the branch
1 with probability f1 (or the branch 0 with probability
1 − f1 ).
(2) At the selected branch node, continue the sameprocess until a leaf is encountered. If the node f2 isselected, choose 1 with probability f2 (or 0 with probability 1 − f2 ). If the selected node is f3 , then choose
1 with probability f3 , etc. And take the corresponding
branch.
(3) At the resulting leaf node, execute the corresponding action a.
(4) Calculate eligibilities for all nodes by∂ln π(a, θ, s) =∂fj

Fig. 3 An actor-critic algorithm making use of eligibility
traces in both the actor and the critic.

yj −fjfj (1−fj )if fj is active0otherwise,

where yj ∈ {0, 1} is the outcome of the node fj .

igibility traces; obviously TD(λ) in the critic refers to useit, and the actor uses eligibility traces on policy parameters. The calculation scheme of the TD(λ) in the critic
is described in Step 3 and 5 in Fig. 3. The parameter λv

Fig. 4 A binary-tree action selection scheme for four actions,and its policy representation. fi denotes a probability
distribution function.

speciﬁes the eligibility trace of the TD(λ = λv ). In the actor, the policy is explicitly represented by its own function

Here we propose a new technique for policy gradientapproximator, and updated according to the gradient ofmethods to cope with enormous similar actions. Fig. 4

value function with respect to the policy parameters 5) 9) .

illustrates the binary-tree action selector for four actions.

Let π(a, θ, s) denote probability of selecting action a underThe stochastic policy is represented by a binary decision

the policy π in the state s. That is, the policy is repre-

tree. Leaves of the decision tree are primitive actions, andsented by a parametric function approximator using thethe other nodes branch to two ways following the corre-internal parameter vector θ. The agent can improve thesponding probability fi . Formally, the policy function ispolicy π by modifying the parameter θ. For example, θgiven bycorresponds to synaptic weights where the action selecting
probability is represented by neural networks, or θ means
weight of rules in classiﬁer systems. The form of the function π(a, θ, s) is speciﬁed for the binary-tree action selec-

π(a, θ, s) =⎧⎪⎪ f1 f2⎪⎨ f (1 − f )a = a1⎪(1 − f1 ) f3⎪⎪⎩

a = a3

1

2(1 − f1 ) (1 − f3 )a = a2a = a4(4)

4

T. SICE Vol.E-4 No.1 2007

Then the eligibility for f1 is given by

⎧
1/f1
⎪
⎪
⎪
⎨

In this case, the gradient-descent TD(λ) algorithm has a

1/f1∂ln π(a, θ, s) =∂f1⎪
⎪ −1/(1 − f1 )a = a2−1/(1 − f1 )a = a4⎪⎩=

sound convergence property 10) . The eligibility evi of thea = a1parameter wi is given by (∂ V̂ (s))/(∂wi ) = xi .
Using the feature vector, the branching probability fj

a = a3y1 − f1,
f1 (1 − f1 )in each node is given by
(5)

fj =

1

1 + exp(−

nθji xi )

i=1

,

(8)

where y1 ∈ {0, 1} denotes the outcome of the unit f1 .

where θji denotes policy parameters. The fj is monotone

Similarly, the eligibility for f2 (or f3 ) is given byincreasing function, and 0 < fj < 1. From Equation 5, 6

⎧
1/f2
⎪
⎪
⎪
⎨

−1/(1 − f2 )∂ln π(a, θ, s) =
∂f2
⎪
⎪ 0

⎪
⎩

=

a = a1and 8, ∂fj /∂θji = xi fj (1 − fj ), then the eligibility eπji ofa = a2

θji is given bya = a3eπji =

a = a40
y2 −f2
f2 (1−f2 )if f2 is active0otherwise.

(6)

=

∂fj ∂
ln π(a, θ, s)∂θji ∂fj(yj − fj )xi

if fj is active0otherwise.

(9)This result says that the calculation of the eligibility atwhere yj ∈ {0, 1} denotes the selected branch (0 or 1) ineach node is the same and can be done by only local infor-

the node fj .

mation. The eligibility on the executed path from the rootof the tree to a leaf is simply given by (yj − fj )xi , other-

The speciﬁed scheme of the proposed algorithm for thewise 0. This property remains in diﬀerent size of the trees.

number of actions is m and the number of features is n is

The required memory size (the number of nodes) is pro-given as:portional to the number of actions minus 1 (see Fig. 5).
a1
a2
a3
a4

a1
a2
a3
a4
a5
a6

a5
a6

a7

6 actions(5 nodes)7 actions(6 nodes)

a1
a2
a3
a4
a5
a6
a7
a8

8 actions(7 nodes)(1) Initialize: Arrange parameters wi (i = 1 · · · n)in the critic, corresponding eligibility traces ev i , policy parameters θji (j = 1 · · · m − 1) in the actor, andcorresponding eligibility traces eπ ji .
(2) Generate a feature vector (x1 (t), x2 (t) · · · xn (t))
from the state input st .
(3) Action selection in the actor by the binary-tree:(a) Start at the root node j = 1.
(b) In the node fj , calculate as follows:
fj =Fig. 5 The binary trees for 6, 7 and 8 actions.

1

1 + exp(−

ni=1

θji xi (t))

Choose the branch 1 following the probability fj , oth3. 3

Actor-Critic with Binary-Tree Action selector

erwise choose the branch 0.
(c) Repeat the same calculation in the successor

This section speciﬁes the scheme of the actor-critic al-node until reaching the leaf node.

gorithm shown in Section 3. 1 using the binary-tree ac-(d) Execute action a in the resulting leaf node.

tion selector shown in Section 3. 2.

(e) Calculate the eligibility in the all node j as

A feature vector(x1 , x2 , · · · , xi , · · · , xn ) is given to the agent as the state
input s. Especially, (x1 (t), x2 (t), · · · , xi (t), · · · , xn (t)) denotes the feature vector where the time step is t. The
features must be constructed from the states in many dif-eπji (t) =(yj − fj )xi (t)if fj is active0otherwise,

where yj ∈ {0, 1} is the outcome of the unit fj .

ferent ways so that the feature vectors are linearly inde-(4) Calculate TD-error in the resulting state st+1 andpendent between the essential states. In the critic, thethe reward rt asstate value function is given by a linear function using
weight parameters wi and the features xi as:V̂ (s) =n
i=1

wi xi .

(7)

(TD-error) = rt + γ V̂ (st+1 ) − V̂ (st )= rt + γ

 n

i=1



wi xi (t + 1)

−

n

i=1

wi xi (t)5

T. SICE Vol.E-4 No.1 2007

feature, at be the selected action at t, st+1 and xi (t + 1)

(5) Update V̂ (s) in the critic:

be the resulting state and its feature, at+1 denote the se-evi (t) = xi (t) ,lected action at t + 1, then the Q-learning rule is

ev i (t) ← evi (t) + ev i (t) ,Δwat i = xi (t) rt + γ max Q(st+1 , a) − Q(st , at )Δwi (t) = (TD-error) ev i (t) ,awat i ← wat i + αΔwat i ,wi ← wi + αv Δwi (t) ,for all i ∈ {1, 2, · · · n}, and α denotes a learning rate fac-

(6) Update policy parameters in the actor:

tor. The learning rule of SARSA(λ) is given byeπ ji (t) ← eπji (t) + eπ ji (t) ,(TD-error) = rt + γQ(st+1 , at+1 ) − Q(st , at )Δθji (t) = (TD-error) eπ ji (t) ,eat i (t) = xi (t) + eat i (t)θji ← θji + απ Δθji (t) ,Δwai = eai (t) (TD-error)(7) Discount the eligibility traces:wai ← wai + αΔwai

ev i (t + 1) ← γ λv ev i (t) ,eai (t + 1) = γ λ eai (t)eπ ji (t + 1) ← γ λπ eπ ji (t) ,for all a
for all a

for all a,

for all i ∈ {1, 2, · · · n}. eai denotes eligibility traces. The(8) Increment the time step as t ← t + 1 and go to

Q-learning requires n × m variables for wi to approximate

step 2.

Q(s, a). The SARSA(λ) needs 2 × n × m variables for wi

3. 4

and its trace eai . It is noteworthy that the SARSA(λ)

Features

When the number of actions are m, the action selection

costs the memory exactly the same size as our method’s.

is executed by log2 m alternatives. The calculation for4.

the choosing action or ﬁnding eligibilities is executed only

Simulation Experimentalong the selected path in the tree structure, and also it

The purpose of this experiment is to investigate theis very simple using only local information in each node.

inﬂuence of increasing the number of actions on the al-

Such a local calculation property is quite suited for large

gorithms. We tested our algorithm on the puddle world

scale problems. The proposed method is strictly a sub-problem shown in Fig. 1, and compared it with Q-learning

5)class of the actor-critic algorithm , therefore it can avoid
inﬂuence of the non-Markovian eﬀect than Q-learning.

and SARSA(λ) algorithms. We used a tile coding method8)

to construct a feature vector from 2-dimensional state

Conventional Methods and Related Works

input as shown in Fig. 6. That feature vector includes

In conventional actor-critic methods, Boltzmann action

12 + 22 + 32 + · · · + 72 = 140 features (x1 , x2 , · · · x140 )selection scheme 8) is frequently used. The same as Sec-

from broad 1 × 1 to narrow 7 × 7 gridding tiles. Eachtion 3. 3, a n-dimensional feature vector is given to thetile corresponds with the component of the feature vec-

agent. When the number of actions is m, policy param-

tor. When a state input is given to m × m gridding tiles,

eters θji (j = 1 · · · m, i = 1 · · · n) and the corresponding

then the corresponding component takes m2 /140, and theeligibility traces eπ ji are arranged. The agent selects anothers are 0.

3. 5

action ak with the following probability:

n

exp
xθ
i=1 i kin
 .
Pr(ak |s) = m
j=1

exp

i=1

xi θjiThroughout the experiments, in our actor-critic algorithm, the discount factor γ = 1, the learning rate
(10)

The eligibility for the policy parameters are calculated in
the following 6) :eπji (t) =αv = 0.1, απ = 0.01, and λv = λπ = 0.9. In the Qlearning, the learning rate α = 0.5 and  = 0.1. In the
SARSA(λ), the learning rate α = 0.1,  = 0.1 and λ = 0.9
Figs. 7, 8, 11, 12 are the results showing inﬂuence of− Pr(aj |s) xi

if aj = ak ,(1 − Pr(aj |s)) xi

if aj = ak .

the number of actions on the binary-tree actor-critic, ﬂatactor-critic, Q-learning and SARSA(λ) respectively. In

The ﬂat-action-selecting actor-critic is achieved by replac-

each graph, ’Cost’ denotes the total cost from the starting the above with the process of the actor in Section 3. 3.

position to the goal area, and ’Trial’ denotes the num-

The Q-learning and the SARSA(λ) approximate state-

ber of trials, where one trial begins start position andnxi wai , and use -greedy

ends in the goal. Although the numbers of actions werepolicy, that is, one selects random action with probability

diﬀerent, yet the actor-critic using the binary-tree policy

, or with probability 1 − , one selects an action that has

performed very similar learning curves without any pa-

largest Q value. Let st be a state at time t, xi (t) be its

rameter tuning nor scheduling. On the other hand, theaction values as Q(s, a) =

i=1

6

T. SICE Vol.E-4 No.1 2007

x1 = 1/140

400

2 by 2 tilings
Dimension #2

Dimension #2

1 by 1 tilingx2, x3, x4, x5= 4/140 or 0350

64 actions
32 actions
16 actions
8 actions
4 actions300
Dimension #1

Dimension #1

250

Cost

Dimension #2

3 by 3 tilings
4 by 4 tilings,
5 by 5 tilings,
6 by 6 tilings,
and so on...

x6, x7,...x14=9/140 or 0

200

150

Dimension #1

100

Dimension #2

7 by 7 tilings
x91,...,x140= 49/140 or 0

50

0
0

Dimension #1

50

100

150

200

250

300

350

400

450

500

Trial

Fig. 6 A tile coding method to generate a feature vector,
which contains all features from broad to narrow
over a continuous two-dimensional state space. Anystate is in exactly one tile of each tiling. Each tileis associated with one element of the feature vector (x1 , x2 , · · · x140 ). The number 140 is come from
12 + 22 + 32 + · · · + 72 . When a state input is in somecertain tiles, the corresponding tiles are activated andtheir elements are set to some positive value (e.g., 1×1
tiling is 1/140, etc.). The other elements are set tozero.

Fig. 8 Performance on the actor-critic method using the ﬂataction selector, averaged over 100 trials. αv = 0.1,
απ = 0.01, λv = 0.9, λπ = 0.9.
a0
a25
a17

64 actions
32 actions
16 actions
8 actions
4 actions

300

a2
a23

a1

a21

a8

a20

a22

a14

a3

a18

a11

a12

a27

a31

a26
a13
a5

400

350

a4 a29 a30 a19
a7

a9
a6
a28
a16 a24 a10 a15

Fig. 9 An example which are randomly labeled actions in thepuddle world.
400

Cost

250
350

64 actions
32 actions
16 actions
8 actions
4 actions

200
300
150
250

Cost

100

200

50
150
0
0

50

100

150

200

250

300

350

400

450

500

Trial

Fig. 7 Performance on the actor-critic method using thebinary-tree action selector, averaged over 100 trials.
αv = 0.1, απ = 0.01, λv = 0.9, λπ = 0.9.

learning curves of the -greedy strategy were strongly affected with the numbers of actions on the Q-learning and
the SARSA. Fig. 10 shows the performance of the actor-

100

50

0
0

50

100

150

200

250

300

350

400

450

500

Trial

Fig. 10 Performance on the actor-critic method using thebinary-tree action selector in the puddle world withrandomly labeled actions, averaged over 100 trials.
αv = 0.1, απ = 0.01, λv = 0.9, λπ = 0.9.

critic using the binary-tree action selector in the puddle
world with randomly labeled actions as shown in Fig. 9.
It is noteworthy that the proposed method can work atleast the same as the ﬂat actor-critic in the puddle world
with randomly labeled actions.

5.

Applying to Real Robots

We applied the algorithms to a learning task in real two
robots that have 2 d.o.f. as shown in Fig. 13. The objec-

T. SICE Vol.E-4 No.1 2007
400

tive of the learning is to ﬁnd eﬀective behavior to move350

forward. The learning agent interacts with the robot (i.e.,

64 actions
32 actions
16 actions
8 actions
4 actions300

the environment) as below:(1) The agent observes the angles of the joints θ1 , θ2
as a state input.

250

Cost

7

(2) The agent selects a destination of angular posi200

tions of the joints a1 , a2 as an action output.
(3) The robot moves each joint to the destination.

150(4) After about 0.2 sec, distance of the movement is100

measured and given to the agent as immediate reward.
(5) Go to step 1.

50

The angles of the joints θ1 , θ2 as the state input and a1 , a2
0
0

50

100

150

200

250

300

350

400

450

500

Trial

as the action output are arranged to take discrete value
from 0 to 7. The reward signal also takes discrete value

Fig. 11 Performance on Q-learning using -greedy policy averaged over 100 trials.  = 0.1, learning rate = 0.5.

from −128 to 127. When the body does not move, thereward is 0.
Each joint is drived by a hobby-use servo motor that400

reacts to angular position commands. The angular posi350

tion command is used as the current angle of the joint.

64 actions
32 actions
16 actions
8 actions
4 actions

300

Therefore, when the agent selects destination angles thatis largely diﬀerent from the latest angles (the diﬀerence is

Cost

250

over 3), hidden state problem is occured quite often because the slow response of the motor cause errors between

200

the true angle of the joints and the state input signal.
150

Since the agent selects action from the eight choices ineach joint, the number of actions are 8 × 8 = 64 in the100

space of the two joints. In the ﬂat action selection method,50

the agent deals with all the 64 actions equally. In the binary action selection method, the agent selects upper or

0
0

50

100

150

200

250

300

350

400

450

500

Trial

downward groups of the angles with respect to the joint
1 in the root node (the ﬁrst layer), and next the agent se-

Fig. 12 Performance on SARSA(λ) using -greedy policy averaged over 100 trials.  = 0.1, learning rate = 0.1,
λ = 0.9. Note that this algorithm costs the memory
exactly the same size as our method’s.

lects upper or downward groups of the angles with respect
to the joint 2 in the node of the second layer. In the 3rd
layer, the agent selects again upper or downward groupsof the angles with respect to the joint 1 where the elementof the groupes are composed of the group that is selectedin the root node. In the 4th layer, the agent selects again
upper or downward groups of the angles with respect tothe joint 2 where the element of the groupes are composedof the group that is selected in the second layer. Thus, the(A)theta2

theta2(B)

decisions for joint 1 and 2 are assigned alternately to thelayers in the binary-tree. The better implementation may

theta1

theta1exist, however, this is one of the simplest way to makea tree structure for decision making in two-dimensional

Fig. 13 Real two robots and their models. The Robot-A has
a two-link arm. The Robot-B consists two boxes withan actuated joint which bends and twists the body.

action space. The feature vector for the state input isgenerated by using the tile-coding shown in Fig. 6, since
the state space is the same two dimensional as the puddle
world.
In order to measure the distance of the movement, a8

T. SICE Vol.E-4 No.1 2007

12000

puddle world, the performance of the ﬂat action-selection
approach is strongly aﬀected with the number of similar

Accumulated Reward

10000

actions. On the other hand, the binary tree approach is
Robot-A using BinTree

not aﬀected with the number of actions when the actions

8000

are arranged according to similarity. It is noteworthy thatthe performance of the random tree approach is the same

6000
Robot-B using BinTreeor the better than the ﬂat approaches in the case that theactions are randomly labeled. The reason of this result is

4000

considered that random groups that are not arranged ac-

Robot-A using FLAT
2000

cording to similarity with using the hierarchical decision
making is still eﬀective in the problems that have many

Robot-B using FLAT

0

similar actions. The binary tree approaches will be weak
0

500

1000

1500

2000

2500

Learning Steps

3000

when an optimum action exists in an action group wheremost of the actions have poor action-values. The reason
is that the nodes in higher layers would not choose such

Fig. 14 Performances of actor-critic algorithms on the realrobots.

an action group that the average of action value is poor
even if an optimum action exists in that group. However,such an ill-natured problem is rare in real tasks. Replac-

wheel that has a diameter of 3cm is attached to the body,ing the ﬂat action selection with the binary tree action

and turning full circle of the wheel generates 200 pulses.

selection achieves not only the eﬀective learning but also

The reward signal is generated by the turning direction

to omit parameter tuning that is coming from the numberof the wheel as the positive or negative sign of the re-of actions.

ward and by the number of pulses as the magnitude of

In the real robot problems, the diﬀerence of the perfor-

the reward. Thus, 1, 000 pulses are equivalent to about 50

mance between the binary tree and ﬂat approaches is out-

cm. The experiment is executed in 3, 000 steps, that takes

standing. One reason of this result would be that the ac-

about 8.5 minutes. This learning problem does not havetion space is two-dimensional while it is one-dimensional

any particular goal states such as in the puddle world,in the puddle world. The analysis of the relation between

therefore we set the discount rate γ = 0.9. For practicalthe number of the action dimension and the learning per-use, the learning rate is set to somewhat large απ = 0.1.

formance is a future work. In this paper, we demonstrate

The other parameters are the same as in the puddle world,that the proposed approach works eﬀectively in the en-

αv = 0.1, λv = 0.9 and λπ = 0.9.

vironments where the actions are arranged according to

Fig. 14 shows learning curves of accumulated reward,

similarity in only one or two dimensional space. How-that is, the distance of the movement from the initial po-

ever, the performance of the hierarchical aproach would

sition. Although the mechanics of the robot A is quite

be strongly aﬀected with the assignment of the action di-diﬀerent from the robot B’s, the proposed algorithm canmension to the decision layer in higher dimensional action

learn smoothly in both robots.

It is noteworthy thatspace. It is possible to arrange independent binary trees

although the number of all the state-action pairs arefor each action dimension. Finding an appropriate struc-64 × 64 = 4092 since state space is 8 × 8 = 64 and actions

ture of the binary tree would also be a learning problem

are 8×8 = 64, the binary-tree approach obtains appropri-

to solve. The design of the binary tree action selector forate behavior with less than the half of 4092 steps. On thehigh dimensional action space is a future work.

other hand, although the learning algorithms and parameters are the same as the binary tree approaches, the ﬂat

7.

Conclusion

action selection approaches cannot learn at all. The dif-

We proposed a binary-tree stochastic policy representa-

ference of the performance between the binary tree andtion, that is a generalization technique of (or using) action

ﬂat approaches is outstanding than the performance inspace for probability of action selection. The eﬃciency ofthe puddle world.

our method is owing to the property of the environments

6.

Discussion

Although the learning problem is very simple in thethat neighboring actions will almost result in similar statetransitions. The computational expense for selectiong action and ﬁnding eligibilities is quite little since the agent

9

T. SICE Vol.E-4 No.1 2007

can perform it using only local information. This feature
is advantageous to the implementation for large problems.
Replacing the ﬂat action selection with the binary tree
action selection achieves not only the eﬀective learning
but also to omit parameter tuning that is coming fromthe number of actions. The proposed action selector isa theoretically sound and simple stochastic-policy representation. Therefore, it can be applied to all the policy
gradient methods such as actor-critic, REINFORCE, or
VAPS algorithms.

Hajime KIMURA (Member)He received Ph.D. degree in intelligence science from Tokyo Institute of Technology in1997. He was empolyed as a PD researcher
in Japan society for the promotion of sciencein 1997. He belonged to the interdisciplinary
graduate school of science and engineering inTokyo Institute of Technology as a research associate from 1998 to 2004. He has been an associate professor of the graduate school of engineering of Kyushu university. The researchinterest is artiﬁcial intelligence, especially reinforcement learning.

References

Shigenobu KOBAYASHI (Member)
1) Barto, A.G., Sutton, R.S. & Anderson, C.W.: Neuronlike
adaptive elements that can solve diﬃcult learning control
problems, IEEE Transactions on Systems, Man, and Cybernetics, vol. SMC–13, no.5, pp. 834–846 (1983).
2) Takanori Fukao, Norikatsu Ineyama and Norihiko Adachi:
Reinforcement Learning Using Regularization Theory toTreat the Continuous States and Actions, Trans. of Institute of Systems, Control and Information Engineers,
Vol.11, No.11, pp.593–599 (1998) in Japanese.
3) Horiuchi, T., Fujino, A., Katai, O. & Sawaragi, T.: Fuzzy
Interpolation-Based Q-learning with Continuous Inputs
and Outputs, Transactions of the Society of Instrument
and Control Engineers, Vol.35, No.2, pp.271–279 (1999) inJapanese.
4) Kimura, H. & Miyazaki, K. & Kobayashi, S.: A Guideline
for Designing Reinforcement Learning Systems, Journal of
the Society of Instrument and Control Engineers, Vol.38,
No.10, pp.618–623 (1999) in Japanese
5) Kimura, H. & Kobayashi, S.: An Analysis of Actor/Critic
Algorithms using Eligibility Traces: Reinforcement Learning with Imperfect Value Functions Journal of Japan Society of Artiﬁcial Intelligence, Vol.15, No.2, pp.267–275(2000) in Japanese.
6) Peshkin, L. & Meuleau, N. & Kaelbling, L. P.: Learning
Policies with External Memory, Proceedings of the 16th International Conference on Machine Learning, pp.307–314(1999).
7) Sutton, R.S.: Generalization in reinforcement learning:
Successful examples using sparse coarse coding, Advancesin Neural Information Processing Systems 8 (NIPS8),
pp.1038–1044 (1996).
8) Sutton, R. S. & Barto, A.: Reinforcement Learning: An
Introduction, A Bradford Book , The MIT Press (1998).
9) Sutton, R. S., McAllester, D., Singh, S. & Mansour, Y.:
Policy Gradient Methods for Reinforcement Learning with
Function Approximation, Submitted to Advances in Neural
Information Processing Systems 12 (NIPS12), (2000).
10) Tsitsiklis, J. N., & Roy, B. V.: An Analysis of TemporalDiﬀerence Learning with Function Approximation, IEEE
Transactions on Automatic Control, Vol.42, No.5, pp.674–
690 (1997).
11) Watkins, C. J. C. H. & Dayan, P.: Technical Note: QLearning, Machine Learning 8 , pp.279–292 (1992).
12) Williams, R. J.: Simple Statistical Gradient Following Algorithms for Connectionist Reinforcement Learning, Machine Learning 8 , pp. 229–256 (1992).

He received Ph.D. degree in decision scienceand technology from Tokyo Institute of Technology in 1974. He joined the department ofcontroll engineering in Tokyo institute of Technology as a research associate in 1974. He
moved to the interdisciplinary graduate schoolof science and engineering in Tokyo Institute ofTechnology as an associate professor in 1981,
and is currently a professor there since 1990.
His research interest is algorithms, inferences,controll and machine learning.

Reprinted from Trans. of the SICE
Vol. 37 No. 12 1147/1155 2001