기술 요약: ACPO: 다중 에이전트 강화 학습을 위한 에이전트 체인 기반 정책 최적화 (Agent-Chained Policy Optimization)

문제 정의

협력적 다중 에이전트 강화 학습(Cooperative Multi-Agent Reinforcement Learning, MARL)은 공동의 보상을 최대화하는 분산된 정책을 찾는 것을 목표로 한다. 중앙 집중식 훈련 및 분산 실행(Centralized Training with Decentralized Execution, CTDE) 패러다임 하에서, 결합 정책 경사(joint policy gradient)를 직접 계산하는 것은 여전히 어려운 과제로 남아 있다. 기존의 접근 방식은 크게 두 가지 범주로 나뉘며, 둘 다 상당한 한계를 지닌다:

1. 독립적 정책 최적화 (예: MAPPO, MADDPG): 에이전트들이 중앙 집중식 비평가(critic)를 사용하여 독립적으로 정책을 업데이트한다. 확장성은 뛰어나지만, 이러한 방법들은 다른 에이전트들의 변화하는 정책으로 인해 발생하는 비정상성(non-stationarity)을 고려하지 못하기 때문에 결합 정책 개선에 대한 일반적인 보장을 제공하지 못한다. 수렴은 가치 분해(value decomposition)와 같은 강력한 구조적 가정이 있을 때만 보장된다.
2. 교대 최적 대응 (Alternating Best-Response Optimization, 예: HAPPO, HATR $\text{R}$O): 에이전트들이 다른 에이전트의 정책을 고정된 것으로 간주하고 순차적으로 업데이트한다. 이는 각 단계에서 결합 보상의 단조적 개선(monotonic improvement)을 보장하지만, 그 고정점(fixed point)은 내쉬 균형(Nash Equilibrium, NE)이다. 협력적 환경에서 NE는 진정한 사회적 최적값(social optimum)에 비해 임의로 차이가 클 수 있으며, 에이전트들은 이러한 하위 최적 균형에서 벗어날 메커니즘이 없다.

본 논문은 두 접근 방식 모두 제한적인 가정 없이는 밑바탕이 되는 다중 에이전트 MDP(MMDP)의 최적 결합 정책을 효과적으로 타겟팅하지 못한다고 주장한다.

방법론: 에이전트 체인 기반 정책 최적화 (ACPO)

본 논문의 핵심 기여는 **결합 정책 경사의 정확한 분산 분해(exact decentralized decomposition)**를 도출하는 것이다. 이는 새로운 형식인 **에이전트 체인 기반 믿음 MDP (Agent-Chained Belief MDP, AC-BMDP)**를 도입함으로써 달성되며, 이를 통해 동시적인 결합 결정 문제를 불완전 정보가 포함된 직렬화된 결정 과정으로 변환한다.

1. 에이전트 체인 기반 믿음 MDP (AC-BMDP)

동시 게임을 불완전 정보가 있는 직렬화된 프로세스로 재구성할 수 있다는 게임 이론적 결과에 착안하여, 저자들은 각 환경 타임 스텝 $t$를 $N$개의 마이크로 스텝(각 에이전트 $i \in \{1, \dots, N\}$를 위한 단계)으로 분해한다.

