計測自動制御学会東北支部 第 209 回研究集会 (2003.6.12)
資料番号 209-9

部分観測マルコフ環境における階層型強化学習 SSS(λ)
Hierarchical Reinforcement Learning SSS(λ) in PartiallyObservable Markovian Environments○釜谷博行 ∗ ，阿部健一 ∗∗○ Hiroyuki Kamaya∗ , Kenichi Abe∗∗*八戸工業高等専門学校, **東北大学大学院工学研究科*Dept. Electrical Eng., Hachinohe National College of Technology,*Dept. Electrical and Communication Eng., Tohoku University
キーワード : 部分観測マルコフ決定過程 (partially observable Markov decision process),
強化学習 (reinforcement learning)

連絡先 : 〒 039-1192 八戸市田面木字上野平 16–1 八戸工業高等専門学校 電気工学科
釜谷博行，Tel.: (0178)27-7283，Fax.: (0178)27-9379，E-mail: kamaya-e@hachinohe-ct.ac.jp

1.

はじめに

Agent
State
(Observation)

数理心理学の分野で動物の学習行動を記述する

RewardActionEnvironment

数学モデルが 種々提案され ，そのモデルが 学習機
能をもつ工学システムの構築に応用されるように

Fig. 1

強化学習モデル .

なった。強化学習 1) もそのモデルのひとつである。
すなわち，強化学習は報酬(あるいは罰)という特別最大化するよ うな政策 π(状態 S から 行動 A への写な情報を手掛かりに，エージェントが環境との相互像) を見出すことといえる。強化学習では ，一般作用を通し てあらかじ め定められた明確なゴ ール

的に環境モデルが 未知で，しかも正解を教えてくを達成するための行動決定戦略を自律的に獲得す

れ るような教師は存在し ない。また，不確実性のる学習システムと捉えることができる (Fig. 1)。各ある環境，報酬に遅れが 存在する環境にも適用可

時間ステップ t ∈ 0, 1, 2, . . .において，エージェント

能であるという特徴をもつ。

は環境状態 st ∈ S を取得し ，何らかの行動 at ∈ A

多くの強化学習問題において，環境はマルコフを選択・実行することで環境状態を変化させ，こ決定過程（ Markov decision process；MDP ）によりの状態遷移に対する評価値 (報酬)をスカラーの強モデル 化できるものとし て扱っており，エージェ

化信号 rt ∈ Rとし て受け取る。ここで ，学習シ ス

ントは環境状態を完全に観測できると仮定し てい

テムの目標は，強化信号とし て与えられる報酬のる。しかし ，自律型移動ロボットやマルチエージェ

長期間にわたる収益をある評価規範にし たがって

ントシステムなど の多くの分野では，センサの計–1–

測範囲の制約など により環境状態を完全に観測す

SSS) アルゴ リズム 4) と呼ばれ る，より一般的なることは困難な場合が 多い。すなわち，実際に真枠組みの階層型 Q-学習を提案し ている。階層型強の環境状態が 異なっていたとし てもエージェント化学習は，すべての問題に対し て最適性が 保証さはそれらを区別することができない。この問題は，れているわけではない。このため，最適値に近い「 不完全知覚 (incomplete perception) 問題 」，「 知覚

準最適な政策を学習することを目指す。

エリアジング (perceptual aliasing)問題」「隠れ状態，

本稿では ，学習速度の改善および ノイズ環境に(hidden state)問題」など とも呼ばれ，これは MDP

おけ る頑健性の向上を目指すため，Sunらの SSSを拡張し た部分観測マルコフ決定過程（ partially

アルゴ リズムに TD(λ)の考えを導入し 改良を加え

observable MDP；POMDP ）を用いて定式化された SSS(λ)を提案する。比較的規模が大きく複雑なる 2) 。近年，MDP 環境下での強化学習アルゴ リズ

POMDP 環境にある迷路探索問題に適用し ，そのムを POMDPの環境に拡張し 適用する試みが 多く

学習性能について検討する。また，HQ-学習とのの研究者によってなされつつある。しかし ，時系

性能比較を行な う。

列データから隠れマルコフモデル（ hidden Markov

model；HMM ）を学習する問題でさえも NP困難で

2.

強化学習

