기술 요약: 다중 소스를 통한 순차적 의사결정 학습: 그룹 강건 마르코프 결정 과정(Group-Robust MDP)을 중심으로

문제 정의

본 논문은 공통된 애플리케이션 컨텍스트를 공유하면서도 이질성(heterogeneity)을 보이는 여러 사이트(예: 병원)에서 수집된 오프라인 데이터셋으로부터 강건한 순차적 의사결정 정책을 학습하는 문제를 다룹니다. 표준적인 오프라인 강화학습(RL)에서는 추가적인 환경 상호작용 없이 사전 수집된 데이터로부터 정책을 학습합니다. 그러나 실제 세계의 다중 사이트 데이터는 다음과 같은 두 가지 결정적인 문제에 직면합니다:

1. 분포 변화(Distributional Shift): 오프라인 궤적은 최적 정책의 상태-행동 분포를 충분히 커버하지 못할 수 있는 행동 정책(behavior policies)에 의해 생성됩니다.
2. 사이트별 이질성(Site-wise Heterogeneity): 데이터 수집 프로토콜, 인구 구성, 환경 조건의 변동성으로 인해 궤적이 단일하고 고정된 마르코프 결정 과정(MDP)으로부터 생성되지 않습니다. 즉, 각 사이트 $k$는 고유한 전이 커널 $P_k$와 보상 함수 $r_k$를 가집니다.

저자들은 이 설정을 **그룹 선형 분포 강건 MDP(Group-Linear Distributionally Robust MDP)**로 모델링합니다. 기본 가정은 모든 사이트가 공통된 알려진 특징 맵(feature map) $\phi: \mathcal{S} \times \mathcal{A} \to \mathbb{R}^d$를 공유하지만, 전이 커널과 보상은 사이트별 파라미터 $(\theta^k_h, \mu^k_h)$를 갖는 이러한 특징들에 대해 선형적이라는 것입니다. 목표는 사이트별 분포의 볼록 헐(convex hull)로 정의된 타당한 불확실성 집합 내에서 최악의 환경 변화에 대해서도 잘 작동하는 정책을 학습하는 것입니다.

방법론

1. 특징별($d$-rectangular) 불확실성 집합

여러 사이트로 인한 불확실성을 처리하면서 계산 가능성을 유지하기 위해, 저자들은 특징별($d$-rectangular) 불확실성 집합을 제안합니다.

• 구조: 모든 특징에 걸쳐 불확실성을 결합하여 비직사각형 집합과 NP-난해한 계획(planning) 문제를 야기하는 표준적인 교차 사이트 볼록 헐과 달리, 이 접근 방식은 각 특징 차원 $i \in [d]$에 대해 독립적으로 믹싱 가중치(mixing weights)를 선택할 수 있게 합니다.
• 정의: 각 단계 $h$와 특징 $i$에 대해, 적대적 주체(adversary)는 사이트별 파라미터의 최악의 혼합을 형성하기 위해 믹싱 벡터 $\alpha_{h,i} \in \Delta^{K-1}$를 선택합니다. 불확실성 집합 $\mathcal{U}_h$는 보상과 전이가 이러한 특징별 혼합에 의해 가중치가 부여된 사이트 파라미터들의 선형 결합이 되도록 정의됩니다.
• 이점: 이러한 완화 방식은 핵심적인 교차 사이트 이질성을 보존하면서도 **강건 벨만 재귀(robust Bellman recursions)**를 복구하여 문제를 계산 가능하게 만듭니다.

2. 비관적 가치 반복 알고리즘(Pessimistic Value Iteration Algorithm)

저자들은 세 가지 핵심 구성 요소를 포함하는 비관적 가치 반복 기반의 오프라인 알고리즘(Algorithm 1)을 개발했습니다:

1. 사이트별 리지 회귀(Per-Site Ridge Regression): 각 사이트 $k$에 대해, 알고리즘은 로컬 데이터셋 $D_k$에 대한 리지 회귀를 사용하여 벨만 타겟 계수 $\hat{\nu}^k_h$를 추정합니다. 이를 통해 선형 파라미터에 대한 사이트별 추정치를 얻습니다.
2. 특징별 최악 사례 집계(Feature-wise Worst-Case Aggregation): 단순히 평균을 내는 대신, 알고리즘은 모든 사이트의 추정된 계수에 대해 **행 단위 최소값(row-wise minimum)**을 수행합니다. 구체적으로, 각 특징 차원 $i$에 대해 강건한 계수는 $\min_{k \in [K]} (\hat{\nu}^k_h)_i$로 설정됩니다. 이는 각 특징에 대해 사이트 간 최악의 시나리오를 포착합니다.
3. 데이터 의존적 비관적 페널티(Data-Dependent Pessimism Penalty): 추정 불확실성과 분포 변화를 고려하기 위해, Q-값에서 페널티 항을 뺍니다. 이 페널티는 리지 회귀에서 얻은 역설계 행렬(공분산 행렬)의 대각 성분을 사용하여 계산됩니다. 이 페널티는 특징 벡터 $\phi(s, a)$와 각 특징 차원에 대해 관찰된 최대 불확실성에 따라 스케일링됩니다.

3. 클러스터 수준 확장(Cluster-Level Extension)

