Causal Bandit Over Unknown Graphs: Upper Confidence Bounds With Backdoor Adjustment

1. 연구 배경 및 문제 정의 (Problem Definition)

• 인과 밴딧 (Causal Bandit) 문제: 다중 암 밴딧 (MAB) 문제의 확장으로, 각 행동 (Arm) 이 시스템 내 변수에 대한 개입 (Intervention, $do(X_i=x_i)$) 에 해당하고, 보상은 인과적 메커니즘을 통해 결정되는 문제입니다. 목표는 누적 후회 (Cumulative Regret) 를 최소화하면서 최적의 개입을 찾는 것입니다.
• 기존 방법의 한계:
  • 대부분의 기존 연구는 인과 그래프 (DAG) 가 완전히 알려져 있거나 특정 구조적 가정을 전제로 합니다.
  • 실제 응용에서는 인과 관계가 불명확한 경우가 많으며, 그래프를 먼저 학습한 후 밴딧을 수행하는 방식은 계산 비용이 크거나 불필요한 정보를 학습할 수 있습니다.
  • 특히 가우시안 (연속형) 변수의 경우, 최적의 개입이 반드시 보상 변수의 부모 (Parent) 노드가 아닐 수 있어, 부모 노드만 탐색하는 기존 방법 (예: CN-UCB) 이 실패할 수 있습니다.
• 핵심 문제: 인과 그래프 구조를 알지 못하면서도, 관측 데이터 (Observational Data) 와 실험 데이터 (Experimental Data) 를 효율적으로 통합하여 최적의 개입을 찾는 알고리즘을 개발하는 것입니다.

2. 제안 방법론: BA-UCB 알고리즘 (Methodology)

저자들은 백도어 조정 상한 신뢰구간 (Backdoor-Adjustment Upper Confidence Bound, BA-UCB) 알고리즘을 제안합니다. 이 알고리즘은 그래프 구조를 사전에 알지 못하더라도 관측 데이터와 실험 데이터를 결합하여 인과 효과를 추정합니다.

2.1. 핵심 아이디어

1. 백도어 조정 (Backdoor Adjustment) 활용:
   • 가우시안 DAG 모델에서 변수 $X_i$가 보상 $Y$에 미치는 인과 효과 $\gamma_i$는 적절한 조정 집합 $S$ (Backdoor Adjustment Set) 를 통해 회귀 계수로 식별 가능합니다 ($\gamma_i = \beta_i(Y \sim X_i + X_S)$).
   • 알고리즘은 그래프를 완전히 복원하는 대신, 각 암 (Arm) 에 대해 후보 조정 집합 (Candidate Adjustment Sets) 을 데이터 기반으로 동적으로 식별합니다.
2. 데이터 통합 추정:
   • 실험 데이터: 개입 하에 수집된 데이터로 직접적인 평균 추정 ($\hat{\mu}_{i, int}$).
   • 관측 데이터: 개입 없이 수집된 데이터로 백도어 조정을 통해 추정 ($\hat{\mu}_{i, obs}$).
   • 가중 평균 (Weighted Average): 두 추정을 가중 평균하여 더 정밀한 상한 신뢰구간 (UCB) 을 구성합니다. 이는 관측 데이터가 실험 데이터보다 저렴하게 대량 확보 가능하다는 점을 활용합니다.
3. 조정 집합 식별 전략:
   • 각 노드의 회귀 이웃 (Regression Neighborhood) 을 관측 데이터로 추정합니다.
   • 관측 추정치와 실험 추정치의 차이가 0 에 가까운지 확인하여 유효한 조정 집합을 후보로 선정합니다.
   • 신뢰구간 (Confidence Interval) 이 0 을 포함하는 집합을 선택하거나, 가장 가까운 집합을 선택하여 탐색을 유도합니다.

2.2. 알고리즘 흐름 (Algorithm 1)

1. 초기 관측 데이터 ($n_0$) 를 기반으로 회귀 이웃을 추정합니다.
2. 각 라운드 $t$에서:
   • 아직 충분히 개입되지 않은 암이 있으면 우선 개입합니다 (Exploration).
   • 그렇지 않으면, 현재까지의 데이터를 바탕으로 각 암에 대한 후보 조정 집합을 식별합니다.
   • 관측 및 실험 데이터를 가중 평균하여 UCB 값을 계산하고, UCB 가 최대인 암을 선택합니다.
   • 새로운 실험 데이터 ($m$개) 와 관측 데이터 ($n$개) 를 수집하여 업데이트합니다.

3. 주요 기여 및 이론적 결과 (Key Contributions & Theoretical Results)

3.1. 유한 시간 후회 상한 (Finite-time Regret Bounds)