あると 指摘されていることから ，HMMに 行動決定が 伴う POMDP 学習問題の複雑度は非常に大き各時点t ∈ {0, 1, 2, . . .}において，環境状態が st ∈なものとなる。このため，POMDPは 近似解法にS のとき ，その状態観測に 基づき ，エージェント

よらざ るを得ず，対象とする問題のクラスに応じが 行動 at ∈ Aをとったとすると ，報酬 rt を受け 取て POMDPの性質を うまく利用し た効率的なアルり，環境状態は 未知の遷移確率でつぎ の状態 st+1

ゴ リズムを開発する必要がある。

に遷移する。エージェント の目標は ，報酬の割引
∞
期待利得 E{ t=0 γ t rt } を最大にすることである。

本研究では ，環境モデルが 未知で遅れ 報酬を伴い，しかも従来の強化学習法では解くことのでき

ここで ，γ(0 ≤ γ ≤ 1)は割引率を表わす。

ない比較的規模の大きな POMDP 学習問題を対象

強化学習では，ある状態 s において行動 a を選とする階層型強化学習について考える。階層型強択するときの評価値を Q 値と呼び ，Q(s, a)で表わ

化学習の基本的な考えは，多数の Q-モジュールをす。Q 値の大きさ応じて，エージェントは状態 s に用意しておき，ある特徴的な観測値（ サブゴ ール ）おいて実行すべき行動aを決定する。環境と対峙しが 得られたときに Q-モジュールをうまく切り替えたエージェントは試行錯誤を繰り返し ながら ，割ることで，部分観測マルコフ環境を局所的にはマ

引期待利得の最大化を目的とし て，各時点で得ら

ルコフ環境へ近似し ながら学習を行うところにあれる報酬rt に基づいて Q値を更新していく。強化学る。未知環境を想定し ているため，設計者があら習アルゴ リズムとして TD法5) ，Q-学習6) ，Sarsa1)

かじ め観測空間上でのサブゴ ールを決定することなど が 広く知られている。

は難しい。このため，エージェントの行動学習と同時にサブゴ ールの学習も行う。階層型強化学習の3.

先駆的な研究として，Wieringらは Q-モジュールの切り替え機構に Q-学習と類似の方法を用いた HQ学習3) を提案している。また，Sunらは行動シーケ

SSS アルゴリズム

SSS の基本的な考えは，状態-行動系列をうまく分割するための知識を設計者があらかじ め与えな
くとも，POMDP 問題を非マルコフ性を解消する

ン スの自動分割 (Self-Segmentation of Sequences；–2–

2-level SSS agent
abstract
actioncontinue

activemodule力する。その結果，エージェントは環境から強化

AQ信号を受け取り，新たな状態を観測する。つぎに，

end

CQ1

CQ2

CQ3

新たな 状態に おいてア クティブ な CQが 再び 行動

Q1

Q2

Q3

選択を行う。このとき”continue”が 選択され ると，

reward

同様な手続きが 繰り返され る。一方，アクティブ

state
actionな CQにおいて”end”が 選択され ると，Q モジュー

Environment

ルはその動作を 終了し ，上位の AQに 制御が 戻さ

Fig. 22 階層 SSS シ ステムの概念図.

れ る。AQ では ，現在の状態に おいて 実行すべきようなサブ タスクに自動的に分解することで，複Q/CQ対を新たに 1つ決定する。選択された Q/CQ

数の Q エージェントが 協力し ながら問題を解決す

対がアクティブになり，その CQにおいて行動選択るところにある。

が 行われ ，”continue” または ”end” にし たがって ，

SSS アルゴ リズ ムはつぎ に 示す 3 種類の学習モ以上述べた一連の手続きが 繰り返される。このよ
うに SSS では，階層構造をオンラ インで柔軟に生ジュールから構成され る。

• 行動モジュール Q: 各モジュールはサブゴ ー

成できるため，下位のモジュールを再利用できる，
永続的なタスクにも適用できるなど の特徴がある。

ルを目指す局所的な政策を学習する。

• コント ローラ CQ: 各 Q モジュールに対し てそれぞれ一つのコントローラ CQが用意され

4.

SSS(λ)アルゴリズム

る。CQ モジュールはある状態において Q モ

学習速度の改善および ノイズ環境における頑健ジュールの動作を “continue”(継続) すべきか

性を向上させるため，Sunらの SSS アルゴ リズム”end”(終了) すべきかを学習する。

に TD(λ)の考えを取り入れた新たな学習アルゴ リ• 抽象コントローラ AQ: 下位に複数個のQ/CQ

ズム SSS(λ)を提案する。TD(λ) 手法を利用するこモジュールをもち，ある状況でアクティブにとで ，現在の TD(temporal-diﬀerence) 誤差を 過去

すべき 下位モジュールをど れに すべきか 学に訪問したすべての状態-行動系列にわたり一度に習する。AQモジュールの行動を抽象行動と分配することができ，報酬伝搬を効率的に行なえ呼ぶ。

る。ここでは ，政策オン 型のアルゴ リズムである

Fig. 2に上位レベルにある 1つの抽象コントロー
ラ AQと下位レベルにある 3つの Q/CQモジュールから 構成され る 2 階層 SSS シ ステムの概念図を示す。アルゴ リズムはつぎ の手順で動作する。試行

Sarsa(λ)に 基づいて学習シ ステムを構築する。以下に 2 階層 SSS(λ)アルゴ リズムを示す。
1) Initialize Q, CQ, and AQ
2) Repeat (for each trial)3)ηQ , ηCQ , and ηAQ are initialized to zero

