NePPO: Near-Potential Policy Optimization for General-Sum Multi-Agent Reinforcement Learning

Each language version is independently generated for its own context, not a direct translation.

🎭 1. 문제 상황: 혼란스러운 파티 (General-Sum Game)

상상해 보세요. 여러 명이 한 방에 모여 파티를 하고 있습니다.

어떤 사람은 춤을 추고 싶고 (경쟁), 어떤 사람은 조용히 대화하고 싶고 (협력), 어떤 사람은 술을 마시고 싶고 (혼합된 목적) 있습니다.
이들에게 "누가 무엇을 해야 할지" 정해달라고 하면, 서로의 의견이 충돌해서 싸움이 나거나, 아무도 행복하지 않은 결과가 나올 수 있습니다.

기존의 AI 학습 방법들은 이런 복잡한 상황 (일반 합 게임) 에서 안정적으로 작동하지 못했습니다. 마치 "누가 이기면 누가 진다"는 식의 단순한 게임 (0 합 게임) 이나 "모두가 무조건 협력해야 한다"는 게임에서는 잘 작동했지만, 서로의 이익이 섞인 복잡한 상황에서는 AI 들이 미친 듯이 흔들리거나 (불안정), 서로 다른 결론에 도달해 혼란을 빚었습니다.

💡 2. 해결책: NePPO (가상의 '만능 지도' 그리기)

이 논문에서 제안한 NePPO라는 방법은 아주 창의적인 아이디어를 사용합니다.

"서로 다른 목표를 가진 사람들이 모두 동의할 수 있는 '가상의 지도 (Potential Function)'를 먼저 그려보자."

🗺️ 비유: "모두가 좋아하는 메뉴를 정하는 요리사"

여러 명이 식당에 갔는데, A 는 매운 걸, B 는 달콤한 걸, C 는 짠 걸 원합니다.

기존 방법: 각자 자기 입맛대로 주문해서 (MAPPO 등), 결국 메뉴가 섞이거나 싸움이 납니다.
NePPO 의 방법:
1. 요리사 (AI) 는 먼저 **"이 메뉴를 다 같이 먹으면, 우리 모두의 만족도가 얼마나 오를까?"**를 계산하는 **가상의 점수표 (Potential Function)**를 만듭니다.
2. 이 점수표는 "누가 무엇을 먹든, 전체적인 만족도가 어떻게 변하는지"를 예측합니다.
3. 그리고 이 점수표가 가장 높아지는 지점을 찾습니다.
4. 그 지점이 바로 **"서로가 불만 없이 받아들일 수 있는 최선의 균형 (내쉬 균형)"**이 됩니다.

즉, 서로 다른 욕심을 가진 사람들을 위해, '함께 만족할 수 있는 공통된 목표'를 수학적으로 찾아내고, 그 목표를 향해 움직이게 만드는 것입니다.

⚙️ 3. 어떻게 작동할까? (두 단계의 춤)

NePPO 는 두 가지 작업을 반복하며 이 '가상의 지도'를 완벽하게 만듭니다.

협력 춤 (Cooperative Dance):
- AI 들이 가상의 점수표 (지도) 를 믿고 함께 협력합니다. "이 지도에 따르면 우리가 이렇게 움직이면 다 같이 행복해지겠군!" 하고 움직입니다.
- 이때는 마치 팀워크가 완벽한 스포츠 팀처럼 움직입니다.
개인 춤 (Individual Dance):
- 그다음, 각자 "내가 만약 혼자 이 지도를 무시하고 내 뜻대로 움직인다면, 내 이익은 얼마나 변할까?"를 계산해 봅니다.
- 만약 "내 뜻대로 움직여도 이득이 안 나거나, 오히려 손해라면" 그건 최선의 균형입니다.
- 하지만 만약 "혼자 움직였을 때 더 큰 이익이 난다면", 그건 아직 균형이 아니라는 뜻입니다.

핵심: NePPO 는 이 두 춤을 반복하며, **"혼자 움직여도 이득이 안 나는 상태 (균형)"**가 될 때까지 가상의 지도를 수정합니다. 지도가 완벽해지면, AI 들은 자연스럽게 서로를 해치지 않는 최선의 행동을 하게 됩니다.

🏆 4. 실험 결과: 왜 NePPO 가 더 좋은가?

저자들은 이 방법을 실제 게임 (다양한 AI 에이전트들이 음식과 적을 피하는 환경) 에서 테스트했습니다.

기존 방법 (MAPPO 등): "우리 팀이 이겨야 해!"라고 생각해서 한쪽 팀만 이기고 다른 팀은 망가뜨리는 결과를 낳았습니다. (불공평함)
NePPO: "서로가 너무 불만족하지 않는 선에서 최선의 결과를 찾아야 해"라고 생각했습니다.
- 그 결과, **다른 방법들보다 훨씬 적은 '후회 (Regret)'**를 남겼습니다. 즉, "아, 내가 저렇게 했으면 더 좋았을 텐데"라는 생각이 가장 적게 들게 한 것입니다.

