본 논문은 다수 에이전트 강화 학습(MARL)에서 공동 상태 및 행동 공간의 크기가 에이전트 수에 따라 기하급수적으로 증가하는 문제를 해결하기 위해 새로운 알고리즘 $\texttt{SUBSAMPLE-MFQ}$를 제안합니다. $\texttt{SUBSAMPLE-MFQ}$는 $n$개의 에이전트 시스템에 대해 $k \leq n$인 임의의 $k$에 대해 다항 시간 내에 정책을 학습하며, 서브샘플링된 에이전트 수 $k$가 증가함에 따라 최적 정책에 $\tilde{O}(1/\sqrt{k})$의 오차로 수렴함을 증명합니다. 특히, 이 경계는 에이전트 수 $n$과 무관합니다. 이는 분산형 랜덤 정책과 결합하여 순차적 글로벌 의사결정과 로컬 에이전트 상호작용 간의 균형을 맞추는 데 효율적인 방법을 제시합니다.