기술 요약: EMAgnet

문제 정의

두 명의 플레이어가 참여하는 제로섬 불완전 정보 게임(IIG)을 해결하기 위한 최근의 진보는, 정규화된 정책 경사(policy gradient) 방법론인 PPO(Proximal Policy Optimization)가 셀프 플레이(self-play)에서 사용될 때 특화된 게임 이론 알고리즘과 대등하거나 이를 능가할 수 있음을 보여주었습니다. 이 프레임워크에서 핵심적인 설계 결정은 정규화 대상(regularization target)의 선택입니다. 균등 분포(uniform distribution)는 엔트로피 보너스를 통해 구현되는 표준적인 대상으로 부상해 왔습니다. 그러나 균등 대상은 전략적으로 무관합니다. 즉, 전략의 실행 가능성과 관계없이 모든 행동에 대해 동일하게 정규화를 수행합니다.

많은 엄격하게 지배되는 전략(suboptimal options)을 포함하는 거대한 전략 공간을 가진 게임에서, 균등 대상은 무관한 전략에 정규화 예산을 낭비합니다. 이러한 한계는 게임의 복잡성이 증가하고 전략적으로 유효한 전략의 비율이 줄어듦에 따라 점점 더 중대한 문제가 됩니다. 또한, 어닐링된(annealed) 균등 정규화를 사용하는 기존 방식은 딜레마에 직면합니다. 초기 단계의 강한 정규화는 정책이 지배되는 전략을 탐색하도록 강제하는 반면, 후기 단계의 약한 정규화는 전략적 혼합(strategic mixing)을 장려하는 데 충분한 압력을 제공하지 못해, 내쉬 균형(Nash equilibrium)보다는 순수 전략(pure strategies)으로 수렴하게 만드는 경우가 빈번합니다.

방법론

저자들은 "무빙 마그넷(moving magnet)" 정규화 대상의 개념을 탭룰(tabular) 설정에서 딥 강화 학습으로 확장한 방법론인 EMAgnet을 소개합니다. 고정된 균등 분포로 정규화하는 대신, EMAgnet은 정책의 자체 네트워크 파라미터의 **지수 이동 평균(Exponential Moving Average, EMA)**을 향해 정규화합니다.

핵심 메커니ism

이 방법은 대칭적 셀프 플레이에서의 PPO를 기반으로 합니다. 표준 PPO 목적 함수는 현재 정책 파라미터($\theta$)를 "마그넷" 정책($\theta_{mag}$) 쪽으로 끌어당기는 KL 발산(Kullback-Leibler divergence) 항을 통해 확장됩니다:

$$L_{PPO-EMAg}(\theta) = L_{PPO}(\theta) + \lambda_{KL} \mathbb{E}_{z \sim \mathcal{T}} \left[ D_{KL}(\pi_{\theta_{mag}}(\cdot | z) \parallel \pi_{\theta}(\cdot | z)) \right]$$

마그넷 파라미터는 각 PPO 단계 이후 파라미터 공간에서의 산술 평균을 사용하여 다음과 같이 업데이트됩니다:
$$\theta_{mag} \leftarrow (1 - \tau) \theta_{mag} + \tau \theta$$
여기서 $\tau \in (0, 1]$는 스텝 사이즈입니다. 마gnet은 정책과 동일한 랜덤 가중치로 초기화됩니다.

적응적 특성

핵심 혁신은 대상의 적응적 성질에 있습니다:

1. 나쁜 전략 망각하기: 정책이 엄격하게 지배되는 전략을 피하도록 학습함에 따라, EMA 마그넷은 해당 행동을 더 이상 지원하지 않는 정책의 가중치를 반영하여 점진적으로 그들을 향한 정규화를 중단합니다.
2. 좋은 전략 기억하기: EMA는 셀프 플레이 사이클링 동안 마주친 전략들의 매끄러운 혼합물을 자연스럽게 축적합니다. 이는 정책이 전략적으로 유효한 옵션들에 대한 커버리지를 유지하도록 장려합니다.
3. 일정한 강도: 어닐링된 균등 정규화와 달리, KL 정규화 강도($\lambda_{KL}$)는 일정하게 유지되지만 대상은 진화합니다. 이는 강한 정규화가 나쁜 전략을 탐색하게 만들거나, 약한 정규화가 순수 전략으로의 붕괴를 막지 못하는 "딜레마"를 피하게 해줍니다.

주요 기여

