제약 조건이 있는 다중 에이전트 강화학습을 위한 조정 그래프 (Coordination Graphs for Constrained

제약 조건이 있는 다중 에이전트 강화학습 (Constrained Multi-agent reinforcement learning, CMARL)은 서로 얽힌 두 가지 문제에 직면해 있습니다. 하나는 에이전트의 수에 따라 결합 행동 공간 (joint action space)이 기하급수적으로 증가한다는 것이며, 다른 하나는 보상 구조만으로는 포착할 수 없는 방식으로 추가적인 요구 사항들이 에이전트들을 결합시킨다는 점입니다. 우리는 조정 그래프 (Coordination Graphs)와 라그랑주 쌍대성 (Lagrangian duality)을 결합하여 이 두 가지 문제를 모두 해결하는 '제약 조건이 있는 다중 에이전트 강화학습을 위한 조정 그래프 (CG-CMARL)' 프레임워크를 소개합니다. 이 시스템은 결합된 문제를 쌍별 영역 (pairwise regions)으로 분해하며, 각 영역은 기본 목적 함수를 위한 하나와 각 제약 조건을 위한 각각의 하나를 포함하는 공유 Q-함수 (Q-functions) 세트에 의해 처리됩니다. 이를 통해 학습되는 모델의 수는 에이전트의 수와 무관하게 유지됩니다. 실행 시에는 Max-Sum 메시지 전달 (Max-Sum message passing)이 팩터 그래프 (factor graph) 전반에 걸쳐 행동을 조정하며, 라그랑주 승수 (Lagrangian multiplier)가 목적 함수와 제약 조건 사이의 트레이드오프 (tradeoff)를 제어하여, 단일 학습 모델이 재학습 없이 파레토 프런트 (Pareto front)를 추적할 수 있도록 합니다. 우리는 완만한 조건 하에서의 수렴 보장 (convergence guarantees)과 함께, 각각의 설계 선택에 기인하며 독립적으로 제어 가능한 해석 가능한 개별 소스들로 분해되는 구성적 오차 경계 (compositional error bound)를 제공합니다. 협력적 내비게이션 태스크 (cooperative navigation tasks, 최대 10명의 에이전트 팀이 쌍별 제약 조건을 만족하면서 목표 위치에 도달하기 위해 협력해야 하는 작업)에 대한 실험 결과, 우리의 방법은 고정된 보상 형성 비율 (reward-shaping ratios)로 학습된 기존 베이스라인들을 능가하는 파레토 프런트를 생성하는 동시에, 중앙 집중식 접근 방식이 다루기 힘들어지는 팀 규모에서도 확장 가능하다는 것을 보여줍니다.