What Do Agents Think One Another Want? Level-2 Inverse Games for Inferring Agents' Estimates of Others' Objectives

이 논문은 기존 1 단계 역게임 이론의 한계를 극복하기 위해, 다중 에이전트 간 상호작용에서 각 에이전트가 상대방의 목표에 대해 어떻게 추론하는지를 파악하는 2 단계 역게임 추론 프레임워크를 제안하고, 이를 통해 실제 시나리오에서 발생하는 목표 불일치를 효과적으로 규명합니다.

핵심

🚗 핵심 비유: "오해하는 두 명의 운전자"

이 논문의 주인공은 자율주행차 두 대입니다. 한 차는 파란색, 다른 한 차는 빨간색이라고 상상해 보세요.

1. 기존의 방법 (레벨 1): "모두가 다 아는 척하는 관찰자"

기존의 기술 (레벨 1) 은 상황을 이렇게 봅니다.

"아, 파란 차가 차선을 바꾸고 싶어 하고, 빨간 차도 차선을 바꾸고 싶어 하네. 두 차가 서로의 의도를 완벽하게 알고 있어서 서로 양보하거나 충돌을 피할 거야."

하지만 실제로는 어떨까요?

• 파란 차의 생각: "저 빨간 차는 차선을 바꾸지 않고 내 차선으로 들어오려는 거야. 내가 먼저 가야지!"
• 빨간 차의 생각: "저 파란 차는 차선을 바꾸지 않고 내 차선을 지키려는 거야. 내가 먼저 가야지!"

두 차는 서로의 진짜 의도를 모르고, 서로가 어떻게 생각할지를 잘못 추측하고 있습니다. 그래서 두 차는 서로를 막아서며 **정체 (Deadlock)**에 빠집니다.

기존의 기술 (레벨 1) 은 이 정체를 보고 "아, 두 차 모두 차선을 바꾸고 싶지 않아서 멈춰 있는구나"라고 잘못 결론 내립니다. 하지만 실제로는 두 차 모두 차선을 바꾸고 싶어 할 뿐, 서로의 생각을 오해하고 있는 것이죠.

2. 새로운 방법 (레벨 2): "심리 분석가 같은 관찰자"

이 논문이 제안하는 레벨 2 방법은 훨씬 더 똑똑합니다. 관찰자는 단순히 "차가 뭐를 원하는가?"만 보지 않습니다. 대신 이렇게 질문합니다.

**"파란 차는 빨간 차가 무엇을 원한다고 생각하고 있을까? 그리고 빨간 차는 파란 차가 무엇을 원한다고 생각하고 있을까?"**

이제 관찰자는 다음과 같이 분석합니다.

• "아! 파란 차는 빨간 차가 차선을 바꾸지 않을 거라고 오해하고 있어서 멈춘 거야."
• "그리고 빨간 차도 파란 차가 차선을 바꾸지 않을 거라고 오해하고 있어서 멈춘 거야."

이렇게 **서로의 '오해' (Belief)**까지 파악하면, 왜 두 차가 멈춰 있는지, 그리고 어떻게 하면 이 오해를 풀고 안전하게 차선을 바꿀 수 있는지 정확히 이해할 수 있습니다.

---

🧩 이 논문이 해결한 세 가지 문제

1. 왜 기존 방법은 실패했을까요?
기존 방법은 "사람들은 서로의 마음을 다 안다"라는 이상적인 가정을 했습니다. 하지만 현실 (도시 운전, 협상 등) 에선 사람들이 서로의 마음을 잘못 이해하는 경우가 많습니다. 이 논문은 그 오해의 구조를 찾아내는 기술을 개발했습니다.

2. 왜 이것이 어려운가요? (수학적 난제)
서로가 서로를 어떻게 생각하는지 추측하는 것은 미로 찾기와 같습니다.

• A 가 B 를 어떻게 생각하는지 알면, B 는 A 를 어떻게 생각하는지 알 수 있습니다.
• 그런데 A 가 B 를 어떻게 생각하는지 다시 바뀌면, B 의 생각도 바뀝니다.
  이처럼 생각의 고리가 꼬여 있어, 수학적으로 정답을 찾기 매우 어렵고 (비볼록 문제) 여러 갈래 길이 존재합니다. 이 논문은 그 미로에서 가장 합리적인 답을 찾는 **효율적인 나침반 (알고리즘)**을 만들었습니다.

