Minimax-Optimal Policy Regret in Partially Observable Markov Games

기술 요약: 부분 관측 가능한 마르코프 게임에서의 미니맥스 최적 정책 후회(Minimax-Optimal Policy Regret)

문제 정의
본 논문은 부분 관측 가능한 환경에서 전략적이고 적응적인 상대(Adversary)를 상대로 하는 순차적 의사결정 문제, 즉 부분 관측 가능한 마르코프 게임(POMG)을 다룹니다. 핵심 과제는 학습자의 전략에 따라 변화하는 적대적 존재에 맞서면서, 부분적인 관측으로부터 잠재된 세계 역학(World dynamics)을 학습하는 것입니다. 표준적인 외부 후회(External regret) 개념은 이 설정에서 부적절한데, 이는 환경의 반응이 학습자의 과거 행동에 의존하여 반사실적 의존성(Counterfactual dependencies)을 생성하기 때문입니다. 따라서 본 논문은 성능 지표로 **정책 후회(Policy regret)**를 채택합니다. 이는 학습자가 처음부터 특정 정책 $\pi^*$를 고수했을 경우, 적대적이 결국 정적인 반응 $R_\infty(\pi^*)$로 수렴했을 것이라고 가정할 때, 학습자의 누적 보상을 최적의 고정 정책 $\pi^*$와 비교하는 것입니다.

이 설정에는 두 명의 플레이어가 등장합니다: 학습자와 적대자이며, 두 플레이어 모두 부분 관측 하에 작동합니다. 학습자는 신호 $o^A$를 관찰하고, 적대자는 $o^B$를 관찰하며, 잠재 상태(Latent state)는 두 플레이어의 행동에 따라 전이됩니다. 적대자는 **$m$-메모리 제한(m-memory bounded)**을 갖는 것으로 가정되는데, 이는 매 에피소드에서의 적대자의 반응이 가장 최근 $m$개 에피소드 동안의 학습자 정책에만 의존함을 의미합니다.

방법론 및 알고가리즘 프레임워크
저자들은 정책 후회를 최소화하기 위해 에포크 기반 낙관적 최대 우도 추정(Epoch-based optimistic Maximum Likelihood Estimation, MLE) 알고리즘(Algorithm 1)을 제안합니다. 이 방법론은 다음과 같은 몇 가지 핵심적인 구조적 구성 요소에 의존합니다:

1. 인과적 분해(Causal Decomposition): 본 논문의 핵심적인 이론적 기여는 관측 가능한 연산자 $J_{\xi,\pi}^h$를 두 개의 뚜렷한 구성 요소로 분해하는 것입니다:

   • 세계 채널(World channel) $W_h^\theta$: 이는 세계 역학(전이 및 방출 커널)에만 의존하며 적대자의 반응 모델과는 독립적입니다.
   • 적대자 집계(Adversary aggregation) 연산자 $G_{\Phi,\pi}^h$: 이는 적대자의 반응 함수와 학습자의 정책에 의존하지만, 세계 파라미터 $\theta$와는 독립적입니다.
     이러한 인수분해를 통해 알고리즘은 세계 역학의 추정과 적대자 반응의 제어를 분리할 수 있습니다.

2. 구조적 가정:

   • 사후-립시츠 적대자(Posterior-Lipschitz Adversary): 적대자의 반응은 학습자의 정책에 따라 매끄럽게 변화합니다. 결정적으로, 이 매끄러움은 순환적 의존성을 피하기 위해 (적대자의 실제 전략과는 독립적인) 고정된 참조 측도 $\mu_{ref}$에 대해 정의됩니다.
   • 다단계 약한 드러냄(Multi-step Weak Revealing): 관측값은 $\kappa$ 스텝의 윈도우 동안 잠재 상태에 대해 충분한 정보를 제공하여, 세계 역학의 차이를 감지할 수 있도록 합니다.
   • 엘루더 차원(Eluder Dimension): 결합된 세계-적대자 모델 클래스의 복잡도는 균등 집계 엘루더 차원($d_E$)으로 측정됩니다.

3. 에포크 기반 실행: 알고리즘은 시간을 기하급수적으로 증가하는 에포크($T_e = 2^e$)로 나눕니다. 각 에포크 내에서:

   • 단일 정책 $\pi_e$가 과거의 모든 데이터를 통해 누적적으로 구축된 신뢰 집합(Confidence set)으로부터 낙관적으로 선택됩니다.
   • 웜업 단계(Warm-up phase)($m-1$ 에피소드)를 통해 $m$-메모리 적대자가 현재 정책에 대한 정적 반응으로 안정화되도록 합니다.
   • 정책은 $T_e$ 데이터 수집 에피소드 동안 실행됩니다.
     이 구조는 학습자가 $T$ 에피소드 동안 $O(\log T)$개의 구별된 정책만을 배치하도록 보장하며, 이는 서로 다른 정책 간의 적대자 반응을 비교하는 비용을 제어하는 데 매우 중요합니다.

