기술 요약: 인과 매개 분석을 위한 고정 신뢰도 최적 팔 식별 (Fixed-Confidence Best-Arm Identification)

1. 문제 정의

본 논문은 인과 밴딧(causal bandit) 설정, 특히 **인과 매개 분석(causal mediation analysis)**에 초점을 맞춘 최적 팔 식별(Best-Arm Identification, BAI) 문제를 다룹니다.

• 맥락: 표준 인과 밴딧에서 목표는 일반적으로 모든 인과 경로를 통합하는 개입 평균 $E[Y | do(X=x)]$를 최대화하는 것입니다. 그러나 연구자들은 특정 매개체$Z$를 통하지 않는(예: 비윤리적인 메커니즘, 광고의 포지셔닝 편향, 또는 부작 most한 중간 반응을 배제하기 위해) 처치 $X$의 효과를 분리하여 식별하고자 하는 경우가 많습니다.
• 목표: 본 논문은 **기대 자연 직접 잠재 결과(Expected Natural Direct Potential Outcome, NDPO)**를 최대화하는 팔 $x^*$를 식별하는 것을 목표로 합니다. 이 양은 처치가 $x$로 설정되는 동시에 매개체 $Z$가 참조 팔 $x_0$ 하에서 가졌을 값에 머물러 있을 때의 기대 결과를 나타냅니다 ($E[Y_{x, Z_{x_0}}]$).
• 설정: 이 문제는 고정 신뢰도(fixed-confidence) 설정으로 정식화되었습니다. 학습자는 팔(개입 $do(X=x)$)을 순차적으로 선택하며, 개입 분포$P(Z, Y | do(X=x))$로부터 i.i.d. 샘플을 관찰합니다. 목표는 최소한$1-\delta$의 확률로 최적의 팔을 식별하면서 정지 시간(샘플 복잡도)을 최소화하는 것입니다.

2. 방법론

2.1 모집단 수준 식별

저자들은 먼저 기대 NDPO가 인과 밴딧 설정 하에서 관찰 가능한 개입 분포로부터 식별 가능하다는 것을 입증합니다.

• 가정: 저자들은 자연 직접 효과에 대한 표준 식별 가정인 $Y_{x,z} \perp\!\!\perp Z_{x'}$ (모든 $x, x', z$에 대해)에 의존합니다. 그래프 측면에서 이는 $X$와 $Z$로부터 나가는 에지(edge)가 제거된 그래프에서 매개체 $Z$와 결과 $Y$ 사이에 미측정 혼란 변수가 존재하지 않음을 의미합니다.
• 식별 공식: 이 가정하에서 기대 NDPO $\theta(x)$는 다음과 같이 식별됩니다:
  $$\theta(x) = \sum_{y,z} y P(Y=y | Z=z, do(X=x)) P(Z=z | do(X=x_0))$$
  이 공식은 밴딧 설정에서 직접 관찰할 수 없는 중첩된 반사실(nested counterfactuals)을 피하고, 오직 결합 개입 분포 $P(Z, Y | do(X=x))$와$P(Z | do(X=x_0))$만을 사용하여 추정을 가능하게 합니다.

2.2 샘플 복잡도 하한선

논문은 $\delta$-정확한 알고리즘을 위한 인스턴스 의존적 샘플 복잡도 하한선을 도출합니다.

