Combining Tree-Search, Generative Models, and Nash Bargaining Concepts in Game-Theoretic Reinforcement Learning

이 논문은 몬테카를로 트리 탐색과 학습된 생성 모델을 결합한 '생성적 최선 대응 (GenBR)' 알고리즘을 제안하여 대규모 불완전 정보 게임에서 PSRO 프레임워크와 내시 협상 이론을 활용해 인간과 협상할 때 사회적 후생과 내시 협상 점수 측면에서 인간 수준의 성과를 내는 확장 가능한 적대 모델링 훈련 체계를 구축했습니다.

핵심

1. 문제: AI 는 왜 상대방을 모를까?

예전부터 AI 는 바둑이나 포커 같은 게임에서 인간을 이기는 데 성공했습니다. 하지만 그 비결은 대부분 **"상대방이 어떤 사람인지 전혀 모른 채, 오직 내 전략만 최적화하는 것"**이었습니다.

• 비유: 가상의 '포커 토너먼트'에 나갔는데, 상대가 초보자인지, 프로인지, 아니면 오늘 컨디션이 좋은지 전혀 모른 채 무작정 똑같은 전략으로만 덤비는 상황입니다.
• 한계: 만약 상대가 "나는 항상 bluff(속임수) 를 잘 치는 사람"이라면, AI 는 그걸 알아채고 대응해야 이길 수 있습니다. 하지만 기존 AI 는 상대방의 성향을 파악하는 '두뇌'가 부족해서, 새로운 상대를 만나면 당황하기 일쑤였습니다.

2. 해결책: "상상력"과 "탐색"을 결합한 새로운 AI

이 논문은 두 가지 핵심 기술을 섞어서 AI 에게 **'상상력'**과 **'탐색 능력'**을 부여했습니다.

① GenBR (생성적 최선 대응): "상상하는 탐정"

기존 AI 는 상대방의 숨겨진 카드 (정보) 를 정확히 계산해야만 최선의 수를 찾았습니다. 하지만 정보가 너무 많으면 계산이 불가능해집니다.
이 연구는 딥러닝을 이용해 상대방의 숨겨진 정보를 '상상'하게 만들었습니다.

• 비유: 추리소설을 쓰는 작가처럼 생각해보세요.
  • 기존 방식: 모든 가능한 범인 (상대방의 카드) 을 하나하나 직접 조사해서 범인을 찾아야 합니다. (시간이 너무 오래 걸림)
  • 이 연구의 방식 (GenBR): "아, 이 상황이라면 범인은 A 일 가능성이 높겠지?"라고 **머릿속으로 시뮬레이션 (상상)**을 해봅니다. 이 '상상'을 통해 수많은 경우의 수를 빠르게 훑어보고, 가장 유력한 시나리오에 맞춰 움직입니다.
  • 결과: 상대방이 어떤 카드를 들고 있든, AI 는 그 상황을 머릿속으로 빠르게 재구성하고 "아, 이럴 때는 이렇게 해야겠다"라고 판단합니다.

② PSRO (전략의 진화): "수만 명의 연습 상대"

AI 가 혼자만 연습하면 실력이 늘지 않습니다. 다양한 스타일의 상대를 만나야 합니다.
이 연구는 AI 가 수천 번의 게임을 반복하며 다양한 '상대방 유형'을 만들어내고, 그들에게 맞춰 전략을 발전시키는 시스템을 사용했습니다.

• 비유: 축구팀이 훈련할 때, 단순히 같은 팀원끼리만 연습하는 게 아니라, '공격형', '수비형', '공격수' 등 다양한 스타일의 가상의 상대팀을 만들어내며 훈련하는 것과 같습니다.
• 특이점: 여기서 중요한 건, 단순히 이기는 것뿐만 아니라 **"상대방과 함께 모두 이기는 (협상) 방법"**을 찾도록 훈련시켰다는 점입니다.

3. 실험 결과: 인간과 함께 협상하는 AI

연구진은 이 AI 를 **"딜 or 노 딜 (Deal or No Deal)"**이라는 협상 게임에 투입했습니다. 두 사람이 물건을 나누어 가지면서 서로의 이익을 최대화해야 하는 게임입니다.

• 인간 vs 인간: 인간들끼리 협상하면 보통 서로를 속이거나 이기려고 해서, 전체적인 이익이 줄어들거나 불공평해지곤 합니다.
• 인간 vs 이 AI:
  • AI 는 인간의 협상 스타일을 실시간으로 파악했습니다. ("아, 이 사람은 공평한 걸 좋아하네", "저 사람은 이득을 많이 보려고 하네")
  • 그 결과, 인간과 AI 가 협상했을 때의 만족도 (사회적 후생) 가 인간끼리 협상했을 때와 비슷하거나 오히려 더 좋았습니다.
  • 특히 '공정함 (Fair)'을 추구하도록 훈련된 AI 는 인간이 가장 만족해하는 결과를 만들어냈습니다.

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

