階層型強化学習
RGoal アーキテクチャへの再帰呼び出し用スタックの導入
2019-06-06 人工知能学会全国大会

1

私の研究の長期的目標• 脳を模倣して「人間のような知能を持つ機械」を作る。
運動野

本研究：前頭前野による行動計画の機能の再現を目指す。

前頭前野

言語野

視覚野

大脳皮質

基底核

扁桃体

海馬小脳

2

RGoal アーキテクチャ[一杉 et al. 2018 8月 汎用人工知能研究会]• 特徴：– 階層型強化学習– 再帰的にサブゴールを設定可能
サブゴール設定＝サブルーチン呼び出し• プログラミング言語のサブルーチンに似たもの• マルチタスク環境での共有・再利用により学習を加速– 思考モードで脳内シミュレーション• 未経験のタスクも過去に得た知識を組み合わせて解く– スタックなしで、シンプルなアルゴリズムで動作（→ 今回はスタックを導入）
3

MAXQ [Dietterich 2000]• 多層の階層型強化学習アーキテクチャ。
• 階層の深さは固定。設計者が与える。
• 行動価値関数の計算が複雑。
• 探索空間に制約があり近似解しか得られない。

4

階層型強化学習の利点[Dietterich 2000]
１．サブタスク共有：
サブルーチンをタスク間で共有することで学習を加速。
２．時間抽象：行動系列をサブルーチンとして抽象化することで学習を加速。
３．状態抽象：サブルーチンごとに実行に関係ない情報を無視することで学習を加速。
5

人間が再帰的にサブゴールを設定する例
初期状態

はしごを置いた状態

はしごを置く

初期状態

上って取る

倉庫にいる状態

倉庫に行く

初期状態

物を取った状態

はしごを運ぶ

部屋を出た状態

部屋を出る

はしごを置いた状態

廊下を進む

倉庫にいる状態

6

サブルーチン共有の例
高いところのものを取る
はしごを置く初期状態

はしごを置いた状態

電球を取り換える
木の枝を切る

最終目的は違っていても、「はしごを置く」というサブルーチンは共通7拡張状態行動空間 [Levy and Shimkin 2011]
Up
Left

𝑠𝑠

Down

Right

拡張Up
Left
Down

𝑠𝑠
𝐶𝐶𝑚𝑚2
𝐶𝐶𝑚𝑚3Right𝑔𝑔 = 𝑚𝑚1
𝑔𝑔 = 𝑚𝑚2𝑔𝑔 = 𝑚𝑚3

𝒮𝒮 = 0,0 , 0,1 , …
𝒜𝒜 = 𝑈𝑈𝑈𝑈, 𝐷𝐷𝐷𝐷𝐷𝐷𝐷𝐷, 𝑅𝑅𝑅𝑅𝑅𝑅𝑅𝑅𝑅, 𝐿𝐿𝐿𝐿𝐿𝐿𝐿𝐿, …

もともとの状態 s とサブゴール gの組 𝑠𝑠̃ = (𝑠𝑠, 𝑔𝑔) を拡張された状態と見なす。
𝒮𝒮̃ = 𝒮𝒮 × ℳ
𝒜𝒜̃ = 𝒜𝒜 ∪ 𝒞𝒞ℳℳ = {𝑚𝑚1 , 𝑚𝑚2 , … } ⊆ 𝒮𝒮
𝒞𝒞ℳ = 𝐶𝐶𝑚𝑚1 , 𝐶𝐶𝑚𝑚2 , …

数学的構造は通常のMDP と同じなので、MDP を前提とした様々な理論的帰結（例えば厳密解への収束性）や強化学習の高速化技術（例えば関数近似や適8格度トレース）が利用可能。

価値関数分解[Singh 1992][Dietterich 2000]• 関数 Q をサブゴール g の到着の前後で分解
到達前

到達後

𝑄𝑄𝐺𝐺𝜋𝜋 (𝑠𝑠, 𝑔𝑔), 𝑎𝑎 = 𝑄𝑄𝜋𝜋 𝑠𝑠, 𝑔𝑔, 𝑎𝑎 + 𝑉𝑉𝐺𝐺𝜋𝜋 𝑔𝑔