1. 알고리즘 확장: 본 논문은 탭룰 무빙 마그넷 개념(Sokota 등이 탐구한 바 있음)을 정책 가중치의 파라미터 공간 EMA를 정규화 대상으로 구현함으로써 딥 강화 학습으로 확장했습니다.
2. 적응적 정규화: 이 방법은 에이전트의 개선되는 전략에 따라 진화하는 적응적 정규화 대상을 제공하며, 이는 균등 분포와 같은 고정된 대상과 구별됩니다.
3. 실험적 평가: 저자들은 세 가지 카테 Category의 게임에 대해 균등 마그넷 정규화(선형 및 파워 로 법칙 어닐링 스케줄 모두 사용)를 적용한 PPO와 PPO-EMAg를 비교 평가했습니다:
   • 표준 벤치마크 (Biased RPS, Goofspiel-4, Kuhn Poker).
   • 단일 엄격 지배 전략인 "포기(forfeit)" 행동이 추가된 수정된 벤치마크 (FF 변형).
   • 그리드월드 네비게이션 과제를 통해 전략 공간의 대다수가 지배되는 환경의 수정된 벤치마크 (Control 변형).

결과

평가는 PPO-EMAg가 엄격하게 지배되는 전략을 포함하는 환경에서 균등 베이스라인보다 낮은 탐색 가능성(exploitability)을 달성하는 동시에, 표준 벤치마크에서는 경쟁력 있는 성능을 유지함을 입증합니다.

• 표준 게임: Biased RPS, Goofspiel-4, Kuhn Poker에서 PPO-EMAg는 베이스라인들과 경쟁할 만한 수준이며, EMA 마그넷 정책은 종종 가장 낮은 탐색 가능성을 달성합니다.
• Forfeit (FF) 게임: 엄격하게 지배되는 포기 행동이 추가된 게임에서 PPO-EMAg는 균등 베이스라인을 크게 앞섭 over 합니다. 균등 마그넷은 훈련 내내 포기 행동을 향해 정규화를 지속하는 반면, EMA 마그넷은 정책이 이를 피하도록 학습함에 따라 이를 향한 정규화를 줄이도록 적응합니다.
• Control 게임: 대부분의 전략이 (네비게이션 실패로 인해) 엄격하게 지배되는 환경에서, PPO-EMAg는 우수한 성능과 현저히 빠른 수렴 속도를 보여줍니다.
  • Control Biased RPS에서 균등 선형 어닐링은 훈련 후반부에 떨어지기 전까지 약 7백만 스텝 동안 학습에 실패하는 반면, PPO-EMAg는 2백만 스텝 이내에 수렴합니다.
  • Control Goofspiel에서 균등 선형 어닐링은 6백만 스텝 동안 거의 개선되지 않지만, PPO-EMAg는 훨씬 일찍 낮은 탐색 가능성에 도달합니다.
• 궤적 분석: 전략 심플렉스(strategy simplex)에서의 정책 궤적 시각화는 균등 어닐링이 초기에 지배되는 전략에 갇히거나 후기에 순수 전략으로 붕로되는 원인을 보여줍니다. PPO-EMAg는 지배되는 행동에 대한 질량을 점진적으로 줄이면서도 혼합 압력을 유지함으로써 이를 방지하고, 정책이 내쉬 균형 근처에서 사이클링할 수 있도록 합니다.

의의 및 주장

본 논문은 EMAgnet이 거대 게임에서 에이전트의 진화하는 전략에 맞춰 정규화 대상을 조정하는 단순하면서도 효과적인 메커니즘을 제공한다고 주장합니다. 정책의 자체 가중치에 대한 파라미터 공간 EMA로 정규화함으로써, 이 방법은 엄격하게 지배되는 전략이 많은 게임에서의 균등 정규화의 함정을 피합니다.

저자들은 게임이 복잡해짐에 따라 전략 공간 중 전략적으로 유효한 부분의 비율이 줄어드는 경향이 있다고 상정합니다. 이러한 시나리오에서, 최적이 아닌 옵션에 정규화 예산을 할당하는 것은 증가하는 비용을 초래합니다. EMAgnet은 나쁜 전략은 "망각"하고 좋은 전략은 "기억"함으로써 이를 해결하며, 표준 PPO 루프 외에 단 한 번의 EMA 업데이트만을 필요로 합니다. 본 논문은 PPO-EMAg가 표준 벤치마크에서 경쟁력이 있을 뿐만 아니라, 특히 지배되는 전략의 밀도가 높은 게임에서 어닐링된 균등 정규화에 비해 더 빠른 수렴과 더 낮은 최종 탐색 가능성을 가능하게 한다는 점에서 주요한 이점이 있다고 결론짓습니다.