Randomness is sometimes necessary for coordination

기술 요약: 무작위성 기반 조정을 위한 다이아몬드 어텐션

문제 제기
협력형 다중 에이전트 강화학습 (MARL) 에서 완전한 매개변수 공유는 동종 에이전트를 위한 표준 접근법이며, 종종 중앙 집중식 학습과 분산 실행 (CTDE) 과 결합됩니다. 그러나 여러 개의 동등하게 최적인 결합 전략이 존재하는 다중 모드 보상 구조를 가진 작업에서는 이 접근법이 실패합니다. 치환 대칭적 관측 하에서 공유된 결정론적 정책은 모든 에이전트에 대해 동일한 행동 분포를 생성하여 역할 분화를 불가능하게 만듭니다. Angluin(1980) 과 Case 등 (2005) 의 이론적 연구는 익명 프로세서 간의 대칭성 깨기가 결정론적으로 불가능함을 입증했으며, 고유 식별자가 없는 에이전트 간 조정에는 공유된 무작위 비트에 대한 접근이 필수 조건임을 밝혔습니다. 기존 해결책들은 실행 시 결정론적으로 남아 있어 (이론적 요구 사항을 충족하지 못함) 또는 순차적 실행을 통해 대칭성을 깨뜨리는데, 이는 $O(N)$ 의 추론 지연을 초래하고 외부에서 부과된 실행 순서를 요구합니다. 이는 진정한 분산 환경에서 순환적 의존성을 야기합니다.

방법론: 다이아몬드 어텐션
저자들은 단일 브로드캐스트 라운드에서 대칭성을 깨기 위해 공유 무작위성의 이론적 필요성을 구현하는 교차 어텐션 아키텍처인 다이아몬드 어텐션 (Diamond Attention) 을 제안합니다.

• 핵심 메커니즘: 각 시간 단계에서 모든 에이전트는 스칼라 무작위 수 $r_i \sim \text{Uniform}[0, 1]$ 을 샘플링합니다. 이러한 스칼라 값은 단일 브로드캐스트를 통해 팀 전체와 공유됩니다.
• 구조화된 마스킹: 무작위 수들은 에이전트 간에 일시적이고 엄격한 순위 매김을 유도합니다. 에이전트 간 교차 어텐션 메커니즘에 구조화된 어텐션 마스크가 적용됩니다:
  • 에이전트 $j$ 의 순위가 에이전트 $i$ 보다 낮을 경우 ($r_j < r_i$), 에이전트 $i$ 는 에이전트 $j$ 를 마스킹합니다.
  • 에이전트 $i$ 는 동등하거나 더 높은 순위를 가진 에이전트에게만 어텐션합니다.
  • 작업 - 에이전트 어텐션은 완전히 마스크되지 않아 모든 에이전트가 글로벌 목표 구조에 접근할 수 있도록 보장합니다.
• 결과적 비대칭성: 이 마스킹은 동적이며 시간 단계별 계층 구조를 생성합니다. 상위 순위 에이전트는 주로 작업 임베딩에 어텐션하여 상대적으로 독립적으로 행동하는 반면, 하위 순위 에이전트는 상위 순위 동료들의 행동에 기반하여 행동을 조건화합니다. 이로 인해 동일한 네트워크 매개변수에도 불구하고 차별화된 잠재 표현과 행동 분포가 유도됩니다.
• 확장성: 이 아키텍처는 에이전트 및 작업 임베딩 집합 위에서 작동하므로, 수정 없이 임의의 수의 에이전트와 작업을 수용할 수 있으며, 다른 팀 크기에 대한 제로샷 일반화를 가능하게 합니다.

주요 기여

1. 이론적 형식화: 본 논문은 XOR 조정과 무작위 비트 공유 간의 동등성을 형식화하여, Case 등 (2005) 의 불가능성 결과에 기반한 아키텍처 설계를 뒷받침합니다.
2. 아키텍처 혁신: 다이아몬드 어텐션은 순차적 실행이나 외부 에이전트 식별자를 요구하지 않고 단일 브로드캐스트 라운드에서 무작위 비트 조정 프로토콜을 실현합니다. 외부 순서 요구 사항을 내부 구조화된 확률성으로 대체합니다.
3. 실증적 검증: 이 방법은 특정 조정 병리 현상을 분리한 세 가지 서로 다른 영역에서 검증되었습니다:
   • 대칭성 깨기 (XOR 게임): 완벽하게 대칭적인 XOR 게임에서 결정론적 베이스라인은 무작위 행동 바닥 (N=2 인 경우 0.5 성공) 근처에서 정체됩니다. 다이아몬드 어텐션은 1.0 의 성공률을 달성합니다.
   • 제로샷 확장성 (VMAS): $N=4$ 에이전트로 훈련된 정책은 정적 (Simple Spread) 및 동적 (Food Collection) 환경 모두에서 $N \in [2, 8]$ 팀으로 제로샷 일반화되어, 보지 못한 팀 크기에서 성능이 저하되는 베이스라인들을 능가합니다.
   • 적대적 전이 (SMACLite): 이 아키텍처는 구조적 한계로 인해 표준 베이스라인이 완전히 실패하는 2s3z 시나리오에서 3s5z 시나리오로의 제로샷 전이를 달성합니다.

결과 및 제거 실험 통찰

• 구조의 필요성: 구조화된 마스크를 표준 드롭아웃 기반 무작위성으로 대체할 경우, SMAC 전이 작업에서 승률이 0% 가 됩니다. 이는 작동하는 핵심 요소가 단순한 확률적 노이즈가 아니라 무작위 순서의 프로토콜 공간 구조임을 확인시켜 줍니다.
• 일반화 한계: 이 방법은 연속 제어 (VMAS) 에서 잘 일반화되지만, XOR 게임에서 행동 공간의 엄격한 부분 집합 (예: $N=2, K=3$) 으로 훈련된 후 더 큰 팀 ($N=3, K=3$) 에 배포될 때는 취약성을 보입니다. 이는 환경 신호가 추가적인 비대칭성을 제공하는 동적 환경에서의 견고성과 대조됩니다.
• 자기회귀 방법과의 비교: 순차적 실행을 통해 대칭성을 깨는 자기회귀 모델 (예: MAT) 과 달리, 다이아몬드 어텐션은 $O(N)$ 지연이나 외부 순서 가정 없이 1.0 의 성공률을 달성합니다.

의의 및 주장
본 논문은 다이아몬드 어텐션이 환경 신호에 의존하는 대신 내부적으로 생성되고 매 단계마다 확률적으로 생성되는 조정 상태를 제공하는 조정 원시 (primitive) 를 제공한다고 주장합니다. 저자들은 이 접근법이 글로벌 동기화나 고정된 에이전트 신원 없이 분산 조정을 가능하게 한다고 강조합니다.

이 연구의 의의는 대칭적이고 익명한 환경에서 조정을 위한 결정론적 최적화나 비구조화된 노이즈가 아닌 구조화된 무작위성이 결정적 요소임을 입증하는 데 있습니다. 이 연구는 재난 대응과 같은 불신뢰 인프라에서의 시간 민감성 배포를 위해, 관찰 가능한 환경 단서에 의존하는 방식보다 내부적으로 샘플링된 조정 상태가 통신 실패 및 적대적 재밍에 더 강건함을 시사합니다. 다만, 저자들은 가변 행동 공간을 처리하면서도 표현 능력을 희생하지 않기 위한 적응적 투영 레이어의 필요성과 PPO 하에서 고차원 희소 보상 환경 ($N > 5$) 에서의 현재 학습 병목 현상 등 한계를 겸손하게 지적합니다.