開始時，AQは スタート 時の観測状態に おいてど

4)

Observe sの Q/CQ 対を選択すべきかを決定する (Fig. 2では5)

k ← AQ (AQ selects Q/CQ from s), s̃ ← s

Q1 /CQ1が選択されている)。各時点で 1つの Q/CQ

6)a ← Qk (Qk selects an action from s)

対のみがアクティブになり，その CQにおいて行動

7)

Repeat (for each step of trial)

8)

Take action a, observe r, s9)ca ← CQk (CQk selects continue or end from

選択が 行われ る。このとき，”continue”が 選択され ると ，これと対をなす Q モジュールは 現在の観測状態にし たがって行動を選択し ，外部環境へ出

s )
10)

–3–

Update CQk . . . . . . . . . . . . . . . . . . . Eq.(10)∼(13)11)

ca ← caに遷移する。このとき，状態 s において，Qk と対

12)

if ca is continue then

をなす CQk によって選択された行動が ”continue”a ← Qk (Qk selects an action from s )Update Qk . . . . . . . . . . . . . . . . . . . . Eq.(5)∼(8)
13)

エージェントの経験組 < s, a, r, s , a >に基づいて，

else (that is, ca is end)

ならば ，Qk は s に おいて 次の行動 a を 選択する。

k ← AQ (AQ selects Q/CQ from s )Update Qk . . . . . . . . . . . . . . . . Eq.(5)(9)(7)(8)Update CQk . . . . . . . . . . Eq.(10)(14)(12)(13)

アクティブな Qk モジュールがつぎ のように更新され る。

Update AQ . . . . . . . . . . . . . . . . . Eq.(16)∼(19)

for ai = a
for all ai = a(5)

δQ = r + γQk (s , a ) − Qk (s, a),

(6)

k
ηQ
(s, ai ) ←s̃ ← s , k ← k1,0,

ηQ and ηCQ are reset to zeroa ← Qk (Qk selects an action from s )




14)

s ← s ,a ← a15)

until s is the terminal

すべての si , ai に対し て，

アルゴ リズム中で，k は AQモジュールの抽象行
動を表わす。計算量を低く押えるため，eligibilityの計算はアクティブ な Q/CQ モジュールに 制限する。すなわち，上位レベルの AQモジュールに制御

Qk (si , ai ) ←k
Qk (si , ai ) + αQ δQ ηQ(si , ai ), (7)kηQ(si , ai ) ←kγληQ(si , ai ).

(8)

一方，状態 s において CQk で選択された行動が”end”ならば ，制御が AQモジュールへ戻る。AQはが移った場合には，アクティブな Q/CQモジュール状態 s において新たな抽象行動 k  を選択する。上の Q 値の更新後に，それらの eligibilityを 0にリセッ

位層AQ(s , k  )の Q値に基づいてアクティブな Qk モ

ト する。

ジュールが 更新される。これは，(6) 式をつぎ のよ

学習ルールはつぎ のようになる。アルゴ リズム

うに置き換えることで実現され る。