• 표준 BAI와의 주요 차이점: 객체가 해당 팔의 분포에만 의존하는 표준 BAI와 달리, NDPO는 팔 $x$의 결과 분포를 베이스라인 팔 $x_0$의 매개체 분포와 결합(coupling)시킵니다.
• 복잡도 구조: 하한선은 준무한 최적화 문제(semi-infinite optimization problem)를 포함합니다. 특성 시간 $T^*(P)$는 다음과 같이 정의됩니다:
  $$(T^*(P))^{-1} = \sup_{w \in \Sigma_K} \inf_{Q \in \text{Alt}(P)} \sum_{x \in \mathcal{X}} w_x KL(P_x \| Q_x)$$
  여기서 $\text{Alt}(P)$는 다른 팔이 최적이 되는 대안 모델들의 집합입니다. $\text{Alt}(P)$를 정의하는 제약 조건은 **비분리적(non-separable)**인데, 이는 베이스라인 매개체 분포 $Q_{x_0}(Z)$가 모든 팔의 목적 함수에 등장하여, 고전적 BAI에는 존재하지 않는 팔 간의 결합을 생성하기 때문입니다.

2.3 제안 알고리즘: TaS-NDPO

저자들은 이 특정 목적에 적응된 TaS-NDPO(Track-and-Stop) 알고리즘을 제안합니다. 이 알고리즘은 세 가지 주요 구성 요소로 이루어집니다:

1. 플러그인 추정(Plug-in Estimation): 개입 분포의 경험적 추정치를 사용하여 $\theta(x)$의 플러그인 추정치를 계산합니다.
2. 샘플링 규칙 (강제성을 동반한 D-tracking):
   • D-tracking: 알고리즘은 하한선으로부터 도출된 최적 샘플링 비율 $w^*$를 추적합니다.
   • 경쟁자 커버리지(Competitor Coverage): 비분리적 제약 조건을 처리하기 위해, 알고리즘은 모든 팔이 최적화 문제에서 "경쟁자"로서 충분히 자주 선택되도록 보장합니다.
   • 셀 레벨 강제성(Cell-level Forcing): 결정적으로, 알고리즘은 셀 레벨(cell-level) $(x, z)$ (팔과 매개체 값의 조합)에서 탐색을 강제합니다. 이는 KL 발산이 매개체 확률에 의해 가중치가 부여된 항들로 분해되기 때문에 필수적이며, 희소한 매개체 값들을 충분히 샘플링하여 조건부 결과 확률 $P(Y|Z, do(X))$의 일관된 추정을 보장해야 합니다.
3. 정지 규칙 (GLRT): 알고리즘은 GLRT 통계량이 임계값 $\beta(t, \delta)$를 초과할 때 정지합니다. 이 통계량은 현재의 경험적 최적 팔보다 다른 팔이 더 나은 것으로 보이는 모든 대안 모델에 대한 최소 KL 발산을 측정합니다.
4. 최적화 솔버: 샘플링 규칙과 정지 규칙의 내부 최소화를 해결하는 데는 준무한 최적화 문제가 포함됩니다. 저자들은 세 개의 팔(베이스라인, 현재 최적 팔, 경쟁자)로 축소하는 방법과 바이코벡스(bi-convex) 하위 문제를 해결하기 위한 교대 최소화(alternating minimization) 기법을 결합한 커팅 셋 방법(cutting-set method)(Mutapcic and Boyd, 2009)을 사용합니다.

3. 주요 기여

1. 문제 정식화: 본 논문은 매개체를 통한 인과 경로를 배제하면서 직접 효과를 최대화하는 데 유효한 양인 기대 NDPO를 최대화하기 위한 BAI 문제를 공식적으로 정의하고 연구합니다.
2. 밴딧에서의 식별: 인과 밴딧 설정에서 사용 가능한 개입 분포만을 사용하여 기대 NDPO를 식별할 수 있음을 입증함으로써, 인과 추론 이론과 순차적 의사결정론을 연결합니다.
3. 이론적 경계: NDPO 최적화의 독특한 과제(베이스라인 매개체 분포를 통한 팔 간의 결합 및 셀 레벨 정보 축적의 필요성)를 강조하는 새로운 샘플 복잡도 하한선을 도출합니다.
4. 알고리즘 설계: 다음을 수행하는 새로운 알고리즘인 TaS-NDPO를 도입합니다:
   • 최적 샘플링 비율을 해결하기 위해 커팅 셋 방법을 사용합니다.
   • 일관성을 보장하기 위해 셀 레벨 강제성을 포함합니다.
   • $\delta$-정확성(확률 $1-\delta$로 정확성 보장)과 점근적 최적성( $\delta \to 0$일 때 샘플 복잡도 하한선 달성)을 증명합니다.

