計測自動制御学会論文集

Vol.33, No.1, 1/9（ 1997 ）確率的２分木の行動選択を用いた Actor-Critic アルゴリズム y|多数の行動を扱う強化学習|
木

元・小

村

林 重

信

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.

に行動選択を行っていることに起因する．われわれは日常生

はじめに活において，たとえば ハンド ルを操作する場合「右に回す」

強化学習は，ロボットの挙動を自ら改善したり知識の欠あるいは「左に回す」のど ちらかを選択した後「少しだけ回落を自ら補うための接近法とし て有望である 4) ．実環境のす」あるいは「普通に回す」を選択するといった具合に，しロボット 学習制御において，繊細な制御を行うためには連

ばしば 階層的に行動を選択することで効率良く意思決定を続で膨大な状態空間の扱いが求められると同時に，多数の行っている．このとき無意識に「右に少し回す」と「右に普行動選択の学習も求められる．代表的な強化学習法である

通に回す」を「右に回す」という上位の行動によってグルーQ-learning

11)

SARSA

8)

は離散的な状 態・行動を対象プ化していると考えられる．実環境における学習問題の多くとし ている．そのため連続な状態空間や行動空間におけるはこのように行動間に距離を定義できる，つまり行動空間

状態評価関数に位相構造が存在するため，物理量的に近接・類似する行動

や(state value function) や状態-行動評価関数(state-action value function) を表現するために関数近似として CMAC を用いる方法 ，ファジィを用いる方法 ，過8)

去の経験を用いて補間する方法

3)

2)など が提案されている．

しかし多数の行動を扱うためには，状態(-行動) 評価関数のをグ ループ 化することで容易に階層化できる．そこで本論
文では数十以上の多数の類似した行動を効率良く扱うために階層的行動選択を行う強化学習方式を提案する．提案手法はパラ メータ化された確率的政策関数表現として２分木

actor-critic アルゴ リズム1) 5) 8)

表現を工夫するだけでなく，行動選択や探査戦略についても構造を導入し，特別の工夫が必要である．一般によく用いられるε策パラ メータを更新する．本手法は行動集合間の半順序関-greedyによって政戦略やボルツマン選択戦略は，仕組みが単純なわりに，行動係についての知識を木構造の階層に反映させることにより，数が少ない場合は強力である．ところがこれらは行動数の学習の効率化を図る．ただし ，本論文では階層構造は設計者増加に比例して学習時間が増加したり，パラ メータのスケが与える．実験により，行動空間に位相構造が存在する環境

ジューリングを行動数に応じて適切に設定する必要があるとでは行動の個数が増加しても提案手法の学習性能が低下しいう問題がある．これらは，全ての行動を区別なくフラット

にくいことを示す．

y 第 27 回 SICE 知能システムシンポジウムにて発表 (2000・3)
 東京工業大学大学院総合理工学研究科
 Interdisciplinary Graduate School of Sci. and Eng. Tokyo

Institute of Technology（ Received January 1, 1997 ）（ Revised January 1, 1997 ）

2.

2. 1

問題設定

マルコフ決定過程 (MDP)

S ，行動空間を A，上界と下界を持つ実数の集合を R と表す．各時刻 t でエージェントは状態観測 st 2 S に
状態空間を

