🤖 machine learning

CAPO: Counterfactual Credit Assignment in Sequential Cooperative Teams

이 논문은 고정된 순서로 행동하는 협력 팀에서 각 에이전트의 기여도를 명확히 파악하고 학습 효율성을 극대화하기 위해, 기존 아리스토크랫 유틸리티를 확장한 'SeqAU'를 기반으로 크리틱이 없는 정책 경사 알고리즘인 CAPO 를 제안합니다.

원저자: Shripad Deshmukh, Jayakumar Subramanian, Raghavendra Addanki, Nikos Vlassis

게시일 2026-04-21

📖 3 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Shripad Deshmukh, Jayakumar Subramanian, Raghavendra Addanki, Nikos Vlassis

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

🌸 상황: 팀 프로젝트의 딜레마

여러 명의 정원사 (에이전트) 가 있다고 상상해 보세요.

정원사 A가 먼저 씨앗을 심습니다.
정원사 B가 그 씨앗에 물을 줍니다.
정원사 C가 비료를 줍니다.
마지막에 한 송이 장미가 피어납니다.

이제 팀장은 "이 장미가 예쁘게 핀 건 팀 전체의 점수 100 점"이라고만 알려줍니다.

"씨앗을 심은 A 가 30 점, 물을 준 B 가 40 점, 비료를 준 C 가 30 점"이라고 누가 알 수 있을까요?
특히, A 가 먼저 배운 뒤 B 를 가르치고, B 가 배운 뒤 C 를 가르치는 순서로 학습을 시킨다면, A 가 배운 내용은 이미 B 와 C 의 행동에 영향을 미쳐서 과거 데이터가 더 이상 유효하지 않게 됩니다. (이걸 '비정상성'이라고 합니다.)

기존 방법들은 이 문제를 해결하기 위해 너무 복잡하거나, 계산량이 너무 많거나, 혹은 엉뚱한 결론을 내는 경우가 많았습니다.

💡 해결책: CAPO (카포) 라는 새로운 방법

이 논문은 CAPO라는 새로운 알고리즘을 소개합니다. CAPO 는 **"만약 네가 다른 행동을 했다면, 꽃은 어떻게 변했을까?"**를 상상하는 능력을 활용합니다.

1. "가상의 꽃"을 피워보세요 (Counterfactual Thinking)

기존 방법들은 "실제 꽃"만 보고 점수를 매기려 했지만, CAPO 는 가상의 꽃을 키웁니다.

"A 가 씨앗을 심을 때, 만약 B 가 물을 주는 대신 다른 물을 줬다면 꽃은 어땠을까?"
"C 가 비료를 줄 때, 만약 다른 비료를 줬다면 어땠을까?"

이렇게 **가상의 시나리오 (Counterfactual)**를 컴퓨터 안에서 빠르게 시뮬레이션해서, 각 정원사가 실제로 한 행동이 팀 점수에 얼마나 영향을 미쳤는지 정확히 따져봅니다.

2. "상류의 물"을 차단하는 마법 (Upstream Cancellation)

여기서 CAPO 의 가장 멋진 아이디어가 나옵니다.

A 가 씨앗을 심은 뒤, B 와 C 가 물을 주고 비료를 줍니다.
A 의 공헌을 계산할 때, B 와 C 가 이미 변한 행동까지 고려해야 하나요?
CAPO 는 **"아니요"**라고 말합니다. A 가 씨앗을 심은 시점에서는 B 와 C 의 행동이 아직 결정되지 않았으므로, A 의 공헌은 A 가 직접적으로 한 일과 A 가 B 와 C 의 행동을 어떻게 바꿨는지 두 가지로만 나뉩니다.
이걸 수학적으로 정리하면, 불필요한 복잡한 계산 (기존 방법들이 겪던 '폭발적인 계산량') 을 모두 없애고 간단한 식으로 공헌도를 구할 수 있습니다.

3. "실제 실험" 대신 "상상력"을 쓰다

