NonZero: 상호작용 기반 탐색을 통한 다중 에이전트 몬테카를로 트리 검색

요약

NonZero는 상호작용 기반 제안 규칙(interaction-guided proposal rule)을 도입하여 다중 에이전트 몬테카를로 트리 검색(MCTS)의 확장성을 크게 향상시킨 방법론입니다. 기존 MCTS가 연립 행동 공간의 지수적 증가 문제에 직면했던 것과 달리, NonZero는 상호작용 점수를 활용하여 계산 가능한 방식으로 다중 에이전트 탐색을 수행합니다. 이 접근 방식은 로컬 편차를 밴디트 문제로 공식화하고 근사 그래프-로컬 최적점에 도달하는 보장된 규칙을 제공함으로써 높은 샘플 효율성과 성능 개선을 입증했습니다.

핵심 포인트

• 다중 에이전트 MCTS의 주요 병목 현상인 연립 행동 공간의 지수적 증가 문제를 해결합니다.
• 상호작용 점수를 사용하여 단일 및 다중 에이전트 간의 협력적 이익을 측정하는 독특한 평가 기준을 제시합니다.
• 로컬 편차를 밴디트 문제로 공식화하고, 선형 이하의 로컬-반감 보장(sublinear local-regret guarantee)을 갖는 제안 규칙을 유도했습니다.
• MatGame, SMAC 등 다양한 환경에서 기존 베이스라인 대비 샘플 효율성과 최종 성능 모두를 개선함을 실험적으로 입증했습니다.