の表現を簡潔にするため，エージェント の経験組

< s, a, r, s , a >に 対する通常の Sarsa(λ) 学習ルー
ルをつぎ のように与える。
1,
for ai = aη(s, ai ) ←0,
for all ai = a

δ = r + γQ(s , a ) − Q(s, a),

(1)
(2)

δQ = r + γAQ(s , k  ) − Qk (s, a).

(9)

CQ : 状態 sにおいてアクティブ な CQk で選択された行動が ”continue”のとき，それに対応する Qk
モジュールに おいて 行動が 実行され る 。その 後，
報酬 r を取得し ，状態が s に遷移する。状態 s におすべての si , ai に対し て，

いて CQk は新たな行動 ca を選択する。このとき，

Q(si , ai ) ← Q(si , ai ) + αδη(si , ai ),(3)

η(si , ai ) ← γλη(si , ai ),(4)

経験組 < s, ca = continue, r, s , ca >に 基づいて ，

ここで，α (0 < α ≤ 1)は学習率，γ (0 ≤ γ ≤ 1)は割

アクティブ な CQk モジュールがつぎ のように更新

引率，η(s, a)は eligibility trace 関数，λ (0 ≤ λ ≤ 1)

され る。

”continue”が 選択され たならば ，エージェント のは eligibility 係数を表わす。また，sは観測状態であ



k
ηCQ
(s, cai ) ←る。SSS(λ)アルゴ リズムの各モジュールに対する

1,0,

for cai = ca
for cai = ca(10)

δCQ = r + γCQk (s , ca ) − CQk (s, continue), (11)

学習ルールを以下に示す。

Q : アクティブな Qk モジュールが状態 sにおいて行動 aを実行し たとき，報酬 r を取得し ，状態が s–4–すべての si , cai に対し て，

CQk (si , cai ) ←CQk (si , cai )k+ αCQ δCQ ηCQ(si , cai ),(12)kηCQ(si , cai )k← γληCQ(si , cai ).



(13)

べた。このアルゴ リズムは 3階層以上のシステムへ拡張できる7) 8) 。例えば ，3階層システムでは，最下k

一方，状態 s において CQ によって選択された行動が ”end”ならば ，制御が AQモジュールへ戻る。

AQ は 状態 s に おいて 新たな 抽象行動 k  を 選択する。上位層 AQ(s , k  )の Q 値に基づいてアクティブ
な CQk モジュールが 更新され る。これは ，(11) 式をつぎ のように置き換えることで実現され る。


以上，2 階層の SSS(λ)アルゴ リズムについて述kδCQ = AQ(s, k ) − CQ (s, end).

層を AQ0 (=Q), CQ0 (=CQ)，中間層を AQ1 (=AQ)，

CQ1 ，最上位層を AQ2 とする。ここで，AQ2 は中間層の AQ1 /CQ1 の中から一つのモジュールを選択するためのモジュール，CQ1 は対応する AQ1 の動作を継続すべきか終了すべきかを決定するためのモジュールとなる。

(14)

AQ : AQがアクティブになった過去の時点t+1−m5.

シミュレ ーション実験における状態 s̃で抽象行動 k を実行し たとき，現時2つの POMDP迷路探索問題において，提案した

点 t + 1 の状態 s に 遷移するまでに 得られた (割引)SSS(λ)アルゴ リズムの評価実験を行う。すべての総報酬 R̃がつぎ の式で計算され る。

問題において，エージェント の目的は スタート 地

R̃ = rt +γrt+1 +γ 2 rt+2 +...+γ t+m−1 rt+m−1 , (15)点から出発し ，ゴ ール地点 G へ向か う行動を学習することである。



ここで ，m(m > 0)は 状態 s̃から 状態 s に 到達する

エージェント の知覚および 行動はつぎ のようにまでに要したステップ 数，rt , rt+1 , . . .は現在までのする。エージェントはすべての時点で自分のグロー



各時点で得られた報酬を表わす。AQは状態 s にお

いて新たな抽象行動k を選択する。エージェントの

バルな (x, y) 座標を認識できず，現在いるセルに隣接する 4 方向（ 西 W，南 S，東 E，北 N ）のセルに関経験組 < s̃, k, R̃, s , k >に 基づいて ，AQ モジューする情報のみを観測できるものとする。このため，

