Budget-Constrained Causal Bandits: Bridging Uplift Modeling and Sequential Decision-Making

다음은 논문 "예산 제약 하의 인과적 밴딧: 업리프트 모델링과 순차적 의사결정의 연결"에 대한 상세한 기술 요약입니다.

1. 문제 정의

본 논문은 디지털 광고, 특히 역사적 데이터가 부족하거나 존재하지 않는 콜드스타트 시나리오(예: 새로운 캠페인, 새로운 시장) 에서 발생하는 예산 제약 하의 치료 할당 문제를 다룹니다.

• 핵심 목표: 총 예산 제약 $B$를 준수하면서 광고를 노출할 사용자 하위 집합을 선택하여 총 전환 수 (치료 결과) 를 최대화합니다.
• 주요 제약 및 과제:
  1. 이질적 치료 효과 (HTE): 사용자는 광고에 다르게 반응합니다. 목표는 높은 긍정적 인과 효과 ($\tau(x)$) 를 가진 사용자를 타겟팅하고, 영향이 없거나 부정적 영향을 받는 사용자는 피하는 것입니다.
  2. 예산 제약: 각 사용자는 특정 비용 $c_t$(예: 광고 경매 가격) 를 가집니다. 누적 비용은 $B$를 초과해서는 안 됩니다.
  3. 콜드스타트 / 데이터 부족: 전통적인 오프라인 방법은 업리프트 모델을 훈련시키기 위해 대량의 역사적 데이터셋을 필요로 합니다. 새로운 시나리오에서는 이러한 데이터가 unavailable 하여 "콜드스타트" 문제가 발생합니다.
  4. 순차적 의사결정: 사용자는 하나씩 도착합니다. 시스템은 치료 효과를 온라인으로 학습하면서 동시에 예산 페이싱 (조기 소진 또는 비효율적인 과소 지출 방지) 을 관리해야 합니다.

공식적 정의:
이 문제는 $T$라운드에 걸친 순차적 과정으로 모델링됩니다. 각 라운드 $t$에서 에이전트는 특징 $x_t$와 비용 $c_t$를 가진 사용자를 관찰하고, 행동 $a_t \in \{0, 1\}$(치료 또는 미치료) 을 선택합니다. 목표는 다음과 같습니다:
$$\max \sum_{t=1}^T a_t \cdot Y_t(1) \quad \text{subject to} \quad \sum_{t=1}^T a_t \cdot c_t \le B$$
여기서 $Y_t(1)$은 치료되었을 때의 잠재적 결과입니다.

2. 방법론: 예산 제약 하의 인과적 밴딧 (BCCB)

저자들은 BCCB를 제안합니다. 이는 세 가지 서로 다른 구성 요소를 단일 순차적 의사결정 과정으로 통합한 통합 온라인 프레임워크입니다. 오프라인 2 단계 파이프라인 (훈련 후 최적화) 이나 HTE 를 무시하는 표준 밴딧과 달리, BCCB 는 학습, 탐색, 페이싱을 동시에 수행합니다.

A. 온라인 HTE 추정

• 접근 방식: 개별 치료 효과를 온라인으로 추정하기 위해 2 모델 접근법을 사용합니다.
  • 모델 1: $P(Y=1 | x, T=1)$을 추정 (치료 시 전환 확률).
  • 모델 2: $P(Y=1 | x, T=0)$을 추정 (대조군일 때 전환 확률).
• 메커니즘: 두 모델 모두 매 관찰 후 로지스틱 손실 (logistic loss) 을 사용하여 확률적 경사 하강법 (SGD) 으로 점진적으로 업데이트됩니다.
• 콜드스타트 처리: 충분한 데이터가 수집되기 전 (치료/대조군 관찰이 50 개 미만) 에는 초기 탐색을 장려하기 위해 낙관적 사전 분포 ($\hat{\tau} = 0.002$) 를 사용합니다.

B. 톰슨 샘플링 탐색

• 목표: 불확실한 사용자를 학습하는 탐색 (exploration) 과 알려진 고가치 사용자를 타겟팅하는 활용 (exploitation) 사이의 균형을 맞춥니다.
• 메커니즘: 전역 치료 및 대조군 성공률에 대한 베타 사후 분포를 유지합니다.
• 탐색 보너스: 각 단계에서 알고리즘은 사후 분포에서 샘플링하여 탐색 보너스를 계산합니다:
  $$\text{exploration\_bonus}_t = (\theta_t^{(1)} - \theta_t^{(0)}) \cdot \eta$$
  이 보너스는 추정된 HTE 에 추가되어, 현재 HTE 추정이 모호하더라도 효과가 불확실한 사용자를 치료하도록 알고리즘을 장려합니다.

C. 적응형 예산 페이싱

• 목표: 예산의 조기 소진 또는 비효율적인 과소 지출을 방지합니다.
• 메커니즘: 각 라운드에서 예산 압박 비율($pace_t$) 을 계산합니다:
  $$pace_t = \frac{B_t / B_0}{(T - t) / T}$$
  • $pace_t > 1$인 경우: 시간에 비해 예산이 풍부함; 알고리즘은 더 자유롭게 지출합니다.
  • $pace_t < 1$인 경우: 예산이 너무 빠르게 소진됨; 알고리즘은 더 선택적이 됩니다.
