📊 statistics

Adaptive Policy Learning Under Unknown Network Interference

본 논문은 깁스 샘플러를 통해 미지의 네트워크 간섭 역학을 공동 학습하고 개별 수준의 치료 할당을 최적화하는 톰슨 샘플링 알고리즘을 제안하여, 적응형 실험 환경에서 아선형 베이지안 후회를 달성하고 정확한 하류 인과 효과 추정을 가능하게 합니다.

원저자: Aidan Gleich, Eric Laber, Alexander Volfovsky

게시일 2026-05-13

📖 4 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Aidan Gleich, Eric Laber, Alexander Volfovsky

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

대규모 사교 클럽의 매니저가 되어 있다고 상상해 보세요. 회원들에게 '선물'(무료 커피나 할인 등) 을 나눠줄 제한된 예산이 있습니다. 당신의 목표는 클럽을 가능한 한 행복하고 수익성 있게 만드는 것입니다.

하지만 함정이 하나 있습니다. 누가 누구와 대화하는지 정확히 알 수 없다는 점입니다. 사실, 한 사람에게 선물을 주는 것이 그들의 친구에게 영향을 미치는지조차 알지 못합니다. 앨리스에게 선물을 주면, 연상 효과로 그녀의 친구 밥이 기뻐할 수도 있습니다. 혹은 두 사람 모두에게 선물을 주면 서로 상쇄되어 효과가 사라질 수도 있습니다. 이를 **간섭 (interference)**이라고 합니다.

오랫동안 이 문제를 해결하려던 과학자들은 거대한 추측을 해야만 했습니다. "이미 우정 지도를 알고 있다고 가정하자"거나 "개인을 걱정할 필요 없이 사람 전체 그룹을 한 번에 대우하자"는 식이었습니다. 하지만 현실 세계에서는 지도를 가지고 있지 않은 경우가 많으며, 전체 그룹을 대우하는 것은 비효율적입니다.

이 논문은 이러한 상황을 처리할 새로운, 지적인 방법을 제시합니다. 이를 게임 플레이 중에 지도를 학습하는 탐정이라고 생각하세요.

문제: "맹목적인" 매니저

보통 선물을 나눠줄 최선의 방법을 파악하려면 두 가지가 필요합니다:

지도: 누가 누구와 친구인지?
전략: 행복을 극대화하기 위해 누구에게 선물을 줘야 하는지?

기존 방법들은 다음과 같은 매니저와 같았습니다:

이미 지도를 가지고 있는 척했다 (이는 거의 사실이 아님).
개별 전략을 포기하고 거추장스러운 큰 그룹만 대우했다.
클럽이 너무 크다면 (12 명 이상) 압도당했다.

해결책: "깁스 (Gibbs)" 탐정

저자들 (에이드언 글라이크, 에릭 레버, 알렉산더 볼포프스키) 은 Gibbs-TS라고 불리는 새로운 알고리즘을 개발했습니다. 한 탐정이 동시에 두 가지 일을 한다고 상상해 보세요:

게임을 플레이한다: 몇 개의 선물을 주고 클럽의 반응을 지켜본 뒤 '행복 점수'를 계산한다.
지도를 업데이트한다: 반응에 기반하여 누가 누구와 친구인지 추측한다. 앨리스가 선물을 받고 밥이 갑자기 더 행복해 보인다면, 탐정은 "아하! 앨리스와 밥은 아마 친구일 거야"라고 생각한다.

그들은 **깁스 샘플러 (Gibbs sampler)**라는 수학적 트릭을 사용합니다. 이를 '만약에 (what-if)' 기계라고 생각하세요. 이 기계는 머릿속에서 수천 개의 미세한 시뮬레이션을 실행합니다:

시나리오 A: 앨리스와 밥이 친구라면? 선물은 어떻게 작용했을까?
시나리오 B: 친구가 아니라면? 그것은 어떻게 보였을까?

이 시나리오들을 반복해서 실행함으로써 기계는 서서히 진실을 좁혀갑니다. 동시에 선물을 나눠줄 최고의 전략을 파악하면서 우정 관계에 대한 최고의 추측 지도를 구축합니다.

이것이 중요한 이유

이 논문은 이 방법이 세 가지 측면에서 엄청난 업그레이드라고 주장합니다:

1. 지도를 학습하면서 게임을 이긴다.
대부분의 다른 방법들은 지도가 알려져 있다고 가정하고 게임을 이기려 하거나, 게임과 상관없이 지도를 그리려 합니다. 이 방법은 둘을 동시에 수행합니다. 마치 운전하는 동안 도로 상태를 학습하는 GPS 와 같으며, 집에 돌아와서야 지도를 그리는 것이 아닙니다.

