強化学習におけるマクロを用いた行動系列の獲得

強化学習におけるマクロを用いた
行動系列の獲得
北海道大学大学院工学研究科
金澤勇樹
発表内容
 研究背景
 学習システム設計方針
 マクロの実装方法
 実装例
 まとめ
2015/9/30
第5回WINGS
強化学習におけるマクロを用いた行動系列獲得
2
研究背景
 強化学習


自律的に環境に適応する機械学習の一種
報酬入力のみを手掛りとして学習
マルチエージェント系や実制御問題に対して有効
在庫管理・生産ライン最適化問題（Wang, Mahadevan 99）
倒立振子の振り上げ安定化問題（Doya 96）
不完全な観測、非マルコフ的な振舞い
• 学習困難である問題が想定
2015/9/30
第5回WINGS
強化学習におけるマクロを用いた行動系列獲得
3
関連研究（１）
 学習困難な問題に対して

経験強化型アプローチ（利益共有法など）
 観測集合から行動集合への確率分布関数のみを推定
 一般に収束性は保証されない

2015/9/30
メモリベース法（Chirisman 92, McCallum 95 ）
 状態推定器を用いて、経験から環境状態を推定
 計算資源の範囲に依存
第5回WINGS
強化学習におけるマクロを用いた行動系列獲得
4
関連研究（２）

階層的強化学習（Barto 03）
 下位階層での部分観測性を上位階層で補う
Precupらはマクロを用いてタスクの階層化を実現
マクロ
状態空間の探索補助
ex. プランニング・・・既存プランを汎化したもの
問題解決
・・・推論のステップを一つにまとめたもの
強化学習
2015/9/30
第5回WINGS
行動制御を提供するもの
強化学習におけるマクロを用いた行動系列獲得
5
マクロとは
（例）
一回周って
Bow！
三回周って
Bow！
？
Action：｛前進、右転回、左転回、Bow ｝
+
Macro：｛一回周る｝
 どのようにして「一回周る」を表現するか？
 どのようにして「一回周る」を獲得するか？
2015/9/30
第5回WINGS
強化学習におけるマクロを用いた行動系列獲得
6
研究目的
 汎用的な行動制御を提供可能なマクロの設計
 経験を基としたマクロ生成方法の提案
マクロを利用した
強化学習エージェントの実装
 学習困難な問題
2015/9/30
第5回WINGS
• 簡便かつ有効に対処
• 学習効率の向上
強化学習におけるマクロを用いた行動系列獲得
7
設計方針
 エージェントと環境の相互作用図
Agent
Environment
Experience
make
Observation
select
Action
2015/9/30
Chain Data Memory
Reward
第5回WINGS
Action control
Macro
強化学習におけるマクロを用いた行動系列獲得
8
価値更新方法
 エージェントはどのマクロで行動制御を行うかを選択
マクロによる行動制御が終了する毎に更新
（マクロの行動制御は任意時間ステップ）
：観測状態
：マクロ
：割引報酬和
：
の時間ステップ数
• 観測状態 - マクロ対の価値を更新
この価値によって方策が決定
2015/9/30
第5回WINGS
強化学習におけるマクロを用いた行動系列獲得
9
実装マクロの構造
 マクロ･･･行動制御を提供するもの
木構造で表現
Primitive action がラベル付け
• Primitive Action Node ･･･
Macro
• Macro Action Tree
･･･他のマクロの組合せで表現

･･･

，
は観測
各々異なる観測がラベル付けされる

2015/9/30
第5回WINGS
で選択可能なマクロ
強化学習におけるマクロを用いた行動系列獲得
は、
で選択可能なマクロ
10
実装マクロの行動制御（１）
Macro
制御（PAD図）
処理
順次
繰返し
･･･
選択
2015/9/30
第5回WINGS
強化学習におけるマクロを用いた行動系列獲得
11
実装マクロの行動制御（２）
 構造化定理
・適正プログラムであれば、「順次」「繰返し」「選択」の３つの基本構造と
その組み合わせだけで、どのような処理も記述できる。
「順次」「繰返し」「選択」の処理が可能なマクロは
（ある程度）汎用的な行動制御が可能ではないか？
2015/9/30
第5回WINGS
強化学習におけるマクロを用いた行動系列獲得
12
実装マクロ生成方法（１）
生成の手順

Step 1: 学習中に発生したデータを蓄積
データ：（観測，マクロ，割引報酬和，実行ステップ）
Step 2: N個のデータを蓄積後、すべてのマクロに対し：
ⅰ）可能な観測マクロ対を付加
ⅱ）付加されたマクロを評価
Step 3：評価結果によってマクロを作成し、Step 1へ戻る
2015/9/30
第5回WINGS
強化学習におけるマクロを用いた行動系列獲得
13
実装マクロ生成方法（２）
新規作成：
条件：
蓄積データより推定
 条件が満たされた場合、確率
 利用可能なマクロの上限を下式で限定
で生成
Primitive Action 数：
長さのマクロの数：
2015/9/30
第5回WINGS
強化学習におけるマクロを用いた行動系列獲得
14
実装マクロ生成方法（３）
結合：
条件：根ノードが一致しているマクロが存在
 新たに次の観測までのマクロが作成
