Causal Inference on Stopped Random Walks in Online Advertising

기술 요약: 온라인 광고에서의 중단된 랜덤 워크(Stopped Random Walks)에 대한 인과 추론

문제 정의
본 논문은 온라인 광고 플랫폼(퍼블리셔)에 특화된 인과 추론 과제를 다룹다. 목표는 경매 낙찰가(reserve prices)와 같은 메커니즘 파라미터의 장기적 처치 효과(treatment effect)를 추정하는 것이다. 고정된 모집단 크기를 가정하는 고전적인 설정(예: 약물 실험)과 달리, 온라인 광고는 퍼블리셔, 사용자, 광고주가 얽힌 복잡하고 상호 연결된 시스템을 포함한다. 이 환경에서는 다음과 같은 현상이 발생한다:

1. 처치가 모집단 크기에 영향을 미침: 처치(예: 더 높은 낙찰가)는 사용자 상호작나 경로(세션 길이)를 변화시키고, 유한한 예산에 의해 제약받는 광고주의 입찰 행동을 변화시켜, 결과적으로 정해진 기간 동안 생성되는 총 임프레션 기회(impression opportunities)의 수를 변화시킨다.
2. 간섭 및 역동성: 처치 효과를 측정하려는 결정이 측정 대상인 시스템 자체를 변화시킨다. 사용자 세션은 마르코프 체인(Markov chains)으로 모델링되며, 광고주 예산은 과거의 경매 결과에 의존하는 또 다른 마르코프 체인으로 진화한다.
3. 측정 척도의 불일치: 목표 지표는 장기 수익(예: $k$일 동안)이지만, 자연스러운 관측 단위는 개별 광고 임프레션이다. 고정된 시간 창 내의 임프레션 수는 처치에 의존하는 확률 변수(중단 시간, stopping time)이다.

핵심적인 어려움은 i.i.d.(독립 동일 분포) 측정 또는 고정된 표본 크기를 가정하는 표준 중심한계정리(CLT) 접근 방식이 불충분하다는 점이다. 본 논문은 누적 수익을 **중단된 랜덤 워크(stopped random walk)**로 모델링하며, 여기서 중단 시간(총 $k$일 동안의 임프레션 수)은 확률적이며 처치에 의존한다.

방법론

1. 모델링 프레임워크
저자들은 퍼블리셔, 사용자, 광고주 간의 삼자 상호작용을 이산 시간 마르코프 체인으로 모델링한다.

• 상태 공간(State Space): 상태에는 모든 사용자가 방문하는 페이지의 프로필($X_n$), 모든 광고주의 잔여 예산($\Omega_n$), 그리고 활성 사용자 인덱스($I_n$)가 포함된다.
• 역동성(Dynamics): 사용자 페이지 전환 및 광고주 예산 업데이트는 정적 전략(낙찰가 함수 및 입찰 함수)과 사용자 행동 및 예산 보충을 나타내는 확률 변수에 의해 제어된다.
• 수익(Revenue): 퍼블리셔의 수익은 낙찰가와 낙찰가(second-price auction 로직)의 비선형적이고 잠재적으로 불연속적인 함수이다.

2. 차원 축소: 순열 트릭(The Permutation Trick)
$d$명의 사용자와 $m$명의 광고주를 동시에 모델링할 때 발생하는 지수적인 상태 공간 크기는 큰 장애물이다. 이를 해결하기 위해 저자들은 순열 트릭을 도입한다.

• 동기: 동시 발생하는 서로 다른 사용자 세션들로부터 오는 페이지 전환의 순서를 재배열하는 것이, 광고 캠페인 기간보다 사용자 세션의 타임스케일이 훨씬 작다는 전제하에 총 판매량 및 현금 흐름에 미치는 영향이 미미하다는 관찰에 기초한다.
• 메커니즘: 저자들은 동일한 사용자 세션에 속하는 모든 페이지 전환을 함께 묶도록 임프레션 시퀀스의 순서를 재정렬하는 순열 $\sigma$를 정의한다.
• 결 결과: 이는 원래의 고차원 마르코프 체인을 훨씬 작은 상태 공간($\mathcal{X} \times \mathbb{R}^m \times [d]$)을 가진 근사 체인으로 변환한다. 여기서 개별 페이지 전환 대신 전체 사용자 세션이 인터리빙(interleaving)된다. 이 근사는 광고 캠페인의 예산과 기간이 개별 임프레션 비용 및 세션 길이에 비해 크다는 가정 2.1에 의존한다.

3. 실험 설계: 예산 분할(Budget Splitting)
처치 효과를 추정하기 위해, 본 논문은 예산 분할 실험 설계(LMK21에서 영감을 받음)를 제안한다.

