[기술 요약] BFTS: Bayesian Additive Regression Trees를 이용한 톰슨 샘플링

1. 문제 정의 (Problem Statement)

본 논문은 컨텍스추얼 밴딧(Contextual Bandits) 환경, 특히 모바일 헬스(mHealth)와 같이 사용자의 행동이 복잡하고 비선형적인 상황에서의 의사결정 최적화 문제를 다룹니다.

• 기존 방식의 한계:
  • 선형 모델(Linear Models): 구현이 쉽고 해석이 용이하지만, 인간 행동의 복잡한 비선형 상호작용이나 임계값 효과(threshold effects)를 포착하지 못해 높은 편향(bias)을 가집니다.
  • 신경망 모델(Neural Networks): 표현력은 뛰어나지만, 온라인 환경에서 하이퍼파라미터 튜닝이 매우 어렵고 모델이 불안정(brittle)할 수 있습니다.
  • 트리 앙상블(Tree Ensembles): 정형 데이터(tabular data) 예측에는 매우 강력하지만, 톰슨 샘플링(Thompson Sampling, TS)에 필수적인 **원칙적인 확률적 불확실성(principled probabilistic uncertainty)**을 제공하지 못하며, 대개 휴리스틱한 방식에 의존합니다.

2. 제안 방법론 (Methodology: BFTS)

저자들은 **Bayesian Forest Thompson Sampling (BFTS)**을 제안합니다. 이는 트리 앙상블의 예측력과 베이지안 모델의 확률적 엄밀함을 결합한 알고리즘입니다.

• 핵심 모델: BART (Bayesian Additive Regression Trees):
  • BART는 여러 개의 회귀 트리를 합친 'sum-of-trees' 모델로, 완전한 확률적 구조를 가집니다.
  • BFTS는 각 행동(arm)에 대해 독립적인 BART 사전 분포(prior)를 설정하여, 보상 함수에 대한 정교한 사후 분포(posterior)를 도출합니다.
• 알고리즘 구조:
  1. 초기화 단계: 각 행동을 순차적으로 시도(Round-robin)하여 기초 데이터를 수집합니다.
  2. 톰슨 샘플링 단계: BART 사후 분포에서 모델 파라미터를 샘플링하고, 해당 모델에서 가장 높은 보상을 줄 것으로 예상되는 행동을 선택합니다.
  3. 배치 업데이트(Batched MCMC): 매 라운드마다 MCMC를 실행하는 것은 계산 비용이 너무 크므로, 특정 주기($r(t)$)마다 MCMC를 실행하여 사후 분포를 갱신(Refresh)합니다.
• 행동 인코딩: 각 행동을 독립적인 모델로 다루는 Separate-arm specification을 채택하여, 차원의 저주를 피하고 이론적 분석의 용이성을 확보했습니다.

3. 주요 기여 (Key Contributions)

① 이론적 증명 (Theoretical Guarantees)

• Bayesian Regret Bound: 이상적인(Ideal) BFTS가 정보 이론적 관점에서 $\tilde{O}(\sqrt{T})$의 베이지안 후회(Bayesian regret) 상한을 가짐을 증명했습니다.
• Frequentist Optimality: 'Feel-good' 변형 모델을 통해, 데이터가 특정 매끄러움(smoothness)을 가진다면 빈도주의적 관점에서도 미니맥스 최적성(minimax optimality)을 달성할 수 있음을 입증했습니다.

② 알고리즘 및 구현

• BART의 정교한 사후 분포를 톰슨 샘플링 루프에 직접 통합한 최초의 컨텍스추얼 밴딧 알고리즘을 제시했습니다.
• MCMC의 계산 효율성을 위해 배치 업데이트 스케줄을 도입했습니다.

③ 실험적 검증

• 합성 데이터(Synthetic benchmarks)와 OpenML의 다양한 정형 데이터셋에서 기존 모델(LinearTS, NeuralTS, XGBoostTS 등)보다 우수한 성능을 보였습니다.
• 특히 불확실성 보정(Uncertainty calibration) 능력이 뛰어나, 신뢰 구간(credible interval)이 실제 보상 범위를 정확하게 반영함을 확인했습니다.

4. 실험 결과 및 의의 (Results & Significance)

• 실제 사례 적용 (Case Study): 음주 조절(Drink Less) mHealth 임상 시험 데이터에 적용한 결과, 기존 정책 대비 사용자 참여율(engagement rates)을 30% 이상 향상시켰습니다.
• 해석 가능성(Interpretability): 블랙박스인 신경망과 달리, BART의 트리 분할 확률을 분석함으로써 어떤 변수(예: 앱 다운로드 후 경과일, AUDIT 점수 등)가 의사결정에 중요한 역할을 하는지 파악할 수 있습니다.
• 결론적 의의: 본 연구는 **"완전한 베이지안 비모수 모델(Fully Bayesian Non-parametrics)이 정형 데이터 기반의 컨텍스추얼 밴딧 문제에서 실용적이고 강력한 대안이 될 수 있음"**을 이론과 실증 모두를 통해 증명했습니다.

---

요약 키워드: Contextual Bandits, Thompson Sampling, BART, Bayesian Non-parametrics, mHealth, Regret Analysis.