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

Presentation on theme: "強化学習におけるマクロを用いた 行動系列の獲得"— Presentation transcript:

1 強化学習におけるマクロを用いた 行動系列の獲得
北海道大学　大学院工学研究科 金澤 勇樹　

2 発表内容 研究背景 学習システム設計方針 マクロの実装方法 実装例 まとめ 2019/2/28
第5回WINGS　　　　　　強化学習におけるマクロを用いた行動系列獲得

3 研究背景 強化学習 自律的に環境に適応する機械学習の一種 報酬入力のみを手掛りとして学習 マルチエージェント系や実制御問題に対して有効
　強化学習 　自律的に環境に適応する機械学習の一種 　報酬入力のみを手掛りとして学習 マルチエージェント系や実制御問題に対して有効 在庫管理・生産ライン最適化問題（Wang, Mahadevan 99） 倒立振子の振り上げ安定化問題（Doya 96） 不完全な観測、非マルコフ的な振舞い 　学習困難である問題が想定 2019/2/28 第5回WINGS　　　　　　強化学習におけるマクロを用いた行動系列獲得

4 関連研究（１） 学習困難な問題に対して 経験強化型アプローチ（利益共有法など） 観測集合から行動集合への確率分布関数のみを推定
　経験強化型アプローチ（利益共有法など）　 観測集合から行動集合への確率分布関数のみを推定 一般に収束性は保証されない 　メモリベース法（Chirisman 92, McCallum 95 ）　 状態推定器を用いて、経験から環境状態を推定 計算資源の範囲に依存 2019/2/28 第5回WINGS　　　　　　強化学習におけるマクロを用いた行動系列獲得

5 関連研究（２） 階層的強化学習（Barto 03） 下位階層での部分観測性を上位階層で補う
Precupらはマクロを用いてタスクの階層化を実現 強化学習 行動制御を提供するもの マクロ 　状態空間の探索補助 　　 ex. プランニング　・・・　既存プランを汎化したもの 　　　　 問題解決　　　・・・　推論のステップを一つにまとめたもの 2019/2/28 第5回WINGS　　　　　　強化学習におけるマクロを用いた行動系列獲得

6 マクロとは （例） 一回周ってBow！ ？ + 三回周ってBow！ どのようにして「一回周る」を表現するか？
Action：｛ 前進、右転回、左転回、Bow ｝ Macro：｛ 一回周る ｝ + 三回周ってBow！ どのようにして「一回周る」を表現するか？ どのようにして「一回周る」を獲得するか？ 2019/2/28 第5回WINGS　　　　　　強化学習におけるマクロを用いた行動系列獲得

7 研究目的 汎用的な行動制御を提供可能なマクロの設計 経験を基としたマクロ生成方法の提案 マクロを利用した 強化学習エージェントの実装
　汎用的な行動制御を提供可能なマクロの設計 　経験を基としたマクロ生成方法の提案 マクロを利用した 強化学習エージェントの実装 簡便かつ有効に対処 学習効率の向上 学習困難な問題 2019/2/28 第5回WINGS　　　　　　強化学習におけるマクロを用いた行動系列獲得

8 設計方針 エージェントと環境の相互作用図 Agent Environment Experience Chain Data Memory
　エージェントと環境の相互作用図 Agent Experience select Chain Data Memory Action control make Macro Environment Reward Observation Action 2019/2/28 第5回WINGS　　　　　　強化学習におけるマクロを用いた行動系列獲得

9 価値更新方法 エージェントはどのマクロで行動制御を行うかを選択 この価値によって方策が決定 マクロによる行動制御が終了する毎に更新
（マクロの行動制御は任意時間ステップ） 　エージェントはどのマクロで行動制御を行うかを選択 ：　観測状態 ：　マクロ ：　割引報酬和 ：　　　の時間ステップ数 　観測状態 - マクロ対の価値を更新 この価値によって方策が決定 2019/2/28 第5回WINGS　　　　　　強化学習におけるマクロを用いた行動系列獲得

10 実装マクロの構造 木構造で表現 マクロ ･･･ 行動制御を提供するもの Primitive action がラベル付け Macro
　Primitive Action Node　･･･　　 　マクロ　･･･　行動制御を提供するもの Primitive action がラベル付け Macro 　Macro Action Tree　　　･･･　 他のマクロの組合せで表現 木構造で表現 　　，　　 は観測　　で選択可能なマクロ 各々異なる観測がラベル付けされる 　　　　　　　　　　　は、　　　 　　　　　　　　　　　　で選択可能なマクロ ･･･ 2019/2/28 第5回WINGS　　　　　　強化学習におけるマクロを用いた行動系列獲得

11 実装マクロの行動制御（１） Macro 制御（PAD図） 処理 順次 繰返し 選択 ･･･ 2019/2/28
第5回WINGS　　　　　　強化学習におけるマクロを用いた行動系列獲得

12 実装マクロの行動制御（２） 構造化定理 「順次」「繰返し」「選択」の処理が可能なマクロは （ある程度）汎用的な行動制御が可能ではないか？
　構造化定理 　・ 適正プログラムであれば、「順次」「繰返し」「選択」の３つの基本構造と 　 その組み合わせだけで、どのような処理も記述できる。 「順次」「繰返し」「選択」の処理が可能なマクロは （ある程度）汎用的な行動制御が可能ではないか？ 2019/2/28 第5回WINGS　　　　　　強化学習におけるマクロを用いた行動系列獲得