ただし 𝑉𝑉𝐺𝐺𝜋𝜋 𝑔𝑔 = Σ𝑎𝑎 𝜋𝜋 𝑔𝑔, 𝐺𝐺 , 𝑎𝑎 𝑄𝑄 𝜋𝜋 (𝑔𝑔, 𝐺𝐺, 𝑎𝑎)• 関数 Q(s,g,a) はもともとのゴール G に依存しないため、異なるタスク間で共有できる。
– 例：「はしごを置く」という行動のコスト（労力）は、はしごを使う目的に依存しない。
– パラメタが減って、学習が速くなる。

9Sarsa による学習（予稿集の説明は不完全なので補足）

𝑄𝑄 𝑠𝑠̃ , 𝑎𝑎� ← 𝑄𝑄 𝑠𝑠̃ , 𝑎𝑎� + 𝛼𝛼(𝑟𝑟 + 𝑄𝑄 𝑠𝑠̃ ′, 𝑎𝑎�′ − 𝑄𝑄 𝑠𝑠̃ , 𝑎𝑎� )サブゴールが g 、スタックの中身が g1,g2,...gn のとき、エージェントの移動経路は s->g->g1->g2->...->gn である。
サブルーチン g' を呼び出すと移動経路は s->g'->g->g1->g2->...->gn に変化。
したがって、以下の式が成り立つ。

𝑄𝑄𝑔𝑔𝑛𝑛 𝑠𝑠̃ ′, 𝑎𝑎�′ − 𝑄𝑄𝑔𝑔𝑛𝑛 𝑠𝑠̃ , 𝑎𝑎�= 𝑄𝑄 𝑠𝑠 ′ , 𝑔𝑔′ , 𝑎𝑎�′ + 𝑉𝑉𝑔𝑔 𝑔𝑔′ + 𝑉𝑉𝑔𝑔1 𝑔𝑔 + 𝑉𝑉𝑔𝑔2 𝑔𝑔1 + ⋯ + 𝑉𝑉𝑔𝑔𝑛𝑛 𝑔𝑔𝑛𝑛−1− 𝑄𝑄 𝑠𝑠, 𝑔𝑔, 𝑎𝑎� + 𝑉𝑉𝑔𝑔1 𝑔𝑔 + 𝑉𝑉𝑔𝑔2 𝑔𝑔1 + ⋯ + 𝑉𝑉𝑔𝑔𝑛𝑛 𝑔𝑔𝑛𝑛−1= 𝑄𝑄 𝑠𝑠 ′ , 𝑔𝑔′ , 𝑎𝑎�′ − 𝑄𝑄 𝑠𝑠, 𝑔𝑔, 𝑎𝑎� + 𝑉𝑉𝑔𝑔 𝑔𝑔′

この式は行動がサブルーチン呼び出しではなくプリミティブの時も成り立つ。
これから、下記の学習則が導かれる。

𝑄𝑄 𝑠𝑠, 𝑔𝑔, 𝑎𝑎 ← 𝑄𝑄 𝑠𝑠, 𝑔𝑔, 𝑎𝑎 + 𝛼𝛼(𝑟𝑟 + 𝑄𝑄 𝑠𝑠′, 𝑔𝑔′, 𝑎𝑎′ − 𝑄𝑄 𝑠𝑠, 𝑔𝑔, 𝑎𝑎 + 𝑉𝑉𝑔𝑔 𝑔𝑔′ )10Softmax による行動選択
𝜋𝜋 𝑠𝑠̃ , 𝑎𝑎� ====exp 𝛽𝛽𝛽𝛽 𝑠𝑠̃ , 𝑎𝑎�Σ𝑎𝑎′ exp 𝛽𝛽𝛽𝛽 𝑠𝑠̃ , 𝑎𝑎′

