NonZero：相互作用に導かれた探索によるマルチエージェントMCTS
arXiv cs.LG / 2026/5/4
📰 ニュースModels & Research
要点
- マルチエージェントのモンテカルロ木探索（MCTS）は、同時に取り得る共同行動の組合せが指数的に増えるため、実用的な探索予算の下では探索効率が低くなりがちです。
- NonZeroは、共同行動全体の空間を直接探索する代わりに、低次元の非線形表現上でサロゲートに導かれた選択を行うことで、探索を扱いやすくします。
- 提案手法は相互作用を考慮した提案ルールを用い、単独エージェントの逸脱は予測される利得で順位付けし、2者の逸脱は混合差分の相互作用指標で評価して協調による利得を捉えます。
- NonZeroは候補提案を、局所的な逸脱に関するバンディット問題として定式化し、共同行動を列挙せずにグラフ局所最適へ近似的に到達するための局所レグレットが準線形で抑えられることを保証します。
- MatGame、SMAC、SMACv2での実験では、探索予算を揃えた条件で、強力なモデルベース／モデルフリーのベースラインに比べてサンプル効率と最終性能が向上したことが示されます。