• 직렬화 (Serialization): 에이전트들은 단일 타임 스텝 내에서 순차적으로 행동을 결정한다. 에이전트 $i$는 에이전트 $1$부터$i-1$까지의 행동 이후에 행동한다.
• 상태 증강 (State Augmentation): 에이전트 $i$의 상태는 이전 에이전트들의 실현된 행동($\vec{a}^{<i}_t$)에 대한 믿음(belief) $b^{(i)}_t$로 증강된다.
• 분산 실행 (Decentralized Execution): 실행 중에는 이전 에이전트들의 실현된 행동을 관찰할 수 없으므로, 믿음은 이전 에이전트들의 행동 분포($\phi^{(j)}_t$)로부터 구축된다. 이 분포들은 공유된 상태와 에이전트들의 정책의 결정론적 함수이며, 통신 없이도 접근 가능하다.
• 체인형 벨만 연산자 (Chained Bellman Operators): 에이전트 $i$의 가치 함수 $Q^{(i)}$는 재귀적으로 정의된다. 에이전트 $i$의 가치는 다음 에이전트(체인 내 다음 순서의 에이전트)의 가치에 의존한다. 오직 마지막 에이전트($N$)만이 환경 보상을 받고 첫 번째 에이전트의 가치로 부트스트래핑(bootstrap)한다. 이 "체이닝(chaining)"은 가치 함수가 분해 가능하다고 가정하지 않고도 신용 할당(credit assignment)을 가능하게 한다.

2. 이론적 토대

본 논문은 두 가지 핵심 정리를 확립한다:

• 에이전트 체인 기반 정책 경사 정리 (Agent-Chained Policy Gradient Theorem): AC-BMDP의 정책 경사는 에이전트 자신의 상태와 이전 행동에 대한 믿음에만 의존하는 분산 비평가 $Q^{(i)}$를 사용하여 계산될 수 있다.
• 다중 에이전트 정책 경사 분해 정리 (Multi-Agent Policy Gradient Decomposition Theorem): 원래 MMDP의 결합 정책 경사가 AC-BMDP에서 유도된 $N$개의 독립적인 에이전트별 항의 합과 정확히 동일함을 보여준다.
  $$\nabla_\theta J(\vec{\pi}_\theta) = \frac{1}{(\gamma')^{N-1}} \sum_{i=1}^N \mathbb{E} \left[ \nabla_\theta \log \pi^{(i)}_\theta(a^{(i)} | s, b^{(i)}) \cdot Q^{(i)}([s, b^{(i)}], a^{(i)}) \right]$$
  결정적으로, 이 분해는 (VDN이나 QMIX와 달리) 결합 가치 함수에 대한 구조적 가정을 요구하지 않으며, 교대 업데이트의 하위 최적 고정점 문제를 피한다.

3. 알고리즘 구현

저자들은 ACPO를 두 가지 실용적인 형태로 구현한다:

• ACPPO (On-Policy): 에이전트 체인 기반 어드밴티지 추정치를 사용하여 클리핑된 대리 목적 함수(clipped surrogate objective)를 최적화하는 PPO 기반 알고리즘이다. 어드밴티지는 에이전트 체인을 가로지르는 체인형 TD 잔차(Temporal Difference residuals)를 합산하는 GAE(Generalized Advantage Estimation)를 통해 계산된다.
• ACTD3 (Off-Policy): 연속 제어를 위한 TD3 기반 알고리즘으로, 에이전트들은 체인형 벨만 구조를 따르는 트윈 비평가(twin critics)를 유지한다.

믿음 근사 (Belief Approximation):

• 완전 관측 (MMMMDP) 환경: 에이전트들은 이전 에이전트들의 정책 네트워크를 쿼리하여 믿음을 정확하게 계산한다.
• 부분 관측 (Dec-POMDP) 환경: 에이전트들은 자신의 로컬 히스토리를 기반으로 이전 에이전트들의 행동 분포를 예측하는 **행동 믿음 네트워크(Action Belief Network)**를 사용하며, 이는 중앙 집중식 타겟에 대해 KL-발산 손실을 통해 학습된다.

주요 기여

1. AC-BMDP의 정형화: 직렬화와 믿음 증강을 결합하여, 가치 분해 가정 없이 CTDE 하에서 최적의 결합 정책 학습을 가능하게 하는 공식적인 프레임워크를 도입했다.
2. 정확한 경사 분해: 결합 정책 경사가 에이전트별 항들로 정확히 분해됨을 증명하여, 개별적인 업데이트가 결합 목적 함수에 대한 단일 경사 단계(single gradient step)를 구성할 수 있게 했다.
3. 최적 결합 정책으로의 수렴: 교대 방식이 내쉬 균형으로 수렴하는 것과 달리, 본 논문은 테이블 형식(tabular settings)에서 에이전트 체인 기반 정책 반복(ACPI)이 밑바탕이 되는 MMDP의 최적 결합 정책으로 수렴함을 증명한다.
4. 확장 가능한 알고리즘: ACPO가 온-폴리시(on-policy) 및 오프-폴리시(off-policy) 딥 RL 알고리즘 모두에 적용될 수 있음을 보여주는 ACPPO 및 ACTD3를 개발했다.

실험 결과

저자들은 세 가지 표준 벤치마크인 Multi-Robot Warehouse (RWARE), SMACv2, MA-MuJoCo에서 ACPO를 평가했다.

• 성능: ACPO(특히 ACPPO)는 MAPPO(독립적 최적화), HAPPO/HATRPO(교대 최적화), 가치 분해 방법(VDN, QMIX)을 포함한 강력한 베이스라인들을 일관되게 능가했다.
• 에이전트 수에 따른 확장성: ACPO와 베이스라인 간의 성능 격차는 에이전트 수가 증가함에 따라 더 커진다는 것이 중요한 발견이다. RWARE에서 이 이점은 8개 및 12개 에이전트 시나리오에서 가장 두드et졌으며, 이는 ACPO가 고도의 협력이 필요한 혼잡한 환경에서 특히 효과적임을 시사한다.
• 오프-폴리시 성능: 오프-폴리시 변형인 ACTD3 또한 MA-MuJoço에서 베이스라인(MADDPG, HATD3)보다 우수한 성능을 보였으며, 이는 에이전트 체이닝 메커니즘의 일반성을 입증한다.
• 절제 연구 (Ablation Studies): 에이전트 체이닝 메커니즘을 제거하면(ACPPO를 믿음 입력을 가진 MAPPO로 축소) 성능이 MAPPO와 유사해졌으며, 이는 성능 향상이 단순히 믿음 상태를 추가했기 때문이 아니라 체인형 어드밴티지 계산 덕분임을 확인시켜 준다.
• 효율성: ACPO는 순차적인 믿음 계산이 필요하지만, 벽시계 시간(wall-clock time) 기준 훈련 시간은 MAPPO와 유사하며, 순차적인 에이전트 업데이트를 요구하는 교대 방식(HAPPO/HATRPO)보다는 상당히 빠르다.

의의 및 주장

본 논문은 ACPO가 CTDE 하에서의 협력적 MARL 문제에 대한 원칙적인 해결책을 제공한다고 주장한다. 그 의의는 다음과 같다:

• 격차 해소: 독립적 업데이트의 이점(확장성)과 교대 업데이트의 이점(단조적 개선 보장)을 결합하면서도, 각각의 단점(비정상성 및 하위 최적 내쉬 균형)을 피한다.
• 이론적 엄밀성: 가치 분해 가정에 의존하지 않는 최초의 정확한 결합 정책 경사 분해를 제시하며, 이론적으로 테이블 형식 설정에서 사회적 최적값으로의 수렴을 보장한다.
• 실질적 효용성: 실험 결과는 명시적인 믿음 체이닝을 통한 협력이 현재의 최첨단 방법들보다 복잡한 다중 에이전트 협력 과제를 처리하는 데 있어 우월한 메커니즘임을 시사하며, 특히 에이전트 집단의 복잡성이 증가할수록 더욱 그러하다.

저자들은 한계점도 솔직하게 언급했다. 구체적으로 믿음 계산이 에이전트 수에 따라 선형적으로 확장되어 $O(N^2)$의 순전파(forward pass)를 요구한다는 점과, 현재의 이론적 보장이 완전 관측(MMDP)에 의존하고 있어 일반적인 Dec-POMDP로의 확장이 향후 과제로 남아 있다는 점이다.