기술 요약: 공동 경험 최적 대응을 통한 샘플 효율적 정책 공간 응답 오라클

1. 문제 정의

다중 에이전트 강화 학습(MARL)은 정밀한 게임 이론적 분석에 대한 확장 가능한 대안을 제공하지만, 두 가지 주요 과제에 직면해 있습니다: 비정상성(에이전트가 업데이트됨에 따라 환경이 변화하는 독립적 학습의 문제)과 다양한 전략 팝퓰레이션 유지(비전이적 상호작용을 포착하기 위함)입니다. 정책 공간 응답 오라클(PSRO) 프레임워크는 근사 최적 대응(Best Responses, BRs)을 통해 제한된 게임을 반복적으로 확장함으로써 이 문제를 해결합니다.

그러나 표준 PSRO는 과도한 계산 및 샘플 비용 문제로 어려움을 겪습니다. 각 반복 단계에서 모든 에이전트는 다른 에이전트들의 현재 메타 전략 프로필에 대해 독립적으로 최적 대응을 계산해야 합니다. 이는 남은 에이전트들을 완전히 시뮬레이션해야 하는 수많은 강화 학습(RL) 문제를 해결하는 것과 같으며, 플레이어 수가 많거나 시뮬레이터가 비싼 도메인에서는 이러한 에이전트별 훈련 구조로 인해 PSRO를 실행 불가능하게 만듭니다.

2. 방법론

핵심 개념: 공동 경험 최적 대응 (Joint Experience Best Response, JBR)

저자들은 모든 에이전트 간에 상호작용 데이터를 재사용하는 PSRO의 수정 방식인 **공동 경험 최적 대응(JBR)**을 제안합니다. JBR은 각 에이전트의 최적 대응을 독립적으로 훈련하는 대신 다음을 수행합니다:

1. 현재 메타 전략 프로필 $\sigma = (\sigma_j)_{j \in N}$ 하에서 궤적(trajectories)을 단 한 번 수집합니다.
2. 전환 $(s_t, a_{1,t}, \dots, a_{n,t}, r_{1,t}, \dots, r_{n,t}, s_{t+1})$을 포함하는 공유 공동 데이터셋 $\mathcal{D}_\sigma$를 구축합니다.
3. 이 단일 데이터셋으로부터 모든 에이전트의 최적 대응을 동시에 계산합니다.

이를 통해 최적 대응 계산을 온라인 RL 문제에서 고정된 데이터셋으로부터 정책을 최적화하는 오프라인 RL 문제로 전환합니다. 이는 샘플 효율성을 획기적으로 개선하지만, 데이터셋이 현재 메타 전략 하에서 생성되었기 때문에 진정한 최적 대응에 유효한 상태-행동 영역을 충분히 커버하지 못할 수 있다는 **분포 변화 편향(distribution-shift bias)**을 야기합니다.

오프라인 RL 편향 해결

JBR의 한계(특히 분포 변화)를 완화하기 위해, 논문은 세 가지 상호 보완적인 해결책을 도입합니다:

1. 보수적 JBR (안전한 정책 개선):

   • 학습된 정책 $\pi_i$가 데이터셋에 의해 충분히 커버된 상태-행동 쌍(카운트 $N_D(s, a_i) \ge N^\wedge$)에서만 베이스라인 메타 전략 $\sigma_i$로부터 벗어나도록 제약을 가합니다.
   • 샘플링이 부족한 영역에서는 정책이 $\sigma_i$로 회귀하여, 성능이 베이스라인 아래로 저하되지 않음을 보장합니다.
   • 한계: 안전하지만, 독립적 BR에 비해 상당한 개선을 찾는 능력을 제한할 만큼 지나치게 조심스럽습니다.

2. 탐색 증강 JBR (Exploration-Augmented JBR):

   • 커버리지를 개선하기 위해 데이터 수집 과정을 변형합니다. 에이전트들은 엄격하게 $\sigma$에 따라 행동하는 대신, $\delta$-변형된 메타 전략을 따릅니다:
     $$\tilde{\sigma}_j(a_j|s) = (1-\delta)\sigma_j(a_j|s) + \delta\nu_j(a_j|s)$$
   • 두 가지 탐색 전략이 제안됩니다:
     • $\delta$-랜덤 ($\delta$-R): $\nu_j$는 균등 무작위 정책(uniform random policy)입니다.
     • $\delta$-타겟형 ($\delta$-T): $\nu_j$는 현재의 최적 대응 후보인 $\pi^{BR,cur}_j$입니다. 이는 탐색을 유망한 궤적으로 유도하며, 효과적인 상대 모델링(opponent modeling)의 형태로서 작용합니다.
   • 이론적 보장: 논문은 유한 2인 제로섬 게임에 대해, 에이전트들이 변형된 전략 $\tilde{\sigma}$에 대한 $\epsilon$-최적 대응을 계산하면, 결과적인 메타 전략이 원래 게임의 $(\epsilon + 2R\delta)$-내쉬 균형(Nash equilibrium)이 됨을 증명합니다 (여기서 $R$은 보상 범위입니다).

