[논문 리뷰] A Comprehensive Survey of Multiagent Reinforcement Learning

📌 A Comprehensive Survey of Multiagent Reinforcement Learning
📝 저자 : Lucian Bus¸oniu, Robert Babuˇska, and Bart De Schutter
📅 발행 연도 : IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews) ( Volume: 38, Issue: 2, March 2008)
🔗 논문 링크 : https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=4445757

🍀 지난 멀티에이전트 논문 리뷰에 이어서 이번에는 MAS 중 가장 활발히 연구된 분야인 Multiagent Reinforcement Learning (MARL)에 대해 더 심화적으로 공부해보려고 한다.

---

I. INTRODUCTION

A. Contribution and Related Work

이 논문은 다중 에이전트 강화학습(MARL)에 대한 가장 포괄적이고 체계적인 초기 Survey 중 하나이다.

당시 기존 연구들은 부분적인 영역만 다뤘다.

• 특정 알고리즘에 집중
• 일부 응용(ex. 로봇 축구, 경제학 모형)에 한정
• 이론적 분석 없이 경험적 결과 위주

그러나, 본 논문은

• 단일 에이전트 RL 개념을 출발점으로 삼아,
• 협력(Cooperative), 경쟁(Competitive), 혼합(Mixed) 환경 모두 포괄,
• 이론적 기반 + 응용 사례를 모두 포함하는 “총체적 관점”을 제시했다.

특히 강조한 기여는 다음과 같다.

1. 명확한 분류 체계 제시: 협력/경쟁/혼합 작업에 따라 MARL 알고리즘을 체계적으로 분류
2. 게임이론적 관점과 연결: 단순한 RL 확장이 아닌, 게임이론, 제어이론과 결합
3. 응용 가능성: 로봇, 분산 제어, 경제학 등 실제 도메인에서의 의미를 분석

➡️ 즉, MARL을 독립된 학문적 주제로 확립시키는 기틀을 마련했다고 볼 수 있다.

B. Overview

논문의 전체 구성은 다음과 같다.

1. 강화학습 배경 지식: 단일 에이전트 RL → 다중 에이전트 확장
2. MARL의 장점과 한계: 왜 중요한가, 왜 어려운가
3. MARL의 목표: 협력/경쟁/혼합에서 어떤 학습 성과를 추구하는가
4. 알고리즘 분류: 대표적인 MARL 기법들을 체계적으로 정리
5. 응용 도메인: 분산 제어, 로봇 팀, 금융, 자원 관리 등
6. 전망과 결론: 향후 과제 및 연구 방향

---

II. BACKGROUND: REINFORCEMENT LEARNING

MARL을 이해하기 위해서는 먼저 RL(Reinforcement Learning)의 기본 개념이 필요하다.

A. Single-Agent Case

1. 기본 정의

• RL은 환경(Environment) 과 상호작용하는 에이전트(Agent)가 보상(reward)을 최대화하는 정책(policy)을 학습하는 과정이다.
• 이는 마르코프 결정 과정(MDP, Markov Decision Process)으로 수학적으로 정의된다.
  • 상태 집합 $S$
  • 행동 집합 $A$
  • 전이 확률 $P(s'|s,a)$
  • 보상 함수 $R(s,a)$
• 목표: 장기 누적 보상 $\sum_t \gamma^t r_t$ 의 최대화
  
  

2. 주요 알고리즘

• Value-based 방법
  • Q-learning, SARSA 등
  • 각 상태-행동 쌍의 가치를 추정 후, greedy 정책으로 행동 선택
• Policy-based 방법
  • Policy Gradient, REINFORCE 등
  • 정책을 직접 파라미터화하고 최적화
• Actor-Critic 방식
  • Value-based + Policy-based 절충

➡️ 이들이 단일 에이전트 강화학습의 “전통적 뼈대”를 이룬다.

B. Multiagent Case

1. 문제 정의

• 여러 에이전트가 동시에 학습할 때, 각 에이전트가 보는 환경은 비정적(non-stationary)이다.
  • 이는 다른 에이전트도 계속 정책을 바꾸기 때문이다.
  • 따라서, 한 에이전트 입장에서 상태 전이 확률 $P$ 가 시간에 따라 변화한다.
• 즉, 단일 에이전트의 MDP가 아니라 Stochastic Game (확률적 게임)으로 모델링된다.

2. 학습 목표

• 협력적 상황: 공동 보상을 극대화 (ex. 팀플레이)
• 경쟁적 상황: 자신의 보상 극대화 (게임이론적 균형 찾기)
• 혼합 상황: 부분적으로 협력하면서도 이익을 다투는 복잡한 관계

➡️ 즉, MARL은 단순히 Q-learning 여러 개가 아니라,
상호작용에 따른 동태적 환경 변화를 본질로 가진다.

C. Static, Repeated, and Stage Games

게임이론은 MARL을 이해하는 기반이다.

1. Static game (정적 게임)

   • 한 번의 행동 선택으로 끝남
   • ex) Prisoner’s Dilemma (죄수의 딜레마)
   • 균형: Nash Equilibrium

