Code-Space Response Oracles: Generating Interpretable Multi-Agent Policies with Large Language Models

이 논문은 블랙박스 신경망 정책의 해석 불가능성을 해결하기 위해 대규모 언어 모델을 활용해 인간이 읽을 수 있는 코드로 직접 정책을 생성하는 '코드-스페이스 응답 오라클 (CSRO)' 프레임워크를 제안하며, 이를 통해 경쟁력 있는 성능과 함께 설명 가능한 다양한 다중 에이전트 전략을 도출할 수 있음을 보여줍니다.

핵심

1. 왜 이 연구가 필요할까요? (기존의 문제점)

기존에 게임이나 전략을 배우는 AI(강화학습) 는 **"무작위 시뮬레이션"**을 수백만 번 반복하며 스스로 학습합니다.

• 비유: 마치 **"눈을 가리고 천 번을 넘어가면서 넘어지지 않는 법을 터득한 사람"**과 같습니다.
• 문제: 이 사람은 넘어지지 않는 법을 잘 알고 있지만, 왜 그렇게 했는지 설명할 수 없습니다. (블랙박스). 또한, 수백만 번의 연습이 필요해서 시간과 돈이 많이 듭니다.

2. 이 논문이 제안한 해결책: CSRO (코드 공간 응답 오라클)

연구진은 **"대규모 언어 모델 (LLM, 예: 우리와 대화하는 AI)"**을 활용했습니다. AI 가 직접 코드를 짜게 하는 것입니다.

• 비유: 이제 AI 는 눈을 가리지 않고, **"유능한 요리사 (LLM) 가 책 (게임 규칙) 을 보고, 다른 요리사들의 실패 사례 (상대방 전략) 를 분석한 뒤, 새로운 레시피 (전략 코드) 를 직접 작성"**하는 방식입니다.
• 장점:
  1. 투명성: AI 가 만든 전략이 코드로 되어 있으므로, 우리가 코드를 보면 "아, 이 AI 는 상대방이 이런 행동을 하면 저렇게 대응하는구나!"라고 이해할 수 있습니다.
  2. 효율성: 수백만 번의 시행착오 대신, 논리와 지식을 활용해 훨씬 빠르게 전략을 만들어냅니다.

3. 어떻게 작동하나요? (세 가지 단계)

이 시스템은 세 가지 방식으로 전략을 다듬습니다.

1. 한 번에 바로 쓰기 (Zero-shot):

   • AI 에게 "이 게임 규칙과 상대방 전략을 보고 이기는 코드를 짜줘"라고 한 번만 요청합니다.
   • 비유: 요리사에게 레시피를 한 번에 받아서 바로 쓰는 것.

2. 수정하며 다듬기 (Linear Refinement):

   • 처음 만든 코드가 이기지 못하면, AI 에게 "너는 여기서 졌어. 왜 졌는지 분석하고 코드를 고쳐줘"라고 말합니다.
   • 비유: 요리사가 맛을 보고 "소금이 부족해"라고 말하면, 다시 소금을 넣고 다시 맛을 보는 과정.

3. 진화시키는 시스템 (AlphaEvolve):

   • 여러 개의 AI 가 서로 다른 코드를 만들고, 서로 경쟁하게 합니다. 이기는 코드는 살아남고, 진 코드는 사라지거나 변형됩니다.
   • 비유: 자연의 진화처럼, 가장 강한 전략만 남도록 여러 세대를 거쳐 전략을 발전시키는 것.

4. 실험 결과: 실제로 잘 하나요?

연구진은 두 가지 게임으로 실험했습니다.

• 가위바위보 (반복 게임):
  • 상대방이 어떤 패턴을 보이는지 분석해서 이기는 전략을 코드로 만들었습니다.
  • 결과: 기존 AI 들보다 더 적은 계산량으로 상대방을 이기면서도, 왜 이겼는지 코드로 설명 가능했습니다.
• 포커 (레두치 포커):
  • 상대방이 언제 블러핑 (속임수) 을 하고, 언제 진심으로 베팅하는지 분석했습니다.
  • 결과: 상대방이 "항상 콜 (Call) 을 한다"는 것을 알아차리면, AI 는 아예 블러핑을 멈추고 강한 카드만 베팅하는 등 상황에 맞춰 전략을 바꿨습니다. 이 모든 논리가 코드로 남아 있어 우리가 확인했습니다.

5. 핵심 요약: 왜 이것이 중요한가요?

