기술 요약: 두 플레이어 게임에서 안정적이고 효율적인 강화 학습을 위한 정규화 정책 최적화 재검토

문제 제기

두 플레이어 제로섬 게임, 특히 보드 게임은 강화 학습 (RL) 의 전통적인 벤치마크 역할을 해왔습니다. AlphaZero(Silver 등, 2018) 와 같은 탐색 기반 방법은 심층 신경망과 미리보기 탐색 (예: 몬테카를로 트리 탐색, MCTS) 을 결합하여 초인적 성능을 달성했지만, 상당한 계산 비용을 수반합니다. 예를 들어, AlphaZero 훈련에는 10 GPU 년 이상이 소요된다고 보고되었습니다 (Silver 등, 2018; Tian 등, 2019). 이러한 자원 집약성은 재현성을 저해하고 자원이 제한된 환경에서의 실용적 적용을 어렵게 만듭니다 (Zhao 등, 2022).

최근 연구들은 트리 깊이 또는 롤아웃 횟수를 제한함으로써 탐색 기반 방법의 계산 부담을 줄이려 시도했습니다 (Hessel 등, 2021; Danihelka 등, 2022). 그러나 이러한 방법들은 여전히 근본적으로 미리보기 탐색에 의존합니다. 반면, 로봇 공학과 연속 제어에서 효율적인 모델 없는 (model-free) RL 방법들은 다중 에이전트 자기 플레이 환경에서의 불안정성으로 인해 보드 게임에서는 충분히 탐구되지 않았습니다. 본 연구가 다루는 핵심 질문은 다음과 같습니다: 순수한 모델 없는 RL 알고리즘이 탐색 기반 방법들에 비해 훨씬 적은 훈련 자원으로 두 플레이어 게임에서 안정적이고 경쟁력 있는 학습을 달성할 수 있을까요?

방법론

저자들은 훈련 중 MCTS 가 필요 없는 모델 없는 RL 알고리즘인 KLENT(KL 및 엔트로피 정규화 정책 최적화) 를 제안합니다. 이 접근법은 역 Kullback-Leibler(KL) 정규화와 엔트로피 정규화라는 두 가지 특정 구성 요소를 통해 정규화 정책 최적화를 재검토하는 데 기반을 둡니다.

1. 정책 업데이트 규칙

KLENT 의 핵심은 다음과 같이 정의된 정규화 정책 최적화 문제입니다:
$$\max_{\pi'} \mathbb{E}_{A \sim \pi'(\cdot|s)}[Q^\pi(s, A)] - \beta D_{KL}(\pi'(\cdot|s) \parallel \pi(\cdot|s)) + \alpha H(\pi'(\cdot|s))$$
여기서:

• $\pi'$는 새로운 정책이고, $\pi$는 사전 정책입니다.
• $D_{KL}(\pi' \parallel \pi)$는 역 KL 발산으로, 자기 플레이에서의 비정상성을 처리하기 위해 점진적인 정책 업데이트를 장려합니다.
• $H(\pi')$는 엔트로피로, 에이전트의 자체 정책에 과적합되는 것을 방지하기 위해 지속적인 탐색을 장려합니다.
• $\alpha$와 $\beta$는 음이 아닌 하이퍼파라미터입니다.

보드 게임의 유한한 행동 공간을 고려할 때, 최적 정책 $\pi'$는 폐쇄형 해석적 해를 가집니다:
$$\pi'(a|s) = \frac{1}{Z(s)} \exp\left( \frac{Q^\pi(s, a) + \beta \log \pi(a|s)}{\alpha + \beta} \right)$$
KLENT 에서 신경망 $\pi_\theta$는 이 해석적으로 유도된 목표 $\pi'$와 출력 간의 교차 엔트로피를 최소화하도록 훈련됩니다.

2. 가치 함수 학습

MCTS 백업으로 행동 가치를 추정하는 탐색 기반 방법과 달리, KLENT 는 신경망을 사용하여 행동 가치 함수 $Q^\pi(s, a)$를 직접 매개변수화합니다. 학습을 안정화하고 편차 - 분산 트레이드오프를 관리하기 위해, 이 알고리즘은 표준 몬테카를로 반환 ($\lambda=1$) 대신 $\lambda$-returns($G^\lambda$) 을 가치 함수의 학습 목표로 사용합니다. 예비 실험에 따르면, 중간 값인 $\lambda \in (0, 1)$이 $\lambda=1$보다 편차와 분산의 제곱 합을 더 잘 최소화하는 것으로 나타났습니다.

3. 알고리즘 구조

KLENT 는 자기 플레이 단계(온-정책 데이터 수집) 와 피팅 단계(네트워크 매개변수 업데이트) 를 번갈아 수행합니다. 손실 함수는 정책과 행동 가치 네트워크를 동시에 최적화합니다:
$$L(\theta) = \mathbb{E}_D \left[ -\sum_{a \in A} \pi'(a|S) \log \pi_\theta(a|S) + (Q_\theta(S, A) - G^\lambda)^2 \right]$$
중요하게도, KLENT 는 훈련 중 트리 탐색이 전혀 필요 없으며, 오직 신경망의 예측과 해석적 정책 업데이트에만 의존합니다.

주요 기여

이 논문은 완전히 새로운 알고리즘적 요소를 제안하기보다는, 이 특정 정규화 조합에 대한 이론적 및 경험적 특성을 규명하는 데 초점을 맞춘 세 가지 주요 기여를 합니다:

1. 알고리즘 공식화: 저자들은 역-KL 과 엔트로피 정규화의 조합을 기반으로 실용적인 모델 없는 RL 알고리즘 (KLENT) 을 유도하여 폐쇄형 정책 업데이트 규칙을 제공합니다.
2. 이론적 보장: 두 가지 설정에서 정책 업데이트 규칙에 대한 새로운 수렴 보장을 제공합니다:
   • 정규형 게임 (Normal-Form Games): 조건 $\alpha(\alpha + 2\beta) > \|R\|_2^2/4$ 하에서 고유한 고정점으로의 국소 선형 수렴을 증명합니다. 이 조건은 이전 결과들 (예: Sokota 등, 2022) 보다 더 넓은 범위의 정규화 계수를 포괄합니다.
   • 유한 길이 게임 (Finite-Length Games): 저자들은 유한한 게임 기간을 가정할 때, KLENT 정책이 역방향 유도 (backward induction) 를 통해 엔트로피 정규화 최적 정책 (Quantal Response Equilibrium) 으로 수렴함을 증명합니다.
3. 경험적 검증: 다섯 가지 보드 게임 (Animal Shogi, Gardner Chess, 9x9 Go, Hex, Othello) 에 대한 포괄적인 실험을 통해 KLENT 가 기존 탐색 기반 및 모델 없는 베이스라인보다 훨씬 높은 훈련 효율성을 달성함을 보여줍니다.

결과

훈련 효율성

실험 결과, KLENT 는 모든 테스트 환경에서 기존 방법들보다 더 효율적으로 학습하는 것으로 나타났습니다.

• 성능 향상: 평균적으로 KLENT 는 연구 내 가장 강력한 탐색 기반 베이스라인인 Gumbel AlphaZero 대비 최대 4 배 높은 훈련 효율성을 달성했습니다. 예를 들어, Gumbel AlphaZero 는 50% 승률에 도달하는 데 3 억 개의 시뮬레이션 평가가 필요했던 반면, KLENT 는 7,500 만 개만 필요했습니다.
• 확장성: 분기 계수가 높은 게임 (예: 9x9 Go, Hex) 에서 효율성 격차는 더욱 벌어지는데, 이는 탐색 기반 방법들이 상당한 시뮬레이션 예산을 필요로 하기 때문입니다. KLENT 의 우위는 미리보기 탐색을 피하고 안정적인 $\lambda$-returns 을 사용하기 때문입니다.
• 대규모 성능: 19x19 Go 에서 KLENT 는 증가된 복잡성에도 불구하고 AlphaZero 와 비교해 경쟁력 있는 학습 효율성을 유지했습니다.

애블레이션 연구

이 연구는 세 가지 핵심 기법의 필요성을 검증합니다:

• 역-KL 정규화: 이를 제거하면 ($\beta=0$ 설정) 급격한 정책 업데이트와 성능 저하, 특히 9x9 Go 에서 발생합니다.
• 엔트로피 정규화: 이를 제거하면 ($\alpha=0$ 설정) 정책이 과도하게 결정론적이 되어 (엔트로피가 거의 0 으로 떨어짐) 불안정한 학습과 성능 붕괴를 초래합니다.
• $\lambda$-Returns: $\lambda$-returns 을 1 단계 백업이나 몬테카를로 반환으로 대체하면 성능이 저하되어 편차와 분산의 균형 중요성이 확인되었습니다.

테스트 시간 성능

테스트 시간 MCTS(800 회 롤아웃) 를 장착했을 때, KLENT 에이전트는 베이스라인에 대해 높은 승률을 기록했으며, 9x9 Go 와 19x19 Go 에서의 직접 대결에서 AlphaZero 와 Gumbel AlphaZero 를 능가했습니다.

중요성 및 주장

저자들은 이 작업을 기존 정규화 기술을 적절히 재검토함으로써 오랫동안 탐색 기반 방법이 지배해 온 분야에서 안정적이고 효율적인 학습을 달성할 수 있음을 보여주는 사례로 위치시킵니다.

• 겸손한 주장: 논문은 주요 기여가 새로운 알고리즘적 요소가 아니라 두 플레이어 게임에서 정규화 정책 최적화에 대한 새로운 이론적 및 경험적 특성 규명임을 명시적으로 밝힙니다.
• 한계: 저자들은 KLENT 가 높은 효율성을 달성하지만, 무제한의 계산 자원이 사용 가능한 경우 반드시 우수한 점근적 성능을 보장하지는 않는다고 인정합니다. 수천 개의 GPU 와 같은 막대한 자원에 접근 가능한 경우 AlphaZero 와 같은 탐색 기반 접근법의 효과성을 배제하지 않습니다.
• 광범위한 영향: 저자들은 기본 가정 (유한 행동 MDP) 이 현재 탐색 기반 방법이 우세한 이산 최적화, 알고리즘적 발견, 수학 증명과 같은 실제 문제에 적용될 수 있음을 시사합니다. 이 작업이 이러한 효율적인 모델 없는 접근법을 다른 분야로 확장하는 것을 장려하기를 바랍니다.

요약하자면, KLENT 는 역-KL 과 엔트로피 정규화의 안정성을 활용하여 훈련 자원의 일부만으로 경쟁력 있는 성능을 달성함으로써, 보드 게임을 위한 탐색 기반 RL 에 대한 계산 효율적인 대안을 제공합니다.