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

몬테 카를로 트리 검색 (Monte Carlo Tree Search, MCTS) 은 협력적 다중 에이전트 도메인에서 확장 시 연립 행동의 지수적으로 큰 집합을 고려해야 하므로 스케일링이 매우 저조하며, 이는 현실적인 검색 예산 하에서 탐색을 심각하게 제한합니다. 우리는 상호작용 기반 제안 규칙 (interaction-guided proposal rule) 을 사용하여 차원수가 낮은 비선형 표현에 대해 대리자 (surrogate) 를 안내하는 선택을 실행함으로써 다중 에이전트 MCTS 를 tractable(tractable: 계산 가능/실현 가능) 하게 만든 NonZero를 제안합니다. 우리의 탐색은 상호작용 점수 (interaction score) 를 사용합니다: 단일 에이전트의 편차는 예측된 이득에 따라 순위가 매겨지며, 두 에이전트의 편차는 협력적 이익을 드러내되 단일 에이전트가 단독으로 개선할 수 없는 경우에도 혼합 차분 측정 (mixed-difference measure) 을 통해 점수가 부여됩니다. 우리는 로컬 편차 (local deviations) 에 대한 밴디트 문제 (bandit problem) 로 후보 제안 (candidate proposal) 을 공식화하고, 연립 행동 공간을 열거하지 않고 근사 그래프 로컬 최적점 (approximate graph-local optima) 에 도달하기 위해 선형 이하의 로컬-반감 보장 (sublinear local-regret guarantee) 을 갖는 NonZero 제안 규칙을 유도합니다. 경험적으로, 매칭된 검색 예산 하에서 NonZero 는 MatGame, SMAC, 및 SMACv2 에서 강력한 모델 기반 (model-based) 및 모델 자유 (model-free) 베이스라인에 비해 샘플 효율성 및 최종 성능을 개선합니다.