ニューイヤーランチ会論文紹介

klis3年 鈴木史麿

内容

• 強化学習の基礎的なアルゴリズムの論文紹介
  → 自分もあやふやだったので
• MAPFの最新の論文の紹介
  → AISTでやっていることを共有

紹介する論文

• Proximal Policy Optimization Algorithms
• Graph Attention-Guided Search for Dense Multi-Agent Pathfinding

Proximal Policy Optimization Algorithms(2017)

John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, Oleg Klimov

流れ

• 強化学習(RL)の基礎を復習
• Policy Gradient と Actor-Critic の位置づけ
• TRPO の課題を理解
• PPO の目的関数を数式で理解する

強化学習の基本設定

• 状態:
• 行動:
• 報酬:
• 方策:

• 目的関数:

Policy Gradient の基本

方策を直接最適化する：

• : 時刻 からの累積報酬
• REINFORCE の基本式

そしてパラメータを更新

分散削減：Advantage 関数

• 状態価値関数:

• Advantage:

• 勾配は次の形に書ける：

Actor-Critic 法

• Actor: 方策
• Critic: 価値関数

TD 誤差による Advantage 近似：

→ 分散が小さく、安定した学習が可能

ActorとCriticの更新

• Actor

• Critic

Policy Gradient の課題

• 学習が不安定
• 一度集めたデータで 1回しか更新できない
• 更新が大きすぎると性能崩壊

→ 方策の更新量を制御したい

Trust Region Policy Optimization (TRPO)

制約付き最適化問題：

subject to:

→ 直接解くことは難しい(非線形・非凸であるからなど)
→ そのため近似して解く

TRPO の問題点

• KL 制約の二次近似が必要
• 共役勾配法など実装が複雑

→ より簡単な trust region が必要

PPO の基本アイデア

TRPO の「安全な更新」を

• KL制約ではなく目的関数で実現
• ミニバッチで複数 epoch 更新可能

確率比

• 新旧方策の変化量を表す

PPO の Clipped Objective

→ 変化量が大きいとclip()で制限する

Clip の役割

→ それ以上の改善・悪化を 打ち切る

→ 方策を「近接(proximal)」に保つ

PPO の直感

• 
  → 行動確率を適度に増やす
• 
  → 行動確率を適度に減らす

→ 極端な更新を防ぐ仕組み

Value Loss & Entropy Bonus

実際に最適化する目的関数：

• を最大化したい
• とはハイパラ
• 探索

PPO アルゴリズム

1. 方策 で軌道収集
   • 軌道: tステップの集合
2. Advantage を計算
3. データをミニバッチ化
4. を複数 epoch 最適化
   • clipがあるため複数回データを使いまわせる
5. 方策更新

PPO の特徴

• TRPO 並みの安定性
• 実装が非常に簡単
• Adam / SGD と相性良好
• 実用 RL のデファクトスタンダード

実験結果(論文)

• MuJoCo(連続制御)
• Atari(離散制御)
• A2C / TRPO を多くのタスクで上回る

まとめ

• PPO = 安定な Policy Gradient
• 核心は Clipped Objective
• Actor-Critic と自然に統合
• 現代 RL の基盤技術

Graph Attention-Guided Search for Dense Multi-Agent Pathfinding(2025)

Rishabh Jain, Keisuke Okumura, Michael Amir, Amanda Prorok

背景：Multi-Agent Pathfinding(MAPF)

MAPF問題

• 複数エージェントが
  • 同一セル占有なし
  • エッジ衝突なし
• 各自のスタート → ゴールへ移動
• 目的：総コスト(makespan / sum of costs)最小化

応用例

• 倉庫ロボット
• 群ロボット
• ゲームAI

MAPFの難しさ

• エージェント数 に対して状態空間が 指数的
• 特に 高密度(dense)環境では
  • 局所的な衝突回避が全体最適を破壊
  • デッドロックが頻発

→ 最適性・計算時間・スケーラビリティのトレードオフ

MAPF 解法の系譜

探索ベース手法

• 完備性・最適性保証
• 例：CBS, LaCAM

学習ベース手法

• 完全性なし・失敗例あり
• 例：GNN, Transformer

→「学習で探索を導く」ハイブリッドが理想かもしれない