기존의 AI 는 "결과만 좋고, 과정은 알 수 없는 마법" 같았습니다. 하지만 이 논문이 만든 CSRO는 **"이유를 설명할 수 있는 논리적인 전략가"**입니다.

• 신뢰: "왜 이 AI 가 저런 행동을 했지?"라고 의심할 필요가 없습니다. 코드를 보면 답이 나옵니다.
• 실용성: 복잡한 게임뿐만 아니라, 자율주행이나 사이버 보안처럼 실제 삶에 적용할 때 "왜 그렇게 판단했는지" 설명이 가능한 AI가 꼭 필요합니다.

한 줄 결론:

"이제 AI 는 눈가리고 넘어지는 법을 배우는 게 아니라, 우리가 읽을 수 있는 '이기는 법의 레시피'를 직접 써주는 똑똑한 요리사가 되었습니다."

기술 요약

1. 문제 정의 (Problem)

다중 에이전트 강화학습 (MARL) 분야에서 정책 공간 반응 오라클 (Policy-Space Response Oracles, PSRO) 은 복잡한 게임에서 근사적인 게임 이론적 균형 (Approximate Nash Equilibria) 을 계산하는 데 성공적으로 사용되어 왔습니다. 그러나 기존 PSRO 의 핵심 구성 요소인 '오라클 (Best Response Oracle)'은 심층 강화학습 (Deep RL) 을 기반으로 합니다. 이로 인해 다음과 같은 심각한 한계가 존재합니다.

• 블랙박스성 (Black-box Nature): RL 오라클이 생성한 정책은 신경망 가중치로 표현되어 해석이 불가능하며, 신뢰성 검증이나 디버깅이 어렵습니다.
• 샘플 비효율성: RL 오라클이 수렴하기 위해서는 수백만~수십억 번의 게임 시뮬레이션이 필요하여 계산 비용이 매우 큽니다.
• 실제 적용의 장벽: 고위험 (High-stakes) 환경이나 설명 가능성이 필수적인 분야에서 이러한 불투명한 에이전트를 배포하는 것은 현실적으로 어렵습니다.

2. 방법론 (Methodology)

저자들은 이러한 문제를 해결하기 위해 코드 공간 반응 오라클 (Code-Space Response Oracles, CSRO) 을 제안합니다. 이는 RL 오라클을 대신하여 대규모 언어 모델 (LLM) 을 사용하여 정책을 실행 가능한 소스 코드로 직접 생성하는 프레임워크입니다.

핵심 메커니즘

1. 프로그래밍 합성 (Program Synthesis) 으로의 재정의:

   • 기존의 수치적 최적화 (Numerical Optimization) 를 LLM 이 게임 규칙, API, 상대방 전략 설명을 입력받아 가독성 있는 Python 코드를 생성하는 프로그래밍 합성 문제로 전환합니다.
   • 생성된 코드는 주석과 문서화 (Docstring) 가 포함되어 있어 전략의 논리를 인간이 직접 분석할 수 있습니다.

2. CSRO 알고리즘 구조:

   • PSRO 의 반복적 루프를 따르지만, 오라클 단계에서 LLM 을 사용합니다.
   • 각 반복 (Iteration) 에서 현재 메타 게임 (Meta-game) 의 균형 전략 ($\sigma$) 에 대한 최선의 대응 (Best Response) 을 LLM 에게 요청합니다.
   • 생성된 정책은 정책 집합 ($P$) 에 추가되어 메타 게임을 풍부하게 만듭니다.

3. 오라클 정제 메커니즘 (Oracle Refinement Mechanisms):
   생성된 코드의 품질을 높이기 위해 세 가지 방식을 도입했습니다.

   • Zero-Shot: 한 번의 프롬프트로 직접 코드를 생성합니다.
   • Linear Refinement: 생성된 코드의 성능을 평가하여 점수가 낮으면 (패배 시), 피드백을 바탕으로 LLM 에게 코드를 수정하도록 요청하는 단일 스레드 반복 루프입니다.
   • AlphaEvolve: 분산된 진화 알고리즘을 적용합니다. LLM 이 여러 스레드에서 프로그램을 변형 (Mutation) 하고, 점수 함수 (Best Response 성능) 를 기준으로 진화적 탐색을 수행하여 다양하고 강력한 전략을 찾습니다.

4. 컨텍스트 관리 (Context Abstraction):

   • 모든 상대방의 소스 코드를 입력하면 토큰 제한을 초과할 수 있으므로, LLM 이 상대방 전략을 자연어로 요약하거나 상위 $k$개 전략만 필터링하여 프롬프트에 포함시킵니다.