TR 0001/97/3301{0001 c 1997 SICE

T. SICE Vol.33 No.1 January 1997
基づいて行動 at 2 A を実行し，状態遷移に伴う報酬 rt 2 R
2を得る．多くの強化学習法が環境のモデルとし て仮定する(MDP) では，一般に次の状態や報酬は確率的で，その分布は st と at にのみ依存する．MDP では次の状態 st は遷移確率 T (st ; a; st ) に従って決まり，報酬
rt も期待値 r(st ; a) によって与えられる．エージェントは予
め T (st ; a; st ) や r(st ; a) についての知識は持っていない．

st

-

st

-

マルコフ決定過程

+1

+1

+1

強化学習の目的はエージェントの挙動を最適化する政策を得して，以下のような割引報酬の合計がある．

Vt =

k=0

kr

,

t+k

Critic V^ (s)Observation

ることである．無限期間のタスクにおける自然な評価規範と

1
X

Agent
Actor
at
stochastic policy 
6 reinforcement for at
TD-errorrt + V^ (st+1 ) V^ (st )1（ ）Fig. 2

rtRewardActionEnvironment
A standard actor-critic architecture.

0   1 は未来に得るであろう報酬の現時点での重要度を表し，Vt は時刻 t の評価値 (value) を表す．MDP

ント位置と，水たまり外周との最短距離にでは評価関数は以下に定義される．

である．水たまりは半径?

割引率

V  (s) = E
ただし E

" 1
X

t

t=0

rt s0 = s; 

#

,

2

（ ）

fg は期待値を表す．MDP における学習の目的は，各状態 s において式2 で定義される評価値を最大化するよ

うな最適政策を見つけることである．
2. 2

多数の類似行動を有する環境

a6

a1

a5

a2

a1
a3

4 actions

8 actionsa15 a0
a14
a1
a13
a2

a0

a12

a3

a11

a4

a10
a9

２分木構造の確率的政策表現を用いた Actor-

Q-learning や SARSA 等の DP-

based または value-based な手法は，行動が離散だが行動間環境の非マルコフ性に対して弱く，状態×行動の膨大な空間

a24
a8

a5
a6
a8 a7

a16

16 actions

32 actions

遷移となる性質を有している．Fig. 1 は

代表的強化学習法である

value 関数を汎化することで対処する方法がほとんど だが，多くの実問題では，隣り合う行動の多くは類似した状態

で各軸について域である．

に類似度や距離が存在するような環境においては行動空間の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.

ばれる経路探索問題[0:9; 0:9] から [1:0; 1:0] までの矩形領

Critic 強化学習アルゴリズム

a0

a4

7)

生成される．ゴールは

a0

a2

Fig. 1におけ る初期状態はゴ ール領域を除いた位置に一様分布で

3.
a7

a3

400 を掛けた値
0:1 で中心座標は (0:1; 0:75) から(0:45; 0:75) までおよび (0:45; 0:4) から (0:45; 0:8) までの位置に配置される．各試行 (episode または trial と呼ばれる)

puddle world と呼を示す．状態空間は２次元の連続値[0; 1] の範囲である．エージェントは現在位

value 関数を推定した後でなければ 政策を得ることができないなど の問題がある．それに対して actor-critic

におけるアルゴ リズムは非マルコフ性に対して頑健な実装が簡単で

value 関数を推定するよcritic が機能しなくても学習可能など のあり，政策改善は状態×行動空間のりずっと速く，また優れた特徴を持つアルゴ リズムだが，離散行動間に類似度や距離が存在するような環境においてその性質を生かす行
動選択方法が無かった．そこで上記の問題に対して有効な

actor-critic の実装方法を提案する．
3. 1

Actor-Critic アルゴ リズム

代表的な強化学習アルゴリズムとしては

SARSA

8)

Q-learning11)やが知られているが ，本論文では，木構造の特殊

0.05 の距離を移動する．移動の際，標準偏差 0.01 のガウ{(Q 値) を用いずに行動選択を行う actor-critic を用いる．この学習アルゴ
リズムは，Q 値の代わりに行動選択確率を制御する政策パ

ス分布のノイズが 各軸方向に付加され る．行動の種類が増

ラメータを明示的に保持する．本手法は，行動選択を行う

置の座標を状態として観測する．エージェントが行動を選択すると，上記の範囲を超えない限り選択された方向へおよそ加すると隣接する行動が類似してくることはFig. 1 より明

1 の報酬に加えて，(puddle) に入ることでさらに負の報酬が与えられらかである．各時間ステップにおいて水たまりる．この水たまりによる負の報酬は，水たまり内のエージェ

な行動決定を行うため，状態 行動の評価値

actor と，状態の評価を行う critic の２つの部分より構成される (Fig. 2)．Actor は状態から行動への写像を確率的政策(stochastic policy) と呼ばれるパラメータ化された確率分布
に従って行動を実行する．Critic は，actor の政策のもとで

計測自動制御学会論文集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(TD-error) = rt + V^ (st+1 ) V^ (st ) , （ 3 ）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) in thecritic according to the TD() method as follows:
ev (t) = @ V^ (st ) ,@w
ev (t) ev (t) + ev (t) ,w(t) = (TD-error) ev (t) ,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 stochasticpolicy accordingto@ e (t) =ln
(at ; ; st ) ,@e (t) e (t) + e (t) ,(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 tt + 1, and go to step 1.
（

Fig. 3


第

(

)

)

