Towards Learning Representations of Policies in Two-Player Zero-Sum Imperfect-Information Games

기술 요약: 2인 제로섬 불완전 정보 게임에서의 정책 표현 학습을 향하여

문제 정의
2인 제로섬 불완전 정보 게임(IIG)에서 에이전트는 자신과 상대방의 정책에 대해 추론함으로써 이득을 얻는 경우가 많다. 테이블 형태의 표현(예: 카운터팩추얼 레그렛 미니마이제이션, CFR)을 사용하는 깊이 제한 탐색(depth-limited lookahead search)은 작은 규모의 게임에서는 가능하지만, 가능한 모든 정책을 열거하는 것이 불가능한 거대한 공적 믿음 상태(public belief states)를 가진 게임에서는 실행 불가능해진다. 결과적으로, 에이전트가 전체 정책 테이블에 접근하지 않고도 전략적 의도를 추론할 수 있게 해주는 압축적이고 유용한 표현(임베딩)이 필요하다. 그러나 IIG에서 이러한 정책 임베딩을 학습하는 것에 관한 기존 연구는 체계적인 정책 데이터셋 생성 방법과 표준화된 다운스트림 평가 작업 모두가 부족하여 매우 드문 실정이다.

방법론
저자들은 데이터셋 생성, 임베딩 학습, 다운스트림 평가의 세 가지 핵심 구성 요소로 이루어진 체계적인 프레임워크를 제안한다.

1. 데이터셋 생성: 저자들은 주어진 게임에 대해 다양한 정책 데이터셋을 만드는 세 가지 방법을 소개한다.

   • 무작위 초기화 (Random Initialization): 표준 PyTorch 초기화의 균질성을 피하기 위해, 행동적 다양성을 보장하는 커스텀 스킴을 사용하여 정책 신경망을 무작위로 초기화한다.
   • 정책 공간 응답 오라클 (PSRO): 기존 정책들의 혼합(mixture)에 대한 최적 대응(best-response)을 반복적으로 학습시켜 확장되는 다양한 전략 풀을 생성한다.
   • 신경 인구 학습 (NeuPL): 모든 에이전트가 공유하는 단일 조건부 신경망을 학습시킨다. 새로운 정책은 해당 네트워크의 잠재 임베딩 공간에서 샘플링함으로써 생성된다.

2. 임베딩 학습: 정책을 벡터 표현으로 매핑하기 위한 여러 방법을 제안한다.

   • 가중치 오토인코더 (Weight Autoencoder): 병목 레이어로부터 정책 네트워크의 평탄화된 가중치 벡터를 재구성하려고 시도하는 단순한 베이스라인이다.
   • 함수적 인코더 (Functional Encoder): 가중치 오토인코더와 유사하지만, 가중치 재구성이 아닌 행동 재구성에 집중하여 샘플링된 정보 상태에 대한 원래 네트워크와 재구성된 네트워크 간의 KL 발산(KL divergence)을 최소화한다.
   • 궤적 인코더 (Trajectory Encoder): SimCLR에서 영감을 받은 대조 학습(contrastive learning) 방식으로, (무작위 상대에 맞서 정책을 실행하여 수집된) 가변 길이의 궤적을 고정 차원 잠재 공간으로 매핑한다. 이 방법은 네트워크 내부 구조에 대한 접근을 필요로 하지 않는다.
   • NeuPL 스타일의 조건부 임베딩: 조건부 네트워크가 잠재 공간의 임의의 벡터를 하나의 정책으로 디코딩하도록 학습하며, 인구(population)와 임베딩을 공동으로 생성한다.
   • Grover 등의 베이스라인: MLP 인코더와 모방 및 트리플릿 식별 손실(imitation and triplet identification losses)로 학습된 조건부 정책 네트워크를 사용하는 하이브리드 생성-판별 모델이다.
   • 베이스라인: 테이블러 베이스라인(모든 정보 상태에서의 행동 분포를 결합)과 아이덴티티 베이스라인(원시 네트워크 가중치를 직접 사용)을 포함한다.

