기술 요약: 다중 목적 다중 팔 밴딧을 위한 베이지안 애니타임 파레토 집합 식별

문제 정의

본 논문은 다중 목적 다중 팔 밴딧(Multi-Objective Multi-Armed Bandit, MOMAB) 문제, 특히 **파레토 집합 식별(Pareto Set Identification, PSI)**에 초점을 맞춥니다. 단일 목적의 표준 밴딧 문제들이 누적 보상 극대화(후회 최소화) 또는 단일 최적 팔 식별을 목표로 하는 것과 달리, MOMAB는 여러 개의 잠재적으로 상충하는 목적들을 동시에 최적화해야 합니다. 이 설정에서는 모든 기준에서 최적인 단일 팔이 존재하지 않으며, 대신 최적의 트레이드오프를 나타내는 파레토 최적 팔($P^\star$)들의 집합이 존재합니다.

구체적으로 다루는 과제는 애니타임(Anytime) PSI 정식화입니다. 기존 문헌은 고정 예산(정해진 샘플 수 이후의 오차 최소화) 및 고정 신뢰도(목표 정확도에 도달하기 위한 샘플 수 최소화) 설정을 광범위하게 다루어 왔으나, 사전 정의된 중단 규칙 없이 매 관측마다 유효하고 지속적으로 업데이트되는 파레토 집합 추정치를 제공할 수 있는 알고리즘에는 공백이 존재합니다. 이는 의사 결정자가 경직된 자원 제약이 아닌 신뢰 수준에 따라 실험 진행 상황을 모니터링하고 동적으로 종료할 수 있어야 하는 실제 응용 분야에서 매우 중요합니다.

방법론: Top-Two 파레토 프런트 톰슨 샘플링 (TTPFTS)

저자들은 MOMAB PSI 문제를 위한 최초의 베이지안 애니타임 알고리즘인 **Top-Two 파레토 프런트 톰슨 샘플링(Top-Two Pareto Front Thompson Sampling, TTPFTS)**을 소개합니다. 이 알고리즘은 단일 목적 최적 팔 식별에서의 Top-Two 톰슨 샘플링(TTTS) 원리를 다중 목적 영역으로 확장합니다.

핵심 메커니즘

목적 함수를 선호도 벡터로 스칼라화(scalarization)하는 대신(이는 문제를 단일 목적으로 축소시킴), TTPFts는 파레토 프런트에 직접 작용합니다. 각 타임스텝 $t$에서:

1. 사후 분포 샘플링: 알고리즘은 이력 $H(t-1)$에 조건화된 각각의 사후 분포로부터 모든 $K$개 팔에 대한 평균 보상 벡터 $\tilde{\theta}^{(t)}_a$를 샘플링합니다.
2. 프런트 식별: 이러한 샘플들을 기반으로, 샘플링된 다른 팔에 의해 지배되지 않는 팔들로 구성된 제1 파레토 프런트($F^\star_1$)를 식별합니다.
3. 확률적 선택: 베르누이 시행(Bernoulli trial)과 확률 $\rho$를 통해 어떤 프런트를 탐색할지 결정합니다:
   • 확률 $\rho$로: 제1 프런트($F^\star_1$)에서 균등하게 무작위로 팔을 선택합니다. 이는 현재 최적인 것으로 믿어지는 팔들을 검증하는 데 집중합니다.
   • 확률 $1-\rho$로: 알고리즘은 $F^\star_1$을 제거하고 남은 팔들로부터 제2 파레토 프런트($F^\star_2$)를 식별합니다. 그 후 $F^\star_2$에서 균등하게 무작위로 팔을 선택합니다. 이는 가장 유망한 하위 최적 팔(도전자들)을 탐색하여, 이들이 과소평가되었는지 확인하거나 혹은 확실히 하위 최적인 상태를 공고히 하기 위함입니다.
4. 업데이트: 선택된 팔을 실행(pull)하고, 보상을 관측하며, 이력을 업데이트합니다. 알고리즘은 항상 추천 집합 $\hat{P}^\star_t$(사후 평균의 파레토 집합)를 유지합니다.

이론적 보장

본 논문은 점근적 정확성(asymptotic correctness)(정리 1)에 대한 증명을 제공합니다. 표준 가정(유한한 팔, 일관된 사후 분포, 엄격한 파레토 갭, 충분한 탐색) 하에서, 알고리즘의 추정치 $\hat{P}^\star_t$는 $t \to \infty$일 때 확률 1로 실제 파레토 집합 $P^\star$로 수렴합니다. 이 증명은 TTPFTS가 모든 팔에 대해 거의 확실하게(almost surely) 무한한 탐색을 보장하여, 어떤 팔도 샘플링 과정에서 영구적으로 "동결"되어 배제되지 않음을 입증하는 보조정리 1(Lemma 1)에 기반합니다.

주요 기여