ルがつぎ のように更新され る。
1,for ki = k
ηAQ (s̃, ki ) ←0,
for all ki = k

エージェントの観測値は最大でも 16種類となり，異

m





δAQ = R̃ + γ AQ(s , k ) − AQ(s̃, k),(16)

トにとって同じ ものと観測され る。各時点でエー(17)すべての si , ki に対し て，AQ(si , ki )なった行動が要求される多くの場所が，エージェン

ジェントは W，S，E，Nの 4 方向の中から選択し た

1つの方向へ 1セルだけ移動できる。壁方向へ移動
し ようとし た場合には移動できず，その場所に留← AQ(si , ki )まるものとする。

+ αAQ δAQ ηAQ (si , ki ), (18)
ηAQ (si , ki )← γ m ληAQ (si , ki ).

(19)

5.1

エージェントがゴ ール到達時あるいは制限時間
内にゴ ールに到達できず試行を途中で打ち切る場
合には ，(6) 式，(11) 式，(17) 式において，つぎ の

状態 s の価値を 0とする。例えば ，AQ モジュールの更新式はつぎ のようになる。

δAQ = R̃ − AQ(s̃, k).

行動選択

本実験では ，AQ モジュール の 行動選択には -

greedy法を，Q/CQモジュールの行動選択には MaxBoltzmann 法を用いる 3) 。-greedy 法は ，確率 でランダ ムな行動を，確率 1 − で最大の Q 値をもつ

greedyな行動を選択するものである。また，Max(20)Boltzmann 法は ，確率 pmax で 最大の Q 値をもつ

–5–

steps1000

G

2 modules
3 modules
5 modules
7 modules
optimal

800
600
400
200
0
0

5000

10000

15000

20000
trialsS

Fig. 3Fig. 4 迷路 1における下位のモジュール数に対する平均学習性能.

迷路 1.

greedyな行動を，確率 1 − pmax で Boltzmann 分布にし たがって 行動を 選択するものである。Boltz-

mann 分布では，状態 st において行動 ai を選択する
確率は次式で与えられ る。

に 減少させた 。Q/CQ モジュールの行動選択には

Max-Boltzmann 法を用いた。このとき，pmax は初
期値 0.9から 1.0 まで 試行回数とともに 直線的に 増Q(st ,ai )e τPr(ai |st ) =  Q(st ,ak ) ,e τ

期値を 0.1とし ，最終試行で 0になるように直線的(21)加させた。温度係数および 学習率は一定とし ，それぞれ τAQ = 0.1，τCQ = τQ = 0.05，αAQ = 0.1，k

ここで ，τ は行動選択のランダ ムさの度合いを決αCQ = αQ = 0.05とし た。また，割引率 γ は 0.97を定するパラ メータで 温度係数と 呼ば れ る 。な お，用いた。1 回のシミュレ ーション実験は 20,000 試行

学習終了時に決定的な方策を得るために，pmax をからなり，各試行のステップ 数の最大値を 1,000とある初期値から 1 まで徐々に増加させる。

し た。

Fig. 4は，下位の学習器のモジュール数がそれぞ

5.2

れ 2，3，5，7 の場合の 2 階層 SSS(0) アルゴ リズム

大きな迷路の平均学習性能を示す。このグ ラフは乱数のシー
ここでは ，下位の Q/CQ モジュールの再利用性能について検討する。Fig. 3に示す大きさ 30 × 25の迷路 9) について考える。この迷路では ，”S”とド 値を 変えた 独立な 100 シ ミュレ ーション の 平均
値をプ ロットし たものである。横軸は試行回数を，
縦軸はゴ ールまでのステップ 数を表わす。グ ラフ

マークされた左下のスタート 地点と ”G”とマークを見ると，試行回数とともにステップ 数が減少し ，された右上のゴ ール地点がある。この問題の最適学習性能が 向上し ていることがわかる。また，モ
値は 131 ステップ で ，かなり大きなものである。
ジュール数の増加につれて学習の収束性能が 良く
この迷路では ，2 階層 SSS(λ)アルゴ リズムにつなることがわかる。