이 연구는 AI 가 **"상대방을 이해하는 능력"**을 갖췄다는 것을 보여줍니다.

• 과거: "내가 이기려면 어떻게 해야 할까?" (이기적인 계산)
• 현재 (이 연구): "상대방이 무엇을 원하고, 어떻게 생각할까? 그리고 그걸 고려해서 우리가 모두 이득을 보는 방법은?" (상호 이해와 협상)

5. 일상 속 적용 가능성

이 기술은 게임뿐만 아니라 우리 삶 곳곳에 적용될 수 있습니다.

• 자동 입찰: 경매장에서 다른 입찰자들의 성향을 파악해 가장 합리적인 가격을 제시할 수 있습니다.
• 자율 주행: 다른 차들이 어떻게 운전할지 예측하고, 사고 없이 모두 안전하게 이동하는 길을 찾을 수 있습니다.
• 협상 봇: 회사 간 계약이나 무역 협상에서 상대방의 숨은 의도를 파악하고, 양측이 만족하는 타협점을 찾아낼 수 있습니다.

결론

이 논문은 **"AI 가 단순히 계산기처럼 작동하는 것을 넘어, 상대방의 마음을 읽는 '상상력'을 갖게 되었다"**는 것을 증명했습니다. 마치 훌륭한 협상가가 상대방의 표정과 말투를 읽으며 최선의 결과를 끌어내는 것처럼, 이 AI 는 게임과 협상에서 인간과 가장 자연스럽게, 그리고 공정하게 소통할 수 있는 능력을 갖게 되었습니다.

기술 요약

이 논문은 **게임 이론적 상대방 모델링 (Game-Theoretic Opponent Modeling)**을 위해 심층 강화학습 (Deep RL), 검색 (Search), 그리고 **생성 모델 (Generative Models)**을 결합한 새로운 프레임워크를 제안합니다. 특히, 대규모 불완전 정보 게임 (Large Imperfect Information Games) 에서 기존 방법론의 한계를 극복하고 인간과 협상할 수 있는 고성능 에이전트를 개발하는 데 중점을 둡니다.

다음은 논문의 핵심 내용을 요약한 기술적 요약입니다.

---

1. 문제 정의 (Problem)

기존의 상대방 모델링 방법은 두 가지 주요 단계를 따릅니다:

1. 상대방의 전략에 대한 믿음 분포 (Belief Distribution) 구축.
2. 이 모델을 기반으로 한 최적 대응 (Best Response) 실행.

그러나 기존 접근법들은 다음과 같은 한계가 있었습니다:

• 도메인 의존성: 상대방 모델을 만들기 위해 게임 규칙이나 인간 행동에 대한 수작업 휴리스틱 (Heuristics) 이 필요하여 다른 도메인으로의 전이가 어렵습니다.
• 확장성 부족: 대규모 불완전 정보 게임 (예: 포커, 협상 게임) 에서 세계 상태 (World State) 에 대한 사후 확률 분포를 정확하게 계산하는 것은 계산적으로 불가능 (Intractable) 합니다. 따라서 기존 최적 대응 알고리즘들이 확장되지 못했습니다.

2. 제안 방법론 (Methodology)

저자들은 **GenBR (Generative Best Response)**이라는 새로운 알고리즘과 이를 PSRO (Policy Space Response Oracles) 프레임워크에 통합한 훈련 체계를 제안합니다.

A. GenBR (Generative Best Response)

AlphaZero 스타일의 MCTS (Monte-Carlo Tree Search) 를 불완전 정보 게임에 확장한 알고리즘입니다.

• 생성 모델 통합: 기존 IS-MCTS (Information Set MCTS) 는 검색 트리의 루트에서 모든 가능한 세계 상태를 나열하고 확률을 계산해야 했지만, GenBR 은 **심층 생성 모델 (Deep Generative Model)**을 학습시켜 검색 시작 시 세계 상태를 직접 샘플링합니다.
• PVGN (Policy-Value-and-Generative Network): 정책 네트워크 (Policy Net), 가치 네트워크 (Value Net), 그리고 생성 네트워크 (Generative Net) 로 구성된 3 개의 신경망을 사용합니다.
  • 생성 네트워크: 에이전트의 정보 상태 (Information State) 를 입력받아 상대방의 숨겨진 선호도나 세계 상태의 분포를 학습하고 샘플링합니다.
  • 검색 과정: 생성된 세계 상태를 기반으로 MCTS 를 수행하며, Bayesian 학습을 통해 온라인으로 상대방의 전략 프로필을 업데이트합니다.
• 장점: 이 방법은 불완전 정보 공간이 매우 큰 게임에서도 확장 가능하며, 검색 시 (Test-time) 에 환경 상태와 상대방 전략을 동시에 추론할 수 있습니다.

B. PSRO 프레임워크 및 협상 이론 기반 메타 전략 솔버