기존 방법 중 하나는 "B 가 물을 주는 대신 다른 물을 주는 실험을 실제로 해봐!"라고 해서 매번 새로운 꽃을 피워보게 했습니다. (시간과 비용이 너무 많이 듦)

CAPO 는 실제 실험을 하지 않습니다.
대신, 현재 가진 데이터 (씨앗을 심은 상태) 를 바탕으로 **"만약 B 가 다른 물을 줬다면, 우리 팀의 AI 가 어떻게 반응했을지"**를 **상상 (시뮬레이션)**만 합니다.
이 상상은 컴퓨터가 순식간에 할 수 있으므로, 실제 환경에 부딪히지 않고도 정확한 점수를 매길 수 있습니다.

🚀 왜 이게 중요한가요? (결과)

이 방법은 특히 팀원이 많을수록 더 강력해집니다.

팀원이 2 명일 때: 기존 방법들도 잘 작동합니다.
팀원이 10 명일 때: 기존 방법들은 계산이 너무 복잡해지거나, "누가 잘못했는지"를 잘못 판단해서 팀이 엉망이 됩니다. (점수 계산의 오차가 팀원 수에 비례해서 폭발합니다.)
CAPO 는? 팀원이 많아져도 오차가 거의 일정하게 유지됩니다. 각 정원사의 공헌도를 정확히 따져주기 때문에, 팀이 커질수록 더 잘 학습합니다.

📝 한 줄 요약

"팀 점수만 받는 순서형 팀에서, 각 멤버가 얼마나 공헌했는지 알기 위해 '가상의 시나리오'를 상상하고, 불필요한 계산을 줄여서 정확한 보상을 주는 새로운 방법 (CAPO) 을 개발했다."

이 기술은 앞으로 여러 개의 AI 가 순서대로 작업을 하는 복잡한 시스템 (예: 한 AI 가 글을 쓰고, 다른 AI 가 수정하고, 또 다른 AI 가 그림을 그리는 작업) 에서 각 AI 가 얼마나 잘했는지 평가하고 학습시키는 데 큰 역할을 할 것으로 기대됩니다.

CAPO: 순차적 협력 팀을 위한 반사실적 신용 할당 (Counterfactual Credit Assignment in Sequential Cooperative Teams)

이 논문은 고정된 순서로 행동하고 단일 팀 보상을 공유하는 협력적 다중 에이전트 시스템에서 발생하는 신용 할당 (Credit Assignment) 문제를 해결하기 위해 제안된 CAPO (Counterfactual Advantage Policy Optimization) 알고리즘과 그 이론적 기반을 다룹니다. 특히, 에이전트들이 한 번에 하나씩 업데이트될 때 발생하는 데이터의 비정상성 (Non-stationarity) 문제를 효과적으로 처리하는 데 중점을 둡니다.

1. 문제 정의 (Problem)

협력적 다중 에이전트 시스템 (예: 대형 언어 모델 (LLM) 파이프라인, 도구 사용 에이전트 등) 에서 에이전트들은 고정된 순서 (1, 2, ..., K) 로 행동하며, 최종적으로 하나의 팀 보상 (Team Reward) 만을 공유받습니다. 이때 다음과 같은 주요 어려움이 존재합니다.

신용 할당의 모호성: 팀 전체의 보상만 주어지므로, 각 에이전트의 행동이 팀 성과에 얼마나 기여했는지 개별적으로 파악하기 어렵습니다.
순차적 업데이트로 인한 비정상성 (Non-stationarity): 에이전트들이 배치 (Batch) 내에서 한 번에 하나씩 업데이트될 때, 이전 에이전트의 정책이 변경되면 이후 에이전트들이 관찰하는 데이터 분포가 바뀝니다. 즉, 초기에 수집된 데이터는 이후 업데이트되는 에이전트들에게는 '오프-폴리시 (Off-policy)' 데이터가 되어 학습을 방해합니다.
기존 방법론의 한계:
- 중앙 집중식 크리틱 (Centralized Critic): 입력 공간이 팀 크기에 따라 지수적으로 증가하여 확장성이 떨어집니다.
- 누적 중요도 샘플링 (Cumulative Importance Sampling): 업데이트된 에이전트 수가 늘어날수록 분산이 지수적으로 증가합니다 (예: HAPPO, HA-GRPO).
- 재플레이 (Replay) 기반 방법: 실제 환경에서 하위 에이전트들의 행동을 재실행해야 하므로 계산 비용이 매우 높습니다 (예: C3).

