NashPG: A Policy Gradient Method with Iteratively Refined Regularization for Finding Nash Equilibria

다음은 논문 "NASHPG: A Policy Gradient Method with Iteratively Refined Regularization for Finding Nash Equilibria"에 대한 상세한 기술 요약입니다.

1. 문제 제기

이 논문은 **다중 에이전트 강화 학습 (MARL)**을 사용하여 **2 인 제로섬 불완전 정보 게임 (2p0s IIGs)**에서 **내시 균형 (Nash Equilibria, NE)**을 찾는 과제를 다룹니다.

• 핵심 난제: 딥 강화 학습 (DRL) 이 완전 정보 게임에서 성공을 거두었음에도 불구하고, 포커와 같은 2p0s IIG 는 부분 관측성과 숨겨진 정보를 포함합니다.
• 기존 방법의 한계:
  • 집합 기반 방법 (예: PSRO, NFSP): 종종 비용이 많이 드는 최적 대응 (best-response) 계산을 요구하며, 마지막 반복이 아닌 평균 정책으로의 수렴만 보장합니다. DRL 환경에서 최종 정책을 추출하는 것은 간단하지 않습니다.
  • 반사적 후회 최소화 (CFR): 전체 게임 트리 열거 (모델 기반) 를 필요로 하므로 대규모 도메인에서는 처리가 불가능합니다.
  • 정규화 기반 방법 (예: R-NaD): 최근 접근법은 정규화된 균형으로의 마지막 반복 수렴을 보장하기 위해 정규화를 사용합니다. 그러나 이러한 방법들은 반드시 진정한 내시 균형이 아니며 (이용 가능한 상태가 남음), 또한 기존 실용적 구현 (예: R-NaD) 은 **Neural Replicator Dynamics (NeuRD)**에 의존하는데, 이는 벤치마크에서 표준 정책 경사 방법보다 열악한 성능을 보여왔습니다.
• 격차: 대규모 IIG 에서 정확한 내시 균형으로 증명 가능하게 수렴하는 확장 가능하고, 모델 프리이며, 정책 경사 기반의 알고리즘이 부재합니다.

2. 방법론

저자들은 이론적 프레임워크 (IMMD) 와 실용적 알고리즘 (NASHPG) 의 2 단계 접근법을 제안합니다.

A. 이론적 프레임워크: 반복적 MMD (IMMD)

저자들은 정규화된 변분 부등식 (VI) 을 해결하는 방법인 **자기 거울 하강 (Magnetic Mirror Descent, MMD)**을 확장합니다.

• 정규화된 VI: 내시 균형을 위한 표준 VI 문제는 단조적이지만 강단조적이지 않아 직접 해결하기 어렵습니다. MMD 는 브레그만 발산 (Bregman divergence) 을 기반으로 하는 강볼록 정규화 항을 추가하여 강단조 연산자를 생성함으로써 유일한 해를 보장합니다.
• 반복적 정제: 하나의 정규화된 문제를 푸는 대신, IMMD 는 연속된 문제들을 풉니다.
  1. 초기 전략 프로파일 $\rho$로 시작합니다.
  2. 정규화된 VI 문제 $VI(Z, G_\rho)$를 풀어 새로운 전략 $z = M(\rho)$를 찾습니다.
  3. 이 새로운 전략 $z$를 다음 라운드의 참조 $\rho$로 사용합니다.
• 이론적 보장: 이 논문은 이 반복 과정이 모든 내시 균형에 대한 브레그만 발산을 엄격하게 단조 감소시킨다는 것을 증명합니다. 결과적으로 전략의 시퀀스는 진정한 내시 균형으로 수렴합니다.

B. 실용적 알고리즘: 내시 정책 경사 (NASHPG)

IMMD 를 전체 열거가 불가능한 대규모 게임에 적용 가능하게 하기 위해, 저자들은 NASHPG를 유도합니다.

• 혼합 전략에서 행동 전략으로: IMMD 에서 사용된 혼합 전략 브레그만 발산을 행동 정책 (RL 의 확률적 정책) 간의 쿨백 - 라이블러 (KL) 발산으로 근사화합니다.
• 목적 함수: 알고리즘은 정규화된 정책 목적 함수를 최적화합니다:
  $$\text{Objective} = \mathbb{E}[R] - \alpha \cdot \mathbb{E}_{o} [ D_{KL}(\pi(\cdot|o) \parallel \rho(\cdot|o)) ]$$
  여기서 $\pi$는 현재 정책, $\rho$는 이전 외부 루프에서 온 참조 정책, $\alpha$는 정규화 강도입니다.
