Active Context Selection Improves Simple Regret in Contextual Bandits

기술적 요약: 능동적 컨텍스트 선택이 컨텍스트 밴딧에서 단순 후회를 개선함

문제 공식화
본 논문은 유한한 컨텍스트 공간 내의 컨텍스트 멀티-암 밴딧 문제를 조사하며, 여기서 컨텍스트는 서로 다른 하위 집단 (예: 인구 통계학적 그룹) 을 나타냅니다. 학습 목표는 컨텍스트 가중 단순 후회로 정의됩니다: 고정된 실험 예산 $T$ 이후, 학습자는 각 하위 집단에 대해 단일 최상의 치료를 추천해야 합니다. 성능 지표는 $k$개 하위 집단 전체에 걸친 인구 분포 벡터 $p$로 가중된 최적 치료와 추천 치료 간의 기대 차이입니다.

본 연구는 두 가지 샘플링 체제를 구분합니다:

1. 수동 샘플링: 컨텍스트는 고정된 분포 $p$에 따라 무작위로 노출되며, 학습자는 치료만 선택합니다.
2. 능동 샘플링: 학습자는 매 라운드에서 하위 집단 (컨텍스트) 과 치료를 모두 능동적으로 선택할 수 있습니다.

분석은 보상 분포에 대해서는 최악의 경우를 가정하지만, 컨텍스트 분포 $p$에 대해서는 인스턴스 의존적입니다. 논문은 수평선 $T$가 치료 수 $n$, 컨텍스트 수 $k$, 그리고 최소 컨텍스트 확률의 역수보다 훨씬 큰 "데이터가 풍부한" 체제에 초점을 맞춥니다.

방법론 및 이론적 프레임워크

• 알려진 $p$에 대한 최적 할당:
  하위 집단 분포 $p$가 알려져 있을 때, 저자들은 실험 예산의 최적 할당을 특징짓습니다. 그들은 최악의 경우 단순 후회 기준에 대해 이력 무관 정책(컨텍스트 선택이 관찰된 이력이 아닌 $p$에만 의존하는 정책) 이 최소최대율을 달성하기에 충분함을 증명합니다.

  • 수동율: 수동 샘플링 하에서 후회는 $\Theta(\sqrt{\frac{n}{T}} \|p\|_{1/2})$로 스케일링됩니다.
  • 능동율: 능동 샘플링 하에서 최적 전략은 확률이 $p_j^{2/3}$에 비례하도록 하위 집단 $j$에 샘플을 할당합니다. 이는 $\Theta(\sqrt{\frac{n}{T}} \|p\|_{2/3})$의 후회율을 달성합니다.
  • 격차: 능동 샘플링 대비 수동 샘플링의 개선 인자는 비율 $R(p) = \|p\|_{1/2} / \|p\|_{2/3}$로 특징지어집니다. 저자들은 매우 불균일한 분포의 경우 이 격차가 $\Theta(k^{1/4})$만큼 클 수 있음을 보입니다. 최적의 능동 할당은 $p$에 비해 더 균일한 분포를 향해 샘플링 확률을 이동시켜, 더 작은 하위 집단에서의 탐색을 증가시킵니다.

• 예산 제한 개입:
  논문은 능동 샘플링이 비용이 드는 상황으로 분석을 확장하여, 학습자가 라운드의 $\alpha$ 비율에서만 하위 집단을 선택할 수 있도록 합니다. 저자들은 할당 $q$가 $q_j \geq (1-\alpha)p_j$를 만족해야 한다는 제약 하에 후회를 최소화하는 제약 최적화 문제를 공식화합니다. 그들은 최적 할당을 위한 임계값 구조를 유도합니다: 예산이 부족하여 개선할 수 없는 경우 $p_j$가 큰 하위 집단은 수동 할당에 머무를 수 있으며, 다른 하위 집단은 $p_j^{2/3}$ 비율을 향해 증폭됩니다. 그들은 완전한 능동 최적율을 회복하는 데 필요한 최소 예산 $\alpha_{\min}(p)$를 식별합니다.

• 알려지지 않은 $p$(EETC 알고리즘):
  $p$가 알려지지 않은 경우, 완전한 능동 정책은 단순히 $p^{2/3}$ 규칙을 채택할 수 없습니다. 저자들은 세 가지 단계를 균형 있게 조정하는 탐색 - 탐색 - 후 결정 (EETC) 알고리즘을 제안합니다:

  1. 초기 수동 탐색: 학습자는 $p$를 추정하기 위해 수동적으로 행동합니다.
  2. 지속된 수동 샘플링: 학습자는 현재 추정에 기반한 최적 능동 할당을 구현하기에 충분한 잔여 예산이 될 때까지 수동 샘플링을 계속합니다.
  3. 결정: 학습자는 추정된 분포를 사용하여 능동 샘플링으로 전환하고 남은 라운드를 할당합니다.
     이론적 분석에 따르면, 큰 수평선에서 EETC는 알려진 $p$를 가진 최적 완전 능동 정책과 동일한 단순 후회율을 달성하며, 이는 상수 인자까지 일치합니다.

주요 결과 및 실험

• 이론적 보장: 논문은 알려진 $p$와 알려지지 않은 $p$ 모두에 대해 엄격한 후회율을 확립합니다. 이는 능동 컨텍스트 선택이 수동 샘플링보다 엄격하게 개선함을 증명하며, 개선의 크기는 컨텍스트 분포의 이질성에 의존합니다.
• 합성 실험: 합성 데이터에 대한 실험은 하위 집단 수 $k$가 증가함에 따라 수동 정책과 능동 정책 간의 후회 격차가 넓어짐을 확인하며, 이는 이론적 $\Theta(k^{1/4})$ 한계와 일치합니다. EETC 알고리즘은 오라클 (알려진-$p$) 능동 정책의 성능과 밀접하게 일치함이 입증되었습니다.
• 실제 데이터 (MovieLens): 저자들은 MovieLens 1M 데이터셋에서 영화 추천을 치료로, 인구 통계학적 그룹을 하위 집단으로 간주하여 방법을 평가했습니다. 결과는 수동 정책이 가장 높은 후회를 산출함을 나타냅니다. 알려진-$p$ 능동 정책과 EETC 모두 수동 기준선보다 현저히 우수하며, EETC는 수평선이 증가함에 따라 오라클 능동 정책의 성능에 접근합니다.

의의 및 주장
본 논문은 실험 설계 및 정책 학습에서 하위 집단을 능동적으로 선택하는 구체적인 가치를 정량화한다고 주장합니다. 주요 기여는 능동 하위 집단 선택이 항상 수동 샘플링보다 성능을 개선함을 보여주는 것이며, 인구 분포가 편향되어 있을 때 그 이득은 상당합니다.

저자들은 그들의 작업이 컨텍스트가 환경적인 표준 컨텍스트 밴딧과 실험자가 샘플을 제어하는 실험 설계 사이의 격차를 메운다고 강조합니다. 최적 할당 규칙 ($q_j \propto p_j^{2/3}$) 을 특징짓고 점근적 최적성을 희생하지 않으면서 알려지지 않은 분포에 적응하는 알고리즘 (EETC) 을 제공함으로써, 논문은 이질적인 인구 집단에서 효율적인 자원 할당을 위한 엄격한 프레임워크를 제시합니다. 이 작업은 타겟 모집이나 통제된 샘플링이 가능한 시나리오에서는 컨텍스트를 선택할 수 있는 능력을 무시하면 최적이지 않은 치료 추천으로 이어질 수 있음을 시사합니다.