13 実装マクロ生成方法（１） 生成の手順 Step 1: 学習中に発生したデータを蓄積 データ： （ 観測，マクロ，割引報酬和，実行ステップ ）
　生成の手順 Step 1:　学習中に発生したデータを蓄積 　データ：　（　観測，マクロ，割引報酬和，実行ステップ　） Step 2: 　N個のデータを蓄積後、すべてのマクロに対し： ⅰ）可能な観測マクロ対を付加 ⅱ）付加されたマクロを評価 Step 3：　評価結果によってマクロを作成し、Step 1へ戻る 2019/2/28 第5回WINGS　　　　　　強化学習におけるマクロを用いた行動系列獲得

14 実装マクロ生成方法（２） 新規作成： 条件： 蓄積データより推定 条件が満たされた場合、確率 で生成 利用可能なマクロの上限を下式で限定
　条件が満たされた場合、確率 　　　　　　　で生成 　利用可能なマクロの上限を下式で限定 Primitive Action 数： 長さ のマクロの数： 2019/2/28 第5回WINGS　　　　　　強化学習におけるマクロを用いた行動系列獲得

15 実装マクロ生成方法（３） 結合： 条件： 根ノードが一致しているマクロが存在 先に作成された方が優先 新たに次の観測までのマクロが作成
条件：　根ノードが一致しているマクロが存在 　新たに次の観測までのマクロが作成 　　　　　先に作成された方が優先 2019/2/28 第5回WINGS　　　　　　強化学習におけるマクロを用いた行動系列獲得

16 実装例（１） ｰ State Office World
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: 　 ランダム Littman’s State Office World G 価値更新手法：　Sarsa（λ） 　　　　 学習率：　0.1 　　　　 割引率：　0.9 2019/2/28 第5回WINGS　　　　　　強化学習におけるマクロを用いた行動系列獲得

17 実装方法 ｰ State Office World
　比較対象 Sarsa(0.9) Sarsa(0.9) + Macro ･･･ マクロを作成 Sarsa(0.9) + Good Macro ･･･ 理想的なマクロを付与 前：　前進 右：　右90度回転 後：　180度回転　　左：　左90度回転 　理想的なマクロ（１０個） 観測： a b c d e f g h i j マクロ： 右 前 右 左 後 右 前 右 左 後 a b b b f g g g 前 前 2019/2/28 第5回WINGS　　　　　　強化学習におけるマクロを用いた行動系列獲得

18 実装結果 ｰ State Office World
Steps to task completion Sarsa（0.9） Sarsa（0.9）+ Macro Sarsa（0.9）+ Good Macro 50 100 150 200 250 300 350 400 450 500 600 700 800 900 1000 Trials 2019/2/28 第5回WINGS　　　　　　強化学習におけるマクロを用いた行動系列獲得

19 結果考察 事前知識として適当なマクロを設定した場合 マクロを設定しない場合 エージェントは付与したマクロを用いた行動制御 学習効率向上
　事前知識として適当なマクロを設定した場合 エージェントは付与したマクロを用いた行動制御 学習効率向上 提案マクロ構造が妥当 　マクロを設定しない場合 エージェントはマクロを作成しながら環境に適応 徐々に事前知識を 与えた結果に接近 提案マクロ生成方法が妥当 2019/2/28 第5回WINGS　　　　　　強化学習におけるマクロを用いた行動系列獲得

20 実装例（２） 犬と飼い主の問題 1 2 3 4 5 6 5 1 6 2 4 8 3 7 States: 32 位置×向き（N，S，E，W）
実装例（２）　犬と飼い主の問題 States:　 　　32 位置×向き（N，S，E，W） Actions:　 　　6 （ stay，move forward， turn left，turn right, turn around bow） Observations: Rewards: 　　１周＋Bow： 10.0 　　２周＋Bow： 100.0 　　３週＋Bow： 　　内or外： -0.1 　　その他：　0.0 Initial State: 　 ランダム 1 2 3 4 5 6 5 1 6 2 4 8 3 7 2019/2/28 第5回WINGS　　　　　　強化学習におけるマクロを用いた行動系列獲得

21 実装結果 － 犬と飼い主の問題 Sarsa(0.9) Sarsa(0.9)+Macro steps 0.5 1 1.5 2 2.5
実装結果　－　犬と飼い主の問題 steps 0.5 1 1.5 2 2.5 50000 100000 150000 200000 250000 300000 rewards par step Sarsa(0.9) Sarsa(0.9)+Macro 2019/2/28 第5回WINGS　　　　　　強化学習におけるマクロを用いた行動系列獲得

22 結果考察 提案エージェントは「一回周ってBow」マクロを獲得 獲得したマクロを選択することにより、 報酬（+10）までの行動制御が可能
初期段階における 報酬獲得効率上昇 ある程度段階が進むと 比較性能が悪化 局所的な報酬獲得の繰返し 　提案マクロ生成方法に改善の余地が有る 　　 ex.　サブゴールの考慮 2019/2/28 第5回WINGS　　　　　　強化学習におけるマクロを用いた行動系列獲得

23 まとめと今後の課題 まとめ 今後の課題 汎用的な行動制御を提供可能なマクロの提案 経験を基としたマクロ生成方法の提案
　汎用的な行動制御を提供可能なマクロの提案 　経験を基としたマクロ生成方法の提案 　提案マクロを利用した強化学習エージェントの実装 　非マルコフ性を有する環境での有効性を確認 　提案マクロ生成方法の改善 　提案マクロの特徴及び限界についての考察 2019/2/28 第5回WINGS　　　　　　強化学習におけるマクロを用いた行動系列獲得

24 参考文献 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). 2019/2/28 第5回WINGS　　　　　　強化学習におけるマクロを用いた行動系列獲得