주요 결과
본 논문은 정책 후회에 대한 미니맥스 최적 상한(Upper bound)과 그에 부합하는 하한(Lower bound)을 확립합니다.

• 상한(Upper Bound): 명시된 가정 하에, 알고리즘은 다음과 같은 정책 후회를 달성합니다:
  $$PR(T) \leq C \left( H \sqrt{\bar{\beta}_T \cdot d_E \cdot T} + mH \log T \right)$$
  여기서 $\bar{\beta}_T = H\beta_T + H^2 \log T$입니다. $H^2 \log T$ 항은 $O(\log T)$개의 서로 다른 정책에 걸쳐 적대자 반응을 비교하는 데 드는 "운송 비용(Transport cost)"을 나타냅니다. $\sqrt{T}$ 의존성은 기하학적 에포크 구조를 통해 달성됩니다. 만약 플랫 배칭(Flat batching)처럼 $O(\sqrt{T})$개의 정책을 배치한다면, 운송 비용의 누적으로 인해 $T^{3/4}$의 후회율을 갖게 될 것입니다.

• 하한(Lower Bound): 저자들은 메모리가 없는 적대자를 가진 완전 드러냄(Fully revealing) POMG에서도 작동하는 알고리즘에 대해 $\Omega(\sqrt{d_E T})$의 하한을 증명합니다. 이는 상한에서의 $\sqrt{T}$ 및 $d_E$ 의존성이 문제 의존적 요소 및 로그 인자를 제외하면 최적임을 확인해 줍니다.

• 확장(Extensions): 프레임워크는 다음을 처리하도록 확장되었습니다:

  • 알려지지 않은 호라이즌(Unknown Horizons): 알고리즘은 수정 없이 알려지지 않은 $T$에 적응합니다.
  • 페이딩 메모리 적대자(Fading Memory Adversaries): 결과는 기하급수적으로 감소하는 메모리를 가진 적대자에게도 유효하며, 웜업 비용은 $O(\frac{H \log^2 T}{1-\gamma})$로 스케일링됩니다.
  • 테이블 방식(Tabular Settings): 상태, 행동, 관측 공간의 크기에 따른 명시적인 경계가 도출되었습니다.

의의 및 주장
본 논문은 적응형 적대자를 상대로 하는 POMG에서의 정책 후회 최소화에 대한 완전한 이론적 처리를 제공한다고 주장합니다. 주요 의의는 적대자의 반응이 매끄럽고(Posterior-Lipschitz) 관측이 약하게 드러나는(Weakly revealing) 경우, 이 복잡한 설정에서도 효율적인 학습($\sqrt{T}$ 후회)이 가능하다는 것을 입증한 데 있습니다.

저자들은 이 결과를 가능하게 한 두 가지 구체적인 기술적 혁신을 강조합니다:

1. 비순환적 정식화(Non-circular Formulation): 사후-립시츠 조건을 고정된 참조 측도에 대해 정의함으로써, 적대자가 제약받는 것에 따라 매끄러움 지표가 의존하게 되는 기존 정식화의 순환성 문제를 피했습니다.
2. 로그 운송 비용(Logarithmic Transport Cost): 에포크 기반 구조를 통해 학습자가 $O(\log T)$개의 구별된 정책을 사용하도록 제한함으로써, 적대자 반응 오차의 운송 비용이 로그 수준으로 유지되도록 하여 최적의 $\sqrt{T}$ 비율을 보존했습니다. 이는 저자들이 주장하기에, 운송 비용의 다항식적 증가로 인해 $T^{3/4}$의 하위 최적(Suboptimal) 비율을 초래하는 플랫 배칭 접근 방식과 대조됩니다.

본 연구는 에이전트가 부분적으로 관측 가능하고 전략적으로 적응하는 다중 에이전트 환경에서 신뢰할 수 있는 성능 보장을 가진 학습 알고리즘을 설계하기 위한 기초적인 단계로 제시됩니다. 저자들은 통계적 보장은 확립되었으나, 일반적인 모델 클래스에 대한 낙관적 계획 단계의 계산적 트랙터빌리티(Computational tractability)는 향후 연구 과제로 남아 있다고 언급했습니다.