다중 클래스 및 희소 컨텍스츄얼 밴딧의 샘플 복잡도

우리는 학습자가 미지의 분포에서 추출된 컨텍스트 (context)를 관찰하고, 유한한 집합 $A$에서 행동 (action)을 선택하며, 밴딧 피드백 (bandit feedback)을 기반으로 주어진 클래스 내에서 근사적으로 최적인 정책 (policy)을 식별하는 것을 목표로 하는 확률적 i.i.d. 설정에서의 컨텍스츄얼 밴딧 (contextual bandits)을 연구합니다. 0-1 보상 (zero-one rewards)을 갖는 밴딧 다중 클래스 분류 (bandit multiclass classification)에서 영감을 받아, 우리는 모든 컨텍스트에 대해 보상 벡터의 $L_1$-norm이 $s \ll |A|$ 이하인 extit{$s$-희소 ($s$-sparse)} 설정에 집중합니다. 우리의 주요 결과는 높은 확률로 정책 클래스 $\Pi$와 비교하여 $\tilde{O} ((s/\epsilon^2 + |A|/\epsilon)\log |\Pi|/\delta)$개의 샘플을 사용하여 $\epsilon$-최적 정책을 출력하는 알고리즘의 설계입니다. 우리는 이 경계 (bound)를 일반적인 Natarajan 클래스로 확장하고, 이에 상응하는 하한 (lower bound) (로그 인자 제외)을 보완함으로써, 추가적인 $\Theta(|A|^9)$ 의존성을 초래했던 이전 연구(Erez et al., 2024, 2025)가 남긴 상당한 격차를 해소합니다. 우리는 두 가지 상호 보완적인 접근 방식을 통해 이러한 결과를 얻습니다. 첫째, 구조화된 관측 (structured observations)을 갖는 컨텍스츄얼 의사결정 (contextual decision making)의 관점에서 컨텍스츄얼 밴딧을 분석하여, 샘플 복잡도가 extit{의사결정-추정 계수} (decision-estimation coefficient; DEC; Foster et al., 2021, 2022)에 의해 결정되는 최적화-기반 탐색 (exploration-by-optimization) 알고리즘을 설계합니다. 우리는 $s$-희소 보상이 있는 경우, 유도된 모델 클래스가 $s$에 따라 확장되고 최적의 속도 (rate)를 직접적으로 산출하는 날카로운 DEC 경계를 허용함을 보여줍니다. 이 접근 방식은 주로 정보 이론적 (information-theoretic)이며 복잡한 min-max 최적화 문제를 해결해야 하므로, 우리는 저분산 탐색 (low-variance exploration) 기술에 기반한 두 번째의 더 전문화된 알고리즘 방법을 개발합니다. 이 접근 방식은 구체적이고 다루기 쉬운 알고리즘으로 이어지며 컨텍스츄얼 조합 세미-밴딧 (contextual combinatorial semi-bandits)으로 자연스럽게 확장되어, 밴딧 다중 클래스 리스트 분류 (bandit multiclass list classification)에 대한 개선된 샘플 복잡도 보장을 제공합니다.