確率的２分木の行動選択を用いた強化学習による多数の類似行動の扱いについて○木村 元，

小林 重信

東京工業大学 大学院総合理工学研究科
Binary Tree Action Selector: Reinforcement Learning to Cope with Enormous Similar Actions○ Ha jime Kimura,

Shigenobu Kobayashi

Interdisciplinary Graduate School of Science and Eng., Tokyo Institute of Technology
Abstract:
In real world applications, learning algorithms often have to handle several dozens of actions, which have some distance metrics. Q-learning or SARSA algorithms with epsilon-greedy exploration
strategies 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 representation that 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.
1 はじめに

1.1

マルコフ決定過程 (MDP)

SAR
2S

状態空間を ，行動空間を ，実数の集合を と
強化学習は，ロボットの挙動を自ら改善したり知に識の欠落を自ら補うための接近法として有望である． 表す．各時刻 t でエージェントは状態観測 staを実行し，状態遷移に伴う報酬基づいて行動t
実環境のロボット学習制御において，繊細な制御をrを得る．多くの強化学習法が基礎としている
t行うためには連続で膨大な状態空間の扱いが求めら
では，一般に次の状態やマルコフ決定過程れると同時に，多数の行動選択の学習も求められる．
連続または膨大な状態空間を扱うための方法として 報酬は確率的で，その分布は st と atにのみ依存する．
では次の状態 st+1は遷移確率 T st ; a; st+1 になど の関数近似やな方法を用いて状態空間を汎化する接近法が 従って決まり，報酬 rtも期待値 r st ; a によって与え確立されている．しかし多数の行動を扱うためには， られる．エージェントは予め T st; a; st+1 や r st; aを汎化する技術だけでなく，行動選択 についての知識は持っていない．強化学習の目的はエージェントの挙動を最適化する政策を得ることでや探査戦略についても特別の工夫が必要である．
やアルゴ リズムと ある．無限期間のタスクにおいて自然な評価規範と戦略やボルツマン選択 して，以下のような割引報酬の合計がある．
共によく用いられるε1X
戦略は仕組みが単純なのでよく用いられ，行動数がkVt
rt+k少ない場合は強力であることが知られている．しかk =0
しこれらは行動の数が増加すると効率が悪くなるた
割引率
は未来に得るであろう報酬の現時関数とはめ，別の工夫が必要である．一方で，を点での重要度を表し，Vtは時刻 t の評価値別に任意のパラメータ表現された政策関数を持つこではは以下に定義される．
表す．とにより，連続値の行動を扱うことが容易な強化学"#1Xが知られている．
t
習アルゴ リズムとし て
V s E
rt s0 s; の政策関数表現として確率的本論文ではt=0な２分木を用いることにより，数十以上の多数の類 ただし Eは期待値を表す．
における学習の似した行動を効率良く扱う方法について示す．
を目的は，各状態 s において式 で定義される

2A2R

instance- MDP

CMAC(Sutton, 1996)
based(action value=Valueactor-critic

()

())

()

Q-learning(Watkins,1992) SARSA-greedy

actor-critic(MDP),0 1

MDP(value)

value

( )=

fg

(1)

=

2

MDP,

(2)

value

最大化するような最適政策を見つけることである．

1.2

る．水たまりは半径 0:1 で中心座標は (0:1; 0:75) から(0:45; 0:75) までおよび (0:45; 0:4) から (0:45; 0:8) までの位置に配置される．各試行 (episode または trialと呼ばれる) における初期状態はゴール状態を除いて一様分布で生成する．ゴールは [0:9; 0:9] から [1:0; 1:0]

多数の類似行動を有する環境までの矩形領域である．

2勾配法による政策改善
2.1a0a1a3a1a2a6a58 actions
a0a1a14a2a13a3a12a4

a11a5a10a8a24a6a9a8a7a16

16 actions

1:6432 actions

4, 8, 16, 32

図水たまり問題．行動の種類はまたの場合がある．行動を選択すると，その矢印のは方向へおよそ : ほど 移動する．状態空間は 次元で，各軸がそれぞれ ; の範囲に限定される．

0 05

1E frja2g = 82