3. 하이브리드 최적 대응 (Hybrid Best Response, HBR):

   • JBR과 표준 독립 최적 대응(Independent BR)을 교대로 수행합니다.
   • 대부분의 반복에서는 효율성을 위해 JBR을 사용합니다. 매 $k$번째 반복마다, 에이전트는 근사 오차를 수정하기 위해 표준 독립 BR 업데이트를 수행합니다.
   • 이는 JBR의 샘플 효율성과 IBR의 정확성을 결합하는 것을 목표로 합니다.

3. 주요 기여

1. JBR 프레임워크: 모든 에이전트의 최적 대응을 동시에 계산하기 위해 공유 궤적을 재사용하여 샘플 효율성을 크게 향상시키는, PSRO의 드롭인(drop-in) 수정 방식인 공동 경험 최적 대응의 도입.
2. 오프라인 편향에 대한 해결책: JBR에 내재된 오프라인 RL의 한계를 식별하고, 세 가지 구체적인 해결책(보수적 JBR, 탐색 증강 JBR(이론적 수렴 보장 포함), 하이브리드 BR)을 제안 및 평가함.
3. 포괄적 실증 연구: 이산적(포커) 및 연속적(입자) 환경 전반에 걸쳐 JBR 변형 모델들을 표준 PSRO(독립적 BR) 및 주요 MARL 베이스라인(독립적 학습 및 CTDE)과 엄격하게 비교함.

4. 실험 결과

환경

• 이산적: Kuhn Poker (작고 완전히 커버된 상태 공간) 및 Leduc Poker (더 큰 상태 공간, 불완전 정보).
• 연속적: Simple Tag, Simple Adversary, Simple Push (다중 에이전트 입자 환경).

주요 결과

• 단순 도메인에서의 실행 가능성: 상태 공간이 작고 완전히 커버된 Kuhn Poker에서 JBR은 표준 PSRO와 동일한 수렴 동작을 보여, 잘 샘플링된 조건 하에서의 실행 가능성을 확인했습니다.
• 나이브(Naïve) JBR의 실패: Leduc Poker에서 탐색이나 보수성이 없는 나이브 JBR은 오프라인 학습 편향으로 인해 균형 정확도를 유지하지 못하고 PSRO보다 높은 착취 가능성(exploitability)에서 정체되었습니다.
• 변형 모델의 효과:
  • 보수적 JBR은 안정적이지만, 과도한 주의성으로 인해 PSRO에 비해 성능이 낮았습니다.
  • **탐색 증강 JBR ($\delta$-R)**은 완만한 이득을 보였으나 방향성이 부족했습니다.
  • **탐색 증강 JBR ($\delta$-T)**은 최적의 트레이드오프를 달성하여, 훨씬 적은 샘플로도 PSRO에 근접한 균형 정확도에 도달했습니다. 타겟형 탐색은 상대방의 업데이트를 예측하여 더 빠른 초기 수렴을 이끌어냈습니다.
  • **하이브리드 BR (HBR-PSRO)**은 약간의 샘플 비용 증가만으로 PSRO와의 남은 정확도 격차를 좁혔습니다.
• 샘플 효율성: JBR-PSRO-$\delta$T는 표준 PSRO가 요구하는 총 최적 대응 에피소드의 약 절반 정도만을 사용하여 근사 PSRO 수준의 NashConv에 도달했습니다.
• MARL과의 비교: 모든 환경에서 PSRO 기반 방법들(JBR 변형 포함)은 전략적 강건성 및 균형 정확도 측면에서 표준 MARL 패러다임(독립적 학습 및 CTDE)을 일관되게 능가했습니다.

5. 의의 및 주장

본 논문은 JBR이 균형 강건성을 유지하면서도 PSRO를 실질적으로 더 유용하게 만든다고 주장합니다.

• 확장성: 에이전트 간의 환경 상호작용을 분담함으로써, JBR은 최적 대응 계산의 샘플 비용을 줄여 다수 에이전트 또는 시뮬레이터가 비싼 설정에서의 PSRO의 주요 병목 현상을 해결합니다.
• 강건성: 결과는 샘플 효율적으로 만들어졌을 때도 (PSRO 스타일의) 전략적으로 기초를 둔 훈련이 표준 MARL 접근 방식보다 여전히 더 강건함을 확인시켜 줍니다.
• 실제 배포: 제안된 변형 모델들, 특히 JBR-PSRO-$\delta$T와 HBR-PSRO는 학습된 균형의 질을 희생하지 않으면서, 환경 상호작용 비용이 실행 시간의 지배적인 요소인 도메인에 PSRO를 배포할 수 있는 실행 가능한 경로를 제공합니다.

저자들은 JBR이 효율성을 개선하지만, PSRO와 그 변형 모델들은 여전히 일반적인 MARL 방법들보다 더 많은 반복과 샘플을 필요로 하며, 고차원 연속 도메인으로의 확장성은 향후 과제로 남아 있다고 언급했습니다.