기술적 요약: 불완전 정보 게임에서 자기 플레이 탐색 가속화를 위한 데이터 증강 게임 시작

문제 제기

대규모 불완전 정보 경쟁 게임 (예: 스타크래프트, 도타, 카운터스트라이크) 에서 근사 균형을 찾는 것은 대부분의 실무자에게 여전히 계산적으로 불가능한 과제로 남아 있습니다. 주요 병목 현상은 전략적 상호작용의 해결이 아니라, 희소 보상, 긴 결정 지평선, 복잡한 숨겨진 상태 역학을 가진 환경에 내재된 탐색의 어려움입니다. 전통적인 자기 플레이 방법은 전략적으로 관련된 하위 게임에 도달하기 위해 조정된 행동의 긴 시퀀스를 반복적으로 탐색하는 데 계산 자원을 낭비하는 경향이 있는데, 이는 고수준 전략적 선택의 집합이 상대적으로 작음에도 불구하고 발생합니다.

인간 시연으로부터의 행동 복제 (Behavioral Cloning, BC) 는 역량을 부트스트랩하는 일반적인 접근 방식이지만, 필요한 기술을 학습하기 위해 광범위한 상태 - 행동 궤적이 필요합니다. 또한, 불완전 정보 게임을 위한 기존 벤치마크는 종종 실제 도메인에서 발견되는 탐색 과제 (희소 보상, 긴 지평선) 가 부족하여, 탐색을 가속화하도록 설계된 방법들을 평가하기 어렵게 만듭니다.

방법론: 데이터 증강 게임 시작 (DAGS)

저자들은 **데이터 증강 게임 시작 (Data-Augmented Game Starts, DAGS)**을 제안합니다. 이는 강화 학습 (RL) 에피소드를 항상 루트 상태에서 재시작하는 대신, 오프라인 게임 플레이 데이터에서 샘플링된 중간 상태에서 초기화함으로써 온라인 탐색을 가속화하는 전략입니다.

핵심 메커니즘

1. 오프라인 데이터셋: 이 방법은 숙련된 (하지만 반드시 최적은 아닐 수 있는) 게임 플레이에서 수집된 전역 상태의 오프라인 데이터셋 $D$를 활용합니다. 이러한 상태는 전략적으로 구별되는 게임 상황에 대한 광범위한 커버리지를 제공합니다.
2. 증강된 초기 상태 분포: DAGS 는 혼합 분포 $\tilde{d}^\beta_0 = (1 - \beta)d_0 + \beta d_D$를 정의합니다. 여기서 $d_0$는 원래 루트 분포이고 $d_D$는 오프라인 데이터셋에 대한 균일 분포입니다. 매개변수 $\beta \in [0, 1]$은 오프라인 상태에서 시작하는 에피소드의 비율을 제어합니다.
3. 자기 플레이와의 통합: 훈련 중 에피소드는 $\tilde{d}^\beta_0$에서 샘플링됩니다. 에피소드가 오프라인 상태에서 시작될 때, 환경은 원래 전이 역학에 따라 계속 진화하여 게임의 정보 구조를 유지합니다.
4. 균형 편향 완화: 저자들은 불완전 정보 게임에서 시작 상태 분포를 수정하면 에이전트의 사적 정보에 대한 신념이 왜곡되어 편향된 균형으로 이어질 수 있음을 식별했습니다. 이를 완화하기 위해 에피소드 소스를 나타내는 이진 관찰 플래그 ($f$: 루트 시작은 $f=0$, 데이터셋 시작은 $f=1$) 를 사용한 멀티태스크 학습을 도입합니다. 이를 통해 정책은 원래 게임 ($f=0$) 에 대한 편향되지 않은 전략을 학습하면서도, 공유 네트워크 매개변수를 통해 데이터셋 시작 에피소드 ($f=1$) 의 증강된 탐색을 활용할 수 있습니다.

벤치마크 구성

분석적으로 다루기 쉬운 악용 가능성 (exploitability) 을 가진 통제된 환경에서 DAGS 를 평가하기 위해, 저자들은 OpenSpiel 게임 (쿤 포커, 구프스피尔) 을 기반으로 한 새로운 벤치마크 환경 세트를 도입했습니다. 이러한 벤치마크는 두 가지 변환을 적용합니다:

1. 포기 (FF) 변환: 모든 결정 노드에 제어 작업을 실행하지 못함을 모델링하는 엄격하게 우세한 '포기' 행동을 추가합니다.
2. 제어 게임 변환: 각 결정을 다단계 그리드 월드 탐색 작업으로 대체합니다. 에이전트는 시간 제한 내에 특정 '행동 마름모'에 도달하기 위해 그리드를 탐색해야 합니다. 올바른 마름모에 도달하지 못하면 포기 행동이 발동됩니다.
   이러한 변환들은 그리드 월드 탐색을 통해 지평선과 상태 공간을 크게 증가시키면서도, 정책이 정확한 악용 가능성 계산을 위해 기본 게임으로 분석적으로 축소될 수 있도록 합니다.