いて評価実験を行う。λ = 0とし ，これ以降SSS(0)Table 1にモジュール数を変えた場合の学習後のと記す。報酬はエージェントがゴ ールに到達でき性能（ 100シミュレ ーション中の最終試行におけるたならば 500を，その他の行動実行毎 (壁方向の移動で 動けない場合も含む) に −0.1 を 与えた 。積極的なサブゴ ール探索を行うため，AQモジュールの

ゴ ールまでの平均ステップ 数，最適ステップを学習
し た割合，タスク成功率，タスク成功時の平均ス
テップ 数 ）を示す。モジュール数が 3 以上のときに行動選択には -greedy 法を用いた。実験では の初–6–

Table 1
モジュール数

2
3
4
5
6
7

迷路 1における学習後の性能.

平
均ステップ 数

最適値の割合 (%)

成功率(%)

成功時の平均ステップ 数

298.8
168.8
162.1
135.3
144.0
135.7

53
62
60
60
63
58

81
96
97
100
99
100

134.3
134.2
136.2
135.3
135.4
135.7

成功率がほぼ 100%で約 60%の割合で最適値を学習
G

1

し ている。ところで，壁方向へ移動する行動は選
択し ないという制約のもとに HQ-学習の学習性能0を調べたところ，成功率がわずか 29%であったとい
う報告がある 9) 。この結果と比較すると，SSS(0)10を用いる方法は非常に良好な学習性能を示し ていると言える。
1

Fig. 5 と Fig. 6 は 下位の 学習器のモジュール 数0が 2と 7の場合において，最適値を学習し たときに発見されたサブゴ ールと使用モジュールの一例を示し ている 。図中の○印が サブゴ ールを 表わし ，Fig. 5 モジュール数が 2の場合に発見されたサブ
ゴ ールと使用モジュールの例.

直線のそばに記し た数字が 使用されたモジュールの識別番号を示す。モジュール数が 2 の場合には ，G

6

0 → 1 → 0 → 1 → 0 → 1 の順番でモジュールが0使われている。このときサブゴ ール 数は 5 個であ1

るが，2つのモジュールを再利用により交互に使用

3

することで効率良く学習し ていることが 確認でき

601

た。また，モジュール数が 7の場合には，2 → 0 →3

6 → 3 → 1 → 0 → 6 → 3 → 1 → 0 → 6 の順番

6でモジュールが 使われている。このときサブゴ ー0

ル数は 10個であるが，4つのモジュールが再利用に

2

より順序良く使用され，合計で 5つのモジュールを用いることで最適値を実現している。このように，Fig. 6

モジュール数が 7の場合に発見されたサブ

ゴ ールと使用モジュールの例.

モジュール数を増やし ても，最適値の実現には必ずし もすべてのモジュールが 使われ るわけではな

5.3

いということも確認できた。また，下位の学習器のモジュール数を増やすことで，学習性能が 向上
することも確認できた。

鍵・ド ア問題

実験環境とし て，26 × 23の部分観測迷路 3) について考える (Fig. 7)。エージェントの目的は，左下のスタート地点S から出発し ，右上の K 地点で鍵を取得し ，右下のゴ ール地点 G へ向か う行動を学習–7–

steps1000

K

HQ:module=9
HQ:module=25
SSS(λ):module=3x3
SSS(λ):module=5x5

800
600
400
200

optimal

0
0

5000

10000

15000

S

20000
trialsG

Fig. 7

Fig. 8 鍵・ド ア問題における平均学習性能 (HQ学習と 3 階層 SSS(λ)).

鍵・ド ア問題.

することである。迷路中の斜線で示した 3つのセル設定し た 。つまり，サブゴ ール 数を 16，λ = 0.9

がド アを表わす。エージェントが 鍵をもたない場とし ，割引率 γ は 1.0 を 用いた 。学習率は ，αQ =合，ド アは壁とし て認識され る。鍵をもっている

0.05，αHQ = 0.01とし ，学習中は一定とし た。ま場合，自由空間となり通過できる。しかし ，エーた，Max-Boltzmann 法の pmax は 初期値 0.4から 0.8

ジェントは 鍵やド アなど を知覚できず，また，鍵まで試行回数とともに直線的に増加させた。温度の取得やド アの通過に際し ては報酬は与えられな係数は 0.2とし ，学習中は一定とし た。

1 回のシミュレ ーション実験は 20,000 試行からない。この問題の最適値は 83 ステップ である。
報酬とし て，エージェントがゴ ールに到達できり，各試行の ステップ 数の最大値を 1,000 とし た 。