exp 𝛽𝛽(𝑄𝑄 𝑠𝑠, 𝑔𝑔, 𝑎𝑎 + 𝑉𝑉𝑔𝑔 𝑔𝑔𝑔 )Σ𝑎𝑎′ exp 𝛽𝛽(𝑄𝑄 𝑠𝑠, 𝑔𝑔, 𝑎𝑎′ + 𝑉𝑉𝑔𝑔 𝑔𝑔𝑔 )exp(𝛽𝛽𝑉𝑉𝑔𝑔 𝑔𝑔𝑔 ) exp 𝛽𝛽𝑄𝑄 𝑠𝑠, 𝑔𝑔, 𝑎𝑎

exp(𝛽𝛽𝑉𝑉𝑔𝑔 𝑔𝑔𝑔 ) Σ𝑎𝑎′ exp 𝛽𝛽𝑄𝑄 𝑠𝑠, 𝑔𝑔, 𝑎𝑎′
exp 𝛽𝛽𝑄𝑄 𝑠𝑠, 𝑔𝑔, 𝑎𝑎Σ𝑎𝑎′ exp 𝛽𝛽𝑄𝑄 𝑠𝑠, 𝑔𝑔, 𝑎𝑎′

11

迷路課題■■■■■■■■■■■■■■■■■■■■■■■■■■・・ｍ・・・・・・・・・・・・・・■・・・・ｍ■■・・・・・■・・ｍ・・・・・・・ｍ■・・・・・■■・・・・・■■■■■・・・・■■■■・・・・・■■・・・・ｍ・・・・■・・・・・■・・・・・・・■■・・・・・■・・・■ｍ・・・ｍ■・・・・・・・■■・・・・・■・・・■■■・・・・・ｍ・・・・・■■・・・・・■・ｍ・・・■・・・・・■・・・・ｍ■■・・・ｍ■■・・・・・■・・・・・■・・・・・■■・・・・・■・・・・・■ｍ■・・・■・・・・・■■・・・・・■・・・■・■・■・・・・・・・・・■■・・・・・・・・・・ｍ■・・・・・・・■・・・■■■■■■・・・・・・・■■■■・・・・■ｍ・・■■・・ｍ■・・・・・・・・・・■・・・・■■■■■■・・・■・・ｍ・・・ｍ・・・■ｍ・・・・・・・■■・・・・・・・・・・■・・・■■■・・・・・・■■・・・・・・・・・・■・・・・・・・・・・・・■■・・・■・・・ｍ・・■・・・・・・・ｍ・・・・■■■■■■■■■■■■■■■■■■■■■■■■■■

m はランドマーク

マップとランドマークの集合は固定。
ランドマークは、ゴールやサブゴールになり得る場所。
スタート S とゴール G をエピソードごとにランダムに設定する。

12

エージェントの動作
@
S

m1

m2

スタートg
G
ゴール

ランドマークサブゴール
エージェント13

エージェントの動作
@
S

m1

m2

g
G

@
S

m1

g
m2

G

Stack=[G]

@
Sg
m1

m2

GStack=[m2, G]

S@
m1g
m2G

Stack=[G]

m1@
m2g
G

Stack=[]S

Stack=[]

14

実験１：スタックなし版 RGoalとの比較[一杉 et al. 2018]

0.08

episodes/steps

0.07
0.06
0.05

Without Stack

0.04

With Stack

0.03
0.02
0.01
01

357

9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39

x 100,000 steps

実験条件にもよるが、同程度の早さで収束している。

15

実験２：スタックの深さの上限S と性能の関係
0.08

episodes/steps

0.07
0.06

S=00.05

S=1
S=20.04

S=30.03

S=4
S=1000.02
0.01
01

357

911 13 15 17 19 21 23 25 27 29 31 33 35 37 39

x 100,000 steps
スタックの上限 S が大きいほど収束は早くなる傾向を示している。

16

思考モードm4• 隣接するランドマーク間の最適移動経路は学習済みだとする。

m1• 離れたランドマーク間の最適移動経路の近似解は、隣接するランドマークをつなげば得られるはず。

m1

m2

m3

m3
m2