사이트들이 유사성을 보일 때 샘플 효율성을 높이기 위해, 저자들은 클러스터 수준의 확장을 제안합니다. 사이트들은 유사성에 대한 사전 지식을 바탕으로 클러스터로 분할됩니다. 각 클러스터 내에서는 데이터가 "슈퍼 사이트"를 형성하기 위해 통합되며, 강건 벨만 연산자는 클러스터 수준의 대표값에 적용됩니다. 이 접근 방식은 클러스터 내 이질성에 의해 발생하는 오차를 제한하면서 더 큰 통합 샘플 크기를 활용합니다.

이론적 결과

본 논문은 강건한 부분 커버리지 가정(robust partial coverage assumption) 하에서 제안된 알고리즘에 대한 유한 샘플 부최적성 경계(finite-sample suboptimality bounds)를 제공합니다.

• 부최적성 분해: 부최적성은 허위 상관관계(spurious correlation), 내재적 불확실성, 그리고 최적화 오차로 분해됩니다.
• 수렴 속도: 사이트별 경험적 공분산 행렬이 강건 최적 정책의 방문 분포의 2차 모멘트를 지배한다는 가정하에, 학습된 정책 $\hat{\pi}$의 부최적성은 다음과 같이 제한됩니다:
  $$\text{SubOpt}(\hat{\pi}; s) \leq O\left( d^2 H^2 \sqrt{\frac{\log(d K H N_{\max}/\xi)}{N_{\min}}} \right)$$
  여기서 $N_{\min}$은 사이트 간 최소 샘플 크기, $d$는 특징 차원, $H$는 호라이즌, $K$는 사이트 수입니다.
• 클러스터 수준 경계: 클러스터 수준 알고리즘의 경우, 경계에는 클러스터 내 파라미터 불일치($\Delta_h$)에 비례하는 추가적인 편향(bias) 항이 포함되며, 이는 클러스터 내 이질성이 통제되는 한 풀링(pooling)이 유익함을 입증합니다.

실험 결과

저자들은 $K=3$ 또는 $4$인 에피소드 선형 MDP 시뮬레이션을 통해 제안된 방식을 검증했습니다.

• 비교 대상: 제안된 "Sitewise" 알고리즘을 다음 벤치마크들과 비교했습니다:
  • 단순 풀링(Naive Pooling): 모든 데이터를 통합하고 표준 비관적 가치 반복(PEVI)을 적용함.
  • 사이트별 PEVI (Average-Q): 독립적인 사이트별 PEVI 실행으로부터 얻은 Q-함수를 평균함.
  • 사이트별 PEVI (Min-Q): 사이트별 Q-함수의 점별 최소값(pointwise minimum)을 취함.
• 성능: 제안된 알고리즘은 모든 벤치마크에 비해 일관되게 현저히 낮은 강건 부최적성을 달 기록했습니다.
  • 단순 풀링은 사이트별 분포 변화에 강건하지 못하며, 최악의 경우가 아닌 평균 성능을 최적화하려 합니다.
  • 사이트별 방식은 제한된 로컬 샘플 크기와 정보 공유의 부재로 인해 높은 분산을 겪습니다.
• 수렴: 경험적 스케일링 법칙은 이론적인 $O(N_{\min}^{-1/2})$ 수렴 속도를 확인시켜 줍니다.
• 비관주의의 필요성: 비관적 페널티를 제거하면(스케일링 상수 $c=0$으로 설정) 효율적인 수렴에 실패함을 실험적으로 보여주었습니다. 이는 그리디 추정기가 특히 불균형한 데이터 커버리지 시나리오에서 유한 샘플 노이즈에 과적합되기 때문입니다.

의의 및 주장

본 논문은 강력한 상태-행동 직사각형성(state-action rectangularity) 가정에 의존하지 않고, 다중 사이트 오프라인 RL 환경에서 강건한 계획을 위한 원칙적인 접근 방식을 제공한다고 주장합니다.

• 계산 가능성 vs 강건성: $d$-직사각형 불확실성 집합을 도입함으로써, 저자들은 일반적인 교차 사이트 볼록 헐의 계산 불가능성과 표준 $(s, a)$-직사각형 강건 MDP의 과도한 보수성 사이의 간극을 메웁니다.
• 개인정보 보호 및 효율성: 알고리즘은 원시 궤적 대신 통합된 사이트 수준의 요약 통계(리지 회귀 계수 및 공분산 대각 성분)만을 전달하므로, 데이터 통신 비용을 줄이고 개인정보 보호를 강화합니다.
• 이질성 처리: 이 프레임워크는 사이트 간의 이질성을 명시적으로 모델링하고 활용하여, 학습된 정책이 최악의 사이트 구성에 대해서도 강건하도록 보장하며, 이는 다중 소스 데이터에 적용되는 표준 오프라인 RL의 근본적인 한계를 해결합니다.

저자들은 자신들의 방법이 사이트 내의 선형 구조에 의존하며, $d$-직사각형 근사가 보수적인 추정치를 초래할 수 있음을 인정합니다. 이들은 향-후 연구에서 더 타이트한 근사법과 비선형 특징 맵을 다루기 위한 표현 학습(representation learning)의 통합을 탐구할 수 있다고 제안합니다.