1. MOMAB PSI를 위한 최초의 애니타임 베이지안 알고리즘: TTPFTS는 고정 예산 및 고정 신뢰도 접근 방식 사이의 간극을 메우는 애니타임 알고리즘으로서의 역할을 수행하며, 유연한 대안을 제공합니다.
2. 새로운 불확실성 정량화(UQ) 지표: 저자들은 알고리즘의 현재 파레토 예측에 대한 신뢰도를 추정하기 위해, 실제 정답(ground-truth)에 의존하지 않는 지표를 도입했습니다. 이 지표는 추정된 제1 프런트($\hat{P}^\star_1$)와 제2 프런트($\hat{P}^\star_2$)의 사후 밀도 사이의 **바타차리 오버랩(Bhattacharyya overlap)**을 계산합니다.
   • 오버랩이 높으면 높은 불확실성(최적과 하위 최적을 구분하기 어려움)을 나타냅니다.
   • 오버랩이 낮으면 높은 신뢰도(프런트 간의 명확한 분리)를 나타냅니다.
   • 이 지표는 실시간 성능 프록시 역할을 하여 동적 중단 기준을 가능하게 합니다.
3. 분자 발견(Molecular Discovery)에서의 실제 적용: 알고리즘은 9,400만 개의 후보를 가진 도전적인 초거대 합성 온디맨드 분자 라이브러리 환경에서 검증되었으며, 상충하는 특성(구조적 유사성 및 LogP)을 최적화하는 분자들을 식별하는 능력을 입과 데모했습니다.

실험 결과

합성 벤치마크

TTPFTS는 다양한 파레토 프런트 기하 구조와 차원을 가진 8개의 합성 환경에서 최신 고정 예산 알고리즘(EGE의 Successive Rejects 및 Successive Halving 변형)과 비교 평가되었습니다.

• 성능: TTPFTS는 Uniform Sampling과 EGE-SH 알고리즘을 일관되적으로 능가했습니다. 또한 더 엄격한 애니타임 제약 조건에도 불구하고 모든 환경에서 EGE-SR(가장 강력한 고정 예산 베이스라인)과 대등한 성능을 달utation했습니다.
• 확장성: 행동 공간이 큰 환경(예: $K=200$)에서 TTPFTS는 EGE 변형 모델들을 크게 앞질렀으며, 이는 사후 분포 기반의 할당이 경직된 갭 기반 제거보다 대규모 문제에서 더 효과적임을 시사합니다.
• 강건성: 알고리즘은 약한 사전 가정(균등 사전 분포) 하에서도 우수한 성능을 보였습니다.

분자 발견 사례 연구

9,400만 개의 화합물 라이브러리 탐색에서:

• 효율성: TTPFTS는 데이터베이스의 단 **0.05%**만을 평가하고도 실제 정답 파레토 프런트와 완벽히 일치하는 분자(52개)를 식별했습니다.
• 비교: 이는 Random Search(최적 분자를 하나도 찾지 못함)와 최신 능동 학습 방법인 MolPAL을 모두 크게 능가했습니다.
• 불확실성 상관관계: 제안된 UQ 지표는 Jaccard 지표(정확도)와 강한 음의 상관관계를 보였습니다. 알고리즘이 파레토 집합 추정치를 개선함에 따라 불확실성 지표가 감소하였으며, 이는 해당 지표가 정답 없이도 신뢰할 수 있는 수렴 지표임을 입증합니다.

의의 및 주장

본 논문은 TTPFTS가 실제 파레토 프런트에 대한 지식 없이도 복잡한 다중 목적 환경에서 학습 진행 상황을 모니터링하기 위한 강력한 방법론을 제공한다고 주장합니다. 애니타임 탐색 전략과 새로운 불확실성 정량화 지표를 결합함으로써, 이 연구는 파레토 집합 식별 문제를 정적인 샘플링 작업에서 동적인 의사 결정 지원 시스템으로 전환시켰습니다.

저자들은 이 접근 방식이 의사 결정자들에게 다음과 같은 이점을 제공한다고 강조합니다:

• 파레토 프런트가 충분히 해결되어 실험을 종료할 시점을 동적으로 결정할 수 있습니다.
• 계산 자원과 발견 신뢰도 사이의 트레이드오프를 최적화할 수 있습니다.
• 전수 스크리닝이 불가능하고 선호도가 사전에 알려지지 않은 신약 개발과 같은 실제 시나리오에 이러한 이점을 적용할 수 있습니다.

본 논문은 유한 시간 오차 경계(finite-time error bounds)에 대해서는 다소 겸허한 태도를 취하며, 점근적 정확성은 증명되었으나 명시적인 유한 시간 속도를 도출하는 것은 과거 표준 톰슨 샘플링이 직면했던 과제와 유사하게 여전히 도전적인 과제임을 인정합니다. 그러나 저자들은 점근적 건전성, 강력한 실험적 성능, 그리고 불확실성 지표의 실용적 유용성의 조합이 TTPFTS를 다중 목적 의사 결정의 중요한 진보로 확립한다고 주장합니다.