ポテンシャルゲームと低ランクな方策構造によるマルチエージェント到達回避MDP

抽象: 本研究では、有限ホライズンのマルチエージェント到達回避（reach-avoid）マルコフ決定過程（MDP）を、\emph{局所フィードバック方策（local feedback policies）}によって最適化する。グローバルなフィードバック方策の解は全体としての最適性をもたらすが、その通信複雑度、メモリ使用量、計算複雑度はいずれもエージェント数に対して指数的に増大する。そこで、この指数的な依存を緩和するために、解の探索空間を局所フィードバック方策に制限し、局所フィードバック方策がグローバルなフィードバック方策のランク1の因数分解（rank-one factorizations）であることを示す。これにより、通信複雑度とメモリ使用量を低減するための原理に基づくアプローチを提供する。さらに、局所フィードバック方策上でのマルチエージェント到達回避MDPがポテンシャルゲーム構造を有する可能性を示すことで、逐次的な最良応答（iterative best response）が、決定論的ナッシュ均衡への収束が保証された、計算可能なマルチエージェント学習スキームであることを示し、結合状態空間上での乗法的動的計画法（multiplicative dynamic program: DP）により各エージェントの最良応答を導出する。異なるMDPおよびエージェント集合に対する数値シミュレーションでは、最適なグローバル到達回避目的に対する近似誤差を維持したまま、ピーク時のメモリ使用量とオフライン計算複雑度が大幅に低減されることを示す。