3. 다운스트림 평가 작업: 다섯 가지 작업을 통해 표현의 유효성을 평가한다.

   • 작업 A & B (페이오프 예측): 균등 무작위 상대에 대한 기대 페이오프(작업 A) 또는 두 특정 정책 간의 페이오프(작업 B)를 선형 예측기를 사용하여 예측한다.
   • 작업 C (익스플로이터빌리티 예측): 주어진 정책에 대한 상대방의 최적 대응(best-response) 페이오프를 예측한다.
   • 작업 D (제로샷 최적 대응): 주어진 임베딩만을 사용하여 특정 정책에 대한 최적 대응을 근사하는 조건부 정책 네트워크를 학습시킨다.
   • 작업 E (에이전트 식별): k-NN 또는 선형 프로브를 사용하여 특정 궤적을 생성한 정책이 무엇인지 분류한다.

실험 결과
실험은 Kuhn Poker(12개 정보 상태)와 Leduc Poker(936개 정보 상태)에서 수행되었으며, 더 큰 게임(Liar's Dice, Phantom Tic-Tac-Toe)에 대한 예비 결과도 포함되었다.

• 페이오프 예측 (작업 A & B): Kuhn Poker에서는 게임 규모가 작기 때문에 테이블러 베이스라인이 우세했다. 그러나 Leduc Poker에서는 학습된 인코더들(Trajectory, Grover, NeuPL)이 높은 차원성(2808 차원)으로 인해 어려움을 겪는 테이블러 베이스라인보다 뛰어난 성능을 보였다. Grover와 Trajectory 인코더는 Leduc의 작업 A에서 최대 32.3%의 MSE 감소율을 기록하며 가장 높은 개선을 보였다. 단순한 Weight 및 Functional 오토인코더는 일반적으로 평균을 예측하는 것보다 나은 성능을 보여주지 못했다.
• 익스플로이터빌리티 및 제로샷 응답 (작업 C & D): NeuPL 방식은 특히 NeuPL로 생성된 정책 인구에 대해 최적 대응 페이오프를 예측(작업 C)하고 제로샷 응답자를 학습(작업 D)시키는 데 있어 베이스라인보다 현저히 뛰어난 성능을 보였다. Identity 및 Weight 베이스라인은 성능이 저조했으며, 종종 평균 베이스라인보다도 좋지 않았다.
• 에이전트 식별 (작업 E): (선형 분류기를 사용하는) Trajectory Encoder는 Grover 베이스라인을 크게 앞질렀다. Kuhn에서는 47.9%, Leduc에서는 57.8%의 top-1 정확도를 달 기록한 반면, Grover는 각각 25.7%와 38.9%를 기록했다.
• 시각화: Kuhn Poker 임베딩의 t-SNE 시각화 결과, Trajectory Encoder는 공격적 전략과 수동적 전략을 성공적으로 분리해낸 반면, Weight Autoencoder 임베딩은 그러한 구조를 보여주지 못했다.

주요 기여

1. 데이터셋 생성: IIG에서 다양한 정책 데이터셋을 생성하기 위한 세 가지 뚜렷한 방법(Random, PSRO, NeuPL)을 도입했다.
2. 표현 학습: 단순한 가중치 재구성부터 대조적 궤적 학습 및 조건부 생성 모델에 이르기까지 다양한 임베딩 기법을 제안하고 비교했다.
3. 평가 스위트: 정책 표현을 엄격하게 평가하기 위해 포괄적인 다운스트림 작업 세트(페이오프 예측, 익스플로이터빌리티, 제로샷 응답, 에이전트 식별)를 정의했다.
4. 체계적 비교: 저자들이 알기로, 이 논문은 정책 표현을 위한 자기 지도 학습(self-supervised learning) 기법을 체계적으로 비교한 최초의 연구 중 하나이다.

의의 및 주장
본 논문은 불완전 정보 게임에서 압축적이고 유용한 행동적 표현을 학습하기 위한 기초적인 단계라고 주장한다. 방법론들이 "매우 기초적"이라고 설명되기도 하지만, 결과는 특히 대조적 궤적 학습이나 NeuPL 스타일의 조건부 학습을 사용할 때 학습된 임베딩에 유용한 행동적 의미론(behavioral semantics)이 존재함을 입증한다. 본 연구는 테이블 형태의 표현이 작은 게임에는 충분하지만, 게임의 복잡성이 증가함에 따라 학습된 임베딩이 더 우월해진다는 점을 강조한다. 저자들은 이 작업을 오픈 프레임워크(코드 제공)로 제시하며, 향후 연구에서 손실 함수(loss term)를 정교화하거나 이러한 표현을 의사 결정 시점의 플래닝(decision-time planning)과 통합할 수 있음을 언급하며 마무리한다.