기술 요약: 상태 증강 및 합의를 통한 확장 가능한 제약 조건이 있는 다중 에이전트 강화 학습

문제 정식화

본 논문은 에이전트들이 **분리 가능한 역학(separable dynamics)**을 가지지만 전역 자원 제약 조건을 충족하기 위해 협력해야 하는 분산 시스템에서의 제약 조건이 있는 다중 에이전트 강화 학습(CMARL) 문제를 다룹니다. 구체적으로, 저자들은 다음과 같은 구조적 가정을 가진 $N$개의 에이전트가 마르코프 게임(Markov Game) 내에서 작동하는 상황을 고려합니다:

1. 독립적 정책: 각 에이전트는 오직 자신의 로컬 상태 $s_i$에 기반하여 행동을 선택합니다.
2. 분리 가능한 역학: 한 에이전트의 행동은 다른 에이전트의 상태 전이에 영향을 미치지 않습니다 ($P(s_{t+1}|s_t, a_t) = \prod P^i(s^i_{t+1}|s^i_t, a^i_t)$).
3. 합산 가능한 보상: 전역 보상과 제약 조건은 개별 로컬 보상의 합입니다.

목표는 이차 보상 $r_1$에 대한 전역 평균 제약 조건(즉, $\sum_i V^i_1(\pi_i) \leq c$)을 준수하면서 일차 보상 $r_0$의 장기 평균을 최대화하는 것입니다. 분리 가능한 구조는 독립적인 학습이 가능함을 시사하지만, 전역 제약 조건은 협력의 과제를 만들어냅니다. 통신 없이는 독립적인 에이전트들이 집단적 한도를 충족하기 위한 적절한 개별 기여도를 결정할 수 없으며, 이는 종종 퇴보적인 솔루션(예: 제약 조건을 사소하게 충족하기 위해 수요를 무기한 연기하는 방식)으로 이어집니다.

방법론

제안된 접근 방식은 **상태 증강 정책 학습(state-augmented policy learning)**과 **듀얼 변수(dual variables, 라그랑주 승수)에 대한 분산 합의(distributed consensus)**를 결합합니다.

1. 상태 증강을 이용한 오프라인 독립 학습

고정된 제약 수준에 대해 별도의 정책을 학습하는 대신, 각 에이전트는 로컬 듀얼 변수인 $\lambda_i$를 상태 입력의 일부로 취급하는 상태 증강 정책 $\pi_i(s_i, \lambda_i)$를 학습합니다.

• 라그랑지안(Lagrangian)은 개별 에이전트 구성 요소로 분해됩니다: $\mathcal{L} = \sum_i [V^i_0(\pi_i) + \lambda_i (c/N - V^i_1(\pi_i))]$.
• 에이전트들은 이 가중치 보상을 최대화하기 위해 표준 RL 알고리즘(예: PPO)을 사용하여 독립적으로 학습합니다. 상태 증강을 통해 정책은 현재의 제약 압박 수준($\lambda$)에 따라 자신의 행동을 동적으로 조정할 수 있습니다.

2. 온라인 듀얼 합의

실행 중에는 에이전트들이 전역 제약 조건을 충족하도록 협력해야 합니다. 이는 듀얼 변수의 분산 업데이트를 통해 달성됩니다:

• 로컬 경사 하강 단계: 각 에이전트는 로컬 제약 위반에 기초하여 로컬 라그랑지안에 대한 경사 하강 단계를 수행하여 자신의 승수 $\lambda_i$를 업데이트합니다.
• 합의 단계: 에이전트들은 통신 그래프 $G$ 내의 인접한 이웃들과 로컬 승수를 교환하고 이를 평균화합니다.
• 업데이트 규칙: 업데이트는 로컬 경사 하강과 합의 항을 결합합니다:
  $$\lambda_i^{k+1} = \lambda_i^k - \alpha \nabla_{\lambda_i} \mathcal{L}_i - \epsilon (\lambda_i^k - \bar{\lambda}_i^k)$$
  여기서 $\bar{\lambda}_i^k$는 이웃들의 승수 평균입니다. 이는 모든 에이전트가 중앙 집중식 조정 없이 공유된 듀얼 변수로 수렴하도록 보장합니다.

3. 이론적 보장

저자들은 완만한 연결성 가정을 바탕으로 다음을 증명합니다:

• 유계된 합의 오차: 에이전트 간의 승수 불일치는 유계되며, 그래프 연결성과 합의 횟수에 따라 감소합니다.
• 유계된 제약 위반: 립시츠 민감도(Lipschitz sensitivity) 논증을 사용하여, 승수 불일치가 유계되면 제약 위반 또한 유계됨을 보여줍니다. 합의 횟수가 증가하거나, 스텝 사이즈가 감소하거나, 그래프 연결성이 개선됨에 따라 위반은 사라집니다.

주요 기여