ントに実装できる計算資源の制限など ，一般に個別の問題ごとに制約が存在するが，本論文では２分木構造の行動選択を行う政策関数を用いる．

Fig. 3 のステップ 4,5 は actor の処
REINFORCE algorithm

理手続きである．適正度 e は12)で定義されているものと同一で，選択した行動が政策パラメータあるいは行動選択確率に与えるインパクトの大きさ

actor の適正度の履歴の性質を定TD() の場合とはやや異なる． が 0に近い場合，critic が学習している V^ の勾配により政策が改善され， が 1 に近い場合は式 1 で定義される実際の利を表す．パラメータ  はめるが，その性質は得の勾配によって政策が改善される 5) ．

 
H*
HHj@@ *@ HHHj
3. 2

２分木構造の確率的行動選択

1

f1

f2

0

f3



Actor は，環境から直接受け取る報酬 rt および critic で推定される評価値 V^ (s) より計算される TD エラーを手がかりに政策を改善する．行動を実行して状態遷移した結果，TD エラーが正ならば，実行
した行動（あるいは行動の時系列）によって良い状態へ遷移したと考えられるので，その行動（あるいは行動の時系列）

TD エラーが負ならば ，悪い状態へ遷移したと考えられるので，その行動（あるいは行動の時系列）の選択確率を低めるよう更新することで政策改善を

actor-critic の 詳 細を示 す ．
Critic における処理手順は Fig. 3 のステップ 3,4,5 に示されている．V^ (s) はパラメータ w による線形関数として表される．実装方法についての詳細は 3.3 節にて説明する．パラメータ v は TD( = v ) の適正度の履歴を表す．政策はactor においてパラメータ化された関数として明示的に表され，式 1 の評価関数 Vt あるいは V^ (s) の勾配を登る方向へ
5)(

トが行動 a を選択する確率を政策  と呼び，関数  a; ; s

政策  を変える． a; ; s の関数形については，エージェ^( )Fig. 3 は本 論 文で用 いた

政策パラメータを更新する 5) 9) ．観測 s においてエージェン

トルを表す．エージェントは  を調節することにより確率的の状態評価値 V s を推定する．

行うものである．

3で表す．パラメータ  はエージェントの政策パラメータベク

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

の選択確率を高める．逆に33 巻 第 1 号 1997 年 1 月

1a1

P (a1 ) = f1 f2

0

a2

P (a2 ) = f1 (1 f2 )1

a3

P (a3 ) = (1 f1 ) f3

0

a4

P (a4 )= (1f1 )(1 f3 )1 ） Start at the root of the tree, choose 1 with probability f1 (or 0 with probability 1 f1 ), and take thecorresponding branch.
（ 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
 y f
@
ln
(a; ; s) = f (1 f ) if fj is active@fj
0otherwise,
where yj 2 f0; 1g is the outcome of the node fj .
（jFig. 4jjj



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

Fig. 4 は２分木構造の行動選択方法について，行動が４個の場合の例を示す．葉ノード はそれぞれ行動に対応する．
それ以外の各ノード では確率 fi に応じて確率的に分岐する．
この確率的政策関数は以下のように記述される．

T. SICE Vol.33 No.1 January 1997

4

8
f1 f2
>
>
>
<

a = a1f1 (1 f2 )a = a2
(a; ; s) =>(1 f1 ) f3
a = a3>>:(1 f1 ) (1 f3 ) a = a4

は状態評価関数をパラメータ wi と状態特徴ベクトルの要素

4（ ）このとき f1 の適正度は以下の式で与えられる：

8
>
>
>
<

1=f1
a = a1a = a2@ ln (a; ; s) = 1=f1
@f1>
1=(1 f1 ) a = a3>>:
1=(1 f1 ) a = a4
（ 5）
= f1y(11 ff11 ) ,ただし y1 2 f0; 1g はノード f1 が選択した値を表す．同様に
f2 や f3 の適正度は以下のようになる．
8
>
>
>
<

