🤖 AI

Discovering Multiagent Learning Algorithms with Large Language Models

본 논문은 대규모 언어 모델이 불완전 정보 게임에 대한 경쟁적 다중 에이전트 강화 학습 알고리즘의 발견을 자동화할 수 있음을 입증하고, 이러한 복잡하고 환경에 특화된 발견 결과를 최소한의 알고리즘적 핵심으로 정제하면 일반화 성능이 향상되고 구조적 복잡성이 감소함을 보여줍니다.

원저자: Zun Li, John Schultz, Daniel Hennes, Marc Lanctot

게시일 2026-05-11

📖 4 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Zun Li, John Schultz, Daniel Hennes, Marc Lanctot

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

로봇들에게 포커, 바둑, 혹은 '거짓말 주사위' 게임을 가르치려 한다고 상상해 보세요. 수십 년 동안 인간은 코치 역할을 하며 로봇의 두뇌를 수동으로 조정해 왔습니다. 다양한 수학 공식을 시도하며 그들이 더 나아지기를 바랐죠. 이는 실패와 성공을 반복하는 느리고 지루한 과정이었습니다.

이 논문은 새로운 코칭 방식을 소개합니다. 인간이 코드를 조정하는 대신, 연구자들은 코드를 이해하는 초지능 AI인 **대규모 언어 모델 (LLM)**이 진화 생물학자처럼 행동하도록 했습니다. 이 시스템을 AlphaEvolve라고 부릅니다.

다음은 그들이 발견한 내용을 단순한 개념으로 풀어낸 이야기입니다.

1. 진화 실험실

연구자들은 두 가지 다른 게임 플레이 알고리즘이 있는 디지털 '실험실'을 구축했습니다.

CFR (반사실 후회 최소화): 마치 자신이 저지른 모든 실수를 돌아보며 "내가 다른 행동을 했다면 이겼을까?"라고 묻는 학생과 같습니다.
PSRO (정책 공간 응답 오라클): 다양한 선수 팀을 구성해 서로 대결시키고, 현재 최강자를 이기기 위해 roster 에 새로운 더 똑똑한 선수들을 끊임없이 추가하는 코치와 같습니다.

LLM 에게는 이러한 알고리즘의 소스 코드가 주어졌고, 다음과 같은 지시를 받았습니다. "이것들을 더 나아지게 만들어라. 로봇들이 저지르는 실수 (취약성) 를 줄여라."

LLM 은 단순히 몇 가지 숫자를 조정하는 데 그치지 않았습니다. 알고리즘의 DNA 를 변이시키듯 코드 자체의 논리를 다시 썼습니다. '적자생존'의 여러 세대를 거친 후, LLM 은 두 가지 새로운 매우 복잡한 알고리즘을 만들어냈습니다.

VAD-CFR: 게임이 얼마나 혼란스러운지에 따라 극적으로 적응하는 '후회' 학생의 변형 버전입니다.
SHOR-PSRO: 매우 구체적이고 복잡한 방식으로 다양한 전략을 혼합하는 '팀 코치'의 변형 버전입니다.

2. '과도하게 설계된' 함정

이 새로운 AI 가 발견한 알고리즘들을 테스트했을 때, 그 성능은 놀라웠습니다. 훈련된 특정 게임에서 인간이 설계한 챔피언들을 모두 물리쳤습니다.

그러나 연구자들은 수상한 점을 발견했습니다. LLM 은 매우 까다로운 한 명의食客를 위해 특정 요리를 만드는 마스터 셰프처럼 알고리즘을 구축했습니다. 코드는 훈련 게임에서는 완벽하게 작동했지만, 게임의 일반적 규칙을 배우기보다는 훈련 데이터를 암기하는 '과적합'일 가능성이 높은 복잡하고 얽힌 메커니즘으로 가득 차 있었습니다.

이는 마치 LLM 이 특정 경주로만 맞춰진 터보차저, 니트로 시스템, 특수 서스펜션을 갖춘 자동차를 만든 것과 같습니다. 그 경주에서는 승리하겠지만, 울퉁불퉁한 흙길로 가져가면 무너질지도 모릅니다.

3. '절제' 수술 (수사 작업)

무엇이 실제로 이 알고리즘들을 똑똑하게 만들었는지 파악하기 위해 연구자들은 '수술'을 실시했습니다. 어떤 일이 일어나는지 확인하기 위해 코드의 일부를 체계적으로 제거했습니다. 이를 **절제 (ablation)**라고 합니다.

