Graph-SND: 다중 에이전트 강화학습의 행동 다양성 측정 효율화

다중 에이전트 강화학습 (Multi-Agent Reinforcement Learning) 에서 시스템 신경 다양성 (System Neural Diversity, SND) 은 모든 $inom{n}{2}$ 쌍의 에이전트 간 거리를 평균하여 행동 이질성을 측정하며, 이는 팀 규모에 대해 제 2 차 함수 (quadratic) 로 계산됩니다. 우리는 임의의 그래프 $G$ 의 에지에 대한 가중 평균을 사용하여 이를 대체하는 Graph-SND 를 소개합니다. 세 가지 regime 가 존재합니다: $G=K_n$ 은 SND 를 정확히 복원하며, 고정된 희소 (sparse) $G$ 는 $O(|E|)$ 비용으로 국소적 다양성 측정 (localized diversity measure) 을 정의하고, 무작위 에드 샘플은 Horvitz-Thompson 추정자와 정규화된 표본 평균을 제공하여 샘플링된 에지 수 $m$ 에서 $O(1/\rac{1}{\sqrt{m}})$ 집중도 (concentration) 를 제공합니다. 고정된 희소 그래프에 대해 확장에서 (expanders) 대한 포워딩 인덱스 왜곡 한계와 저랭크 거리 구조 (low-rank distance structure) 하에서의 스펙트럴 정밀도를 증명합니다. 무작위 $d$-정규 그래프에 대해 조건부 없는 확률적 $\widetilde{\mathcal{O}}(D_{\max}/\sqrt{n})$ 한계를 증명합니다. VMAS 에서 복원, 편향 없음 (unbiasedness), 집중도, 그리고 벽시계 스케일링을 검증하며, PettingZoo TVD 패널이 비정규분포 (non-Gaussian) 전이를 확인합니다. 500 번 반복 $n=100$ PPO 실행에서 Bernoulli-$0.1$ Graph-SND 는 전체 SND 를 추적하면서 호출당 메트릭 시간을 약 $10\times$ 줄입니다. 고정된 정책 GPU 타이밍은 $n=500$ 까지 예측된 $inom{n}{2}/|E|$ 속도 향상을 따릅니다. 무작위 $d$-정확 확장은 $Θ(n \log n)$ 에지에서 SND$_G^u$/SND ∈ [0.9987, 1.0013] 을 달성합니다. DiCo 다양성 제어에서 $n=50$ 에서 Bernoulli-$0.1$ Graph-SND 는 쌍의 보상 차이 (paired reward differences) 가 9 개 매칭 셀 (matched cells) 에서 0 에 미묘한 차이를 보이며 호출당 메트릭 비용을 ${\sim}9.5\times$ 절감합니다. 이 결과들은 SND 집계 병목 현상을 변경하지 않고 제거할 수 있음을 보여주며, 완전 그래프 SND 를 넘어 확장 가능한 드롭인 희소 대안을 제공하며 수동 측정 (passive measurement) 과 클로즈드 루프 다양성 제어 (closed-loop diversity control) 를 지원합니다.