기술 요약: 오토마타 조건부 협력 다중 에이전트 강화 학습 (ACC-MARL)

1. 문제 정의

본 논문은 중앙 집중식 훈련 및 분산 실행 (CTDE) 하에서 협력하는 팀을 위한 멀티태스크, 다중 에이전트 정책 학습 문제를 다룹다. 구체적인 설정은 실행 시점에 에이전트들에게 **사전에 알 수 없는 시간적 작업(temporal tasks)**이 할당되며, 에이전트들은 명시적인 통신 없이 이를 완료해야 하는 상황이다.

핵심적인 어려움은 동적인 작업에 일반화하면서 복잡하고 장기적인 목표를 충족해야 한다는 점이다. 결정적 유한 오토마타(DFA)와 같은 형식적 명세를 사용하여 작업을 표현하는 기존 방식들은 종종 샘플 효율성이 낮고 단일 작업 시나리오에 국한되어, 새로운 목표가 생길 때마다 재학습이 필요하다는 한계가 있다. 또한, 다중 에이전트 맥락에서는 세 가지 주요 과제가 실현 가능성을 저해한다:

1. 이력 의존성 (History Dependency): 정책은 결정을 내리기 위해 작업 진행 상태(이력)를 추적해야 하며, 이는 마르코프 성질(Markov property)을 깨뜨려 하위 최적(suboptimal) 정책을 초래한다.
2. 신용 할당 (Credit Assignment): 팀 단위 보상은 희소하며(전체 작업 완료 시에만 지급됨), 이로 인해 개별 에이전트의 행동이 글로벌 목표에 어떻게 기여하는지 파악하기 어렵다.
3. 표현 병목 현상 (Representation Bottleneck): 잠재적 DFA 표현과 제어 정책을 동시에 학습하는 것은 특히 두 명 이상의 에이전트로 구성된 팀에서 확장성 문제를 야기한다.

2. 방법론: ACC-MARL 프레임워크

저자들은 **오토마타 조건부 협력 다중 에이전트 강화 학습 (ACC-MARL)**을 제안하며, 이는 DFA로부터 도출된 작업 표현에 분산 정책을 조건화하는 프레임워크이다. 이 접근 방식은 다음 메커니즘들을 통해 세 가지 과제를 해결한다:

A. 마르코프 재정형화를 통한 이력 의존성 완화

원시 관측 이력에 정책을 조건화하는 대신, 본 프레임워크는 각 에이전트에 대한 현재 최소 DFA 상태로 상태 공간을 확장한다.

• 메커니즘: 각 단계에서 환경 상태에 레이블이 지정되고, 할당된 DFA는 이러한 레이블을 기반으로 진행(업데이트)된다. 에이전트의 관측값은 최신 최소 DFA 표현과 함께 확장된다.
• 결과: 이는 비마르코프 게임을 환경 상태와 DFA 상태의 곱 공간($S \times D^n$) 상의 마르코프 게임으로 변환한다. 저자들은 이 재정형된 마르코프 게임에서 리턴(return)을 최대화하는 것이 할인 계수 $\gamma \to 1$일 때 원래의 시간적 목표를 만족할 확률을 최대화하는 것과 동일함을 증명한다 (정리 3.1).

B. 잠재 기반 보상 형성(PBRS)을 통한 신용 할당 해결

희소한 보상을 극복하기 위해 저자들은 **잠재 기반 보상 형성(Potential-Based Reward Shaping, PBRS)**을 적용한다.

• 메크니즘: 각 에이전트 $i$에 대해 할당된 DFA가 충족되면 1을, 그렇지 않으면 0을 반환하는 잠재 함수 $\Phi_i$를 정의한다. 보상은 현재와 다음 상태 사이의 잠재 차이에 의해 형성된다: $R_{PBRS} = R_{base} + \gamma \Phi_i(next) - \Phi_i(current)$.
• 결과: 에이전트는 자신의 특정 하위 작업을 완료할 때 밀집된 양의 피드백을 받으며, 동시에 형성된 보상에 대한 최적 정책이 원래의 목표에 대해서도 최적이라는 이론적 보장을 유지한다.

C. RAD 임베딩을 통한 표현 병목 현상 해결

학습 중에 (규모가 큰 팀에서 성능 저하를 일으키는) 잠재 DFA 표현을 처음부터 학습하는 것을 피하기 위해, 프레임워크는 사전 학습된 RAD (ReachAvoidDerived) 임베딩을 활용한다.

• 메커니즘: 고정된 Graph Attention Network (GATv2) 인코더가 DFA를 잠재 벡터(RAD 임베딩)로 매핑한다. 이 임베딩들은 서로 다른 최소화된 DFA를 고유하게 표현하고, 광범위한 시간적 작업 클래스 전반의 의미적 유사성을 인코딩하도록 학습되었다.
• 결과: 정책은 원시 DFA나 학습된 표현 대신 이러한 고정된 임베딩에 조건화된다. 이는 표현 학습과 제어 학습을 분리하여, 더 큰 규모의 팀(예: 4명의 에이전트)으로의 효율적인 확장을 가능하게 한다.