그들은 정교하고 복잡한 부분들 (변동성 추적이나 특정 방식으로 전략을 혼합하는 것 등) 이 대부분 쓸모없는 장신구임을 발견했습니다. 이러한 부분들은 훈련 경주에서 알고리즘이 이기도록 도왔지만, 새로운 게임으로 일반화하는 데는 도움이 되지 않았습니다.

그들이 '화려한 옷'을 벗겨내자, 실제로 엔진을 작동하게 만든 본질적인 뼈대가 드러났습니다.

4. 정제된 승자

가장 필수적이고 근본적인 원리만 남기고 과도하게 복잡해진 코드를 버림으로써, 그들은 두 가지 더 간단하고 새로운 알고리즘을 만들었습니다.

WOP-CFR (웜스타트된 낙관적 예측 CFR):
- 비유: 나쁜 습관을 기록하지 않기 위해 수업 첫 500 일 동안은 노트를 쓰기를 거부하는 학생을 상상해 보세요 (웜스타트). 그 후 노트를 쓰기 시작하지만, '낙관적'입니다. 다음 행위가 실제보다 약간 더 나을 것이라고 가정함으로써 더 빠르게 학습합니다.
- 결과: 이 단순한 버전은 복잡한 원본보다 실제로 새로운 게임으로 일반화하는 데 더 뛰어났습니다. 새로운 상황에 혼동될 가능성이 적었습니다.
PM-PSRO (투사 매칭 PSRO):
- 비유: 관중의 '소음'을 무시하는 코치를 상상해 보세요. 모든 점수를 하나하나 보는 대신, 전체 팀의 평균에 비해 선수가 어떻게 수행하는지 봅니다. 평균 이하인 선수는 즉시 잊혀집니다. 평균 이상인 선수는 스포트라이트를 받습니다.
- 결과: 이 간소화된 버전도 복잡한 원본보다 우수했습니다. 이는 LLM 의 복잡한 혼합 논리가 불필요했음을 증명했습니다.

5. 핵심 교훈

이 논문은 LLM 은 아이디어를 제안하는 데 뛰어나지만, 이를 정제하는 데는 인간이 필요하다고 결론 내립니다.

LLM 은 500 개의 움직이는 부품으로 기계를 만드는 창의적인 발명가처럼 행동했습니다. 연구자들은 "이 부품 중 3 개만 있으면 작동하고, 나머지 497 개를 제거하면 더 빠르고 신뢰할 수 있다"는 엔지니어처럼 깨달았습니다.

주장의 요약:
연구자들은 AI 를 활용하여 인간 전문가를 능가하는 새로운 게임 플레이 알고리즘을 발견하는 데 성공했습니다. 그러나 AI 의 raw 발견 결과는 너무 복잡하고 전문화되어 있었습니다. 불필요한 복잡성을 수술적으로 제거함으로써, 그들은 새로운 보지 못한 게임을 처리하는 데 더 뛰어난 더 간단하고 깔끔한 알고리즘을 만들었습니다. 이는 인간이 결과를 단순화하고 해석할 수 있다면 AI 가 과학적 발견을 위한 강력한 도구가 될 수 있음을 증명합니다.

기술 요약: 대규모 언어 모델을 활용한 다중 에이전트 학습 알고리즘 발견

문제 정의

역사적으로 불완전 정보 게임에 대한 다중 에이전트 강화 학습 (MARL) 의 발전은 알고리즘적 기준의 수동적이고 반복적인 정제에 의존해 왔습니다. 연구자들은 후회 할인 (regret discounting), 균형 유도 (equilibrium derivation) 등 업데이트 규칙과 구조적 선택의 방대한 조합 공간을 직관과 시행착오를 통해 탐색하며, 종종 최적이지 않을 수 있는 수학적으로 다루기 쉬운 휴리스틱에 의존해 왔습니다. 본 논문은 대규모 언어 모델 (LLM) 을 사용하여 알고리즘 발견 과정 자체를 자동화함으로써 수동 설계의 한계를 해결하는 방안을 제시합니다.

방법론