주요 기여

1. 새로운 벤치마크 스위트: 저자들은 악용 가능성을 분석적으로 계산할 수 있는 긴 지평선과 탐색 과제 (그리드 월드 탐색) 를 가진 2 인 제로섬 (2p0s) 게임 세트를 제공합니다. 이는 전략적 복잡성과 다루기 쉬운 평가를 결합한 벤치마크의 부재를 해결합니다.
2. DAGS 를 통한 수렴 가속화: 이 논문은 DAGS 가 정규화된 정책 경사 알고리즘 (특히 PPO-Uniform 및 PPO-EMAg) 이 고정된 계산 예산 하에서 훨씬 더 큰 탐색 과제를 가진 게임에서 더 낮은 악용 가능성을 달성할 수 있음을 보여줍니다.
3. 균형 편향의 식별 및 완화: 이 연구는 시작 상태 분포를 증강하는 것이 불완전 정보 게임에서 학습된 균형을 편향시킬 수 있음을 보여줍니다. 그리고 편향되지 않은 플레이를 회복하기 위해 멀티태스크 관찰 플래그를 사용한 직관적인 완화 전략을 제공합니다.

실험 결과

저자들은 쿤 포커, 4 카드 구프스피尔, 그리고 균형 편향을 드러내도록 설계된 맞춤형 반례 게임에서 DAGS 를 평가했습니다.

• 탐색 확장: '컨트롤 트래블' 변형 (에이전트가 행동을 실행하기 위해 그리드를 탐색해야 하는 경우) 에서, 표준 자기 플레이 ($\beta=0$) 는 시간 제한 내에 특정 행동 마름모로 탐색하는 방법을 발견하지 못해 높은 악용 가능성 (실질적인 포기) 으로 이어졌습니다. DAGS ($\beta > 0$) 는 에피소드를 중간 상태에서 성공적으로 초기화하여 에이전트가 고수준 전략적 상호작용 해결에 집중할 수 있게 했습니다. 높은 난이도 (트래블 20) 의 구프스피尔에서 표준 자기 플레이는 높은 악용 가능성에서 정체되었으나, DAGS 는 낮은 악용 가능성으로 수렴을 계속했습니다.
• 균형 편향: 반례 게임에서 $\beta=1$ (항상 오프라인 데이터에서 시작) 로 설정하면 숨겨진 정보에 대한 왜곡된 신념으로 인해 에이전트가 높은 악용 가능성을 가진 편향된 균형으로 수렴하게 되었습니다.
• 완화 효과: 중간 $\beta$(예: 0.5) 를 작업 식별 관찰 플래그와 함께 사용하면 편향을 성공적으로 완화했습니다. $f=0$ 브랜치는 원래 게임에 대한 편향되지 않은 정책을 학습하는 반면, $f=1$ 브랜치는 탐색을 촉진했습니다. 이 접근법은 균형의 정확성을 희생하지 않으면서 효과적인 탐색을 달성했습니다.

중요성 및 주장

이 논문은 DAGS 가 긴 제어 시퀀스 탐색 비용과 전략적 상호작용 학습 비용을 분리함으로써 대규모 불완전 정보 게임을 해결하는 실용적인 경로를 제공한다고 주장합니다. 정책 초기화가 아닌 상태 커버리지를 위해 오프라인 데이터를 활용함으로써 DAGS 는 행동 복제보다 적은 데이터를 필요로 하며, 시연이 불완전하거나 비최적일 때에도 실행 가능합니다.

저자들은 특정 알고리즘 (정규화된 PPO) 사용 측면에서 기여의 범위가 제한적이지만, 다중 에이전트 설정에서의 상태 재시작에 관한 방법론적 통찰이 중요하다고 강조합니다. 그들은 단일 에이전트 RL 에서 시작 분포를 수정하는 것은 알려진 기법이지만, 이를 불완전 정보 게임에 적용하면 반드시 해결해야 할 고유한 균형 편향 위험이 도입된다고 지적합니다. 제안된 멀티태스크 학습을 통한 완화는 이러한 특정 과제에 대한 강력한 해결책을 제공합니다.

이 연구는 현재 벤치마크가 분석적 다루기 쉬움을 유지하기 위해 단순한 메커니즘을 사용하지만, DAGS 의 원칙은 시연이 희소하고 행동 복제가 데이터 비효율적인 복잡한 도메인 (예: 격투 게임, FPS) 으로 확장될 것으로 예상된다고 결론지었습니다. 저자들은 DAGS 를 정확한 악용 가능성이 다루기 어려운 게임에 이러한 기법을 적용하는 미래 작업의 유망한 방향으로 위치시킵니다.