• 알고리즘 구조:
  1. 내부 루프: 현재 참조 $\rho$에 대해 정규화된 목적 함수를 최적화하기 위해 $K$단계의 표준 정책 경사 업데이트 (예: PPO 사용) 를 수행합니다.
  2. 외부 루프: $K$단계 후, 참조 정책 $\rho$를 현재 정책 $\pi$로 업데이트하고 반복합니다.
• 모듈성: NASHPG 는 특정 정책 경사 추정기에 무관합니다. **PPO(Proximal Policy Optimization)**와 같은 고급 단일 에이전트 RL 알고리즘과 원활하게 통합될 수 있습니다.

3. 주요 기여

1. 이론적 수렴: 2p0s 확장형 게임에서 브레그만 발산의 엄격한 단조 감소와 정확한 내시 균형으로의 수렴을 보장하는 다중 라운드 정규화 프레임워크인 IMMD를 도입했습니다.
2. 실용적 알고리즘 (NASHPG): 표준 정책 경사 방법 (예: PPO) 과 KL 정규화를 사용하여 IMMD 프레임워크를 구현하는 확장 가능하고 모델 프리인 알고리즘을 개발했습니다.
3. 가설 검증: 이전 정규화 방법 (예: R-NaD) 의 낮은 성능이 정규화 프레임워크 자체 때문이 아니라 내부 솔버로 NeuRD를 사용했기 때문이라는 실증적 증거를 제공했습니다. 유사한 프레임워크에서 NeuRD 를 PPO 로 교체하면 성능이 크게 향상되었습니다.
4. 확장성: 정확한 열거가 불가능한 대규모 도메인 (예: 배틀십, 헤즈업 노리미트 텍사스 홀덤) 을 해결할 수 있는 능력을 입증했습니다.

4. 실험 결과

저자들은 쿠인 포커 (Kuhn Poker) 와 같은 작은 게임부터 헤즈업 노리미트 텍사스 홀덤과 같은 거대한 게임까지 7 가지 게임에서 NASHPG 를 평가했습니다.

• 수렴 및 안정성: 일부 베이스라인과 달리 NASHPG 는 높은 정규화 강도에서도 발산 없이 안정적인 수렴을 보였습니다.
• 베이스라인 대비 성능:
  • 작은 게임: 쿠인 포커, 레듀크 포커, 다크 헥스, 팬텀 틱택토에서 NFSP, PSRO, MMD, R-NaD 와 비교하여 동등하거나 더 낮은 이용 가능성 (exploitability) 을 달성했습니다.
  • 대형 게임: 배틀십과 헤즈업 노리미트 텍사스 홀덤 (정확한 이용 가능성 계산이 불가능한 경우) 에서 NFSP, PSRO, R-NaD, MMD 등 모든 베이스라인과의 일대일 매치에서 더 높은 평균 보상을 달성했습니다.
• 절대적 연구 (R-NaD vs. PPO): R-NaD 프레임워크에서 NeuRD 를 PPO 로 교체한 통제 실험 (RNaD-PPO 생성) 을 수행했습니다.
  • 작은 게임에서는 업데이트 규칙의 영향이 적었습니다.
  • 대형 게임에서는 RNaD-PPO가 표준 R-NaD 를 압도적으로 능가하여 NASHPG 와의 격차를 줄였습니다. 이는 **내부 최적화 규칙 (PPO 대 NeuRD)**이 샘플 기반 다중 라운드 정규화의 주요 병목 현상임을 확인시켜 주었습니다.
• 효율성: 구현은 표준 독립 PPO 대비 약 20 줄의 코드 수정만 요구되어 접근성을 강조했습니다.

5. 의의

• 이론과 실전의 연결: 이 논문은 종종 작고 열거된 게임으로 제한되는 이론적 수렴 보장과 실용적이고 확장 가능한 MARL 알고리즘 사이의 간극을 성공적으로 메웠습니다.
• MARL 을 위한 새로운 패러다임: 반복적으로 정규화 참조를 정제하는 것과 표준 정책 경사를 결합하는 것이 집합 기반 방법이나 이전 정규화 기술보다 내시 균형을 찾는 데 더 우월한 접근법임을 확립했습니다.
• 접근성: 표준 PPO 와 간단한 KL 정규화에 의존함으로써 NASHPG 는 실무자의 진입 장벽을 낮추어, 복잡한 커스텀 솔버나 전체 게임 트리 열거 없이도 고급 게임 이론적 수렴 보장을 적용할 수 있게 합니다.
• 최첨단 성능: 불완전 정보 게임에서 모델 프리 방법의 새로운 벤치마크를 설정하여 작고 큰 도메인 모두에서 기존 베이스라인을 능가했습니다.