• この近似解は実際に行動しなくても「脳内シミュレーション」だけで見つけられる。[Singh 1992]– 一種のモデルベース強化学習– 演繹推論17

思考モードの実装• 思考モードはアルゴリズムのわずかな修正だ
けで実現可能• Q(s,g,a) を環境のモデルと見なして、時間を抽象化した脳内シミュレー
ション

18

あらかじめ簡単なタスクを事前学習■■■■■■■■■■■■■■■■■■■■■■■■■■・・ｍ・・・・・・・・・・・・・・■・・・・ｍ■■・・・・・■・・ｍ・・・・・・・ｍ■・・・・・■■・・・・・■■■■■・・・・■■■■・・・・・■■・・・・ｍ・・・・■・・・・・■・・・・・・・■■・・・・・■・・・■ｍ・・・ｍ■・・・・・・・■■・・・・・■・・・■■■・・・・・ｍ・・・・・■■・・・・・■・ｍ・・・■・・・・・■・・・・ｍ■■・・・ｍ■■・・・・・■・・・・・■・・・・・■■・・・・・■・・・・・■ｍ■・・・■・・・・・■■・・・・・■・・・■・■・■・・・・・・・・・■■・・・・・・・・・・ｍ■・・・・・・・■・・・■■■■■■・・・・・・・■■■■・・・・■ｍ・・■■・・ｍ■・・・・・・・・・・■・・・・■■■■■■・・・■・・ｍ・・・ｍ・・・■ｍ・・・・・・・■■・・・・・・・・・・■・・・■■■・・・・・・■■・・・・・・・・・・■・・・・・・・・・・・・■■・・・■・・・ｍ・・■・・・・・・・ｍ・・・・■■■■■■■■■■■■■■■■■■■■■■■■■■

ユークリッド距離が８以内にあるランドマークのペアの間の経路を事前学習
20x19=380個のペアのうちの60個

m はランドマーク

19

実験３：思考フェーズの長さ T と性能の関係
0.08

0.06
0.05

T=0

各エピソードの実行直前に、思考モードでエピソードを T 回実行

T=1

0.04

T=10

0.03

T=100

0.02
0.01
0
2001
2005
2009
2013
2017
2021
2025
2029
2033
2037
2041
2045
2049
2053
2057
2061
2065
2069
2073
2077
2081
2085
2089
2093
2097

episodes/steps0.07

x 1,000 steps
思考フェーズ（脳内シミュレーション）が十分長ければ、未経験のタスクであっても、近似解がゼロショットで得られている。

20

汎用人工知能につながる
RGoal アーキテクチャの有望な性質• 報酬最大化のために最適なサブゴールを選択する。 → 自律性・目的指向性• 帰納論理プログラミングと組み合わせると、サブルーチンの汎用性が増し、知識が増えるたびに解ける問題が組み合わせ爆発的に増える。 → 汎用性• 学習結果はサブゴールとスタックを内部状態に持つオートマトンと見なせる。
→ 万能性
21

まとめと今後• RGoal アーキテクチャ（スタックあり）を提案
人間の知能の２つの重要な特性を再現– 再帰的サブゴール設定– 時間を抽象化した高速なプランニング• 今後：– 記号推論（帰納論理プログラミング）と強化学習の統合– 脳型汎用人工知能の中核技術を目指す

22

予備スライド

23

先行研究との関係• 提案アーキテクチャは、階層型強化学習のいくつかのアイデアをシンプルな１つのアーキテクチャに統合– 可変時間分解能モデル（時間抽象） [Singh 1992]– 再帰的なサブゴール設定 [Kaelbling 1993]– 価値関数分解 [Singh 1992][Dietterich 2000]– 拡張状態行動空間 [Levy et al. 2011]24

スタックなし版での動作
@
Sg
G

m1m2

@
S

m1

gm2

G@
Sg
m1

m2

G

S

@
m1

m2

g
G

S

@
m1

g
m2

G

ここまではスタックあり版と同じ

おおもとのゴール G をサブゴールに再設定

25