2. 대규모 네트워크에서 작동한다.
이전 방법들은 작은 그룹 (약 12 명) 만 처리할 수 있었습니다. 이 새로운 방법은 수백 명, 심지어 수천 명으로 구성된 네트워크에서 작동합니다. 저자들은 인도의 한 마을과 미국의 한 학교에서 얻은 실제 데이터로 이를 테스트했으며, 매우 잘 작동했습니다.

3. "보너스 보고서"를 생성한다.
알고리즘이 우정 지도를 학습하기 때문에, 누구에게 선물을 줄지 알려줄 뿐만 아니라 네트워크의 재구성된 지도도 제공합니다. 이는 영향이 어떻게 퍼지는지 (예: 소문이나 질병이 집단 내에서 어떻게 이동하는지) 연구하려는 과학자들에게 귀중한 자료입니다.

결과: 후회 감소, 행복 증가

실험 세계에서 '후회 (regret)'는 '놓친 기회'를 위한 세련된 표현입니다. 잘못된 사람에게 선물을 주었다면, 다른 사람에게 주었으면 더 많은 행복을 만들었을 것이므로 '후회'가 생깁니다.

기존 방법: 사람들이 서로에게 영향을 미친다는 사실을 무시했을 때, 그들은 거대한 실수 (선형 후회) 를 저질렀습니다. 그들은 같은 잘못된 선택을 계속 반복했습니다.
이 새로운 방법: 실수를 했지만 빠르게 학습했습니다. '후회'는 매우 느리게 증가했습니다 (비선형). 직접 대결 테스트에서 이 새로운 방법은 다음으로 가장 좋은 경쟁자보다 10 배 적은 실수를 범했습니다.

결론

이 논문은 사람들 간의 연결을 알지 못하는 messy 한 실제 사회 네트워크에서 실험을 수행할 수 있는 도구를 제시합니다. 최상의 결과를 얻으려 노력하는 동시에 연결 관계를 실시간으로 학습합니다.

저자들은 수학적으로 이 접근 방식이 효율적임을 증명했으며, 컴퓨터 시뮬레이션과 실제 데이터를 통해 이전 방법들보다 훨씬 잘 작동함을 보여주었습니다. 또한 그들이 구축한 지도는 나중에 사람들이 서로에게 어떻게 영향을 미치는지에 대한 다른 과학적 질문에 답하는 데 사용될 수 있다고 지적했습니다.

간단히 말해: 이는 미리 그려진 지도가 필요 없이, 숨겨진 사회적 웹을 파악하면서 동시에 사람들을 돕는 최선의 방법을 찾아내는 지능형 자기 학습 시스템입니다.

기술적 요약: 미지의 네트워크 간섭 하의 적응적 정책 학습

문제 정의

많은 실험 환경에서, 단위 (unit) 의 결과는 자체 처치뿐만 아니라 기본 네트워크 내 이웃들에게 할당된 처치에도 의존합니다. 이러한 현상을 **간섭 (interference)**또는 스필오버 (spillover) 라고 하며, 이는 안정적 단위 처치 가치 가정 (SUTVA) 을 위반합니다. 간섭 하의 정적 실험에 대한 인과 추론 문헌은 강력한 방법론을 개발해 왔습니다 (예: Sussman and Airoldi, 2017; Aronow and Samii, 2017). 그러나 이러한 접근법들은 일반적으로 간섭 네트워크가 알려져 있다고 가정하거나, 거친 군집 수준의 무작위화에 의존합니다.

기존의 적응적 (순차적) 실험 방법론은 다음과 같은 중대한 한계에 직면해 있습니다:

알려진 네트워크 가정: Gleich 등 (2025) 과 같은 확장 가능한 방법론들은 네트워크 구조가 완전히 관측된다고 가정합니다. 이는 사회적 또는 행동적 유대가 잠재적인 많은 응용 분야에서 비현실적입니다.
확장성 문제: 네트워크 구조를 학습하려는 시도 (예: Agarwal 등, 2024) 는 모든 가능한 이웃 구성에 대한 푸리에 분석에 의존하여, 이웃 크기에 대해 지수적으로 증가하는 매개변수 수를 초래합니다. 이러한 방법론들은 대략 $n \approx 12$ 개 단위를 초과하는 규모에서는 확장되지 못합니다.
세분성 상실: 다른 적응적 설계 (예: Viviano and Rudder, 2024) 는 사전 정의된 군집에서 작동하여 개별 단위 수준의 최적화를 우회하고, 간섭 네트워크 자체를 복원하지 못합니다.

