기술 요약: 제약 조건이 있는 다중 에이전트 강화 학습을 위한 조정 그래프 (CG-CMARL)

1. 문제 정의

본 논문은 여러 협력 에이전트가 주요 목표를 최대화하는 동시에 안전 제약 조건(예: 충돌 회피, 에너지 예산)을 충족해야 하는 제약 조건이 있는 다중 에이전트 강화 학습(CMARL) 문제를 다룹니다. 저자들은 두 가지 밀접하게 연관된 과제를 식별했습니다:

1. 확장성(Scalability): 결합 행동 공간(joint action space)이 에이전트 수($N$)에 따라 기하급수적으로 증가하여, 중간 규모의 팀 규모에서도 중앙 집중식 접근 방식은 실행 불가능해집니다.
2. 제약 조건 결합(Constraint Coupling): 안전 제약 조건은 보상 구조만으로는 포착할 수 없는 방식으로 에이전트들을 결합합니다. 독립적인 학습자가 자신의 라그랑주 승수(Lagrangian multiplier)를 최적화하면 집단적으로 글로벌 제약 조건을 위반할 수 있는 반면, 중앙 집중식 원-쌍대(primal-dual) 방법은 글로벌 상태와 결합 행동 공간에 대한 접근 권한을 필요로 하므로 인수 분해된 방식의 이점을 상쇄합니다.

이 문제는 기대 할인된 주요 보상 $V^\pi_0$를 최대화하되 제약 조건 보상 $V^\pi_j$가 특정 임계값을 초과하도록 하는 제약 마르코프 결정 과정(CMDP)으로 정식화됩니다. 저자들은 독립적 전이(에이전트의 다음 상태는 오직 자신의 행동에만 의존함)와 조정 그래프 상에서의 가법적 보상 인수 분해(보상이 지역적 구성 요소, 특히 쌍별(pairwise) 영역으로 분해됨)를 가정합니다.

2. 방법론: CG-CMARL

제안된 프레임워크인 CG-CMARL은 확장 가능한 분산 제약 조건 충족을 달 수 있도록 조정 그래프(Coordination Graphs, CG)를 라그랑주 쌍대성(Lagrangian duality)과 통합합니다. 이 방법은 중앙 집중식 훈련, 분산 실행(CTDE) 패러다임 하에서 작동합니다.

2.1 이중 헤드 Q-함수 아키텍처

단일 결합 보상 신호를 위해 하나의 Q-함수를 학습하는 대신(이는 서로 다른 트레이드오프를 위해 재학습이 필요함), CG-CMARL은 각 영역당 두 개의 별도 Q-함수를 유지합니다:

• 주요 헤드 ($Q_{prim}$): 표준 Q-러닝을 사용하여 주요 목표에 대한 최적의 지역 Q-함수를 학습합니다.
• 비용 헤드 ($Q_{cost}$): (주요 헤드에 의해 유도된 탐욕적 정책 하에서의) 예상 제약 보상(예: 충돌 비용)을 학습합니다. 결정적으로, 비용 헤드는 자신의 값을 최대화하지 않고, 주요 에이전트의 결정에 따른 결과를 평가합니다. 이는 행동 선택 시 일관된 구성을 보장합니다.

2.2 라그랑주 트레이드오프 및 파레토 스위핑 (Pareto Sweeping)

실행 시점에 두 헤드는 라그랑주 승수 $\lambda$를 통해 결합됩니다:
$$Q_{aug, R}(s_R, a_R) = Q_{prim, R}(s_R, a_R) + \lambda Q_{cost, R}(s_R, a_R)$$

• 훈련: 에이전트는 관찰된 제약 위반에 따라 업데이트되는 로컬 승수 $\lambda_i$를 유지합니다. 행동 선택 중에는 평균 승수 $\bar{\lambda}$가 사용됩니다.
• 평가: 단일 학습된 모델에서 $\lambda$를 범위 내에서 스위핑함으로써, 시스템은 재학습 없이 전체 목적-제약 파레토 프런트(Pareto front)를 추적합니다. 이는 제약 트레이드오프를 학습 과정으로부터 분리합니다.

2.3 Max-Sum 메시지 전달

중앙 집중식 계산 없이 팩터 그래프(factor graph) 전반에서 행동을 조정하기 위해, 이 방법은 Max-Sum 메시지 전달을 채택합니다:

• 에이전트(변수 노드)와 지역 Q-함수(팩터 노드)는 $\max_a \sum_R Q_{aug, R}(s_R, a_R)$라는 조합 최적화를 해결하기 위해 메시지를 교환합니다.
• 댐핑(Damping): 쌍별 조정 그래프는 $N \ge 3$인 경우 사이클을 포함하므로, 수렴을 안정화하기 위해 메시지 댐핑이 적용됩니다.
• 복잡도: 단계당 복잡도는 $N$에 대한 다항식($O(N^2 |A| K)$)이며, 이는 전수 조사(exhaustive search)의 지수적 복잡도 $O(|A|^N)$보다 크게 개선된 것입니다.

2.4 파라미터 공유

