기술 요약: 불완전 정보 자기대결에서 GAE 의 부진

문제 제기

불완전 정보 게임에서의 경쟁적 다중 에이전트 강화학습 (MARL) 은 에이전트가 적대적인 상대에 대해 부분 관측성 하에서 작동해야 하므로 확률적 정책이 필수적입니다. 근접 정책 최적화 (PPO) 를 활용한 자기대결 강화학습은 경험적으로 성공을 거두었으나, 균형 학습에서 이점 추정 분산이라는 치명적인 병목 현상에 직면해 있습니다.

일반적인 PPO 구현은 다단계 시간차 (TD) 잔차를 집계하기 위해 일반화된 이점 추정 (GAE) 에 의존합니다. 단일 에이전트 환경에서 GAE 는 편향과 분산 사이의 균형을 효과적으로 유지합니다. 그러나 불완전 정보 자기대결에서는 균형 정책이 본질적으로 확률적입니다. GAE 는 다단계 추적 내 미래 행동의 샘플링에서 무작위성을 물려받습니다. 균형 정책은 서로 다른 행동에 서로 다른 가치를 부여하므로, 미래 행동의 샘플링은 고유한 노이즈를 도입합니다. 이 분산은 자기대결 시나리오에서 증폭되며, 상태 가치 비평가 ($V$-critic) 가 정확하더라도 지속됩니다. 결과적으로 표준 GAE 는 안정적인 학습이 가장 중요한 영역에서 고분산 그라디언트 추정을 생성하여 고품질 균형으로의 수렴을 방해합니다.

방법론

Q-부스팅 추정기

행동 샘플링으로 인한 분산을 해결하기 위해 저자들은 **Q-부스팅 (Q-boosting)**이라는 분산 감소 이점 추정기를 제안합니다. 핵심 혁신은 GAE 에서 사용되는 샘플링된 다단계 TD 추적을 중앙 집중식 행동 가치 비평가 ($Q$-critic) 로부터 계산된 다단계 기대 SARSA($\lambda$) 추적 으로 대체하는 것입니다.

• 메커니즘: 샘플링된 다음 행동을 통한 부트스트래핑 (노이즈를 유발함) 대신, Q-부스팅은 각 백업 단계에서 정책 기대값을 계산합니다. 이는 현재 정책이 정의한 행동 분포에 대한 기대값을 취함으로써 확률적 미래 행동의 노이즈를 평균화합니다.
• 수식화: 중앙 집중식 $Q$-critic $Q_i(s, a)$와 결합 정책 $\pi$가 주어졌을 때, 상태 가치는 $V^\pi_i(s) = \sum_a \pi(a|s) Q_i(s, a)$로 계산됩니다. Q-부스팅 이점 추정치 $\hat{A}^{boost}_{i,\tau}$는 다음과 같이 정의됩니다:
  $$\hat{A}^{boost}_{i,\tau} \triangleq Q_i(s_\tau, a_\tau) - V^\pi_i(s_\tau) + \sum_{\tau' \ge \tau} (\lambda\gamma)^{\tau'-\tau} \cdot \delta^+_{i,\tau'}$$
  여기서 기대 SARSA 시간차 잔차는 $\delta^+_{i,\tau'} \triangleq r_{i}(s_{\tau'}, a_{\tau'}) + \gamma V^\pi_i(s_{\tau'+1}) - Q_i(s_{\tau'}, a_{\tau'})$입니다.
• 이론적 보장: 저자들은 온-정책 (on-policy) 궤적과 $\lambda=1$에 대해 Q-부스팅 추정기가 스코어 함수 정책 그라디언트 항의 편향 없는 추정을 제공함을 증명합니다. 또한, $Q$-critic 이 충분히 정확하다면, 미래 행동의 행동 가치에 0 이 아닌 분산이 존재하는 한, Q-부스팅 추정기의 평균 제곱 오차는 정확한 $V$-critic 을 가진 GAE 보다 엄격하게 낮습니다.

분산 감소 정책 최적화 (VRPO)

저자들은 Q-부스팅을 **분산 감소 정책 최적화 (VRPO)**라는 PPO 스타일 알고리즘에 통합합니다.

• 아키텍처: VRPO 는 중앙 집중식 훈련과 분산 실행 (CTDE) 패러다임을 따릅니다. 실행을 위한 분산 에이전트와 훈련을 위한 중앙 집중식 $Q$-critic 을 활용합니다.
• 목적: 이 알고리즘은 PPO 의 클리핑된 대리 목적 함수와 신뢰 영역 업데이트를 유지하지만, 이점 추정 및 비평가 학습 절차를 수정합니다.
• 훈련 절차:
  1. 에이전트 업데이트: 에이전트는 Q-부스팅 이점 추정을 사용하여 업데이트됩니다. 온-정책 속성을 유지하기 위해, 이점 계산에 사용되는 정책 기대값 항은 고정된 비평가 값을 유지하면서 현재 에이전트 확률을 사용하여 재계산됩니다.
  2. 비평가 업데이트: 중앙 집중식 $Q$-critic 들은 Q-부스팅 목표 (다단계 기대 SARSA 추적) 에 대한 제곱 회귀 손실을 최소화하도록 훈련됩니다.
  3. 정규화: 탐험을 장려하고 마지막 반복 수렴을 촉진하기 위해 균등 분포에 대한 명시적 KL-발산 패널티가 정책 목적 함수에 추가됩니다.