2. 방법론 (Methodology)

논문은 순차적 아리스토크라트 유틸리티 (Sequential Aristocrat Utility, SeqAU) 를 도입하고, 이를 기반으로 크리틱이 없는 (Critic-free) 정책 경사 알고리즘인 CAPO를 제안합니다.

2.1. 순차적 아리스토크라트 유틸리티 (SeqAU)

Wolpert 와 Tumer 의 'Aristocrat Utility (AU)' 개념을 순차적 설정으로 확장한 것입니다.

개념: 에이전트 $k$ 의 유틸리티는 팀 보상에서 $k$ 의 행동에 대한 기대값을 뺀 값으로 정의됩니다.
최적성: 순차적 설정에서 각 에이전트의 학습 가능성 (Learnability) 을 최대화하는 유일한 기준선 (Baseline) 은 선행 에이전트들의 행동 (Prefix, $a_{<k}$ ) 에 조건부인 기대 보상입니다.
식: $A^{SeqAU}_k = E_{\pi}[R | a_{\le k}] - E_{\pi}[R | a_{<k}]$ $A_{k}^{S e q A U} = E_{π} [R ∣ a_{\leq k}] - E_{π} [R ∣ a_{< k}]$
- 이는 COMA 알고리즘의 반사실적 이점과 유사하지만, 순차적 업데이트의 비정상성을 고려하여 도출되었습니다.

2.2. CAPO 알고리즘의 세 가지 핵심 요소

SeqAU 를 실제 계산 가능한 추정기로 만들기 위해 다음 세 가지 기법을 결합합니다.

가산적 보상 분해 (Additive Reward Decomposition):
- 팀 보상을 각 에이전트의 행동에 대한 개별 기여도의 합으로 근사합니다 ( $R(a) \approx \sum \phi_k(a_k)$ ).
- 릿지 회귀 (Ridge Regression) 를 사용하여 단일 배치 데이터로부터 각 에이전트의 기여도 ( $\phi_k$ ) 를 폐쇄형 (Closed-form) 으로 추정합니다. 이는 학습된 크리틱을 필요로 하지 않습니다.
상류 상쇄 (Upstream Cancellation):
- SeqAU 이점을 계산할 때, 현재 에이전트 $k$ 보다 앞선 에이전트들의 기여도는 두 항 (조건부 기대값) 에서 동일하게 나타나 서로 상쇄됩니다.
- 결과적으로 이점은 직접 효과 (Direct Effect) 와 간접 효과 (Indirect Effect) 두 부분으로 단순화됩니다.
  - 직접 효과: 에이전트 $k$ 의 행동 변화에 따른 즉각적인 보상 변화.
  - 간접 효과: 에이전트 $k$ 의 행동이 하위 에이전트들의 행동 분포를 변화시켜 발생하는 보상 변화.
가상 샘플링 (Fictitious Sampling) 을 통한 간접 효과 추정:
- 간접 효과를 추정하기 위해 실제 환경 재실행이나 중요도 샘플링 (IS) 을 사용하지 않습니다.
- 대신, 현재 정책 ( $\pi$ ) 을 사용하여 각 롤아웃의 선행 행동 (Prefix) 을 고정하고, 하위 에이전트들의 행동을 가상적으로 샘플링하여 기대값을 계산합니다.
- 이 방식은 IS 의 분산 증가 문제를 피하고, 환경 상호작용 비용을 최소화합니다.

3. 주요 기여 (Key Contributions)