모든 쌍별 영역은 단일 세트의 Q-함수 파라미터를 공유합니다. 모든 영역이 정확히 두 명의 에이전트를 포함하므로, 학습된 모델의 수는 팀 규모 $N$에 관계없이 $O(1)$이며, 이를 통해 대규모 팀으로의 확장이 가능합니다.

3. 이론적 기여

본 논문은 완만한 가정(독립적 전이, 보상 인수 분해, Slater의 조건) 하에 엄격한 이론적 보증을 제공합니다:

• 수렴: 두 헤드 Q-러닝은 최적의 지역 Q-함수와 주요 탐욕 정책 하에서의 제약 값으로 거의 확실하게(almost surely) 수렴합니다. 평균 라그랑주 승수는 최적의 쌍대 해(dual solution)로 수렴합니다.
• 구성 오류 경계 (Compositional Error Bound): 학습된 솔루션과 실제 최적값 사이의 격차에 대한 경계를 도출하며, 이를 네 가지 해석 가능한 소스로 분해합니다:
  1. 구조적 오류 ($\beta$): 인수 분해 근사(중첩된 영역)에서 발생합니다.
  2. 조정 오류 ($\epsilon_{MS}$): 루프가 있는 그래프에서의 Max-Sum의 근사적 특성에서 발생합니다.
  3. 샘플링 오류: 유한한 데이터($O(1/\sqrt{n})$)로 인해 발생합니다.
  4. 표현 오류: 함수 근사($\epsilon_{NN}$)로 인해 발생합니다.
     이 경계는 이러한 오류들이 벨만 백업(Bellman backup)을 통해 어떻게 전파되는지 정량화하여, 시스템 설계에 대한 질적 가이드를 제공합니다.

4. 실험 결과

이 방법은 Simple Spread 협력 내비게이션 벤치마크(PettingZoo/MPE)에서 팀 규모 $N \in \{3, 4, 6, 10\}$에 대해 평가되었습니다.

• 베이스라인: IQL, QMIX, Deep Coordination Graphs (DCG), MAPPO, MAPPO-Lagrangian과 비교되었습니다.
• 성능: CG-CMARL은 모든 베이스라인을 압도하는 파레토 프런트를 생성합니다. 다른 방법들(QMIX, MAPPO 등)은 고정된 보상 형성 비율을 위해 별도의 훈련 실행이 필요하지만(단일 동작 지점 생성), CG-CMARL은 하나의 모델로부터 전체 트레이드오프 곡선을 추적합니다.
• 확장성: 이 방법은 중앙 집중식 접근 방식이 실행 불가능해지는 $N=10$ 에이전트까지 확장됩니다. $N$이 증가함에 따라 쌍별 조정 그래프의 밀도가 높아지지만, 랜드마크 보상에 비해 쌍별 충돌 페널티 간의 결합이 약하기 때문에 실질적인 구조적 오류는 작게 유지됩니다.
• 안전성: 이 방법은 커버리지(주요 목표)와 충돌 회피(제약 조건) 사이의 균형을 효과적으로 맞추며, 라그랑주 승수가 정책을 실행 가능성(feasibility) 쪽으로 성공적으로 유도합니다.

5. 의의 및 주장

본 논문은 CG-CMARL이 (조정 그래프를 통한) 인수 분해된 가치 함수의 확장성과 (분산 아키텍처에서의 라그랑주 방법론을 통한) 제약 조건 처리 능력을 결합한 최초의 연구라고 주장합니다.

주요 주장은 다음과 같습니다:

• 학습과 트레이드오프의 분리: 주요 보상과 제약 보상의 학습을 분리함으로써, 이 방법은 표준 제약 RL 방식에는 없는, 재학습 없이 사후적으로 파레토 프런트를 탐색할 수 있는 능력을 제공합니다.
• 확장 가능한 분산화: 이 프레임워크는 $O(1)$의 모델 복잡도와 다항식 시간의 행동 선택 복잡도를 달성하여, 다중 에이전트 결합 행동 공간의 "차원의 저주"를 극복합니다.
• 해석 가능성: 구성 오류 경계는 성능 격차를 그래프 토폴로지, 샘플링, 네트워크 용량과 같은 특정 설계 선택 사항과 명시적으로 연결하여, 시스템을 분석하고 개선할 수 있는 원칙적인 방법을 제공합니다.

저자들은 한계점을 인정하며, $N$이 커짐에 따라 쌍별 그래프가 조밀해지고(Max-Sum 계산 증가), 두 헤드 구성이 보수적인 근사(비용 헤드가 최종 정책이 아닌 주요-탐욕 정책을 평가함)를 포함한다는 점을 언급했습니다. 향후 연구에서는 희소/동적 그래프 토폴로지를 탐색하거나, 이론적으로 이 보수적 근사를 해결하기 위해 $\lambda$를 Q-함수에 직접 조건화하는 $\lambda$-증강(augmented) 형식을 탐구할 수 있다고 제안하며, 다만 이는 샘플 복잡도의 증가를 초래할 수 있습니다.