• 대규모 행동 공간 처리: 두더지 (Dou Dizhu) 와 같이 거대한 행동 집합을 가진 게임의 경우, 저자들은 복잡한 결정을 여러 시간 단계로 분해합니다. 이는 각 단계에서 사용 가능한 행동의 수를 관리 가능한 크기로 줄여, Q-부스팅 추적에 필요한 정책 기대값을 위한 열거를 가능하게 합니다.

주요 기여

1. 분산 원인 규명: 이 논문은 GAE 에서의 미래 행동 샘플링이 확률적 자기대결에서 추가적인 분산을 도입하며, 이는 정확한 가치 함수가 있더라도 지속된다고 규명합니다.
2. Q-부스팅 추정기: 저자들은 중앙 집중식 $Q$-critic 에 기대 SARSA($\lambda$) 추적을 적용하여 미래 행동 샘플링 노이즈를 평균화하는 PPO 호환 추정기인 Q-부스팅을 유도했습니다.
3. VRPO 알고리즘: Q-부스팅을 활용하여 향상된 안정성과 성능을 달성하는 PPO 스타일 알고리즘인 VRPO 를 제안했습니다.
4. 경험적 검증: 이점 추정 분산을 줄이는 것이 다양한 규모의 게임에서 균형 품질에 상당한 개선을 가져온다는 것을 입증했습니다.

실험 결과

중형 게임 (정확한 착취 가능성)

저자들은 정확한 착취 가능성을 계산할 수 있는 중형 게임인 급작스러운 팬텀 틱택토 (APTTT), 급작스러운 다크 헥스 3 (ADH3), 그리고 2 개의 주사위와 5 개의 면을 가진 거짓말주사위 (LiDi 2D5F) 에서 VRPO 를 벤치마크했습니다.

• 성능: 공유 훈련 스케줄 하에서 VRPO 는 다양한 PPO 기반 베이스라인 (IPPO, MAPPO, MMD, PPG) 에 비해 15% 이상 낮은 착취 가능성을 일관되게 달성했습니다.
• 애블레이션: 성능 향상이 다양한 추적 파라미터 ($\lambda$), 정규화 계수 ($\alpha$), PPO 클리핑 계수 ($\epsilon$) 에서 견고하게 유지됨을 실험을 통해 확인했습니다.

대규모 게임

저자들은 정확한 착취 가능성이 계산 불가능한 대규모 도메인에서 VRPO 를 평가했습니다.

• 두더지 (Dou Dizhu): VRPO 는 이전 최첨단 에이전트인 PerfectDou 와 대결하며 훈련되었습니다. 일치된 훈련 예산 ($\approx 2.65 \times 10^9$ 타임스텝) 하에서 VRPO 는 훈련 단계의 40% 만으로도 PerfectDou 를 능가했습니다. 10 만 건의 딜에 대한 정면 대결 평가에서 VRPO 는 PerfectDou, DouZero, 그리고 역할이 바뀐 자기 대결 (role-swapped matchups) 에서 모두 긍정적인 성과를 거두어 새로운 최첨단을 확립했습니다.
• 헤즈업 노리미트 텍사스 홀덤 (HUNL): VRPO 는 200 빅블라인드 스택으로 HUNL 에서 훈련되었습니다. IPPO 와 MAPPO 와 비교하여 VRPO 는 훈련 중 이점 추정치의 표준 편차를 현저히 감소시켰습니다. 강력한 베이스라인인 Slumbot 에 대해, VRPO 에이전트는 100 만 핸드에 걸쳐 핸당 $33 \pm 19$ mBB 의 평균 수익을 달성했습니다. 주목할 점은 이 성능이 온라인 검색, 서브게임 해결, 또는 청사진 기반 레이즈 사이징 없이 달성되었다는 것입니다.

중요성과 범위

이 논문은 주요 기여로 균형 자기대결에서의 병목 현상인 이점 추정 분산을 규명하고, Q-부스팅이 이 문제를 효과적으로 완화한다는 것을 입증했다고 주장합니다. 결과는 이점 추정에서의 분산을 줄이는 것이 학습된 균형의 품질에 상당한 개선을 가져올 수 있음을 시사합니다.

저자들은 주장의 범위를 겸손하게 유지합니다:

• 이 접근법은 (분해를 통해) 대규모 이산 행동 집합을 가진 게임에 대해 검증되었으나, 고차원 연속 행동 공간은 다루지 않습니다.
• 경험적 초점은 중앙 집중식 비평가를 사용하는 확률적 자기대결에 맞춰져 있으며, 표준 단일 에이전트 RL 벤치마크에서 GAE 에 대한 광범위한 개선을 주장하지는 않습니다.
• 이 방법은 행동에 대한 정책 기대값을 계산할 수 있는 능력에 의존하며, 이는 테스트된 도메인에서는 가능하지만 극도로 큰 행동 공간의 경우 특정 아키텍처적 고려가 필요할 수 있습니다.

결론적으로, VRPO 는 확률적 균형 학습에 내재된 이전에 충분히 식별되지 않았던 특정 분산 원인을 해결함으로써, 불완전 정보 게임에 정책 그라디언트 방법을 적용하는 데 있어 중요한 진전을 이루었습니다.