기술 요약: 결합된 동역학을 가진 부분 관측 마르코프 잠재 게임에서 나시 균형의 독립 학습

문제 설정

본 연구는 **부분 관측 마르코프 게임 (POMGs)**에서 나시 균형을 학습하는 과제를 다룹니다. 표준적인 다중 에이전트 강화 학습 (MARL) 에서는 에이전트들이 환경 상태에 완전히 접근할 수 있다고 가정하는 경우가 많습니다. 그러나 자율 주행이나 다중 로봇 제어와 같은 실제 시나리오에서는 에이전트들이 부분 관측 하에 작동하며, 노이즈가 있거나 제한된 관측 정보만 수신합니다.

POMG 에서 나시 균형을 계산하는 일반적인 문제는 계산적으로 처리 불가능합니다. 기존 접근법들은 종종 중앙 집중식 조정이나 정보 공유에 의존하는데, 이는 플레이어 수 ($N$) 에 따라 복잡도가 기하급수적으로 증가하는 "다중 에이전트의 저주"를 초래합니다. 또한, 단일 에이전트 부분 관측 마르코프 결정 과정 (POMDP) 에서조차 최적 정책은 일반적으로 전체 행동 - 관측 이력에 의존하므로, 통계적 및 계산적 복잡도가 기하급수적으로 증가합니다.

저자들은 두 가지 구조적 가정을 특징으로 하는 POMG 의 특정 하위 클래스에 초점을 맞춥니다:

1. 결합된 동역학 (Decoupled Dynamics): 에이전트들은 보상 함수를 통해 결합되어 있지만, 상태 전이 동역학과 관측 커널은 플레이어 간에 독립적입니다. 즉, 에이전트 $i$의 상태 전이는 다른 에이전트들의 상태나 행동이 아닌, 자신의 상태와 행동에만 의존합니다.
2. 마르코프 잠재 구조 (Markov Potential Structure): 근본적으로 완전히 관측 가능한 마르코프 게임 (에이전트들이 실제 상태를 관측할 수 있다면) 은 마르코프 잠재 게임입니다. 이는 정책 변경으로 인한 에이전트의 효용 변화가 전역 잠재 함수의 변화와 일치하는 잠재 함수의 존재를 의미합니다.

목표는 에이전트들이 아무것도 통신하지 않고, 오직 자신의 로컬 이력만 관측하며, 다중 에이전트의 저주를 겪지 않고 근사 나시 균형에 수렴하는 독립 학습 알고리즘을 설계하는 것입니다.

방법론

제안된 접근법은 처리 불가능한 POMG 와 처리 가능한 대리 모델 간의 간극을 다음 단계들을 통해 연결합니다:

1. 슈퍼상태 마르코프 게임 근사

무한한 이력을 유지하지 않고 부분 관측성을 처리하기 위해, 저자들은 **슈퍼상태 마르코프 게임 ($G_m$)**을 사용하여 POMG 를 근사합니다.

• 유한 창 정책 (Finite-Window Policies): 전체 이력에 의존하는 정책 대신, 에이전트들은 최근 $m$개의 행동 - 관측 단계의 유한한 창 ( "슈퍼상태") 에 기반한 정책을 사용합니다.
• 구성: $G_m$의 상태 공간은 이러한 단축된 이력 창으로 구성됩니다. $G_m$의 전이 커널과 보상은 관측된 창과 일치하는 잠재 상태들에 대해 마진화하여 정의되며, 초기 분포와 모델 동역학에서 유도된 belief state 를 활용합니다.
• 필터 안정성 (Filter Stability): 이 근사의 유효성은 필터 안정성 가정에 의존합니다. 이 가정은 사후 belief 에 대한 초기 사전 확률의 영향이 시간의 흐름에 따라 지수적으로 감소한다고 주장합니다 (수축 인자 $\rho$에 의해 제어됨). 이 조건 하에서 유한 창에 기반한 정책은 원래 POMG 에 대한 충분한 근사 보장을 제공합니다.

2. 구조적 속성

저자들은 슈퍼상태 마르코프 게임 $G_m$의 두 가지 중요한 이론적 속성을 확립합니다:

• 균형 보존 (Equilibrium Preservation): $G_m$에서의 $\epsilon$-근사 나시 균형이 원래 POMG 에서 $(\epsilon + \delta)$-근사 나시 균형을 유도함을 증명합니다. 여기서 오차 $\delta$는 창 크기 $m$과 필터 안정성 매개변수 $\rho$에 의존합니다.
• 근사 잠재 구조 (Near-Potential Structure): 근사 오차로 인해 $G_m$이 정확한 잠재 게임은 아니지만, 마르코프 근사 잠재 게임임이 입증되었습니다. 진정한 잠재 구조에서의 편차는 근사 오차에 비례하는 항으로 제한됩니다. 이 구조적 속성은 독립 학습 알고리즘에 대한 수렴 보장을 가능하게 하는 데 결정적입니다.

3. 독립 학습 알고리즘

근사 잠재 구조를 바탕으로, 저자들은 다음과 같이 작동하는 독립 학습 알고리즘 (알고리즘 1) 을 제안합니다:

• 자기 플레이 프로토콜 (Self-Play Protocol): 에이전트들은 $K$번의 반복 (에피소드) 동안 환경과 상호작용합니다. 각 반복에서 에이전트들은 고정된 정책을 따르고, 로컬 행동, 관측, 보상의 궤적을 수집하며, 개별적으로 정책을 업데이트합니다. 에이전트 간에는 정보가 공유되지 않습니다.
• 모델 추정: 에이전트들은 로컬 궤적의 경험적 빈도를 사용하여 슈퍼상태 마르코프 게임 $G_m$의 전이 확률과 보상 함수를 추정합니다.
• 소프트 정책 반복 (Soft Policy Iteration): 에이전트들은 추정된 슈퍼상태 게임에서 소프트 정책 반복 (또는 정규화가 포함된 Q-학습) 을 수행합니다. 그들은 수렴을 보장하는 스텝 사이즈 스케줄을 사용하여 추정된 Q-값을 최대화하도록 정책을 업데이트합니다.

주요 기여

1. 이론적 근사 보장: 본 논문은 필터 안정성 하에서 슈퍼상태 마르코프 게임 $G_m$이 명시적인 오차 한계와 함께 원래 POMG 의 나시 균형을 보존함을 확립합니다. 이는 단일 에이전트 POMDP 근사 결과를 다중 에이전트 설정으로 확장한 것입니다.
2. 근사 잠재 구조: 저자들은 슈퍼상태 마르코프 게임이 결합된 동역학으로부터 근사 잠재 구조를 계승함을 증명합니다. 이를 통해 잠재 게임을 위해 설계된 독립 학습 기법을 부분 관측 설정에 적용할 수 있게 됩니다.
3. 독립 학습 알고리즘: 에이전트들이 로컬 관측만으로 학습하는 통신 없는 알고리즘이 제시됩니다. 이 알고리즘은 유한 창 모델 추정과 소프트 정책 반복을 결합합니다.
4. 복잡도 분석: 주요 이론적 결과 (정리 1) 는 알고리즘이 준다항식 (quasi-polynomial) 샘플 및 계산 복잡도로 $\epsilon$-근사 나시 균형에 수렴함을 증명합니다. 핵심적으로, 이 복잡도는 플레이어 수 $N$에 대해 기하급수적으로 증가하지 않으므로, 이 특정 게임 클래스에 대한 "다중 에이전트의 저주"를 극복합니다.

결과

본 논문은 창 크기 $m$, 에피소드 수 $T$, 반복 횟수 $K$를 적절히 선택할 경우, 결합 정책이 높은 확률 ($1-\delta$) 로 $\epsilon$-근사 나시 균형에 수렴함을 보여주는 엄격한 수렴 분석을 제공합니다.

샘플 복잡도는 다음과 같이 제한됩니다:
$$O\left( \left( \frac{NHAO}{\beta \alpha \epsilon} \right)^{O(\rho^{-1} \log(A/(\beta \epsilon)))} \log(1/\delta) \right)$$
여기서 $A$와 $O$는 행동 및 관측 공간의 최대 크기이고, $H$는 시간 범위 (horizon) 이며, $\alpha, \beta, \rho$는 각각 상태 방문, 관측 노이즈, 필터 안정성과 관련된 매개변수입니다.

핵심적인 결론은 복잡도가 문제 매개변수에 대해 준다항식이며 플레이어 수에 대해 선형 (또는 다항식) 이라는 점으로, 일반적인 POMG 학습이나 중앙 집중식 접근법에서 발견되는 $N$에 대한 기하급수적 의존성을 피합니다.

중요성과 주장

저자들은 이 연구가 부분 관측 마르코프 게임에서 나시 균형을 위한 첫 번째 증명 가능한 독립 학습 방법임을 주장합니다.

• 다중 에이전트의 저주 극복: 결합된 동역학과 잠재 구조를 활용함으로써, 이 방법은 중앙 집중식 또는 정보 공유 접근법 (예: [30]) 이 겪는 플레이어 수에 대한 기하급수적 확장을 피합니다.
• 단일 및 다중 에이전트 이론 간의 연결: 본 연구는 이전에 단일 에이전트 POMDP 에서 성공적이었던 (예: [11, 13]) "필터 안정성" 프레임워크를 다중 에이전트 영역으로 확장하여, 유사한 구조적 가정이 복잡한 다중 에이전트 설정에서 효율적인 학습을 가능하게 함을 보여줍니다.
• 실용적 관련성: 결합된 동역학 가정은 에이전트들이 종종 독립적인 상태 진화를 가지지만 결합된 보상을 가지는 무선 네트워크, 스마트 에너지 그리드, 다중 로봇 시스템과 같은 실제 응용 분야에서 동기화됩니다.
• 겸손함: 저자들은 그들의 결과가 결합된 동역학과 잠재 구조를 가진 POMG 로 제한됨을 인정합니다. 또한 POMG 에서 처리 가능한 영역과 처리 불가능한 영역 사이의 경계를 이해하는 것은 여전히 열린 방향이라고 지적합니다. 추가로, 가정 4 (충분한 상태 방문) 에 대한 의존성은 한계이며, 이를 더 약한 분포 불일치 조건으로 완화하는 것이 향후 과제로 제안됩니다.

요약하자면, 본 논문은 부분 관측 다중 에이전트 시스템의 구체적이지만 실용적으로 관련 있는 클래스에서 확장 가능한 독립 학습을 위한 이론적 기반을 제공하며, 이전 방법들이 보장을 제공하지 못하거나 기하급수적 복잡도에 시달렸던 영역에서 준다항식 보장을 제공합니다.