📝 한 줄 요약

"서로 다른 목표를 가진 AI 들이 싸우지 않고 공존하려면, '서로가 모두 만족할 수 있는 가상의 공통 목표 (지도)'를 먼저 찾아서, 그 지도를 따라 움직이게 하면 된다."

이 논문은 복잡한 세상에서 AI 들이 서로를 해치지 않고, 오히려 함께 최선의 결과를 만들어낼 수 있는 새로운 학습 규칙을 제시했다는 점에서 매우 의미 있습니다.

Each language version is independently generated for its own context, not a direct translation.

1. 문제 정의 (Problem)

다중 에이전트 강화 학습 (MARL) 은 자율 주행, 드론 추적, 동적 가격 책정 등 다양한 분야에서 적용되고 있지만, 일반합 게임 (General-Sum Games) 환경, 즉 에이전트 간에 협력과 경쟁이 혼재된 상황에서 학습을 수행하는 것은 여전히 큰 도전 과제입니다.

학습 불안정성: 기존 MARL 알고리즘은 2 인 제로섬 게임이나 완전 협력 게임과 같은 제한된 설정에서만 수렴이 보장됩니다. 일반합 게임에서는 학습 동역학이 불안정하거나 혼돈 (chaotic) 상태에 빠질 수 있습니다.
균형 선택의 어려움: 에이전트들의 선호도가 이질적이고 상충될 때, 어떤 시스템 수준의 목표를 설정해야 하는지 불분명합니다. 또한, 여러 개의 나시 균형 (Nash Equilibrium) 이 존재할 때 어떤 균형을 선택할지 결정하는 기준이 부재합니다.
기존 방법의 한계: 중앙 집중식 학습 - 분산 실행 (CTDE) 기반 알고리즘 (MAPPO, MADDPG 등) 은 협력 환경에서는 잘 작동하지만, 이질적인 에이전트와 혼합 동기 (mixed-motive) 환경에서는 균형 수렴을 보장하지 못하거나 수렴하지 못합니다.

2. 방법론 (Methodology)

저자들은 **NePPO(Near-Potential Policy Optimization)**라는 새로운 MARL 파이프라인을 제안합니다. 이 방법의 핵심은 원래 게임의 나시 균형을 근사하는 **협력 게임의 공통 보상 함수 (Potential Function)**를 학습하는 것입니다.

가. 마르코프 근사 포텐셜 함수 (Markov Near-Potential Function, MNPF)

개념: 모든 에이전트가 동일한 유틸리티 함수 (포텐셜 함수 $\Phi$ ) 를 공유하는 협력 게임을 정의합니다.
핵심 아이디어: 만약 이 협력 게임의 나시 균형이 원래 일반합 게임의 $\alpha$ -근사 나시 균형이 되도록 하는 포텐셜 함수 $\Phi$ 를 찾을 수 있다면, 해당 균형을 구하는 것이 가능해집니다.
목표: 모든 에이전트의 편향된 전략 변경에 따른 보상 변화와 포텐셜 함수의 변화 사이의 오차 ( $\alpha$ ) 를 최소화하는 $\Phi$ 를 학습합니다.

나. 최적화 지표 (Optimization Metric)

기존의 MNPF 정의 (모든 정책 프로필에 대해 조건을 만족) 는 계산적으로 매우 어렵습니다. 따라서 저자들은 **균형 주변 (equilibrium-relevant)**의 정책 변화에만 초점을 맞춘 새로운 목적 함수 $F_i(\Phi)$ 를 도입했습니다.

정의: $F_i(\Phi)$ 는 협력 게임의 균형 $\pi^*,\Phi$ 에서 에이전트 $i$ 가 자신의 최적 반응 (Best Response) 으로 편향되었을 때, 포텐셜 함수의 변화량과 실제 보상 함수의 변화량 사이의 차이입니다.
정리 3.1: 만약 $\max_i F_i(\Phi) \le \alpha$ 라면, $\pi^*,\Phi$ 는 원래 게임의 $\alpha$ -근사 나시 균형이 됩니다.
최소화 목표: $\min_{\Phi} \max_i F_i(\Phi)$ 를 최소화하여 $\alpha$ 를 줄이고, 더 정확한 근사 균형을 찾습니다.

다. NePPO 알고리즘 (Algorithm 1)

이 비선형, 비볼록 최적화 문제를 해결하기 위해 0 차 (Zeroth-order) 경사 하강법을 사용합니다. 알고리즘은 다음과 같은 모듈로 구성됩니다.