3. 실제로 효과가 있을까요?
저자들은 가상의 도시 운전 시나리오를 만들어 실험했습니다.

• 레벨 1 방법: "두 차가 서로를 막아서고 있어. 아마도 둘 다 차선을 바꾸고 싶지 않은가 봐." (틀린 결론)
• 레벨 2 방법: "두 차 모두 차선을 바꾸고 싶어 하지만, 서로의 의도를 잘못 읽어서 서로를 막고 있어. 이 오해를 풀면 해결될 거야." (정확한 결론)

---

💡 요약: 이 연구가 우리에게 주는 메시지

이 논문은 인공지능이나 자율주행차가 단순히 "상대방이 뭐를 원하는지"만 보는 게 아니라, "상대방이 나를 어떻게 생각하는지"까지 이해해야 진정한 협력이 가능하다고 말합니다.

마치 연인 사이의 오해를 풀 때, "내가 원하는 게 뭐야?"만 묻는 게 아니라 "너는 내가 너를 어떻게 생각하는지 어떻게 생각하니?"라고 물어봐야 오해를 풀 수 있는 것과 같습니다.

이 기술은 앞으로 더 안전한 자율주행, 원활한 도시 교통, 그리고 인간과 로봇이 자연스럽게 소통하는 미래를 만드는 데 큰 역할을 할 것입니다.

기술 요약

1. 문제 정의 (Problem Statement)

• 배경: 자율 주행, 협상 등 다중 에이전트 상호작용 환경에서는 각 에이전트의 행동 목적 (Objective) 을 추론하여 상대방의 행동을 예측하는 것이 필수적입니다.
• 기존 접근법의 한계 (Level-1 Inference): 기존 역게임 (Inverse Game) 연구들은 대부분 '1 단계 (Level-1)' 추론을 가정합니다. 이는 관찰자가 에이전트들의 목표를 추론할 때, 모든 에이전트가 서로의 목표를 완벽하게 알고 있다는 가정을 전제로 합니다.
• 실제 문제: 실제 세계 (예: 도시 주행) 에서는 에이전트들이 서로의 목표를 오해하거나 불완전한 정보를 바탕으로 행동하는 경우가 많습니다. 서로의 목표를 잘못 추정하면 (예: 상대방이 차선을 변경하려는지, 유지하려는지 오해), 이로 인해 비효율적이거나 위험한 행동 (교착 상태, deadlock) 이 발생합니다.
• 핵심 질문: "각 에이전트의 실제 목표는 무엇이며, 각 에이전트가 다른 에이전트의 목표를 어떻게 추정하고 있는가?"를 동시에 추론할 수 있는 프레임워크가 필요합니다.

2. 제안 방법론 (Methodology)

저자들은 '2 단계 (Level-2) 역게임' 프레임워크를 제안하여 에이전트들이 서로의 목표를 어떻게 인지하고 있는지 (Beliefs) 를 추론합니다.

• 2 단계 게임 모델링:
  • 각 에이전트 $i$는 자신의 실제 목표 파라미터 $\theta_{i,i}$를 알고 있으며, 다른 에이전트 $j$의 목표에 대한 추정치 $\theta_{i,j}$를 가집니다.
  • 에이전트 $i$는 자신이 추정한 모든 에이전트의 목표 ($\Theta_i = \{\theta_{i,i}, \theta_{i,-i}\}$) 를 기반으로 가상의 나시 균형 (Hypothesized Nash Equilibrium) 을 계산하고, 이를 바탕으로 자신의 행동을 결정합니다.
• 수학적 형식화:
  • 관찰자는 관측된 행동 데이터 $y$를 바탕으로 각 에이전트의 목표 파라미터와 상대방에 대한 추정 파라미터 ($\hat{\Theta}$) 를 추정합니다.
  • 이는 최대 가능도 추정 (MLE) 문제로, 관측 데이터와 모델이 예측한 행동 간의 오차를 최소화하는 $\hat{\Theta}$를 찾는 과정입니다.