본 논문이 다루는 핵심 과제는 미지의 간섭 네트워크를 공동으로 학습하고 개별 단위 수준의 처치 할당을 순차적 환경에서 최적화하여 누적 결과 (예: 수익, 건강 지표) 를 극대화하는 것입니다.

방법론

저자들은 Gibbs 샘플러를 사용하여 간섭 네트워크와 보상 매개변수를 공동으로 추론하는 **Thompson Sampling (TS)**프레임워크를 제안합니다.

1. 모델 설정

환경: 예산 제약 $\|Z_t\|_1 \le B$ 하에 $T$ 라운드에 걸쳐 $n$ 개 단위에 이진 처치 $Z_t \in \{0, 1\}^n$ 을 순차적으로 할당합니다.
이웃 간섭 가정 (NIA): 단위 $i$ 의 결과는 자체 처치와 미지의 인접 행렬 $A$ 로 정의된 이웃들의 처치에만 의존합니다.
보상 모델: 기대 결과는 매개변수 벡터 $\theta$ 에 대해 선형입니다. 즉, $r(Z; A, \theta) = H(Z; A)\theta$ 입니다. 설계 행렬 $H$ 는 네트워크 $A$ 에 의존합니다.

2. Gibbs 를 통한 공동 사후 분포 샘플링

우도 함수가 $A$ 에 대해 비선형 (이웃 수로 인해) 이므로, 폐쇄형 사후 분포는 존재하지 않습니다. 저자들은 사후 분포 $\pi(\theta, A | \mathcal{D}_{t-1})$ 로부터 근사적인 공동 샘플을 추출하기 위해 엣지 단위 Gibbs 샘플러를 사용합니다:

매개변수 업데이트 ( $\theta | A$ ): $A$ 가 고정되면, 모델은 표준 켤레 가우시안 회귀로 축소됩니다. $\theta$ 에 대한 사후 분포는 가우시안입니다.
엣지 업데이트 ( $A | \theta$ ): $\theta$ 가 고정되면, 샘플러는 모든 엣지 $(i, j)$ 를 순회합니다. 엣지 $A_{ij}$ 에 대한 완전 조건부 분포는 노드 $i$ 와 $j$ 의 보상 스트림에만 의존합니다. 업데이트 규칙은 우도 비율의 로짓 변환을 통해 유도되어, 모든 $2^{\binom{n}{2}}$ 개의 그래프 구성을 열거하지 않고도 효율적인 샘플링이 가능합니다.

3. 알고리즘 (Gibbs-TS)

각 라운드 $t$ 에서:

$K$ 번의 Gibbs 스윕을 수행하여 근사적인 공동 샘플 $(\theta^{(t)}, A^{(t)})$ 을 얻습니다.
샘플링된 기대 총 보상을 최대화하는 처치 벡터 $Z_t$ 를 선택합니다: $Z_t = \arg\max_{Z: \|Z\|_1 \le B} \mathbf{1}^\top H(Z; A^{(t)}) \theta^{(t)}$ .
보상을 관측하고 기록 $\mathcal{D}_t$ 를 업데이트합니다.
다음 라운드의 Gibbs 체인을 현재 라운드의 최종 샘플로 워밍업 (warm-start) 합니다.

4. 탐색 후 확정 (Explore-Then-Commit, ETC) 변형

모듈러 붕괴가 성립하지 않는 일반적인 NIA 보상의 경우, 저자들은 ETC 전략을 분석합니다:

1 단계: 관측된 스필오버를 기반으로 엣지 확률을 추정하기 위해 $m$ 라운드에 걸쳐 각 노드를 고립된 상태로 처치합니다.
2 단계: 추정된 그래프 $\hat{A}$ 를 사용하여 (네트워크가 알려진 것으로 가정하는) 표준 Thompson Sampling 알고리즘을 실행합니다.

주요 기여

