복잡한 계획 문제 해결에 중요한 역할을 하는 몬테카를로 트리 탐색(MCTS)은 다중 에이전트 계획에 적용 시, 에이전트 수가 증가함에 따라 기하급수적으로 증가하는 방대한 조합의 행동 공간에 직면합니다. 본 논문에서는 joint-action return에 대한 저차원 표현 구조를 활용하여 복잡한 다중 에이전트 계획에서 효율적인 MCTS를 가능하게 하는 새로운 접근 방식인 MALinZero를 제안합니다. MALinZero는 joint-action returns를 contextual linear bandit 문제 공식으로 표현할 수 있는 저차원 공간에 투영합니다. 저차원 보상 함수에 대한 MALinZero의 후회(regret)를 분석하고, sub-modular objective를 최대화하여 joint action selection을 위한 (1-1/e)-근사 알고리즘을 제안합니다. MALinZero는 matrix games, SMAC, SMACv2와 같은 다중 에이전트 벤치마크에서 모델 기반 및 모델 프리 다중 에이전트 강화 학습 baseline보다 빠른 학습 속도와 더 나은 성능을 보여줍니다.