2. Repeated game (반복 게임)

   • 동일 게임을 여러 번 반복
   • 에이전트는 과거(history)를 이용해 전략을 조정
   • ex) “Tit-for-Tat” 같은 보복/협력 전략이 등장 가능

3. Stage game (단계 게임)

   • 매 시점마다 상태와 보상 구조가 달라짐
   • RL이 다루는 환경과 유사
   • Stochastic Game = 반복된 stage game + 확률적 전이

➡️ 따라서 MARL은 게임이론 + 강화학습의 교차 영역에 서 있다.

---

III. BENEFITS AND CHALLENGES IN MARL

다중 에이전트 강화학습은 단일 에이전트보다 훨씬 복잡하지만, 동시에 현실적 문제를 해결하는 데 강력한 장점을 가진다.

A. Benefits of MARL

1. 분산성 (Decentralization)

   • 여러 에이전트가 동시에 학습 → 중앙집중식 제어가 필요 없음
   • 시스템이 커져도 확장성(Scalability)이 뛰어남
   • ex) 교통 신호 제어에서 각 신호등이 개별 학습해도 전체 최적화 가능

2. 강건성 (Robustness)

   • 일부 에이전트가 실패해도 시스템 전체가 무너지지 않음
   • 로봇 팀에서 한 로봇이 고장나도 다른 로봇이 임무를 이어갈 수 있음

3. 자연스러운 모델링 (Natural Modeling)

   • 실제 세계는 본질적으로 다중 주체 환경
   • 사회, 경제, 군사, 네트워크 모두 여러 개체가 동시에 상호작용
   • 따라서, MARL은 현실을 가장 충실히 반영하는 학습 방식

4. 협력적 이득 (Emergent Cooperation)

   • 개별 학습을 통해 자연스럽게 협력 행동이 나타날 수 있음
   • ex) 개미 집단, 분산 로봇 시스템

B. Challenges in MARL

하지만, 장점만 있는 것은 아니다. MARL은 단일 에이전트 RL보다 훨씬 어려운 문제들을 가진다.

1. Non-stationarity

   • 다른 에이전트도 학습하기 때문에 환경의 전이 확률 $P(s'|s,a)$ 이 시간에 따라 계속 변함
   • 단일 에이전트 RL의 이론적 수렴성(ex. Q-learning의 수렴 보장)이 깨짐
   • 학습 안정성 문제가 가장 큰 도전 과제 중 하나

2. Credit Assignment Problem

   • 공동 보상(Cooperative setting)에서 누가 성과에 기여했는지 알기 어려움
   • 잘못된 크레딧 할당은 학습을 방해
   • ex) 축구 게임에서 골을 넣은 로봇과 패스를 잘 연결한 로봇의 기여도를 나누기 어려움

3. Scalability

   • 에이전트 수가 늘어나면 상태·행동 공간이 지수적으로 폭발
   • Joint-action learner 방식은 $|A|^N$ (행동 공간이 N차원으로 증가) → 비현실적
   • 따라서, 독립 학습(Independent Learning)이나 근사 기법 필요

4. Partial Observability

   • 각 에이전트가 전체 상태를 보지 못하고 국소적 관찰(local observation)만 가능
   • 정보 부족 문제 + 통신이 없으면 학습 성능 저하

5. Equilibrium Selection

   • 게임이론적으로는 여러 Nash Equilibrium이 존재할 수 있음
   • 학습이 어느 균형으로 수렴할지 보장되지 않음
   • 협력적 상황에서도 “비협력적 균형”으로 수렴할 수 있음

---

IV. MARL GOAL

MARL의 목표는 단순히 “보상을 최대화한다”가 아니다.
환경이 협력적/경쟁적/혼합적이냐에 따라 학습 목표 자체가 달라진다.

1. 협력적(Cooperative) 목표