図数ya44 actions

12: Bernoulli semilinear ユニットの一例．確率変2 f0; 1g は分布 P (y = 1) = f に従う．
本章は本手法に関連の深い REINFORCE アルゴ
リズム (Williams, 1992) の特殊な場合について述べる．図 2のような Bernoulli semilinear ユニットを考える．確率変数 y 2 f0, or 1g は分布 f に従い，P (y = 1) = f または P (y = 0) = 1 f のように

a3a2a15 a0

y = 1 a を実行し報酬 rを得る
: 行動

Efr
ja g = 10f XXX
z 行動 a を実行し報酬 rを得る
y =X0 XXa0a7

REINFORCE アルゴリズム

2[0 1]

振舞う．エージェントは現在の状態を特徴ベクトルx1 ; x2; ; xi ; ; xn によって観測する．分布関数f は以下の式で与えられる：()f=1 + exp (1Px)

i i i,(3)

ただし xiは状態入力の特徴ベクトルの要素，iは政多くの実問題では，隣り合う行動の多くは類似し 策パラメータの要素を表す．エージェントは政策パた状態遷移となる性質を有している．図 はラメータの調節により挙動を改善する．エージェンの水たまり問題を示す． トは行動 または を選択し，報酬 rを受け取る．そ状態空間は２次元の連続値で各軸は ; の範囲であ のとき政策パラメータの適正度は以下る．エージェントは現在位置の座標を状態とし て観 の式で計算される．
測する．エージェントが行動を選択すると，上記の@P 実行された行動
eの範囲を超えない限り選択された方向へおよそ@i(のガウス@距離を移動する．移動の際，標準偏差
fy@i
分布のノイズが各軸方向に付加される．行動の種類@
fy@iが増加すると隣接する行動が類似してくることは図y f xiの報より明らかである．各時間ステップにおいてアルゴ リズムはに入ることでさらに このとき
酬に加えて，水たまり1996)

1 (Sutton,(puddle world task)[0 1]
0.010.05
1(puddle)

負の報酬が与えられる．この水たまりによる負の報を掛けた値であ酬は，境界線からの最短距離に40010(eligibility)

ln ()
ln
if = 1=ln(1 ) if = 0= ( )REINFORCE
i = e (r b)ii + i ,=(4)(reinforcement base- tic policy) に従って行動を実行する．Critic は，Actor の政策のもとでのそれぞれの状態の value を推定する．Actor は，環境から直接受け取る報酬と，critic
f g.
で推定される value より計算される TD エラーを手がかりに政策を改善する．図 4は本論文で用いたアル

ただし は学習率，b は報酬基線と呼ばれる値で，yとは条件付独立である．このアルゴ リズムは以下の勾配に比例して政策パラメー@
報酬 rを報酬タを更新する：E i@i E r
合計 Vtに置き換えてもこの特徴は失われない。

line)f g =ゴ リズムを示す．
このアルゴ リズムは報酬基線 b を適切に設定するにおける処理手順は図 のステップ からことで性能を改善できる．例えば 図 のような簡単のとき，エージェントはど までに示されている．パラメータv は v
な環境を考える．bにおいて関数とちらの行動を選択しても常に正しい行動 a1を強化で の適正度の履歴を表す．政策は関きるため，性能が最も良い．例えば行動 a1を実行し して明示的に表現され，政策パラメータをにより強化 数の勾配によって更新する
た場合，a1は正の強化値 r b．
される．行動 a2を実行した場合，a2の選択確率は負により減少するため a1が強 観測 s においてエージェントが行動 a を選択する確率の強化値 r b化される．さらに洗練された方法とし て b を適応的 を政策と呼び，関数 a; ; s で表す．政策 a; ; sの は行動 a の集合が連続値の場合は確率密度関数であに生成する方法がある．
は，報酬の予測値rを適 る．エージェントは内部変数を調節することにより応的に更新し，以下のように報酬基線として用いる． 確率的政策を変える．

2=9Critic

435TD( = )actorvalue(Kimura and Kobayashi,1998; Sutton, McAllester, Singh & Mansour,2000)= 10 9=8 9((Sutton & Barto, 1998)
Reinforcement comparisoni = e (r r)i
i + i ,4(5))(4,5 actor
REINFORCE algorithm)