1=f
1=(1
@
@f ln (a; ; s) = >
0
>
>
:
0
2

f2 )

2

=

(

a = a1a = a2a = a3a = a4以上より，各ノード の計算処理は全く同じで，しかもローカ
ルな情報だけで実行できる．２分木のルート ノード より葉yj fj
ノード までの選択されたパス上の適正度は単純に fj (1fj )で与えられ ，それ以外のノード では になる．この性質は0

木のサイズが変わっても全く同じである．必要なメモリ容量(ノード 数) は Fig. 5 に示すように (行動数) 1 に等しい．
a1

a1

a1

a2
a3
a4

a2
a3
a4
a5

a2
a3
a4
a5

a6

a6
a7
a8

a5
a6

a7

6 actions(5 nodes)7 actions(6 nodes)Fig. 5nX
i=1

wi xi .

7

（ ）上記の近似表現は線形アーキテクチャ(linear architecture)

TD 法により，ある条件のもとで二乗誤差最小のと呼ばれ，推定値への収束が証明されている 10) ．パラ メータ wi の適
正度 evi は(@ V^ (s))=(@wi ) = xi で与えられる．

Actor における２分木行動選択の各ノード の分岐確率 fj

も状態特徴ベクトルを用いて以下のように表す：

fj =1
1 + exp( Pni ji xi ) ,

8

（ ）

=1

ただし ji は 政策パラ メータであ る ．この 関数はシグ モ

0 か ら 1 までの 単 調 増 加関 数であ5, 6 および 式 8 よ り@fj =@ji = xi fj (1 fj ) であることから以下で与えられる：eji = @fj @ ln (a; ; s)@ji @fj
イド 関 数で ，値 域が20V^ (s) =る ．ji に 関 す る適 正 度 eji は 式

if f is active （ 6 ）otherwise.

y2 f2
f2 (1 f2 )xi との線形結合によって以下のように近似表現する：

8 actions(7 nodes)The binary trees for 6, 7 and 8 actions.

