기술 요약: 인과적 밴딧을 위한 정보 지향 샘플링 (Information-Directed Sampling for Causal Bandits)

문제 정식화

본 논문은 조작 불가능한 변수(non-manipulable variables)를 포함하는 환경에서의 문맥적 인과 밴딧(contextual causal bandits) 문제를 다룹니다. 표준적인 멀티 암드 밴딧(multi-armed bandit) 문제에서는 미지의 분포를 가진 보상을 최대화하기 위해 행동을 선택합니다. 인과적 밴딧에서 행동은 구조적 인과 모델(SCM)에 대한 개입($do(X=x)$)에 해당하며, 여기서 보상은 공유된 인과 기제를 통해 서로 결합되어 있습니다.

여기서 다루는 구체적인 과제는, 보상에 영향을 미치지만 직접적으로 조작할 수 없는 특정 변수들(예: 인구통계학적 속성, 유전적 특성, 또는 거시 경제 조건)이 존재하는 상황에서 발생합니다. 이러한 변수들은 개입의 대상이 될 수는 없지만, 행동 선택 전에는 문맥(context) 변수로 관찰되며 개입 후에는 관찰된 변수로 기능합니다. 목표는 후보 암(arm) 집합으로부터 실행 가능한 개입을 선택하여 문맥 의존적 기대 보상 $\mu_x(c) = E[Y | do(x), C=c]$를 최대화하는 것입니다.

저자들은 다음을 가정합니다:

1. 잠재적 교란 요인(latent confounders)이 없는 알려진 인과 그래프 $G$.
2. 조작 불가능한 변수 집합 $N \subseteq V \setminus \{Y\}$.
3. 문맥 변수 $C$는 행동 선택 전에 관찰되며, 조상 관계에 대해 닫혀 있음($An(C)=C$).
4. 관측 분포는 미지이며, 조건부 확률 테이블(CPT)에 의해 매개변수화됨.

방법론

1. 베이지안 정식화 및 매개변수화

저자들은 미지의 파라미터 $\theta$가 관측 분포의 조건부 확률 테이블로 구성되는 베이지안 프레임워크를 채택합니다. 잠재적 교환 요인이 없다는 가정하에, 개입 분포는 절단 팩토리제이션 공식(truncated factorization formula)을 통해 관측 분포로부터 식별 가능합니다.

• 파라미터 독립성: 파라미터 벡터 $\theta$는 각 변수의 부모 구성에 따른 CPT에 대응하는 로컬 벡터 $\theta_{ij}$로 분해됩니다.
• 사후 확률 업데이트: 공액 디리클레 사전 분포(conjugate Dirichlet priors)를 가정하여, 관측된 데이터를 기반으로 $\theta$에 대한 사후 분포를 분석적으로 업데이트합니다. 이를 통해 한 가지 개입 하에서 수집된 샘플이 공유된 CPT를 정교화함으로써 다른 개입에 대한 추정치를 업데이트할 수 있게 합니다.

2. 후보 암의 식별

조작 불가능한 변수를 처리하기 위해, 본 논문은 Lee와 Bareinboim [2019]에서 도출된 가능한 최적 최소 개입 집합(Possibly Optimal Minimal Intervention Sets, POMISs) 개념을 활용합니다.

• 투영(Projection): 원래의 그래프를 조작 가능한 변수만을 포함하는 그래프 $H$로 투영합니다. 조작 불가능한 변수에 의해 유도된 잠재적 교란은 $H$ 내의 양방향 화살표(bidirected edges)로 표현됩니다.
• 암 선택: POMISs의 열거를 통해 후보 암 집합 $\mathcal{A}$를 생성합니다. 이는 알고리즘이 조작 가능성 제약 조건 하에서 이론적으로 최적인 개입만을 고려하도록 보장합니다.

3. 제안된 알고리즘

본 논문은 표준 밴딧 알고리즘의 두 가지 인과적 변형을 제안합니다.

A. 인과적 톰슨 샘플링 (Causal Thompson Sampling, TS)

• 메커니즘: 매 라운드 $t$에서, 주어진 문맥 $C_t=c_t$에 대해 알고리즘은 문맥 조건부 사후 분포 $P(\theta | F_t, C_t=c_t)$로부터 파라미터 $\theta_t$를 샘플링합니다. 그 후, 샘플링된 파라미터 하에서 기대 보상을 최대화하는 행동 $a_t$를 선택합니다: $a_t = \arg\max_{a \in \mathcal{A}} E[Y_a | \theta_t, c_t]$.
• 후회 분석(Regret Analysis): 저자들은 최적 행동 매핑의 엔트로피 $H(\Pi^*)$에 의존하는 서브리니어(sublinear) 베이지안 후회 상한을 확립합니다. 이 상한은 $O(\sqrt{T |A| |C| \log |A|})$로 스케일링됩니다.