이론적 확장 (Theorem 1): Wolpert 와 Tumer 의 프레임워크를 순차적 협력 팀으로 확장하여, 학습 가능성을 최대화하는 유일한 기준선인 SeqAU를 증명했습니다.
CAPO 알고리즘: 크리틱이 필요 없으며, 가산적 분해, 상류 상쇄, 가상 샘플링을 통해 효율적으로 반사실적 이점을 추정하는 알고리즘을 제시했습니다.
정밀한 편향 및 분산 분석 (Theorems 2-4):
- 편향: 보상이 가산적이지 않을 때 발생하는 편향은 비가산성 잔차 (Residual) 에 선형적으로 비례합니다.
- 분산: 공유 기준선 방법 (MA-GRPO) 은 팀 크기에 비례하여 분산이 증가하고, 누적 IS 방법 (HA-GRPO) 은 지수적으로 증가하는 반면, CAPO 는 정책의 분해 구조에 따라 분산이 적응합니다 (최대 $O(K-k)$ 또는 $K$ 와 무관).
- 기대 오차: 중요도 샘플링 비율로 인한 분산 증가가 없습니다.
실험적 검증: 통제된 순차적 밴디트 (Sequential Bandit) 환경에서 이론적 예측을 검증하고, 팀 크기가 커질수록 CAPO 의 성능 우위가 커짐을 입증했습니다.

4. 실험 결과 (Results)

이점 추정 품질 (Advantage Estimation Quality):
- 팀 크기 ( $K$ ) 가 증가함에 따라 CAPO 의 평균 제곱 오차 (MSE) 는 거의 일정하게 유지되는 반면, MA-GRPO 는 선형적으로, HA-GRPO 는 더 빠르게 증가했습니다.
- $K=16$ 일 때, CAPO 는 C3 보다 약 2 배, MA-GRPO 보다 30 배, HA-GRPO 보다 46 배 낮은 MSE 를 기록했습니다.
비가산적 보상 견고성:
- 보상 구조가 가산적이지 않을 때 (상호작용 강도 증가), CAPO 의 오차는 예측대로 선형적으로 증가했으나 여전히 다른 방법들보다 우수한 성능을 보였습니다.
종단간 최적화 (End-to-End Optimization):
- 팀 크기가 커질수록 (특히 $K \ge 6$ ) CAPO 의 누적 후회 (Regret) 가 MA-GRPO 및 HA-GRPO 보다 현저히 낮았습니다.
- HA-GRPO 는 팀 크기가 커짐에 따라 분산 폭주로 인해 성능이 급격히 저하되었습니다.
간접 효과의 중요성 (Ablation Study):
- 비정상성이 없는 상황 ( $\rho=0$ ) 에서는 간접 효과를 제거한 'CAPO-Direct'가 CAPO 와 유사하거나 더 좋았습니다.
- 그러나 비정상성이 존재할 때 ( $\rho \ge 10$ ), 간접 효과를 포함한 CAPO 가 압도적으로 성능이 우수하여, 순차적 업데이트 환경에서 간접 효과 보정이 필수적임을 입증했습니다.

5. 의의 및 결론 (Significance)

확장성: CAPO 는 크리틱 학습이나 환경 재실행 없이도 대규모 협력 팀 (예: 다중 LLM 파이프라인) 에서 효율적으로 작동합니다.
이론적 엄밀성: 순차적 협력 학습에 대한 체계적인 편향 - 분산 분석을 제공하여, 기존 방법론들의 한계를 명확히 규명하고 새로운 기준을 제시했습니다.
실용성: 계산 비용이 높은 보상 평가 (예: 인간 평가, 코드 실행) 가 필요한 시나리오에서, 최소한의 환경 상호작용으로 최적의 신용 할당을 가능하게 합니다.

결론적으로, CAPO 는 순차적 협력 다중 에이전트 시스템에서 발생하는 비정상성과 신용 할당 문제를 해결하기 위한 이론적으로 엄밀하고 실용적으로 효율적인 프레임워크를 제공합니다.