능동적 문맥 선택을 통한 문맥적 밴딧(Contextual Bandits)의 단순 후회(Simple Regret) 개선

우리는 유한한 문맥 공간(context space, 일명 하위 집단)을 가진 문맥적 다중 팔 밴딧(contextual multi-armed bandit) 문제를 연구하며, 여기서 학습자는 각 문맥에 대해 최적의 행동을 추천하고 문맥 가중 단순 후회(context-weighted simple regret)로 평가받습니다. 우리의 보장(guarantees)은 보상 분포(reward distributions)에 대해 최악의 경우(worst-case)를 다루는 동시에, 문맥 분포 벡터 $p$에 대해서는 인스턴스 의존적(instance-dependent)인 특성을 유지합니다. 관심 대상인 모집단은 고정되어 있지만 샘플링되는 하위 집단은 제어할 수 있는 실험 설계(experimental design) 문제와 유사하게, 우리는 학습자가 어떤 문맥을 샘플링할지 능동적으로 선택할 수 있도록 허용합니다. 알려진 $p$에 대해, 우리는 타이트한 후회율(tight regret rates)을 규명합니다: 문맥이 무작위로 드러나는 수동적 샘플링(passive sampling)은 $\sqrt{n/T , | p |{1/2}}$ 차수의 후회를 달성하는 반면, 할당량 $q_j \propto p_j^{2/3}$를 사용하는 능동적 샘플링(active sampling)은 타이트한 비율인 $\sqrt{n/T} , | p |{2/3}$를 달성합니다. 결과적인 개선 효과는 $k$가 문맥의 수일 때 최대 $Θ(k^{1/4})$만큼 클 수 있습니다. 우리는 분석을 예산 제약이 있는 능동적 샘플링(budgeted active sampling)으로 확장하여, 그에 상응하는 타이트한 비율을 규명하고, 제한된 능동 예산이 완전한 능동 비율을 회복하기에 충분한 시점을 식별합니다. $p$를 모르는 경우, 우리는 문맥 분포를 추정하는 것과 능동적 할당으로 전환하는 시간 사이의 균형을 최적으로 맞추는 Explore-Explore-Then-Commit (EETC) 알고리즘을 제안하며, 이 알고리즘은 긴 호라이즌(horizons)에 대해 상수 항을 제외하고 알려진 $p$를 사용할 때의 능동적 비율과 일치합니다. 합성 데이터 및 실제 데이터에 대한 실험은 우리의 이론적 발견을 뒷받침합니다.