• 모든 에이전트가 공동 보상을 최적화
• 팀 전체가 최대 성과를 내는 것이 목표
• 문제: credit assignment, 역할 분담 필요

2. 경쟁적(Competitive) 목표

• 각 에이전트가 자신의 보상을 최대화
• 다른 에이전트의 성과는 내 성과의 손실
• 목표: Nash Equilibrium, Minimax 전략 등

3. 혼합(Mixed) 목표

• 현실의 대부분은 협력 + 경쟁 혼합
• ex) 무선 네트워크에서 주파수 자원을 공유(협력)하면서도 성능 경쟁
• 목표는 상대적 성과 + 협력적 효율성 간 균형

4. 연구적 의미

• MARL 목표 정의는 단순한 “보상 함수” 문제를 넘어섬
• 어떤 균형으로 수렴할지, 협력이 자발적으로 발생할지,
  게임이론적 분석과 RL 알고리즘 설계가 동시에 필요

---

V. TAXONOMY OF MARL ALGORITHMS

MARL 알고리즘은 크게 네 가지 범주로 분류할 수 있다.

1. Fully Cooperative Tasks (완전 협력적 작업)

   • 모든 에이전트가 공동 보상을 공유
   • 목표: 팀 전체의 성과 극대화

2. Explicit Coordination Mechanisms (명시적 조정 메커니즘)

   • 에이전트들이 통신, 역할 분담, 계획 공유 등을 통해 협력
   • 목표: 조정 비용을 줄이고 안정적인 협력 도출

3. Fully Competitive Tasks (완전 경쟁적 작업)

   • 제로섬 게임 구조
   • 목표: Nash Equilibrium, Minimax 전략을 달성

4. Mixed Tasks (혼합 작업)

   • 협력 + 경쟁이 동시에 존재
   • 현실 세계의 가장 일반적인 형태

➡️ 이 네 가지 분류가 MARL 알고리즘을 이해하는 큰 틀을 제공한다.

---

VI. MARL ALGORITHMS

이제 각 범주별 대표 알고리즘을 살펴보겠다.

A. Fully Cooperative Tasks

1. Joint-Action Learners (JAL)

• 모든 에이전트의 행동 조합 $(a_1, a_2, …, a_N)$ 에 대해 Q값을 학습
• ex) Joint Action Learner Q-learning
• 장점: 이론적으로 최적 공동 정책 가능
• 단점: 행동 공간 $|A|^N$ → 지수적 폭발 (Scalability 문제)

2. Independent Learners (IL)

• 각 에이전트가 독립적으로 학습(자신의 행동과 관찰만 활용)
• ex) Independent Q-learning
• 장점: 계산량 감소
• 단점: 환경이 non-stationary → 수렴 보장 어려움

3. Team Learning Approaches

• Global reward를 사용하면서 개별 기여도를 추정
• ex) Difference Rewards (D-value)
  • 전체 보상에서 한 에이전트의 행동이 빠졌을 때의 변화량으로 기여도를 측정
• 효과: credit assignment 문제 완화

B. Explicit Coordination Mechanisms

1. Communication 기반

• 에이전트 간 명시적 메시지 교환
• ex) Distributed Q-learning with communication
• 문제: 통신 비용, 지연(latency), 신뢰성

2. 역할(Role)-기반 학습

• 각 에이전트에 역할(Role)을 부여하고 학습
• ex) Role-based MARL (탐험자/공격자/수비자 역할 분담)
• 효과: credit assignment 단순화, 전략 다양성 증가

3. 계약 기반(Contract Net Protocol)

• 에이전트가 협상하여 역할/작업을 분배
• ex) 분산 작업 할당에서 사용

➡️ 명시적 조정 기법은 협력의 안정성을 보장하지만, 통신 비용과 설계 복잡성이 단점이다.

C. Fully Competitive Tasks

1. Markov Games (Stochastic Games)

• 다중 에이전트 환경을 확률적 게임으로 모델링
• 각 에이전트의 보상은 상충

2. Minimax-Q (Littman, 1994)

• 제로섬 게임에서 사용
• 각 상태에서 최적의 Minimax 정책 학습
• 보장: Nash Equilibrium에 수렴

3. Nash-Q (Hu & Wellman, 1998)

• 제로섬이 아닌 일반 합(Game)에서도 적용 가능
• 각 상태에서의 Nash Equilibrium 기반 Q-learning
• 단점: 계산량이 크고, 실제 환경에서는 수렴 어려움

➡️ 경쟁적 MARL은 게임이론과 RL의 결합이 핵심이다.

