기술 요약: 평균 보상을 갖는 분포 강건 마르코프 게임 (Distributionally Robust Markov Games with Average Reward)

문제 정의

본 논문은 모델 불확실성과 확장된 운영 지평을 특징으로 하는 환경에서의 다중 에이전트 의사결정 문제를 다룹니다. 마르코프 게임(Markov Games, MG)은 경쟁적인 다중 에이전트 시스템을 위한 프레임워크를 제공하지만, 표준적인 정식화는 가정된 전이 모델이 비정상성(non-stationarity), 모델링 오류 또는 적대적 교란으로 인해 실제 환경과 달라지는 "Sim-to-Real" 간극을 반영하지 못하는 경우가 많습니다.

이를 완화하기 위해, 저자들은 사전 정의된 불확실성 집합 내의 최악의 전이 커널에 대해 최악의 성능을 최적화하는 **분포 강건 마르코프 게임(Distributionally Robust Markov Games, DR-MGs)**을 연구합니다. 결정적으로, 본 연구는 흔히 연구되는 유한 지평(finite-horizon) 또는 할인 보상(discounted-reward) 설정이 아닌 **평균 보상 기준(average-reward criterion)**에 초점을 맞춥니다. 평균 보상 기준은 무기한의 시간 지평 동안 작동하는 시스템(예: 창고 로봇 공학, 통신 네트워크)에 필수적이지만, 다음과 같은 중요한 이론적 난제를 제시합니다:

1. Min-Max 쌍대성(Duality)의 실패: 강건한 설정에서는 한 에이전트를 위한 최악의 전이 커널이 다른 에이전트의 것과 다를 수 있으며, 이는 제로섬 게임에서도 사들점(saddle-point) 구조를 깨뜨립니다.
2. 구조적 복잡성: 할인 설정과 달리, 평균 보상 설정에서는 제한적인 구조적 가정이 없다면 정적 정책(stationary policy)과 상태-행동 빈도(state-action frequency) 사이의 대응 관계가 무너집니다.
3. 기존 솔루션의 부재: 기존의 할인된 DR-MG 또는 비강건 평균 보상 MG를 위한 방법론은 벨만 연산자의 수축성(non-contraction) 결여와 해의 비유일성 때문에 평균 보상 강건 설정으로 직접 확장될 수 없습니다.

본 논문은 구조적 가정이 없다면 평균 보상 DR-MG가 정적 내쉬 균형(Nash Equilibrium, NE)을 갖지 않을 수 있음을, 구성된 2인 제로섬 게임의 반례를 통해 보여줍니다.

방법론

1. 이론적 기초: 균형의 존재성

저자들은 두 가지 뚜렷한 구조적 가정 하에서 정적 강건 내쉬 균형의 존재성을 입증합니다.

• 기약성(Irreducible) 설정: 임의의 정적 결합 정책과 임의의 허용 가능한 커널에 대해 유도된 마르코프 체인이 기약적(모든 상태가 단일 재귀 클래스에 속함)이라고 가정합니다.

  • 저자들은 최적 정책과 **강건 벨만 방정식(robust Bellman equation)**의 해 사이의 대응 관계를 도출합니다.
  • 강건 벨만 방정식이 이득(gain)과 편향(bias)에 대해 (상수 벡터를 제외하고) 유일한 해를 가짐을 증명합니다.
  • 이러한 결과들을 사용하여 최적 대응 매핑(best-response mapping)이 비어 있지 않고, 볼록하며, 상반연속(upper semi-continuous)임을 보입니다. 카쿠타니 고정점 정리(Kakutani fixed-point theorem)를 적용하여 정적 강건 NE의 존재를 증명합니다.

• 약한 통신(Weakly Communicating) 설정: 상태 공간이 일시적 상태(transient states)와 재귀 클래스의 합집합으로 분해될 수 있는 더 일반적인 설정입니다.

  • 이 설정에서는 정책과 벨만 해 사이의 직접적인 대응 관계가 실패합니다.
    서로 다른 두 가지 방식의 접근을 통해 이를 해결합니다.
  • 저자들은 상수 이득 최적 강건 벨만 연산자를 기반으로 한 **프록시 집합값 맵(proxy set-valued map)**을 구축합니다.
  • 이 프록시 맵이 실제 최적 대응 매핑의 부분집합이며 카쿠타니 고정점 정리의 조건을 만족함을 증명함으로써, 더 넓은 맥락에서도 정적 강건 NE의 존재를 입증합니다.

2. 알고리즘 솔루션

본 논문은 강건 NE를 계산하기 위한 두 가지 알고로리즘을 제안합니다.