((yj fj )xi if fj is active（ 9）0otherwise.
ただし yj 2 f0; 1g はノード fj が選択した値を表す．
=

以上より，状態特徴ベクトルの要素 n 個，行動数 m 個の場合における提案手法の詳細は以下のようになる．
（

1 ） 初期化：Critic の n 個の変数 wi (ただし i = 1    n)

および その 適 正 度の 履 歴を 保 持 す る n 個の 変 数 evi ，actor の n(m 1) 個の政策パラ メータ変数 ji (ただしj = 1  m 1) および その 適 正度の履 歴を保 持するn(m 1) 個の変数 eji を用意して値を初期化する．
（ 2 ） 状態 st の特徴ベクト ル (x (t); x (t)    xn (t)) を
1

2

観測
（

3 ） Actor の２分木で行動選択（ a ） ルート ノード j = 1 より以下の計算を始める：（ b ） ノード fj において以下を計算する：
1fj =1 + exp( Pn ji xi (t))
i=1

fj の確率で 1 を選択 (または 1 fj の確率で 0 を選択)．

3. 3

２分木構造の Actor を用いた Actor-Critic

3.2 節の２分木構造の行動選択器を 3.1 節のactor-critic の actor へ適用し た実装例の詳細に ついて述
本節ではべる．まず，エージェントは現在の状態 s を特徴ベクトル(x ; x ;  ; xi ;   ; xn ) に よって観 測するものと する．た1

2

だし 時刻 t の特徴ベクト ルで あることを 強調するときは(x (t); x (t);  ; xi (t);    ; xn (t)) のように t の関数として
12記述する．通常，センサ入力などの刺激からどのように状態表現を生成すべきかとい う問題は学習対象とし て扱われ ることが多いが，本論文では対象外とし ，状態表現は特徴ベク

Critic でトルとしてトップダウンに与えられるものとする．

選択した数字のリンクの方向へ進む．

c ） 進んだ先のノード で同様の処理を繰り返す．
（ d ） 最終的にたど り付いた葉ノード の行動 a を実行（ e ） 全ノード j について以下の適正度を計算：((yj fj )xi(t) if fj is activee (t) =0
otherwise,
ただし yj 2 f0; 1g はノード fj の出力を表す．
（ 4 ） 報酬 rt を受け取り，遷移後の状態 st を観測して以下の TD-error を計算する．
(TD-error) = rt + V^ (st ) V^ (st)
（

ji

+1

+1

計測自動制御学会論文集= rt +

n
X
i=1

!

n
X

wi xi (t + 1)

i=1

ji

ji

提案手法の特徴

行動の選択は行動数 m に対して

33 巻 第 1 号 1997 年 1 月

5, xi (t + 1)，時刻 t + 1 で選んだ行動を
at+1 とすると，Q-learning の学習則はwati = xi (t) rt + max
Q(st+1 ; a) Q(st ; at )awati wati + wati ,これを全ての i 2 f1; 2;  ng について行う． は学習率．
SARSA() の学習則は以下のとおり(TD-error) = rt + Q(st+1 ; at+1 ) Q(st ; at )eati (t) = xi (t) + eat i (t)wai = eai(t) (TD-error) for all a
wai wai + wai
for all aeai (t + 1) =  eai (t)for all a,
これを全ての i 2 f1; 2;  ng について行う．eai は適正度の履歴である．Q-learning では Q(s; a) を近似するため変数wi を n  m 個要する．SARSA() では変数 wi とその履歴
eai のために 2  n  m 個の変数を要する．SARSA が消費状態と特徴量を st+1

wi xi (t)（ 5 ） Critic の V^ (s) を以下のように更新する．
evi (t) = xi (t) ,evi (t) evi(t) + evi (t) ,wi (t) = (TD-error) evi (t) ,wi wi + v wi (t) ,（ 6 ） 適正度 e (t) で actor の行動選択確率を更新する
eji (t) e (t) + eji (t) ,ji (t) = (TD-error) eji (t) ,ji ji +  ji (t) ,（ 7 ） 適正度の履歴を以下のように割り引く．
evi (t + 1)
v evi (t) ,eji (t + 1)
 eji (t) ,（ 8 ） 時刻を tt + 1 に進めてステップ 2 へ戻る．
3. 4

第log m 回の二者択一に2するメモリーは提案手法と全く同じである．

Q-learning や

SARSA では，本論文のように大量の行動を扱う場合には，実行した行動 at について Q(st ; at ) を更新するだけでなく，
at の近傍の行動についても同様の更新を行う方法がある 8) ．

よって行われる．選択のための計算や適正度の計算は，木構4.

造上で選択されたパス上だけで，個々のノード のローカルな値を用いた単純計算で実行される．よって大規模問題への適Actor-critic アルゴ リズムを用いているため，ある程度の非マルコフ性を有する環境でも Q-learning用に有効である．

ほど の影響を受けずに学習が可能である 5) ．
3. 5

既存手法および 関連研究

Actor-critic では離散的な行動選択として Boltzmann 選
3.3 節の設定と同様の n 次元状態特徴ベクトルが与えられ，m 個の行動がある場合，actor ではn  m 個の政策パラメータ変数 ji (ただし j = 1    m) お択が提案されている 8) ．

よびその適正度の履歴を保持する n m 個の変数 eji を用意する．ある行動 ak を以下の確率で選択する：
Pn
i=1 xi ki 
ak s PmPn
j=1
i=1 xi ji

Pr( j ) =

exp
exp

（

10 ）

行動 ak を実行した場合の政策パラメータの適正度は以下のように計算する 6) ：(Pr(aj js) xi
if aj 6= ak ,(1 Pr(aj js)) xi if aj = ak .
これらの処理を 3. 3 節中の actor の部分と置き換えるだけでフラットな行動選択の actor-critic になる．
Q-learningと SARSA() で は ，状 態-行 動 評 価 値 を
Pn
Q(s; a) = i xiwai と表す．行動選択戦略としては Boltsmann 選択の他，-greedy 選択がよく用いられる．これは確率  でランダムに行動を選び，残りの確率で最も大きな Qeji (t) ==1

値を持つ行動を選ぶ方法である．時刻 t の状態を st ，その()特徴量を xi t ，そのとき選択した行動を at ，状態遷移後の計算機シミュレーション実験

行 動 数の 増 加が アルゴ リズ ムに 与え る影 響を調 べ る ．

Fig. 1 の水たまり問題において提案手法，フラットな行動選択を行う actor-critic，-greedy 戦略を用いる Q-learning
および SARSA() を比較する．状態入力から特徴ベクトル(x ; x ;  x ) を生成するためタイルコーディング を用
1

2

8)

