Multi-Armed Bandits With Machine Learning-Generated Surrogate Rewards

1. 문제 정의 (Problem Definition)

배경:
다중 팔 밴딧 (Multi-Armed Bandit, MAB) 은 불확실성 하의 순차적 의사결정을 위한 널리 사용되는 프레임워크입니다. 전통적인 MAB 알고리즘 (예: UCB, Thompson Sampling) 은 온라인 단계에서 팔을 당겨 얻은 데이터에만 의존합니다. 그러나 실제 응용 분야 (임상 시험, 추천 시스템 등) 에서는 팔을 당기기 전에 풍부한 보조 데이터 (과거 사용자 특성, 히스토리 등) 가 존재하는 경우가 많습니다.

핵심 문제:
기존 연구들은 오프라인 데이터를 활용하려 시도했으나, 대부분 다음과 같은 한계가 있었습니다:

1. 편향 (Bias): ML 모델이 생성한 대리 보상 (Surrogate Rewards) 은 실제 보상과 평균값이 완전히 다르게 (Misaligned) 설정될 수 있어, 단순히 대리 보상의 평균을 기준으로 팔을 선택하면 실패합니다.
2. 외삽 (Extrapolation): 새로운 팔 (새로운 치료법, 새로운 상품) 에 대한 데이터가 오프라인에 존재하지 않아, ML 모델은 외삽에 의존해야 하며 이는 불확실성을 증가시킵니다.
3. 공분산 미지: 실제 보상과 대리 보상 간의 공분산 행렬을 사전에 알 수 없는 경우가 많습니다.

목표:
편향될 수 있지만 실제 보상과 상관관계 (Correlation) 를 가지는 ML 생성 대리 보상을 활용하여, 편향을 보정하고 분산을 줄임으로써 누적 후회 (Cumulative Regret) 를 최소화하는 새로운 MAB 설정과 알고리즘을 제안하는 것입니다.

---

2. 방법론 (Methodology)

저자들은 MLA-UCB (Machine Learning-Assisted Upper Confidence Bound) 알고리즘을 제안했습니다. 이 알고리즘은 다음과 같은 핵심 기법을 사용합니다.

가. 설정 (Setting)

• 온라인/오프라인 데이터: 각 팔 $k$에 대해 오프라인 데이터셋 $\{ \hat{R}^{off}_{k,s} \}$과 온라인 데이터 $(R_{k,s}, \hat{R}_{k,s})$ 쌍을 관찰합니다. 여기서 $R$은 실제 보상, $\hat{R}$은 ML 모델이 생성한 대리 보상입니다.
• 가정: 실제 보상과 대리 보상은 이변량 정규분포 (Bivariate Gaussian) 를 따르며, 평균은 임의로 다를 수 있지만 공분산 행렬은 미지수입니다.

나. ML 보조 평균 추정기 (ML-Assisted Mean Estimator)

전통적인 표본 평균 대신 편향 보정 (Debiasing) 기법을 적용합니다. 이는 예측 기반 추론 (Prediction-Powered Inference, PPI) 에 기반합니다.

• 추정량 $\hat{\mu}^{MLA}_{k,n}$은 다음과 같이 정의됩니다:
  $$\hat{\mu}^{MLA}_{k,n} = \bar{R}_{k,n} - \hat{\lambda}_{k,n} (\bar{\hat{R}}_{k,n} - \bar{\hat{R}}^{off}_{k})$$
  여기서 $\hat{\lambda}_{k,n}$은 분산을 최소화하는 가중치로, 온라인 데이터와 오프라인 데이터의 공분산 구조를 추정하여 계산됩니다.
• 이 추정기는 대리 보상의 평균 편향을 보정하면서도, 실제 보상과 대리 보상의 상관관계를 활용하여 추정량의 분산을 줄입니다.

다. 신뢰 구간 구성 (Confidence Bound Construction)

• 유한 표본 분포 분석: 추정량의 오차를 두 성분 ($S_1$: 대리 보상 평균의 편향 오차, $S_2$: 회귀 절편 추정 오차) 으로 분해하고, 이를 통해 정확한 유한 표본 분포를 유도했습니다.
• t-분포 기반 상한: 분산과 상관관계가 미지수이므로, Student's t-분포의 분위수를 사용하여 신뢰 상한 (Upper Confidence Bound) 을 구성합니다. 이는 기존 UCB 가 사용하는 고정된 상수 대신 데이터에 의존하는 더 정교한 보정 인자를 사용합니다.
• Batched Reward 확장: 실제 적용 시 개별 단위별 데이터가 아닌 배치 (Batch) 단위로 수집되는 경우를 고려하여, 비정규 분포에서도 유효한 신뢰 구간을 제공하기 위해 자기 정규화 중대 편차 (Self-normalized Moderate Deviation) 이론을 적용했습니다.

