기술적 요약: 선형 함수 근사를 통한 대규모 상태 공간이 있는 강건한 마르코프 게임에서 다중 에이전트의 저주 극복

1. 문제 정의

본 연구는 대규모 또는 무한한 상태 공간을 가진 환경에서의 분포 강건 다중 에이전트 강화 학습 (Distributionally Robust Multi-Agent Reinforcement Learning, MARL) 과 관련된 과제를 다룹니다. 저자들은 두 가지 중요한 난제를 결합한 강건 선형 마르코프 게임 (Robust Linear Markov Games, R-LMGs) 에 초점을 맞춥니다:

1. 강건성 (Robustness): 에이전트들은 지정된 불확실성 집합 (특히 총변동 거리로 정의됨) 내에서 명목 모델로부터 벗어난 환경에 대해 최악의 경우 성능을 최적화해야 합니다.
2. 확장성 (다중 에이전트의 저주): 표준 MARL 에서 결합 행동 공간은 에이전트 수 ($n$) 에 따라 기하급수적으로 증가하여, 표본 복잡도가 $n$에 대해 기하급수적으로 증가합니다. 이는 상태 공간이 크거나 무한할 때 더욱 악화되어 표본 기반 (tabular) 방법론을 실행 불가능하게 만듭니다.

강건한 마르코프 게임 (RMGs) 을 위한 기존에 증명된 효율적인 알고리즘들은 표본 기반 설정 (유한한 상태/행동 공간) 으로 제한되어 있으며, RMGs 에 대한 선형 함수 근사 (LFA) 의 유일한 선행 연구는 제한적인 가정 (소멸하는 최소 가치) 에 의존하면서도 여전히 다중 에이전트의 저주에 시달리고 있습니다. 이에 본 논문은 다음과 같은 질문을 던집니다: 대규모 상태 공간이 있는 강건한 마르코프 게임에서 다중 에이전트의 저주를 극복할 수 있는가?

2. 방법론

본 논문은 생성 모델 (Generative Model) 설정과 새로 제안된 온라인 상호작용 (Online Interactive) 설정이라는 두 가지 서로 다른 데이터 수집 메커니즘 하에서 R-LMG 를 위한 증명 가능한 데이터 효율적 알고리즘을 제안합니다. 두 설정 모두 각 에이전트별 독립 선형 함수 근사 (Independent Per-Agent Linear Function Approximation, LFA) 를 활용하는데, 여기서 각 에이전트의 전이 및 보상 함수는 다른 에이전트의 행동과 무관한 특징 벡터 $\phi(s, a_i)$의 선형 함수로 모델링됩니다.

2.1 생성 모델 설정

이 설정에서 알고리즘은 임의의 상태 - 행동 쌍에 대해 명목 전이 커널 $P^0$에서 샘플을 생성할 수 있는 시뮬레이터에 접근할 수 있습니다.

• 알고리즘: L-Robust-Q-FTRL.
• 주요 혁신 (무한에서 유한으로의 축소): 포괄적인 샘플링이 필요한 표본 기반 방법과 달리, 저자들은 특징 공간의 기하학에 기반한 보조 Lemma 1 에서 유도된 분포 $\rho_i$를 사용하여 상태 - 행동 쌍의 유한 지지 집합 ($Y_i$) 을 구성합니다. 이를 통해 Ridge 회귀를 통해 전체 (잠재적으로 무한한) 상태 공간을 보장하면서 $O(d^2)$ 크기의 유한 부분집합에서만 샘플링할 수 있습니다.
• 메커니즘: 알고리즘은 역방향 재귀를 수행합니다. 각 반복에서 구성된 유한 집합에서 샘플링하고, Ridge 회귀를 통해 명목 모델 (보상 및 전이) 을 추정하며, 강건한 벨만 방정식의 쌍대 형태를 사용하여 강건 Q-함수를 업데이트합니다. 정책 업데이트에는 Follow-the-Regularized-Leader (FTRL) 전략을 사용합니다.

2.2 온라인 상호작용 설정

이 설정은 에이전트들이 환경을 상호작용하여 궤적을 수집하는 더 실용적인 환경입니다. 주요 과제는 실제 최악의 경우 전이 커널이 알려져 있지 않으며, 불확실성 집합 커널이 명목 커널에 대해 가정된 선형 구조를 반드시 만족하지는 않는다는 점입니다.

• 알고리즘: Online-L-Robust-Q-FTRL.
• 주요 혁신 (하이브리드 샘플링 및 비관적 추정):
  • 적대자 근사: 실제 최악의 경우 커널이 알려져 있지 않으므로, 알고리즘은 직접 샘플링할 수 없습니다. 대신 비관적 강건 가치 추정치 (pessimistic robust value estimates) 의 시퀀스를 도입합니다. 이러한 추정치는 불확실성 집합 내의 "근사적 적대 환경 (approximate adversarial environment)" (정의 1) 을 쿼리하는 데 사용됩니다.
  • 하이브리드 샘플링 전략: 선형 모델 추정 (명목 커널에만 적용됨) 의 유효성을 유지하기 위해, 알고리즘은 하이브리드 샘플링 방식을 사용합니다. 궤적의 처음 $h-1$단계에서는 에이전트들이 근사적 적대 환경 (비관적 추정치를 사용) 과 상호작용합니다. 마지막 단계 $h$에서는 명목 커널로부터 샘플링으로 전환합니다. 이는 $h-1$ 단계까지 최악의 경우 동역학에 의해 유도된 상태 - 행동 점유 분포를 유지하면서, 최종 전이 데이터가 선형적으로 근사 가능한 명목 모델에서 오도록 보장합니다.
  • 쌍대 추정치: 알고리즘은 정책 업데이트를 위한 낙관적 (optimistic) 가치 추정치와 적대적 샘플링을 안내하기 위한 비관적 (pessimistic) 가치 추정치를 모두 유지합니다. 이는 일반적으로 낙관성에만 의존하는 표준 선형 MG 들과 구별되는 점입니다.