1. CMARL을 위한 분산 합의 메커니즘: 본 논문은 듀얼 변수에 대한 분산 합의를 상태 증강 제약 RL과 통합합니다. 중앙 집중식 크리틱(critic)이나 결합된 상태 관측 없이도 가벼운 이웃 간 통신만으로 전역적으로 조정된 제약 조건 강제가 가능하다는 것을 증명합니다.
2. 선형 확장성: 문제의 분리 가능성을 정책 학습에 활용하고 조정을 위해 가벼운 합의를 사용함으로써, 본 방법은 학습과 실행 모두에서 선형적으로 확장됩니다. 본 모델은 중앙 집중식 훈련-분산 실행(CTDE) 베이스라인이 중앙 집중식 크리틱의 이차적 복잡도 증가로 인해 수십 명의 에이전트로 제한되는 것과 달리, 최대 1,000명의 에이전트를 성공적으로 처리합니다.
3. 합의의 경험적 필요성: 스마트 그리드 수요 반응 실험을 통해, 합의는 단순히 유익한 것이 아니라 실행 가능성(feasibility)을 위해 필수적임을 입증했습니다. 합의가 없으면 독립적으로 학습된 에이전트들은 제약 조건을 충족하기 위해 수요를 무기한 연기하는 등 퇴보적인 방식으로만 제약 조건을 만족하게 됩니다. 합의가 있으면 에이전트들은 공유된 듀얼 변수로 수렴하여 그리드 제약과 수요 충족을 모두 달전합니다.

실험 결과

본 방법은 태양광 에너지와 배터리 저장 장치를 갖춘 건물들을 포함하는 스마트 그리드 수요 반응 태스크를 통해 검증되었습니다.

• 실행 가능성 vs. 퇴보성: 절제 연구(ablation study)에서 합의가 없는 에이전트들은 수요를 무기한 연기함으로써 그리드 용량 제약을 충족했으나, 이는 무한한 미충족 수요를 초래했습니다. 합의를 적용했을 때 에이전트들은 안정적이고 실행 가능한 솔루션을 달성했습니다.
• 상태 증강의 필요성: 고정된 라그랑주 승수를 사용하여 정책을 학습하는 방식(상태 증강 없이)은 매우 취약한 것으로 나타났습니다. 테스트된 414개의 고정 승수 구성 중 단 7개만이 실행 가능한 동작을 생성했습니다. 반면, 상태 증강 방식은 모든 제약 수준에 대해 일반화 성능을 보였습니다.
• 베이스라인과의 비교: 중앙 집중식 크리틱에 의존하는 최신 MARL 베이스라인(MAPPO, MADDP_G, MASAC, ISAC)과 비교했을 때, 제안된 방법은 현저히 낮은 계산 오버헤드로 동등하거나 더 나은 제약 조건 충족 성능을 달성했습니다.
• 중앙 집중식 오라클(Oracle) 비교: 분산 방법은 "중앙 집중식 오라클"(완벽한 전역 정보 보유)과 비교되었습니다. 분산 접근 방식은 오라클 대비 < 0.2% (구체적으로 +0.086%)의 비용 차이만을 보였으며, 이는 탈중앙화가 이 설정에서 무시할 만한 성능 손실을 초 incurs 함을 입증합니다.
• 확장성: 본 시스템은 1,000명의 에이전트까지 선형적으로 확장되었습니다. 학습 비용은 에이전트 수에 대해 $O(1)$이었으며(두 종류의 에이전트 유형에 대해 두 개의 정책만 학습), 실행 시간은 에이전트 수에 따라 선형적으로 증가했습니다.

의의 및 주장

본 논문은 에이전트들이 디커플링된 역학을 가지지만 자원 예산을 공유하는 대규모 인프라 관리 문제(예: 스마트 그리드, EV 충전, 플릿 관리)를 위한 실용적인 프레임워크를 제공한다고 주장합니다.

• 확장성: 주요 의의는 유계된 제약 위반 보장을 갖추면서 수천 명의 에이전트를 조정할 수 있는 능력이며, 이는 현재의 CTDE 방법으로는 도달할 수 없는 규모입니다.
• 실행 가능성: 본 연구는 독립적으로 학습된 정책을 집단적으로 실행 가능한 솔루션으로 변환하기 위해 합의 조율이 필수적임을 확립하며, 이를 통해 에이전트들이 제약 충족을 위한 사소하고 퇴보적인 솔루션을 찾는 것을 방지합니다.
• 완만한 최적성 주장: 저자들은 중앙 집중식 오라클과의 근접한 동등성이 일반적인 최적성 보장이 아닌, 스마트 그리드 테스트베드에 특화된 경험적 관찰임을 명시적으로 밝힙니다. 이론적 분석은 합의 오차와 실행 가능성 여유를 제한하지만, 일반적인 경우에 대한 완전한 프라이멀 최적성(primal optimality)을 제공하지는 않습니다.
• 한계점: 본 접근 방식은 분리 가능한 역학 및 합산 가능한 보상을 가진 문제로 제한됩니다. 따라서 에이전트의 전이가 서로에게 직접적인 영향을 미치는 결합된 역학(예: 다중 로봇 조작 또는 교통 혼잡)이 있는 환경에는 적용할 수 없습니다.