• 강건 내쉬 반복법(Robust Nash-Iteration): 표준 내쉬 반복법의 확장입니다. 이는 편향 추정치를 유지하며 각 단계에서 강건한 Q-값에 의해 정의된 스테이지 게임의 내쉬 균형을 위해 문제를 풉니다.

  • 수렴성: 기약성 가정과 스테이지 게임의 균형 선택(예: 전역 최적성 또는 사들점 선택)에 관한 추가 가정이 있을 때 강건 NE로 수렴함을 증명합니다.
  • 한계: 일반적으로 일반-합(general-sum) 설정에서 PPAD-완전(PPAD-complete)인 스테이지 게임의 NE를 계산하기 위한 오라클(oracle)이 필요합니다.

• 강건 TD 경사 하강법(Robust TD Descent): NE 오라클의 필요성을 우회하기 위해 설계된 2-타임스케일 액터-크리틱(actor-critic) 알고리즘입니다.

  • 메커니즘: 이는 전역 강건 템포럴 차이(TD) 갭의 최소화를 통해 강건 NE를 특징짓습니다. 알고-리즘은 비매끄러움(non-smoothness)을 처리하기 위해 모로 포락선(Moreau envelope)을 사용하여 이 갭의 평활화된 버전을 최소화합니다.
  • 수렴성: 이 알고리즘은 평활화된 목적 함수의 정적 점(stationary point)으로 약하게 수렴함이 증명되었습니다. 국소 그래디언트 지배(local gradient domination)와 같은 추가 가정이 없다면 정확한 NE로의 수렴을 보장하지는 않지만, NE 오라클에 의존하지 않고 평균 보상 DR-MG를 위해 증명 가능한 수렴성을 제공하는 최초의 방법입니다.

3. 할인된 균형과의 연결

저자들은 평균 보상과 할인된 DR-MG 사이의 이론적 가교를 구축합니다. 할인 계수 $\gamma \to 1$로 갈 때, 할인된 게임의 강건 NE가 평균 보상 게임의 강건 NE로 수렴함을 증명합니다. 이를 통해 더 다루기 쉬운 할인된 정식화를 사용하여 까다로운 평균 보상 문제를 근사할 수 있습니다.

주요 결과

1. NE의 존재성: 본 논문은 기약성 및 약한 통신 가정 하에서 평균 보상 DR-MG의 정적 강건 내쉬 균형 존재성을 증명하여, 기존 문헌에서 미결로 남아 있던 근본적인 해결 가능성 문제를 해결했습니다.
2. 강건 벨만 방정식의 해결 가능성: 저자들은 평균 보상 MDP를 위한 강건 벨만 방정식의 해결 가능성과 유일성(상수 제외)에 대한 기초적인 결과를 제공하여, 기존 문헌의 공백을 메웠습니다.
3. 수렴 알고리즘: 두 가지 알고리즘이 도입되었습니다. 강건 내쉬 반복법은 특정 구조적 가정 하에서 수렴성을 제공하며, 강건 TD 경사 하강법은 오라클이 필요 없는 실용적인 접근법으로서 정적 점으로의 수렴성을 제공합니다.
4. 할인을 통한 근사: 평균 보상 균형이 충분히 큰 할인 계수를 가진 할인된 균형에 의해 효과적으로 근사될 수 있음을 검증하여, 실용적인 계산 경로를 제시했습니다.

의의 및 주장

본 논문은 복잡하고 불확실하며 장기적으로 실행되는 다중 플레이어 환경에서의 의사결정을 위한 포괄적인 이론적 및 알고리즘적 토대를 제공한다고 주장합니다. 구체적으로:

• 표준적인 기법들이 실패하는 평균 보상 다중 에이전트 설정에서 강건한 균형이 존재하는지에 대한 근본적인 질문을 해결합니다.
• 할인된 또는 유한 지평 근사를 넘어, 평균 보상 DR-MG를 해결하기 위해 증명 가능한 수렴성을 가진 최초의 알고리즘들을 도입합니다.
• 정적 균형의 존재를 위해 구조적 가정(기약성 또는 약한 통신)이 필수적임을 강조하며, 반례를 통해 이러한 가정이 단순한 기술적 요구가 아니라 필수적임을 보여줍니다.

저자들은 본 프레임워크가 강력한 토대를 제공하지만, 일반-합 게임에서 정확한 균형을 찾는 것은 여전히 도전적인 과제이며, TD 기반 알고리즘은 정확한 강건 NE를 찾기 위한 필수적인 첫 단계인 정적 점으로 수렴한다는 점을 언급합니다. 향-후 연구로는 더 강력한 수렴 보장을 위한 국소 그래디언트 지배 탐색과 $(s, a)$-직사각형 불확실성 집합을 넘어선 프레임워크 확장이 제안됩니다.