B. 인과적 정보 지향 샘플링 (Causal Information-Directed Sampling, IDS)

• 메커니즘: IDS는 **정보 비율(information ratio)**을 최소화하는 행동 분포를 선택합니다. 정보 비율은 제곱된 기대 즉각적 후회(expected instantaneous regret)를 최적 행동에 대한 기대 정보 이득(expected information gain)으로 나눈 값으로 정의됩니다.
  • 후회 항: $\Delta_t(\pi | c_t) = \sum \pi(a) E[Y_{\Pi^*(c_t)} - Y_a]$.
  • 정보 이득 항: $g_t(\pi | c_t) = \sum \pi(a) D_{KL}(P(\Pi^*, Y_a) || P(\Pi^*)P(Y_a))$.
• 몬테카를로 근사: 정보 비율을 계산하는 데 필요한 사후 기대값은 연속적인 파라미터 공간에서 분석적으로 다루기 어렵기 때문에, 알고리즘은 사후 분포로부터 $N$개의 몬테카를로 샘플을 사용하여 이를 근사합니다.
• 오차 제어: 저자들은 기대 후회와 정보 이득의 몬테카를로 추정치에 대한 고확률 집중 경계(high-probability concentration bounds, Lemma 3 및 4)를 도출합니다. 이 경계는 근사에 의해 도입된 추가 오차를 명시적으로 정량화합니다.

주요 기여

1. 조작 불가능한 변수를 위한 베이지안 프레임워크: 본 논문은 관측 CPT를 미지 파라미터로 취급함으로써 조작 불가능한 변수가 있는 문맥적 인과 밴딧을 정식화했습니다. 이 정식화는 일부 변수를 조작할 수 없는 상황에서도 공유된 인과 기제를 통해 개입 간의 정보 공유를 가능하게 합니다.
2. 후회 보증이 있는 인과적 톰슨 샘플링: 저자들은 인과적 TS 알고리즘을 제안하고 엔트로피 의존적인 서브리니어 베이지안 후회 상한을 증명했습니다. 이는 구조적 제약과 문맥이 존재하는 설정으로 TS의 보증을 확장합니다.
3. 근사 분석이 포함된 인과적 IDS: 본 논문은 후회 최소화와 정보 획득 사이의 균형을 맞추는 인과적 IDS 알고리즘을 개발했습니다. 결정적으로, 표준적인 정보 이론적 항과 몬테카를로 근사에 의해 도입된 오차를 명시적으로 분리하는 후회 상한을 도출했습니다. 정보 비율이 정확하게 계산되는 경우(오라클 버전), 표준적인 서브리니어 IDS 비율이 회복됩니다.
4. 몬테카를로 추정치를 위한 집중 경계: 저자들은 기대 즉각적 후회와 문맥적 정보 이득의 몬테카를로 추정치에 대한 고확률 신뢰 경계를 제공합니다. 이러한 결과는 사후 샘플링 오차가 알고리즘의 성능 보증에 미치는 영향을 정량화합니다.

결과 및 평가

제안된 방법들은 구조화된 예시와 무작위 생성된 인과 그래프를 포함한 다수의 합성 인과 밴딧 작업에서 평가되었습니다.

• 성능: 실험 결과, 제안된 Causal TS 및 Causal IDS 알고리즘이 인과적 및 비인과적 베이스라인 모델보다 우수한 성능을 보임을 입증했습니다.
• 메커니즘: 이러한 우수한 성능은 조작 불가능한 변수가 존재하는 상황에서도 공유된 인과 구조를 통해 공유되는 정보를 더 효과적으로 활용하는 알고리즘의 능력 덕분입니다.

의의

본 논문은 모든 변수를 완전히 제어할 수 없는 인과적 환경에서의 의사결정을 위한 원칙적인 프레임워크를 제공한다는 점에서 의의를 가집니다. 조작 불가능한 변수를 인과적 밴딧 프레임워크에 통합하고, (근사 오차 분석을 포함한) 엄격한 후회 상한을 제공함으로써, 이 연구는 이론적 인과 추론과 실질적인 순차적 의사결정 사이의 간극을 메웁니다. 특히 IDS에서 몬테카를로 근사 오차를 명시적으로 다룬 점은 핵심적인 이론적 진보로 강조되며, 이는 정확한 계산이 불가능한 상황에서도 정보 지향 샘플링의 이점이 유지되도록 보장합니다.