たならば 500を，その他の移動毎 (壁方向へ移動しノイズなし の場合と行動ノイズのある場合についようとし て動けない場合も含む)に −0.1を与える。

て実験を行った。

本問題では ，3 階層 SSS(λ)と HQ-学習について
学習実験を行う。3 階層 SSS(λ) のパラ メータはつ

5.3.1

ぎのように設定した。すべてのモジュールにおいて一律に λ = 0.9とし ，割引率γ は 0.97を用いた。学習率は αAQ0 = αCQ0 = 0.05，αAQ1 = αCQ1 = αAQ2

= 0.2とし ，学習中は一定とした。積極的な探索を行うため，行動選択において AQ2 , AQ1 に -greedy
法を，CQ1 ，AQ0 ，CQ0 に Max-Boltzmann 法を用いた 。-greedy 法では  の初期値を 0.1 とし ，最終

Fig. 8は ，学習器のモジュール数が 9，25の HQ学習と下位の学習器のモジュール数が 3 × 3，5 × 5の SSS(λ)の平均学習性能を示す。これらのグラフ
は 乱数のシ ード 値を 変えた 独立な 100 シ ミュレ ー
ションの平均値を 500 試行毎にプ ロットしたものである。結果から SSS(λ)の収束速度が速いことがわかる。

試行で 0になるように直線的に減少させた。また，

Max-Boltzmann 法の pmax は初期値 0.9から 1.0 まで
試行回数とともに直線的に増加させた。温度係数は τAQ0 = τCQ0 = 0.1，τCQ1 = 0.2とし ，学習中は一定とし た。

HQ-学習のパラ メータは ，文献 3) と同一の値にノイズ なし の場合

Table 2，Table 3は ，2 つの学習シ ステムにおいてモジュール数を変えた場合の学習後の性能を示している。ど ちらの学習システムでも，モジュール数が 増えるにし たがい学習性能の向上し ていることがわかる。HQ-学習のモジュール数が 25のとこ
ろと SSS(λ)のモジュール数が 5 × 5のところで比較–8–

Table 2

鍵・ド ア問題における学習後の性能 (HQ-学習).

モジュール数平均ステップ 数

最適値の割合 (%)

成功率(%)

成功時の平均ステップ 数

232.6
115.5
124.1
97.7
88.9
99.9

15
15
14
13
8
11

84
97
96
99
100
99

86.4
88.1
87.6
88.6
88.9
90.8

3
4
5
9
16
25

Table 3

鍵・ド ア問題における学習後の性能 (3 階層 SSS(λ)).

モジュール数平均ステップ 数

最適値の割合 (%)

成功率(%)

成功時の平均ステップ 数

237.6
111.5
99.0
88.3
88.0
88.5

8
19
28
34
21
17

84
98
99
100
100
100

101.0
93.4
89.9
88.3
88.0
88.5

2×2
3×3
4×4
5×5
6×6
7×7

すると，ど ちらも成功率がほぼ 100%であるが ，最

steps
1000

適値の割合は，それぞれ 11%，34%，また，平均ス
テップ 数で比較するとそれぞれ 99.9，88.3である。

800

このことから，SSS(λ)の学習性能が高いことが確

600

認できた。

HQ:module=9
HQ:module=25
SSS(λ):module=3x3
SSS(λ):module=5x5400

SSS(λ)において最適行動を学習したときに使用200される下位のモジュール数を調べてみたところ，3

optimal0〜4モジュールが学習結果の大部分を占めた。した

0

5000

がって，学習シ ステムにたくさんのモジュールを用意し ても，最終的には少ないモジュールで最適

Fig. 9

10000

15000

20000
trials

行動ノイズのある鍵・ド ア問題におけ る

行動を学習し ていることが 確認できた。

平均学習性能 (HQ-学習と 3 階層 SSS(λ)).

5.3.2

習し ている。しかし ，行動ノイズの影響で学習性

行動ノイズ のある場合能がかなり悪化し ていることがわかる。HQ-学習

10%の確率でエージェントが 選択し た行動と無関係にランダ ムな行動が 実行される行動ノイズのと比較すると，SSS(λ)の学習性能が良好であることが 確認できた。