4. 실험 결과

저자들은 합성 데이터와 대규모 실제 광고 데이터셋(IPinYou) 모두에서 TaS-NDPO를 평가했습니다.

• 실제 데이터 검증 (IPinYou):
  • 데이터셋은 클릭($Y$)을 최대화하기 위해 광고 크리에이티브($X$)를 선택하는 문제를 다루며, 슬롯 가시성($Z$)이 매개체 역할을 합니다.
  • 의사 결정의 괴리(Decision Divergence): 표준 개입 평균을 최대화하는 팔과 NDPO를 최대화하는 팔이 서로 달랐습니다. 표준 평균은 상단 슬롯에 자주 노출되는 크리에이티브(매개 효과)를 선호한 반면, NDPO 최적 팔은 달랐습니다.
  • 성능: TaS-NDPO는 중앙값 정지 시간으로 12,928 샘플을 기록하였으며, 이는 팔 레벨 변형 방식(25,856 샘플)보다 약 50% 더 효율적이었고, 균등 샘플링 및 베이스라인 우선 접근법보다 현저히 우수한 성능을 보였습니다. 모든 방법은 $\delta=0.05$에서 제로 경험적 오류율을 유지했습니다.
• 합성 실험:
  • 갭 스케일링(Gap Scaling): 결과는 하한선에서 예측된 $1/\Delta^2$ 스케일링을 따르는 샘플 복잡도를 확인시켜 주었습니다.
  • 매개체 희소성: 셀 레벨 강제성의 이점은 매개체-결과 셀이 드문 상황(희소한 환경)에서 가장 두드러졌으며, 이 환경에서 팔 레벨 강제성은 충분한 정보를 축적하는 데 실패했습니다.
  • 실행 시간: 커팅 셋 최적화의 계산 오버헤드는 완만했습니다(최대 100k 샘플까지 실행당 평균 22.5초). 이는 샘플 효율성 이득에 비해 병목 현상이 되지 않는 수준입니다.

5. 의의 및 주장

본 논문은 TaS-NDPO가 매개된 경로를 제외하면서 직접적인 인과 효과를 최대화하는 처치를 식별하기 위한 이론적으로 근거 있고 경험적으로 효율적인 솔루션을 제공한다고 주장합니다.

• 이론적 의의: 본 연구는 목적 함수가 베이스라인 매개체를 통해 서로 다른 팔의 분포를 결합하는 경우에도 점근적 최적성 달성이 가능함을 증명함으로써, Track-and-Stop 프레임워크를 인과적 설정(중첩된 반사실 포함)으로 확장했습니다.
• 실무적 의의: 직접 효과를 격리함으로써, 본 방법은 표준 평균 최대화 접근법이 선호할 수 있는 바람직하지 않은 메커니즘(예: 클릭베이트, 부작용, 또는 비윤리적인 포지셔닝)을 피하는 의사결정을 가능하게 합니다.
• 한계점 명시: 저자들은 현재 프레임워크가 이진 결과(binary outcomes)와 특정 인과 그래프 구조(매개체가 처치와 결과 사이에 위치)에 집중하고 있음을 인정합니다. 다범주 결과로의 확장은 간단하지만, 더 넓은 인과 구조에서 경로 특정 효과(path-specific effects)로 일반화하는 것은 향후 연구 과제로 남겨두었습니다. 또한, 식별은 인과 추론의 표준적이지만 테스트 불가능한 가정인 (특히 $Z$와 $Y$ 사이의 미측정 혼란 변수 부재) 인과 그래프의 타당성에 의존한다는 점을 명시합니다.