D. Mixed Tasks

1. Market-Based MARL

• 에이전트들이 자원을 사고팔며 학습
• 가격 메커니즘으로 협력/경쟁을 동시에 반영

2. Negotiation & Bargaining Approaches

• 에이전트 간 협상을 통해 협력 수준 결정
• ex) 다중 로봇이 작업을 분배할 때, 비용-보상을 흥정

3. General-Sum Q-learning

• 각 에이전트의 보상이 다르고, 상호작용 구조가 복잡한 경우 확장

➡️ 혼합 작업은 현실 응용에서 가장 빈번하며,
협력적 효율성과 경쟁적 이익 사이 균형을 찾는 것이 핵심이다.

---

VII. APPLICATION DOMAINS

MARL은 다양한 실제 응용 도메인에서 활발히 연구되고 있다.

A. Distributed Control

• 전력망 제어, 교통 제어, 통신 네트워크와 같이 대규모 분산 시스템에 활용
• 각 에이전트가 국소적으로 의사결정 → 전체 시스템 안정성 유지
• ex) 스마트 그리드에서 각 발전소·소비자가 독립적으로 RL을 통해 에너지 효율 최적화

B. Robotic Teams

• 다중 로봇 협업 문제: 탐사, 수색, 구조, 군사 응용
• 로봇 축구(RoboCup)가 대표적 벤치마크
• 개별 로봇이 학습하면서도 팀 전체 전략이 발전

C. Automated Trading

• 금융 시장: 다중 거래 에이전트가 서로 경쟁/협력
• RL을 통한 포트폴리오 최적화, 경매 전략, 자동 매매 시스템 설계
• 특징: 상대방의 전략 변화가 환경에 큰 영향을 줌 → 전형적 MARL 시나리오

D. Resource Management

• 컴퓨팅 자원, 무선 주파수, 물류 등에서 에이전트들이 자원을 효율적으로 나눔
• 경쟁과 협력이 동시에 발생하는 혼합적 상황
• ex) 클라우드 환경에서 서버 간 작업 분배, 주파수 할당 문제

E. Remarks

• MARL 응용은 이질적, 복잡한 환경에서 특히 효과적
• 그러나, 실제 시스템 적용에는 수렴성, 안정성, 계산 비용의 문제가 여전히 존재

---

VIII. OUTLOOK

다음은 미래 연구 방향에서 저자들이 제안한 주요 포인트이다.

A. Practical MARL

• 실세계 적용을 위한 확장성 있는 알고리즘 필요
• 특히 에이전트 수가 늘어날 때도 학습이 안정적으로 유지되어야 함

B. Learning Goal

• 단순히 Nash Equilibrium 수렴이 아니라,
  사회적으로 바람직한 균형을 학습하는 방법 연구 필요
• Cooperative-Competitive trade-off에서 어떤 결과를 도출할지가 핵심

C. Joint Environment and Learning Dynamics

• 학습 과정이 환경에 영향을 주고, 환경 변화가 다시 학습에 영향을 줌
• MARL은 단순한 정적 문제 풀이가 아니라 동태적 상호작용 시스템 연구로 확장되어야 함

---

IX. CONCLUSION

본 논문의 결론은 다음과 같다.

• MARL의 포괄적 정리를 최초로 제시
• 배경(RL, 게임이론), 장점과 도전 과제, 알고리즘 분류, 응용까지 망라
• MARL은 분산성, 강건성, 현실 적합성에서 큰 잠재력을 가지지만,
  수렴성, 비정상성, 크레딧 할당 문제가 여전히 중요한 연구 과제로 남음

➡️ 결론적으로, MARL은 AI, 제어이론, 게임이론을 통합하는 중요한 학문적 주제임을 명확히 했다.

---

💭 My Thoughts

멀티에이전트 시스템에 대해서 공부하기 전에는 이를 단순히 “여러 개의 에이전트가 함께 움직이는 구조” 정도로만 생각했었는데, 이번 논문을 읽으면서, 그 안에는 단순한 협력이 아니라 끝없는 학습과 변화 속에서 질서를 만들어 가는 과정이 있다는 걸 깨달았다.

특히 흥미로웠던 건, 한 에이전트의 학습이 곧 다른 에이전트의 환경을 바꾸기 때문에, 세상 자체가 끊임없이 달라지는 느낌이었다. 인간 사회도 각자의 선택과 행동이 서로의 삶을 바꾸듯이, 에이전트들도 그렇게 얽혀 있었다.