• 임계값 조절: 페이싱 비율은 의사결정 임계값을 동적으로 조정합니다. 예산이 부족할 때 치료 임계값이 상승하여 비용 효율성이 높은 사용자만 선택되도록 합니다.

D. 결합된 의사결정 규칙

각 사용자 $t$에 대해 알고리즘은 점수와 달러당 가치 지표를 계산합니다:

1. 점수: $s_t = \hat{\tau}(x_t) + \text{exploration\_bonus}_t$
2. 가치: $v_t = s_t / c_t$
3. 의사결정: $v_t > \frac{\lambda}{\max(pace_t, \epsilon)}$인 경우 치료 ($a_t=1$) 합니다. 여기서 $\lambda$는 기본 임계값입니다.

3. 주요 기여

1. 통합 프레임워크: BCCB 를 제안하여, 사전 수집된 역사적 데이터 없이 HTE 학습, 톰슨 샘플링 탐색, 적응형 예산 페이싱을 단일 온라인 과정으로 통합한 최초의 프레임워크입니다.
2. 데이터 효율성 교차점: 약 10,000 개의 역사적 관찰이라는 임계값을 경험적으로 확인했습니다. 이보다 낮으면 오프라인 방법이 실패하거나 매우 불안정하며, 이보다 높으면 오프라인 방법이 온라인 방법보다 우월할 수 있습니다. BCCB 는 최초 사용자부터 효과적으로 작동합니다.
3. 성능 안정성: 반복 실행 시 BCCB 는 오프라인 방법 대비 3~5 배 낮은 성능 분산을 보여주어 캠페인 계획에 더 신뢰할 수 있음을 입증했습니다.
4. 우월한 온라인 성능: 순수 온라인 방법 중 BCCB 는 모든 예산 수준에서 표준 톰슨 샘플링, 예산이 포함된 톰슨 샘플링, 탐욕적 HTE 추정을 일관되게 능가합니다.

4. 실험 결과

이 연구는 합성 비용 (로그 정규 분포를 통해 생성) 을 적용한 Criteo 업리프트 데이터셋(140 만 명 사용자) 에서 평가되었습니다.

• 온라인 vs 온라인 비교:
  • 고예산 ($8,000) 에서 BCCB 는 46 건의 전환을 달성하여 표준 톰슨 샘플링 (37 건) 과 탐욕적 HTE (29 건) 를 능가했습니다.
  • 엄격한 예산 ($1,000) 에서 BCCB 와 예산이 포함된 TS 가 가장 좋은 성과를 거두어 예산 인식의 중요성을 강조했습니다.
• 데이터 효율성 교차점 (오프라인 vs 온라인):
  • 2,000 개 미만 관찰: 오프라인 방법은 완전히 실패했습니다 (대조군에서 0 개의 긍정적 예시로 인해 모델 적합 불가). BCCB 는 성공적으로 작동했습니다.
  • 2,000 ~ 10,000 개 관찰: 오프라인 방법은 극단적인 분산을 보였습니다 (변동 계수 > 100%). BCCB 는 안정적이었습니다.
  • 50,000 개 이상 관찰: 오프라인 방법이 결국 BCCB 를 능가했습니다 (104 대 25 건 전환), 풍부한 대표성 있는 데이터가 존재할 때 오프라인 방법이 우월함을 확인했습니다.
• 안정성: BCCB 는 713 건의 표준 편차를 보인 반면, 오프라인 방법은 3565 건의 범위를 보였습니다. 이 3~5 배의 분산 감소는 예측 가능한 ROI 예측에 중요합니다.
• 확장성: BCCB 는 데이터셋 규모 (10 만, 50 만, 140 만 사용자) 전반에 걸쳐 최상위 성능을 유지한 반면, 탐욕적 HTE 방법은 매우 불일치했습니다.

5. 의의 및 한계

의의:

• 콜드스타트 문제 해결: 역사적 데이터가 unavailable 한 새로운 광고 캠페인에 대한 실현 가능한 솔루션을 제공하며, 이는 표준 산업 파이프라인이 실패하는 시나리오입니다.
• 리스크 완화: BCCB 의 높은 안정성은 작은 데이터셋으로 훈련된 오프라인 모델에서 흔히 발생하는 무작위 시드 분산으로 인한 캠페인 실패 리스크를 줄여줍니다.
• 패러다임 전환: 자원 제약 하의 인과 추론 분야에서 "훈련 후 배포"에서 "동시 학습 및 할당"으로의 전환을 주도합니다.

한계:

• 데이터 풍부성: 같은 모집단에서 50,000 개 이상의 역사적 관찰을 가진 경우, 오프라인 방법이 여전히 우월합니다.
• 합성 비용: 연구는 로그 정규 분포에 기반한 합성 비용을 사용했습니다. 실제 세계의 경매 역학은 더 복잡할 수 있습니다.
• 모델 복잡성: 현재 구현은 HTE 를 위해 선형 분류기를 사용합니다. 더 표현력 있는 온라인 모델 (예: 온라인 신경망) 은 정확도를 높일 수 있으나 향후 작업으로 남겨두었습니다.

결론:
BCCB 는 업리프트 모델링과 순차적 의사결정 간의 격차를 해소하여, 특히 데이터 부족과 즉각적이고 안정적인 성능이 필요한 시나리오에서 디지털 광고의 예산 제약 하 치료 할당을 위한 견고하고 데이터 효율적인 솔루션을 제공합니다.