• 혼합 상보성 문제 (MCP) 전사 및 최적화:
  • 비선형 동역학과 비이차형 비용 함수를 다루기 위해, 각 에이전트의 가상의 나시 균형 조건을 **혼합 상보성 문제 (Mixed Complementarity Problem, MCP)**로 전사합니다.
  • 암시적 미분 (Implicit Differentiation): MCP 솔버의 해를 파라미터에 대해 미분하여 손실 함수의 그래디언트를 효율적으로 계산합니다. 이를 통해 기울기 기반 (Gradient-based) 최적화 알고리즘을 설계하여 국소 최적해 (Local Optima) 를 찾습니다.

3. 주요 기여 (Key Contributions)

1. 2 단계 역게임 프레임워크 정립:

   • 마음의 이론 (Theory of Mind) 개념을 기반으로, 에이전트들이 서로의 목표에 대해 가지는 **불일치된 추정 (Mismatched Estimates)**을 명시적으로 모델링하는 수학적 프레임워크를 제안했습니다.
   • 이를 coupled Nash equilibrium 문제의 집합으로 형식화했습니다.

2. 비볼록성 증명 및 오차 한계 분석:

   • 선형 - 이차 (LQ) 게임과 같은 단순한 환경에서도 2 단계 역추론 문제가 **비볼록 (Non-convex)**임을 증명했습니다.
   • 에이전트들의 목표 추정치가 불일치할 때, 기존 1 단계 추론이 얼마나 큰 예측 오차를 발생시키는지 이론적 상한선과 하한선을 유도했습니다.

3. 효율적인 알고리즘 개발 및 실험 검증:

   • MCP 기반의 기울기 계산 알고리즘을 개발하여 2 단계 역게임 문제를 해결했습니다.
   • 시뮬레이션 결과: 합성 도시 주행 (차선 변경) 시나리오에서, 기존 1 단계 방법은 에이전트들의 오해를 설명하지 못해 교착 상태를 잘못 예측하는 반면, 제안된 2 단계 방법은 에이전트들의 **불일치된 신념 (Mismatched Beliefs)**을 정확히 복원하여 행동의 원인을 설명했습니다.

4. 실험 결과 (Results)

• LQ 게임 (선형 - 이차 게임):
  • 에이전트들이 서로의 목표를 다르게 추정할 때, 1 단계 추론의 손실 (Loss) 은 급격히 증가하는 반면, 2 단계 추론은 낮은 손실 값을 유지하며 정확한 파라미터를 복원했습니다.
  • 1 단계 추론의 예측 오차는 에이전트 간 목표 추정치의 이질성 (Heterogeneity) 에 비례하여 증가함을 확인했습니다.
• 차선 변경 시나리오 (Urban Driving):
  • 상황: 두 차량이 서로의 차선 변경 의도를 오해하여 교착 상태 (Deadlock) 에 빠지는 상황.
  • 1 단계 추론: 두 차량 모두 차선을 유지하려는 것으로 잘못 추론하여, 교착 상태의 원인을 설명하지 못함.
  • 2 단계 추론: "차량 A 는 차량 B 가 차선을 변경하려 한다고 믿고, 차량 B 는 차량 A 가 차선을 변경하려 한다고 믿는다"는 불일치된 신념을 성공적으로 복원. 이를 통해 교착 상태가 발생한 이유 (과도한 주의) 를 정확히 설명함.

5. 의의 및 결론 (Significance & Conclusion)

• 이론적 의의: 기존의 역게임 연구가 가진 "완전한 정보 공유"라는 비현실적인 가정을 완화하고, 에이전트의 **인지적 불일치 (Cognitive Misalignment)**를 수학적으로 모델링하는 새로운 패러다임을 제시했습니다.
• 실용적 가치: 자율 주행 차량, 로봇 협업, 도시 교통 관리 등 복잡한 다중 에이전트 시스템에서 관찰자가 에이전트들의 행동 동기 (Motivation) 와 오해의 구조를 파악할 수 있게 하여, 더 안전하고 효율적인 예측 및 제어 전략 수립에 기여합니다.
• 미래 과제: 비선형 확률 게임으로의 확장, 2 단계 파라미터의 관측 가능성 (Observability) 에 대한 형식적 분석, 그리고 경쟁적 가설을 추론하는 방법론 개발 등이 향후 과제로 제시되었습니다.

이 논문은 다중 에이전트 시스템의 상호작용을 이해하는 데 있어, 단순한 '목표 추론'을 넘어 '상대방에 대한 추론 (Belief)'까지 포함하는 **계층적 추론 (Hierarchical Inference)**의 필요성을 강력하게 입증했습니다.