3. 주요 기여 (Key Contributions)

• 해석 가능한 다중 에이전트 학습 프레임워크: RL 의 블랙박스 정책을 인간이 읽을 수 있는 코드로 대체하여 전략의 검증과 디버깅을 가능하게 했습니다.
• LLM 기반 오라클의 확장성: 기존 LLM-PSRO 와 달리, 반복적 정제 (Iterative Refinement) 와 컨텍스트 요약을 도입하여 복잡한 게임에서도 확장 가능하고 견고한 전략을 생성할 수 있음을 증명했습니다.
• AlphaEvolve 통합: LLM 기반 진화 시스템을 Best Response 솔버로 활용하여, 단순한 제로샷 생성을 넘어 게임 이론적 균형에 근접하는 고성능 전략을 발견했습니다.
• 엄격한 벤치마크 검증: 기존 연구가 내부 비교에 그쳤던 것과 달리, 표준화된 외부 봇 집단과 게임 이론 솔버 (CFR+, PSRO-IMPALA) 와 비교하여 CSRO 의 성능을 객관적으로 입증했습니다.

4. 실험 결과 (Results)

저자들은 반복된 가위바위보 (Repeated Rock-Paper-Scissors, RRPS) 와 반복된 Leduc Hold'em 포커 환경에서 CSRO 를 평가했습니다.

• 반복된 가위바위보 (RRPS):

  • AlphaEvolve 오라클이 가장 낮은 취약성 (Exploitability) 을 보이며 PSRO 프레임워크의 목표인 견고한 균형을 달성했습니다.
  • Linear Refinement (코드 입력) 방식은 가장 높은 집계 점수 (AggScore) 를 기록하여, 27B 파라미터 규모의 LLM 에이전트 (Gemma 3) 와 경쟁 가능한 성능을 보였습니다.
  • 기존 RL 기반 PSRO-IMPALA 는 모든 지표에서 CSRO 보다 현저히 낮은 성능을 보였습니다.

• 반복된 Leduc 포커:

  • CSRO-AlphaEvolve 는 CFR+ (게임 이론 솔버) 와 경쟁 가능한 취약성 (4.4) 을 보였습니다.
  • 특히, 상대방의 패턴 (AlwaysCall, AlwaysFold) 을 학습하여 초내쉬 (Super-Nash) 수준의 수익을 내는 전략을 발견했습니다. 예를 들어, AlwaysFold 봇에게는 끊임없이 블러핑을 하고, AlwaysCall 봇에게는 가치 베팅을 하는 등 상황 적응형 전략을 코드로 구현했습니다.

• 해석 가능성 (Qualitative Analysis):

  • 생성된 코드는 고차원적 추론 (Theory of Mind), 확률적 예측, 다양한 휴리스틱의 앙상블 등을 명확한 주석과 함께 구현하고 있었습니다.
  • 이는 블랙박스 신경망에서는 불가능했던 전략의 논리적 흐름을 직접 확인하고 수정할 수 있게 합니다.

5. 의의 및 결론 (Significance)

• 패러다임의 전환: 다중 에이전트 학습을 "불투명한 매개변수 최적화"에서 "해석 가능한 알고리즘 행동 합성" 으로 전환했습니다.
• 계산 효율성: RRPS 환경에서 CSRO 는 게임 전체를 수행하는 데 LLM 호출이 한 번만 필요한 반면 (정책 생성 후 재사용), 기존 LLM 에이전트는 매 턴마다 LLM 을 호출해야 하므로 CSRO 가 훨씬 계산 효율적입니다.
• 실용적 가치: 설명 가능성 (Explainability) 이 중요한 금융, 사이버 보안, 자율 주행 등 고위험 분야에서 다중 에이전트 시스템을 배포할 수 있는 새로운 길을 열었습니다.
• 한계점: 현재 LLM 의 컨텍스트 윈도우 제한으로 인해 매우 복잡한 상태 공간 (StarCraft 등) 에 적용하는 것은 여전히 과제로 남아있으며, 프롬프트 품질과 LLM 자체의 성능에 결과가 의존적입니다.

이 논문은 LLM 을 단순한 대화 도구가 아닌, 복잡한 게임 이론적 문제를 해결하고 해석 가능한 전략을 생성하는 지능형 오라클로 활용할 수 있음을 입증한 획기적인 연구입니다.