매개변수화된 포텐셜 함수: $\Phi_w$ 를 신경망 매개변수 $w$ 로 표현합니다.
부드러운 근사 (Smoothing): $\max_i F_i(\Phi)$ 의 비연속성을 해결하기 위해 Softmax 기반의 부드러운 근사 함수 $\tilde{F}_\beta(\Phi)$ 를 사용합니다.
0 차 경사 추정:
- 매개변수 $w$ 를 무작위 방향 $u$ 로 교란시켜 $\hat{w}$ 와 $\check{w}$ 를 생성합니다.
- 두 지점에서의 목적 함수 값 차이를 이용해 경사를 추정합니다.
내부 모듈 실행 (매 반복마다):
- (M1) 협력 게임 솔버 (CoopGameSolver): 현재 포텐셜 함수 $\Phi_w$ 를 공통 보상으로 사용하는 협력 게임의 나시 균형 $\pi^*,\Phi$ 를 구합니다. (예: HAPPO, MAPPO 사용)
- (M2) 개별 최적 반응 솔버 (RLSolver): 다른 에이전트가 $\pi^*,\Phi$ 를 사용할 때, 각 에이전트 $i$ 의 최적 반응 $\pi^*,J_i$ 를 구합니다. (예: PPO 사용)
- 값 평가: 몬테카를로 롤아웃을 통해 $F_i(\Phi)$ 값을 계산합니다.
업데이트: 추정된 0 차 경사를 사용하여 $w$ 를 업데이트합니다.

3. 주요 기여 (Key Contributions)

새로운 MARL 파이프라인 제안: 일반합 게임에서 근사 나시 균형을 계산하기 위해 에이전트 독립적인 포텐셜 함수를 학습하는 NePPO 를 제안했습니다.
새로운 최적화 목적 함수: 전체 정책 공간이 아닌 균형 주변에서 포텐셜 조건을 만족하도록 하는 새로운 목적 함수 $F_i(\Phi)$ 를 설계하여, 수렴성을 보장하면서도 계산 효율성을 높였습니다.
모듈형 알고리즘 설계: 기존 MARL 솔버 (HAPPO, PPO 등) 를 '협력 게임 솔버'와 '최적 반응 솔버' 모듈로 재사용할 수 있도록 설계하여 확장성을 확보했습니다.
이론적 보장: 제안된 목적 함수를 최소화하면 원래 게임의 근사 나시 균형이 도출됨을 이론적으로 증명했습니다.

4. 실험 결과 (Results)

저자들은 NePPO 를 단순한 2 인 게임과 복잡한 Multi-Particle Environment(Simple World Comm) 에서 평가했습니다.

Toy Example (2 인 2 행동 게임):
- NePPO 는 정확한 나시 균형 (보상 1, 1) 을 성공적으로 복원했습니다.
- 반면, MAPPO 는 보상 합을 최대화하는 비균형 전략 (보상 0.5, 1.75 등) 으로 수렴하여 나시 균형에 도달하지 못했습니다.
Simple World Comm (복잡한 환경):
- 환경: 영웅 (영웅) 과 적대자 (Adversary) 가 공존하는 부분 관측 가능 환경. 영웅은 먹이를 모으고 적대자를 피해야 하며, 적대자는 영웅을 잡아야 합니다.
- 비교 대상: MAPPO, IPPO, MADDPG.
- 성능: NePPO 는 최대 후회 (Max Regret) 측면에서 모든 베이스라인을 능가했습니다.
  - MAPPO: 팀 보상 합을 최적화하여 특정 팀의 이익만 극대화하고 다른 팀을 희생시킴.
  - IPPO: 개별 보상을 최적화하여 경쟁에서는 잘하지만 복잡한 조율 (coordination) 에 실패.
  - MADDPG: 이 환경에서 수렴하지 못함.
  - NePPO: 협력과 경쟁을 동시에 고려하여 모든 에이전트의 후회를 최소화하는 균형을 학습함.

5. 의의 (Significance)

이론과 실용의 연결: 일반합 게임의 나시 균형 계산이라는 이론적 난제를, 실제 MARL 알고리즘 (PPO, HAPPO 등) 을 활용할 수 있는 실용적인 파이프라인으로 전환했습니다.
불안정성 해결: 기존 MARL 알고리즘이 겪는 학습 불안정성과 균형 선택의 모호함을 해결할 수 있는 체계적인 프레임워크를 제공합니다.
확장성: 특정 게임 구조에 의존하지 않고, 다양한 이질적인 에이전트와 혼합 동기 환경을 가진 복잡한 시스템에 적용 가능한 가능성을 보여줍니다.

결론적으로, NePPO 는 일반합 다중 에이전트 환경에서 안정적이고 이론적으로 보장된 나시 균형을 학습하기 위한 강력한 새로운 접근법을 제시합니다.