140

いる．２次元状態入力から広域および 局所的特徴量を含む
特徴ベクトルを生成するため Fig. 6 のように

140 コの特徴

量を生成するタイルコーディングを用いた．状態空間全部1  1 から 7  7 まで分割したタイルを用いる
1 + 2 + 3 +  + 7 = 140 コの特徴量となる．個々のタイルは特徴ベクトル (x ; x ;    x ) の各要素をカバーする
ため，合計

2

2

2

2

に対応する．状態入力がある m

1

2

140

 m 分割のタイル内にある

場合，そのタイルは発火し，対応する特徴量ベクトルの要素

140 の値をとり，それ以外の要素はゼロである．
割引 率は= 1，提案手法の v = 0:1，  = 0:01，
v =  = 0:9 とした．Q-learning と SARSA() の探査パ
ラメータ  = 0:1，Q-learning の学習率 = 0:5，SARSA()の学習率 = 0:1， = 0:9 とした．
Figs. 7，8，11，12 は各手法の学習結果を示す (割引率= 1)．各グラフの縦軸 (cost) はスタートからゴ ール領域
までのコスト (負の報酬) を表し，横軸 (trial) はスタートからゴ ール領域に到達するまでを 1 trial とし て表している．
全ての手法において学習の進行すなわち trial の増加にとは m2 =

もなってコストが減少している．特に提案手法では，行動の個数が増加しても，性能がほとんど 変化しない．一方フラットな行動選択を用いた

actor-critic， Q-learning および

T. SICE Vol.33 No.1 January 1997

6

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

Fig. 6

50

100

200

250

300

350

400

450

500

Trial

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  1tiling is 1=140, etc.). The other elements are set tozero.

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

350

64 actions
32 actions
16 actions
8 actions
4 actions300

a4 a29 a30 a19
a7
a2
a23

a1

a21

a8

a20

a22

a14

a3

a18

a11

a12

a27

a31

a26
a13
a5

400

Fig. 9a9
a6
a28
a16 a24 a10 a15

An example which are randomly labeled actions in thepuddle world.

400

250

Cost

150

350

200

64 actions
32 actions
16 actions
8 actions
4 actions

300

150

250

Cost

100

50

200

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.

100

50

0
0

されている場合の２分木行動選択の学習のようすを示す．行
動がランダムに配置されていても，この問題では２分木行動

100

150

200

250

300

350

400

450

500

Trial

SARSA では，行動の個数によって性能が大きく影響を受ける．Fig. 10 は行動が Fig. 9 に示すようにランダ ムに配置

50

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.

選択は少なくともフラット選択と同等の性能を示した．
5.

ロボット への適用

Fig. 13 に示すように，モータを２個搭載した２自由度の機構を持つロボット

A および B に対し，完全に同一のアルゴ リズムを適用し，効率よく前進する動作の獲得を試みる．

()

エージェント コントローラ が獲得すべき制御規則は，現在の関節の角度を状態入力とし て与えられたとき，前進するような動きとなるようにモータの目標値とすべき関節の計測自動制御学会論文集
400

33 巻 第 1 号 1997 年 1 月

7角度を出力することである．ロボットの学習目標は，効率よ350

く前進することなので，各時刻におけるボディの前進速度を64 actions
32 actions
16 actions
8 actions
4 actions300

エージェントが報酬として受け取るよう設定する．エージェ( )1 ） エージェントは状態観測としてロボットの関節の角

ントとロボット 環境 は以下のやりとりを行う．
（

250

Cost

第

度 1 ; 2 を受け取る．

200（2 ） エージェントは行動出力として関節モータの角度の目標値 a1 ; a2 を出力1503 ） ロボットは目標角度の方向へ各モータを動かす．
（ 4 ） 約 0.2 秒後，ロボットはボディが移動した距離を計（100測し，その値を報酬としてエージェントに与える．