GenBR 을 PSRO 의 '오라클 (Oracle)' 단계에 사용하여 오프라인 상대방 모델을 자동 생성합니다.

• PSRO (Policy Space Response Oracles): 반복적인 게임 이론적 추론과 집단 기반 훈련을 통해 상대방의 전략 혼합 (Mixture) 을 구축합니다.
• 내시 협상 해 (Nash Bargaining Solution, NBS) 활용: 협상 게임의 특성상, 단순한 제로섬 (Zero-sum) 해가 아닌 협력적 해가 필요합니다. 저자들은 **내시 협상 해 (NBS)**를 기반으로 한 새로운 메타 전략 솔버 (MSS) 를 제안합니다.
  • 이는 파레토 최적 (Pareto Frontier) 에 근접하는 전략 프로필을 식별하고, 사회적 후생 (Social Welfare) 을 극대화하는 혼합 전략을 생성합니다.
  • 로그 내시 곱 (Log Nash Product) 을 최대화하는 경사 상승법 (Projected Gradient Ascent) 을 사용하여 효율적으로 해를 구합니다.

3. 주요 기여 (Key Contributions)

1. GenBR 알고리즘 개발: AlphaZero 스타일의 MCTS 에 심층 생성 모델을 결합하여 대규모 불완전 정보 게임에서 강력한 최적 대응 전략을 학습하는 새로운 검색 방법을 제안했습니다. 이는 온라인 의사결정 시 환경 상태와 상대방 전략을 추론할 수 있게 합니다.
2. 게임 이론적 메타 전략 솔버: PSRO 프레임워크 내에서 내시 협상 해 (NBS) 와 파레토 효율성을 기반으로 한 새로운 솔버들을 도입했습니다. 이는 협상 상황에서 인간과 유사한 사회적 후생과 공정한 결과를 도출하는 데 기여합니다.
3. 인간 행동 연구 (Human Behavioral Study): 'Deal or No Deal' 협상 게임에서 인간 참가자와 에이전트의 상호작용을 평가했습니다. 제안된 에이전트는 인간 간의 협상과 비교했을 때 동등한 수준의 사회적 후생과 내시 협상 점수를 달성했습니다.

4. 실험 결과 (Results)

A. Colored Trails 및 벤치마크 게임

• Colored Trails (협상 게임): 제안된 NBS 기반 메타 전략 솔버는 기존 솔버들보다 파레토 갭 (Pareto Gap) 을 더 크게 줄였으며, 훈련 과정에서 파레토 프론트에 더 빠르게 수렴했습니다.
• 일반적 성능: 다양한 벤치마크 게임 (Kuhn Poker, Leduc Poker 등) 에서 PSRO 와 GenBR 의 조합이 Nash 균형 (Nash Equilibrium) 수렴 속도와 사회적 후생 측면에서 우수한 성능을 보였습니다.

B. Deal or No Deal (DoND) 인간 실험

• 실험 설정: 346 명의 인간 참가자를 모집하여 인간 vs 인간 (HvH) 및 인간 vs 에이전트 (HvA) 조건으로 협상 게임을 진행했습니다.
• 성능 비교:
  • 공격적 에이전트 (IndRL, Comp): 인간을 과도하게 착취하여 개인 수익은 높았으나, 사회적 후생은 낮았습니다.
  • 협력적 에이전트 (Coop, Fair): Fair 에이전트는 인간과 협상 시 사회적 후생 (Combined Utility) 과 내시 협상 점수 (Nash Bargaining Score) 에서 인간 간 협상 (HvH) 과 유사한 수준을 달성했습니다.
  • GenBR 의 효과: 생성 모델과 검색을 결합한 에이전트는 훈련 중 및 테스트 중 더 강력한 정책을 발견했으며, 인간과 협상할 때 인간과 유사한 효율성과 공정성을 보여주었습니다.

5. 의의 및 결론 (Significance)

이 연구는 도메인 지식 없이도 대규모 불완전 정보 환경에서 상대방을 모델링하고 적응할 수 있는 범용적인 다중 에이전트 훈련 체계를 제시했습니다.

• 기술적 혁신: 생성 모델을 통한 세계 상태 추론과 MCTS 검색의 결합은 불완전 정보 게임의 계산적 난제를 해결하는 새로운 패러다임을 제시합니다.
• 실용적 가치: 자동화된 경매 입찰, 로봇 협상, 사이버 보안, 자율 주행 차량 등 다양한 다중 에이전트 시나리오에 적용 가능합니다.
• 윤리적 고려: 협상 에이전트가 사용자의 의도와 다른 착취적 행동을 할 수 있는 위험을 인지하고, 실제 배포 전 철저한 테스트와 인간 중심의 연구가 필요함을 강조했습니다.

요약하자면, 이 논문은 심층 생성 모델과 게임 이론적 검색을 결합하여 인간과 자연스럽게 협상할 수 있는 AI 에이전트를 성공적으로 개발하고 검증한 획기적인 연구입니다.