D. 최적 작업 할당

프레임-워크는 학습된 가치 함수를 활용하여 테스트 시점에 작업을 최적으로 할당한다. 다양한 작업 할당 순열에 대해 기대 팀 성능(가치 함수의 합)을 평가함으로써, 시스템은 전체 팀 성공을 극대화하는 파레토 최적(Pareto-optimal) 할당을 선택할 수 있다. 특히 비대칭 환경에서 효과적이다.

3. 주요 기여

1. 프레임워크 도입: DFA에 조건화된 멀티태스크, 다중 에이전트, 에고-센트릭(ego-centric) 정책을 학습하기 위한 ACC-MARL 프레임워크를 제안하였다.
2. 이론적 보장: 제안된 마르코프 재정형화와 보상 형성이 원래의 비마르코프 문제에 대해 최적성을 보존함을 증명하였다.
3. 확장성 솔루션: 사전 학습된 RAD 임베딩을 사용하는 것이 표현 병목 현상을 극복하여, 두 명 이상의 에이전트가 있는 팀에서도 효과적인 학습을 가능하게 함을 입증하였다.
4. 작업 할당: 학습된 가치 함수를 사용하여 최적의 작업 할당을 계산하는 방법을 제시하였다.
5. 툴체인: 병렬화된 DFA 연산을 위한 JAX 기반 툴체인(DFAx)과 RL 애플리케이션에 오토마타 작업을 통합하기 위한 Python 패키지를 구현하였다.

4. 실험 결과

프레임워크는 버튼, 문, 토큰이 포함된 레이아웃을 가진 2인 및 4인 변형을 특징으로 하는 이산적이고 완전 관측 가능한 환경인 TokenEnv에서 평가되었다.

• 실행 가능성 및 확장성 (Q1 & Q2):
  • 절제 연구(Ablation studies) 결과, 제안된 솔루션(특히 PBRS 및 RAD 임베딩)이 없으면 정책이 수렴하지 못하거나 낮은 성공률(<0.5)을 보임을 확인했다.
  • 2인 환경에서는 사전 학습된 인코더와 학습되지 않은 인코더가 유사하게 작동하지만, 사전 학습된 임베딩이 더 낮은 분산을 제공한다.
  • 4인 환경에서 사전 학습된 RAD 임베딩을 사용하는 정책이 처음부터 표현을 학습하는 방식보다 현저히 우수한 성능을 보여, 확장을 위해 사전 학습이 필수적임을 확인했다.
• 일반화 (Q3):
  • RAD DFA로 학습된 정책은 학습 시 보지 못한 작업 클래스(Reach 및 ReachAvoid)와 학습된 것보다 상태 수가 많은 분포 외(OOD) DFA에 대해서도 일반화된다.
  • 사전 학습된 임베딩은 특히 "Avoid" 제약(회복 불가능한 조건)이 포함된 작업에서 성능을 향상시킨다.
• 작업 할당 (Q4):
  • 대칭 환경(Buttons)에서는 작업 할당 순서가 미미한 영향을 미쳤다.
  • 비대칭 환경(Rooms)에서는 학습된 가치 함수로부터 도출된 최적 작업 할당이 무작위 할당에 비해 팀 성공 확률을 유의미하게 향提高시켰다.
• 창발적 행동 (Q5):
  • 질적 분석 결과, 에이전트가 시간을 아끼기 위해 팀원을 위해 문을 잡아주거나, 한 에이전트가 다른 에이전트가 더 짧은 경로를 이용할 수 있도록 문을 여는 것과 같은 창발적 협력 기술이 나타났다.

5. 의의 및 주장

본 논문은 런타임에 작업이 할당되는 멀티태스크 협력 MARL 설정에서 형식적 명세(DFA)를 활용한 첫 번째 연구라고 주장한다. 그 의의는 다음과 같다:

• 형식 방법론과 MARL의 가교 역할: 오토마타 조건부 RL을 단일 에이전트에서 다중 에이전트 설정으로 확장하여, 복잡한 팀 목표를 하위 작업으로 분해할 수 있게 한다.
• 확장성 문제 해결: 사전 학습된 임베딩을 통해 표현 학습을 분리함으로써, 이전에 오토마타 조건부 MARL을 소규모 팀으로 제한했던 성능 병목 현상을 해결한다.
• 최적성: 효율적인 신용 할당과 일반화를 가능하게 하면서도 원래의 비마르코프 문제에 대해 최적의 팀 행동을 보장하는 이론적 근거를 제공한다.

저자들은 고정된 레이블링 함수 가정, 완전 관측성, 그리고 매우 큰 팀에 대한 작업 할당 열거의 계산 비용 등을 한계점으로 언급하였다. 향후 연구 과제로 부분 관측성, 동적 레이블링, 연속 도메인 적용 등을 제시하였다.