[Google DeepMind] — AlphaEvolve: LLM을 활용한 다중 에이전트 학습 알고리즘의 자동 발견 및 최적화

Background and Overview

다중 에이전트 강화학습(Multi-Agent Reinforcement Learning, MARL) 분야, 특히 불완전 정보 게임(Imperfect-information games)에서의 알고리즘 발전은 오랫동안 연구자의 직관과 수동적인 시행착오에 의존해 왔습니다. Counterfactual Regret Minimization(CFR)이나 Policy Space Response Oracles(PSRO)와 같은 핵심 프레임워크들은 탄탄한 이론적 토대를 갖추고 있지만, 이를 최적화하기 위한 구체적인 업데이트 규칙이나 가중치 설계는 인간이 탐색하기에 너무나 방대한 조합의 영역이었습니다.

Google DeepMind 연구진이 발표한 이번 연구는 이러한 한계를 극복하기 위해 대규모 언어 모델(LLM) 기반의 진화형 코딩 에이전트인 AlphaEvolve를 제안합니다. AlphaEvolve는 알고리즘의 소스 코드를 마치 ‘게놈(Genome)’처럼 취급하며, LLM을 지능적인 유전 연산자로 활용해 코드의 논리적 구조를 변경하고 새로운 상징적 연산을 주입합니다. 이를 통해 단순히 하이퍼파라미터를 튜닝하는 수준을 넘어, 인간의 직관을 벗어난 완전히 새로운 형태의 평형 탐색 알고리즘을 자동으로 발견하는 데 성공했습니다.

Model-Specific Test Results: VAD-CFR & SHOR-PSRO

연구진은 AlphaEvolve를 통해 두 가지 핵심 패러다임에서 혁신적인 알고리즘 변종을 발견했습니다.

1. VAD-CFR (Volatility-Adaptive Discounted CFR) 이 알고리즘은 후회(Regret) 누적과 정책 유도 논리를 혁신하여 Volatility-sensitive discounting, Consistency-enforced optimism, 그리고 Hard warm-start라는 세 가지 비직관적인 메커니즘을 도입했습니다.

• 성능: 3인 Kuhn Poker, Leduc Poker, 4카드 Goofspiel 등에서 기존 최첨단(SOTA) 모델인 Discounted Predictive CFR+ (DPCFR+) 및 HS-PCFR+를 능가하는 수렴 속도를 보였습니다.
• 특이점: 특히 3인 Kuhn Poker에서 모든 베이스라인보다 현저히 낮은 착취 가능성(Exploitability)을 달성했으며, 학습 초기 단계의 노이즈를 필터링하는 것이 후반부의 수렴 최적화만큼이나 중요하다는 것을 입증했습니다.

2. SHOR-PSRO (Smoothed Hybrid Optimistic Regret PSRO) 인구 기반 학습(PBT) 알고리즘인 PSRO의 성능을 극대화하기 위해 훈련 및 평가 시점의 메타 전략 솔버를 진화시킨 모델입니다.

• 성능: Optimistic Regret Matching(ORM)과 온도 조절형 소프트맥스 분포를 결합한 하이브리드 업데이트 규칙을 사용합니다. 훈련 초기에는 인구의 다양성을 장려하고 후기에는 정밀한 평형 탐색으로 전환하는 어닐링(Annealing) 스케줄을 자동화했습니다.
• 결과: 기존의 고정된 메타 솔버(Uniform, Nash 등) 대비 더 빠른 수렴 속도와 안정성을 보였으며, 특히 6면 주사위 Liar’s Dice와 같이 상태 공간이 큰 게임에서 탁월한 효율성을 나타냈습니다.

Test Datasets 및 환경

알고리즘의 견고성과 일반화 능력을 테스트하기 위해 연구진은 두 가지 게임 세트를 활용했습니다. 모든 실험은 Google DeepMind의 OpenSpiel 프레임워크를 기반으로 수행되었습니다.

• Training Set (알고리즘 진화 및 튜닝): 3인 Kuhn Poker, 2인 Leduc Poker, 4카드 Goofspiel, 5면 Liar’s Dice.
• Test Set (일반화 성능 검증): 4인 Kuhn Poker, 3인 Leduc Poker, 5카드 Goofspiel, 6면 Liar’s Dice.
• 평가 지표: 착취 가능성(Exploitability)을 로그 스케일로 측정하여 정확한 평형 도달 수치를 계산했습니다. VAD-CFR의 경우 총 11개 게임 중 10개 게임에서 기존 SOTA와 동등하거나 그 이상의 성능을 기록했습니다.

Research Methodology and Conclusion

AlphaEvolve는 LLM의 창의적 코드 생성 능력과 진화 알고리즘의 엄격한 선택 압력을 결합한 프레임워크입니다. 연구 방법론은 다음과 같은 루프를 반복합니다.

1. 인구 초기화: 표준 CFR 또는 PSRO 코드로 시작합니다.
2. LLM 기반 변이: Gemini 모델(Gemini 2.5 Pro 등)이 소스 코드를 분석하여 성능(착취 가능성 감소)을 높일 수 있는 의미론적 수정을 제안합니다.
3. 자동 평가: 생성된 알고리즘 후보군을 프록시 게임에서 실행하여 적합도 점수를 산출합니다.
4. 진화적 선택: 우수한 성적을 거둔 코드를 다시 부모 알고리즘으로 선택하여 다음 세대로 이어갑니다.

연구진은 이 과정을 통해 발견된 VAD-CFR이 단순히 수학적 수식을 다듬은 것이 아니라, 학습 과정의 변동성(Volatility)을 실시간으로 추적하여 ‘과거의 불안정한 기록을 얼마나 빨리 잊을지’를 결정하는 지능적인 메커니즘을 갖추게 되었다고 결론지었습니다. 이는 인간 설계자가 직관적으로 떠올리기 어려운 복합적인 제어 흐름입니다.

Implications

이번 연구는 AI 알고리즘 설계의 패러다임이 ‘인간의 가이드’에서 ‘자동화된 상징적 진화’로 이동하고 있음을 시사합니다.

• 해석 가능한 알고리즘 발견: 신경망 기반의 블랙박스 메타 학습과 달리, AlphaEvolve가 생성한 코드는 사람이 직접 읽고 분석할 수 있는 상징적(Symbolic) 형태입니다. 이는 발견된 메커니즘을 다른 도메인에 이식하거나 이론적으로 분석하는 데 매우 유리합니다.
• 비대칭적 최적화: 학습용 솔버와 평가용 솔버를 분리하거나, 양수/음수 후회값에 서로 다른 가중치를 부여하는 등 ‘알고리즘적 비대칭성’이 실전에서 얼마나 강력한지 확인되었습니다.
• 확장성: 연구진은 향후 이 프레임워크를 딥 강화학습 에이전트 전체로 확장하거나, 일반적인 협력 게임 메커니즘 발견에 적용할 계획입니다. 이는 향후 복잡한 엔터프라이즈 환경에서의 의사결정 에이전트 설계나 자원 배분 최적화 알고리즘 개발에도 큰 영향을 미칠 것으로 보입니다.

References:

1. **https://arxiv.org/abs/2602.16928v2**

Tags: #GoogleDeepMind #AlphaEvolve #GameTheory #MARL #LargeLanguageModels #AlgorithmDiscovery #구글딥마인드 #다중에이전트 #강화학습 #게임이론 #알고리즘최적화 #AI연구