ある環境で 実験を 行な う。Fig. 9 は ，学習器のモ

Table 4，Table 5は ，2 つの学習シ ステムにおいジュール数が 9，25の HQ-学習と下位の学習器のモてモジュール数を変えた場合の学習後の性能を示

ジュール数が 3 × 3，5 × 5の 3 階層 SSS(λ)の平均学し ている。モジュール数の大きいところでタスク

習性能である。試行回数の増加とともにゴ ールまでのステップ 数が 減少し ていることから ，ノイズのある環境でもゴ ールへ到達するための行動を学

成功時の平均ステップ 数を比較すると，SSS(λ)は
約 151〜160，HQ-学習は約 310〜347である。このことから，SSS(λ)は HQ-学習と比較して，ノイズ–9–Table 4

行動ノイズのある鍵・ド ア問題における学習後の性能 (HQ-学習).
モジュール数平均ステップ 数

最適値の割合 (%)

成功率(%)

成功時の平均ステップ 数

406.9
405.3
393.0
458.2

0
0
0
0

86
88
91
83

310.3
324.2
333.0
347.2

5
9
16
25

Table 5

行動ノイズのある鍵・ド ア問題における学習後の性能 (3 階層 SSS(λ)).
モジュール数平均ステップ 数

最適値の割合 (%)

成功率(%)

成功時の平均ステップ 数

299.0
219.2
192.7
252.1
227.9

0
0
0
0
0

86
93
96
90
91

184.8
160.4
159.0
169.0
151.5

3×3
4×4
5×5
6×6
7×7

環境における学習性能がかなり高いことがわかる。

6.

of Artificial Intelligence Research, 4, pp.237–285,
1996.
3) Wiering, M. and Schmidhuber, J.: “HQ-learning,”
Adaptive Behavior, 6-2, pp.219–246, 1997.

おわりに

本稿では ，Sun らの SSS アルゴ リズ ムに TD(λ)の考えを導入することで，部分観測問題における学習性能の向上を目指し た新たな階層型強化学習
アルゴ リズム SSS(λ)を提案し た 。SSS(λ) の学習
性能を 2つの部分観測迷路探索問題においてシミュ
レ ーションにより実験的に評価し た。実験結果から，SSS(λ)は HQ-学習に比べて学習速度の向上が図れ ることを確認し た。また，学習システムのモ
ジュール数を増やすことで ，学習性能を改善できることを示した。さらに，SSS(λ)はノイズなど の非決定性をもつ比較的規模の大きな部分観測問題
においても，良好な政策を学習できることを明らかにし た。HQ-学習と比較し ても，ノイズ環境での学習性能が 高いことが 確認できた。

参考文献
1) Sutton, R. S. and Barto, A. G.: Reinforcement
Learning : An Introduction., MIT Press, 1998.
2) Kaelbling, L. P., Littman, M. L. and Moore, A.
W.: “Reinforcement Learning: A Survey,” Journal– 10 –

4) Sun, R. and Sessions, C.: “Self-Segmentation ofSequences: Automatic Formation of Hierarchies ofSequential Behaviors,” IEEE Trans., SMC-B-303, pp.403–418, 2000.
5) R. S. Sutton: “Learning to predict by the methods of temporal diﬀerences,” Machine Learning, 3,
pp.9–44, 1988.
6) C. J. C. H. Watkins and P. Dayan: “Q-learning,”
Machine Learning, 8, pp.279–292, 1992.
7) H.Kamaya and K.Abe, “Hierarchical SelfSegmentation Algorithms for Q-learning in
Non-Markovian Environments,” Proc. of the
ACIS 2nd International Conference on Software
Engineering, Artificial Intelligence, Networking
and Parallel/Distributed Computing (SNPD’01),
pp. 55–62, 2001.
8) H.Kamaya and K.Abe, “Self-Segmentation ofSequences Algorithm with Eligibility Traces in
POMDPs,” Proc. of the 4th Asian Control Conference (ASCC 2002), pp. 408–413, Singapore,
September, 2002.
9) 山城啓秀，上野敦志，武田英明: “遅れ 報酬に基づく遺伝的アルゴ リズムによる部分観測マルコフ決定問題の解決手法,” 電子情報通信学会論文誌 D-I,
J84-D-I-12, pp.1635–1647, 2001.