先に作成された方が優先
2015/9/30
第5回WINGS
強化学習におけるマクロを用いた行動系列獲得
15
実装例（１）ｰ State Office World
Littman’s State Office World
G
価値更新手法： Sarsa（λ）
学習率： 0.1
割引率： 0.9
2015/9/30
第5回WINGS
States:
89（88＋1）
位置×向き（N，S，E，W）
Actions:
5
（ stay，move，
turn left，turn right,
turn around ）
Observations:
16（14）
・前後左右の壁の有無を観測
・正しい観測が得られる確率0.7
（確率0.3でランダムな観測）
Rewards:
ゴール到達： + 1.0
その他： 0.0
Initial State:
ランダム
強化学習におけるマクロを用いた行動系列獲得
16
実装方法ｰ State Office World
 比較対象
 Sarsa(0.9)
 Sarsa(0.9) + Macro
･･･マクロを作成
 Sarsa(0.9) + Good Macro ･･･理想的なマクロを付与
前：前進
後： 180度回転
• 理想的なマクロ（１０個）
右：右90度回転
左：左90度回転
観測：
マクロ：
2015/9/30
a
b
c
d
e
f
g
h
i
j
右
前
右
左
後
右
前
右
左
後
前
a
b
b
b
前
f
g
g
g
第5回WINGS
強化学習におけるマクロを用いた行動系列獲得
17
実装結果ｰ State Office World
500
Sarsa（0.9）
Sarsa（0.9）+ Macro
Sarsa（0.9）+ Good Macro
450
Steps to task completion
400
350
300
250
200
150
100
50
0
0
100
200
300
400
500
600
700
800
900
1000
Trials
2015/9/30
第5回WINGS
強化学習におけるマクロを用いた行動系列獲得
18
結果考察
 事前知識として適当なマクロを設定した場合
エージェントは付与したマクロを用いた行動制御
学習効率向上
提案マクロ構造が妥当
 マクロを設定しない場合
エージェントはマクロを作成しながら環境に適応
徐々に事前知識を
与えた結果に接近
2015/9/30
第5回WINGS
提案マクロ生成方法が妥当
強化学習におけるマクロを用いた行動系列獲得
19
実装例（２）犬と飼い主の問題
4
5
1
1
5
2
2
6
2
4
3
3
7
6
5
8
States:
32
位置×向き（N，S，E，W）
Actions:
6
（ stay，move forward，
turn left，turn right, turn around
bow）
Observations:
6
Rewards:
１周＋Bow： 10.0
２周＋Bow： 100.0
３週＋Bow： 1000.0
内or外： -0.1
その他： 0.0
Initial State:
ランダム
2015/9/30
第5回WINGS
強化学習におけるマクロを用いた行動系列獲得
20
実装結果－犬と飼い主の問題
2.5
rewards par step
2
1.5
1
Sarsa(0.9)
0.5
Sarsa(0.9)+Macro
0
0
50000
100000
150000
200000
250000
300000
steps
2015/9/30
第5回WINGS
強化学習におけるマクロを用いた行動系列獲得
21
結果考察
提案エージェントは「一回周ってBow」マクロを獲得
獲得したマクロを選択することにより、
報酬（+10）までの行動制御が可能
局所的な報酬獲得の繰返し
初期段階における
報酬獲得効率上昇
ある程度段階が進むと
比較性能が悪化
 提案マクロ生成方法に改善の余地が有る
ex. サブゴールの考慮
2015/9/30
第5回WINGS
強化学習におけるマクロを用いた行動系列獲得
22
まとめと今後の課題
 まとめ
 汎用的な行動制御を提供可能なマクロの提案
 経験を基としたマクロ生成方法の提案

提案マクロを利用した強化学習エージェントの実装
• 非マルコフ性を有する環境での有効性を確認
 今後の課題
 提案マクロ生成方法の改善
 提案マクロの特徴及び限界についての考察
2015/9/30
第5回WINGS
強化学習におけるマクロを用いた行動系列獲得
23
参考文献






Barto, A. G., Mahadevan, S.,
“Recent advances in hierarchical reinforcement learning,”
Discrete-Event Systems journal, (2003).
Chirisman, L.,
“Reinforcement Learning with Perceptual Aliasing,”
10th National Conference on AI, (1992).
Doya, K.,
“Efficient nonlinear control with actor-tutor architecture,”
Advances in Neural Information Prosessing Systems, (1996).
McCallum, R. A.,
“Instance-based utile distinctions for reinforcement learning with hidden state,”
Proc. of 12th Intern Conf. on Machine Learning, (1995).
Precup, D. and Sutton, R. S.,
“Theoretical results on reinforcement learning with temporal resolution models,”
Proc. of 10th European Conf. on Machine Learning, (1998)
Wang, G. and Mahadevan, S.,
“Hierarchical optimization of policy-coupled semi-markov decision prosesses,”
Proc. of 16th Intern Conf. on Machine Learning, (1999).
2015/9/30
第5回WINGS
強化学習におけるマクロを用いた行動系列獲得
24

Download Report