3. 주요 기여

1. 대규모 상태 공간에서 다중 에이전트의 저주 극복: 본 논문은 다중 에이전트의 저주를 극복하는 대규모 (잠재적으로 무한한) 상태 공간을 가진 R-LMG 를 위한 첫 번째 증명 가능한 표본 효율적 알고리즘을 제공합니다. 표본 복잡도와 후회 (regret) 한계는 결합 행동 공간 $\prod A_i$가 아닌 특징 차원 $d$와 최대 개별 행동 공간 크기 $\max_i A_i$에 대해 다항식적으로 의존합니다.
2. 생성 모델 보장: 생성 모델 설정 하에서 제안된 알고리즘은 $\epsilon$-근사 coarse correlated equilibrium (CCE) 을 $\tilde{O}(H^9 d^3 / \epsilon^4)$의 표본 복잡도로 달성합니다. 이는 불확실성 집합 공식과 무관하게 생성 모델 하의 R-LMG 에 대한 최초의 그러한 보장입니다.
3. 온라인 상호작용 프로토콜: 저자들은 불확실성 집합 내의 전이 커널 (근사적 적대 환경) 에서 샘플링할 수 있는 실질적으로 의미 있는 온라인 프로토콜을 제안합니다. 그들은 알고리즘이 $\tilde{O}(H^2 d \max_i A_i \sqrt{T})$의 부분 선형 후회를 달성함을 증명합니다.
4. 기술적 신규성:
   • 무한에서 유한으로의 축소: 강건 설정에서 무한 상태 공간으로 일반화하기 위해 유한 부분집합을 샘플링하는 방법.
   • 하이브리드 샘플링: 불확실성 집합의 비선형성을 극복하면서 적대 환경의 점유 분포를 유지하는 명목 모델을 추정하기 위한 새로운 메커니즘.
   • 비관적 - 낙관적 쌍대성: 실제 강건 가치가 부재할 때 적대 환경을 근사하기 위해 비관적 가치 추정치를 도입한 것.

4. 결과 및 이론적 보장

• 생성 모델 (정리 2): 알고리즘은 $N_{all} \ge O(H^9 d^3 / \epsilon^4)$개의 샘플을 사용하여 확률 $1-\delta$로 $\epsilon$-강건 CCE 를 출력합니다. 표본 기반 축소 ($d = S \max A_i$) 에서 이는 $\tilde{O}(H^9 S^3 (\max A_i)^3 / \epsilon^4)$의 복잡도를 산출하며, 이는 모든 매개변수에 대해 다항식적이어서 기존 표본 기반 강건 방법들의 지수적 의존성과 대조됩니다.
• 온라인 설정 (정리 3): 알고리즘은 $\tilde{O}(H^2 d \max_i A_i \sqrt{T})$의 후회 한계를 달성합니다. 에피소드 수 $T$가 $T > H^4 d^2 (\max_i A_i)^2 / \epsilon^2$를 만족하면, 출력은 $\epsilon$-강건 CCE 가 됩니다.
• 비교: 결과는 선형 RMGs 에 대한 유일한 기존 연구 (Zheng and Lin, 2025) 보다 크게 개선되었습니다. 해당 연구는 제한적인 "소멸하는 최소 가치" 가정을 요구했고 다중 에이전트의 저주 ($d_{curse} = S \prod A_i$) 에 시달렸습니다. 제안된 방법은 이러한 제한을 제거하고 에이전트 수에 대한 다항식 의존성을 달성합니다.

5. 중요성 및 주장

저자들은 본 연구가 다중 에이전트의 저주를 성공적으로 극복하는 대규모 (잠재적으로 무한한) 상태 공간을 가진 강건한 선형 마르코프 게임을 위한 첫 번째 증명 가능한 표본 효율적 알고리즘을 제공한다고 주장합니다.

• 강건성: 이 연구는 강건 MARL 의 범위를 작고 표본 기반인 도메인에서 자율 주행, 로봇 공학, 금융 시장과 같은 실제 응용 분야에 관련된 대규모 연속 환경으로 확장합니다.
• 데이터 효율성: 에이전트 수에 대한 지수적 의존성을 깨뜨림으로써, 결합 행동 공간이 본래 처리 불가능할 수 있는 다중 에이전트 시스템에서 강건한 학습을 실현 가능하게 합니다.
• 실용성: 근사적 적대 환경에서 샘플링을 허용하는 제안된 온라인 상호작용 설정은 안전-중요 응용 분야 (예: 시뮬레이션 - 현실 전이, 적대적 학습) 에서 사용되는 실용적 패러다임과 부합하며, 부분 선형 후회를 달성하기 위해 문제를 잘 정의된 상태로 유지합니다.

본 논문은 제안된 하이브리드 샘플링 전략과 비관적 가치 추정치의 사용이 강건 강화 학습 분야의 향후 연구에 독립적인 관심을 가질 수 있는 핵심 기술적 기여라고 결론지었습니다.