LaCAM(lazy constraints addition search for MAPF)

特徴

• 探索ベース MAPF アルゴリズム
• エージェントの優先度順序を探索
• 局所的な衝突を抑えつつスケーラブル

強み

• 完備性あり
• 大規模問題に比較的強い

MAGAT

MAGATとは

• MAPF専用の GNN ポリシー
• ノード：エージェント
• エッジ：近傍関係
• Graph Attention により相互作用を学習

出力

• 各エージェントの行動分布(次の移動)

課題

• デッドロック
• グローバル整合性不足

問題意識(この論文の動機)

なぜ過去の「学習誘導探索」は失敗してきたのか？

• 学習ヒューリスティックが 不安定
• 探索アルゴリズムの理論保証を破壊
• 密集環境で誤誘導 → 探索破綻

→ 慎重に設計された統合が必要

経路計画のヒューリスティックとは？

探索アルゴリズムが「目的地まであとどれくらいで着けそうか」や「この状況ではどちらに向かえばいいのか」を予測するための「目安」や「ヒント」

• 例
  • 直線距離
  • cost-to-go(ゴールまでのコスト)
  • ニューラルネットの出力

提案手法：LaGAT

LaGAT = LaCAM + GAT-based Heuristic

• MAGAT を改良した MAGAT+
• LaCAM の探索を
  • 学習済みヒューリスティックで誘導
• 完全性は LaCAM 側で保証

「探索の骨格は壊さず、賢く案内する」

MAGAT+ の改良点

• より表現力の高い Graph Attention
• エージェント間の密な相互作用を明示的にモデル化
• Dense MAPF に特化した設計

ポイント

• 行動そのものを強制しない
• あくまで「探索の優先度」を提示

学習戦略：Pre-train → Fine-tune

1. 事前学習

   • 汎用 MAPF 環境
   • 一般的な協調パターンを獲得

2. ファインチューニング

   • 対象マップ特化
   • 密集構造に適応

→ 実環境・特定レイアウトへの適応が可能

安全装置：デッドロック検出

問題

• 学習ヒューリスティックは誤る

対策

• 探索中にデッドロックを検出
• MAGAT 誘導を一時停止
• 通常の LaCAM 探索へフォールバック

完備性・堅牢性を維持

実験設定

• 高密度 MAPF ベンチマーク
• エージェント数：多
• 狭い通路・ボトルネックあり

比較手法

• 純探索(LaCAM)
• 純学習(MAGAT)

実験結果

結果

• LaGAT が最良性能
  • 解の質(near-optimal)
  • 成功率
  • 計算時間

特に

• Dense 環境で顕著な改善
• 学習単体・探索単体の弱点を補完

なぜうまくいったのか？

• 学習は「決定」ではなく「誘導」
• 探索の理論保証を維持
• デッドロック対策を明示的に設計

→ ハイブリッド設計の教科書的成功例

本論文の貢献

• 学習 × 探索の統合設計指針を提示
• 「学習誘導探索は使える」ことを実証

まとめ

• MAPFの難所：高密度・強結合
• LaGAT：
  • 探索の強さ × 学習の直感
• ハイブリッドは強力

AlphaZeroもハイブリッド

紹介した論文の振り返り

• Proximal Policy Optimization Algorithms
  → 学習の安定性を高めた、方策勾配型の強化学習アルゴリズム
• Graph Attention-Guided Search for Dense Multi-Agent Pathfinding
  → MAPFにおける探索 + 学習誘導 アルゴリズム

周辺の論文の紹介(リンクのみ)

RL, MARL

• Trust Region Policy Optimization(2015)
• The Surprising Effectiveness of PPO in Cooperative, Multi-Agent Games
  (2021)
• A Review of Cooperation in Multi-agent Learning(2023)
• HyperMARL: Adaptive Hypernetworks for Multi-Agent RL(2024)

周辺の論文の紹介(リンクのみ)

MAPF

• Priority Inheritance with Backtracking for Iterative Multi-agent Path Finding
  (2019)
• LaCAM: Search-Based Algorithm for Quick Multi-Agent Pathfinding(2022)
• MAPF-GPT: Imitation Learning for Multi-Agent Pathfinding at Scale(2024)