図 のステップ
はの処理手続きである．
で定義されて適正度 e はの適いるものと同一である．パラメータは の
ただし rの計算においては現在の行動 yの情報を用い 正度の履歴の性質を定めるが，その性質はが場合とはやや異なる．が に近い場合，に適正度の履歴を用いたてはならない．の勾配により政策が改善され，V
学習しているがアルゴリズムは，rを Vtに，rをV s にそれぞれ置き換えたものである． に近い場合は式 で定義される実際の利得の勾配に，かつ t <よって政策が改善される．ここで のときe tと仮定する．このとき図 のアルゴ
2.2 Actor-Critic アルゴリズム
リズムは以下のように政策パラメータを更新する：

critic

Actoractor(Kimura & Kobayashi, 1998)
1
^
 ()

0^

1=1

()=01X

エージェントActor

st -at

確率的政策 6reinforcement for at=0=trt + V^ (st+1 ) V^ (st ) TD-error
st- Critic V^ (s) 

状態観測

報酬
環境rt
行動(t) =?

1X
t=0

1=X=X=X

t=01

t=0

1

t=0actorTD( )critic1

rt + V^ (st+1) V^ (st )1e (t)

X

 t1X

 =t

 =0!

t e (t)r + V^ (s ) V^ (s )!

+1!

r

 t

e (t) Vt V^ (st)
t
X



 =t

e (t)

4

rt + V^ (st+1 ) V^ (st) e (t)

X

t=00

.

V^ (st )!

(7)(8)