저자들은 MARL 알고리즘 설계를 자동화하기 위해 LLM(특히 Gemini 2.5 Pro) 기반의 분산 진화 코딩 에이전트인 AlphaEvolve를 배포합니다. 이 프레임워크는 알고리즘의 소스 코드를 유전체로 간주하고, LLM 을 지능형 유전 연산자로 활용하여 의미론적 변이를 수행하고, 논리를 재작성하며, 새로운 기호 연산을 주입합니다.

본 연구는 두 가지 명확한 게임 이론적 패러다임에 초점을 맞춥니다:

가상 후회 최소화 (CFR): 탐색 공간은 세 가지 진화 가능한 Python 클래스로 정의됩니다: RegretAccumulator(후회가 어떻게 처리/할인되는지), PolicyFromRegretAccumulator(후회에서 정책이 어떻게 유도되는지), PolicyAccumulator(최종 평균을 위해 정책이 어떻게 가중치 부여되는지).
정책 공간 응답 오라클 (PSRO): 탐색 공간은 두 개의 별도 진화 가능 클래스를 포함합니다: TrainMetaStrategySolver(오라클 훈련 중 메타 전략 생성용) 와 EvalMetaStrategySolver(평가용 전략 프로필 계산용). 이 분리를 통해 LLM 은 훈련과 평가 간의 동적이고 비대칭적인 스케줄을 발견할 수 있습니다.

실험 프로토콜:

훈련 세트: 알고리즘은 4 가지 게임 (3 인 쿤 포커, 2 인 레두크 포커, 4 카드 구프스피얼, 5 면 거짓말 주사위) 세트에서 진화시켜 적합도 (부정적 착취 가능성) 를 극대화합니다.
평가: 고정된 진화 알고리즘은 더 넓은 18 개 게임 세트에서 테스트되며, 여기에는 더 큰 변형과 다른 게임 계열 (포커, 구프스피얼, 거짓말 주사위, 블로토, 배틀십) 이 포함됩니다.
절제 (Ablation) 를 통한 증류: LLM 이 핵심 원리 위에 복잡한 시너지 메커니즘을 층층이 쌓아 과적합할 수 있음을 인식하여, 저자들은 엄격한 훈련 - 테스트 분할 절제 (train-test split ablation) 방법론을 사용합니다. 그들은 로그 개선 점수의 사분위 평균 (IQM) 을 사용하여 일반화를 주도하는 구성 요소와 단순히 훈련 적합도를 극대화하는 구성 요소를 분리합니다.

주요 기여

1. 고성능 알고리즘의 발견

진화적 탐색은 최첨단 인간 설계 기준과 경쟁 가능한 두 가지 새로운 알고리즘을 성공적으로 발견했습니다:

VAD-CFR (Volatility-Adaptive Discounted CFR): 변동성 추적을 기반으로 한 적응형 할인, 즉각적인 후회 부스팅, 그리고 낙관적 예측을 특징으로 하는 CFR 변형입니다.
SHOR-PSRO (Smoothed Hybrid Optimistic Regret PSRO): 최적 후회 매칭+ (ORM+) 와 평활화된 최선 순수 전략을 혼합한 메타 솔버로, 훈련과 평가에 비대칭 솔버를 활용합니다.

2. 과도한 전문화 (Over-Specialization) 의 식별

체계적인 절제 연구를 통해, 원시 LLM 발견물은 훈련 분포에서는 매우 효과적이지만, 종종 훈련 세트에 밀접하게 결합되어 일반화에는 기여하지 않는 "과도하게 설계된" 구성 요소 (예: 특정 변동성 추적, 복잡한 혼합 스케줄) 를 포함한다는 것을 논문은 입증합니다. 어떤 경우에는 이러한 복잡한 메커니즘이 일반화 패널티로 작용합니다.

3. 최소 솔버의 증류

절제 연구에서 식별된 과도한 전문화 휴리스틱을 제거하고 기초적인 구조적 변화만 유지함으로써, 저자들은 두 가지 최소적이고 수학적으로 순수한 솔버를 생산합니다:

WOP-CFR (Warm-started Optimistic Predictive CFR): 이 증류된 버전은 VAD-CFR 의 세 가지 핵심 메커니즘을 유지합니다:
1. 하드 웜-스타트 (Hard Warm-Start): 초기 고분산 노이즈가 누적 전략을 오염시키는 것을 방지하기 위해 정책 평균화를 엄격하게 500 회 반복 동안 중단합니다.
2. 극단적 비대칭 할인: 음수 후회에 대해 음수 지수 ( $\beta = -0.1$ ) 를 사용하여 즉각적인 "망각 게이트" 역할을 하며, 인간이 튜닝한 기준보다 더 빠르게 이를 감쇠시킵니다.
3. 낙관적 예측: 감쇠하는 낙관적 인자와 함께 비선형 투영 (지수 1.5) 을 통해 정책을 유도합니다.
  결과: WOP-CFR 은 구조적 복잡성을 크게 줄이면서 원시 VAD-CFR 보다 우수한 일반화 (더 높은 테스트 IQM) 를 달성합니다.
PM-PSRO (Projection Matching PSRO): 이 증류된 버전은 SHOR-PSRO 의 복잡한 하이브리드 혼합 및 어닐링 스케줄을 단일 핵심 메커니즘으로 대체합니다:
1. 접선 투영 유틸리티 (Tangent-Projected Utility): 후회 매칭의 후회 신호를 기대 유틸리티 벡터의 접선 투영 (개체군 평균으로 유틸리티 중심화) 으로 대체합니다.
2. 동적 예산: 내부 솔버 반복 횟수를 경험적 게임 크기에 비례하여 선형적으로 확장합니다.
3. 통합 솔버: 훈련과 평가 모두에 시간 평균 솔버를 사용합니다.
  결과: PM-PSRO 는 단순화되고 해석 가능한 구조로 일반화 작업에서 원시 SHOR-PSRO 를 능가합니다.

결과

성능: 원시 발견물 (VAD-CFR, SHOR-PSRO) 과 증류된 최소 솔버 (WOP-CFR, PM-PSRO) 모두 18 개 게임 평가 세트에서 일관되게 상위 3 위 안에 랭크됩니다.
일반화: 증류된 솔버는 종종 홀드아웃 테스트 게임에서 원시 LLM 대응물보다 더 나은 성과를 냅니다. 예를 들어, WOP-CFR 은 원시 VAD-CFR 의 15 개 대비 18 개 게임 중 14 개에서 가장 낮은 착취 가능성을 달성하지만, 원시 버전 대비 +0.119 의 테스트 IQM 개선을 보입니다. 마찬가지로 PM-PSRO 는 SHOR-PSRO 대비 +0.059 의 테스트 IQM 개선을 보입니다.
강건성: 증류된 알고리즘은 다양한 게임 계열 (포커, 구프스피얼, 거짓말 주사위, 블로토, 배틀십) 과 다양한 규모 (2 개에서 347,810 개의 정보 상태까지) 에서 높은 성능을 유지합니다.
무작위 NFG: 무작위로 생성된 $N$ 인 정규형 게임 (Normal-Form Games) 평가에서 SHOR-PSRO 와 PM-PSRO 모두 확립된 기준 (Uniform, AlphaRank, PRD, RM) 을 압도하며, 반복 횟수가 증가함에 따라 성능 격차가 벌어집니다.

중요성과 주장

본 논문은 LLM 기반 진화적 탐색이 알고리즘 발견을 위한 강력한 제안 메커니즘이라고 주장하지만, 이는 인간 - 루프 (human-in-the-loop) 파이프라인에 내장될 때 가장 효과적이라고 명시합니다. LLM 은 복잡한 메커니즘의 후보 조합을 제안하지만, 어떤 구성 요소가 실제로 일반화되는지 표면화하기 위해서는 체계적인 훈련 - 테스트 절제가 필요합니다. 그런 다음 연구자는 이러한 생존자들을 최소 솔버로 증류합니다.

저자들은 그들의 작업이 해석 가능한 코드 골격을 진화시킴으로써 표현력 있는 신경 메타 학습과 기호적 발견 사이의 간극을 메운다고 강조합니다. 그들은 증류된 알고리즘에 대한 공식적인 수렴 보장을 제공하지 않으며 (이것들은 이론적으로 증명된 것이 아니라 경험적으로 동기 부여된 것임), 정확한 착취 가능성 계산의 필요성으로 인해 평가가 표적 기반 기준과 35 만 개 미만의 정보 상태를 가진 게임으로 제한되었다고 명시적으로 밝힙니다. 연구는 LLM 의 진정한 가치가 직관적이지 않은 메커니즘을 찾기 위해 설계 공간을 탐색하는 능력에 있으며, 이는 이후 견고하고 일반화 가능한 알고리즘으로 단순화될 수 있다는 결론으로 끝납니다.