• 잠재적 혼란변수 (Latent Confounders) 가 없는 경우:
  • 충분한 초기 관측 데이터가 있을 때, 누적 후회 상한은 $O(\sqrt{T \log T / (m+n)})$ 입니다.
  • 기존 표준 MAB 알고리즘의 후회 상한인 $O(\sqrt{K T \log T})$ (여기서 $K$는 암의 수) 와 비교할 때, 암의 수 $K$에 대한 의존성이 크게 완화되었습니다.
  • 이는 관측 데이터가 실험 데이터만큼이나 후회 감소에 기여하며, 정보 공유 (Information Sharing) 를 통해 모든 암의 인과 효과를 동시에 추정할 수 있음을 의미합니다.
• 잠재적 혼란변수가 있는 경우 (ADMG 모델):
  • 유효한 조정 집합이 존재하지 않는 암 ($I_1$) 과 존재하는 암 ($I_0$) 을 구분합니다.
  • 후회 상한은 $I_0$에 대해서는 $(m+n)$에 비례하여 감소하고, $I_1$에 대해서는 $m$에만 비례하여 감소하는 형태로 확장됩니다.
  • 알고리즘은 유효한 조정 집합이 없을 경우 자동으로 실험 데이터만 사용하는 방식으로 전환하여 강건성을 보장합니다.

3.2. 계산 효율성

• 기존 베이지안 방법 (BBB-UCB) 은 모든 가능한 부모 집합에 대한 사후 확률을 계산해야 하여 계산 복잡도가 $O(p \cdot 3^p)$로 매우 높습니다.
• BA-UCB 는 그래프 전체를 복원하지 않고 국부적인 회귀 이웃과 조정 집합만 탐색하므로, 계산 효율성이 매우 높고 대규모 그래프에서도 확장 가능합니다.

4. 실험 결과 (Simulation Results)

• 시뮬레이션 설정: 다양한 크기의 가우시안 DAG ($p=10, 20, 30, 50$) 를 생성하여 BA-UCB 를 기존 방법 (Standard UCB, CN-UCB, BBB-UCB) 과 비교했습니다.
• 성능 비교:
  • 후회 (Regret): BA-UCB 는 표준 UCB 및 CN-UCB 보다 현저히 낮은 누적 후회를 보였습니다. 특히 최적의 개입이 보상 변수의 부모가 아닌 경우, CN-UCB 는 성능이 급격히 저하되지만 BA-UCB 는 안정적으로 작동했습니다.
  • 계산 시간: BBB-UCB 는 $p \ge 20$일 때 계산 시간이 prohibitive(실현 불가능) 해졌으나, BA-UCB 는 $p=50$에서도 5 분 이내에 실행 가능했습니다.
  • 데이터 통합 효과: 가중 평균 추정 방식이 단일 회귀 방식보다 더 강건하며, 관측 데이터가 많을수록 후회가 줄어드는 것을 확인했습니다.
• 잠재적 혼란변수 존재 시: 관측 데이터와 실험 데이터를 결합한 BA-UCB 는 혼란변수가 존재하는 상황에서도 UCB 보다 우수한 성능을 유지하며, 조정 집합 식별 정확도가 시간이 지남에 따라 75% 이상으로 향상됨을 보였습니다.

5. 의의 및 결론 (Significance & Conclusion)

1. 지식 불확실성 하의 의사결정: 인과 그래프 구조를 알지 못하더라도, 관측 데이터와 실험 데이터를 결합하여 최적의 개입을 찾을 수 있음을 증명했습니다.
2. 비용 효율성: 실험 데이터는 비용이 많이 드는 반면 관측 데이터는 상대적으로 저렴합니다. BA-UCB 는 이러한 비용 차이를 활용하여 실험 횟수를 줄이면서도 높은 정확도를 달성합니다.
3. 확장성: 기존 방법들이 가정한 "최적 개입은 부모 노드"라는 제약을 제거하고, 잠재적 혼란변수가 있는 복잡한 상황 (ADMG) 으로도 확장 가능하여 실제 응용 (의료, 경제, 농업 등) 에 매우 유용합니다.
4. 이론적 엄밀성: 관측 데이터의 양이 충분할 때 후회가 암의 수 $K$에 무관하게 감소한다는 이론적 보장을 제공하여, 대규모 인과 밴딧 문제 해결의 새로운 기준을 제시했습니다.

요약하자면, 이 논문은 알려지지 않은 인과 구조 하에서 관측 데이터와 실험 데이터를 지능적으로 융합하여, 계산 효율성과 통계적 효율성을 동시에 극대화하는 새로운 인과 밴딧 알고리즘 (BA-UCB) 을 제안하고 그 우수성을 이론적, 실증적으로 입증한 연구입니다.