3: 一般的な actor-critic アルゴ リズムの枠組． 式 8は式 1および式 7より得る．ここで式 8のΣ中の項について e (t) は行動 atに関連し , Vtは atの割引報酬Actor-Critic 学習システムは，政策反復法 (Policy であり，V^ (st) は atや Vtを計算するよりも前に与えiteration) の一種であると言われている．政策反復法 られるため atや Vtとは条件付独立である．よって式 8は状態評価と政策改善を交互に繰り返す．Actor は， のΣ中の項は式 5と同じであり，図 4が reinforcement
状態から行動への確率分布である確率的政策 (stochas- comparison の拡張であることが分かる．
図



3

1. 状態 stを観測し，確率分布(at; ; st) に従って行動 atを選択／実行する．

+1+1した割引報酬の期待値を表す．

3. TD 法を用いて critic のV^ (s) を更新する．
@ ^V (s ) ,ev (t) =@w t
ev (t)
ev (t) + ev (t) ,w(t) = (TD-error) ev (t) ,w
w + v w(t) ,ただし ev はV^ (s) のパラメータ wの適正度，ev はその適正度の履歴， vは学習率を表す．

4. TD-error で actor の行動選択確率を更新する= @@ ln (at; ; st) ,e (t) + e (t) ,= (TD-error) e (t) , +  (t) ,P (a1 ) = f1 f2*a1

1 f HHja
0H

12

2. 報酬 rtを受け取り，遷移後の状態 st を観測して以下の TD-error を計算する．
(TD-error) = rt + V^ (st ) V^ (st) , (6)(0   1) は割引率，V^ (s) は critic が推定e (t)e (t)
(t)

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



ただし e は政策パラメータの適正度，e はその適正度の履歴，  は学習率を表す．

f1

P (a2 ) = f1 (1 f2 )2@@0a*
1
@ f HHja0H

P (a3 ) = (1 f1 ) f3

3P (a4 )

3= (14f1 )(1 f3 )1. 最上位ノードにおいて f の確率で 1 を選択 (または 1 f の確率で 0 を選択)．選択した数字
11のリンクの方向へ進む．

2. 次のノードにおいても同様に f または f の確率で 1 を選択，さもなければ 0 を選択し，選択23した数字のリンクの方向へ進むという処理を葉ノードにたどり着くまで繰り返す．

3. 最終的にたどり付いた葉ノードの行動 a を実行
4. 全てのノードについて以下の適正度を計算：
y f
if fj is active@ln (a; ; s) = f f@fj
0otherwise,
ただし yj 2 f0; 1g はノード fj の出力を表す．
(jjj (1j)5:

図
行動が４個の場合における２分木行動選択の処
理例と確率的政策表現．fiは確率分布関数を表す．

5

図 は２分木構造の行動選択方法について，行動が４個の場合の例を示す．葉ノードはそれぞれ行動に対応する．それ以外のノードは図 のによって構成される．理論上，この確率的政策関数は以下のように記述される．

2 Bernoulli semi5. 適正度の履歴を以下のように割り引く．
linear unitev (t + 1)
v ev (t) ,f f
a=ae (t + 1)
 e (t) ,f (1 f )a=a (a; ; s) =(9)(1 f ) fa=a
ただし v および  (0  v ;   1) はそれぞ
(1 f ) (1 f ) a = a
れ critic と actor の割引率である．
6. 時刻を t t + 1 に進めてステップ 1 へ戻る． このとき f の適正度は以下の式で与えられる：
1=fa=a@ln (a; ; s) = 1=f1=(1 f ) aa == aa@f
図 4: Actor と critic の両方に適正度の履歴を用いる
1=(1 f ) a = a
actor-critic アルゴ リズム．
= f y(1 ff ) ,(10)
8>
>
>
>
<>
>
>
>
:

1112

112

1233

138>
>
>
>
<1112>>
>
>
:

1

14

1

1

13

14

@@f @
 (a; ; s) = 1
ln (a; ; s) = (y1 f1)xi .
@i@i @f1
同様に f2や f3の適正度は以下のようになる．

=>
>
>
>
:
(1=f
1=(1002

y2 f2
f2 (1 f2 )

0
(

(y02

if f is active
otherwise.
2f2 )xi

if f is activeotherwise.
2以上より，各ノードの計算処理はローカルな情報だけで実行できる．２分木のルートノードより葉ノード までの選択されたパス上の適正度は単純に yj fj xiで与えられ，それ以外のノード では になる．この性質は木のサイズが変わっても全く同じである．必に等しい．
要なメモリ容量 ノード 数 は 行動数(0Dimension #1

Dimension #1

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

7 by 7 tilings

よって f2の政策パラメータについての適正度は@f2 @ln (a; ; s) =@i @f2

x2, x3, x4, x5= 4/140 or 0

Dimension #1

a = a1a = a2a = a3a = a4f2 )2 by 2 tilings

x1 = 1/140

Dimension #2@ln (a; ; s) =@f2

8>
>
>
>
<1 by 1 tiling
Dimension #2

310Dimension #2( = 1 2 or 3)
4Dimension #22 f0 1g

ただし y1; はユニット f1が選択した値を表す．
;
を式 のシグモイ
ここで分布関数 fj j
ド 関数で与えるもととする．式 と式 より，f1の政策パラメータの適正度は以下のようになる．

)

x91,...,x140= 49/140 or 0

Dimension #16:

図２次元状態入力から広域および 局所的特徴量を含む特徴ベクトルを生成するタイルコーデ ィング．
x140 の各要
個々のタイルは特徴ベクトル x1; x2;
2222はより．状素に対応．数字
態入力があるタイル内にある場合，そのタイルは発のタ火，対応する特徴量はある正の値 例えばなど をとる．それ以外の要素はゼロ．
イルは =( )140 1 +2 +3 +    +71 140()

11Q選び，残りの確率で最も大きな 値を持つ行動を選ぶ．時刻 t の状態を st ，その特徴量を xi t ，そのとき選択した行動を at ，状態遷移後の状態と特徴量をst
xi t，時刻 t
で選んだ行動を at+1との学習則はすると，()+ 1, ( + 1)
+1
Q-learningwa i = xi(t) rt + max
Q(st ; a) Q(st ; at)
4 計算機シミュレーション結果
awa i
wa i + wa i ,行動数の増加がアルゴ リズムに与える影響を調べる．図 1の水たまり問題において提案手法と Q-learning これを全ての i 2 f1; 2;   140g について行う． はおよび SARSA() を比較する．状態入力より特徴ベ 学習率．SARSA() の学習則は以下のとおり
クトル (x ; x ;    x ) を生成するため図 6のタイル(TD-error) = rt + Q(st ; at ) Q(st; at)コーデ ィング (Sutton & Barto, 1996) を用いる．
ea i (t) = xi (t) + ea i (t)actor-critic では状態 value をV^ (s) = i xiwi とwai = eai(t) (TD-error) for all aji xi ))表し，actor は図 5同様 fj = 1=(1+exp(iwaiwai + wai
for all aと表す．行動の個数 N のとき critic 中の wiとその適eai (t + 1) =  eai (t)for all a,正度の履歴ev について 2  140 個の変数を要し，actorにおける政策パラメータji とその適正度の履歴eにこれを全ての i 2 f1; 2;   140g について行う．eaiは
ついて 2  140  (N 1) 個の変数を要することから，適正度の履歴である．Q-learning では Q(s; a) を近似
本手法は 2  140  N 個の変数を必要とする．
するため変数 wiを 140  N 個要する．SARSA() でQ-learning と SARSA() では，状態-行動 value を は変数 wiとその履歴eaiのために 2  140  N 個の変Q(s; a) = i xi waiと表す．行動選択戦略として 数を要する．SARSA が消費するメモリーは提案手法
-greedy を用いる．つまり確率でランダムに行動を と全く同じである．
()

1





+1tt

12tt

140+1

P140=1
P140=0P140=1tt+1

800

800
64 actions
32 actions
16 actions
8 actions
4 actions

700

600

Cost/Episode600

Cost/Episode64 actions
32 actions
16 actions
8 actions
4 actions

700500400300500

400300200200

100

100000200400600

800

10000200

Episodes1000= 1)

Q-64 actions
32 actions
16 actions
8 actions
4 actions

700

600

Cost/Episode(図は各手法の学習結果を示す 割引率．
提案手法では，行動の個数が増加しても，性能がほ政策を用いた
とんど 変化しない．一方やでは，行動の個数によって性能が大きく影響を受ける．

learning SARSA

800

800

7: ２分木行動選択と actor-critic を用いた手法
100 試行について平均した学習曲線． v = 0:1,
 = 0:0005, v = 0:9, p = 0:9．
-greedy600

Episodes

図を7, 8400500

400

300

200

1005

まとめ002004006008001000Episodes

本稿では ２分木による確率的政策表現方法を提案した．本手法は，隣接する行動が類似の状態遷移をもたらすことが多い環境にて効果を発揮する．行動選択や適正度の計算は単純かつローカルな情報だけで可能であり，大規模問題への拡張も容易である．提案手法は単に確率的政策表現方法の一つであり，理論的にだけでなくも単純なため，アルゴ リズム等へも適用できる．

actor-critic

REINFORCE

参考文献

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).
Kimura, H. & Kobayashi, S.: An Analysis of Actor/Critic Algorithms using Eligibility Traces: Reinforcement Learningwith Imperfect Value Function, 15th International Conference on Machine Learning , pp.278{286 (1998).

8: Q-learning -greedy
SARSA( ) -greedy
100=01( )( )=01

図と政策を用いた場合 上および と政策を用いた場合 下の試行平均の学習曲線．
: ，学習率:．

Sutton, R.S.: Generalization in reinforcement learning: Successful examples using sparse coarse coding, Advances in
Neural Information Processing Systems 8 (NIPS8) , pp.1038{1044 (1996).
Sutton, R. S. & Barto, A.: Reinforcement Learning: An Introduction, A Bradford Book , The MIT Press (1998).
Sutton, R. S., McAllester, D., Singh, S. & Mansour, Y.:
Policy Gradient Methods for Reinforcement Learning withFunction Approximation, Submitted to Advances in NeuralInformation Processing Systems 12 (NIPS12) , (2000).
Watkins, C. J. C. H. & Dayan, P.: Technical Note: Q-Learning,Machine Learning 8 , pp.279{292 (1992).
Williams, R. J.: Simple Statistical Gradient Following Algorithms for Connectionist Reinforcement Learning, Machine
Learning 8 , pp. 229{256 (1992).