jsai2023_kawamura

類似グラフ環境における事前知識を活用した 方策学習のための世界モデル 河村 和紀1、池之内 颯都3、石川 峻弥2、村上 綾菜4、 河野 慎1、松尾 豊1 (1. 東京大学、2. 電気通信大学、3. 愛媛大学、4. お茶の水女子大学)

グラフ環境における方策を学習する世界モデルの構築 背景 グラフで表される環境は多く、それらのグラフ環境は特徴的な性質を持つことが多い 課題 グラフ環境化で最適な方策を求める手法はいくつかあるが，類似した環境下で 体験した事前知識（グラフの性質）を新たな方策を学習する際に活用できていない 手法 グラフで表される環境に対する世界モデルを構築し，類似の環境に対する知識を獲得 した状態でより良い方策を学習する 評価 グラフで表される迷路ゲームをシミュレーションし，グラフに対する世界モデルが 事前知識を用いない単純な強化学習モデルよりも良い性能であることを示す 2

背景｜グラフで表される環境 ランダムに作られたグラフとは異なり何らかの特徴を持つことが多い ゲーム （迷路やグリッドワールド） タスク例：迷路を最短時間で抜ける経路の探索 特徴例：連結性、均一性 交通ネットワーク タスク例：最適なルートの探索（旅行時間、 交通量、燃料消費） 特徴例：スケールフリー性、クラスタリング ソーシャルネットワーク ウェブグラフ タスク例：情報の伝播や影響力の最大 特徴例：スモールワールド性、クラスタリング タスク例：特定のウェブページへの最短のクリック経路や、 特定の情報の最も効率的な検索経路 特徴例：スケールフリー性 3

関連研究｜グラフで表される環境化での方策の学習 Learning to Solve Combinatorial Optimization Problems on RealWorld Graphs in Linear Time [Drori+, 2020] グラフ上の可能な探索パスを列挙し， グラフ特徴を元に最適なパスを選択する 元のグラフ構造 グラフの探索可能パス 完全にランダムに生成される単発のグラフに対して最適な方策を決定するのであればこれでも良い 一方，現実の多くのグラフ構造には既に経験したことのあるような事前知識が含まれていることが多く， そのような知識をうまく利用することでより効率的に方策の学習ができる可能性がある 4

手法｜Graph-WM：グラフ環境に対応した世界モデル 環境 行動 観測 (グラフの一部) VGAE (V) 制御器 (C) 観測の変化 MDN-RNN (M) 行動 グラフ環境に対応した世界モデル 5

手法｜Graph-WM：グラフ環境に対応した世界モデル VAE（V）モデル：観測の潜在表現を獲得 Variational Graph Auto-Encoders [NeurIPS’16 BDL] 通常のVAEと同様事後 分布に正規分布を仮定 Multil-Layer GCN 𝑧 Inner Product Decoder Input Graph Output Graph 特徴行列 隣接行列 予測隣接行列 𝐗 ෩ 𝐀 𝐀 𝐿𝑜𝑠𝑠 = 𝐸𝑞(𝐙∣𝐗,𝐀)[log 𝑝(𝐀 ∣ 𝐙)] − 𝐾𝐿[𝑞(𝐙 ∣ 𝐗, 𝐀) ∥ 𝑝(𝐙)] 6

手法｜Graph-WM （グラフ環境に対する世界モデル） MDN-RNN（M）モデル：将来の潜在表現を予測 𝑧𝑡 𝑎𝑡 , 𝑧𝑡 ℎ𝑡+1 RNN 𝑎𝑡−1 , 𝑧𝑡−1 ℎ𝑡 RNN RNN ℎ𝑡−1 𝑧𝑡+2 𝑧𝑡+1 𝑎𝑡+1 , 𝑧𝑡+1 ℎ𝑡+2 7

実験｜Graph-WMを用いた迷路ゲームの攻略 環境 行動 観測 (グラフの一部) VGAE (V) 制御器 (C) MDN-RNN (M) 行動 グラフ環境に対応した世界モデル 8

実験｜Graph-WMを用いた迷路ゲームの攻略 エージェントは今いるノードの一つ先までを観測できる設定 エージェントの 現在位置 エージェントが ①へ移動 エージェントの 現在位置 エージェントの 1時刻前の位置 エージェントの 現在位置 エージェントが ②へ移動 エージェントの 1時刻前の位置 G 9

実験｜Graph-WMを用いた迷路ゲームの攻略 環境 行動 観測 (グラフの一部) VGAE (V) 制御器 (C) 観測の変化 MDN-RNN (M) 行動 グラフ環境に対応した世界モデル 10

データ（迷路）生成 スタートとゴールの位置を固定し、隣接するノードをエッジで結んだグラフを生成 S 1 2 3 4 5 6 7 G 迷路サイズ：3 • スタートノード，ゴールノードの位置は統一 • ノードにはどちらの方向にエッジが繋がっている かの特徴が含まれる • ゴールノードはy=1，他はy=0 11

実験｜比較手法 グラフ環境のエンベッドやエンベッド空間上での未来予測をせず，単純に グラフ特徴のみから直接アクションを出力する強化学習モデル（DQN） エージェントが次に どこに動くか environment グラフ構造で表された迷路 （エージェントは自分のいる場所のN個先の ノードしか観測できない状況とする） モデル baseline-RL • ２層のDNN（中間層50） • • • 学習率 0.01 割引率 0.99 バッチサイズ 32 ハイパーパラメータ 12

実験詳細 1. データ • 事前学習用にはランダムに4×4の10000個の迷路を生成 • コントローラの学習・評価用には上記と異なる1000個の迷路を生成 2. Vモデル • GVAE • 潜在変数次元：32 3. Mモデル • LSTM • 系列長：32 • 隠れ状態次元：256 4. コントローラ • 1層のNN 学習は全てAdam（初期パラメータ）でバッチサイズ32で実行 13

実験結果 環境全体が観測できる状態 環境の一部が観測できる状態 200トライアル後の結果 手法 平均ステップ数 500トライアル後の結果 手法 平均ステップ数 DQN 12.5 ± 1.6 DQN 32.6 ± 5.9 提案手法 9.3 ± 1.5 提案手法 24.9 ± 4.8 14

今後の展望 • より多様なグラフでの提案手法の検証 • より細かな報酬が与えられた場合の課題が解けるか？ • 異種グラフの課題が解けるか？ • エージェントがインタラクションするような課題が解けるか？ • VGAEの改良が有効かの検証 • VGAEの改良版であるARVGA [Pan+, IJCAI ‘18] や GraphSage [Bacciu+, GraphVAE [Simonovsky+, ICANN+ ‘18] へ変更した場合の性能の変化 ICML ‘18] ， 15

グラフ環境における方策を学習する世界モデルの構築 背景 グラフで表される環境は多く、それらのグラフ環境は特徴的な性質を持つことが多い 課題 グラフ環境化で最適な方策を求める手法はいくつかあるが，類似した環境下で 体験した事前知識（グラフの性質）を新たな方策を学習する際に活用できていない 手法 グラフで表される環境に対する世界モデルを構築し，類似の環境に対する知識を獲得 した状態でより良い方策を学習する 評価 グラフで表される迷路ゲームをシミュレーションし，グラフに対する世界モデルが 事前知識を用いない単純な強化学習モデルよりも良い性能であることを示す 16