공동 학습 프레임워크: 본 논문은 NIA 하에서 네트워크 복원과 적응적 처치 할당의 공동 문제를 공식화합니다. 이는 네트워크와 보상 매개변수의 공동 사후 분포를 샘플링하기 위해 엣지 단위 Gibbs 스윕을 사용하는 Thompson Sampling 알고리즘을 도입합니다.
하류 인과 추론: 추정된 네트워크 $\hat{A}$ 는 단순한 부산물이 아니라 과학적 산출물입니다. 이는 실험 후 직접 효과, 간접 효과, 총 처치 효과의 추정을 지원하고 후속 실험 설계를 가능하게 합니다.
이론적 후회 (Regret) 상한:
- 가법적 스필오버 모델: 총 보상이 잠재적 스코어 계수를 가진 처치 벡터에 대해 선형인 모델 (예: 평균 선형 모델) 의 경우, 저자들은 정확한 사후 샘플링에 대해 $O(\sqrt{nT \cdot B \log(en/B)})$ 차수의 베이지안 후회 상한을 증명합니다. 이 상한은 $\theta$ 의 주변 차수가 아닌 잠재적 스코어 차원 $n$ 에 의존합니다.
- 일반 NIA: 일반적인 보상의 경우, ETC 변형은 $O(n^2 \log T)$ 의 그래프 발견 비용을 갖는 후회 상한을 달성합니다.
- 하한: $\Omega(n \log T)$ 의 정보 이론적 하한이 확립되어, 일관된 알고리즘이라면 네트워크 발견을 위해 $n$ 에 선형적인 비용을 치러야 함을 보여줍니다.
확장성: 이 방법은 수백 개의 노드를 가진 네트워크 (평균 선형 모델 하에서 최대 $n=1000$ ) 로 확장 가능하며, $n \approx 12$ 로 제한된 기존 방법론을 크게 능가합니다.

실증 결과

후회 성능: 두 가지 실세계 네트워크 (63 개 노드의 대출 네트워크와 121 개 노드의 학교 우정 네트워크) 에서 Gibbs-TS 알고리즘은 아선형 (sublinear) 후회를 달성합니다. 참 네트워크를 아는 오라클에 비해 격차가 존재하지만, 간섭을 무시하는 베이스라인 (선형 후회를 겪음) 에 비해 후회가 현저히 낮습니다.
최첨단 기법과의 비교: Agarwal 등 (2024) 이 실행 가능한 작은 네트워크 ( $n=8$ ) 에 대한 직접 비교에서, Gibbs-TS는 후회를 10 배 이상 감소시킵니다 (예: 특정 조건 하에서 Agarwal 등의 중앙값 후회 1571 대비 141).
네트워크 복원: 이 알고리즘은 높은 정확도로 간섭 네트워크를 성공적으로 복원합니다 (합성 환경에서 F1 점수 > 0.98, 실세계 환경에서 0.74).
하류 추정: 복원된 네트워크 $\hat{A}$ 를 사용하여, 직접, 간접, 총 처치 효과에 대한 추정치는 참 네트워크를 사용하여 얻은 추정치와 밀접하게 일치하며, 작은 평균 제곱근 오차 (RMSE) 를 보입니다.

중요성과 주장

본 논문은 사전 정의된 군집 구조를 요구하지 않고 순차적 환경에서 간섭 네트워크를 공동으로 학습하고 개별 단위 수준의 처치 할당을 최적화하는 최초의 적응적 실험 설계를 제공한다고 주장합니다.

과학적 가치: 복원된 네트워크는 직접적인 과학적 산출물로서, 적응적 환경에서 이전에 접근 불가능했던 인과 분석 (직접/간접 효과) 을 가능하게 합니다.
실용적 영향: 이 방법은 간섭 하의 이론적 인과 추론과 실용적 대규모 적응적 실험 간의 격차를 해소합니다. 이는 플랫폼과 기관이 백신 배포, 마케팅과 같은 개입을 실시간으로 최적화하면서 동시에 기본 사회적 또는 행동 역학을 매핑할 수 있게 합니다.
이론적 통찰: 이 연구는 가법적 스필오버 모델 하에서 문제의 복잡성이 잠재적 스코어 벡터의 차원으로 축소되어, 그래프 토폴로지의 복잡성과 무관한 후회 상한을 가능하게 함을 확립합니다.

저자들은 올바른 보상 함수 명세에 대한 의존성, 일반적인 NIA 환경에서 처치 선택을 위한 정수 선형 프로그래밍의 계산 병목 현상, 그리고 그래프 발견 비용에 대한 $O(n^2)$ 상한과 $\Omega(n)$ 하한 사이의 격차 등 한계를 인정합니다. 그러나 그들은 그들의 접근 방식이 미지의 네트워크 간섭 하에서 확장 가능한 적응적 실험에서 중요한 진전을 나타낸다고 주장합니다.