• 모집단 분할: 사용자는 확률 $q$와 $1-q$에 따라 하위 모집단 $A$와 $B$로 무작위 할당된다.
• 처치 할당: 하위 모집단 $A$는 처치 $v$(낙찰가 $v$)를 받고, $B$는 처치 $w$를 받는다.
• 예산 분할: 각 광고주의 예산은 두 하위 모집단 사이에 비례적으로($q$와 $1-q$) 분할된다. 각 그룹의 광고주는 자신에게 할당된 하위 모집단의 마르코프 체인 내에서만 경쟁한다.
• 추정량: 총 처치 효과에 대한 추정량 $\hat{\Delta}$는 관측된 하위 모집단의 평균 수익과 임프레션 수를 각각 $1/q$와 $1/(1-q)$로 스케일링함으로써 구축되며, 이는 하위 모집단의 결과를 전체 모집단으로 외삽(extrapolate)하는 과정이다.

4. 이론적 보장
저자들은 다음을 사용하여 장기 처치 효과 $\Delta$에 대한 신뢰 구간을 도출한다:

• 마르코프 체인 CLT: 순열된 체인에 적용되어 수익 합의 점근적 정규성을 확립한다.
• Wald 유사 방정식(Wald-like Equation): 확률적 중단 시간(총 $k$일 동안의 임프레션)을 처리하는 데 사용된다.
• Ansce로의 정리(Anscombe Theorem): 무작위 표본 크기에도 불구하고 중단된 랜덤 워크가 정규 분포로 수렴함을 정당화하기 위해 사용된다.
• 에르고디시티(Ergodicity) 가정: 분석은 기본 마르코프 체인이 해리스 에르고딕(Harris ergodic)하며 기하학적 에르고딕(geometrically ergodic)임을 가정하며, 이는 불변 분포의 존재를 보장한다.

주요 기여

1. 모델링: 모집단 크기(임프레션 수)가 확률적이며 처치에 의존하는 인과 추론을 위한 중단된 랜덤 워크 모델을 도입했다. 이는 고정된 모집단을 가정하는 고전적 인과 추론을 일반화한다.
2. 분석적 기여: 다중 사용자, 다중 광고주 마르코프 시스템에서 차원을 축소하기 위한 순열 트릭을 개발하였으며, 이는 타임스케일에 관한 완만한 가정 하에서 실행 가능한 분석을 가능하게 한다.
3. 통계적 추론: 마르코프 CLT, Wald 유사 방정식, Anscombe 정리를 결합하여 복잡한 환경에서의 장기 처치 효과에 대한 신뢰 구간을 도출하였다. 이는 실험 기간을 결정하기 위한 이론적 토대를 제공한다.

결과
주요 결과(정리 3.6)는 시변하지 않는 전략, 에르고디시티 및 캠페인 규모의 가정하에 제안된 추정량 $\hat{\Delta}$가 실제 처치 효과 $\Delta$로 수렴함을 확립한다. 구체적으로, 본 논문은 다음을 증명한다:
$$\lim_{k \to \infty} P(|\hat{\Delta} - \Delta| \leq \epsilon) \geq 1 - 2\alpha$$
여기서 $\epsilon$은 하위 모집단 체인의 점근적 분산과 하위 모집단과 전체 모집단의 불변 분포 간의 차이에 의존하는 경계값이다. 저자들은 실제 상황에서 사용자 인구가 많을 경우 이러한 분포들이 서로 매우 가까울 것으로 예상되며, 따라서 추정량이 효과적일 것이라고 언급한다.

의의 및 주장
본 논문은 "분석 단위"(사용자 세션)와 "측정 단위"(임프레션)가 서로 다른 척도에서 작동하고, 처치 자체가 생성되는 데이터의 양을 변화시키는 온라인 광고 시스템에서의 인과 추론을 위한 엄격한 프레임워크를 제공한다고 주장한다.

• 이는 고전적 인과 추론의 "유한 모집단" 가정을 넘어 확률적이고 처치 의존적인 모집단으로 나아간다.
• 단순히 간섭을 제어하기 위해 무작위화 기술에만 의존하는 대신, 사용자 및 광고주의 역동성을 명시적으로 모델링함으로써 양방향 시장의 "간섭" 문제를 해결하는 실질적인 솔루션을 제공한다.
• 신뢰 구간의 폭을 점근적 분산 및 기간 $k$와 연결함으로써 실험 기간에 대한 실행 가능한 지침을 제공한다.

저자들은 모델이 정적 전략을 가정하며 비정적 역동성(예: 새로운 광고주의 시스템 진입)을 명시적으로 처리하지 않는다는 한계를 인정한다. 또한 예산 분할 설계가 효과적일 수 있지만, 특정 마르코프 모델에 포착되지 않는 임의의 간섭 효과까지 교정할 수는 없음을 시사한다.