50

（
0
0

50

100

150

200

250

300

350

400

450

500

Trial
Fig. 11

Performance on Q-learning using -greedy policy averaged over 100 trials.  = 0:1, learning rate = 0:5.

モータの角度の目標値 a1 ; a2 は，それぞれ整数値をとる．報酬の値は0 から 7 までの

128〜127 の範囲の整数値をと0 である．

り，ボディが移動しない場合は関節の駆動モータとし て模型用サーボモータを用いたた

400

め，本実験における状態観測 1 ; 2 は，直前のステップにお350

いてエージェントが出力した行動 a1 ; a2 に等しい値とした．

64 actions
32 actions
16 actions
8 actions
4 actions300

よって，エージェントが直前のステップで出力した値とは大(きく異なる値 値の差がおおむね

250

Cost

5 ） ステップ 1 に戻って繰り返す．

状態観測である関節の角度 1 ; 2 および行動出力である関節3 以上) を出力した場合，モータの応答が追い付かないため，エージェントが観測する
角度状態とロボットの真の角度とが食い違う隠れ状態問題を200

生じやすい．

8 種類の目標値のうち１つを選択するため，２関節で 8  8 = 64 コの行動を扱うことになる．フラットな行動選択では，これら 64 コの行動を区別

150

エージェントは各関節毎に

100

50

なく選択する．２分木の行動選択を行うアルゴ リズムでは，
ルート ノード において関節１に ついて上半分または下半分

0
0

50

100

150

200

250

300

350

400

450

500

Trial
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.

の行動集合どちらかを選択し，第２層では関節２について上半分または下半分の行動集合を選択する．第３層では再び関節１について第1 層で選択した集合のうち上半分または下半分を選択し ，第４層では関節２について同様に選択するといった具合に２分木の深さに 対して行動の次元を交互に対応させる．もっと良い実装方法があるかもしれないが，この実装は，２次元の行動空間を木構造に反映させる最も単純な方法の一例である．状態入力は水たまり問題と同じ次元の連続値なので，本実験でも同様に

2

Fig. 6 に示すタイ

ルコーデ ィングで特徴ベクトルを生成した．
移動距離を計測するため１回転(A)

theta2

theta2(B)

200 パルスのロータリー

3cm の車輪を付け，パルス個数を報酬の1000
パルスは約 50cm の距離になる．実験は 3000 ステップの学習を行った．実時間で約 8.5 分である．本実験は水たまり

エンコーダに直径

絶対値，回転方向を報酬の符号とし て計測した．報酬

theta1

Fig. 13

theta1

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.

問題とは異なり，ゴ ールのような終端状態が存在しないの= 0:9 に設定した．また，実時間で学習させる
ため，  = 0:1，と大きめに設定した．それ以外の学習パ
ラメータは水たまり問題と同じ学習率 v = 0:1，v = 0:9，
 = 0:9 とした．
で割引率

T. SICE Vol.33 No.1 January 1997

8
12000

分木行動選択に置きかえることにより，学習の高速化だけでなく，行動の個数に応じてパラメータをチューニングする手

Accumulated Reward

10000

間も省けることが期待できる．
Robot-A using BinTree

ロボットの実験ではフラットな行動選択と階層的な行動選

8000

択との性能の差がさらに顕著に現れた．水たまり問題と大き2 次元である点なので，これが影響く異なるのは，行動が6000
Robot-B using BinTree

していると考えられるが，行動次元の増加と学習性能との因

Robot-A using FLAT

は１次元および ２次元空間に行動が整然と配置されている

果関係についての詳しい解析は今後の課題である．本論文で

4000

2000

環境において，提案手法が効率良く機能することを示した．
Robot-B using FLAT

行動がさらに多次元になった場合，階層的行動選択ではどの2000れる．各軸で独立の出力を行うような実装も可能であるし，0次元から選ぶかによって性能が大きな影響を受けると予想さ
0

500

1000

1500

2500

3000

Learning Steps

木構造の決定自体も学習対象となりうると考えられる．高次
元の行動空間の場合にど のような木構造にすべきかに つい