---

3. 주요 기여 (Key Contributions)

1. 새로운 MAB 프레임워크 제안: ML 생성 대리 보상이 편향되어 있더라도 상관관계만 있다면 활용할 수 있는 새로운 MAB 설정을 정립했습니다.
2. MLA-UCB 알고리즘 개발:
   • 분산과 공분산에 대한 사전 지식 없이도 작동합니다.
   • 편향된 대리 보상을 활용하여 분산을 줄임으로써 후회를 감소시킵니다.
   • 가우시안 가정 하에서 점근적 최적성 (Asymptotic Optimality) 을 증명했습니다.
3. 이론적 성과:
   • 후회 상한 (Regret Upper Bound): 기존 UCB 의 후회 하한보다 엄격하게 개선된 상한을 유도했습니다. 특히, 대리 보상과 실제 보상의 상관관계 $\rho_k$가 0 이 아닐 때, 후회 항의 주된 계수가 $(1-\rho_k^2)$만큼 감소함을 보였습니다.
   • 후회 하한 (Regret Lower Bound): 제안된 알고리즘이 주어진 설정 하에서 최적의 성능을 달성함을 증명했습니다.
4. 비정규 분포 및 배치 처리: 배치 단위 보상과 비정규 분포 데이터에 대한 확장을 통해 알고리즘의 실용성을 높였습니다.

---

4. 실험 결과 (Results)

저자들은 시뮬레이션과 실제 데이터셋을 통해 알고리즘의 성능을 검증했습니다.

• 가우시안 시뮬레이션:
  • 오프라인 샘플 크기 ($N$) 가 증가할수록 누적 후회가 감소하며, 상관관계 ($\rho$) 가 높을수록 감소 폭이 커졌습니다.
  • 상관관계가 0 일 때도 기존 UCB 와 동등한 성능을 보였으며, 상관관계가 존재할 때는 현저히 우수한 성능을 발휘했습니다.
• ML 생성 비정규 대리 보상:
  • 선형 회귀, SVR, 신경망, 결정 트리 등 다양한 ML 모델을 사용하여 비선형 관계를 가진 비정규 분포의 대리 보상을 생성했습니다.
  • 이론적 가정이 엄격하게 성립하지 않음에도 불구하고, MLA-UCB 는 기존 UCB 대비 일관되게 후회를 감소시켰습니다. 특히 예측 정확도 ($\rho^2$) 가 높은 모델일수록 효과가 컸습니다.
• 실제 사례 연구:
  • 언어 모델 선택 (Language Model Selection): 오픈소스 LLM(대리) 과 상용 LLM(실제) 을 비교하는 시나리오에서, 오프라인 데이터를 활용하여 상용 모델 선택의 효율성을 높였습니다.
  • 동영상 추천 (Video Recommendation): KuaiRec 데이터셋을 사용하여 사용자 특성을 기반으로 한 ML 예측을 대리 보상으로 활용, 추천 시스템의 사용자 참여도를 최적화하는 데 성공했습니다.

---

5. 의의 및 결론 (Significance)

이 논문은 다음과 같은 중요한 의의를 가집니다:

1. 데이터 효율성 극대화: 비용이 많이 드는 실제 보상 (온라인 피드백) 을 얻기 전에, 저렴하게 구할 수 있는 ML 예측 (대리 보상) 을 효과적으로 활용하여 탐색 (Exploration) 비용을 절감합니다.
2. 편향에 대한 강건성: 대리 보상이 평균적으로 완전히 틀릴지라도 (Ranking이 틀릴지라도), 상관관계만 있다면 이를 활용하여 분산을 줄일 수 있음을 이론적으로 증명했습니다. 이는 실제 산업 환경 (데이터 드리프트 발생 등) 에서 매우 중요한 통찰입니다.
3. 실용적 적용 가능성: 분산이나 공분산에 대한 사전 지식이 필요하지 않으며, 배치 처리 및 비정규 분포까지 지원하여 실제 시스템 (온라인 광고, 임상 시험, 추천 시스템 등) 에 바로 적용 가능한 알고리즘을 제공합니다.

결론적으로, MLA-UCB는 머신러닝의 예측 능력을 밴딧 알고리즘의 의사결정 과정에 통합하여, 불확실성 하의 의사결정 효율성을 획기적으로 개선하는 새로운 패러다임을 제시합니다.