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

요약

본 연구는 유한한 문맥 공간을 가진 문맥적 다중 팔 밴딧(Contextual Multi-Armed Bandit) 문제에서 능동적 문맥 선택을 통해 단순 후회(Simple Regret)를 개선하는 방법을 다룹니다. 수동적 샘플링 대비 능동적 샘플링이 더 타이트한 후회율을 달성함을 이론적으로 규명하였으며, 문맥 분포를 모르는 상황에서도 최적의 성능을 내는 EETC 알고리즘을 제안합니다.

핵심 포인트

• 능동적 샘플링을 통해 문맥 가중 단순 후회(context-weighted simple regret)를 수동적 방식보다 효과적으로 낮출 수 있음
• 문맥 분포 $p$를 알 때, 특정 할당량($q_j ext{ ∝ } p_j^{2/3}$)을 사용하는 능동적 샘플링이 타이트한 후회율을 달성함
• 문맥의 수 $k$에 따라 최대 $\Theta(k^{1/4})$만큼의 개선 효과를 기대할 수 있음
• 문맥 분포를 모르는 경우를 위해 탐색과 활용의 균형을 맞춘 EETC 알고리즘을 제안하여 이론적 성능을 입증함