Fig. 14

Performances of actor-critic algorithms on the realrobots.

学習によってエージェントが得た報酬の累積，すなわち初Aては今後の課題である．
7.

おわりに

本稿では２分木による確率的政策表現方法を提案した．本期位置からロボットが移動するようすを Fig. 14 に示す．

手法は類似の状態遷移をもたらす行動が多数ある環境にてと効果を発揮する．行動選択や適正度の計算は単純かつロー

B は全く異なるメカニズムであるにもかかわらず，提案手法を用いた場合にはどちらのロボットも順調に学習を行って8  8 = 64，
行動空間が 8  8 = 64 より全状態-行動ペアが 4092 組ある

カルな情報だけで可能であり，大規模問題への拡張が容易でいる．特にここで注目すべき点は，状態空間がある．従来のフラットな行動選択と置き換えることにより，にもかかわらず，その半分以下のステップ数でほぼ行動を獲チューニングも不要となる．提案手法は単に確率的政策表現得している点である．それに対してフラットな行動選択の場

方法の一つであり，理論的にも単純なため，合には，学習アルゴリズムやパラメータが同じであるにもか外のアルゴ リズムとの組合わせも可能である．

かわらず，ほとんど 学習が進んでいない．行動選択方法のちがいによる性能の差は水たまり問題よりも顕著に現れた．
6.

考察

単純な水たまり問題でも，単に類似した行動を増やすだ
けで，フラットな行動選択を用いた場合には学習アルゴ リ
ズムに関係なく学習性能が行動数の影響を受ける．ところが2 分木行動選択を用いると，類似した行動が順番に並んでいる場合には行動数の影響をほとんど 受けずに学習できる．興味深いのは，行動がランダムに配置された場合でもフラットな行動選択と同等かそれ以上の性能だった点である．
これは，類似した行動が多数存在する問題においては，行動をランダムにグループ化しても，階層的な行動選択により効率良く学習できるためと考えられる．階層的な行動選択が苦手とする環境として考えられるのは，あるグループ化された行動集合中において，低い評価値を持つ行動がほとんど の割合を占める中に最適な行動がぽ つんと存在するような場合である．行動グループの中に最適な行動が含まれていたとしても，その行動グループの平均評価値が低ければ，上位階層
ではその行動グループを選択しなくなるので最適行動を学習できないと考えられる．しかし 実問題ではこのように意地の悪い問題はほとんど 無いだろう．フラットな行動選択を

2

学習性能の向上だけでなく，行動の個数に応じたパラメータ

参

考

文

actor-critic 以

献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 ）深尾 隆則，稲山 典克，足立 紀彦：正則化理論を用いた連続的状態と行動を扱う強化学習，システム制御情報学会論文誌，

Vol.11, No.11, pp.593{599 (1998).

3 ）堀内 匡，藤野 昭典，片井 修，椹木 哲夫：連続値入出力を扱う
ファジィ内挿型 Q-learning の提案，計測自動制御学会論文集,
Vol.35, No.2, pp.271{279 (1999).
4 ）木村 元，宮崎 和光，小林 重信：強化学習システムの設計指針，
計測と制御, Vol.38, No.10, pp.618{623 (1999).
5 ）木村 元，小林 重信：Actor に適正度の履歴を用いた ActorCritic アルゴ リズム{ 不完全な Value-Function のもとでの強化学習，人工知能学会誌, Vol.15, No.2, pp.267{275 (2000).
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).
［著
木

村

者

紹 介］

元 （ 正会員）

1997

年東京工業大学大学院知能科学専攻博士課程修了，同年 月日本学術振興会
研究員，
年 月，東京工業大学大学院総合理工学研
究科助手，現在に至る．人工知能，特に強化学習に関する研究に従事．

1998 4

小

林

重

4

PD

信 （ 正会員）

1974

年東京工業大学大学院博士課程経営工学専攻修了．同年 月，同大学工学部制御工学科助
手．
年 月，同大学大学院総合理工学研究
年 月，教授．現在に至る．問科助教授．
題解決と推論制御，知識獲得と学習など の研究に従事．

4
1981 81990 833 巻 第 1 号 1997 年 1 月

9